流密码及RC4算法

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

大半学期过去,还没交过作业,上上周密码学老师要我们设计一个流密码当作业这周交。俺刚刚学了比较流行的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

 

Avatar_small
λ 说:
2011年10月22日 14:01

中文加密解密的话,一般也都用二进制码直接输入输出加密解密的,能还原字节就好。

R4的模运算原理一下没看懂……有点复杂。-_-;;;

至于公钥系统那个问题,RSA加密算法最经典了,利用大素数分解的困难来设计的,要证明解密的有效性要了解下欧拉方程。

http://jakwings.is-programmer.com/posts/29107.html

Avatar_small
abellong 说:
2011年10月24日 23:58

@λ: 嗯,听过大素数分解问题,原来是用在公钥系统中啊

Avatar_small
samehere 说:
2016年7月07日 17:52

写的很好,中文也是编码,可以有很多种类的编码,根据不同地区,一般2个字节代表1个汉字


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter