第6讲-经典密码学分析课件

第6讲经典密码学古典加密算法分组加密算法第6讲经典密码学古典加密算法1密码学相关术语密码编码学(cryptography)是密码体制的设计学，而密码分析学(cryptanalysis)则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学(cryptology)。如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。如果密码体制中的密码不能被可使用的计算资源破译，则这一密码体制称为在计算上是安全的。密码学相关术语密码编码学(cryptography)是密码体2基本术语使消息保密的技术和科学叫做密码编码学（cryptography），从事此行业的叫做密码编码者（cryptographer），密码分析者（cryptanalyst）是从事密码分析的专业人员，密码分析学（cryptanalysis）就是破译密文的科学和技术。密码学（cryptology）作为数学的一个分支，包括密码编码学和密码分析学两部分。基本术语使消息保密的技术和科学叫做密码编码学（cryptog3基本术语(续)消息被称为明文(Plaintext)，用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)

密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数发送者对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)基本术语(续)消息被称为明文(Plaintext)，用某种方4加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)

和解密密钥(DecryptionKey)明文明文密文加密算法解密算法加密密钥解密密钥加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控5一般的数据加密模型E加密算法D解密算法加密密钥K解密密钥K明文X明文X密文Y=EK(X)截取者截获篡改密钥源安全信道一般的数据加密模型ED加密密钥K解密密钥K明文X明文6密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条7密码分析密码分析学，是攻击者在不知道密钥的情况下，恢复出明文的科学。对密码进行分析的尝试称为攻击（Attack)。攻击密码的方法：穷举法，又称强力法（Brute-force）分析法密码分析密码分析学，是攻击者在不知道密钥的情况下，恢复出明文8密码分析Kerchkhoff原则假设攻击者是在已经密码体制的前提下来破译密码系统的密钥；最常见的破解类型如下：唯密文攻击：攻击者有一些密文，它们是使用同一加密算法和同一密钥加密的；已知明文攻击：攻击者不但得到一些密文，而且能够得到这些密文对应的明文；密码分析Kerchkhoff原则9密码分析3选择明文攻击：攻击者不仅得到一些密文和明文，而且能选择用于加密的明文；4选择密文攻击：攻击者可以选择不同的密文来解密，并能够得到解密后的明文；这一切的目的都是：破译出密钥一般说来：密码系统应该经得起已知明文的攻击。如果攻击者无论得到多少密文，都没有足够的信息去恢复明文，则密码系统是无条件安全的。理论上，只有一次一密的系统才能真正实现。密码分析3选择明文攻击：10古典密码--信息隐藏Youcan'tunderstandYoucan'tunderstandSteganography也称隐写术：将秘密消息隐藏在其他消息中。隐形墨水，字符上的针眼，手写字符的差异，字符上的铅笔记号等图象中隐写：用消息位代替图象的每个字节的最不重要的位，而肉眼无法看出差异；隐写术不使用算法或者密钥古典密码--信息隐藏Youcan'tunderstand11Steganography(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.Steganography(a)Threezebras121.移位密码体制(单字母)设P=C=K=Z/(26),对,定义同时dk(y)=y-k(mod26)注1*：26个英文字母与模26剩余类集合{0,….,25}建立一一对应：ABCDEFGHIJKLMNOPQRSTUVWXYZ012345678910111213141516171819202122232425

2*.当k=3时，为Caesar密码：若明文：caesarcipher

密文：FDHVDUFLSKHU

实际算法为：有

同时有，d3(y)=y-3(mod26)1.移位密码体制(单字母)设P=C=K=Z/(26),对133*.一个密码体制要是实际可用必须满足的特性每一个加密函数ek和每一个解密函数dk都能有效地计算。破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。3*.一个密码体制要是实际可用必须满足的特性每一个加密函数e14移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文c变成了密文F移位密码移位密码(substitutioncipher)的15移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a变成了密文D移位密码移位密码(substitutioncipher)的16移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文e变成了密文H移位密码移位密码(substitutioncipher)的17凯撒密码的改进凯撒密码只有25个密钥k，非常不安全；若有意改变字母的排列顺序，可增大密钥空间；例如：使用密钥KeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopgrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectacularbdfghijkmnoqvwxyz泄露给破译者的信息更少；凯撒密码的改进凯撒密码只有25个密钥k，非常不安全；182.替换密码体制设P=C=Z/(26)，K是由26个符号0，1,..,25的所有可能置换组成。任意，定义

