RC4程序设计和数据分析比较

1、RC4程序设计和数据分析比较RC4 Programming and Data Analysis Comparison 摘要RC4是RSA公司设计的密钥流生成算法，本文采用Java程序分别实现了RC4算法和线性同余算法，并完成了流密码对应RC4相应的加密解密程序设计。本文还对RC4与在特定情况下的线性同余法进行对比，对运行程序的实验数据进行分析比较，在实验过程中发现RC4本身产生的随机序列与线性同余法的随机序列各有优劣，线性同余法的随机序列整体上均衡性好一些；游程方面，周期在256字节之间RC4比线性同余法更好，大于256字节后则线性同余法更好。关键词：RC4；流密码；随机序列；线性同余法Abs

2、tractRC4 is a key flow generation algorithm designed by RSA company. In this paper, Java programs are used to implement RC4 algorithm and linear congruence algorithm respectively, and the encryption and decryption program design of flow password corresponding to RC4 is completed.This paper also comp

3、ares RC4 with the linear congruence method under specific circumstances, and analyzes and compares the experimental data of the running program. In the experimental process, it is found that the random sequences generated by RC4 have their own advantages and disadvantages compared with the random se

4、quences generated by the linear congruence method, and the random sequences generated by the linear congruence method have better equilibrium on the whole.In terms of running distance, RC4 is better than the linear congruence method when the cycle is between 256 bytes, and better than the linear con

5、gruence method when the cycle is greater than 256 bytes.Key words：RC4; Stream cipher; Random sequence; Linear congruence method目录第一章 绪论11.1 课题背景和意义11.2研究内容2第二章 密码学简介42.1密码学的由来42.2随机数与伪随机数5第三章 实验过程和结果分析73.1 RC473.1.1RC4数据分析及结论83.2线性同余法123.2.1线性同余法数据分析及结论133.3 RC4与线性同余法对比17第四章：总结与展望194.1总结194.2展望20参考文

6、献21致谢22附录23第一章 绪论1.1 课题背景和意义流密码是目前被比较广泛使用的密码，在被使用的同时，密码学学者们也对其不断的研究探讨，最早出现的Vernam密码，具有“一次一密”的特性，Vernam利用产生的随机的不会发生重复的字符对明文进行加密，其产生的密文也具有唯一性，使得密文被使用过一次后，被使用过的密文就不会在其他消息中再次被使用，这就使得密钥个数要与明文长度相等才行，否则明文加密就达不到“一次一密”的效果，因为要使加密达到“一次一密”效果，所以在对密钥的管理分配等方面具有相当大的难度，在后来，“一次一密”的密码体制也被Shannon证明是理论上不可破译的。因为“一次一密”不可被

7、破译，并且其实现难度较大，因为“一次一密”的密钥产生、分配与管理相对困难，在建立一次一密的密码系统时，必须在传输明文的时候交换传输一串与明文长度一样的密钥流，使其使用范围收到了极大的限制，在网络世界中也比较容易产生安全隐患，在保密强度大的情况下，该体制就被舍弃，因此奠定了流密码技术的发展基石，流密码由此而产生，流密码包含的算法产生的序列具有比较强的随机性。流密码包含同步流密码与自同步流密码两类，同步流密码的原理是：由流密码产生的密钥流独立于明文信息，其内部状态只由上一刻的内部状态决定，与传输的明文没有任何关系。它具有信息传输错误率低的特点，即一个符号在传输时候发生错误，也不能够对后面的符号产生

8、影响。自同步流密码与同步流密码相反，它十分依赖明文信息或密文信息，如果在传输时候明文或密文产生了错误，则会严重影响传输的质量。因为原理上的问题，使得该自同步流密码在社会中存在十分稀少，更多的是流密码中的另一类同步流密码。在2000年时候，欧洲提出一个以征集新的流密码方案为目的之一的NESSIE计划，其一直持续到了2003年，在此次流密码征集中，欧洲委员会收到了6个同步流密码算法，0个自同步流密码算法，但是因为这些收集到的流密码算法在安全性方面存在一些问题，所以这些收集到的流密码算法都落选了。在同一时期，日本也提出了与NESSIE相似的计划，把一些密码算法用于政府和工商业领域。在日本提出的计划之

