第2章传统密码技术1_1

1、l第第1 1章章 密码学概述密码学概述l第第2 2章章 传统密码技术传统密码技术l第第3 3章章 分组密码分组密码l第第4 4章章 公钥密码体制公钥密码体制 l第第5 5章章 散列函数与消息鉴别散列函数与消息鉴别 l第第6 6章章 数字签名技术数字签名技术 l第第7 7章章 密钥管理技术密钥管理技术l第第8 8章章 身份鉴别技术身份鉴别技术 l第第9 9章章 序列密码序列密码 l第第1010章章 密码技术应用密码技术应用l附录附录 课程主要内容课程主要内容2第第2 2章章 传统密码技术传统密码技术 本章主要内容本章主要内容 替代密码替代密码: :利用预先设计的替代规则利用预先设计的替代规则,

2、,对明文逐字符或对明文逐字符或逐字符组进行替代的密码逐字符组进行替代的密码. . 分为单表替代和多表替代分为单表替代和多表替代两种两种 置换密码置换密码: :对各字符或字符组进行位置移动的密码对各字符或字符组进行位置移动的密码. . 转轮机密码转轮机密码 ：利用转轮机进行加解密操作利用转轮机进行加解密操作3第第2 2章章 传统密码技术传统密码技术2.1.1 2.1.1 替代密码替代密码 单表替代密码单表替代密码l 一般单表替代密码l 移位密码l 仿射密码多表替代密码多表替代密码l 弗吉尼亚密码4第第2 2章章 传统密码技术传统密码技术2.1.1 2.1.1 单表替代密码单表替代密码 单表替代密

3、码：明文字母表到密文字母表的固定映射单表替代密码：明文字母表到密文字母表的固定映射 f：AB， f ( ai ) bj Aa0, a1, an-1为包含了为包含了n n个字母的明文字母表；个字母的明文字母表； Bb0, b1, bn-1 为包含为包含n n个字母的密文字母表个字母的密文字母表 一般一般: :f 是一一映射，以保证加密的可逆性。是一一映射，以保证加密的可逆性。5第第2 2章章 传统密码技术传统密码技术 一般单表替代密码一般单表替代密码 明文空间明文空间M M 和密文空间和密文空间C C 都是都是2626个英文字母的集合，密钥空间个英文字母的集合，密钥空间K=：Z26Z26|是置换

4、是置换，是所有可能置换的集合。，是所有可能置换的集合。 对任意对任意K K，定义，定义: : 加密变换：加密变换：e( (m)=)=( (m)=)=c 解密变换：解密变换：d(c) = -1(c)=m， -1是是的逆置换。的逆置换。 【例例2.12.1】设置换设置换的对应关系如下：的对应关系如下： 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 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 q w e r t y u i o p a s d f g h j k l z x c v

5、b n m q w e r t y u i o p a s d f g h j k l z x c v b n m 试用单表替代密码以试用单表替代密码以为密钥对明文消息为密钥对明文消息messagemessage加密，然后写出逆置换加密，然后写出逆置换 ，并对密文解密。并对密文解密。 解：以解：以为密钥用单表替代密码对明文消息为密钥用单表替代密码对明文消息messagemessage加密，所得加密，所得 密文消息为：密文消息为： (m) (e) (s) (s) (a) (g) (e)=dtllqut 2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）6第第2 2章章 传统密码技术传统

6、密码技术 一般单表替代密码算法特点：一般单表替代密码算法特点： 密钥空间密钥空间K很大，很大，|K|=26!=41026 ，破译者穷举搜索计算不可行，破译者穷举搜索计算不可行，1微秒试微秒试一个密钥，遍历全部密钥需要一个密钥，遍历全部密钥需要1013 年。年。 移位密码体制是替换密码体制的一个特例，它仅含移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。个置换做为密钥空间。 密钥密钥不便记忆。不便记忆。 针对一般替换密码密钥针对一般替换密码密钥不便记忆的问题，又衍生出了各种形式单表替代密不便记忆的问题，又衍生出了各种形式单表替代密码。码。移位密码移位密码 把把26个英文字母与

