（基础数学专业论文）rc4密钥扩展算法的不动点数分析.pdf

摘要 摘要 本文利用一类双随机矩阵刻画了r c 4 的s 表初始值最的状态转移概率，给 出了此类双随机矩阵的计算公式，在此基础上，进一步算出了r c 4 的密钥扩展 算法的不动点数的数学期望，并给出r c 4 的一个统计弱点。由此看出，r c 4 的 密钥扩展算法的设计是不够完善的。 第一章首先介绍了前人的研究成果，给出了r c 4 的描述，然后给出了双随 机矩阵的定义，使用双随机矩阵描述r c 4 的s 表的初始值鼠的状态转移概率。 第二章得到用双随机矩阵描述r c 4 的状态转移概率的矩阵的计算公式，由 此得到r c 4 的密钥扩展算法的不动点数的数学期望的极限值约为0 8 9 6 3 6 2 。这 说明r c 4 的密钥扩展算法的设计是不够完善的。 关键词：双随机矩阵；不动点；密钥扩展算法；r c 4 ； 状态转移概率矩阵 a b s t r a c t t h ep r o b a b i l i t i e so ft h es t a t et r a n s i t i o n so ft h ei n i t i a lv a l u es o i nt h est a b l eo fr c 4a r ed e s c r i b e db yak i n do fb i s t o c h a s t i cm a t r i c e s ， a n dt h e nac o m p u t a t i o n a lf o r m u l af o rs u c hb i s t o c h a s t i cm a t r i c e si sg i v e n 。 b yw h i c ht h em a t h e m a t i c a le x p e c t a t i o no ft h en u m b e ro ff i x e dp o i n t si n t h ek e ye x t e n d i n g a l g o r i t h mo fr c 4i so b t a i n e d a sar e s u l t ，as t a t i s t i c a l w e a k n e s so ft h ek e ye x t e n d i n ga l g o r i t h mo fr c 4i sp r e s e n t e d i nt h ef ir s tc h a p t e r ，a tf ir s tw ein t r o d u c et h er e s e a r c hq ff in n e y m a n t i na n ds h a m i r ，t h e nw ed e s c r i b et h ek e ye x t e n d i n ga l g o r i t h mo fr c 4 ， w eu s eak i n do fb i s t o c h a s t i cm a t r i c e st od e s c r i b et h ep r o b a b i l i t i e so f t h es t a t et r a n s i t i o n so fi n i t i a lv a l u est a b l eo fr c 4 i nt h es e c o n dc h a p t e r ，w eg i v eac o m p u t a t i o n a lf o r m u l af o rs u c h b i s t o c h a s t i cm a t r i c e s ，b yw h i c hw ep r o v et h a tt h el i m i t i n gv a l u eo f m a t h e m a t i c a le x p e c t a t i o no ft h en u m b e r o ff i x e dp o i n t si nt h ek e ye x t e n d e d a l g o r i t h mo fr c 4i sa b o u t0 8 9 6 3 6 2w h i c hi m p li e st h a tt h ek e ye x t e n d i n g a l g o r it h mo fr c 4i si m p e r f e c t k e yw o r d s ：b i s t o e h a s t i em a t r i x ；f i x e dp o i n t ；k e ye x t e n d i n ga l g o r i t h m ；r c 4 ； s t a t et r a n s i t i o np r o b a b i l i t ym a t r i x 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文 中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意 义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论 文或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 极花 日期：硼挥乡月占日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本 人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单 位仍然为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密醇 ( 请在以上方框内打“4 ”) 论文作者签名： 极毳 日期：谚瞬石月6 日 2 8 引言 引言 密码学是一门即古老又年轻的科学，几乎世界历史上所有文明都使用过密 码：古埃及人，古罗马人，古阿拉伯人可以说，在语言产生之初，人们就需 要以某种方式来保守一些秘密，而当一种文化在文学，科学和语言方面发达到一 定的复杂程度，秘密的，符号性的信息交流也就应运而生了。 军事和外交一直是密码应用最重要的领域。国王，将军，外交官以及阴谋 家们，为了保护自己的信息不被外人所知，使用过行行色色的密码；而为了刺探 于己不利的秘密，他们又绞尽脑汁地破译对手的密码。恺撒更改字母的顺序，纳 粹拥有英钠格玛，我们进行计算机和数字编码，这些试图编制和破译秘密通讯方 法的行为又往往在人类历史进程中演绎着“柳暗花明”、“峰回路转 、抑或“千 古遗恨”。 到了数字化的今天，密码学又有了新的发展：1 9 4 9 年香农发表了一篇题为 “保密系统的通信理论 的著名论文，该文首先将信息论引入了密码，从而把已 有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。该文利 用数学方法对信息源、密钥源、接收和截获的密文进行了数学描述和定量分析， 提出了通用的秘密钥密码体制模型。 需要提出的是，由于受历史的局限，七十年代中期以前的密码学研究基本上 是秘密地进行，而且主要应用于军事和政府部门。密码学的真正蓬勃发展和广 泛的应用是从七十年代中期开始的。 1 9 7 7 年美国国家标准局颁布了数据加密标准d e s 用于非国家保密机关。该 系统完全公开了加密、解密算法。此举突破了早期密码学的信息保密的单一目的， 使得密码学得以在商业等民用领域的广泛应用，从而给这门学科以巨大的生命 力。 在密码学发展的进程中的另一件值得注意的事件是，在1 9 7 6 年，美国密码 学家迪菲和赫尔曼在一篇题为“密码学的新方向 一文中提出了一个崭新的思 想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。但这并不意味 着保密程度的降低因为如果加密密钥和解密密钥不一样。而将解密密钥保密就可 以。这就是著名的公钥密码体制。若存在这样的公钥体制，就可以将加密密钥象 电话簿一样公开，任何用户当它想经其它用户传送- a n 密信息时，就可以从这本 密钥薄中查到该用户的公开密钥，用它来加密，而接收者能用只有他所具有的解 密密钥得到明文。任何第三者不能获得明文。 1 9 7 8 年，由美国麻省理工学院的里维斯特，沙米尔和阿德曼提出了r s a 公 青岛大学硕士学位论文 钥密码体制，它是第一个成熟的、迄今为止理论上最成功的公钥密码体制。它的 安全性是基于数论中的大整数因子分解。该问题是数论中的一个困难问题，至今 没有有效的算法，这使得该体制具有较高的保密性。 随着密码学在各行各业的应用越来越广泛，也随这产生这一些需要解决的 问题。比如，在密码传输过程，由于所要处理的数据量特别大，往往会出现一些 误差，这当然会给用户带来一定的麻烦和损失。正是社会的这一巨大需求促进 了纠错码理论及其工程应用的迅速发展，各种纠错编码以其自动纠正或检测出数 据传输中的误差这一特点，深受各界的青睐。各种功能完备的纠错编码已在实际 工程中得到广泛的应用。按照人们对密码的一般理解，密码是用于将信息加密 而不易破译，但在现代密码学中，除了信息保密外，还有另一方面的要求，即信 息安全体制还要能抵抗对手的主动攻击。所谓主动攻击指的是攻击者可以在信息 通道中注入他自己伪造的消息，以骗取合法接收者的相信。主动攻击还可能窜改 信息，也可能冒名顶替，这就产生了现代密码学中的认证体制。该体制的目的就 是保证用户收到一个信息时，他能验证消息是否来自合法的发送者，同时还能验 证该信息是否被窜改。在许多场合中，如电子汇款，能对抗主动攻击的认证体制 甚至比信息保密还重要。 在密码的生成过程中一个非常重要的环节就是伪随机序列生成器的应用， 无论是什么密码体系，都希望加密得到的密文是一个真正的随机数，但是这种情 况只有在上帝的帮助下才能出现，于是我们为了得到近似随机的密钥，伪随机序 列生成器的应用就至关重要，在密码分析中对一种密码的伪随机序列生成器的分 析也是一中非常重要的手段。 在私钥密码体系中又分为序列密码和分组密码，d e s 和a e s 就是非常著名的 分组密码而r c 4 则为序列密码的代表。 r c 4 是r o nr i v e t s 在1 9 8 7 年为r s a 数据安全公司设计的序列密码算法。作 为无线局域网标准i e e e 8 0 2 1 1 的w e p 协议的一部分。r c 4 主要应用于基于s s l 的安全通信协议。 r c 4 加密算法是r s a 的r o nr i v e s t 在1 9 8 7 年设计的密钥长度可变的流加密 算法簇。之所以称其为簇，是由于其核心部分的s - b o x 长度可为任意，但一般为 2 5 6 字节。该算法的速度可以达到d e s 加密的1 0 倍左右，且具有很高级别的非 线性。r c 4 起初是用于保护商业机密的。但是在1 9 9 4 年9 月，它的算法被发布 在互联网上。r c 4 也被叫做a r c 4 ( a l l e g e dr c 4 所谓的r c 4 ) ，因为r s a 从 来就没有正式发布过这个算法。 r c 4 算法的原理很简单，包括初始化算法( k s a ) 和伪随机子密码生成算法 2 引言 ( p r g a ) 两大部分。假设s - b o x 长度和密钥长度均为为i l 。先来看看算法的初始 化部分( 用类c 伪代码表示) ： f o r ( i = 0 ：i n ：i + + ) s = i ： j = o ： f o r ( i = o ：i n ：i + + ) j = ( j + s + k ) 2 5 6 ； ，r1、 s w a pl s ，sl j j ，： 在初始化的过程中，密钥的主要功能是将s - b o x 搅乱，i 确保s - b o x 的每个 元素都得到处理，j 保证s - b o x 的搅乱是随机的。而不同的s - b o x 在经过伪随机 子密码生成算法的处理后可以得到不同的子密钥序列，并且，该序列是随机的： i = j = o ： w h i l e ( 明文未结束) + + i = n ： j = ( j + s ) n ： s w a p ( s ，s j ) ： s u b _ k = s ( ( s + s j 3 ) n ) ： ) 得到的子密码s u b k 用以和明文进行x o r 运算，得到密文，解密过程也完全 相同。 由于r c 4 算法加密是采用的x o r ，所以，一旦子密钥序列出现了重复，密文 就有可能被破解。关于如何破解x o r 加密，请参看b r u c es c h n e i e r 的a p p l i e d c r y p t o g r a p h y 一书的1 4 节s i m p l ex o r ，在此我就不细说了。那么，r c 4 算法 生成的子密钥序列是否会出现重复呢? 由于存在部分弱密钥，使得子密钥序列在 不到1 0 0 万字节内就发生了完全的重复，如果是部分重复，则可能在不到1 0 万 字节内就能发生重复，因此，推荐在使用r c 4 算法时，必须对加密密钥进行测试， 判断其是否为弱密钥。其不足主要体现于，在无线网络中i v ( 初始化向量) 不 变性漏洞。 而且，根据目前的分析结果，没有任何的分析对于密钥长度达到1 2 8 位的 r c 4 有效，所以，r c 4 是目前最安全的加密算法之一，大家可以放心使用! 本文的主要工作是，首先给出了一类双随机矩阵的定义，用双随机矩阵刻画 了r c 4 的密钥生成过程，使人们更直观的理解r c 4 的密钥生成过程，其次对o 。进 青岛大学硕士学位论文 行分析，因为它的主对角线极限表明了密钥的随机性，而其极限的不是1 可以得 出r c 4 的密钥生成过程是不完善的。 4 第一章对r c a 的描述和双随机矩阵 第一章对r c 4 的描述和双随机矩阵 众所周知，r c 4 在网络协议以及公钥密码体系中有非常多的应用，所以对r c 4 的研究历来都是非常多而且深刻的，本章首先介绍了前人的研究成果，描述了 r c 4 的密钥生成过程，然后介绍了双随机矩阵，并用双随机矩阵刻画了r c 4 的密 钥生成过程。 1 1r c 4 密码的研究史 r c 4 是r o nr i v e t s 在1 9 8 7 年为r s a 数据安全公司设计的序列密码算法。作 为无线局域网标准i e e e 8 0 2 1 1 的w e p 协议的一部分，r c 4 主要应用于基于s s l 安全通信协议的i n t e r n e t 通信与无线通信。r s a 公司宣称r c 4 的加密速度是d e s 的l o 倍。r s ad s i 也宣称r c 4 可以抵抗差分分析与线形分析，没有短循环，具 备良好的非线性。尽管至今没有有效的分析具有充分长密钥( 超过1 2 8 b i t s ) 的 r c 4 的方法，但已有许多文献对r c 4 的攻击方法与弱点进行了分析与研究。 由于r c 4 是一个广泛应用的流密码，从它一出现就吸引了社会的注意。但是， 到目前为止还没有人能找到一个有效的分析方法对r c 4 的p r g a 部分对n = 8 和长 密钥产生威胁，最好的已知的分析需要2 删次来找到它的初始状态。但是，这些 年来发现了r c 4 的许多的有趣的性质。 f i n n e y 列出了r c 4 不能输入的一种状态。这包括所有的j = 口，j = a + l 并且 s a + 1 】- 1 的状态( 这种状态占所有状态的1 n 2 ) 。分析这种类型的状态表明这 些状态是周期为( + 1 ) 的短周期因此这种状态在r c 4 轮操作中式不能够使用 的。因为r c 4 的状态是可以倒推的，并且初始状态f _ j = 0 并不在这种状态里， r c 4 在任何密钥的情况下都不会进入这种状态下。如果r c 4 的初始状态是这种， 那么生成的流就会是一个非常短的周期，而它的原始状态就能很轻松的得到。 r c 4 的大量的内在状态并不是随机的，因此有效的密钥的大小并不能反映它 的安全性。一个好的r e 4 变量安全性的基准是去掉了大量的有初始状态引起的自 相矛盾的输出的“分支和范围分析的时间复杂度。他们是基于“猜测需求”的 范例的。这些分析模拟发生器的过程通过保持所有已知的值和猜n 分支的轨迹， 来继续模拟。这种分析的时间复杂度在，结果与实验数据是一致的。这个分析是 非常低效率的( 例如：比完全搜索典型的密钥大小要差) ，并且只能在n o n t = 2 q m 。当r c 4 使用有z 个字的弱密钥时，固定k 的 ( 刀+ g 。) 比特以1 2 的概率来确定初始序列的o ( g ) 比特还以各种概率( 由他们的长度决定) 确定 输出的前面的值。另外，这个弱点也暗示了r c 4 难以抵抗尝试分析，因此它易受 时间空间数据的分析。 7 青岛大学硕士学位论文 i 2r c 4 的描述 1 2 1 s 表初始值瓯的产生方式： 令r = ( ，) 二1 ，j o = o ，将，个密钥字节，局，i 一。 o ，1 ，2 ，2 1 1 ，可以 是相同的，多次循环排列，构成扩展密钥露= ( 岛) 二1 ，即 k = ( 1 , o i , 1 砖一l k o k , 砖i ) 足( ) 表示r 的第j 个位置的数值。设 五= ( j o + r o ( 0 ) + k o ) m o d 2 “ 则将r 中的两个数r ( o ) 和r o ( ) 交换位置得到墨。 如此继续，设： z = ( z 一。+ 足一。( t - 1 ) + k t 一。) m o d 2 “ 将r 一。中的r 一。( t - 1 ) 着 1r t 一。( 工) 交换位置得到r 。经2 ”次对换后，得到恐， 即为s 表的初始值品。 1 2 2 密钥流序列的产生 假设i d = 五= o 。对于f l ，令 则有置满足： 称 f f = ( f f 一。+ 1 ) m o d 2 , z = ( j l 一。+ 墨一。( i , ) ) m o d 2 4 墨( f f ) = 墨一。( z ) ，墨( z ) = s 一，( ) z f = s ( 墨( ) + 墨( z ) ) l f o ) 第一幸对r c 4 的描述和双随机矩阵 是由k o ，毛，t 一。诱导的密钥流序列。 在本文中，对于，= 2 ”( 并非必要) 使用状态转移概率矩阵来刻画r c 4 的 密码特征。 1 3 双随机矩阵 1 3 1 双随机矩阵 设，岛，砖一。是概率空间( q ，f ，p ) 上取值于z ：。的独立均匀同分布的随机 变量。因为z = ( z 一。+ r 一。( t - 1 ) + k , 一) m o d 2 “，易证 ，f i ，z 是概率空间( g f ，p ) 上取值于z ：。的由k ，墨，砖一。诱导的独立均匀同分布的随机变量。由此得到状态 转移概率矩阵鸠，= 1 ，2 ，2 ” 定理1 3 1 ：设m ，= ( ) ：。，1 = 1 ，2 ，2 “，则 2 t 一专，z = h ； 去，江z 一1 ，。巧：，一1 ； 2 “7 。 0 ； 证明：当，= 1 时，由于1 , o 是取值于z 2 的独立均匀i 司分布的随机变量， 五= ( 矗+ 民( o ) + 毛一) m o d 2 4 = g o ，故 也是取值于z ：。的独立均匀同分布的随机 变量，所以r ( o ) 转移到任意位置的概率为吉，其他位置转移到r ( 0 ) 的概率也 是吉，不动的概率为卜去。又因为k ，毛，乞- 1 是概率空间( q ，f ，p ) 上取值于 z ： 的独立均匀同分布的随机变量 ，可得 z = ( z 一。+ r 一，( f 1 ) + t 一。) m o d 2 “( 1 fs2 ”) ，也是概率空间( q ，f ，p ) 上取值于z ： 的独立均匀同分布的随机变量。类似于，：1 的证明，易知定理成立。 定义1 3 1 ：非负矩阵的每行每列之和都等于1 ，则称其为双随机矩阵。 9 青岛大学硕士学位论文 推论1 3 1 ：m ，= ( ) ：叼。，l = 1 ，2 ，2 “均为双随机矩阵。 证明：不妨设，= 1 。由定理得 证毕。 1 3 2 用双随机矩阵刻画r c 4 密钥生成过程 用 。表示r c 4 的密钥生成过程 七 定义1 3 1 ：o 。= n 鸩。 l = 1 引理1 3 1 ：任意两个双随机矩阵的乘积仍然是双随机矩阵。 证明：不妨设彳；( 吩) 。，召= ( 6 ：f ，) 。是两个双随机矩阵，对任给 l e o ，1 ，2 ，m - 1 ) ，则： = = l ； 一l m lm - im - im l a 巧= = = 1 ； r = 0j = o j - - o r = 0 z 0 推论1 3 2 ： 是双随机矩阵。 例子1 3 1 ：当r t = 2 时，有 m l = l1 44 l 3 44 1 o 4 三 o 4 11 44 o0 三 o 4 o 三 4 m 2 = 1 0 3 1 44 11 44 o 三 4 o 三 4 0o l1 44 三 o 4 o 三 4 仍 仍 】5 c 瓷 ， l k i i i i 一秒 一矿 一 一 l l + + l r ，一r = = 州脚n州匹脚州匹 1 j t i = i l 1 一r 。一矿 矽 z = = ) 舢 咖 f厶间儿f厶瑚 剃脚 勖 州脚 = 吩 脚 剃脚 第一章对r c a 的描述和双随机矩阵 m 3 = 三 o 4 o 三 4 ll 44 0o 1 _ - 4 l - 4 0 0 11 44 l3 44 4 = m l m 2 m 3 m 4 = 显然o 。是双随机矩阵。 ，m 4 圭 6 4 2 5 6 7 5 2 5 6 6 3 2 5 6 5 4 2 5 6 三 o 4 o 三 4 o0 11 44 6 4 2 5 6 5 7 2 5 6 7 2 2 5 6 6 3 2 5 6 6 4 2 5 6 6 0 2 5 6 5 7 2 5 6 7 5 2 5 6 o 三 4 o 三 4 31 44 l1 4 4 6 4 2 5 6 6 4 2 5 6 6 4 2 5 6 6 4 2 5 6 对于刀= 2 时，我们也可以利用枚举的方式直接计算0 。枚举方式为：根据 月c 4 结构枚举，蜀，岛，岛( 2 2 ) 4 - - 2 8 = 2 5 6 种情况：统计状态转移数：将状态转 移数转化为状态转移概率矩阵。易于验证实际统计结果与理论计算结果是一致 的。 但是当雅比较大时，枚举( 2 ”) 2 “种情况计算。是不可能。 青岛大学硕士学位论文 第二章r c 4 密钥生成算法不动点个数分析 加密算法的不动点个数的数学期望是衡量该加密算法安全性的重要密码学 参数之一。众所周知，随机置换的不动点个数的数学期望为l 。因此，一个加密 算法的不动点个数的数学期望越偏离1 ，则该算法的随机性就越弱。比如，在极 端情况下，若一个以b i t s 分组密码算法的不动点个数的数学期望是2 “，此时密 文即为明文，该算法没有随机性，即没有起到加密作用。又如，s m s 4 是基于正 形置换设计的，其不动点个数的数学期望为1 ，因此从该算法的不动点个数的数 学期望来看，其随机性是良好的。基于这种观点，本章研究了r c 4 密码密钥生成 算法的不动点个数的数学期望。 2 1 o 。的计算公式 令 o 。o = ( 引枞 0 t ( 2 ) = 0 t ( 3 ) = z x ( 1 - - x ) x ( 1 一石) 2 工( 1 一x ) 卜1 工( 1 一工) 扣1 工( 1 一工) 扣1 o t ( 4 ) = 其中4 k 2 ”，并且玎2 。 工 x ( 1 一x ) 石( 1 一x ) 2 x ( 1 - 工) 卜1 x ( 1 - x ) x o 一工) ( 1 一工) 0 0 ( 1 一工) 叫2 - k ) z 犯t t k ( 2 n - k m 2 一k ) 定理2 1 1 ：设o 。= 肘。m ：蝇= ( ) r ( 4 七2 4 ，刀2 ) ，则有如下的公式： 1 2 第二章r c a 密钥生成算法不动点个数分析 其中 。1 = ( 0 ，k ) h 。满足： 1 ) 若f _ 1 或，= 七则瞄= 古； 2 ) 若i = 2 和j = 2 ，3 ，k - i 则 卟群兰渤 喏= 古( - 一古) ( - + 古( 一专) 卜卜1 ； 3 ) 当忌为奇数时，对于2 i k 2 + l ，歹 f 。r 孚f 七，j f j | + 2 一i ； 则 当七为偶数时，对于2 f 兰+ l ，j 哮h 2 一，旧+ 争南 溉b ) _ 2 吨一一o 8 9 6 3 6 2 在实际应用中，取靠= 8 ，则有( 专) 。8 9 7 。8 。8 9 ，这说明r c 4 的密钥扩展算 法是不够完善的。 2 l 0， 1 4 q ，、 剃 有 中 然 其 显 结论 结论 本文主要针对r c 4 密码密钥生成算法进行分析。衡量一个加密算法安全性的 一个重要密码学参数之一就是加密算法的不动点个数的数学期望。本文利用双随 机矩阵描述了r c 4 密钥生成算法，并对其不动点个数的数学期望进行计算，从而 得出了r c 4 的密钥生成算法的不安全性。 在第一章中，我们首先给出了r c 4 密码的生成过程，然后给出了双随机矩阵 的定义，随后利用双随机矩阵描述r c 4 的s 表的初始状态的转移。 在第二章中，我们给出了r c 4 的s 表的状态转移概率矩阵的计算公式并给出 了一般性证明，随后得到r c 4 的密钥扩展算法的不动点数的数学期望的极限值约 为0 8 9 6 3 6 2 ，这说明了r c 4 的密钥生产过程是不够完善的。 总之，本文对r c 4 密码的密钥生成算法进行了比较深入的研究，所得到的结 果对人们进一步研究r c 4 密码有一定的启示作用。其中有些问题还有待进一步的 探讨，比如，r c 4 密钥的不完善性会对其密码的产生有什么影响，利用双随机矩 阵能否更清晰的描述密码的生成算法，双随机矩阵的方法能应用于其它的密码研 究么? 参考文献 参考文献 w a a r b a u g h 8 0 2 1 1s e c u r i t yy u l n e r a b i l i t i e s 2 a b i r y u k o v ，a s h a m i r ，a n dd w a g n e r r e a lt i m ec r y p t a n a l y s iso f a 5 1o nap c i nf s e 2 0 0 0 ，2 0 0 0 3l 卅m a ns t a n d a r dc o m i t e e w i r e l e s sl a nm e d i u ma c c e s sc o n t r o l ( m a c ) a n dp h y s i c a ll a y e r ( p h y ) s p e c i f i c a t i o n s ，1 9 9 9e d i t i o n i e e e s t a n d a r d8 0 2 11 ，1 9 9 9 4 h f i n n e y a nr c 4c y c l et h a tc a n th a p p e n ，s e p t e m b e r1 9 9 4 5s r f l u h r e ra n dd a m c g r e w s t a t i s t i c a la n a l y s i so ft h ea l l e g e d r c 4k e y s t r e a mg e n e r a t o r i nf s e 2 0 0 0 ，2 0 0 0 6 s r f l u h r e r ，i m a n t i n ，a n da s h a m i r w e a k n e s s e si nt h ek e y s c h e d u l i n ga l g o r i t h mo fr c 4 i ns a c 2 0 0 1 ，2 0 0 1 7 j d g o l i c l i n e a rs t a t i s t i c a lw e a k n e s so fa l l e g e dr c 4k e y s t r e a m 8 9 g e n e r a t o r i ne u r o c r y p t 9 7 ，1 9 9 7 i m i r o n o v ( n o rs o ) r a n d o ms h u f f l e so fr c 4 i nc r y p t o 0 2 ，2 0 0 2 i m a n t i n t h es e c u r i t yo ft h es t r e a mc i p h e rr c 4 m a s t e r 7 st h e s i s ， t h ew e i z m a n ni n s t i t u eo fs c i e n c e ，o c t o b e r2 0 0 1 h t t p ：| 搠w i s d o m w e i z m a n n a c i l 。i t s i k r c 4 t h e s i s h t m l 1 0l r k n u d s e n ，w m e i e r ，b p r e n e e l ，v r ij m e n ，a n ds v e r d o o l a e g e a n a l y s i sm e t h o d sf o r ( a l l e g e d ) r c 4 i na s i a c r y p t 9 8 ，1 9 9 8 11i m a n t i na n da s h a m i r ap r a c t i c a la t t a c ko nb r o a d c a s tr c 4 i n f s e 2 0 0 1 ，2 0 0 1 1 2s m i s t e ra n ds e t a v a r e s c r y p t a n a l y s i so fr c 4 一l i k ec i p h e r s i n s a c 9 8 ，1 9 9 8 1 3r r i v e s t r s as e c u r i t yr e s p o n s et ow e a k n e s s e si nk e ys c h e d u li n g a l g o r i t h mo fr c 4 t e c hn o t e ，r s ad a t as e c u t i r y ，i n c ，o c t o b e r2 0 0 1 1 4a r o o s a c l a s so fw e a kk e y si nt h er c 4s t r e a mc i p h e r s c i c r y p t p o s t i n g ，s e p t e m b e r1 9 9 5 1 5 a s t u b b l e f i e l d ，j i o a n n i d i s ，a n da d r u b i n u s i n gt h ef l u h r e r ， m a n t i na n ds h a m i ra t t a c kt ob r e a kw e p t e c h n i c a lr e p o r tt d 一4 z c p z z ， a t & tl a b s ，a u g u s t2 0 0 1 参考文献 1 6 b l a h u t ，r ，p r i n c i p l e sa n dp r a c t i c eo fi n f o r m a t i o nt h e o r y ”， a d d is o n w e s l e y ，1 9 8 3 1 7g o li c ，j ，”l i n e a rm o d e l sf o rat i m e v a r i a n tp e r m u t a t i o n g e n e r a t o r 一，i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y ，v 0 1 4 5 ，n o 7 ，p p 2 3 7 4 2 3 8 2 ，n o v 19 9 9 1 8g o l i c ，j ”l i n e a rs t a t i s t i c a lw e a k n e s so fa l l e g e dr c 4k e y s t r e a m g e n e r a t o r ，p r o c e e d i n g so fe u r o c r y p t 7 9 7 ，s p r i n g e r v e r l a g 1 9 k n u d s e n ，l ，m e i e r ，w ，p r e n e e l ，b ，r i j m e n ，v ，a n d v e r d 0 0 1 a e g e ，s ， a n a l y s i sm e t h o d sf o r ( a l l e g e d ) r c 4 ，p r o c e e d i n g so fa s i a c r y p ，r 7 9 9 ，s p r i n g e r - v e r l a g 2 0m i s t e r ，s a n dt a v a r e s ，s ，c r y p t a n a l y s i so fr c 4 一l i k ec i p h e r s ，i n t h ew o r k s h o pr e c o r do ft h ew o r k s h i po ns e l e c t e da r e a si n c r y p t o g r a p h y ( s a c 9 8 ) ，a u g 1 7 1 8 ，1 9 9 8 ，p p 1 3 6 1 4 8 2 1r i v e s t ，r ，t h er c 4e n c r y p t i o na l g o r i t h m ，r s ad a t as e c u r i t y ，i n c ， m a r 1 9 9 2 2 2r s al a b o r a t o r i e sf a q ，q u e s t i o n3 6 3 ， h t t p ：w w w r s a s e c u r i t y c o m r s a l a b s f a q 3 6 3 h t m l 2 3 s c h n e i e r ，b ，4a p p l i e dc r y p t o g r a p h y 。n e wy o r k ：w i l e y 。1 9 9 6 2 4 h f i n n e y a nr c 4c y c l et h a tc a n th a p p e n s e p t e m b e r1 9 9 4 2 5 r j j e n k i n s i s a c ca n dr c 4 t e c h n i c a lr e p o r t ，1 9 9 8 h t t p ：w w w b u r tle n e t b o b r a n d is a a c h t m l 2 60 g o l d r e i c h f o u n d a t i o n so fc r y p t o g t a p h y 1e d i t i o n ，1 9 9 9 2 7 a l g r o s u la n dd s w a l l a c h a r e l a t e d k e yc r y p t a n a l y s i so f r c 4 j u n e2 0 0 0 2 8m i s t e ra n dt a v a r e s c r y p t a n a l y s i so fr c 4 一l i k e c i p h e r s i n s a c ：a n n u a li n t e r n a ti o n a l w o r k s h o p o ns e l e c t e da r e a si n c r y p t o g r a p h y l n c s ，19 9 8 2 9a r o o s ac l a s so fw e a kk e y si nt h er c 4s t r e a mc i p h e r s e p t e m b e r 1 9 9 5 3 0 b s c h n e i e r a p p li e dc r y p t o g r a p h y j o h nw il e y s o n s ，i n c ，t o r o n t o ， c a n a d a ，2e d i t i o n ，1 9 9 6 3 1t i md i e r k sa n dc h r i s t o p h e ra l l e n t h et l sp r o t o c o l ，v e r s i o n1 o i n t e r n e te n g i n e e r i n gt a s kf o r c e ， j a n u a r y 1 9 9 9 r f c - 2 2 4 6 ， 参考文献 f t p ：f t p i s i e d u i n n o t e s r f c 2 2 4 6 t x t 3 2j o v a nd j g o li c l i n e a rs t a t i s t i c a lw e a k n e s s o fa l l e g e dr c 4 k e y s t r e a mg e n e r a t o r i na d v a n c e si nc r y p t o l o g y e u r o c r y p t 9 7 ， v o l u m e1 2 3 3o fl e c t u r en o t e si nc o m p u t e rs c i e n c e ，p a g e s2 2 6 2 3 8 ， k o n s t a n z ，g e r m a n y ，m a y1 9 9 7 s p r i n g e r v e r l a g 3 3l a r sr k n u d s e n ，w il l im ei e r ，b a r tp r e n e e l ，v in c e n tr ij m e n ，a n d s v e nv e r d o o l a e g e a n a l y s i sm e t h o d so f ( a l l e g e d ) r c 4 i na d v a n c e s i n c r y p t o l o g y a s i a c r y p t9 8 ，v o l u m e1 5 9 2o fl e c t u r en o t e si n c o m p u t e rs c i e n c e ，p a g e s3 2 7 3 4 1 ，b e i j i n g ，c h i n a ，o c t o b e r1 9 9 8 s p r i n g e r - y e r l a g 3 4 j o h nk e l s e y ，b r u c e s c h n e i e r ，a n dd a v i dw a g n e r k e y s c h e d u l e c r y p t a n a l y s iso fi d e a ，g - d e s ，g h o s t ，s a f e r ，a n dt r i p l e d e s i n a d v a n c e si nc r y p t o l o g y c r y p t o 9 6 ，v o l u m el1 0 9o fl e c t u r en o t e s i nc o m p u t e rs c i e n c e ，p a g e s2 3 7 2 5 1 ，s a n t ab a r b a r a ，c a li f o r n i a ， a u g u s t1 9 9 6 s p r i n g e r v