现代密码学第2章：经典密码学

1、1经典密码学现代密码学第2章2本章主要内容 1 1、密码体制的定义与分类、密码体制的定义与分类 2 2、代替密码与移位密码、代替密码与移位密码 3 3、变换密码、变换密码 4 4、乘积密码、乘积密码 5 5、密码机的发展历史、密码机的发展历史31. 密码体制的定义密码体制的定义一个密码体制密码体制是一个六元组：（M, C, K1, K2, E, D )其中，M -明文空间C -密文空间K1 -加密密钥空间K2 -解密密钥空间E -加密变换空间D -解密变换空间4密码体制的理解密码体制的理解明文（明文（) )乃信息的原始形式，一般是信息的基本单元（字母、数字或符号等）的有限排列；密文（密文（)

2、)乃明文经过加密以后的结果形式，一般没有明确意义；密钥（密钥（) )乃用于加解密变换的关键信息，视其用于加解密而分别称为加密密钥与解密密钥；5密码体制的理解密码体制的理解一个加密变换加密变换乃一个下列形式的一一映射：E: MK1 C 一般对于给定的kK1,把E(-,k)记为Ek; 一个解密变换解密变换乃对应一个加密变换E而言，其实是一个以下形式的映射：D: CK2 M 并且适合（对于给定的kK2,也把D(-,k)记为Dk）：6密码体制的理解密码体制的理解：对任一kK1,都能找到k”K2,使得Dk”(Ek(m)=m，mM。7一般性说明一般性说明u我们常将26个英文字母(不区分大小写) 与整数02

3、5依次一一对应。u记 Zq=0,1,2, ,q-1称之为模q剩余类环；当q为素数时，该环进一步形成为域，可改写为Fq 。8一般性说明一般性说明u一般说来，一个密码体制的任一密钥控制下的加密变换都要求把明文按n（最少必要的固定数）个信息单元进行分组。照理，一个密码体制的明文空间M应该是所有可能明文的集合，但人们却习惯于把它写成前述所有n个信息单元组的集合；如此，密文空间C以及加解密变换的定义也有相应的变通。9简单密码举例 密码学的历史已有4000多年 古埃及人曾把象形文字写在石碑上10简单密码举例简单密码举例例例1. 凯撒（Caesar)密码凯撒密码是古罗马人Julius Caesar发明的一种

4、密码体制，它是使用最早的密码体制之一。凯撒密码用于对英文信息进行加密，它依据下列代替表（由英文字母表左环移3位得到）对信息中26个英文字母进行替换：明文字母a b c d e f g h i j k l m n o p q r s t u v w x y z 密文字母D E F G H I J K L M N O P Q R S T U V W X Y Z A B C11简单密码举例简单密码举例若明文为：Substitution cryptosystem 则相应的密文是： VXEVWLWXWLRQ FUBSWRVBVWHP在上述凯撒密码体制中，英文字母代替表即相当于密钥；若将英文字母表左环移k

