摘 要：基于伪随机序列的流密码目前仍是国际密码应用的主流。其加密与解密的基本思想以及与图论中一些著名问题相联系的密钥构造方法，对发展学生的信息安全观念、数学素养和数学文化意识具有深远的意义。
关键词：二元流密码；密钥；保密性
《普通高中数学课程标准（实验）》选修系列3—2“信息安全与密码”专题，首先列出了古典密码体制“流密码”（stream cipher）。这种安排既是因为基于伪随机序列的流密码目前仍是国际密码应用的主流，也是因为它利用模的同余方式加密与解密的基本思想不仅有助于学生对纯粹、抽象的数论的应用有所体会，它两种较为通俗的密钥构造方法还与离散数学图论的树形图、哈密顿周游世界问题和欧拉哥尼斯堡七桥问题有联系。这无疑能在培养学生信息安全观念的同时，又对发展学生的数学素养和数学文化意识大有裨益。
1 流密码的起源
流密码的起源可追溯到古典的凯撒（Caesar）密码、维吉尼亚 （Vigenere） 密码和弗纳姆（Vernam）密码体制。流密码利用模的同余方式加密与解密的基本思想起源于凯撒密码。但凯撒密码是一种单表代替密码，其体制存在严重的缺陷：①密钥太少。以英文进行保密通信为例，此时密钥总数只有25个，可能被破译者逐个试密钥的值而被破译。②明文中重复出现的同一个字母在密文中也被替换为相同的字母，易被破译者采用频率统计分析破译。
1586年，法国外交官维吉尼亚用增加密钥长度的方法创立了维吉尼亚密码体制。这种体制使用一个词组作为密钥，因而改变了凯撒密码密钥周期为1的状况，拓展了密钥空间；并使明文中两个相同的字母在密文中被替换为不同的字母，提高了密码的保密性。虽然二百年后这种密码也被英国人巴比奇和德国人卡西斯基破译，但它启示人们，增加密钥序列的周期长度是提高密码体制安全性的有效途径。
1917年，美国电话电报公司的弗纳姆为电报通信设计了一种非常方便的密码——弗纳姆密码，这是一种序列密码。其加密原理是：将明文及密钥分别变换为二进制字符流，然后将明文字符流与密钥字符流位对位地进行模2加（异或）运算得到密文。解密时，则将密文字符流与密钥字符流位对位地进行模2加运算得到明文。但由于弗纳姆密码的关键是生成随机的二元密钥序列，在该体制诞生的20世纪20年代，产生、存储及分配随机密钥序列都存在一定的困难，所以半个世纪以来该体制并没有得到广泛的应用。
1965年，挪威政府的首席密码学家赛尔默（Selmer）提出了移位寄存器理论，这就为研究随机密钥流提供了重要的数学工具。加上20世纪70年代微电子技术的发展，使伪随机序列的产生、存储及分配都有了完善的理论支撑和技术支持。这些理论与技术的合流直接导致了能生成二元周期序列的移位寄存器的诞生，它可以方便而快捷地生成周期长度很大的二元周期序列，并且这种周期序列还具有数字平衡和序列数量多的特性，用其作为密钥，密文破译的难度大为增加。这样，在计算机技术迅猛发展，通讯信息都采用二进制数字序列表示的20世纪下叶，以具有伪随机性的大周期二元序列为密钥的二元流密码体制在密码学各领域得到了广泛的应用。
2 二元流密码的加密与工作原理
在保密通信中，以周期序列为密钥的加密体制被称为序列密码，序列密码亦称为流密码。从表1“密码的分类”中我们看到，流密码是一种对称密码体制。按照密钥流的产生与明密文信息流有关和无关，又分为同步流密码和自同步流密码，目前已有的同步流密码，大多数是所谓二元加法流密码。这种密码体制的密钥流、明文和密文都编码为0，1序列，密钥流zi由其种子密钥k控制密钥流发生器产生，加密原理是将明文流mi与密钥流zi按顺序逐比特进行模2加（异或）运算，产生密文流ci：ci =zimi；解密时则将密文流ci与密钥流zi按顺序逐比特进行模2加运算，得到明文流mi：mi =zici。图1直观地展现出上述过程。图2“二元流密码体制示意图”中，解密方利用加密方通过安全信道传送过来的相同的种子密钥k控制与加密方相同的密钥流发生器，使其输出与加密端同步的密钥流zi，并使用与加密变换相同的解密变换，得到明文流mi。
3 二元流密码的保密性分析
二元流密码的安全程度主要取决于密钥序列的性质，它包括两个方面：一是周期长度，二是随机性。一般地，密钥序列的周期越大，破译就越困难。目前采用的二元流密码，密钥序列的周期至少为230。但又不能无限地扩大周期，因为周期越大，在技术上加密和解密实现起来就越困难。这样，在周期长度一定的情况下，其保密程度就主要取决于它的随机性了。那么，周期长度为l的密钥k1k2…kl满足什么条件，其随机性从而保密性最好呢？
3.1 密钥特征分析与2元n级M序列
为研究的方便，不妨取密钥序列的周期l=8。
考察密钥①：k1k2…k8=10000000与密钥②：k1k2…k8=01111111。易知，在密钥①序列作用下，明文中每8个字符只有1个字符发生了变化；在密钥②序列作用下，明文中每8个字符有7个字符发生了相同的变化。两个密钥序列加密的结果都使得明文字符变化的规律明显而易被破译。看来，字符0，1在密钥中出现的次数相差太大，不利于密码的保密性。这就启发人们，密钥中单个字符0，1出现的次数应该均衡。密钥的单个字符或字符串出现的次数均衡，在统计上称该密钥具有均匀性。
考察密钥③：k1k2…k8=11110000与密钥④：k1k2…k8=11101000，单个字符0，1在它们中都各自出现了4次，具有均匀性，但是密钥④序列加密的密文的保密性显然比密钥③要好，因为经密钥③序列作用的明文，每8个字符中前面4个发生了相同的变化，而后面4个字符不变，呈现某种规律性；而经密钥④序列作用的明文却不具有这种规律性。这就导致了单个字符虽然都具有均匀性的密钥③、④序列，经其作用的密文的保密性仍存在差异。看来，研究密码的保密性能，仅考察单个字符在密钥中出现的次数是不够的。
为进一步研究的需要，我们先来给出一种定义：密码学中，称密钥序列中的单个字符叫长度为1的状态；连续的2个字符叫长度为2的状态；连续的3个字符叫长度为3的状态；…由此，在上述密钥③序列k1k2…k8=11110000中，k1=1，k2=1，k3=1，k4=1，k5=0，k6=0，k7=0，k8=0，知长度为1的状态1和0各出现4次，具有均匀性；k1k2=11，k2k3=11，k3k4=11，k4k5=10，k5k6=00，k6k7=00，k7k8=00，k8k1=01，知长度为2的状态11和00各出现3次，10和01各出现1次，不具有均匀性；k1k2k3=111，k2k3k4=111，k3k4k5=110，k4k5k6=100，k5k6k7=000，k6k7k8=000，k7k8k1=001，k8k1k2=011，知长度为3的状态111和000各出现2次，110，100，001，011各出现1次，不具有均匀性。密钥④序列k1k2…k8=11101000中，长度为1的两种状态1和0均出现4次，具有均匀性；长度为2的四种状态11，10，01，00各出现2次，具有均匀性；长度为3的八种状态111，110，101，010，100，000，001，011各出现1次，具有均匀性。注意到密钥④序列的周期8与长度为1，2，3状态出现的次数4、2、1存在关系；4=8÷21，2=8÷22，1=8÷23，即密钥序列的周期能被21，22，23整除；还注意到此密钥序列由2个字符0，1构成，并且密钥序列的周期8=23。在密码学中，一个由0，1组成的周期l=2n的密钥序列k1k2…kl k1k2…kl…， 如果它对长度为n 的状态具有均匀性，即长度为n的不同状态在k1k2…kn，k2k3…kn+1 ，…，klk1…kn-1中各出现1次，则称它是一个2元n级M序列。显然，密钥④序列11101000就是这样一个周期l=23的2元3级M序列。
3.2 密钥序列的均匀性定理
注意到定义2元n级M序列时，仅对周期l=2n（n≥2）的密钥序列中长度为n的状态作出了规定，但在前面对密钥④的状态分析中我们看到，密钥④对长度为1，2，3的状态都具有均匀性。事实上，一个由字符0，1组成的周期l=2n的密钥序列，如果对长度为n的状态具有均匀性，那么它一定对n-1，n-2， …，2，1的状态都具有均匀性。这是流密码理论的一个基本定理。当取n=3时，它可表述为：若周期l=23的密钥序列k1k2…k8k1k2…k8…对长度为3的状态具有均匀性，那么它对长度为2，1的状态也具有均匀性。
证明如下：
由假设知，在状态k1k2k3，k2k3k4，k3k4k5，k4k5k6，k5k6k7，k6k7k8，k7k8k1，k8k1k2 （A）中，000，001，010，011，100，101，110，111各出现了1次，把（A）中各项最后一个元素去掉，得到八个长度为2的状态：k1k2，k2k3，k3k4，k4k5，k5k6，k6k7，k7k8，k8k1（B）。由于长度为3的各种不同状态在（A）中分别只出现1次，比如000，001分别出现了1次，它们对应于（B）中的字符串就都变为了00，就是说00在（B）中出现了2次；同理，01，10，11在（B）中也出现了2次。这样，长度为3的状态的均匀性就保证了长度为2状态的均匀性。同理，长度为2的状态的均匀性也保证了长度为1状态的均匀性。
3.3 二元流密码的保密性
上述2元n级M序列的定义和密钥序列的均匀性定理都表明：二元流密码密钥序列中0和1的位置排列非常平衡，这就使它具备了一个随机序列必须具备的一个最重要的特性——0、1的平衡性（序列的每个周期段中0和1出现的次数相等或仅相差一次），并且还可从理论上证明它也具备一个随机序列所要求的另两个特性——游程特性，即序列的每个周期段中，长为r的游程（序列的周期段中连续相同的元素段称为游程，例如，周期段中形如“100001”的一段与形如“011110”的一段分别称为长为4的0-游程与长为4的1-游程）占周期段游程总数（2元n级M序列周期段的游程总数为2n-1）的1/2r，且0-游程与1-游程的个数相等或至多相差一个；以及自相关特性（序列的异相自相关系数是一个常数）。对于一个不是真正随机意义下的序列，如果它具有类似于上述的三个特性，就称它是伪随机序列。由上述我们知道，2元n级M序列是一种伪随机序列，所以它不易被破译，具有很好的保密性。
此外，密钥量的大小也是衡量一种密码体制保密性能的重要指标，因为出于安全的考虑，密钥必须经常更换，密钥量大，选择的余地就越大，保密性能就越好。对于2元n级M序列，现已证明了序列的总个数为2，据之，可算得2元3级、4级、5级…M序列的个数分别为2=2，2=16，2=2048…前面我们在分析二元流密码的保密性时已知道，目前采用的二元流密码，其级数n至少在30以上，所以2元n级流密码的密钥量之大也就可想而知了。
参考文献：
[1]教育部.普通高中数学课程标准（实验）[S].北京：人民教育出版社，2003：70-71.
[2]罗启彬，张健.流密码的现状和发展[M].信息与电子工程，2006（1）：75-80.
[3]冯克勤.保密通信的发展概况[J].数学通报，2003（11）：11-14.
[4]毛明，等.大众密码学[M].北京：高等教育出版社，2005：27-29，55-62.
[5]冯克勤.数论与密码[M].北京：科学出版社，2007：17-46.
[6]宋震，等.密码学[M].北京：中国水利水电出版社，2002：5-6，26-33，36-39.
作者简介：
舒春香（1968-），女，汉族 ，江西赣州人，本科，副教授，江西环境工程职业学院教师，主要从事数学教学与研究。