9、后，2004年欧洲又启动了一个新的工程：ECRYPT，在这次的ECRYPT工程中，他们从各个地区中得到了34个流密码算法，这次得到的流密码算法比NESSIE计划多的多。从这里可以看出，当时社会各界对于具有安全性的流密码有多么的渴望，又可能是因为要证明精心设计过的流密码可以与AES算法相比较，甚至在某些方面某些环境下流密码具有超越AES算法的优点。如今在流密码方面主要研究的有两项：1.衡量密钥流好坏的标准通过流密码算法产生的序列能否拥有足够的随机，也就是随机性的强度，对密钥流的好坏具有重要的影响。如果算法越安全，那么其密钥流就越与真随机性相近。2.构造长周期和高复杂度的密钥流序列流密码的设计中密

10、钥流产生器有：钟控序列产生器、基于线性反馈移位寄存器的前馈序列产生器和非线性组合产生器等。在流密码被广泛使用时，与流密码相关的分析攻击逐渐显露，Kerckhoff就根据攻击者是否知道明文、密文等相关信息，把分析攻击分为四种：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击。当然，针对流密码的攻击还有线性攻击、代数攻击等。线性攻击主要是建立统计区分器，通过区分两个不同的概率分布来获得流密码的弱点。流密码的分析与设计是处于保密状态的，之所以处于保密状态，是因为在很多需要用到通信以及其他保密的用途中，流密码价值非常大。因为流密码加密时候密钥长度取决于明文长度，因此流密码具有长度可以根据需要来改变

11、的特点，其运算速度也比较快，在对密文进行传输的时候，其传输的正确率高，出错率低，因为流密码具有以上的优点，所以流密码在如今注重效率和安全的时代，自然而然的成为了密码应用的主流，具有伪随机性的RC4是流密码的重要成员以及代表之一。1.2研究内容本文阐述了密码学的由来、近代密码学和现代密码学发展的事件，介绍流密码从如何产生到被推广的历程。本文一共分为四个章节第一章主要介绍流密码产生的雏形，流密码的种类，流密码在近年来被作为项目的历程以及与流密码相关的分析攻击等。第二章主要介绍了密码学的由来，密码学的发展，密钥随机性的分类，随机数的真伪与产生等。第三章是实验过程与数据分析，此章详细介绍了RC4用ja

12、va的设计流程，指出实现代码时简化的地方，RC4算法实现的流程；详细分析了线性同余法中符合满周期的特定情况，指出了游程、初始值、游程对于线性同余法的影响，对比了RC4与线性同余法的周期、游程和均衡性，并作出了对比结果总结。第四章是总结与展望，此章对本文的研究和数据分析进行了总结，对不足进行了说明，针对不足提出了下一个目标与计划28第二章 密码学简介2.1密码学的由来密码学是研究如何在不被除接受者和发送者以外的人获得传递符号或信息的一门学科。密码学家Ron Rivest曾说过：“密码学是关于如何在敌人存在的环境中通讯”，密码学是一门研究与密码相关的学科，密码的安全性与隐蔽性是重中之重，信息传递也

13、是如此，在传递信息的过程中，能够把信息涵义隐蔽地传递出去也是密码学的重点。密码学最早约于公元前400年产生，密码的使用历史与人类使用文字的历史相当。中国从古代开始就已经有一些用近于密码雏形的通信手段，宋朝时期的曾公亮等编撰武经总要就记载了这么一个和密码学相关故事，在北宋时期，宋朝的某个将领在作战中就用过由40个字组成的五言律诗，把40种作战情况以及要求用在这40个字组成的律诗中，这种用暗含的方式把字表示为作战方式，就已经具有加密体制的特点了。密码形成一门学科的时候是20世纪70年代，计算机在那个时代开始进入高速发展期，密码也逐渐被推动起来，从而形成了一门专门用于计算机科学的密码学学科。因为计算

