2 古典密码的演化

现代密码学概论7/29/202610:55AM1江苏大学计算机科学与通信工程学院主讲人：潘森杉第2讲古典密码的演化名词与基本概念311/10/1510:57加密是获得信息保密的实用工具，保密是密码学的核心现代加密技术是一些变换算法，将消息看成空间中的数字或者代数元，然后在“有意义的消息区”和“不可理解的消息区”之间进行变换。原文，有意义消息区中的消息和加密算法的输入密文，加密算法不可理解的输出明文，忽视加密输入消息的可理解性，可以是随机数或者密文消息的第二次加密输入解密，加密变换的逆变换，用于恢复信息密码体制，加密算法、解密算法、消息和密钥的形式描述构成了一个密码系统的密码体制。11/10/1510:574DefinitionofCryptographicSystem:密码体制构成如下：

明文消息空间M

密文消息空间C

加密密钥空间K

解密密钥空间K’有效的密钥生成算法：

有效的加密算法：

有效的解密算法：密码体制图示511/10/1510:57Ke和Kd相同时，就是对称密码体制，也称单钥密码体制；Ke和Kd成对出现且互不相同时，称为公钥密码体制或者非对称密码体制。设计密码被广泛认可的约定：Kerchoffs原理

611/10/1510:57

Knowledgeofthealgorithmandkeysizeaswellastheavailabilityofknownplaintext,arestandardassumptionsinmoderncryptanalysis.Sinceanadversarymayobtainthisinformationeventually,itispreferablenottorelyonitssecrecywhenassessingcryptographicstrength《保密系统的通信理论》

byClaudeShannon混淆(confusion)：密钥密文扩散(diffusion)：明文密文缺点：错误传播711/10/1510:578作业1：已知一段问题的密文为FRQJUDWXODWLRNVZKDWLVBRXUQDPH请解密并回答上述问题。古典密码体制古典密码有两个基本工作原理：代换(substitution)置换(permutation)这两个基本工作原理在仍然是现代对称加密算法的最重要的核心技术现代对称密码DES和AES中就有这两个工作原理的应用911/10/1510:57代换密码

1移位密码shiftcipher在移位密码中，密钥空间、明文空间和密文空间是相同的，加密和解密的定义为：11/10/1510:5710因为JuliusCaesar用过N＝26,k=3时的加密算法,它也称为恺撒密码注：a除以b所得余数记为amodb实用加密体制需满足：

1.Εk，Dk易于计算

2.对任何敌手，即使获得密文y，不可能由此确定k和x。已知y，试图得到k的过程，称为密码分析。要求：通过y计算k至少与通过y计算x同样困难。2仿射密码affinecipher11/10/1510:5712此处，要求gcd(k₁,N)=1因为这样才能使得k₁×m(modN)取遍消息空间ZN定义：a∈Zm

，若存在a’∈Zm

,使aa’≡a’a≡1(modm)，a’称为a在Zm上的乘法逆，记为a-1

modm，简记为a-1

。解：7-1mod26=15，故加密解密函数为：

Ek(x)=7x+21mod26Dk(y)=15(y-21)mod26security1842201781924计算7x+21得：1723951025247密文RXJFKZYH例：k=(7,21)，对security加密。作业已知加密算法是仿射密码，对security的加密结果是RXJFKZYH，如何破解该密码（能够求出密钥k=(k1,k2)或对VLXIJH解密）。147/29/202610:55AM1511/10/1510:573单表代换密码例：原文proceedmeetingasagreed=>密文cqkzyyrjyyowftvlvtqyyr明文和密文消息串中各包含了22个消息，而密钥空间大小为26!>4×1026，与消息空间的大小比是非常大的单表密码是非常弱的：每一个明文字符被加密成唯一的密文字符，可以采用密码分析中的“频度分析”来攻击。(譬如英文里e是使用频率最高的字符，对应密文中y是最高的,如此……)思考：为什么不用空格？1611/10/1510:57etaonrishdlfcmugypwbvkjxqz11/10/1510:57abcdefghijklm0.0820.0150.0280.0430.1270.0220.0200.0610.0700.0020.0080.0400.024nopqrstuvwxyz0.0670.0750.0190.0010.0600.0630.0910.0280.0100.0230.0010.0200.001仿射密码的密码分析例：利用仿射密码中获得密文：

FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH(57)频数统计：R(8),D(7),EHK(5),FV(4),S(3),…R←eD←te(4)=4a+b=17e(19)=19a+b=3

a=6b=19,gcd(a,26)=2,密钥不合法

E←t4a+b=1719a+b=4

a=13,密钥不合法

H←t4a+b=1719a+b=7

a=8,密钥不合法

K←t4a+b=1719a+b=10

a=3,b=5K=(3,5)为合法密钥解密函数为：dK(y)=a-1(y-b)=9y-19对密文解密：algorithmsarequitegeneraldefinitionsofarithmticprocesses例题Vigenère密码密钥为gold，对应表(6,14,11,3)其中，A=0,……，Z＝25输入为proceedmeetingasagreed，对应下表的第一行则输出对应第三行，为vfzfksopkseltulvguchkr11/10/1510:57194多表密码PolyalphabeticCiphers

Vigenère密码的密码分析确定密钥字的长度m

Kasiski测试法

(1863FriedrichKasiski)----两个相同的明文段将被加密成相同的密文段，位置间距≡0(modm)----搜索长度至少为3的密文段，记下其离起点的那个密文段的距离，可猜测m为它们的最大公因子的因子。

