流密码及RC4算法

abellong posted @ 2011年10月22日 02:21 in 密码学 with tags RC4 密码学 c , 10877 阅读

大半学期过去，还没交过作业，上上周密码学老师要我们设计一个流密码当作业这周交。俺刚刚学了比较流行的RC4，把自己所学分享出来吧

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