14、机的高速运算作用，那些研究密码设计的专家们也由此得到极大的便利，他们可以不必在纸上实现繁杂的设计时产生一些不必要的错误。历史上最著名的密码机Enigma于德国1919年设计出，这部密码机层被用于第二次世界大战，因为这台密码机，世界大战时期英国将近有10个月都解读不出德国潜艇所发出的信号的含义。这台密码机属于转轮密码机，虽然转轮密码机加密速度快，但是其密钥量被限制了，在第二次世界大战末期，引出了一场加密与破译加密的对抗风暴。那时候波兰人发现德国所发出的电报中的前几个字母不断重复出现，于是针对其下手，后来破解了Enigma密码机，接着又把如何破译该密码机的方法交给了英国与法国。著名的英国数学家艾伦

15、麦席森图灵带领他的团队们在二战时期通过寻找德国人选择密钥的失误，成功夺得了德军的部分密码本，从而拿到密钥，并且利用明文攻击等手段，破解了大量德军重要情报内容。这一时期属于近代密码学时期。近代密码学这一阶段的开始真正源于香农在二十世纪40年代末期发表的论文。近代密码学在发展历程中最重要的突破是“数据加密标准”（DES）的出现，一方面，它的意义在于密码学从政府走向民间。另一方面，DES密码设计中的思想（S盒等）被后来大部分分组密码采用。现代密码学中，密码体制可以分为对称密码与非对称密码体制，流密码被包含与对称密码体制中，RC4则是流密码的一部分，其可以相对容易地实现对任意长度信息加密。RC4全名是

16、“Rivest Cipher 4”，是密码学家Ron Rivest在1987年间设计发明的RC4加密系统并用于他的公司的商业密码，因此RC4最初为商业秘密。作为商业密码的RC4一直到1994年9月份才被人匿名公开在网络世界中，使得RC4不再为专有的商业秘密，它的泄露无从而知，但是它推动了RC4的使用。RC4算法可以改变密钥长度，以随机置换为基础，产生一个极大的周期秘钥流，使得它加密的信息相对安全，并且该算法的运行速度较快。现代的密码体制有两种，由于密文是通过密钥与明文作用产生的，在加密时候的密钥与解密时候密钥是否相同，在密钥与明文作用产生密文的过程中，能否在这个过程推导出密文与密钥作用的过程，

17、决定了该密码体制是否是对称密钥体制。对称密钥加密又叫作私钥加密，即发送信息的人和接收信息的人利用相同的密钥对明文或密文进行加密或解密。其优点是加解密的速度极快，比较适用于对传送的数据进行加密，这些数据的量也可以是巨大的。2.2随机数与伪随机数随机数在与密码相关的领域中起了很大的作用，现在所使用的很多伪随机算法都是以随机性为目的而产生，随机数是针对随机性实验过后得到的结果。随机性包含两个概念：真随机性和伪随机性。真随机性：指下一个产生的结果无法预测，就如抛硬币一般，它抛出去后的显示的是人头还是数字，这只能猜测，无法真真切切的在看之前得知结果。又如打雷闪电一般，无法知道它下一次雷劈到的具体位置是哪

18、。真随机性具有均匀分布与独立的特性，使得随机数分布一致，在序列中不能由其他数推导出来。产生的随机数具有不可预测性，一般运用于认证、会话秘钥产生等。伪随机性：指通过指定的随机比特样本中，1和0出现的数目相等或无限接近，即“10”“01”这两个的数量应该相等或无限接近，满足这类的数字能使人看起来是随机的。伪随机性具有有边界的特性，因为伪随机数是通过算法，如线性同余法产生随机数，算法是确定的，而且算法是具有范围的，使得产生的序列不具有真随机性，但是一般情况下可以经受随机性的检测。因为真的随机数，很难获取，也很难链接到网络上，所以需要计算机通过算法产生伪随机数。伪随机数生成的算法有很多种，线性同余法在

19、众多的伪随机数生成算法中脱颖而出，它一般用于伪随机数发生器，产生相应的伪随机数供用户使用。线性同余法产生伪随机数中，可以根据特定的取值产生伪随机数。线性同余法在产生伪随机数的时候，其模的值必须尽可能大，因为当模的值太小时，其容易被“肉眼”一眼看出其数据有哪些，这样就不具有伪随机拥有的特性了。RC4中的伪随机序列生成算法也具有伪随机性，RC4一般用于用户传递信息，保证用户传递的信息不那么容易地被他人破译出来。第三章 实验过程和结果分析3.1 RC4RC4算法是在电子信息中的一种加解密技术手段，一般用于各种网络通讯，它是一种密钥长度可变的、面向字节操作的流密码。RC4是一种非线性变换算法，其最重要

