在密码学中的应用课件

古典密码的两大机制：

代替密码：字母表范围内替换；

换位密码：在消息内变换字母的位置。2.1代替密码

1.描述密钥是字母表的任意组合，有一个明密对应表；密钥空间巨大：26!；单表代替密码的两个特例：移位密码和仿射密码。

2.举例首先选加密表；为了便于记忆，协商一个密钥：

DOYOULIKETHISBOOK

去掉重复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz

DOYULIKETHSBACFGJMNPQRVWXZ第二节代替与换位古典密码的两大机制：abcdefghijkl1第二节代替与换位2.2换位密码

1.机制：单个字符不变而位置改变。如将文本翻转：明文computersystems

密文SMETSYSRETUPMOC2.特点：

(1)密文长度与明文长度相同；

(2)唯密文攻击可能得到多种不同的破译结果；如keep－peek；live－evil－vile3.分组换位密码针对固定大小的分组进行操作。举例：明文canyouunderstand(1)列换位法设密钥k=4，将明文进行分组排列第二节代替与换位2.2换位密码2canyouunderstand按列读出密文：

CODTAUEANURNYNSDCANYOUUNDERSTAND按行读出明文：

canyouunderstand明文：canyouunderstand按4个字符一行分组排列按4个字符一列分组排列12341234第二节代替与换位canyouunderstand按列密文：CANYOUUND3按列读出typecanyouunderstand密文：

YNSDNURNCODTAUEACANYOUUNDERSTAND按行读出明文：

canyouunderstand明文：canyouunderstand按4个字符一行分组排列按type(3,4,2,1)填入123434

21YNSDNURNCODTAUEA(2)密钥为字符串type1234按密钥长度分组第二节代替与换位按列typecanyouunders4(3)矩阵换位法：置换矩阵作为密钥明文：canyouunderstandcanyouunderstandncyauonurdsentda密文：NCYAUONURDSENTDA按置换矩阵的阶4分组canyouunderstandNCYAUONURDSENTDA明文：canyouunderstand解密置换矩阵：说明：第二节代替与换位(3)矩阵换位法：置换矩阵作为密钥明文：canyouunde5第二节代替与换位2.3频率攻击1.原理：利用自然语言的频率攻击字母出现的频率有规律：

e:11.67t:9.53o:7.81a:7.73…the:4.65to:3.02of:2.61and:1.85…2.应用：对古典密码进行唯密文攻击。3.举例：对仿射密码的攻击密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP

统计字母出现的次数：

F－6G－4H－3J－3……

猜测：e(4)－F(5)t(19)－G(6)

则有：Ea,b(e)=FEa,b(t)=G第二节代替与换位2.3频率攻击1.原理：利用自然语言6第二节代替与换位Ea,b(4)=(a4+b)%26Ea,b(19)=(a19+b)%265=(4a+b)%266=(19a+b)%26a=15-1%26=7b=3加密密钥a-1%26=15-a-1b=-15×3%26=7解密密钥Ea,b(x)=(7x+3)%26解密函数为：E15,7(x)=(15x+7)%26解密后的明文为：

meetmeaftermidnightinthealley第二节代替与换位Ea,b(4)=(a4+b)%267第二节代替与换位4.举例：对代替密码的攻击

KOSBMKKBSISSYFSJNFKBMESKOSIDYIFPKFJSSMK.thetheeeeeeeetttttooooniiilllkbbssddbay

分析：由ESROL得到er,s,o,l或re,s,o,lloser或

sorel那么：由VIERD得到drive或irevd所以比较合理的明文是：loser

drive5.举例：对换位密码的攻击

ESROLVIERD第二节代替与换位4.举例：对代替密码的攻击IDYIF8第二节代替与换位作业：(1)解密由仿射密码加密的密文：

VCLLCPBKLCLJKXXCHCP(2)解密用简单换位密码加密的密文：

EAGGARDAIREP第二节代替与换位作业：(1)解密由仿射密码加密的密文：93.1群

1.二元运算

定义：设s为集合，函数f:sss称为s上的二元运算或代数运算。满足：可计算性：s中任何元素都可以进行这种运算；单值性：运算结果唯一；封闭性：s中任何两个元素运算结果都属于s。

2.群的定义

