abellong's Blog

原话及翻译(申明: 资料均取自网易公开课视频)
---------------------------
Collaboration policy.This is extremely important so everybody pay attention. If you are asleep now wake up. Like that's going to wake anybody up, right?
 The goal of homework, Professor Demaine and my philosophy is that the goal of hemework is to help you learn the material. And one way of helping to learn is not to just be stuck and unable to solve something, because then you're in no better shape when the exam roles around, which is where we're actually evaluating you. So, you're encouraged to collaborate.

 But there are some commonsense things about collaboration. If you go and you collaborate to the extent that all you're doing is getting the information from somebody else, you're not learning the material and you're not going to do well on the exams. In our experience, students who collaborate generally do better than students who works alone. But you owe it to yourself, if you're going to work in a study group, to be prepared for your study group meeting. And specifically you should spend a half an hour to 45 minutes on each problem before you go to group so you're up to speed and you've tried out your ideas. And you may have solutions to some, you may be stuck on some other ones, but at least you applied yourself to it. After 30 to 45 minutes, if you cannot get the problem, just sitting there and banging your head against it makes no sense. It's not a productive use of your time. And I know most fo you have issues with having time on your hands, right? So, don;t go banging your head against problems that are too hard or  where you don't understand what's going on or whatever. That's when the study group can help out. And, as I mentioned, we'll have homework labs which will give you an opportunity to go and do that and coordinate with other students rather than necessarily having to form your own group. And the TAs will be there. If your group is unable to solve the problem, then talk to other groups or ask your recitation instructor. And, that's how you go about solving them.
 Writing up the problem sets, however, is your individual responsibility and should be done alone. You don't write up your problem solutions with other students, you write up on your own. And you should on your problem sets, because this is an academic place, we understand that the source of academic information is very important, if you collaborated on solutions you should write a list of the collaborators. Say I worked with so an so on this solution. It does not afect your grade. It's just a question of being scholarly. it is a violation of this policy to submit a problem solution that you cannot orally explain to a member of the course staff. You say oh, well, my wrte-up is similar to that other person's, I didn't copy them. We may ask you to orally explain your solution. If you are unable, according to this policy, the presumptions is that you cheated. So do not write up stuff that you don't understand. You should be able to write up the stuff that you understand. Understand why you're putting down what you're putting down. If it's not obvious, no collaboration whatsoever is permitted in exams...

合作原则：这是非常重要的所以每个人都要注意，如果你在打瞌睡，现在醒醒，这样的事会让任何人清醒过来，对吧？
课后作业的目的，Demaine教授和我的观点是，家庭作业的目标是帮你学习这些知识。促进学习的一个办法是不要卡在一道题目上，因为这对你考试的时候没有任何帮助，考试才是检验你真枪实弹水平的地方。所以在做作业时你大可以和别人合作。
但是有一些关于合作的常识问题，如果你合作到所有的信息你都从别人哪里获得的地步，你就什么都学不到你就不能在考试中取得好成绩，依我们的经验，通常合作的学生比单独一个人学习的表现会更好。但是如果要参加学习小组合作学习，你必须保证，你在小组讨论时是做了准备的。讨论之前，每个问题你应该花半小时到45分钟思考，这样你能进步得更快， 而且你已经尝试过了你的想法，你可能解决了一些问题，可能还有一些把你卡住了，但是至少应该让自己有所准备，30到45分钟之后，如果你还是不能解决问题，那你就不要在这个问题上浪费时间了，这是在做无用功，我想大家可以利用这个时间，可以去做点别的什么，对吧？这样的话，就不要在思考难题上浪费时间了，就算完全弄不懂也没有什么关系，此时学习小组可以帮助解决问题，就像我说的那样，我们会有课外实验室，这里可以和其他同学合作来找出答案，不一定非得成立你自己的学习小组，也可以向助教请教，如果你的小组不能解决你遇到的问题，去其他小组尝试下，或请教你的辅导老师。这些都是可以解决问题的方法。
不过，写作业则是你必须独立完成的过程，这是你的责任。你写答案的时候，不能与其他人讨论，你必须独立作出解答。而且在作业上，因为这里是做学术的地方，我们知道学术信息来源是非常重要的，如果是通过合作而得到的解决方案，你应该列出合作者名单，说明合作情况，这不会影响你的评分，这是学术研究的态度问题。如果你不能对授课工作人员完整口述你的问题解决方案，这是明令禁止的。你可能说，好吧，我所写的作业知识和其他人的类似，我没有抄袭别人。我们会要求你口述你的解决方案，如果你不能完成，根据规定，你将被视为作弊，因此，不要写下你不懂的东西。按部就班去完成你所弄懂的，总结解决问题的方法和方式。显然，考试没有合作一说…