20、的部分有两个：密钥编制算法（KSA），伪随机序列生成算法（PRGA）互联网中如今有许多C语言实现的RC4算法，他们都需要两个向量，一个是S，另一个是T，虽然RC4实现中确实需要两个向量，但是把向量T产生过程简化到j产生时刻中也许会简洁些。因此我在用java实现RC4时，简化了向量T产生的步骤。另外，我发现把置换算法写成单个方法更方便使用，这样就不需要在每个模块中都写一次置换操作，写成单个方法后再使用，使得编写效率会更高一点。RC4实现的主要步骤有以下四个：初始化S盒，置换操作，通过伪随机序列生成算法生成密钥流，对明文或密文异或操作。1.一开始生成一个能容纳256字节的S盒，从0到255按照升序

21、赋值于S盒。for (int i = 0; i 256; i+) si = i; 2.接着通过置换操作，使得S盒被打乱，此处为密钥编制算法（KSA），对S盒中的每一个字节都处理一次，共处理256次。每执行一次循环都会使得j产生一个新的值，这个值由密钥和S盒相关，j加上特定时候的S与T相加再模256的到新的j，再对si与sj进行置换操作。i的从0开始改变，每次变化使得S盒中元素都能产生变化，每次产生的j都能保证其具有一定的随机性，遍历了256次后，得到初始的S盒。for (int i = 0; i 256; i+) j = (j + si + key.charAt(i % key.length(

22、) % 256; swap(s, i, j); 此处的key.charAt(i % key.length()在C语言中原本是Ti，TI=Keyi%keylen，简化了向量T后，减少了for循环的使用，使得代码更加简洁。置换算法如下public void swap(Integer s, int i, int j) Integer Temp = si;si = sj;sj = Temp;通过不断变换S盒中原来的值，使其带有一定的随机性。3.打乱S盒后，通过伪随机序列生成算法（PRNG）产生具有伪随机性的密钥流。由于RC4加解密都需要把密钥拓展为256字节，使得密钥流能够与明文或密文进行异或操作。例

23、如密钥为abcd时，它会一直重复密钥n次，直至abcd能够填满256字节。int i = 0, j = 0;for (int k = 0; k plainLength; k+) i = (i + 1) % 256;j = (j + si) % 256;swap(s, i, j);keySchedulk = (char) (s(si + sj) % 256).intValue();该伪随机序列生成算法产生的序列称为伪随机序列，它的原理是不断的变换S盒中值的位置，把si和sj相加获得的值模256，得到S盒中该改变时刻的值输为位密钥流该时刻的值。4.最后通过明文与密钥流异或（xor）产生密文，因为该

24、算法属于对称加密，所以要把密文变成明文，只需要再次把加密的密文与密钥流异或（xor）就能够恢复成明文。for (int i = 0; i clearOrCipher.length(); i+) cipher.append(char) (clearOrCipher.charAt(i) keyScheduli); 3.1.1RC4数据分析及结论(1)满周期S盒是由0至255进行初始排序，再通过KSA对S盒进行打乱，从而产生混乱的序列，因为在S盒中，其内部的数据不重复，通过KSA后也没有产生重复的数据，仅仅是交换si和sj的值，所以此时的RC4的S盒满足满周期的性质，此时RC4的S盒是满周期状态的。

25、在RC4的伪随机序列生成算法中，i与j的获取都与256求余，密钥流的取值也由求余256所得。当明文长度为16、32、64、65536、131072时，得到的随机序列数据：1)明文长度取值为16时：742506546177201114212014777315356812182)明文取值长度为32时：7425065461772011142120147773153568121824619516 229139142201177147151246738 190229653)明文取值长度为64时：7425065461772011142120147773153568121824619516 22913914

