（基础数学专业论文）一类高度随机序列的产生.pdf

摘要 1 9 9 7 年，美国国家标准技术研究所( n i s t ) 在全世界遴选d e s ( 数据加密 标准) 的替代者a e s ( 高级加密标准) ，2 0 0 0 年，比利时的学者d a e 憎n 和剐m e n 的 蹦n d a e l 算法【，】被选中。本文依托停一走序列( 又称钟控序列，参见定义2 3 ) 的 优良的乎台( 高且稳定的周期及线性复杂度) ，借鉴r i j n d a d 算法的部分思路，对 一个停一走序列进行变换与置换，产生了一个高度随机的加密序列，此加密序 列既避免了停一走序列的长游程的弱点，也打破了加密序列仅由。和1 组成的 传统。程序部分将会验证此种加密方法的优点。 关键词：m 一序列；停一走序列；线性复杂度；周期；随机性。 a b s t r a c t 1 1 11 9 9 7 ，t 1 1 en a t i o n a li i l s t i t u t eo fs t a n d a r d sa n d r e d l i l o l o g y ( n i s t ) b e g a nt o 萄f tt h c r e p l a c e l n e n to fd e s ( d a t ae n c r y p t i o ns t a n d a r d ) a e s ( a d v a n c e de n c r y p t i o ns t a n ( 1 a r d ) i nt h ew o r l d i n2 0 0 0 ，t h ea k o r i t h mr 巧n d 捌【1 lo fd a e m e na n dr u m e n ，t h e8 d 1 0 1 盯so fb e l g i u m ，m ss e k c t e d i nt h i sp a p e r ，d e p e n do nt h e b e t t e rp l a t f b r m ( h i g ha n ds t a b l ep e r i o da 肛d l i n e a rc o m p l e ( i t y ) o fs t o p - a n d _ g os e q u e n c e ( a n o t h e rn a m ei sc l o c k - c o n t r o l l e ds e q u e n c e ，s e e d e n n i t i o n2 3 ) ，r e f e r e n c ep a r to fi d e ao ft h ea l g o r i t h mr 封n d a e l ，、et r a n s f b r ma n dp e r m u t et o as t o p a n d _ g os e q u e n c e ，8 0ad e e p _ 8 t o c h a s t i ce n c r y p t i o n s e q u e n c ei sp r o d u c e d t h ew e a k _ n e s so fs t o p - a n d g os e q u e n c e ，l o n gp l a t e 叭l ，i sa v o i d e di nt h i se n c r y p t i o n s e q u e n c e ，a tt h e s a m et i m e ，i tb r e 出渴t h et r a d j t i o no fo n l yoa n dli na ne n c r y p t i o n - s e q u e n c e i t sa d 、随n t a g e sw i ub ev e r i f i e di nt h ep r o g r a mp a r t t i c k e yw o r d ：1 _ 8 e q u e n c e ；s t o p - a n d - g os e q u e n c e ；l i n e a rc o m p l e l ( i t y ；p e r i o d ；s t o c h a s 一 1 l 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者 第一章引言 11密码体制的定义 首先通过一个例子来了解密码体制。 例l ：字母a z 、空格及句号分别用z 。上的o 2 7 代替，我们用一种最简 单的加密体制对明文( ib k em a t h e m a t i c s ) 进行加密： a 明文： 1 i ( er n a t h e m a t i c s b 对明文进行代码转换： 82 6 1 18 1 042 6 1 20 1 974 1 20 1 982 1 82 7 c 对上述代码在磊8 上加l ：92 7 1 29 1 152 7 1 3 12 085 1 3 12 093 1 9o d 得到密文t jm j l fn b u i 鼢l q d t a 这就完成了文字的加密，对文字的解密是加密过程的逆过程： e 密文： j m j 正b u 妇b u j d t a f 对密文进行代码转换： 92 71 291 152 71 312 0851 312 0931 9o g 对上述代码在2 上减l ：82 61 18l o42 61 20 1 9741 2o1 9821 82 7 h 得到明文： i k em 砒h e m 时1 c s 下面我们对密码体制进行定义： 定义1 1 一个密码体制是满足以下条件的五元组( p ，c ，口) ： 1 p 表示所有可能的明文组成的有限集 2 c 表示所有可能的密文组成的有限集 3 k 代表密钥空间，是由所有可能的密钥组成的有限集( 例1 中的c 和g 分别 为一个加密密钥和一个解密密钥，由于二者互逆，我们将它们统称为一个密 钥) 4 对任意的女足，都存在一个加密法则e t 和相应的解密法则靠口并且对 每一个p c 和以：c p ，对任意的明文z p 均有氐( e k ( z ) ) = z 。 1 2相关常识及特定称谓 密码学的基本目的是使得两个在不安全的信道通信的人，通常称为a 1 i c e 和 b o b ，以一种使他们的敌手o s c ”不能明白和理解通信内容的方式进行通信。这 样的不安全信道在实际生活中是普遍存在的，比如电话线、手机短信或计算机 网络。a l i c e 发送给b 0 b 的信息，通常称为明文( p l a i n t e x t ) ，例如语言、数据或 符号。a l i c e 使用预先商量好的密钥对明文进行加密，加密过的明文称为密文 ( c i p b e r t “t ) ，a l i c e 将密文通过不安全的信道发送给b 0 b 。对于敌手o s c a r 来说， 它可以窃听到密文，却无法知道其所对应的明文；而对于b 。b ，由于知道密钥， 可以对密文进行解密，获得明文， 对于明文串及密文串，我们约定用下述方式表达： 明文串：z = z l z 2 强 密文串：g = i 驰v 3 51 3流密码简介 例l 所用的密码体制称为移位密码体制，相当于把所有的字母向右移动1 位但这样的移位至多有2 8 种情况，即密钥空间大小为2 8 ，敌手0 8 c a r 至多尝 试2 8 种情况即可破解密文，所以这样的加密安全性太差 目前广泛使用的密码体制称为流密码( s t r e a n c i p l l e r ) ，其基本思想是产生一 个密钥流：= 郫2 岛， 明文：。麓奶z 2 如， 密文：= e ：。( ) “：。( f 2 ) c ( $ 3 ) 例如我们产生一个易。下的f i h o n ”c i 数列对例l 中的明文进行加密 明文代码：82 6 1 18 1 042 6 1 20 1 974 1 20 1 082 1 82 7 密码流z l l235 81 32 162 754 91 32 2 7189 2 密文代码：92 71 31 11 51 21 1561 81 282 1 1 31 31 532 68 获得密文： n l p i n l 培s r n j n p di 这样的加密是否安全取决于密码流的随机度( 上述f i b o n a c c i 数列的随机度 显然较差) ，我们的目标就是产生一个高度随机的密钥流。这里的高度随机并不 是完全随机，完全随机的密码流虽然易于得到，但解密者( b o b ) 无法知道这个 密钥流，所以这里的高度随机实际上是伪随机的。 1 4d e s 及a e s 简介 这一部分的内容并不是对d e s 及a e s 的具体算法的技术性介绍，而是通 过此简介来了解目前密码学的最新发展概况。 美国国家标准局( n b s ) 于1 9 7 7 年公布了由i b m 公司研制的一种加密算法， 并批准把它作为非机要部门使用的数据加密标准( d a t ae n c r y p t i o ns t a n d a r d ) ，简 称d e s 。自从公布以来，它一直超越国界成为国际上商用保密通信的最常用 加密算法。当时规定d e s 的使用期限为1 0 年，后来美国政府宣布延长它的使 用期，其原因大概有两条：一是d e s 尚未受到严重的威胁，二是一直没有新的 数据加密标准问世。 d e s 使用了s 盒，而s 盒现在已经是几乎所有分组密码算法不可缺少的部 件，但d e s 的s 盒的设计细节始终没有公布，因此被人怀疑设有陷门。这种不 透明的设计显然影响其商用前景。其次，9 0 年代后，对d e s 各种攻击方法纷 纷被提出，穷举搜索是对其攻击的主角，并取得极大突破。 鉴于d e s 的没落，1 9 9 7 年，美国国家标准技术研究所( 其前身为美国国家 标准局) 为了履行其法定职责，发起了一场推选用于保护敏感的联邦信息的对 称密钥加密算法的活动。于是密码界的精英纷纷加入竞争的行列。与此同时， n i s t 制定了用于比较候选算法的评估准则： 安全性 3 成本 算法和实现特性 美国国家标准局推荐使用c 和j a v a 两种语言。对c 实现过程主要测试在 不同的处理器、操作系统、编译器上的实现速度。对j a m 的测试除了关注实现 速度，还关注内存使用情况。 2 0 0 0 年1 0 月2 i ，美国商业部长n o r - r m y m l n e t a 宣布，“m j n d a e l 数据 加密算法”最终获胜， a e s ( a d v a n c e de r y p t i o ns t a n d a r 【：1 ) 应运而生。 第二章理论基础 定义2 1 线性递归序列：设g f ( q ) 上的序列为s 。= s o s ，s 2 如果2 三有 g f ( q ) 上的一组元素( c - ，c 2 ，钆，n ) 满足： 则称s o 。为l 阶线性递归序列。s o s l s 。s c 一。为线性递归关系的初始值。若o = o ， 则称线性递归关系为齐次的；否则为非齐次的。 定理2 1 。】定义2 1 中的钆o 时，线性递归序列是周期序列。n 次不可约 多项式产生的线性递归序列的最小周期整除矿一1 。 定义2 2m 一序列及本原多项式：若g f ( q ) 上的几次不可约多项式生成的 序列的最小周期为q n 一1 ，我们称序列为最大长度序列，又称n 级m 一序列；此 不可约多项式称为礼次本原多项式。 定理2 2 1 4 l 设p 是一个素数，g f ) o ) 是一个关于乘法的循环群。 定义23 停一走序列( 钟控序列) ：设g f ( 2 ) 上的两个n 级m 一序列为： o = o o 1 血2 ；b o 。= 6 0 6 1 6 2 它们的极小多项式分别为，( z ) 和9 ( z ) 。整数函数g ( ) 为 1 g ( 0 ) = o ；g ( t ) = 巩，t = 1 ，2 o = 0 定义停一走序列“。= u o u l 札2 为：产n g 扛o ，1 ，2 ， 引理2 1g f ( 2 ) 上的礼次本原多项式，( z ) 必有：，( z 2 ”1 ) 是g f ( 2 ) 上的不 可约多项式，次数为n ( 2 n 一1 ) ，每个根的阶为( 2 “一1 ) 2 。 证明设，( 。) 的扎个根为：卢，卢2 ，p 铲，卢2 1 ；它们都是g f ( 2 ”) 上的本原元， 方程，( z z “) = o 的解集合就是以下礼个方程： z 2 “一1 = 卢筘，( o 曼j s i 卜1 ) 0 各自解的集合的并。方程z 2 。1 = p 有2 n 一1 个解，记它们为 其中n 为( 2 “一1 ) 2 阶元。注意到 a ，2 ，n 2 1 是不同方程的解；而0 2 ”= q p ； a 卢，( n 卢) 2 ，( a p ) 2 1 是不同方程的解；而( n p ) ”= n p z ； n 口2 ，( q 2 ) 2 ，( q 卢2 ) 2 1 是不同方程的解；而( q p 2 ) ”= n 卢3 o 卢2 。2 ，沁卢2 “2 ) 2 ，( q 卢2 ”2 ) 2 是不同方程的解；而( q 卢2 ”2 ) 2 “= q 。 综上所述，方程，( 。2 “1 ) = o 的解集合就是a 的2 _ 共轭根系。 引理2 1 得证。 定理2 3 停一走序列u 。的极小多项式为，( z 2 “1 ) ，从而线性复杂度为n ( 2 n 一1 ) 最小周期为( 2 “一1 ) 2 。 证明记p = 2 “一1 ，注意到整数函数g ( t ) 满足： g 0 + 巾) = g 0 ) + m 2 “一 设，( z ) = 黑q 一，c 0 = 1 。设e 为时间延迟算子，记b g ( t ) ，则 ，( 驴) 毗= ，( 驴) n g = 黑c 驴。n g n = 叠岛n g ( t 一鲫 = 曼q n g 。2 。一。：量岛j 于2 ”n k ：厂( j f 2 ”。) 。女：，( e ) 2 ”n k ：o t = 0 = 0 因此，( 一”1 ) 是的一个特征多项式。由引理2 1 ，定理得证。 6 第三章新序列的生成算法 本节依程序运行的次序逐一介绍各子程序的算法。 算法1 ：o o o 及6 0 0 的产生 首先用程序挑选一个g f ( 2 ) 上的5 次本原多项式：这里我们定为，( z ) = 1 + z + z 2 + z 3 + 护，即s = s ，一1 + 岛一2 + 勺一3 + s 一5 ，( j 5 ) 用1 3 1 代表不同的初始向量，规则是将这3 1 个数转化为长为5 的二进制 数，比如 l 一0 0 0 0 1 ；2 0 0 0 1 0 ；3 1 1 1 1 1 1 。随意挑选l 一3 1 中的两个( 可以相同) ， 记为n ，、n 2 ，用以产生o m 及6 0 0 此算法对应源程序中的h l r s g e n e r a t o r ( ) 函 数。 算法2 ：停一走序列u 。0 的产生 扎。的产生方法为：用护控制o 。，见定义2 3 。源程序中的相应函数为s t o p a n d g o g e n e r a t o r ( ) 。u 。的最大缺点是长游程过多过长。 算法3 ：深加密程序1 为了克服“。长游程过多过长的缺点，我们产生一个。和1 分布相对均匀 的序列”一；并用口。和u 。相加( g f ( 2 ) 上) ，得到一个。和1 分布相对于“o 。 来说较为理想的序列训。 ”o 。的产生办法为：定义两个数组( 序列的另一种称谓) 护、e 。o ，周期分别为1 3 和1 7 ：初始向量分别为 o ，o ，1 ，o ，1 ，o ，1 ，1 ，o ，1 、o ，o ，1 ) 和 1 ，o ，1 ，1 ，o ，o ，1 ，1 ，o ，1 ，o ，1 ，o ，1 ，o ，1 ，1 ) ； u 。= d o d l d 2 d 3 恕! ：塑d 】d 2 d 3 d 4 皂三：生d z d s d 4 d 5 1 1 暨兰! 如d 4 4 5 d 6 = 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 l o l 0 1 1 0 0 0 1 0 1 这一部分对应源程序中的函数v o i dd e e p l o c l ( 1 ( ) 。 训。为：vi o ，毗= ( u 汁仇) ( m o d 2 ) 。这一部分比较简单，设置在主函数 i n a i l l ( ) 中。 之所以让。o = “。蜘。，是想继承u ”的优良、稳定的线性复杂度及周期与 7 ”。良好的o 、1 分布特性。 算法4 ：深加密程序2 这一部分是整个程序的核心。 在已发表的论文三元树上的线性递归序列【”】中，我将g f ( 2 ) 上的序列 置换为磊上的最长游程为2 的序列，并对这一序列的构造及特性作了详细的 分析。 在设计论文程序时，我对厥来的构造作了一些调整，因为：我们对一个字 符或数字进行加密时，一般是对这些字符或数字所对应的代码加上一个两位 数，但忍上的两位数仅有9 种情况：0 0 、吡、0 2 、1 0 、1 1 、1 2 、2 0 、 2 1 和2 2 。也就是说：任一明文字符或数字在这一体制下所产生的密文仅有9 种，敌手在解密时将有机可乘，所以我将历的序列改为蜀。上的序列，即数字 。一9 均会出现在序列z m 中，这样加密序列z ”的随机性更好。 我们将“，o 。这一。一1 序列置换为而。上的序列z 。其中z o 。的最长游程仅 为2 。 伽。转化为茁。的方法如下：首先将”从伽。开始每四个分成一组； 。一( 札o 训1 州2 叫3 ) ( 叫4 叫5 叫6 7 ) ( 鲫8 伽9 1 0 1 1 ) 每一组均可写成训4 。叫4 件1 4 件2 4 h 3 的 形式。其中i o ，i z 。 再将i 分为3 种情况：i ( m o d 3 ) = o ；i ( m o d 3 ) 兰1 ；i ( m o d 3 ) i 2 。 u o o o _ 1 4 1 4 0 1 0 1 8 0 7 5 1 0 1 1 3 4 9 i ( - n o d 3 ) = o 的置换情况 0 0 0 1 2 1 3 1 0 0 1 6 8 9 l1 0 1 * 4 8 9 0 0 1 0 + 5 6 2 3 0 1 1 0 4 3 6 0 1 1 l o 7 4 2 7 0 1 0 0 _ 7 3 l 1 0 1 0 6 7 9 7 1 1 l l 8 3 2 4 i ( r n o d 3 ) ；1 的置换情况 1 0 0 0 2 7 3 11 0 0 4 9 8 ( ) ( ) 1 1 2 0 5 0 0 1 1 1 9 2 7 0 0 0 0 _ 5 6 4 50 0 0 1 _ 7 5 10 0 1 0 _ 3 1 6 0 叭0 0 _ 6 4 61 0 0 0 _ 6 1 60 0 1 1 _ 2 7 2 7 0 1 0 1 6 0 1 61 0 0 1 8 6 4 0 1 1 0 一7 1 6 1 0 1 0 3 6 2 1 1 0 0 4 7 9 00 1 1 1 3 5 4 5 8 z ( m o d 3 ) ；2 的置换情况 o 0 0 0 9 8 7 0 0 0 l 一2 9 8 30 0 1 0 4 6 3 20 1 0 0 0 7 4 1 0 0 0 0 1 2 30 0 1 1 _ 1 0 5 6 0 1 0 1 2 5 61 0 0 1 7 1 70 1 1 0 4 3 5 81 0 1 0 _ 9 8 4 91 1 0 0 _ 8 3 50 1 1 1 _ 4 0 7 1 0 l l 一8 2 4 1 1 0 1 6 2 1 21 1 1 0 5 1 2 3 1 l l l 一5 3 1 假设”。= 伽。叫1 耽训3 毗鹕姚嘶训8 蚴叫，。1 1 = 丽面( 0 0 0 0 ) q q 2 9 命( 1 1 1 1 ) 三三旦 则俨矗( 5 6 4 5 ) 够商( 4 6 4 ) $ 注意到z 。的长游程至多为2 ，因为上述蜀。上的置换代码均为l 游程， 仅可能在接口处产生2 游程，例如：1 2 3 4 与4 5 6 7 在接口处产生一个2 游程 1 2 3 生蛎6 7 。 这一部分对应源程序的v o i dw t h a n s f 0 咖( ) 函数。 算法5 ：字符转化为数字 c h 材一t o _ i n t t r a n s f o r m ( ) 函数将接受一段包含a z 、空格、逗号( ，) 、句号 ( ) 及问号( ? ) 这3 0 个字符的文字，并将它们转化为：o o 2 9 ，即a 0 0 ， b _ 0 1 ? _ 2 9 。 算法6 ：数字转化为字符 v o i di n t t o c 1 1 a r ( ) 函数将接收一个元为0 2 9 的数组，并按。一a ，1 一b 2 9 一? 的方式将整数数组转化为字符。 算法7 ：周期测试 i n t i i o d t e s t ( ) 函数接收一个测试上限m 和一个整数数组( 序列) o 1 ， 并测定其周期。方法如下： 变量丁的初值为l ，i 为数组n 的下标，i 的初值为o ； 如果。闭= n _ + 卅：i + + ； 如果o 【t n 口+ 习：t + + ； 江m 时，停止。 算法8 ：浅加密程序1 9 i n t8 h a l l o w l o c k l ( ) 函数接收一个1 3 1 的整数n 1 ，素数p 1 = 1 0 9 3 9 ，七1 = 5 2 1 令女吲1 = ( n ? 1 - 2 + 七1 ) ( m o d p l ) ，显然，由定理2 2 ：( 七e y l 一1 ) ( n l o d p l ) 是n 1 在 模p 1 下的逆。 算法9 ：浅加密程序2 i n ts h a h o w l o c k 2 ( ) 函数接收一个1 3 1 的整数n 2 ，素数p 2 = 1 3 8 3 l ，七2 = 3 8 8 9 ， 令七e 2 = ( n 9 2 2 + 后2 ) ( m o d p 2 ) 。 算法1 0 ：浅加密程序3 i n ts h a l l o w l o c 蝌涵数接收一个。一5 0 0 的整数6 e 9 i n p o s 僦o n ，素数p 3 = 1 6 2 6 7 ， 七3 = 2 7 6 9 ，令七e 3 = ( 6 e 9 i n z ) 0 5 i t i 。帆p 3 2 + 后3 )( m o dp 3 ) 。 算法1 1 ：解密程序1 i n tu n l o c k l ( ) 函数接收整数k e 口1 ，作如下运算： ( 七叫1 一1 ) ( m o dp 1 ) 】，1 。 m o d ( p 1 ) 并返回此值，易知此值恰为n 。 算法1 2 ：解密程序2 i n tu n l o c k 2 ( ) 函数接收整数后e 2 ，作如下运算： n 2 = 【( k e 2 一岛2 ) ( m o dp 2 ) 】9 2 2 ) m o d ( p 2 ) 算法1 3 ：解密程序3 i 1 1 t u n l o c k 3 ( ) 函数接收整数e ”3 ，作如下运算： 沈口i n - p i 挽d n = ( ( 七e 3 一自3 ) ( m o dp 3 ) 】弗_ 2 m o d ( p 3 ) 1 0 第四章程序演示 我们以一个例子来介绍整个加密( 解密) 程序的运行步骤：我们以n - 。8 ， n 2 ：2 3 ，b e 9 讥一p d s 捌m = 8 0 为例 e pj ： 输入整数8 ，它的五位二进制表示为：0 1 0 0 0 ，以( 0 1 0 0 0 ) 为初始向量， 调用函数h l r s g e n e r a t o r ( ) ，产生一个以2 5 1 = 3 1 为周期的序列n 。：它的前 3 l 位为： n 。：0 1 0 0 0 0 1 1 0 0 一1 0 0 1 l 一1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 印2 ： 调用函数i n ts h a l l o w 一1 0 c k l ( ) ，计算出七e 1 = 8 1 。9 3 7 + 5 2 1 ) ( m o d l 0 9 3 9 ) = 7 3 5 8 ， 返回主函数。 s t 印3 ： 输入整数2 3 ，它的五位二进制表示为：1 0 1 1 1 ，以( 1 毗1 1 ) 为初始向量， 调用函数h l r s g e n e r a t 。r ( ) ，产生一个以3 1 为周期的序列铲：它的前3 1 位 为： b 。：1 0 1 1 1 0 0 0 1 0 一1 0 1 1 0 一1 0 0 0 0 1 1 0 0 1 0 0 1 l l 一1 e p4 ： 调用函数i n ts h m l o w l o c k 2 ( ) ，计算出e 2 = 2 3 1 3 8 2 9 + 3 8 8 9 ) ( m o d l 3 8 3 1 ) = 2 0 8 5 ， 返回主函数。 s t e p5 ： 调用函数s t 。p a n d g 。一g e n e r a t 。r ( ) ，用铲控制8 。，产生停- 走序列札。， 方法如下 g ( 0 ) = 0 ；+ c l o = o g ( 0 1 = n o = o g ( 1 ) = 6 0 = 1 ；“1 = n g ( 1 ) = n 1 = 1 g ( 2 ) = g ( 1 ) + 6 1 = 1 + o = 1 ；札2 = g ( 2 ) = n l = 1 g ( 3 ) = g ( 2 ) + 6 2 = 1 + 1 = 2 ；u 3 = g ( 3 ) = 2 = o g ( 4 ) = g ( 3 ) + 6 3 = 2 + 1 = 3 ；“4 = n g ( 4 ) = 0 3 = o g ( 5 ) = g ( 4 ) + 6 4 = 3 + 1 = 4 ；“5 = 血g ( 5 ) = 0 4 = o g ( 6 ) = g ( 5 ) + 6 5 = 4 + o = 4 ；“6 = n g ( 6 ) = n 4 = o g ( 7 ) = g ( 6 ) + = 4 + o ：4 ；u 7 = n c ( 7 ) = n 4 = 0 我们从程序的运行结果中截取前8 0 位，u 0 。：0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 l o 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 ，u o 。的长游程过多过长的弱点 一目了然。 s t 印6 ； 调用函数i tp e r i o d t e s t ( ) ，测试札。的周期，测试结果为9 6 1 。 印7 2 调用函数v o j dd e 印一l o c k l ( ) 产生序列t 户。 ”的前2 0 项为0 0 1 0 一1 0 1 1 o l ( ) 1 一0 1 1 0 1 0 1 0 s 托p8 ： 调用函数i n tp e r i o d t e 8 t ( ) ( 需单独测试) ，测试俨的周期，测试结果为 1 7 6 8 s t e p9 令训。0 = t 严+ o 。( 模2 上) ，产生训。它的前2 0 项为：0 1 0 0 一1 0 1 1 一叭0 0 1 0 1 0 一1 0 1 0 s t e p1 0 ： 调用函数i n tp e r i o d t e s t ( ) ，测试”。的周期，( 需单独测试) 测试结果为 t 4 3 0 0 0 0 。 s t e p1 i ： 调用函数v o i d w t h a i l 8 f o r m ( ) ，产生加密序列z 。它的前1 6 位为：7 3 1 8 6 0 一0 7 4 6 7 9 7 3 6 2 s t e p1 2 ： 输入明文。本程序仅允许输入小写字母口z 、空格、逗号( ，) 、句号( ) 及问号( ? ) 。程序调用库函数s t r l e n ( ) 测定明文长度。此长度在程序中用 s t r l e n ( p l a i n t e x t ) 表示。 假如我们输入明文： l j k em a t h e m a t i c s j 则s t r i e l l ( p l a i n t e x t ) = 1 9 。 s 蛔，j ? ： 调用函数c 1 1 盯一t o i n t t r a n s f o r m ( ) 将明文转化为模3 0 上的数字序列：82 6 l l81 042 61 201 9741 201 9821 82 8 5 t 印j 4 ： 输入加密序列。的起始位置6 e g i 礼p o s 捌讲l ，调用函数i n t8 h a l l o w l o c k 3 ( ) ， 产生七叫3 ，e 3 = ( 6 e 9 仇埘s 饿帆一2 + 2 7 6 9 ) ( l o dp 3 ) 。假设6 e 9 m 掣s 侧d n = 8 0 ， 七e 3 = 2 1 5 9 ，a 托c e 将( 七e 1 ，e 掣2 ，七e 3 ) = ( 7 3 5 8 ，2 0 8 5 ，2 1 5 9 ) 从安全信道传给b d 6 。 加密序列从z 8 0 开始，产生2 8 t r l e n ( p l a i n t e x t ) 个数：z 8 0 2 8 1 卫8 2 。2 删。( p 矧n 钯删+ 7 9 。 若明文如上，则加密序列为( z 舯一z 1 1 7 ) ：2 78 64 l0 56 20 50 35 45 25 69 27 47 90 46 3 2 43 60 61 6 。 1 3 e pj 5 ： 在主函数中我们将e p l 3 和印1 4 中的两组数在模3 0 下相加 0 82 61 10 81 00 42 61 20 01 90 70 41 2o 【) 1 90 80 21 82 8 + 2 78 64 10 56 20 50 35 45 25 69 27 47 90 46 32 43 60 61 6 52 22 2 1 31 20 92 9u 62 21 5u 91 8l42 2282 41 4 印d ： 调用函数v o i di n t t o c 1 1 甜( ) ，将印1 5 中相加后的数字序列转化为密文， 密文为：储w n m j ? g w p j s b e w c i y o ，按如下格式输出： 三饥e1 ：h 啪m - j ? g w p _ j s b e w - c i y 0 4 e n d 符号+ e n d 表示密文结束。 加密程序结束。 懈密程序基本跟加密程序一样，不同点是： b o b 对接到的解密码( 七e ”1 ，七e 2 ，七e 3 ) = ( 7 3 5 8 ，2 0 8 5 ，2 1 5 9 ) 中的七叼1 调用函数 i n tu n l o c k l ( ) ，得到n 1 ，之后产生序列”；对e 可2 调用函数i n tu n l o c k 2 ( ) ，得到 “2 ，之后产生序列护；对女e ”3 调用函数i n tu n l o c k 3 ( ) ，得到b e 咖n p o s 慨o n 。 印了中的明文输入改为密文输入，即输入接到的密文。 e pj 5 中的模3 0 上相加改为相减，即密文码减去加密码。 1 4 第五章算法分析 5 1透明性 由于商业的需要，加解密的算法必须高度透明，本算法可以作为一种公钥 密码体制，私钥为：n 1 、啦、托9 i ”o m s 饿、p 1 、p 2 、自l 、2 、3 、 ”的初始f 缸垦的设置及”一z 。的置换情况，其他的每一个步骤及算法均可 公开。 52灵活性 用户可以很方便的按自己的需要设置以下参数： 产生n ”及护的极小多项式，( z ) 。 俨的初始向量，但尽量使”一的0 1 分布均匀。 “，”一z o 。的置换，尽量使z 。o 不出现2 以上的游程。 浅加密算法中的素数p l 、p 2 、p 3 及对应的觚2 和3 。 53简捷性 程序使用标准的c 语言，并考虑到计算机之间的系统差别，确保在各种计 算机及编译系统下均可正常运行。 用程序去实现加解密比用硬件加密成本低、简捷实用、适用范围广。 1 5 5 4安全性 5 4 1浅加密的混淆性分析 如果敌手在安全信道中捕获( e 1 ，e 可2 ，七e 3 ) ( 当今混乱的网络现状使得这 样的假设并不多余) ，若我们直接用后叫l = 醒卜2 ( m o dp 1 ) ，敌手可能采用逐个素数 淘汰法去确定p 1 ：选定素数埘，令n 。= 女e p _ 2 ( m o dp i ) ，若o 。 3 1 ，则淘汰脚；现 在我们在后面加一个数，例子中设定叫1 = ( 胡1 _ 2 + 5 2 1 ) ( m o dp 1 ) ，5 2 1 这个位置的 数可由用户任意设置，这样敌手便无法通过七e 1 去确定n ，。需要注意的是：尽 量不要设初始向量为( 0 0 0 0 1 ) ，因为这会暴露这个加数( 此时：七叫1 = 1 + 5 2 1 ) 。 5 4 2叫。的周期分析 砌。等于停走序列乱。和深加密序列可m 模2 上相加；而且由它直接产生 加密序列z o 。，所以埘。0 的周期至关重要。 丁( u 。) = ( 2 5 1 ) 2 = 3 1 2 ；丁( o 。) = 1 7 6 8 = 2 3 1 3 1 7 ：显然g c d ( 丁( u 。0 ) ，t ( 。) ) = 1 ， 丁( o 。) 为t ( u 。) t ( 。) = 2 3 1 3 1 7 3 1 2 的一个因子。 受内存的限制，程序无法检测出”o 。的真实周期，但通过对叫。的长度进行 调节( 调至4 4 0 0 0 0 ，计算机的内存需2 5 6 兆) ，我们能检测出其周期大于4 3 0 0 0 0 。 我们有以下结论：t ( 鲫。o ) 三2 2 1 3 1 7 3 1 2 = 8 4 9 5 2 4 。因为： 丁( “严) 的最大真因子为1 7 6 8 9 6 1 2 = 8 4 9 5 2 4 ，次大因子为1 7 6 8 9 6 1 4 ：4 2 4 7 6 2 ；由于我们检测其周期大于4 3 0 0 0 0 ，所以次大因子不可能是其周期， 从而可知：丁( ，。) 只可能为：8 4 9 5 2 4 或1 6 9 9 0 4 8 ( 8 4 9 5 2 4 2 ) 。 5 、4 3对加密序列z 。的一系列分析 ( a ) 对。的周期分析 假设训m 的周期为其下界8 4 9 5 2 4 ，因为叫。一z o 。的对应为4 元组对4 元组 1 6 或4 元组对3 元组，二者机会大致各半；又由于我们把w 。的4 元组分为3 种 情况，9 c d ( 3 ，8 4 9 5 2 4 ) = l ，所以z 。的周期t ( z o 。) 3 8 4 9 5 2 4 7 8 2 2 3 0 0 0 0 。 ( b ) 对z 。的线性复杂度的分析 对z 。的线性复杂度的分析是基于以下事实：z o 。的最长游程为2 。我们采 用概率的方法来估计其线性复杂度： 设。o 。的周期为? ，线性复杂度为m ，( n 。，nh 棚。一，) 为初始向量，由于吼 可能为。一9 的任一数字，我们着重分析z 。一。z 。z z 。扣一。这礼长序列最长 游程至多为2 游程的概率( 为了便于分析，假定n 为偶数) ，分析方法如下： 分析此n 长序列共有i 个2 游程的个数( i 如2 ) ：首先确定一个长为n i 的最长为l 游程的序列个数，显然为1 0 9 一”1 个；再把这个长为n i 的序列 写成如下形式： s 。( ) s 。( ) s 。( ) s n 一。( ) ，我们在这n i 个括号中挑出i 个括号，在这i 个括 号中填上与它前面那个数相同的数，其余括号擦去，得到一个长为n 的、共有 i 个2 游程的序列，这种取法共c 一i ，i ) 种，所以礼长序列共有 个2 游程的 个数0 n 2 ) 为；1 0 9 ”- 1 g m 一 ， ) 个。 由上面的分析我们不难得到如下结论：n 长序列最长游程至多为2 游程的 个数s m = 至1 0 9 “一1 g ( ? t i ，i ) ，其概率r n e = s “m 1 0 “。 附录3 中的程序的运行结果如下： 1 0 0 1 5 0 s 札m 1 0 0 9 8 1 0 9 6 3 0 9 0 1 7 冗o t e 1 0 0 9 8 1 9 6 3 4 05 2 2 5 5 7 3 0 8 5 9 6 7 1 0 3 0 6 在我的计算机上仅能检测出n 3 0 8 时的情况，从程序运行的结果可以看 出，随着n 的增大，觑把逐渐减小，但减小的幅度越来越小，但考虑到z 。的 周期丁( 。0 。) 3 0 8 ，我们完全可以忽略诸如t m 1 0 0 0 0 的可能性，从而有： 加密序列z 0 。在其周期内可视为随机序列。 ( c ) 对z 。的线性攻击 一个基本的数学原理：如果明文与密文的关系是n 维线性关系，且系数是 密钥，则n 个明密文对就可破解密钥。由( b ) 中的分析：若敌手想用分析序 列的线性复杂度的方法来破解密码，它必需对9 6 1 种情况中的每一种( 不同的 初始向量得到的z 。的线性复杂度也不同) 掌握2 0 0 多万对明密文对，这在 现实中是不可能的。 ( d ) 对密钥空间的分析 假设6 e 9 i n p o s 捌o n 的取值范围为。一( m 凹一1 ) ，若我们已确定了一种置换( 尽管这种置换可随时进行变更) ，密钥空间的大小很容易计算出来：m n 似3 1 3 1 2 1 3 2 1 7 ( 1 61 ) 3 l n z 94 5 1 0 5 1 。 ( e ) 对密钥空间的穷尽搜索攻击分析 这部分分析的前提是：敌手已掌握足够长、足够多的明密文对，尽管 这在现实中是绝不可能的。我们按目前最快的搜索速度：每秒搜索3 0 0 0 亿个 密钥( 至少需要1 0 0 ，0 0 0 台计算机协同工作) ，假定m n z = 1 0 0 0 0 ，敌手至少需要 ( 9 4 5 1 0 5 5 ) ( 3 1 0 1 1 3 6 0 0 2 4 3 6 6 1 0 8 ) 9 9 1 0 2 8 亿年。 1 8 溉 溉 溉 幌 1 1 6 n d 叭 吡 地 m 1 1 6 5 参考文献 【1 】 d o u g l a 8r s t i n s o n ：c r y p t o r a p h yt h e o r ya n dp r a c t i c e ，p u b u s h i n gh o u s eo fe l e c t r o i 卜 i c si n d u s tr y ) 2 0 0 3 。 2 】t b e t h ，f c p i p e r ：t h es t o p a n d - g og e n e r d t o r ，p r o c e l l r o c r y p t 8 4 ，a d v a n c e 8i nc r y p t o l o g y l n c s ，1 9 8 5 。 3 胡予濮，张玉清，肖国镇：对称密码学，机械工业出版社，2 0 0 2 。 4 】 l i d l ，r a n dn i e d e r r e i t e r ：i n t r o d u c t i o nt of i n i t ef i e l d sa n dt h e i ra p l i c a t i o 工l s ，c a m b r i d g eu n i v e r s i t yp r e s s ，1 9 8 6 5 】万哲先：代数与编码，科学出版社，北京，1 9 8 5 。 6 肖国镇，梁传甲，王育民：伪随机序列极其应用，北京，国防工业出版社， 1 9 8 5 。 f 7 r v 呕e 1 o nt h el i n e a rc o m p l e x i t yo fc a 8 e c a d e ds e q u e n c e a d n c e si nc r y p t o l o g y l n c s ，s p r i n g e r1 9 9 0 ，2 0 9 ：9 9 1 0 9 8 王锦玲：控制序列的构造与分析，信息工程学院学报，1 9 9 3 ，1 2 ( 2 ) 3 2 3 8 。 【9 王锦玲：一种产生大线性复杂度的方法，通信保密，1 9 9 4 ，5 7 ( 1 ) ：5 3 5 7 。 1 0 王锦玲：一类钟控序列线性复杂度的界，通信保密，1 9 9 3 ，6 0 ( 4 ) ：4 4 4 8 。 1 1 】毕文斌，王锦玲：三元树上的线性递归序列，郑州大学学报( 工学版)