dπ(y)=-1(y)=x,π-1是π的逆置换。

注：1*.置换π的表示：

2*密钥空间K很大，|K|=26!≈4×1026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间2.替换密码体制设P=C=Z/(26)，K是由26个符号0，193.仿射密码体制替换密码的另一个特例就是仿射密码。加密函数取形式为

要求唯一解的充要条件是gcd(a,26)=1

该体制描述为：

设P=C=Z/(26)

对

定义ek(x)=ax+b(mod26)

dk(y)=a-1(y-b)(mod26)

3.仿射密码体制替换密码的另一个特例就是仿射密码。20例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19,易见dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：例子，设k＝（7，3），注意到7-1(mod26)=15,21英文中字母的使用频率02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率E使用最多；然后是TRNIOAS其他字母使用较少最少的是JKQXZ英文中字母的使用频率02468101214ABCDEFGH224.维吉尼亚密码(Vigenere,多字母)设m为一固定的正整数，定义P=C=K=(Z/(26))m,对一个密钥K＝（k1,k2,…,km),定义ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x这里的所有的运算都是在（mod26)中进行的。4.维吉尼亚密码(Vigenere,多字母)设m为一固定的23维基尼亚密码（Vigenere）-示例若密钥字为deceptive，即m=9明文wearediscoveredsav的加密过程：明文：wearediscoeredsav密钥：deceptivedeceptive密文：ZICVTWQNGRZGVTWAVZ密钥字母d对应数字3，因而明文字母w在密钥字母d的作用下向后移位3，得到密文字母Z。依次类推；维基尼亚密码（Vigenere）-示例若密钥字为decept24维基尼亚密码（Vigenere）维基尼亚密码是多表替换体制，分析起来更加困难。密钥空间大，可能的密钥字达26m

如果秘要字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个；例如，当m=5，密钥空间所含密钥的数量是>1.1x107

明文和密文的字母频率分布相同，仍然能使用统计分析破译维基尼亚密码（Vigenere）维基尼亚密码是多表替换体制，255.Hill密码体制设ｍ为某个固定的正整数，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩阵}对每一个,定义ek(x)=xk(mod26)和dk(y)=yk-1(mod26)注：明文与密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值∈Z*/(26),它为Z/(26)中全体可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：当m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

k

5.Hill密码体制设ｍ为某个固定的正整数，P=C=(Z/(26事实上yi为x1,x2的线性组合，y1=11x1+3x2;y2=8x1+7x2，一般，将取m×m的矩阵K作为我们的密钥：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

换言之，y=xK;且有x=yK-1若K=,可得K-1=若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有事实上yi为x1,x2的线性组合，y1=11x1+3x2;y27（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是对july加密的结果为DELW。为了解密，Bob计算

且因此，得到了正确的明文“july”

（9,20）＝（99＋60,72＋140286.置换密码体制

设m为固定的正整数，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置换构成，对一个密钥π∈K，定义eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))这里π－1为π的逆置换。注：这里的加密与解密仅仅用了置换，无代数运算。例子：设m=6,取密钥