26、2201177147151246738 1902296531442242081597362 251148170186159111314517177 97146840193152118169366 1711861171114)明文取值长度为65536时：74250654617720111421201 47773153568121824619516 229139142201177147151246738 1902296531442242081597362 25114817018675177235192251 9921052185239162126199128124 1031322143073254

27、2312372351315)明文取值长度为131072时：74250654617720111421201 47773153568121824619516 229139142201177147151246738 1902296531442242082890 2917922162182221154463798 6566410721018010420134168 224134230163156由RC4的伪随机序列生成算法产生的数据可知，因为S盒的容量为256，所以其值只有256个，当明文输入的长度足够长时，通过伪随机序列生成算法产生的值会发生重复，所以RC4的伪随机序列生成算法不能产生满周期数。(2

28、)游程及均衡性分析对密钥长度取值为5，明文长度分别取值为16，32，64，12865536，131072，以下表3-1-1分别列出了16，32，64，65536,131072的游程：满周期游程161001010111110101000001101110101100011100100111100101010111001001101111111100100110011001111000101000111011010321001010111110101000001101110101100011100100111100101010111001001101111111100011101100100110

29、110001100100111001011111000100001110011010111110111001011000001641001010111110101000001101110101100011100100110111000001110110110001101100011100001100100101010100011000001100110001110110101010011110000101010101110111010111010111011655361001010111110101000001101110101100011100100111100101010111001001

30、101111111100100110011001111000101000111011010111111100110011110000100110101101111010010011111111011100111111011011110101110000011131072100101011111010100000110111010110001110010011110010101011100100110111111110010011001100111100010100011101101010011010001010010000110310101000111000001000011011100110

31、1010001110011100表3-1-1 RC4满周期数与游程从上表3-1-1中可知，当RC4中的伪随机序列生成算法利用明文长度取值为16时，其为0游程的数目为28，1游程的数目为29；明文长度取值为32时，其为0游程的数目为56，1游程的数目为56；明文长度取值为64时，其为0游程的数目为110，1游程的数目为110；明文长度取值为65536时，其为0游程的数目为114983，1游程的数目为114983；明文长度取值为131072时，其为0游程的数目为229547，1游程的数目为229548。另外再使明文长度取值为2的n次方，n4，如下表3-1-2所示：满周期01101628293256

32、56641101101282212212564414415128888881024180018012048359935994096719171928192144001440016384288122881332768574915749265536114983114983131072229547229548表3-1-2 RC4满周期游程数1和0的交替由上述表3-1-1和表3-1-2可知，由RC4中伪随机序列生成算法产生的数据具有伪随机性，0和1的游程数相等或相差1，由此可知，RC4中的算法具有均衡性。3.2线性同余法线性同余法是如今最广泛使用的伪随机数生成算法之一，它是通过对上一个数开始进行运算并

33、取模，即a=c mod m,表示c=mq+a,a范围为0am，随机序列Xn由以下公式产生：其中n0，0am,0cm。当n为0时，X0被称为初始种子或初始值，此时0X0m。在线性同余法中，能否产生相对合格的随机数取决于a，c，m。例如当a=7，c=0，m=36，X0=1时，得到的序列Xn为1，7，13，19，25，31，1，7，13,有此序列得知该序列的周期为6，然而因为m为36,36比6大得多，所以不适合把该序列作为密钥序列。从这里可以得知，应当存在a，c，m取于某值，使得随机数的周期能够与模m相近或相等时，它的周期为接近最大周期或为最大周期。3.2.1线性同余法数据分析及结论（1）满周期1)

34、当取a为5，c为1，m为16时，得到的数据如下：6 15 12 13211 891474510301所得周期为16，与模16相等，无重复数据，属于满周期。2)当取a为11，c为1，m为16时，得到的数据如下12589413011258941301所得周期为8，小于模16，不属于满周期。3)当取a为13，c为1，m为16时，得到的数据如下1471213103896154521101所得周期为16，与模16相等，无重复数据，属于满周期。4)当取a为5，c为1，m为64时，得到的数据如下631281321156256255203758354849541512615059409463942142193