7、整数个英文字母与整数0，1，2，25一一对应，如表一一对应，如表2.1所示。所示。 2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）表表2.1 字母数字映射表字母数字映射表7第第2 2章章 传统密码技术传统密码技术加密变换，加密变换，E=E:Z26Z26, Ek (m) = m + k (mod26)| mM, kK 解密变换，解密变换，D=D:Z26Z26, Dk (c) = ck (mod26)| cC, kK 解密后再把解密后再把Z26中的元素转换成英文字母。中的元素转换成英文字母。 显然，移位密码是前面一般单表替代密码的一个特例。当移位显然，移位密码是前面一般单表替代密码的

8、一个特例。当移位密码的密码的 密钥密钥k=3时，就是历史上著名的凯撒密码（时，就是历史上著名的凯撒密码（Caesar）。）。根据其加密函数特根据其加密函数特 点，移位密码也称为加法密码。点，移位密码也称为加法密码。2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）8 恺撒密码恺撒密码这是一种对这是一种对英文字母英文字母的典型逐字母加密的的加法密码的典型逐字母加密的的加法密码,其密钥其密钥k=3。 英文字母被编码为该字母的序号英文字母被编码为该字母的序号 英文 A B C D X Y Z 数字 0 1 2 3 23 24 25 破译以下密文：破译以下密文： 密文：密文：PHHW PH