而6.置换密码体制 设m为固定的正整数，P=C=(Z/(2629若给定的明文是：cryptography首先找分成6个字母长的明文组：crypto|graphy求得的密文是：YTCOPRAHGYPR注：事实上，置换密码是Hill密码的特例。给定一个集合{1,2,..,m}的置换矩阵

(置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。)请同学们验证若给定的明文是：cryptography首先找分成6个字母30对上面例子决定的置换π对应：对上面例子决定的置换π对应：31CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc32CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc33CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc34CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc35CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc36CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc37CIPHER145326attackbeginsatfour密文的得出密钥顺序明文先读顺序为1的明文列，即aba

CIPHER密文的得出密钥先读顺序为1的明文列，即ab38CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为2的明文列，即cnu

CIPHER密文的得出密钥再读顺序为2的明文列，即cn39CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为3的明文列，即aio

CIPHER密文的得出密钥再读顺序为3的明文列，即ai40CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为4的明文列，即tet

CIPHER密文的得出密钥再读顺序为4的明文列，即te41CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为5的明文列，即tgf

CIPHER密文的得出密钥再读顺序为5的明文列，即tg42CIPHER145326attackbeginsatfour密文的得出密钥顺序明文最后读顺序为6的明文列，即ksr

因此密文就是：abacnuaiotettgfksr

CIPHER密文的得出密钥最后读顺序为6的明文列，即k43CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文先写下第1列密文aba

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥先写下第1列密文44CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第2列密文cnu

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥再写下第2列密文45CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第3列密文aio

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥再写下第3列密文46CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第4列密文tet

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥再写下第4列密文47CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第5列密文tgf

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥再写下第5列密文48CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文最后写下第6列密文ksr

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列写下密钥最后写下第6列密49CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr

CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密50CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr

CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密51CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr

得出明文：attackbeginsatfour

CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密527.置换密码(栅栏技术)最简单的例子是栅栏技术：按照对角线的顺序写入明文，而按行的顺序读出作为密文。明文：meetmeaftertheparty写为：mematrhpryetefeteat密文：mematrhpryetefeteat7.置换密码(栅栏技术)最简单的例子是栅栏技术：按照对角线的53古典密码小结研究古典密码原理，对于理解、构造和分析现代密码是十分有益的。古典密码小结54序列密码与分组密码序列码体制是将明文X看成是连续的比特流(或字符流)x1x2…，并且用密钥序列

Kk1k2…中的第i个元素ki对明文中的xi进行加密，即序列密码与分组密码序列码体制是将明文X看成是连续的比特55序列密码体制密钥序列产生器种子

I0发端ki密钥序列产生器种子

I0收端ki密文序列明文序列明文序列xixiyiyi在开始工作时种子I0对密钥序列产生器进行初始化。按照模2进行运算，得出：

(9-1)序列密码体制密钥序列产生器种子发端ki密钥序列产生器种子收56序列密码体制密钥序列产生器种子

I0发端ki密钥序列产生器种子

I0收端ki密文序列明文序列明文序列xixiyiyi在收端，对yi的解密算法为：(9-2)序列密码又称为密钥流密码。序列密码体制密钥序列产生器种子发端ki密钥序列产生器种子收57序列密码体制的保密性序列密码体制的保密性完全在于密钥的随机性。如果密钥是真正的随机数，则这种体制就是理论上不可破的。这也可称为一次一密乱码本体制。严格的一次一密乱码本体制所需的密钥量不存在上限，很难实用化。密码学家试图模仿这种一次一密乱码本体制。目前常使用伪随机序列作为密钥序列。关键是序列的周期要足够长，且序列要有很好的随机性（这很难寻找）。序列密码体制的保密性序列密码体制的保密性完全在于密钥的随机58第6讲经典密码学古典加密算法分组加密算法第6讲经典密码学古典加密算法59密码学相关术语密码编码学(cryptography)是密码体制的设计学，而密码分析学(cryptanalysis)则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学(cryptology)。如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。如果密码体制中的密码不能被可使用的计算资源破译，则这一密码体制称为在计算上是安全的。密码学相关术语密码编码学(cryptography)是密码体60基本术语使消息保密的技术和科学叫做密码编码学（cryptography），从事此行业的叫做密码编码者（cryptographer），密码分析者（cryptanalyst）是从事密码分析的专业人员，密码分析学（cryptanalysis）就是破译密文的科学和技术。密码学（cryptology）作为数学的一个分支，包括密码编码学和密码分析学两部分。基本术语使消息保密的技术和科学叫做密码编码学（cryptog61基本术语(续)消息被称为明文(Plaintext)，用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)

密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数发送者对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)基本术语(续)消息被称为明文(Plaintext)，用某种方62加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)