定义：设<G,>是代数系统，为G上的二元运算，如果运算是可结合的，则称<G,>半群。若<G,>为半群，并且二元运算存在单位元eG，则称<G,>为幺半群；若<G,>为半群，并且二元运算存在单位元eG，G中的任何元素x都有逆元x-1G，称<G,>为群，简记为G。第三节置换3.1群第三节置换10

举例：

(1)<Z,+>是群，其中Z为整数集合，+是普通的加法，单位元是0，整数x的逆元是-x。

(2)<Z6,>是群，Z6={0,1,2,3,4,5}，为模6加法。显然满足结合律，单位元是0；由于15=0，24=0，33=0，所以1和5互为逆元，2和4互为逆元，3和0的逆元仍然是3和0。

3.群中元素的阶

定义：设<G,>是群，aG，nZ，则a的n次幂为

en=0an=an-1an>0(a-1)m

n<0,n=-m

举例：在群<Z,+>中，30=0，35=15，3-5=-15

在群<Z3,>中，20=0，23=0，2-3=0第三节置换举例：第三节置换11

阶的定义：

(1)设<G,>是群，aG，使得等式ak=e成立的最小正整数k称为a的阶，记做|a|=k，a称为k阶元，若不存在这样的整数k，则a称为无限阶元。例如：在<Z6,>中，2和4是3阶元，3是2阶元，

1和5是6阶元，0是1阶元。在<Z,+>中，0是1阶元，其他都是无限阶元。

(2)设<G,>为群，aG，且|a|=r。设k是整数，则ak=e当且仅当r|k。

(3)设<G,>为群，则群中任何元素a与其逆元a-1

具有相同的阶。第三节置换阶的定义：第三节置换124.循环群和置换群

定义1：设<G,>为群，如果存在一个元素aG，使得G={ak|kZ}，则称G为循环群，记做G=<a>，称a为生成元。若|a|=n，则G称为n阶循环群。例如：

<Z6,>是循环群，其中Z6={0,1,2,3,4,5,}，为模6加法，生成元为1或5。

<Z,+>是循环群，生成元为1或-1。

<Zn,+>是循环群，Zn={0,1,…,n-1,}，生成元为1。第三节置换4.循环群和置换群第三节置换13

定义3：设s={1,2,…,n}，s上的n!个置换构成集合sn，则称sn与置换的复合运算◦构成的群<sn,◦>为s上的n元对称群，<sn,◦>的任意子群称为s上的n元置换群。第三节置换

定义2：设s={1,2,…,n}，s上的任何双射映射函数:ss称为s上的n元置换，记为：定义3：设s={1,2,…,n}，s上的n!个置换构143.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。置换与集合内容无关第三节置换3.2置换概念平凡置换e：没有移动任何元素的置换。置换与集合152.置换的合成或乘积

设g和h是两个置换，先应用h，再应用g，

记为：g◦h或gh

注意：

g◦h≠h◦g

置换的合成满足结合律：(g◦h)◦k=g◦(h◦k)3.逆置换

对于任意置换g，存在一个逆置换g-1，满足：

g◦g-1=g-1◦g=e4.图表记法

用来计算两个置换的乘积。如：第三节置换2.置换的合成或乘积第三节置换165.循环

最简单的置换是不同长度的循环。一个k循环满足：

f(i1)=i2,f(i2)=i3,…,f(ik-1)=ik,f(ik)=i1，对于任意j(i1,i2,…,ik)，有f(j)=j。

举例：则：可见：g◦h≠h◦g，具有不可交换性。记作：(i1,i2,…,ik)(12)(13)第三节置换5.循环则：可见：g◦h≠h◦g，具有不可交换性。记作：176.结论

(1)如果g是一个k循环，那么gk=e。注意：一个k循环有k种表示法。比较：