重合指数法(1920WilliamFriedman)----x=x1x2…xn的重合指数Ic(x)定义为x中两个随机元素相同的概率假设f0,f1,…,f25为A,B,…,Z在x中出现的频数，有Cn2种方法选择x中任意两个元素，有Cfi2种方法使所选字母皆为i，故:Ic(x)=(∑Cfi2)/Cn2=(∑fi(fi-1))/n(n-1)x为英文文本串，A,B,…,Z出现的期望概率p0,p1,…,p25Ic(x)≈∑pi2=0.065用维吉尼亚密码加密：y=y1y2…yn

y1=y1ym+1y2m+1…y2=y2ym+2y2m+2………ym=ymy2my3m…m如果是密钥字长度，Ic(yi)≈0.065，否则yi更为随机，其值接近0.038(完全随机串的值26(1/26)2)已知m，确定K=(k1,k2,…km)----f0,f1,…,f25为A,B,…,Z在yi中出现的频数，n’=n/m为yi长度

26个字母在yi中的概率分布为：

f0/n’,f1/n’,…,f25/n’----

yi中是由明文子集中字母移ki位所得，故移位后概率分布fki/n’,f1+ki/n’,…,f25+ki/n’

应近似等于p0,p1,…,p25----

定义Mg=∑(pifi+g)/n’,g=0,1,…25

如果g=ki,Mg

≈∑pi2=0.065

如果g≠ki，Mg

一般应该＜0.065

对每个i，由此确定ki11/10/1510:5723换位密码换位密码，也成为置换密码，通过重新排列消息中元素的位置而不改变元素本身来变换一个消息，这种思想广泛应用于现代分组密码的构造。密钥为置换：加密算法为：显然有：解密算法为：

共有b!种不同的密钥，或者说一个明文对应b!种可能的密文。

思考为什么换位密码对于频率分析技术也是脆弱的。11/10/1510:5724注意空格的处理！希尔密码(HillCipher)P=C=(Z26)m,m(≥2)∈Z，

K={定义在Z26上的m阶可逆矩阵}对每一个K∈K

，定义：

eK(x)=xK=(x1,x2,…,xm)K

dK(y)=yK-1=(y1,y2,…,ym)K例：密钥，试对明文abcd加密。解：(a,b)=(0,1)加密

(0,1)

K

=(3,7)=(D,H)；

(c,d)=(2,3)加密

(2,3)K=(31,37)=(5,11)=(F,L)。所以，明文abcd经过Hill密码加密后，变为密文DHFL.

对DHFL解密：

(D,H)=(3,7)解密(3,7)

K-1

=(0,1)=(a,b)(F,L)=(5,11)解密(5,11)K-1

=(2,3)=(c,d)得明文abcdHill密码的密码分析唯密文攻击较难，已知明文攻击易假设敌手已知m,至少有m个不同的明-密文对:xj=(x1,j,…,xm,j),yj=(y1,j,…,ym,j)有yj=e(xj)

定义X=(xij),Y=(yij),有Y=XK

如果X可逆，K=X-1Y

如果X不可逆，重新选择m个明-密文对。

例：m=2的Hill密码：friday→PQCFKU,求K。解：eK(5,17)=(15,16)eK(8,3)=(2,5)eK(0,24)=(10,20)注：如果不知道m，假设m不太大，可试m=2,3,…，直到找到密钥。古典密码的应用与安全性基于字符的代换密码，明文消息空间是字母表，加密就是逐字符的代换，明文消息中一个字符将被加密为密文消息中一个固定的字符(自然语言中，字符有固定的频度，频度分析技术，可由密文消息发现明文或者密钥消息)多表密码和换位密码比代换密码安全，但是如果密钥很短而消息很长，密码分析技术还是很容易攻破这样的密码如果密钥使用了某些条件，那么古典密码甚至简单代换密码也可以非常安全。实际上，正确地使用密钥后，简单代换密码可以广泛的应用于密码体制和协议。2811/10/1510:5711/10/1510:5729Vernam密码和一次一密(One-TimePad)明文密钥密文与加密算法：其中，表示均匀、随机地选取1.Vernam密码满足是代换密码的特例，如果密钥串仅用一次，就满足了密码的两个强安全性条件。——无条件安全。2.k=(逐比特的)，由于任意m能产生c,所以密文消息串不能提供给窃听者任何关于明文m的信息。古典密码、频率分析和一次一密11/10/1510:57流密码分组密码——将明文分成固定长度的组，用相同的密钥和算法对每组加密的到固定长度的密文

x=x1x2x3…

KKK…y=y1y2y3…流密码——又称序列密码，每次加密1比特或1字节

x=x1x2x3…

密钥流z=z1z2z3…z1z2z3…y=y1y2y3…定义：

同步流密码是一个六元组(P，C，K，L，E，D)和一个函数g

P——明文空间，C——密文空间，K——密钥空间

L——密钥流字母表，

g——密钥流生成器，以K为输入，输出密钥流为

z=z1z2z3…

满足：每个z，存在ez∈E

和相应的dz∈D，使得dz(ez(x))=x

，对每个x∈

P

例：维吉尼亚密码的密钥长度为m，P=C=L=Z26，K=(Z26)mK=(k1,k2,…,km)∈K，定义密钥流z=z1z2z3…=k1k2…kmk1k2…kmk1k2…km…定义ez(x)=x+zmod26dz(y)=y-zmod26注：分组密码可视为流密码的特例周期流密码：密钥流是周期序列如前例维吉尼亚密码可视为周期为m的周期流密码流密码常以二元字符表示，加解密可用硬件有效实现m级线性移位寄存