和解密密钥(DecryptionKey)明文明文密文加密算法解密算法加密密钥解密密钥加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控63一般的数据加密模型E加密算法D解密算法加密密钥K解密密钥K明文X明文X密文Y=EK(X)截取者截获篡改密钥源安全信道一般的数据加密模型ED加密密钥K解密密钥K明文X明文64密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条65密码分析密码分析学，是攻击者在不知道密钥的情况下，恢复出明文的科学。对密码进行分析的尝试称为攻击（Attack)。攻击密码的方法：穷举法，又称强力法（Brute-force）分析法密码分析密码分析学，是攻击者在不知道密钥的情况下，恢复出明文66密码分析Kerchkhoff原则假设攻击者是在已经密码体制的前提下来破译密码系统的密钥；最常见的破解类型如下：唯密文攻击：攻击者有一些密文，它们是使用同一加密算法和同一密钥加密的；已知明文攻击：攻击者不但得到一些密文，而且能够得到这些密文对应的明文；密码分析Kerchkhoff原则67密码分析3选择明文攻击：攻击者不仅得到一些密文和明文，而且能选择用于加密的明文；4选择密文攻击：攻击者可以选择不同的密文来解密，并能够得到解密后的明文；这一切的目的都是：破译出密钥一般说来：密码系统应该经得起已知明文的攻击。如果攻击者无论得到多少密文，都没有足够的信息去恢复明文，则密码系统是无条件安全的。理论上，只有一次一密的系统才能真正实现。密码分析3选择明文攻击：68古典密码--信息隐藏Youcan'tunderstandYoucan'tunderstandSteganography也称隐写术：将秘密消息隐藏在其他消息中。隐形墨水，字符上的针眼，手写字符的差异，字符上的铅笔记号等图象中隐写：用消息位代替图象的每个字节的最不重要的位，而肉眼无法看出差异；隐写术不使用算法或者密钥古典密码--信息隐藏Youcan'tunderstand69Steganography(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.Steganography(a)Threezebras701.移位密码体制(单字母)设P=C=K=Z/(26),对,定义同时dk(y)=y-k(mod26)注1*：26个英文字母与模26剩余类集合{0,….,25}建立一一对应：ABCDEFGHIJKLMNOPQRSTUVWXYZ012345678910111213141516171819202122232425

2*.当k=3时，为Caesar密码：若明文：caesarcipher

密文：FDHVDUFLSKHU

实际算法为：有

同时有，d3(y)=y-3(mod26)1.移位密码体制(单字母)设P=C=K=Z/(26),对713*.一个密码体制要是实际可用必须满足的特性每一个加密函数ek和每一个解密函数dk都能有效地计算。破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。3*.一个密码体制要是实际可用必须满足的特性每一个加密函数e72移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文c变成了密文F移位密码移位密码(substitutioncipher)的73移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a变成了密文D移位密码移位密码(substitutioncipher)的74移位密码移位密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文e变成了密文H移位密码移位密码(substitutioncipher)的75凯撒密码的改进凯撒密码只有25个密钥k，非常不安全；若有意改变字母的排列顺序，可增大密钥空间；例如：使用密钥KeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopgrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectacularbdfghijkmnoqvwxyz泄露给破译者的信息更少；凯撒密码的改进凯撒密码只有25个密钥k，非常不安全；762.替换密码体制设P=C=Z/(26)，K是由26个符号0，1,..,25的所有可能置换组成。任意，定义

dπ(y)=-1(y)=x,π-1是π的逆置换。

注：1*.置换π的表示：

2*密钥空间K很大，|K|=26!≈4×1026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间2.替换密码体制设P=C=Z/(26)，K是由26个符号0，773.仿射密码体制替换密码的另一个特例就是仿射密码。加密函数取形式为

