《教学课件第八章在密码学中的应用II》由会员分享，可在线阅读，更多相关《教学课件第八章在密码学中的应用II（51页珍藏版）》请在金锄头文库上搜索。
1、第八章第八章 在密码学中的应用在密码学中的应用(II) 古典密古典密码的两大机制：的两大机制： 代替密代替密码：字母表范字母表范围内替内替换； 换位密位密码：在消息内在消息内变换字母的位置。字母的位置。2.1代替密代替密码 1.描述描述 密密钥是字母表的任意是字母表的任意组合，有一个明密合，有一个明密对应表；表； 密密钥空空间巨大：巨大：26!； 单表代替密表代替密码的两个特例：移位密的两个特例：移位密码和仿射密和仿射密码。 2.举例例 首先首先选加密表；加密表；为了便于了便于记忆，协商一个密商一个密钥： DO YOU LIKE THIS BOOK 去掉重复字母，再去掉重复字母，再进行行补充，
2、形成加密表：充，形成加密表： abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二节 代替与换位第二节 代替与换位2.2 换位密位密码 1.机制：机制：单个字符不个字符不变而位置改而位置改变。 如将文本翻如将文本翻转：明文：明文 computersystems 密文密文 SMETSYSRETUPMOC 2.特点：特点： (1)密文密文长度与明文度与明文长度相同；度相同； (2)唯密文攻唯密文攻击可能得到多种不同的破可能得到多种不同的破译结果；果； 如如 keeppeek；liveevilvile 3.分分组换位密位密码 针对固定大小的分
3、固定大小的分组进行操作。行操作。 举例：明文例：明文 can you understand (1)列列换位法位法 设密密钥k=4，将明文，将明文进行分行分组排列排列canyouunderstand按列按列读出出密文：密文： CODTAUEANURNYNSDCANYOUUNDERSTAND按行按行读出出明文：明文： canyouunderstand明文：明文：canyouunderstand按按4个字符一行分个字符一行分组排列排列按按4个字符一列分个字符一列分组排列排列1 2 3 41 2 3 4第二节 代替与换位按列按列读出出t y p ecanyouunderstand密文：密文： YNSD
4、NURNCODTAUEACANYOUUNDERSTAND按行按行读出出明文：明文： canyouunderstand明文：明文：canyouunderstand按按4个字符一行分个字符一行分组排列排列按type(3,4,2,1)填入1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密密钥为字符串字符串type1234按密按密钥长度分度分组第二节 代替与换位(3)矩矩阵换位法：置位法：置换矩矩阵作作为密密钥明文：明文：canyouunderstandc a n y o u u n d e r s t a n dn c y a u o n u r d s e n t d a
5、密文：密文：NCYAUONURDSENTDA按置按置换矩矩阵的的阶4分分组c a n y o u u n d e r s t a n dN C Y A U O N U R D S E N T D A明文：明文：canyouunderstand解密置解密置换矩矩阵：说明：明：第二节 代替与换位第二节 代替与换位2.3 频率攻率攻击1.原理：原理：利用自然利用自然语言的言的频率攻率攻击字母出字母出现的的频率有率有规律：律：e:11.67 t:9.53 o:7.81 a:7.73 the:4.65 to:3.02 of:2.61 and:1.85 2.应用：用：对古典密古典密码进行唯密文攻行唯密文攻
6、击。3.举例：例：对仿射密仿射密码的攻的攻击 密文：密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP 统计字母出字母出现的次数：的次数： F6 G4 H3 J3 猜猜测：e(4)F(5) t(19)G(6) 则有：有：Ea,b(e)=F Ea,b(t)=G 第二节 代替与换位 Ea,b(4)=(a4+b)%26 Ea,b(19)=(a19+b)%265=(4a+b)%266=(19a+b)%26a=15-1%26=7b=3加密密加密密钥a-1%26=15-a-1b=-153%26=7解密密解密密钥Ea,b(x)=(7x+3)%26解密函数解密函数为：E15,7(x)=(15x+
7、7)%26解密后的明文解密后的明文为： meet me after midnight in the alley第二节 代替与换位4.举例：例：对代替密代替密码的攻的攻击KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.thetheeeeeeeetttttooooniiilllkbbssddbay 分析：由分析：由ESROL得到得到er,s,o,l或或re,s,o,lloser 或或 sorel 那么：由那么：由VIERD得到得到drive或或irevd所以比所以比较合理的明文是：合理的明文是： loser drive5.举例：例：对换位密位密码
8、的攻的攻击ESROL VIERD第二节 代替与换位作作业：(1)解密由仿射密解密由仿射密码加密的密文：加密的密文： VCLLCP BKLC LJKX XCHCP(2)解密用解密用简单换位密位密码加密的密文：加密的密文： EAGGAR DAIREP3.1 群群 1.二元运算二元运算 定定义：设s为集合，函数集合，函数f:s ss称称为s上的二上的二元运算或代数运算。元运算或代数运算。满足：足： 可可计算性：算性：s中任何元素都可以中任何元素都可以进行行这种运算；种运算； 单值性：运算性：运算结果唯一；果唯一； 封封闭性：性：s中任何两个元素运算中任何两个元素运算结果都属于果都属于s。 2.群的定
9、群的定义 定定义：设是代数系是代数系统， 为G上的二元运上的二元运算，如果算，如果 运算是可运算是可结合的，合的，则称称半群。半群。 若若为半群，并且二元运算半群，并且二元运算 存在存在单位元位元e G，则称称为幺半群；幺半群； 若若为半群，并且二元运算半群，并且二元运算 存在存在单位元位元e G，G中的任何元素中的任何元素x都有逆元都有逆元x-1 G，称，称为群，群，简记为G。第三节 置 换 举例：例： (1)是群，其中是群，其中Z为整数集合，整数集合，+是普通是普通的加法，的加法，单位元是位元是0，整数，整数x的逆元是的逆元是-x。 (2)是群，是群，Z6=0,1,2,3,4,5， 为模模
10、6加法。加法。显然然 满足足结合律，合律，单位元是位元是0；由于；由于1 5=0，2 4=0，3 3=0，所以，所以1和和5互互为逆元，逆元，2和和4互互为逆逆元，元，3和和0的逆元仍然是的逆元仍然是3和和0。 3.群中元素的群中元素的阶 定定义：设是群，是群，a G，n Z，则a的的n次次幂为 e n=0 an= an-1 a n0 (a-1)m n0,n=-m 举例：例：在群在群中，中，30=0，35=15，3-5=-15 在群在群中，中，20=0，23=0，2-3=0第三节 置 换 阶的定的定义： (1)设是群，是群，a G，使得等式，使得等式ak=e成立的成立的最小正整数最小正整数k称
11、称为a的的阶，记做做|a|=k，a称称为k阶元，元，若不存在若不存在这样的整数的整数k，则a称称为无限无限阶元。元。 例如：例如： 在在中，中，2和和4是是3阶元，元，3是是2阶元，元， 1和和5是是6阶元，元，0是是1阶元。元。 在在中，中，0是是1阶元，其他都是无限元，其他都是无限阶元。元。 (2)设为群，群，a G，且，且|a|=r。设k是整数，是整数，则ak=e当且当且仅当当r|k。 (3)设为群，群，则群中任何元素群中任何元素a与其逆元与其逆元a-1 具有相同的具有相同的阶。第三节 置 换 4.循循环群和置群和置换群群 定定义1：设为群，如果存在一个元素群，如果存在一个元素a G，使
12、得使得G=ak|k Z，则称称G为循循环群，群，记做做G=，称称a为生成元。若生成元。若|a|=n，则G称称为n阶循循环群。群。 例如：例如： 是循是循环群，其中群，其中Z6=0,1,2,3,4,5,， 为模模6加法，生成元加法，生成元为1或或5。 是循是循环群，生成元群，生成元为1或或-1。 是循是循环群，群，Zn=0,1,n-1,，生成生成 元元为1。第三节 置 换 定定义3：设s=1,2,n，s上的上的n!个置个置换构成集合构成集合sn，则称称sn与置与置换的复合运算的复合运算构成的群构成的群为s上上的的n元元对称群，称群，的任意子群称的任意子群称为s上的上的n元置元置换群。群。第三节
13、置 换 定定义2：设s=1,2,n，s上的任何双射映射函数上的任何双射映射函数 :ss称称为s上的上的n元置元置换，记为：3.2置置换概念概念 1.置置换 一个集合一个集合X的置的置换f定定义为X到自身的一个双射到自身的一个双射函数函数f。对应有有n个元素的集合个元素的集合X，共有，共有n!个置个置换。 问题：对于集合于集合X，给定某个状定某个状态，经过多少次多少次置置换返回初始状返回初始状态？ Sn=1,2,3,n-1,n表示表示n个元素的置个元素的置换群群 置置换g为满足足g(k)=ik的一个置的一个置换：平凡置平凡置换e：没有移没有移动任何元素的置任何元素的置换。 即即对于所有的于所有的
14、i，有，有e(i)=i。置置换与集合与集合内容无关内容无关第三节 置 换2. 置置换的合成或乘的合成或乘积 设g和和h是两个置是两个置换，先，先应用用h，再，再应用用g， 记为：gh或或gh 注意：注意： gh hg 置置换的合成的合成满足足结合律：合律： (gh)k=g(hk)3. 逆置逆置换 对于任意置于任意置换g，存在一个逆置，存在一个逆置换g-1，满足：足： gg-1=g-1g=e4. 图表表记法法 用来用来计算两个置算两个置换的乘的乘积。如：。如：第三节 置 换5. 循循环 最最简单的置的置换是不同是不同长度的循度的循环。 一个一个k循循环满足：足： f(i1)=i2, f(i2)=
15、i3 , f(ik-1)=ik, f(ik)=i1，对于任意于任意j (i1,i2,ik)，有，有f(j)=j。 举例：例：则：可可见：gh hg，具有不可交，具有不可交换性。性。记作：作：(i1,i2,ik)(1 2)(1 3)第三节 置 换6. 结论 (1)如果如果g是一个是一个k循循环，那么，那么gk=e。注意：注意：一个一个k循循环有有k种表示法。种表示法。比比较： (1 2 3)与与(1 3 2)(1 2 3)= (2 3 1)= (3 1 2)(1 3 2)如：如：则：即：即：对某个集合某个集合应用用g操作操作k次，不会次，不会对集合集合产生生任何影响。任何影响。第三节 置 换(2
16、)置置换的的阶 是置是置换被多次被多次应用后却不用后却不产生任何生任何实际影响所需影响所需要的重复次数。要的重复次数。 若置若置换g是一个是一个k循循环，则有有gk=e，g的的阶为k。(3)不相交的循不相交的循环 若若g=(i1,ik)和和h=(j1,jl)分分别为k循循环和和l循循环，且，且i1,i2,ik和和j1,j2,jl是不相交的列表，是不相交的列表，则有：有： gh=hg 这样的循的循环g和和h称称为不相交的循不相交的循环。第三节 置 换 一个置一个置换g的的阶k=不相交循不相交循环分解中各循分解中各循环长度度的最小公倍数。的最小公倍数。如：如：思考：思考：如果一副如果一副50张的牌
17、洗得好，重复洗的牌洗得好，重复洗8次后所次后所有的牌将返回初始位置。有的牌将返回初始位置。阶为4(4) 置置换的不相交循的不相交循环分解分解 任何置任何置换都可以表示都可以表示为不相交循不相交循环的乘的乘积，并，并且本且本质上只有上只有这一种表示方法。一种表示方法。=(1 4 5 7)(2 3)(6)第三节 置 换3.3 切牌切牌 最最简单的切牌：的切牌：选择一个随机点把一副牌一分一个随机点把一副牌一分为二，然后交二，然后交换两部分。两部分。 n张牌：牌：0,1,n-1 i+1,n-1,0,1,i 切牌切牌过程程为：fi(x)=(x+n-i-1)%n 如：如：n=6,i=1 0,1,2,3,4
18、,5 2,3,4,5,0,1 置置换过程程为：f1(x)=(x+4)%6第三节 置 换若若n张牌的位置牌的位置编号号为： 1,2,n-1,n i+1,n-1,n,1,i则切牌切牌过程程为：fi(x)=(x+n-i-1)%n+1第三节 置 换如：如：n=6,i=2 1,2,3,4,5,6 3,4,5,6,1,2置置换过程程为：f1(x)=(x+3)%6+12n张牌：牌： 1,2,n,n+1,2n-1,2n 两半交两半交错：n+1,1,n+2,2,2n-1,n-1,2n,n 1,n+1,2,n+2,n-1,2n-1,n,2n命命题：对一副有一副有2n张牌牌1,2,2n-1,2n的完美快速的完美快速
19、 洗牌洗牌过程程为：f(x)=(2x)%(2n+1)推推论：若：若e为2模模2n+1的的阶，即，即e是是满足足2e=1 mod 2n+1的最小正整数。那么的最小正整数。那么对一副有一副有2n张牌牌经 过e次洗牌后，所有的牌都第一次返回到它次洗牌后，所有的牌都第一次返回到它们 的起始位置。的起始位置。不好的洗牌不好的洗牌完美洗牌完美洗牌第三节 置 换3.4洗牌洗牌然后按列然后按列读取取这些数：些数： 0,n,2n,mn-n,1,n+1,2n+1,mn-n+1,mn-1对于数于数x，行：，行：x/n 列：列：x%n3.5 分分组交交错 给定正整数定正整数m和和n，针对mn个元素，一个个元素，一个m
20、 n分分组交交换的置的置换定定义为： 按行将按行将mm个数据写成个数据写成m n的矩的矩阵的形式的形式第三节 置 换然后按列然后按列读取取这些数：些数： 0,4,8,1,5,9,2,6,10,3,7,11对应的置的置换过程程为：例：例：12个数据个数据 0,1,2,3,4,5,6,7,8,9,10,11， 进行行3 4分分组交交错。 对应的循的循环分解分解为：数据数据置置换位置位置阶为5按按4行行3列写出列写出第三节 置 换命命题：忽略两个不：忽略两个不动点点0和和mn-1，m n分分组交交错 对集合集合1,2,3,mn-2的作用是：的作用是： x (mx)%(mn-1)举例：例：3 6分分组
21、交交错3x%173x%17 分析：快速洗牌，去掉两个不分析：快速洗牌，去掉两个不动点点 完美的快速洗牌：完美的快速洗牌： x (2x)%(2n+1)第三节 置 换作作业： (1)计算乘算乘积第三节 置 换 用不相交循用不相交循环的乘的乘积表示上述的表示上述的结果，并确定果，并确定阶。(2)S5中任意元素的最大中任意元素的最大阶是多少？是多少？S14呢？呢？(3)确定确定对一副一副20张牌的完美快速洗牌的循牌的完美快速洗牌的循环分解。分解。(4)找出找出3 5的分的分组交交错置置换的循的循环分解。分解。第四节 现代对称密码 香香农提出的提出的现代密代密码设计准准则： Kerchhoff原原则：系
22、系统的安全性不依的安全性不依赖于于对密文或密文或 加密算法的保密，而依加密算法的保密，而依赖于密于密钥。惟一需要保密的是密惟一需要保密的是密钥；决定了古典密决定了古典密码学与学与现代密代密码学。学。 一个好的密一个好的密码将融合混淆和将融合混淆和扩散散混淆：混淆：混淆明文的不同部分；混淆明文的不同部分；扩散：散：对攻攻击者者隐藏一些藏一些语言的局部特征；言的局部特征；现代密代密码将将结合合换位和代替：位和代替：代替密代替密码在混淆上是有效的；在混淆上是有效的；换位密位密码扩散性散性较好。好。4.1 数据加密数据加密标准准DES(Data Encryption Standard) 1976年被采
23、年被采纳作作为联邦邦标准，并授准，并授权在非密在非密级的政府通信中使用，的政府通信中使用，应用广泛。用广泛。 DES是一个分是一个分组加密算法，加密算法，对称密称密码，64位分位分 组，密，密钥长度度为64位位(实际长度度为56位位)。第四节 现代对称密码现代密代密码算法的特点：算法的特点： 只要保只要保证密密钥安全，就能保安全，就能保证加密信息的安全。加密信息的安全。对称密称密码算法：算法：很好地融合了混淆和很好地融合了混淆和扩散；散； DES、AES、IEDA、RC6等等非非对称密称密码算法：算法：基于数学基于数学难题； RSA、ECC、ElGamal等等 DES的整个算法是公开的，系的整
24、个算法是公开的，系统的安全性靠的安全性靠密密钥保保证。算法包括三个步。算法包括三个步骤：初始置：初始置换IP、16轮迭代的乘迭代的乘积变换、逆初始、逆初始变换IP-1。 1.初始置初始置换IP 初始置初始置换IP可将可将64位明文位明文M=m1m2m64的位置的位置进行置行置换，得到乱序的，得到乱序的64位明文位明文组M0=m58m50m7。 2. 逆初始置逆初始置换IP-1 逆初始置逆初始置换IP-1将将16轮迭代后的迭代后的64比特数据的各比特数据的各字字节按列写出，将前四列插到后四列中，再按列写出，将前四列插到后四列中，再对各列各列进行行逆序，然后将元素按行逆序，然后将元素按行读出即可得
25、到出即可得到输出的密文出的密文组。 IP和和IP-1的作用主要是打乱的作用主要是打乱输入的入的ASCII码字划分关系，字划分关系，并将明文校并将明文校验码变成成IP输出的一个字出的一个字节。第四节 现代对称密码第四节 现代对称密码第四节 现代对称密码第四节 现代对称密码【举例例】设64位明文位明文M为：00000000 11111111 01010101 00010001 10001000 11001100 00110011 10101010则经过IP置置换后的后的M0为：00100110 01001110 00100110 01001110 10110010 11000010 1011001
26、0 11000010转换过程如下：程如下：第四节 现代对称密码 3. 乘乘积变换 乘乘积变换是是DES算法的核心部分。将算法的核心部分。将经过IP置置换后的数据分成后的数据分成32位的左右两位的左右两组，在迭代，在迭代过程中彼此程中彼此左右交左右交换位置。每次迭代位置。每次迭代时只只对右右边的的32位位进行一系列行一系列的加密的加密变换，然后把左，然后把左边的的32位与右位与右边得到的得到的32位逐位逐位位进行异或操作，作行异或操作，作为下一下一轮迭代迭代时左左边的段。的段。迭代公式迭代公式为： Li=Ri-1，Ri=Li-1 f(Ri-1,ki) ：按位异或操作运算符，即按位作模按位异或操作
27、运算符，即按位作模2相加运算。相加运算。运算运算规则为：1 0=1，0 1=1，0 0=0，1 1=0 f的功能的功能是将是将32比特的数据比特的数据经过选择扩展运算展运算 E、密、密钥加密运算、加密运算、选择压缩运算运算S和置和置换运算运算P转换为32比特的比特的输出。出。 第四节 现代对称密码第四节 现代对称密码 (1)选择扩展运算展运算E 选择扩展运算下可将展运算下可将输入的入的32比特比特Ri-1扩展成展成48位的位的输出。令出。令s表示表示E原原输入数据比特的下入数据比特的下标，则E的的输出是将原下出是将原下标s为0或或1(模模4)的各比特重复一次的各比特重复一次得到的，得到的，实现
28、数据数据扩展。展。第四节 现代对称密码 (2) 密密钥加密运算加密运算 密密钥加密运算将加密运算将48比特的子密比特的子密钥ki与与选择扩展展运算运算E输出的出的48比特数据比特数据进行按位异或运算。行按位异或运算。【举例例】设32比特数据比特数据Ri-1为 00000000 11111111 00000000 11111111，48比特子密比特子密钥ki为 00000000 11111111 01010101 10101010 11001100 10001000，求，求Ri-1经过选择扩展运算展运算E后与子密后与子密钥ki异或后的异或后的结果。果。第四节 现代对称密码 16个子密个子密钥ki
29、的的产生：生： 64比特初始密比特初始密钥k经过换位函数位函数PC-1将位置号将位置号为8,16,24,32,40,48,56和和64的的8位奇偶位去掉并位奇偶位去掉并换位；位；换位后的数据分位后的数据分为2组，经过循循环左移位左移位LSi和和换位函数位函数PC-2变换后得到每次迭代加密用的子密后得到每次迭代加密用的子密钥ki。第四节 现代对称密码第四节 现代对称密码 LSi表示求子密表示求子密钥ki时将将Ci-1和和Di-1进行循行循环左左移，其移位位数移，其移位位数为： (3)选择压缩运算运算 选择压缩运算可将密运算可将密钥加密运算后的加密运算后的48比特数比特数据从左至右分成据从左至右分
30、成8组，每，每组为6比特，并行迭入比特，并行迭入8个个S盒后盒后压缩成成32比特比特输出。每个出。每个S盒的盒的输入入为6比特，比特，输出出为4比特，以完成比特，以完成压缩变换。 对于某个于某个S盒盒Si，假，假设其其输入入为b1b2b3b4b5b6， 在在Si表中找到表中找到b1b6行，行，b2b3b4b5 列的整数，列的整数，转换 为4位二位二进制就是制就是输出的出的4比特数据。比特数据。第四节 现代对称密码第四节 现代对称密码第四节 现代对称密码【举例例】设S5的的输入入为b1b2b3b4b5b6=110110。 则(b1b6)2=(10)2=2，(b2b3b4b5)2=(1011)2=
31、11在在S5中找到行中找到行为2，列，列为11的数据的数据5转换为4位二位二进制制为0101，所以，所以S5的的输出出为0101。 (4)置置换运算运算P S1S8盒的盒的输出合成出合成32比特数据后，用比特数据后，用换位表位表p进行置行置换，得到的，得到的32比特数据就是比特数据就是f(Ri-1,ki)的的输出。出。第四节 现代对称密码 DES的解密算法和加密算法相同，只是在解密的解密算法和加密算法相同，只是在解密 过程中将子密程中将子密钥的的顺序序颠倒。倒。 DES的出的出现在密在密码史上是个史上是个创举。以前任何。以前任何设计者者对于密于密码体制体制细节都是都是严加保密的。自公布以加保密
32、的。自公布以来，它一直活来，它一直活跃在国在国际保密通信的舞台上，成保密通信的舞台上，成为商用商用保密通信和保密通信和计算机通信的最常用的加密算法。由于算机通信的最常用的加密算法。由于DES的安全性完全依的安全性完全依赖于密于密钥，而其，而其64位的密位的密钥太太短，因而出短，因而出现了了许多多DES的改的改进算法，如三重算法，如三重DES、分分组反反馈连接式接式DES以及密以及密码反反馈模式模式DES等。随着等。随着新的攻新的攻击手段和改手段和改进的加密算法的不断出的加密算法的不断出现，DES也也许将完成它的将完成它的历史使命。史使命。 高高级加密加密标准准AES评选于于2000年年10月月
33、结束，束，Rijdael算法算法为AES的唯一算法。的唯一算法。第四节 现代对称密码 4. DES的安全性的安全性 (1)差分分析差分分析 1990年年Biham和和Shamir提出差分密提出差分密码分析。分析。是一种比是一种比穷举攻攻击有效的有效的选择明文的攻明文的攻击方法。方法。 差分分析的攻差分分析的攻击方法是方法是针对DES和其他和其他类似的有似的有固定固定S盒的算法。盒的算法。DES的的S盒恰好最适宜于抗差分分盒恰好最适宜于抗差分分析。最佳差分分析的析。最佳差分分析的总结表明表明对16轮DES的攻的攻击需需选择明文明文247，分析的复，分析的复杂性性为237。 (2)线性密性密码分析
34、分析 Mitsuru Matsui提出了提出了线形密形密码分析。使用分析。使用线性性近似近似值来逼近分来逼近分组密密码的操作。攻的操作。攻击完整的完整的16轮DES，当已知明文的平均数，当已知明文的平均数为243时，可得到密，可得到密钥，是最有效的攻，是最有效的攻击DES的方法。的方法。 第四节 现代对称密码第四节 现代对称密码4.2 序列密序列密码 1.随机数生成器随机数生成器 (1)任意由确定任意由确定过程生成的随机数序列，从程生成的随机数序列，从实际意意义上上讲都不是随机的。都不是随机的。 (2)pRNG(pseudo-random number generators):伪随机数随机数发
35、生器，其典型生器，其典型应用是一次一密乱用是一次一密乱码本。本。 (3)一个一个pRNG要求：在不知道密要求：在不知道密钥的情况下，的情况下，由随机数序列中已知部分推由随机数序列中已知部分推测下一个数是下一个数是“困困难”的。的。 (4)伪随机数序列的周期：要求尽可能大随机数序列的周期：要求尽可能大 对于序列于序列s0,s1,s2,若存在若存在p，使得，使得si+p=si 则称它称它为周期周期为p的周期序列。的周期序列。第四节 现代对称密码 2.线性同余性同余发生器生器 最最为广泛使用的广泛使用的伪随机数随机数产生器。生器。 (1)产生方式生方式 sn+1=(asn+b) mod m Zm 其
36、中其中0am,0 bm，初，初值s0称称为种子。种子。 (2)分析分析 a,b,m的取的取值是是产生高生高质量随机数的关量随机数的关键。 取取a=2,b=7,m=17，则 sn+1=(2sn+7) mod 17 取种子取种子s0=1，生成的，生成的伪随机序列随机序列为：1,9,8,6,2,11,12,14,1,9,8,6,2,11,12,14,1,9,序列的周期序列的周期为8，而且，而且Z17中只有中只有8个元素出个元素出现。第四节 现代对称密码 取取a=7,b=1,m=17,则sn+1=(7 sn+1) mod 17 取种子取种子s0=1，生成的，生成的伪随机序列随机序列为：1,8,6,9,
37、13,7,16,11,10,3,5,2,15,4,12,0,1,8,序列的周期序列的周期为16。(14未出未出现) 取种子取种子s0=14，则序列序列为： 14,14,14,14,(3)线性同余性同余发生器的周期生器的周期 定理定理1：只要种子是模只要种子是模p非零的，非零的，则线性同余性同余发生生器器si+1=a si mod p的周期的周期为a在乘法群在乘法群Z/p 中的中的阶l。 而且，而且，l|p-1，且当，且当a为模模p的本原根的本原根时，l=p-1。 定理定理2：线性同余性同余发生器生器si+1=a si+b mod p的周的周期期为a在在Zp 中的中的阶，只要种子，只要种子s0不等于坏种子不等于坏种子 sbad=-(a-1)-1 b mod p举例：求例：求sn+1=7sn+2 mod 13的坏种子的坏种子sbad。