(123)与(132)(123)=(231)=(3

12)(132)如：则：即：对某个集合应用g操作k次，不会对集合产生任何影响。第三节置换6.结论注意：一个k循环有k种表示法。(123)=(18(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称为不相交的循环。第三节置换(2)置换的阶(3)不相交的循环第三节置换19

一个置换g的阶k=不相交循环分解中各循环长度的最小公倍数。如：思考：如果一副50张的牌洗得好，重复洗8次后所有的牌将返回初始位置。阶为4(4)置换的不相交循环分解任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。=(1

457)(23)(6)第三节置换一个置换g的阶k=不相交循环分解中各循环长度的最203.3切牌

最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。

n张牌：0,1,…,n-1i+1,…,n-1,0,1,…,i

切牌过程为：fi(x)=(x+n-i-1)%n

如：n=6,i=10,1,2,3,4,52,3,4,5,0,1

置换过程为：f1(x)=(x+4)%6第三节置换3.3切牌f1(x)=(x+4)%6第三节置换21若n张牌的位置编号为：

1,2,…,n-1,ni+1,…,n-1,n,1,…,i则切牌过程为：fi(x)=(x+n-i-1)%n+1第三节置换如：n=6,i=21,2,3,4,5,63,4,5,6,1,2置换过程为：f1(x)=(x+3)%6+1若n张牌的位置编号为：第三节置换如：n=6222n张牌：1,2,…,n,n+1,…,2n-1,2n两半交错：n+1,1,n+2,2,…,2n-1,n-1,2n,n1,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=1mod2n+1的最小正整数。那么对一副有2n张牌经过e次洗牌后，所有的牌都第一次返回到它们的起始位置。不好的洗牌完美洗牌第三节置换3.4洗牌2n张牌：1,2,…,n,n+1,…,2n-1,2n23然后按列读取这些数：

0,n,2n,…,mn-n,1,n+1,2n+1,…,mn-n+1,…,mn-1对于数x，行：x/n

列：x%n3.5分组交错

给定正整数m和n，针对mn个元素，一个mn分组交换的置换定义为：按行将mm个数据写成mn的矩阵的形式第三节置换然后按列读取这些数：3.5分组交错第三节置换24然后按列读取这些数：

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，进行34分组交错。对应的循环分解为：数据置换位置阶为5按4行3列写出第三节置换然后按列读取这些数：例：12个数据0,1,2,3,425命题：忽略两个不动点0和mn-1，mn分组交错对集合{1,2,3,…,mn-2}的作用是：

x(mx)%(mn-1)举例：36分组交错3x%173x%17

分析：快速洗牌，去掉两个不动点

完美的快速洗牌：

x(2x)%(2n+1)第三节置换命题：忽略两个不动点0和mn-1，mn分组交错3x%17326作业：

(1)计算乘积第三节置换

用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？S14呢？(3)确定对一副20张牌的完美快速洗牌的循环分解。(4)找出35的分组交错置换的循环分解。作业：第三节置换用不相交循环的乘积表示上述的结果，27第四节现代对称密码

香农提出的现代密码设计准则：

Kerchhoff原则：系统的安全性不依赖于对密文或加密算法的保密，而依赖于密钥。惟一需要保密的是密钥；－－决定了古典密码学与现代密码学。

一个好的密码将融合混淆和扩散

混淆：混淆明文的不同部分；

扩散：对攻击者隐藏一些语言的局部特征；

现代密码将结合换位和代替：

代替密码在混淆上是有效的；

换位密码扩散性较好。第四节现代对称密码香农提出的现代密码设计准则：284.1数据加密标准DES(DataEncryptionStandard)

1976年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。

DES是一个分组加密算法，对称密码，64位分组，密钥长度为64位(实际长度为56位)。第四节现代对称密码现代密码算法的特点：

只要保证密钥安全，就能保证加密信息的安全。对称密码算法：很好地融合了混淆和扩散；

DES、AES、IEDA、RC6等非对称密码算法：基于数学难题；

RSA、ECC、ElGamal等4.1数据加密标准DES(DataEncryption29

DES的整个算法是公开的，系统的安全性靠密钥保证。算法包括三个步骤：初始置换IP、16轮迭代的乘积变换、逆初始变换IP-1。

1.初始置换IP

初始置换IP可将64位明文M=m1m2…m64的位置进行置换，得到乱序的64位明文组M0=m58m50…m7。

2.逆初始置换IP-1

逆初始置换IP-1将16轮迭代后的64比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密文组。

IP和IP-1的作用主要是打乱输入的ASCII码字划分关系，并将明文校验码变成IP输出的一个字节。第四节现代对称密码DES的整个算法是公开的，系统的安全性靠第四节30第四节现代对称密码第四节现代对称密码31第四节现代对称密码第四节现代对称密码32第四节现代对称密码第四节现代对称密码33【举例】设64位明文M为：0000000011111111010101010001000110001000110011000011001110101010则经过IP置换后的M0为：0010011001001110001001100100111010110010110000101011001011000010转换过程如下：第四节现代对称密码【举例】设64位明文M为：第四节现代对称密码34

3.乘积变换

乘积变换是DES算法的核心部分。将经过IP置换后的数据分成32位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的32位进行一系列的加密变换，然后把左边的32位与右边得到的32位逐位进行异或操作，作为下一轮迭代时左边的段。迭代公式为：

Li=Ri-1，Ri=Li-1f(Ri-1,ki)：按位异或操作运算符，即按位作模2相加运算。运算规则为：10=1，01=1，00=0，11=0

f的功能是将32比特的数据经过选择扩展运算

E、密钥加密运算、选择压缩运算S和置换运算P转换为32比特的输出。第四节现代对称密码3.乘积变换迭代公式为：Li=Ri-1，35第四节现代对称密码第四节现代对称密码36

(1)选择扩展运算E

选择扩展运算下可将输入的32比特Ri-1扩展成48位的输出。令s表示E原输入数据比特的下标，则E的输出是将原下标s为0或1(模4)的各比特重复一次得到的，实现数据扩展。第四节现代对称密码(1)选择扩展运算E第四节现代对称密码37

(2)密钥加密运算密钥加密运算将48比特的子密钥ki与选择扩展运算E输出的48比特数据进行按位异或运算。【举例】设32比特数据Ri-1为00000000111111110000000011111111，48比特子密钥ki为00000000

1111111101010101101010101100110010001000，求Ri-1经过选择扩展运算E后与子密钥ki异或后的结果。第四节现代对称密码(2)密钥加密运算第四节现代对称密码38

16个子密钥ki的产生：

64比特初始密钥k经过换位函数PC-1将位置号为8,16,24,32,40,48,56和64的8位奇偶位去掉并换位；换位后的数据分为2组，经过循环左移位LSi和换位函数PC-2变换后得到每次迭代加密用的子密钥ki。第四节现代对称密码16个子密钥ki的产生：第四节现代对称密码39第四节现代对称密码第四节现代对称密码40

LSi表示求子密钥ki时将Ci-1和Di-1进行循环左移，其移位位数为：

(3)选择压缩运算选择压缩运算可将密钥加密运算后的48比特数据从左至右分成8组，每组为6比特，并行迭入8个S盒后压缩成32比特输出。每个S盒的输入为6比特，输出为4比特，以完成压缩变换。对于某个S盒Si，假设其输入为b1b2b3b4b5b6，在Si表中找到b1b6行，b2b3b4b5

列的整数，转换为4位二进制就是输出的4比特数据。第四节现代对称密码LSi表示求子密钥ki时将Ci-1和Di-1进行41第四节现代对称密码第四节现代对称密码42第四节现代对称密码第四节现代对称密码43【举例】设S5的输入为b1b2b3b4b5b6=110110。则(b1b6)2=(10)2=2，(b2b3b4b5)2=(1011)2=11在S5中找到行为2，列为11的数据5转换为4位二进制为0101，所以S5的输出为0101。

(4)置换运算PS1~S8盒的输出合成32比特数据后，用换位表p进行置换，得到的32比特数据就是f(Ri-1,ki)的输出。第四节现代对称密码【举例】设S5的输入为b1b2b3b4b5b6=11011044在密码学中的应用课件45

DES的解密算法和加密算法相同，只是在解密过程中将子密钥的顺序颠倒。

DES的出现在密码史上是个创举。以前任何设计者对于密码体制细节都是严加保密的。自公布以来，它一直活跃在国际保密通信的舞台上，成为商用保密通信和计算机通信的最常用的加密算法。由于DES的安全性完全依赖于密钥，而其64位的密钥太短，因而出现了许多DES的改进算法，如三重DES、分组反馈连接式DES以及密码反馈模式DES等。随着新的攻击手段和改进的加密算法的不断出现，DES也许将完成它的历史使命。高级加密标准AES评选于2000年10月结束，Rijdael算法为AES的唯一算法。第四节现代对称密码DES的解密算法和加密算法相同，只是在解密第四节464.DES的安全性

(1)差分分析

1990年Biham和Shamir提出差分密码分析。是一种比穷举攻击有效的选择明文的攻击方法。差分分析的攻击方法是针对DES和其他类似的有固定S盒的算法。DES的S盒恰好最适宜于抗差分分析。最佳差分分析的总结表明对16轮DES的攻击需选择明文247，分析的复杂性为237。

(2)线性密码分析

MitsuruMatsui提出了线形密码分析。使用线性近似值来逼近分组密码的操作。攻击完整的16轮DES，当已知明文的平均数为243时，可得到密钥，是最有效的攻击DES的方法。第四节现代对称密码4.DES的安全性第四节现代对称密码47第四节现代对称密码4.2序列密码

1.随机数生成器

(1)任意由确定过程生成的随机数序列，从实际意义上讲都不是随机的。

(2)pRNG(pseudo-randomnumbergenerators):伪随机数发生器，其典型应用是一次一密乱码本。

(3)一个pRNG要求：在不知道密钥的情况下，由随机数序列中已知部分推测下一个数是“困难”的。

(4)伪随机数序列的周期：要求尽可能大对于序列s0,s1,s2,…若存在p，使得si+p=si

则称它为周期为p的周期序列。第四节现代对称密码4.2序列密码(1)任意48第四节现代对称密码2.线性同余发生器

最为广泛使用的伪随机数产生器。

(1)产生方式

sn+1=(a·sn+b)modm∈Zm

其中0<a<m,0b<m，初值s0称为种子。

(2)分析

a,b,m的取值是产生高质量随机数的关键。①取a=2,b=7,m=17，则

sn+1=(2·sn+7)mod17

取种子s0=1，生成的伪随机序列为：1,9,8,6,2,11,12,14,1,9,8,6,2,11,12,14,1,9,…序列的周期为8，而且Z17中只有8个元素出现。第四节现代对称密码2.线性同余发生器1,9,8,649第四节现代对称密码②取a=7,b=1,m=17,则sn+1=(7sn+1)mod17

取种子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=asimodp的周期为a在乘法群Z/p中的阶l。而且，l|p-1，且当a为模p的本原根时，l=p-1。

定理2：线性同余发生器si+1=asi+bmodp的周期为a在Zp中的阶，只要种子s0不等于坏种子

sbad=-(a-1)-1bmodp举例：求sn+1=7sn+2mod13的坏种子sbad。第四节现代对称密码②取a=7,b=1,m=17,则s50

古典密码的两大机制：

代替密码：字母表范围内替换；

换位密码：在消息内变换字母的位置。2.1代替密码

1.描述密钥是字母表的任意组合，有一个明密对应表；密钥空间巨大：26!；单表代替密码的两个特例：移位密码和仿射密码。

2.举例首先选加密表；为了便于记忆，协商一个密钥：

DOYOULIKETHISBOOK

去掉重复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz

DOYULIKETHSBACFGJMNPQRVWXZ第二节代替与换位古典密码的两大机制：abcdefghijkl51第二节代替与换位2.2换位密码

1.机制：单个字符不变而位置改变。如将文本翻转：明文computersystems

密文SMETSYSRETUPMOC2.特点：

(1)密文长度与明文长度相同；

(2)唯密文攻击可能得到多种不同的破译结果；如keep－peek；live－evil－vile3.分组换位密码针对固定大小的分组进行操作。举例：明文canyouunderstand(1)列换位法设密钥k=4，将明文进行分组排列第二节代替与换位2.2换位密码52canyouunderstand按列读出密文：

CODTAUEANURNYNSDCANYOUUNDERSTAND按行读出明文：

canyouunderstand明文：canyouunderstand按4个字符一行分组排列按4个字符一列分组排列12341234第二节代替与换位canyouunderstand按列密文：CANYOUUND53按列读出typecanyouunderstand密文：

YNSDNURNCODTAUEACANYOUUNDERSTAND按行读出明文：

canyouunderstand明文：canyouunderstand按4个字符一行分组排列按type(3,4,2,1)填入123434

21YNSDNURNCODTAUEA(2)密钥为字符串type1234按密钥长度分组第二节代替与换位按列typecanyouunders54(3)矩阵换位法：置换矩阵作为密钥明文：canyouunderstandcanyouunderstandncyauonurdsentda密文：NCYAUONURDSENTDA按置换矩阵的阶4分组canyouunderstandNCYAUONURDSENTDA明文：canyouunderstand解密置换矩阵：说明：第二节代替与换位(3)矩阵换位法：置换矩阵作为密钥明文：canyouunde55第二节代替与换位2.3频率攻击1.原理：利用自然语言的频率攻击字母出现的频率有规律：

e:11.67t:9.53o:7.81a:7.73…the:4.65to:3.02of:2.61and:1.85…2.应用：对古典密码进行唯密文攻击。3.举例：对仿射密码的攻击密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP

统计字母出现的次数：

F－6G－4H－3J－3……

猜测：e(4)－F(5)t(19)－G(6)

则有：Ea,b(e)=FEa,b(t)=G第二节代替与换位2.3频率攻击1.原理：利用自然语言56第二节代替与换位Ea,b(4)=(a4+b)%26Ea,b(19)=(a19+b)%265=(4a+b)%266=(19a+b)%26a=15-1%26=7b=3加密密钥a-1%26=15-a-1b=-15×3%26=7解密密钥Ea,b(x)=(7x+3)%26解密函数为：E15,7(x)=(15x+7)%26解密后的明文为：

meetmeaftermidnightinthealley第二节代替与换位Ea,b(4)=(a4+b)%2657第二节代替与换位4.举例：对代替密码的攻击

KOSBMKKBSISSYFSJNFKBMESKOSIDYIFPKFJSSMK.thetheeeeeeeetttttooooniiilllkbbssddbay

分析：由ESROL得到er,s,o,l或re,s,o,lloser或

sorel那么：由VIERD得到drive或irevd所以比较合理的明文是：loser

drive5.举例：对换位密码的攻击

ESROLVIERD第二节代替与换位4.举例：对代替密码的攻击IDYIF58第二节代替与换位作业：(1)解密由仿射密码加密的密文：

VCLLCPBKLCLJKXXCHCP(2)解密用简单换位密码加密的密文：

EAGGARDAIREP第二节代替与换位作业：(1)解密由仿射密码加密的密文：593.1群

1.二元运算

定义：设s为集合，函数f:sss称为s上的二元运算或代数运算。满足：可计算性：s中任何元素都可以进行这种运算；单值性：运算结果唯一；封闭性：s中任何两个元素运算结果都属于s。

2.群的定义

定义：设<G,>是代数系统，为G上的二元运算，如果运算是可结合的，则称<G,>半群。若<G,>为半群，并且二元运算存在单位元eG，则称<G,>为幺半群；若<G,>为半群，并且二元运算存在单位元eG，G中的任何元素x都有逆元x-1G，称<G,>为群，简记为G。第三节置换3.1群第三节置换60

举例：

(1)<Z,+>是群，其中Z为整数集合，+是普通的加法，单位元是0，整数x的逆元是-x。

(2)<Z6,>是群，Z6={0,1,2,3,4,5}，为模6加法。显然满足结合律，单位元是0；由于15=0，24=0，33=0，所以1和5互为逆元，2和4互为逆元，3和0的逆元仍然是3和0。

3.群中元素的阶

定义：设<G,>是群，aG，nZ，则a的n次幂为

en=0an=an-1an>0(a-1)m

n<0,n=-m

举例：在群<Z,+>中，30=0，35=15，3-5=-15

在群<Z3,>中，20=0，23=0，2-3=0第三节置换举例：第三节置换61

阶的定义：

(1)设<G,>是群，aG，使得等式ak=e成立的最小正整数k称为a的阶，记做|a|=k，a称为k阶元，若不存在这样的整数k，则a称为无限阶元。例如：在<Z6,>中，2和4是3阶元，3是2阶元，

1和5是6阶元，0是1阶元。在<Z,+>中，0是1阶元，其他都是无限阶元。

(2)设<G,>为群，aG，且|a|=r。设k是整数，则ak=e当且仅当r|k。

(3)设<G,>为群，则群中任何元素a与其逆元a-1

具有相同的阶。第三节置换阶的定义：第三节置换624.循环群和置换群

定义1：设<G,>为群，如果存在一个元素aG，使得G={ak|kZ}，则称G为循环群，记做G=<a>，称a为生成元。若|a|=n，则G称为n阶循环群。例如：

<Z6,>是循环群，其中Z6={0,1,2,3,4,5,}，为模6加法，生成元为1或5。

<Z,+>是循环群，生成元为1或-1。

<Zn,+>是循环群，Zn={0,1,…,n-1,}，生成元为1。第三节置换4.循环群和置换群第三节置换63

定义3：设s={1,2,…,n}，s上的n!个置换构成集合sn，则称sn与置换的复合运算◦构成的群<sn,◦>为s上的n元对称群，<sn,◦>的任意子群称为s上的n元置换群。第三节置换

定义2：设s={1,2,…,n}，s上的任何双射映射函数:ss称为s上的n元置换，记为：定义3：设s={1,2,…,n}，s上的n!个置换构643.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。置换与集合内容无关第三节置换3.2置换概念平凡置换e：没有移动任何元素的置换。置换与集合652.置换的合成或乘积

设g和h是两个置换，先应用h，再应用g，

记为：g◦h或gh

注意：

g◦h≠h◦g

置换的合成满足结合律：(g◦h)◦k=g◦(h◦k)3.逆置换

对于任意置换g，存在一个逆置换g-1，满足：

g◦g-1=g-1◦g=e4.图表记法

用来计算两个置换的乘积。如：第三节置换2.置换的合成或乘积第三节置换665.循环

最简单的置换是不同长度的循环。一个k循环满足：

f(i1)=i2,f(i2)=i3,…,f(ik-1)=ik,f(ik)=i1，对于任意j(i1,i2,…,ik)，有f(j)=j。

举例：则：可见：g◦h≠h◦g，具有不可交换性。记作：(i1,i2,…,ik)(12)(13)第三节置换5.循环则：可见：g◦h≠h◦g，具有不可交换性。记作：676.结论

(1)如果g是一个k循环，那么gk=e。注意：一个k循环有k种表示法。比较：

(123)与(132)(123)=(231)=(3

12)(132)如：则：即：对某个集合应用g操作k次，不会对集合产生任何影响。第三节置换6.结论注意：一个k循环有k种表示法。(123)=(68(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称为不相交的循环。第三节置换(2)置换的阶(3)不相交的循环第三节置换69

一个置换g的阶k=不相交循环分解中各循环长度的最小公倍数。如：思考：如果一副50张的牌洗得好，重复洗8次后所有的牌将返回初始位置。阶为4(4)置换的不相交循环分解任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。=(1

457)(23)(6)第三节置换一个置换g的阶k=不相交循环分解中各循环长度的最703.3切牌

最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。

n张牌：0,1,…,n-1i+1,…,n-1,0,1,…,i

切牌过程为：fi(x)=(x+n-i-1)%n

如：n=6,i=10,1,2,3,4,52,3,4,5,0,1

置换过程为：f1(x)=(x+4)%6第三节置换3.3切牌f1(x)=(x+4)%6第三节置换71若n张牌的位置编号为：

1,2,…,n-1,ni+1,…,n-1,n,1,…,i则切牌过程为：fi(x)=(x+n-i-1)%n+1第三节置换如：n=6,i=21,2,3,4,5,63,4,5,6,1,2置换过程为：f1(x)=(x+3)%6+1若n张牌的位置编号为：第三节置换如：n=6722n张牌：1,2,…,n,n+1,…,2n-1,2n两半交错：n+1,1,n+2,2,…,2n-1,n-1,2n,n1,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=1mod2n+1的最小正整数。那么对一副有2n张牌经过e次洗牌后，所有的牌都第一次返回到它们的起始位置。不好的洗牌完美洗牌第三节置换3.4洗牌2n张牌：1,2,…,n,n+1,…,2n-1,2n73然后按列读取这些数：

0,n,2n,…,mn-n,1,n+1,2n+1,…,mn-n+1,…,mn-1对于数x，行：x/n

列：x%n3.5分组交错

给定正整数m和n，针对mn个元素，一个mn分组交换的置换定义为：按行将mm个数据写成mn的矩阵的形式第三节置换然后按列读取这些数：3.5分组交错第三节置换74然后按列读取这些数：

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，进行34分组交错。对应的循环分解为：数据置换位置阶为5按4行3列写出第三节置换然后按列读取这些数：例：12个数据0,1,2,3,475命题：忽略两个不动点0和mn-1，mn分组交错对集合{1,2,3,…,mn-2}的作用是：

x(mx)%(mn-1)举例：36分组交错3x%173x%17

分析：快速洗牌，去掉两个不动点

完美的快速洗牌：

x(2x)%(2n+1)第三节置换命题：忽略两个不动点0和mn-1，mn分组交错3x%17376作业：

(1)计算乘积第三节置换

用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？S14呢？(3)确定对一副20张牌的完美快速洗牌的循环分解。(4)找出35的分组交错置换的循环分解。作业：第三节置换用不相交循环的乘积表示上述的结果，77第四节现代对称密码

香农提出的现代密码设计准则：

Kerchhoff原则：系统的安全性不依赖于对密文或加密算法的保密，而依赖于密钥。惟一需要保密的是密钥；－－决定了古典密码学与现代密码学。

一个好的密码将融合混淆和扩散

混淆：混淆明文的不同部分；

扩散：对攻击者隐藏一些语言的局部特征；

现代密码将结合换位和代替：

代替密码在混淆上是有效的；

换位密码扩散性较好。第四节现代对称密码香农提出的现代密码设计准则：784.1数据加密标准DES(DataEncryptionStandard)

1976年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。

DES是一个分组加密算法，对称密码，64位分组，密钥长度为64位(实际长度为56位)。第四节现代对称密码现代密码算法的特点：

只要保证密钥安全，就能保证加密信息的安全。对称密码算法：很好地融合了混淆和扩散；

DES、AES、IEDA、RC6等非对称密码算法：基于数学难题；

RSA、ECC、ElGamal等4.1数据加密标准DES(DataEncryption79

DES的整个算法是公开的，系统的安全性靠密钥保证。算法包括三个步骤：初始置换IP、16轮迭代的乘积变换、逆初始变换IP-1。

1.初始置换IP

初始置换IP可将64位明文M=m1m2…m64的位置进行置换，得到乱序的64位明文组M0=m58m50…m7。

2.逆初始置换IP-1

逆初始置换IP-1将16轮迭代后的64比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密文组。

IP和IP-1的作用主要是打乱输入的ASCII码字划分关系，并将明文校验码变成IP输出的一个字节。第四节现代对称密码DES的整个算法是公开的，系统的安全性靠第四节80第四节现代对称密码第四节现代对称密码81第四节现代对称密码第四节现代对称密码82第四节现代对称密码第四节现代对称密码83【举例】设64位明文M为：0000000011111111010101010001000110001000110011000011001110101010则经过IP置换后的M0为：0010011001001110001001100100111010110010110000101011001011000010转换过程如下：第四节现代对称密码【举例】设64位明文M为：第四节现代对称密码84

3.乘积变换

乘积变换是DES算法的核心部分。将经过IP置换后的数据分成32位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的32位进行一系列的加密变换，然后把左边的32位与右边得到的32位逐位进行异或操作，作为下一轮迭代时左边的段。迭代公式为：

Li=Ri-1，Ri=Li-1f(Ri-1,ki)：按位异或操作运算符，即按位作模2相加运算。运算规则为：10=1，01=1，00=0，11=0

f的功能是将32比特的数据经过选择扩展运算

E、密钥加密运算、选择压缩运算S和置换运算P转换为32比特的输出。第四节现代对称密码3.乘积变换迭代公式为：Li=Ri-1，85第四节现代对称密码第四节现代对称密码86

(1)选择扩展运算E

选择扩展运算下可将输入的32比特Ri-1扩展成48位的输出。令s表示E原输入数据比特的下标，则E的输出是将原下标s为0或1(模4)的各比特重复一次得到的，实现数据扩展。第四节现代对称密码(1)选择扩展运算E第四节现代对称密码87

(2)密钥加密运算密钥加密运算将48比特的子密钥ki与选择扩展运算E输出的48比特数据进行按位异或运算。【举例】设32比特数据Ri-1为00000000111111110000000011111111，48比特子密钥ki为00000000

1111111101010101101010101100110010001000，求Ri-1经过选择扩展运算E后与子密钥ki异或后的结果。第四节现代对称密码(2)密钥加密运算第四节现代对称密码88

16个子密钥ki的产生：

64比特初始密钥k经过换位函数PC-1将位置号为8,16,24,32,40,48,56和64的8位奇偶位去掉并换位；换位后的数据分为2组，经过循环左移位LSi和换位函数PC-2变换后得到每次迭代加密用的子密钥ki。第四节现代对称密码16个子密钥ki的产生：第四节现代对称密码89第四节现代对称密码第四节现代对称密码90

LSi表示求子密钥ki时将Ci-1和Di-1进行循环左移，其移位位数为：

(3)选择压缩运算选择压缩运算可将密钥加密运算后的48比特数据从