35、2333863604534432457302352526316172247442918278411473653105101所得周期为64，与模64相等，无重复数据，属于满周期。5)当取a为5，c为1，m为65536时，其数据为：631156781390619531321202952916574173352114040165421821091399202993149669295464763577347794423631520810505550501310701 从得到的数据可以发现该周期也为65536，与模65536相等，无重复数据，属于满周期。当更改m为131072时，也得到该周期为13107

36、2，同样属于满周期。再经由多次改变a的值与m的值，我得出了以下结论与规律： c和m互质； m的所有质因子的积能整除a-1； 若m是4的倍数，则a-1也是； a，c是正整数； a满足8n-3，并且m满足2的n次方（n大于等于4）。当满足以上条件时，该周期必定为满周期。（2）游程以及均衡性分析分别取上述满周期时的m值为16，32，64，65536，131072，其中a为5，c为1，如下表3-2-1所示：满周期游程1611101111110011011010111000100111101111001011010110321110111111110011011010111100011001111101

37、011110100100010011110111100101011010100110641110111111110011011010111110001100111111011011110100100101111010100011110000110001110110111111001111011100101110111010001001101110101001011011100010100111101111001001101011010110011065536111011111100111001100001101111101000010100110001001011111110101111000

38、111001101011001100000010111110100001110110111101001010010100100111001110010111001100110011013107211101111110011100110000110111110100001010011000100101110111110101111000101110011010110011010000001011111010000111011011110101001010010100100110011001100110表3-2-1 线性同余法满周期数与游程从表3-2-1中得知满周期为16的0游程的数目为13个，1

39、游程的数目为14个；满周期为32的0游程的数目为25, 1游程的数目为26个；满周期为65536的0游程的数目为245760个，1游程的数目为245761个；满周期为131072的0游程的数目为524289个，1游程的数目为524290个。另外，我获得了以a为5，c为1，m为2的n次方，其中n4的情况下满周期的0与1的游程数据如下表3-2-2所示：满周期01101613143225266480811281921932564484495121024102510242304230520485120512140961126411265819224576245771638453248532493276

40、811468811468965536245760245761131072524289524290表3-2-2 线性同余法满周期游程数1和0的交替从表3-2-1与表3-2-2的数据得知：无论满周期的摸m值大小，其游程0与1总是相差1。所以从数据中可以得到一个结论：在通过特定的条件，如指定a、c为某一值，m为2的n次方，n4，使得线性同余法达到满周期条件，即在周期m内，各个数值都出现且只出现1次，因为各个数值出现的频率相同的，且各数值出现的位置不完全是固定的，所以符合了均匀分布，也符合了均衡性。（3）满周期初始值分析取线性同余法中a、c、m分别为5、1、16，初始值分别为1、2、3，得到的序列值如

41、下图3-2-1所示：图3-2-1 序列5、1、16初始值取线性同余法中a、c、m分别为5、1、32，初始值分别为1、2、3，得到的序列值如下图3-2-2所示：图3-2-2 序列5、1、32初始值取线性同余法中a、c、m分别为13、1、32，初始值分别为1、2、3，得到的序列值如下图3-2-3所示：图3-2-3 序列13、1、16初始值对在确定线性同余法中的周期为满周期，a为定值，只改变模m的前提下，分别对满周期的初始值即X0进改变，得到不同的序列；接着改变a的值，模m不变，再分别改变初始值X0进行实验，从而观察初始值X0的取值对序列有无影响。最初设置了a取值为5，c取值为1，m取值为16与32

42、，设置初始值X0分别为1，2，3，得到序列如图3-2-1和图3-2-2所示；再改变a值，使a值分别为5与13，c取值为1，m取值为32，得到序列如图3-2-2和图3-2-3所示。从3个图可以得知，改变初始值X0只会对值出现的Xn产生移位效果，但是如果以某一定值为标准，则初始值的改变不会对满周期有影响，不会改变原本定好的Xn，因为相对位置还是确定的。如图3-2-1所示的序列，假如取1为定值，1后面产生的数不会因为初始值的改变而使得其不为6，只会使得1的位置由原来X0变为X113.3 RC4与线性同余法对比RC4线性同余法周期取值为16、32、64、65536、131072 当密钥长度为5时：周期