5、(0k1）称该密码为分组（块）密码。25密码体制的分类密码体制的分类：加解密速度快，无错误扩散；一般用于实际的安全产品。：适合数据库加密，组内有错误扩散；一般用于公开的理论研究。26密码体制的分类密码体制的分类v依据密钥分类依据密钥分类单钥密码单钥密码( (传统密码，对称钥密码）传统密码，对称钥密码）双钥密码双钥密码( (公钥密码公钥密码, ,非对称钥密码非对称钥密码) )基于计算复杂性，人们可以设计出这样的密码体制：加密变换与相应的解密变换分别使用不同的密钥k与k”，并且kk”在计算上不可行（尽管理论上应该能够）。如此，用户选择该体制的一对加解密密钥(k,k”)后，可以将前者公开而后者私存。

6、区别于传统上加解密密钥一致或相近而必须都保密的观念,称之为非对称(公开)钥密码体制。27密码体制的分类密码体制的分类一般说来，单钥密码体制（包括分组、序列密码）都是基于计算安全性的，而双钥密码体制是基于可证明安全性的。这两种安全性都是从计算量来考虑，但不尽相同。计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知数学难题的计算量。28密码体制的分类密码体制的分类单钥密码优点：运行速度快，具有可靠的保密强度； 不足：不便密钥交换和管理。双钥密码优点：便于密钥交换和管理，还可用于消息认证（数字签名）； 不足：运行速度缓慢，其安全性所 依赖的数学难题的复杂

7、性一般都未能证明。29早期密码体制大都比较简单，其中许多经不起计算机的破译攻击。这些体制一般都是直接针对原始的信息单元（字母或符号等）设计，而并不象现代密码体制那样非常重视和体现信息的数字化与数学处理。 但对早期密码体制的讨论可以说明构造和破译的基本原理和方法，对于理解、构造和分析现代复杂的实用密码体制有着起码的利益。2. 代替密码代替密码30早期密码体制基本上可以按照下述分类笼统起来：n代替密码n移位密码以下我们便按照这样的分类来依次学习早期的密码体制及其破译。2. 代替密码代替密码312. 代替密码代替密码一个代替密码，若其任何密文可以看成是对相应明文的各组信息单元使用同一个代替表进行替换

8、而得到，则称其为单表代替密单表代替密码码； 否则，即有密文是依次对相应明文的各组信息单元使用有限个周期性重复的或无限多的固定代替表进行替换而得到，称其为多多表代替密码。表代替密码。32单表代替密码 每个字母可以用其它任何一个字母替换（不能重复） 每个字母可以随机的映射到其它一个 因此密钥长度是26个字母 单字母替换密码（ Monoalphabetic Substitution Cipher ） 例如： 明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS

9、 Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA33单表代替密码举例给定密钥字 “STARWARS”，去掉重复字母得到 “STARW”，填写剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列读取字母得到密文： Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY 可以用这个密钥加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INO

10、CHIT 34单表代替密码 需要一种简单方法指定密钥。 有多种方法，一种简单方法是写没有重复字母的“密钥字密钥字”，其它字母按顺序写在密钥字最后字母后面。 例如， 给定密钥字 JULIUSCAESAR Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: JULISCASRTVWXYZBDFGHKMNOPQ 35单表代替密码的密码分析 根据频率统计进行分析，确定每个字母被映射到什么字母，单个字母出现的可能是A或I（since know single words are A or I ） 一般来说个字母出现的可能是THE或AND，还可以用其他通常出现的双字母或三字母

11、组合。 还可以应用其它很少应用的字母36单表代替密码构造方法单表代替密码构造方法u举例例例1.1. 一个英文单表代替密码例例2.2. 方格密码例例3.3. 普莱费尔(Playfair)密码u构造方法构造单表代替密码的关键是构造一张明密代替表(可能以对应Z26的观点写成一个数学公式)。 以后不加声明，总假定M=C =a,b, c,z(记为A ), Z26, 或它们的n-直积。37单表代替密码构造方法单表代替密码构造方法密钥字法该法形成明密代替表如下：首先依次列出密钥字中字母(去掉其中的重复)，然后依次列出字母表中其余的字母。特点：便于由记忆的密钥字构造出明密代替表；但密钥空间K由所有可能的密钥字

12、构成，其实密钥量|K|比较小。38洗牌法该法就是将写有每个英文字母的26张纸牌打乱次序后重新排列形成明密代替表。如例1。特点：密钥空间K由26个英文字母的所有可能的全排列构成（|K|=26！），密钥的保密性较好，但不便于记忆。单表代替密码构造方法单表代替密码构造方法39仿射法该法的加密变换Ek为：Ek(m)=k1m+k2 (mod 26), mZ26其中，k=(k1,k2)为密钥；为使上述加密变换是一一的（从而才有相应的解密变换），必要且只要(k1, 26)=1。特点：便于用计算机实现，但密钥空间K =(k1,k2) | k1,k2Z26, (k1, 26)=1，密钥量|K|=1226-1=3

13、11较小。单表代替密码构造方法单表代替密码构造方法40多项式法该法的加密变换Ek为(t为取定自然数)：Ek(m)=ktmt+ kt-1mt-1+ k1m+k0 (mod 26), mZ26其中，k=(kt,kt-1, ,k1,k0)为密钥。仿射法其实是上述多项式法当t=1时的特例。有关多项式法的加密变换Ek何时是一一的以及对密钥空间K 的讨论已超出本课程的知识范围，在此不去涉及。单表代替密码构造方法单表代替密码构造方法41矩阵法该法的思想是：将明文组m=(m1m2mn)通过Z26上可逆的线性变换转换为密文组c=(c1c2cn) 。如此，密钥空间K =(kij)| (kij)为Z26上n阶可逆方

14、阵(有关讨论超出本课程的知识范围)；对于k= (kij)K ，加密变换Ek为：Ek(m1m2mn)=(c1c2cn), miZ26其中，ci=ki1m1+ki2m2+kinmn (mod 26)。单表代替密码构造方法单表代替密码构造方法42（2）多表代替密码）多表代替密码多表代替密码是依次对明文的各组信息单元使用有限个周期性重复的或无限多的固定代替表进行替换来得到密文的：若是使用无限多的固定代替表（相对于明文变化是随机的），则称其为一次一密代一次一密代替密码替密码；若是使用有限个周期性重复的固定代替表，则称其为周期多表代替密码周期多表代替密码。43（2 2）多表代替密码）多表代替密码一次一密密

15、码是在理论上唯一不可破解的密码，这种密码对于明文的特点可实现完全隐藏，但由于需要的密钥量与明文所含信息单元的个数一样大，故其难以实用。周期多表代替密码的实际情形如下：在给定的密钥(d个代替表排列T1T2Td)之下，加密明文m= m1m2m3的结果是c=T1(m1)Td(md) T1(md+1)Td(m2d) d称为该周期多表代替密码的周期。44周期多表代替密码周期多表代替密码u 举例例例1.1.四表代替密码。例例2.2.维吉尼亚(Vigenere)密码。45 Blaise de Vigenre 发明了多字母替换密码（polyalphabetic substitution cipher） 使用多

16、个单字母替换表 因此一个字母可以被多个字母替换。 方法：用一个密钥选择对每个字母使用哪个字母表，密钥的第I个字母表示使用第 ith 个字母表，依次使用每个字母表，当密钥的字母使用完后，在从头开始。Vigenre Cipher46 例： 写出明文，在明文下重复写出密钥字； 依次使用每个字母作为caesar cipher 的密钥，加密对应的明文字母。 Plaintext THISPROCESSCANALSOBEEXPRESSED Keyword CIPHERCIPHERCIPHERCIPHERCIPHE Plaintext VPXZTIQKTZWTCVPSWFDMTETIGAHLH Vigenre

17、 Example47 C - CDEFGHIJKLMNOPQRSTUVWXYZAB C - CDEFGHIJKLMNOPQRSTUVWXYZAB I - IJKLMNOPQRSTUVWXYZABCDEFGH I - IJKLMNOPQRSTUVWXYZABCDEFGH P - PQRSTUVWXYZABCDEFGHIJKLMNO P - PQRSTUVWXYZABCDEFGHIJKLMNO H - HIJKLMNOPQRSTUVWXYZABCDEFG H - HIJKLMNOPQRSTUVWXYZABCDEFG E - EFGHIJKLMNOPQRSTUVWXYZABCD E - EFGHIJ

18、KLMNOPQRSTUVWXYZABCD R - RSTUVWXYZABCDEFGHIJKLMNOPQ R - RSTUVWXYZABCDEFGHIJKLMNOPQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ to map the above plaintext letters. to map the above plaintext letters. T uses key C maps to V H uses key I maps to P I ises key P maps to X。Vigenre Example48 可以看出

19、，越安全的密码使用起来越复杂，因此，在有些场合还可以看到单码替换密码，随着破译单码密码的技术提高，使得vigenre cipher 逐渐被各国使用，1854年，首次被 Charles Babbage 攻破，但没有公开。 Friedrich Kasiski 与1863年攻破并发表了此密码的各种变形被沿用到20世纪。History of the Vigenre Cipher49周期多表代替密码例例3.3.博福特(Beaufort)密码。例例4.4.弗纳姆(Vernam)密码该密码是美国电报电话公司的G.W.Vernam在 1917年发明的。他将英文字母编成五位二元波多电码(Baudot code)

20、，参见P.47表3.2.9。选择随机的二元密钥序列k= k1k2ki，对字母变换成二元码后的明文m= m1m2mi加密以后得到c= c1c2ci，其中ci= mi ki，i=1,2,50周期多表代替密码周期多表代替密码思考：怎样理解上述弗纳姆密码是周期多表代替密码？其实，弗纳姆密码可以看成周期d=明文长(明文所含字母数目)的多表代替密码。一般地,我们称周期d=明文所含信息单元组数目的多表代替密码为滚动密钥滚动密钥(Running-(Running-key)key)密码密码。51周期多表代替密码周期多表代替密码对于一个滚动密钥密码,其密钥序列(即依次决定d个代替表的系列对应要素，如弗纳姆密码所用

21、的二元密钥序列)若能真正随机产生，则该种代替密码便相当于一次一密的了；一般密钥序列要由一给定主密钥作为初态的某密钥源伪随机地产生。52周期多表代替密码周期多表代替密码u构造方法照理，周期为d的多表代替密码的密钥空间应为K =T1T2Td|Ti为代替表,i=1,2,d,但在实际应用之中的密钥变化量往往较小：人们首先构造出dd个代替表T1,T2, Td，然后以T1,T2,Td取出d个的排列为密钥空间。如例1、2、3。上述在T1,T2,Td中取出d个排列起来的过程一般是借助决定d个代替表的系列对应要素进行，因此称之为构造密钥序列。53周期多表代替密码周期多表代替密码显然，周期多表代替密码的构造可以归

22、结为： 多个代替表（称为底表）的构造 密钥序列的构造一个周期多表代替密码的密钥其实是上述密钥序列，底表预先定义，而在加密中每次应用哪一底表完全由该密钥序列来控制。54周期多表代替密码周期多表代替密码 底表的构造一个底表一般为二维表，并且要求每个密文单元所在的行或列中出现一次且只出现一次，即该二维表应构成一个拉丁方阵。有关拉丁方阵的研究和构造可参见一些组合学书籍或刊物。55周期多表代替密码周期多表代替密码要求底表为一个拉丁方阵是必要的：因一般来说，底表的行、列分别对应明文和密钥：若横行有重码，则加密变换便不是一一的；若纵列有重码，则即使密钥序列是随机选取的，但明码中的不平衡性，也会造成密码的不平

23、衡，从而使破译者仅从密码的统计分析即可获得明文的部分信息，这不利于保密。当然，若周期较大，则对保密性而言，底表的作用不大，其完全取决于密钥序列。56周期多表代替密码周期多表代替密码 密钥序列的构造人们当然希望所产生的密钥序列具有尽可能好的随机性。一般可有下述三种构造方法：主观密钥源该种密钥源是以一本书或一个文件的选择内容作为密钥序列k1k2kd。评价评价：由于书本或文件中各信息单元出现的频率差异很大，故该种密钥源的保密性能不佳。57周期多表代替密码周期多表代替密码随机密钥源该种密钥源是以某种随机的方式产生密钥序列k1k2kd。例如，对维吉尼亚密码或博福特密码，使用者可将分别刻有26个英文字母的

24、26个小球放在坛子里，然后用有放回地随机拣球方法产生密钥序列。评价评价：该种密钥源的保密性能最佳，但当d较大时一则难以实现，另则必须将此产生的较长密钥序列完全传送给接收方、或要由接收方妥善保管、等等，实有诸多不便。58周期多表代替密码周期多表代替密码伪随机密钥源该种密钥源是根据现代的编码方法，利用计算机硬件或软件实时地产生密钥序列k1k2kd。评价评价：该种密钥源往往以一给定的主密钥作为初态，产生一个自身呈周期性的密钥序列。但设计者可根据实际保密强度的要求，预期密钥序列的周期远远大于一般所加密明文的长度，而且还具有良好的随机性；此时可以认为伪随机密钥源在保密性能上已近似于随机密钥源了。59周期

25、多表代替密码周期多表代替密码一个值得重视的问题是：密钥序列自身的保密性能固然重要，但若是应用不当，再好的密钥序列也可能无济于整个体制的安全。比如，密钥序列重用(这一现象称为重乱）就会给相应的周期多表代替密码体制带来危害，有关的具体情形以后会讲到。60多表代替密码的特点多表代替密码的特点q 单表代替密码的特点单表代替密码的特点：具有明密异同规律，一般容易破译。q 周期多表代替密码的特点周期多表代替密码的特点： 在一定程度上打破了明密异同规律 当周期d较小时，可确定之，并通过对密文重排，使其破译问题转化为对单表代替密码的破译 对周期d较大且密钥序列是伪随机的，可达到实际保密 对周期d较大且密钥序列

26、是随机的,可达到理论保密q 一次一密代替密码的特点一次一密代替密码的特点：无规律可循613. 变换密码 transposition ciphers 变换密码（或置换密码） 方法：通过重新编排消息字母隐藏信息 特点：没有改变原来消息的字母集62（1）Scytale 密码 一种早期的 希腊变换密码 一张纸条环绕在一个圆柱上 消息沿着圆柱横写 纸条上的字母看起来是一些随机字母 并不十分安全，密钥是纸条和圆柱的宽度63 以不同的行写下消息字母 按行读取消息 Plain: I A E S W C N U R D C M I A I O Q E E Cipher: IAESW CNURD CMIAI OQ

27、EE （2）轨道栏杆密码 Rail Fence cipher64 以一种形式写下消息，以另一种形式读取消息 （3）几何图形密码65 变换密码的关键思想 按一定规则写出明文，按另一规则读出密文。 密钥：用于读密文的方法和写明文的方法变换密码的关键思想66（4）行变换密码-Row transposition ciphersgroup the message and shuffle letters within each group more formally write letters across rows then reorder the columns before reading off

28、the rows always have an equivalent pair of keys (Read off vs Write In) 67Plain: THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey (R): 2 5 4 1 3 Key (W): 4 1 5 3 2 T H E S I S T I E H M P L E S E M S L P T P O S S S T S O P I B L E T E I T L B R A N S P S R P N A O S I T I T O I I S O N S X X X O X S N Cipher:

29、 STIEH EMSLP STSOP EITLB SRPNA TOIIS XOXSN 行变换密码68 可以用一个英文单词做密钥，指定以字母顺序做为读取密文（或明文）Plain: CONVENIENTWAYTOEXPRESSTHEPERMUTATION Key (W): C O M P U T E R Key (W): 1 4 3 5 8 7 2 6 A N O V I N C EE W T A O T N Y E R P E T S X SH E P R T U E M A O I N Z Z T Z Cipher: ANOVI NCEEW TAOTN YERPE TSXSH EPRTU EM

30、AOI NZZTZ 行变换密码69 用密钥 sorcery 加密下列消息: Key(R): sorcery = 6 3 4 1 2 5 7 laser beams can be modulated to carry more intelligence than radio waves = erasb lecam snabd umole atoed ctamo ryrre elntl iicee ntgha dnria oesav w 行变换密码举例70 步骤: 按列写出消息 按解密密钥读取明文 行变换密码解密算法71 频率分析能够提供语言轮廓 基本思想:猜测密钥周期,再对可能的行列变换进行猜测

31、. 利用常出现的双字母对或3字母对.Cryptanalysis of Row Transposition ciphers72密码分析举例 给定密文: LDWOE HETTS HESTR HUTEL OSBED EFIEV NT 对连续周期测试, 对前面一些字母重新排列. 2: LD WO EH ET TS HE ST RH UT EL OS BE DE FI EV NT - NO 3: LDW OEH ETT SHE STR HUT ELO SBE DEF IEV NT - NO 4: LDWO EHET TSHE STRH UTEL OSBE DEFI EVNT - NO 5: LDWOE

32、HETTS HESTR HUTEL OSBED EFIEV NT - NO 6: LDWOEH ETTSHE STRHUT ELOSBE DEFIEV NT - YES! note 第二组可能提供 THESET or TTHESE 可以猜测6字密钥能够给出这种密文 key 5,6,1,4,2,3 恢复明文如下: WEHOLD THESET RUTHST OBESEL FEVIDE NT or WE HOLD THESE TRUTHS TO BE SELF EVIDENT 73（5）块（Block ）变换密码 另一类变换密码 消息按行写，按列读出。 按列读出的顺序由密钥给出。74 为方便起见，把

33、消息写成满矩阵形式 Key(R): s o r c e r y s o r c e r y Key(R): 6 3 4 1 2 5 7 6 3 4 1 2 5 7 l a s e r b e l a s e r b e a m s c a n b a m s c a n b e m o d u l a e m o d u l a t e d t o c a t e d t o c a r r y m o r e r r y m o r e i n t e l l I i n t e l l i g e n c e t h g e n c e t h a n r a d i o a n r a

34、d i o w a v e s w a v e s q r matrix incompleteincomplete completecomplete 块变换密码举例75续 由密钥给出的顺序读出密文（4, 5, 2, 3, 6, 1, 7) ecdtm ecaer auool edsam merne nasso dytnr vbnlc rltiq laetr igawe baaei hor 76块变换密码解密 计算密文行数 (by dividing message length by key length) 按列写出密文消息（密钥给出顺序） 按行读出明文消息77块变换密码分析 首先要知道是否块变

35、换密码，通过消息长度猜测距阵大小，简单 测试每个密钥，按列写出消息 最一般的，利用自动工具实验所有置换，可以对一些可能单词组合形式的变换进行实验。78密码分析例子 给定密文: HADVF NITHB CTSBE HTEGE SRYRN AMINR IAIST TETOO ETSAN GLIET GTDRS CYGAI TANAH FLNAU ETIEM EOHUE AELYR IIS 假设对行变换失败现猜测是块变换寻找THE，实验各种大小的密钥 try 2, use command b 2 /THE - none match try 3, use command b 3 /THE - none

36、 match try 4, use command b 4 /THE - 2 matches, both rubbish try 5, use command b 5 /THE - 1st match gives answer - b 5 /THE THEGR EATES TDISC OVERY OFMYG ENERA TIONI STHAT AHUMA NBEIN GCANA LTERH ISLIF EBYAL TERIN GHISA TTITU DES Accept (y/n/q)?y79Nihilist ciphers 更复杂的变换密码（行变换和列变换同时应用）80 仅仅基于替换或置换的

37、密码是不安全的 前面的得例子可以看到这一点 这是由于他们不能克服语言结构的特点 因此考虑连续使用几种密码克服, 注: 两个替换密码只能提高很少的复杂度 两个置换也只能提高很少的复杂度 但替换与置换连用，可以提高较高的复杂密码增加密码的安全性814. 乘积密码 是一种替换与变换合用的密码，一般情况下，手工破译是非常困难的。 一种有名的乘积密码“ADFGVX cipher” 在第一次世界大战中使用。82ADFGVX 乘积密码 这样命名是因为变换仅依赖与 ADFGVX，在WW1有德国人使用，并被英国人破译。 方法：使用一个固定的替换表，把每个明文字母映射成一个字母对 (row-col index)，在用一个带密钥的块变换把每个对分解then 利用带密钥的块变换写下所有字母对，写出密文（按块密码形式）。83ADFGVX Substitution