在密码学中的应用课件.pptx

古典密码的两大机制：古典密码的两大机制：代替密码：代替密码：字母表范围内替换；字母表范围内替换；换位密码：换位密码：在消息内变换字母的位置。在消息内变换字母的位置。2.1代替密码代替密码 1.描述描述 密钥是字母表的任意组合，有一个明密对应表；密钥是字母表的任意组合，有一个明密对应表；密钥空间巨大：密钥空间巨大：26!；单表代替密码的两个特例：移位密码和仿射密码。单表代替密码的两个特例：移位密码和仿射密码。2.举例举例 首先选加密表；为了便于记忆，协商一个密钥：首先选加密表；为了便于记忆，协商一个密钥：DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：去掉重复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二节 代替与换位第二节 代替与换位2.2 换位密码换位密码 1.机制：机制：单个字符不变而位置改变。单个字符不变而位置改变。如将文本翻转：明文如将文本翻转：明文 computersystems 密文密文 SMETSYSRETUPMOC 2.特点：特点：(1)密文长度与明文长度相同；密文长度与明文长度相同；(2)唯密文攻击可能得到多种不同的破译结果；唯密文攻击可能得到多种不同的破译结果；如如 keeppeek；liveevilvile 3.分组换位密码分组换位密码 针对固定大小的分组进行操作。针对固定大小的分组进行操作。举例：明文举例：明文 can you understand (1)列换位法列换位法 设密钥设密钥k=4，将明文进行分组排列，将明文进行分组排列canyouunderstand按列按列读出读出密文：密文：CODTAUEANURNYNSDCANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按按4 4个字符一列分组排列个字符一列分组排列1 2 3 41 2 3 4第二节 代替与换位按列按列 读出读出t y p ecanyouunderstand密文：密文：YNSDNURNCODTAUEACANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 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密文：密文：NCYAUONURDSENTDA按置换矩阵的阶按置换矩阵的阶4 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 e:11.67 t:9.53 o:7.81 a:7.73 the:4.65 to:3.02 of:2.61 and:1.85 the:4.65 to:3.02 of:2.61 and:1.85 2.应用：应用：对古典密码进行唯密文攻击。对古典密码进行唯密文攻击。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)%26解密后的明文为：解密后的明文为：meet me after midnight in the alley第二节 代替与换位4.举例：举例：对代替密码的攻击对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.t th he et th he ee eeeeee ee eeeeet tt tt ttttto oo oo oo on ni ii ii il ll ll lk kb bb bs ss sd dd db ba ay y 分析：由分析：由ESROL得到得到er,s,o,l或或re,s,o,lloser 或或 sorel 那么：由那么：由VIERD得到得到drive或或irevd所以比较合理的明文是：所以比较合理的明文是：loser drive5.举例：举例：对换位密码的攻击对换位密码的攻击 ESROL VIERD第二节 代替与换位作业：作业：(1)解密由仿射密码加密的密文：解密由仿射密码加密的密文：VCLLCP BKLC LJKX XCHCP(2)解密用简单换位密码加密的密文：解密用简单换位密码加密的密文：EAGGAR DAIREP3.1 群群 1.二元运算二元运算 定义：定义：设设s为集合，函数为集合，函数f:s ss称为称为s上的二上的二元运算或代数运算。满足：元运算或代数运算。满足：可计算性：可计算性：s中任何元素都可以进行这种运算；中任何元素都可以进行这种运算；单值性：运算结果唯一；单值性：运算结果唯一；封闭性：封闭性：s中任何两个元素运算结果都属于中任何两个元素运算结果都属于s。2.群的定义群的定义 定义：定义：设设是代数系统，是代数系统，为为G上的二元运上的二元运算，如果算，如果 运算是可结合的，则称运算是可结合的，则称半群。半群。若若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，则称，则称为幺半群；为幺半群；若若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，G中的任何元素中的任何元素x都有逆元都有逆元x-1 G，称，称为群，简记为为群，简记为G。第三节 置 换 举例：举例：(1)是群，其中是群，其中Z为整数集合，为整数集合，+是普通是普通的加法，单位元是的加法，单位元是0，整数，整数x的逆元是的逆元是-x。(2)是群，是群，Z6=0,1,2,3,4,5，为模为模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称为称为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，使得使得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元置换元置换群。群。第三节 置 换 定义定义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：没有移动任何元素的置换。没有移动任何元素的置换。即对于所有的即对于所有的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)=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循环有循环有k k种表示法。种表示法。比较：比较：(1 2 3)与与(1 3 2)(1 2 3)=(2 3 1)=(3 1 2)(1 3 2)如：如：则：则：即：即：对某个集合应用对某个集合应用g g操作操作k k次，不会对集合产生次，不会对集合产生 任何影响。任何影响。第三节 置 换(2)置换的阶置换的阶 是置换被多次应用后却不产生任何实际影响所需是置换被多次应用后却不产生任何实际影响所需要的重复次数。要的重复次数。若置换若置换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=不相交循环分解中各循环长度不相交循环分解中各循环长度的最小公倍数。的最小公倍数。如：如：思考：思考：如果一副如果一副5050张的牌洗得好，重复洗张的牌洗得好，重复洗8 8次后所次后所 有的牌将返回初始位置。有的牌将返回初始位置。阶为阶为4 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,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的完美快速的完美快速 洗牌过程为：洗牌过程为：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 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 5按按4 4行行3 3列写出列写出第三节 置 换命题：忽略两个不动点命题：忽略两个不动点0和和mn-1，m n分组交错分组交错 对集合对集合1,2,3,mn-2的作用是：的作用是：x (mx)%(mn-1)举例：举例：3 6分组交错分组交错3x%173x%17 分析：快速洗牌，去掉两个不动点分析：快速洗牌，去掉两个不动点 完美的快速洗牌：完美的快速洗牌：x (2x)%(2n+1)第三节 置 换作业：作业：(1)计算乘积计算乘积第三节 置 换 用不相交循环的乘积表示上述的结果，并确定阶。用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？中任意元素的最大阶是多少？S14呢？呢？(3)确定对一副确定对一副20张牌的完美快速洗牌的循环分解。张牌的完美快速洗牌的循环分解。(4)找出找出3 5的分组交错置换的循环分解。的分组交错置换的循环分解。第四节 现代对称密码 香农提出的香农提出的现代密码现代密码设计准则：设计准则：KerchhoffKerchhoff原则：原则：系统的安全性不依赖于对密文或系统的安全性不依赖于对密文或 加密算法的保密，而依赖于密钥。加密算法的保密，而依赖于密钥。惟一需要保密的是密钥；惟一需要保密的是密钥；决定了古典密码学与现代密码学。决定了古典密码学与现代密码学。一个好的密码将融合混淆和扩散一个好的密码将融合混淆和扩散 混淆：混淆：混淆明文的不同部分；混淆明文的不同部分；扩散：扩散：对攻击者隐藏一些语言的局部特征；对攻击者隐藏一些语言的局部特征；现代密码将结合换位和代替：现代密码将结合换位和代替：代替密码代替密码在混淆上是有效的；在混淆上是有效的；换位密码换位密码扩散性较好。扩散性较好。4.1 数据加密标准数据加密标准DES(Data Encryption Standard)1976年被采纳作为联邦标准，并授权在非密级年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。的政府通信中使用，应用广泛。DES是一个分组加密算法，对称密码，是一个分组加密算法，对称密码，64位分位分 组，密钥长度为组，密钥长度为64位位(实际长度为实际长度为56位位)。第四节 现代对称密码现代密码算法的特点：现代密码算法的特点：只要保证密钥安全，就能保证加密信息的安全。只要保证密钥安全，就能保证加密信息的安全。对称密码算法：对称密码算法：很好地融合了混淆和扩散；很好地融合了混淆和扩散；DES、AES、IEDA、RC6等等非对称密码算法：非对称密码算法：基于数学难题；基于数学难题；RSA、ECC、ElGamal等等 DES的整个算法是公开的，系统的安全性靠的整个算法是公开的，系统的安全性靠密钥保证。算法包括三个步骤：初始置换密钥保证。算法包括三个步骤：初始置换IP、16轮轮迭代的乘积变换、逆初始变换迭代的乘积变换、逆初始变换IP-1。1.初始置换初始置换IP 初始置换初始置换IP可将可将64位明文位明文M=m1m2m64的位置进的位置进行置换，得到乱序的行置换，得到乱序的64位明文组位明文组M0=m58m50m7。2.逆初始置换逆初始置换IP-1 逆初始置换逆初始置换IP-1将将16轮迭代后的轮迭代后的64比特数据的各比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密文组。逆序，然后将元素按行读出即可得到输出的密文组。IP和和IP-1的作用主要是打乱输入的的作用主要是打乱输入的ASCII码字划分关系，码字划分关系，并将明文校验码变成并将明文校验码变成IP输出的一个字节。输出的一个字节。第四节 现代对称密码第四节 现代对称密码第四节 现代对称密码第四节 现代对称密码【举例举例】设设64位明文位明文M为：为：00000000 11111111 01010101 00010001 10001000 11001100 00110011 10101010则经过则经过IP置换后的置换后的M0为：为：00100110 01001110 00100110 01001110 10110010 11000010 10110010 11000010转换过程如下：转换过程如下：第四节 现代对称密码 3.乘积变换乘积变换 乘积变换是乘积变换是DES算法的核心部分。将经过算法的核心部分。将经过IP置置换后的数据分成换后的数据分成32位的左右两组，在迭代过程中彼此位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的左右交换位置。每次迭代时只对右边的32位进行一系列位进行一系列的加密变换，然后把左边的的加密变换，然后把左边的32位与右边得到的位与右边得到的32位逐位逐位进行异或操作，作为下一轮迭代时左边的段。位进行异或操作，作为下一轮迭代时左边的段。迭代公式为：迭代公式为：Li=Ri-1，Ri=Li-1 f(Ri-1,ki)：按位异或操作运算符，即按位作模按位异或操作运算符，即按位作模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)的各比特重复一次的各比特重复一次得到的，实现数据扩展。得到的，实现数据扩展。第四节 现代对称密码 (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的产生：的产生：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比特数比特数据从左至右分成据从左至右分成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=11在在S5中找到行为中找到行为2，列为，列为11的数据的数据5转换为转换为4位二位二进制为进制为0101，所以，所以S5的输出为的输出为0101。(4)置换运算置换运算P S1S8盒的输出合成盒的输出合成32比特数据后，用换位表比特数据后，用换位表p进行置换，得到的进行置换，得到的32比特数据就是比特数据就是f(Ri-1,ki)的输出。的输出。第四节 现代对称密码 DES的解密算法和加密算法相同，只是在解密的解密算法和加密算法相同，只是在解密 过程中将子密钥的顺序颠倒。过程中将子密钥的顺序颠倒。DES的出现在密码史上是个创举。以前任何设的出现在密码史上是个创举。以前任何设计者对于密码体制细节都是严加保密的。自公布以计者对于密码体制细节都是严加保密的。自公布以来，它一直活跃在国际保密通信的舞台上，成为商用来，它一直活跃在国际保密通信的舞台上，成为商用保密通信和计算机通信的最常用的加密算法。由于保密通信和计算机通信的最常用的加密算法。由于DES的安全性完全依赖于密钥，而其的安全性完全依赖于密钥，而其64位的密钥太位的密钥太短，因而出现了许多短，因而出现了许多DES的改进算法，如三重的改进算法，如三重DES、分组反馈连接式分组反馈连接式DES以及密码反馈模式以及密码反馈模式DES等。随着等。随着新的攻击手段和改进的加密算法的不断出现，新的攻击手段和改进的加密算法的不断出现，DES也许将完成它的历史使命。也许将完成它的历史使命。高级加密标准高级加密标准AES评选于评选于2000年年10月结束，月结束，Rijdael算法为算法为AES的唯一算法。的唯一算法。第四节 现代对称密码 4.DES的安全性的安全性 (1)差分分析差分分析 1990年年Biham和和Shamir提出差分密码分析。提出差分密码分析。是一种比穷举攻击有效的选择明文的攻击方法。是一种比穷举攻击有效的选择明文的攻击方法。差分分析的攻击方法是针对差分分析的攻击方法是针对DES和其他类似的有和其他类似的有固定固定S盒的算法。盒的算法。DES的的S盒恰好最适宜于抗差分分盒恰好最适宜于抗差分分析。最佳差分分析的总结表明对析。最佳差分分析的总结表明对16轮轮DES的攻击需的攻击需选择明文选择明文247，分析的复杂性为，分析的复杂性为237。(2)线性密码分析线性密码分析 Mitsuru Matsui提出了线形密码分析。使用线性提出了线形密码分析。使用线性近似值来逼近分组密码的操作。攻击完整的近似值来逼近分组密码的操作。攻击完整的16轮轮DES，当已知明文的平均数为，当已知明文的平均数为243时，可得到密时，可得到密钥，是最有效的攻击钥，是最有效的攻击DES的方法。的方法。第四节 现代对称密码第四节 现代对称密码4.2 序列密码序列密码 1.随机数生成器随机数生成器 (1)任意由确定过程生成的随机数序列，从实任意由确定过程生成的随机数序列，从实际意义上讲都不是随机的。际意义上讲都不是随机的。(2)pRNG(pseudo-random number generators):伪随机数发生器，其典型应用是一次一密乱码本。伪随机数发生器，其典型应用是一次一密乱码本。(3)一个一个pRNG要求：在不知道密钥的情况下，要求：在不知道密钥的情况下，由随机数序列中已知部分推测下一个数是由随机数序列中已知部分推测下一个数是“困难困难”的。的。(4)伪随机数序列的周期：要求尽可能大伪随机数序列的周期：要求尽可能大 对于序列对于序列s0,s1,s2,若存在若存在p，使得，使得si+p=si 则称它为周期为则称它为周期为p的周期序列。的周期序列。第四节 现代对称密码 2.线性同余发生器线性同余发生器 最为广泛使用的伪随机数产生器。最为广泛使用的伪随机数产生器。(1)产生方式产生方式 sn+1=(asn+b)mod m Zm 其中其中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,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。