43、取值为16时，序列产生的值无发生重复； 当周期取值为32、64、65536、131072时，序列中的值发生重复 当a取值为5，c取值为1时： 模m取值为16、32、64、65536、131072时，序列中的值无发生重复游程 周期取值为16、32、64、128、256、512、1024、2048、4096、8192、16384、32768、65536、131072时其为0的游程数目为：28，56，110，221，441，888，1800，3599，7191，14400，28812，57491，114983，229547 周期取值为16、32、64、128、256、512、1024、2048、40

44、96、8192、16384、32768、65536、131072时其为0的游程数目为：13，25，80，192，448，1024，2304，5120，11264，24576，53248，114688，245760，524289均衡性 由表3-1-2可知，当密钥长度为5时，明文长度改变，从得到的游程数据可知：部分序列游程0和1游程数相等，部分游程0和1游程数相差1。所以RC4不具有均衡性 由表3-2-2可知，当a取值为5，c取值为1时，改变模m的值与RC4明文长度相等，从的到的游程数据可知：游程0和1的游程数总是相差1。所以线性同余法具有均衡性表3-3-1 RC4与线性同余法比较由表3-3-1可

45、以总结出以下结论：1.在周期方面，RC4中伪随机序列生成算法的周期长度取决于明文长度以及S盒的容量，其明文长度可以无限延长；线性同余法的周期则取决于m，达到满周期需要特殊的a、c、m的取值，达不到特定条件则不能满周期。在此方面RC4比线性同余法好。在周期相等的前提下，RC4的伪随机序列生成算法可以取任意值，其周期不为满周期。在RC4中，虽然S盒中的值不会重复，但是由伪随机序列生成算法产生的密钥流会重复；线性同余法满周期时，其值不会在周期内发生重复。2.在游程方面，在周期相等情况下，当周期在16到256之间，RC4的0游程的数目比线性同余法多，当周期大于256时，线性同余法的0游程的数目比RC4

46、多。这个是由RC4的值最大为256导致的。因此在256字节时，RC4比线性同余法好，当大于256字节后，线性同余法则比RC4更难破解。3.在均衡性方面，在周期相等的情况下，由RC4的伪随机序列生成算法生成的值的游程可知，有部分游程0和1相等，部分游程的0和1相差1，而线性同余法的游程0和1全都相差1，所以线性同余法具有均衡性，RC4的伪随机序列生成算法在均衡性方面比线性同余法差一点，RC4的伪随机序列生成算法则介于均衡性与均匀性之间。4.总体来说，RC4生成的密钥流会因为S盒的容量而被限制，导致密钥数值在一定情况下出现重复，线性同余法在周期内产生的数值则不会出现重复，线性同余法更具有随机性。由

47、于RC4产生的密钥流会出现重复，也就是说会因为上一个的值的影响使得结果发生重复，所以RC4比线性同余法更适合用于传输信息，线性同余法更适合用于产生随机数。第四章：总结与展望4.1总结最初实现RC4时，我对RC4的实现原理还不清楚，在查询部分资料后才知道当密钥长度不足256时，不足的那些空位会由密钥循环填充，例如密钥为1,2,3,4,5，因为该密钥只有5位，故其会一直不断重复这个密钥，即1,2,3,4,5,1,2,3,4,5。RC4和线性同余法一样，都具有伪随机性，但是RC4的随机性相对于线性同余法来说还是没那么好，因为RC4的伪随机序列生成算法中，由于256这个范围与线性同余法模m相比还是相对

48、较小的，并且其密钥序列的生成需要依靠明文，产生的密钥序列会发生重复，线性同余法的周期在满足满周期的条件下可以任意扩大，并且满周期的情况下在周期内不会产生重复的值，RC4密钥具有可延伸性，其明文密钥可以达到相当大的字节，所以在生活中，RC4一般用于通信传输中，对传输的信息进行加解密处理，而线性同余法则更多地用于伪随机数生成器，产生伪随机数，如今也用于短信验证码的生成。在实现代码途中，由于纠结向量T的作用，导致项目的执行效率低下，后来才发现T可以使S盒更具有随机性，使S盒更混乱。在查找的资料中，得知RC4是有可能会受到弱密钥的攻击的，假如使用的密钥为如密钥，那么在十万字节以内密钥流的序列就有很大的