ps: 学过c语言的童鞋看这篇文章没难度

一、什么是密码系统及流密码？

密码系统（cryptosystem）是一套用来实现某种形式的加密及解密的算法，他分为两大类：私钥密码系统和公钥密码系统。私钥密码系统是指是指加密者和解密者（可以都是自己呵呵）在某些私有的信息上预先做了约定，来进行加密解密，如果有第三方知道了这私有信息（私钥），加密就没有意义了。公钥密码系统是指发送信息的人用对所有人公开的信息（公钥）来对信息加密后发送，接收方接到信息后用私钥（只有接收方本人知道的）进行解密；加密的算法是公开的，你可能问：难道就不能根据这个算法进行解密？这是公钥系统要解决的问题，即是否存在那样的函数y=f(x)，由x计算y很容易，由y计算x非常困难；我还不知道这些函数有哪些，以后学了再说

私钥密码系统又分为分组密码（block cipher）和流密码(stream cipher)。两者的区别，形象来说，分组密码的转换是固定的，流密码的转换是随“时间”变换而变换的，它像水流一样源源不断的产生。流密码能够流行主要归功于香农对于 “一次一密” 的分析，他证明了“一次一密”几乎“攻不可破”。

一次一密的算法非常简单，假设你需要加密的信息（明文）有n比特长，然后你随机选一个长度为n比特的密码，可以选择的密码有2^n个，然后将明文和密码”相加“，两者都是一个同长度的二进制数，“相加”是指在相同的位进行异或运算（两数字相同时“和”为”0“,不同时“和”为”1“）.要对密文进行解密，只需要将密文和密码“相加”就能得到明文了（可以试试）。如果密码真的是随机取的，第三方想破译，他最多可能需要尝试2^n次，就算信息只有60比特，大家知道的，2^60已经是个天文数字了。所以这方法非常安全。问题是，要记住这个密码可不是易事。解决这个问题的方法就是使用流密码喽。

流密码就是使用较短的一串数字（叫它密钥吧），来生成无限长的伪随机密码流，当然事实上只需要生成和明文长度一样的密码流就够了。一个非常简单的流密码算法是，用6个比特位101100做密钥，将它不断重复得到密码流101100101100101100....直到和明文长度相等，然后将密码流和明文“相加”就得到密文了，解密就是将这个密码流和密文“相加”。简单吧！其实这个流密码算法有个特殊的名称——维吉尼亚密码，当然这里密钥长度可以不是6。用较短的密钥产生无限长的密码流的方法非常多，其中有一种就叫做RC4。

在介绍RC4前，说说那个“相加”运算怎么实现。现在我们把明文的信息限制在ascii码字符集内（它已经能表示所有的英文资料了哈哈），每个字符是一个比特，占8位。假设明文是abc，a、b、c的ascii值分别为97、98、99。二进制形式为01100001、01100010、01100011。密钥流和明文长度一样，假设是sdf，同样可以得到二进制流01110011、01100100、01100110，让他们在对应位做异或运算就可以得到密文了，c语言有^运算符来实现“相加”的操作。我们就直接对字符进行“相加”即a^s, b^d, c^f。得到的结果的二进制形式为00010010、00000110、00000101，它们分别表示ascii码值为18、6、5的字符，在文本编辑器里打开是乱码，没有关系，反正是密文嘛:)

二、RC4

RC4用两步来生成密码流
首先你指定一个短的密码，储存在key[MAX]数组里，还有一个数组S[256]，令S[i]=i。然后利用数组key来对数组S做一个置换，也就是对S数组里的数重新排列，排列算法为

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

第二步利用上面重新排列的数组 S 来产生任意长度的密钥流，算法为

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

output K 一次产生一字符长度（8bit）的密钥流数据，一直循环直到密码流和明文长度一样为止。

产生密钥流之后，对信息进行加密和解密就只是做个“相加”的运算了。

附件是我的c代码，编译得到encrypt可执行文件，在命令行下运行 encrypt 命令（后面必须跟一个纯文本文件名FILE作为参数），然后输入密钥，可将文件FILE进行加密，再次运行并输入相同的密钥可以进行解密，如果前后密钥不同，就不是解密而是进行二次加密了，哈我可以用自己理解的方式来加密信息了:) 这个程序本是针对纯英文文件来加密的，但是文件里有中文时一样可以加解密。不知道c语言对于中文是如何处理的？？

我还没研究RC4的安全性，不知道破译密码难度大不大

附件：https://github.com/abellong/simpleRC4Encryption
参考资料：
http://en.wikipedia.org/wiki/RC4
MJB Robshaw - 1995  Stream Ciphers