要求唯一解的充要条件是gcd(a,26)=1

该体制描述为：

设P=C=Z/(26)

对

定义ek(x)=ax+b(mod26)

dk(y)=a-1(y-b)(mod26)

3.仿射密码体制替换密码的另一个特例就是仿射密码。78例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19,易见dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：例子，设k＝（7，3），注意到7-1(mod26)=15,79英文中字母的使用频率02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率E使用最多；然后是TRNIOAS其他字母使用较少最少的是JKQXZ英文中字母的使用频率02468101214ABCDEFGH804.维吉尼亚密码(Vigenere,多字母)设m为一固定的正整数，定义P=C=K=(Z/(26))m,对一个密钥K＝（k1,k2,…,km),定义ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x这里的所有的运算都是在（mod26)中进行的。4.维吉尼亚密码(Vigenere,多字母)设m为一固定的81维基尼亚密码（Vigenere）-示例若密钥字为deceptive，即m=9明文wearediscoveredsav的加密过程：明文：wearediscoeredsav密钥：deceptivedeceptive密文：ZICVTWQNGRZGVTWAVZ密钥字母d对应数字3，因而明文字母w在密钥字母d的作用下向后移位3，得到密文字母Z。依次类推；维基尼亚密码（Vigenere）-示例若密钥字为decept82维基尼亚密码（Vigenere）维基尼亚密码是多表替换体制，分析起来更加困难。密钥空间大，可能的密钥字达26m

如果秘要字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个；例如，当m=5，密钥空间所含密钥的数量是>1.1x107

明文和密文的字母频率分布相同，仍然能使用统计分析破译维基尼亚密码（Vigenere）维基尼亚密码是多表替换体制，835.Hill密码体制设ｍ为某个固定的正整数，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩阵}对每一个,定义ek(x)=xk(mod26)和dk(y)=yk-1(mod26)注：明文与密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值∈Z*/(26),它为Z/(26)中全体可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：当m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

k

5.Hill密码体制设ｍ为某个固定的正整数，P=C=(Z/(84事实上yi为x1,x2的线性组合，y1=11x1+3x2;y2=8x1+7x2，一般，将取m×m的矩阵K作为我们的密钥：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

换言之，y=xK;且有x=yK-1若K=,可得K-1=若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有事实上yi为x1,x2的线性组合，y1=11x1+3x2;y85（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是对july加密的结果为DELW。为了解密，Bob计算

且因此，得到了正确的明文“july”

（9,20）＝（99＋60,72＋140866.置换密码体制

设m为固定的正整数，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置换构成，对一个密钥π∈K，定义eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))这里π－1为π的逆置换。注：这里的加密与解密仅仅用了置换，无代数运算。例子：设m=6,取密钥

而6.置换密码体制 设m为固定的正整数，P=C=(Z/(2687若给定的明文是：cryptography首先找分成6个字母长的明文组：crypto|graphy求得的密文是：YTCOPRAHGYPR注：事实上，置换密码是Hill密码的特例。给定一个集合{1,2,..,m}的置换矩阵

(置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。)请同学们验证若给定的明文是：cryptography首先找分成6个字母88对上面例子决定的置换π对应：对上面例子决定的置换π对应：89CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc90CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc91CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc92CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc93CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc94CIPHER145326attackbeginsatfour置换密码置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。CIPHER置换密码置换密码(transpositionc95CIPHER145326attackbeginsatfour密文的得出密钥顺序明文先读顺序为1的明文列，即aba

CIPHER密文的得出密钥先读顺序为1的明文列，即ab96CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为2的明文列，即cnu

CIPHER密文的得出密钥再读顺序为2的明文列，即cn97CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为3的明文列，即aio

CIPHER密文的得出密钥再读顺序为3的明文列，即ai98CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为4的明文列，即tet

CIPHER密文的得出密钥再读顺序为4的明文列，即te99CIPHER145326attackbeg