49、可能发生重复，发生重复后，密文的安全性就可能降低，使得密文可能会被破解，而如果达到一百万时，密钥流的序列就会完全重复。此时对密钥进行检测就比较重要了；RC4另一个缺点在于其密钥需要提前传输密钥。虽然其有被破解的风险，但是缺点在优点之前则将近可以忽略：1.根据目前研究的结果，没有任何的数据分析对密钥长度超过128位的RC4有效2.RC4实现相对简单，便于用于软件之中。3.RC4对硬件资源消耗低。线性同余法在学校上课期间就接触过一点，那时候大致了解其实现方法，并且完成了部分的代码。在最初的了解中，只知道满周期是什么，但是对其满周期的条件还相当模糊，仅仅知道周期与模m相等则为满周期，后来才知道当什么

50、条件下才能达到满周期，就如文中所说的，当a取值为8n-3，c为1，m为2的n次方，n4情况下能够使线性同余法达到满周期。这是因为其满足了c与m互质，m如果是4的倍数，a-1也应是4的倍数。在最初的实现线性同余法时，我把其运行产生的结果放在一个文本中，由于是用二维数组实现，所以我可以观察定值为m，变值为a的时候，a对满周期的影响。通过网上查资料，接触到了第一组满周期数据，也就是a为5，c为1，m为16，X0为1，这时候产生的数据少，肉眼可以直接观察。接着我改变m的值，改为20，因为20满足c为4的倍数的条件，发现其不是满周期。我又把数值修改为32，发现其周期刚好为32，这时候我就想，16是2的倍

51、数，32也是2的倍数，且一个是2的4次方，另一个是2的5次方，这之间理论上有联系。在测试了更多组数据后我发现只要是满足2的n次方的数，在a为5，c为1的时候都为满周期。在后来的调试中，仅改变a的值，其他不变，发现改变a的值后，以c为1，m为32为例，当a取值分别为5、13、21时，其周期为满周期，于是我把这些值用于更大的数，例如64、128、256直到65536与131720时，发现这些周期都为满周期，于是总结了a的取值规律：8n-3。线性同余法在实现游程时，一开始用像16、32、64这些数来测试，所以一开始数游程数的时候都人工去数，计算游程的难度相对较小，但是测试相对较大的数据时候，例如上千

52、的数据，则只能去用软件计算游程数，而且用软件计算游程数可以保证无太大误差。线性同余方法速度快，如果对乘数和模数进行适当的选择，可以满足用于评价一个随机数产生器的准则：(1)这个函数应该在重复之前产生出0 到m之间的所有数，例如m为1000时，在发生重复前，1到1000之间所有的数都出现一次； (2)产生的序列应该看起来是随机的；4.2展望在实现毕设过程中，我学到了很多知识，但是也在学习过程中认识到了自己的不足之处，如对时间的分配问题，在实现毕设时，由于已经开始实习了，工作时候只是单纯的工作，导致毕设一直被延期；在编程方面也相对薄弱，整个设计过程中，在游程方面是请教好友帮忙处理游程数的；在数据分

53、析方面，对于线性同余法满周期的分析，并没有更深入的探究除了2的n次方以外的m取值规律，对线性同余法探究的不够彻底。因此在接下来我会对不足之处进行修改以及学习：1.在工作期间也分配好学习时间，不能因工作而丢弃学习2.提高java编程的能力，学习相应的框架以应未来之需3.继续学习密码学及其相关知识，深入研究线性同余法满周期与RC4其他规律参考文献1 梁勇，戴开宇.Java语言程序设计与数据结构M，机械工业出版社，2018.82 韩露露等.一种组合式伪随机数发生器的构造，小型微型计算机系统J，2019.33 陈小松.密码学及信息安全基础M. 清华大学出版社. 2018.104 王方鑫.基于RC4算法分析与研究J, 科技风, 2019.15 刘程远.基于RC4算法的流密码原理与实现J, 信息技术与网络安全,2018.96 侯整风等.RC4流密码算法的分析与改进J，计算机工程与应用，2014.047 赵伟,曹云飞.R