9、DIWHO WKH SDUWBPHHW PH DIWHO WKH SDUWB 明文：明文：meet me after the partymeet me after the party第第2 2章章 传统密码技术传统密码技术2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）返回250,26mod)3()(3mmmEc加密变换为加密变换为：解密变换为解密变换为：250,26mod)3()(3cccDm9第第2 2章章 传统密码技术传统密码技术2.1.1 2.1.1 单表替代密码（续）单表替代密码（续） 是替换密码的一个特例是替换密码的一个特例 加密函数的形式为：加密函数的形式为： K=(

10、k1，k2)| k1，k2Z26，gcd(k1，26)=1 对任意对任意mM，cC，k = (k1，k2)K， 加密变换为：加密变换为： c = Ek (m) = k1 m +k2 (mod 26) 解密变换为：解密变换为： m = Dk (c) = k11 (ck2) (mod 26)仿射密码仿射密码10第第2 2章章 传统密码技术传统密码技术【例例2.32.3】设明文消息为设明文消息为chinachina，密钥，密钥 试用仿射密码对其进行试用仿射密码对其进行 加密，然后再进行解密。加密，然后再进行解密。 解：利用扩展的欧几里德算法（参见附录解：利用扩展的欧几里德算法（参见附录A.1.2A.

11、1.2）可计算出）可计算出 加密变换为：加密变换为： 解密变换为：解密变换为： 明文明文消息对应的数字依次为消息对应的数字依次为2，7，8，13，0，用仿射密码对明文进行加密，用仿射密码对明文进行加密 如下：如下： 22207213()98222 mod 2613215022kunEmwcpc113k1,2()(9,2)kk k2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）12( )(mod26)92(mod26)kmmmkkE 112( )()(mod26)3 (2)(mod26)(36)(mod26)kcccckkD字母数字映射表字母数字映射表11第第2 2章章 传统密码技术

12、传统密码技术 密文消息为密文消息为unwpcunwpc。而解密过程如下：。而解密过程如下： 即恢复明文消息为即恢复明文消息为chinachina。 仿射密码要求仿射密码要求gcd(k1, 26)=1 ，否则就会有多个明文字母对应，否则就会有多个明文字母对应一个密文字母的情况。由于与一个密文字母的情况。由于与26互素的整数有互素的整数有12个，故仿射密码密钥空间大个，故仿射密码密钥空间大小为小为|K|=1226=312。 若将仿射密码的加密函数换为多项式函数时，即为多项式密码若将仿射密码的加密函数换为多项式函数时，即为多项式密码。l 密钥短语密码密钥短语密码 选用一个英文选用一个英文短语或单词串

13、作为密钥，去掉其中重复的字母得到一个无短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构造出一个字母替代表。如密钥为可构造出一个字母替代表。如密钥为key时，替代表如表时，替代表如表2.2所示。所示。 20621367()32268mod 2615613260kchDmina2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）12第第2 2章章 传统密码技术传统密码技术 表表2.2 2.2 密钥为密钥为keykey的单表替代密码的单表替代密码 当选择上

14、面的密钥当选择上面的密钥进行加密时，若明文为进行加密时，若明文为“china”，则密文为，则密文为“yfgmk”。 显然，不同的密钥可以得到不同的替换表显然，不同的密钥可以得到不同的替换表。2.1.2 2.1.2 多表替代密码多表替代密码 单表替代密码表现出明文中单字母出现的频率分布与密文中相同，单表替代密码表现出明文中单字母出现的频率分布与密文中相同， 多表替代密码使用从明文字母到密文字母的多表替代密码使用从明文字母到密文字母的多个映射多个映射来隐藏单字母来隐藏单字母出现的频率分布，出现的频率分布，每个映射是简单替代密码中的一对一映射每个映射是简单替代密码中的一对一映射, ,多表替多表替代密

15、码将明文字母划分为长度相同的消息单元，称为明文代密码将明文字母划分为长度相同的消息单元，称为明文分组分组，对，对明文成组地进行替代，同明文成组地进行替代，同一个字母有不同的密文一个字母有不同的密文，改变了单表替代，改变了单表替代密码中密文的唯一性，使密码分析更加困难。密码中密文的唯一性，使密码分析更加困难。 13第第2 2章章 传统密码技术传统密码技术 多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉尼亚密码和尼亚密码和HillHill密码等均是多表替代密码。密码等均是多表替代密码。1.1.维吉尼亚密码维吉尼亚密码 该密码

16、体制有一个参数该密码体制有一个参数n n，按按n n个字母一组进行变换。也是把英文字母个字母一组进行变换。也是把英文字母映射为映射为0 02525的数字再进行运算，明文空间、密文空间及密钥空间都是长度的数字再进行运算，明文空间、密文空间及密钥空间都是长度为为n n的英文字母串的集合，因此可表示的英文字母串的集合，因此可表示 加密变换定义如下：加密变换定义如下： 设密钥设密钥 k=(k1,k2,kn), , 明文明文m=(m1,m2,mn), , 加密变换为加密变换为： 其中其中ci=(mi + ki)(mod26)，i =1,2,n Ek(m)=(c1,c2,cn), , 对密文对密文 c=(

17、c1,c2,cn), , 解密变换为：解密变换为： Dk(c)=(m1,m2,mn), , 其中其中 mi=(ci ki)(mod26)，i =1,2,n2 6nPCKZ2.1.2 多表替代密码多表替代密码（续）（续） 14第第2 2章章 传统密码技术传统密码技术【例例2.42.4】设密钥设密钥k k =cipher=cipher，明文消息，明文消息appliedcryptosystemappliedcryptosystem， 试用维吉尼亚密码对其进行加密，然后再进行解密。试用维吉尼亚密码对其进行加密，然后再进行解密。解：由密钥解：由密钥k k=cipher=cipher，得，得n=6n=6，

18、密钥对应的数字序列为，密钥对应的数字序列为 (2(2，8 8，1515，7 7，4 4，17)17)。然后将明文按每。然后将明文按每6 6个字母进行分组，并转换这个字母进行分组，并转换这些明文字母为相应的数字，再用模些明文字母为相应的数字，再用模2626加上对应密钥数字，其加加上对应密钥数字，其加密过程如表密过程如表2.32.3所示。所示。 表表2.3 2.3 密钥为密钥为ciphercipher的维吉尼亚密码加密过程的维吉尼亚密码加密过程 密文为：密文为：cxtsmvfkgftkqanzxvocxtsmvfkgftkqanzxvo。 解密使用相同的密钥，但用模解密使用相同的密钥，但用模262

19、6的减法代替模的减法代替模2626加法，这里加法，这里不再赘述。不再赘述。2.1.2 多表替代密码多表替代密码（续）（续） 15第第2 2章章 传统密码技术传统密码技术 1. 单表替代的优缺点单表替代的优缺点 优点优点: 明文字符的形态一般将面目全非明文字符的形态一般将面目全非 缺点缺点: (A) 明文的位置不变明文的位置不变; (B) 明文字符明文字符相同相同,则则密文字符密文字符也相同也相同; 从而导致从而导致: (I) 若明文字符e被加密成密文字符a,则明文中e的出现次数就 是密文中字符a的出现次数; (II) 明文的跟随关系反映在密文之中. 因此因此,明文字符的统计规律就完全暴露在密文

20、字符的统计规明文字符的统计规律就完全暴露在密文字符的统计规律之中律之中.形态变但位置不变形态变但位置不变替代密码替代密码的安全性分析的安全性分析 16第第2 2章章 传统密码技术传统密码技术 2. 多表替代的优缺点多表替代的优缺点 优点优点: 只要只要 (1) 多表设计合理多表设计合理,即每行中元互不相同即每行中元互不相同,每列中元互不相同每列中元互不相同.(这这样的表称为拉丁方表样的表称为拉丁方表) (2) 密钥序列是随机序列密钥序列是随机序列，即具有等概性和独立性。这个多表，即具有等概性和独立性。这个多表代替就是完全保密的。代替就是完全保密的。 等概性等概性:每个位置的字符取可能字符的概率

21、相同；每个位置的字符取可能字符的概率相同； 独立性：独立性：在其它所有字符都知道时，也判断不出未知的字符在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。取哪个的概率更大。替代密码替代密码的安全性分析的安全性分析 17第第2 2章章 传统密码技术传统密码技术 2. 多表替代的缺点多表替代的缺点密钥序列是随机序列意味着：密钥序列是随机序列意味着： （1）密钥序列不能周期重复；）密钥序列不能周期重复； （2）密钥序列必须与明文序列等长；）密钥序列必须与明文序列等长； （3）这些序列必须在通信前分配完毕；）这些序列必须在通信前分配完毕； （4）大量通信时不实用；）大量通信时不实用； （5

22、）分配密钥和存储密钥时安全隐患大。）分配密钥和存储密钥时安全隐患大。 替代密码替代密码的安全性分析的安全性分析 18第第2 2章章 传统密码技术传统密码技术 置换密码通过改变明文消息各元素的相对位置，但明文消置换密码通过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不变；息元素本身的取值或内容形式不变； 形态形态不不变但位置变变但位置变。 2.2 置换密码置换密码 ( Permutation/Transposition Cipher )( Permutation/Transposition Cipher )19第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置

23、换密码 最简单的例子是栅栏技术：最简单的例子是栅栏技术： 明文明文：meet me after the partymeet me after the party 写为写为：m e m a t r h p r ym e m a t r h p r y e t e f e t e a t e t e f e t e a t 密文密文：mematrhpry etefeteatmematrhpry etefeteat20第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置换密码 例：设例：设m=6m=6，设置密钥置换，设置密钥置换P24P24： 加密的密钥置换加密的密钥置换 解密的密钥置

24、换解密的密钥置换 3 5 1 6 3 5 1 6 4 4 2 2 K = 3 6 1 5 2 4 3 6 1 5 2 4 K-1 =明文组中的第明文组中的第3 3个字符个字符置换到第置换到第1 1位位明文组中的第明文组中的第5 5个字符个字符置换到第置换到第2 2位位密文的第密文的第3 3个字符置换个字符置换到第到第1 1位，位，密文的第密文的第6 6个字符置换个字符置换到第到第2 2位，位，21 对明文对明文cryptographycryptography进行进行加密加密，首先将明文分成，首先将明文分成6 6个字母个字母长的明文组：长的明文组：crypto|graphycrypto|grap

25、hy； 然后将每个明文组按密钥置换然后将每个明文组按密钥置换K K重新排列：重新排列：加密的密加密的密钥置换钥置换 1 2 3 4 1 2 3 4 5 5 6 6 3 5 1 6 3 5 1 6 4 4 2 2 K = c r y p t oc r y p t o y t c o p r y t c o p r （crypto）K = g r a p h yg r a p h y a h g y p ra h g y p r（graphy）K = YTCOPR= AHGYPR第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置换密码22 对密文对密文YTCOPRAHGYPR进行进

26、行解密解密，首先将密文分成，首先将密文分成6 6个个字母长的明文组：字母长的明文组：YTCOPR|AHGYPRYTCOPR|AHGYPR； 然后将每个密文组按密钥置换然后将每个密文组按密钥置换K K-1-1重新排列：重新排列：解密的密解密的密钥置换钥置换 1 2 3 4 1 2 3 4 5 5 6 6 3 6 1 5 2 4 3 6 1 5 2 4 K-1 = y t c o p r y t c o p r c r y p t oc r y p t o（ YTCOPR）K-1 = a h g y p ra h g y p r g r a p h yg r a p h y（AHGYPR）K =

27、crypto=第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置换密码graphy23第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置换密码 列置换密码列置换密码- -加密加密 把明文一行一行的写出，然后按列读取，但把列把明文一行一行的写出，然后按列读取，但把列的次序打乱，列的次序就是密钥；的次序打乱，列的次序就是密钥； 密钥：密钥： 4 3 2 14 3 2 1 明文：明文： t h i st h i s b o y i b o y i s a w o s a w o r k e r r k e r 密文：密文：sior iywe hoak tbsrsior

28、 iywe hoak tbsr24第第2 2章章 传统密码技术传统密码技术2.2 2.2 置换密码置换密码 列置换密码列置换密码- -解密解密 把密文一列一列的写出，然后按行读取把密文一列一列的写出，然后按行读取 密钥：密钥： 4 3 2 14 3 2 1 密文：密文： s i h ts i h t i y o b = i y o b = o w a s o w a s r e k r r e k r 明文：明文：this boy is a workerthis boy is a workert h i st h i sb o y ib o y is a w os a w or k e rr

29、k e r25用编号表示内部引线的三转轮机用编号表示内部引线的三转轮机(a)(a)初始情况初始情况（b b）经过一次按键后的情况）经过一次按键后的情况第第2 2章章 传统密码技术传统密码技术2.3 2.3 转轮机转轮机26第第2 2章章 传统密码技术传统密码技术2.4 传统密码的统计分析传统密码的统计分析 在对密码进行安全分析时，一般假设密码分析者知道密码体在对密码进行安全分析时，一般假设密码分析者知道密码体制，这就是制，这就是KerckhoffsKerckhoffs假设，假设，密码分析重点在获取密钥。密码分析重点在获取密钥。 移位密码、仿射密码、维吉尼亚密码、置换密码等对己知明移位密码、仿射

30、密码、维吉尼亚密码、置换密码等对己知明文攻击都是非常脆弱的。即使用惟密文攻击，大多数古典密码文攻击都是非常脆弱的。即使用惟密文攻击，大多数古典密码体制都容易被攻破。体制都容易被攻破。大多数古典密码体制都不能很好隐藏明文大多数古典密码体制都不能很好隐藏明文消息的统汁特征。消息的统汁特征。 下面就针对单表替代密码、多表替代密码和下面就针对单表替代密码、多表替代密码和HillHill密码来介绍密码来介绍利用英文语言的统计特征和密码特点，运用惟密文攻击或已知利用英文语言的统计特征和密码特点，运用惟密文攻击或已知明文攻击等方式破译古典密码的基本方法。明文攻击等方式破译古典密码的基本方法。 27第第2 2

31、章章 传统密码技术传统密码技术2.4.1 2.4.1 单表替代密码分析单表替代密码分析 本质上，密文字母表是明文字母表的一种排列。本质上，密文字母表是明文字母表的一种排列。但企但企图使用计算机穷举一切密钥来破译密钥词组替代密码也图使用计算机穷举一切密钥来破译密钥词组替代密码也是计算不可行的。是计算不可行的。 穷举不是攻击密码的惟一方法，密码分析者便可利穷举不是攻击密码的惟一方法，密码分析者便可利用语言的统计特性进行分析。用语言的统计特性进行分析。如果明文语言的这种统计如果明文语言的这种统计特性在明文中有所反映，密码分析者便可通过分析明文特性在明文中有所反映，密码分析者便可通过分析明文和密文的统

32、计规律而破译密码。和密文的统计规律而破译密码。 通过对大量英文语言的研究可以发现，每个字母出现通过对大量英文语言的研究可以发现，每个字母出现的频率不一样，的频率不一样，e e出现的频率最高。如果所统计的文献足出现的频率最高。如果所统计的文献足够长，便可发现各字母出现的频率比较稳定。如表够长，便可发现各字母出现的频率比较稳定。如表2.42.4所所示（表中字母出现频率为字母出现次数除以文本字母总示（表中字母出现频率为字母出现次数除以文本字母总数）。数）。28第第2 2章章 传统密码技术传统密码技术 表表2.4 262.4 26个英文字母出现频率统计表个英文字母出现频率统计表 2.4.1 2.4.1

33、 单表替代密码分析（续）单表替代密码分析（续）字母字母出现频率出现频率字母字母出现频率出现频率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m0.0249z0.00082902468101214A B C D E F G HI J K L MNOP QR S T U V WX Y Z频率频率E使用最多；使用最多；然后是然后是T R N I O A S其他字母使用较少其他字母使用较少最少的是最少的是J K Q X Z英文中字母的使用频率英文中字母的使用频率 第第2 2章章 传统密码技术传统密码技术2.4.1 2.4.1 单表替代密码分析（续）单表替代密码分析（续）301 1 密文：密文： UZ