第12讲 古典密码的加密与破译 之数学原理.

Presentation on theme: "第12讲 古典密码的加密与破译 之数学原理."— Presentation transcript:

1 第12讲 古典密码的加密与破译 之数学原理

2 教学目标 1、了解古典密码的历史和发展 2、了解凯撒密码的数学原理 3、掌握模运算，理解模逆的概念 4、掌握Hill密码的数学原理，理解公钥、模逆矩阵的概念，会用Hill密码进行加密和破译 5、了解现代密码的数学原理，了解公开密钥的概念和作用。 2017/9/12 广东科学技术职业学院

3 密码和解密模型 问题 1.甲方收到与之秘密通信往来的乙方的一个密文信息，密 文内容为:
WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWW CVLEMIMCC 按照甲方与乙方的约定，他们之间的密文通信采用Hill2密 码，密钥为二阶矩阵 且汉语拼音(或英文字母)的 26个字母与0 ～25之间的整数建立一一对应关系，称之为 字母的表值，具体表值见下表，问这段密文的原文是什么？ A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 表1 2017/9/12 广东科学技术职业学院

4 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 经分析这段密文是用Hill2密码编译的，且其中的字母U
问题 2.甲方截获了一段密文 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 经分析这段密文是用Hill2密码编译的，且其中的字母U CRS依次代表字母TACO，问能否破译这段密文的内容？ 2017/9/12 广东科学技术职业学院

5 问题背景和实验目的 保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。
为了将信息传递给己方的接受者，同时又要防止他人（特别是敌人）知道信息的内容，必须将要传递的信息（明文）加密，变成密文后发送出去，这样，即使敌方得到密文也看不懂，而己方的接受者收到密文后却可以按照预先定好的方法加以解密。

6 问题背景和实验目的 密码可分为古典密码和现代密码
古典密码：以字符为基本加密单元； 现代密码：以信息块为基本加密单元。 本实验主要介绍古典密码的加密与破译原理，同时介绍如何用 Matlab 编程来实现加密、解密和破译过程。

7 加密信息传递过程 加密器 发送方 明文（信息） 密文 普通信道 发送 敌方截获 破译 解密器 明文（信息） 密文 接收方

8 密码的起源 密码学的历史大致可以推早到两千年前， 相传名将凯撒为了防止敌方截获情报， 用密码传送情报。
凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表 这种密码我们往往称之为代替密码或置换密码

9 这样，如果不知道密码本，即使截获一段信息也看不懂
比如收到一个的消息是 EBKTBP，那么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。 近年来一些谍报题材的电视剧中，比如用菜价(一组数字)传递信息，这些数字对应某本书的页码和字的次序。 金庸先生在他的《连城诀》中就使用了这种密码。

10 密码的发展与应用 对于这种密码的破译，只要多截获一些情报，统计一下字母的频率，就可以解破出这种密码。
柯蓝道尔在他的“福尔摩斯探案集”中“跳舞的小人”的故事里已经介绍了这种小技巧。

11 在第二次世界大战中，日本军方的密码设计就很成问题。美军破获了日本很多密码。
在中途岛海战前，美军截获的日军密电经常出现 AF 这样一个地名，应该是太平洋的某个岛屿，但是美军无从知道是哪个。 于是美军就逐个发表自己控制的每个岛屿上的假新闻。当美军发出“中途岛供水系统坏了”这条假新闻后，从截获的日军情报中又看到 AF 供水出来问题的电文，美军就断定中途岛就是 AF。 事实证明判断正确，美军在那里成功地伏击了日本主力舰队。

12 总的来说，日本在二战中情报经常被美国人破译，以致他们的海军名将山本五十六也因此丧命。我们常说落后就要挨打，其实不会使用数学也是要挨打的。
已故的美国情报专家雅德利二战曾在重庆帮助国民党破解日本的密码。雅德利在回国后写了本书《中国黑室》，从书中的历史可以了解到，日本和重庆间谍约定的密码本就是美国著名作家赛珍珠获得1938年诺贝尔奖的《大地》一书。密码所在的页数就是一个非常简单的公式：发报日期的月数加上天数再加上10.比如3月11号发报，密码就在 =24页。 总的来说，日本在二战中情报经常被美国人破译，以致他们的海军名将山本五十六也因此丧命。我们常说落后就要挨打，其实不会使用数学也是要挨打的。 2017/9/12 广东科学技术职业学院

13 好的密码必须做到不能根据已知的明文和密文的对应推断出新的密文的内容。从数学的角度上讲，加密过程可以看作是一个函数的运算F，解密的过程是反函数的运算。明码是自变量，密码是函数值。好的（加密）函数不应该通过几个自变量和函数值就能得到函数。 2017/9/12 广东科学技术职业学院

14 在很长时间里，人们试图找到一些好的编码方法使得解密者无法从密码中统计出明码的统计信息，但是基本上靠经验。
有经验的编码者会把常用的词对应成多个密码，使得破译者很难统计出任何规律。 比如如果将汉语中的“是”一词对应于唯一一个编码 0543，那么破译者就会发现 0543 出现的特别多。 但如果将它对应成十个密码 0543，3737，2947 等等，每次随机的挑一个使用，每个密码出现的次数就不会太多，而且破译者也无从知道这些密码其实对应一个字。

15 事实上在二战中，很多顶尖的科学家包括提出信息论的香农都在为美军情报部门工作， 而信息论实际上就是情报学的直接产物。
香农提出信息论后， 为密码学的发展带来了新气象。 根据信息论，密码的最高境界是使得敌人在截获密码后，对我方的所知没有任何增加，用信息论的专业术语讲，就是信息量没有增加。

16 一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀分布使得敌人无从统计，而统计独立能保证敌人即使看到一段密码和明码后，不能破译另一段密码。
这也是电视剧《暗算》 里传统的破译员老陈破译的一份密报后， 但无法推广的原因，而数学家黄依依预见到了这个结果，因为她知道敌人新的密码系统编出的密文是统计独立的。 有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括电视剧《暗算》里的“光复一号”密码，应该就是基于这个理论。

17 公开密钥体制的提出就是为了从根本上解决上述问题 。其基本思想是：把密钥划分为公开密钥和秘密密钥两部分 ,两者互为逆变换，但几乎不可能从公开密钥推出秘密密钥 .每个使用者均有自己的公开及秘密密钥。 虽然只要能解密的密文，从理论上讲都是可破译的，但如果破译所需要的工作量过大，要求花费的时间过长，以致超过了保密期限，则该密码系统应当被认为是安全可靠的。 就是靠这样的数学原理，保证了二战后的密码几乎无法被破解。冷战时期美苏双方都投入了前所未有的精力去获得对方的情报，但是没有发生过大的因为密码被破而泄密的事件。 2017/9/12 广东科学技术职业学院

18 Hill密码的数学原理 希尔(Hill)密码
前面提到过代替密码的一个致命弱点 是明文字符和密文字符有相同的使用频率,破译者可从统计出来的字符频率中找到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字符间的一一对应。 1929年，希尔利用线性代数中的矩阵运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。 2017/9/12 广东科学技术职业学院

19 Hill密码加密算法的思想是将l各明文字母通过线性变换转换为l个密文字母，解密只要做一次逆变换就可以了，密钥就是变换矩阵本身，即一般取n=26。
其中 或写成 其中 解密 2017/9/12 广东科学技术职业学院

20 模运算 设n是正整数，a是整数，如果用n去除a，得商为q，余数为r，则可以表示为： a=qn+r,0≤r<n,
用a mod n表示余数r，则r≡a mod n. 例如：令a=17, n=5,则17=3×5 +2, r =2≡17mod5 在MATLAB软件中，求余(模)运算命令式mod和rem，当x和y异号时，mod(x,y) 求余数，结果与 y 同号，rem(x,y) 求余数，则与 x 同号，当x,y同号时，两者结果是一样的

21 模运算典型实例 时钟模12的运算

22 同余 设n是正整数，a, b是整数，如果a mod n≡b mod n，则称整数a和b模n同余，记为a≡b mod n。
显然，a≡b mod n，则n|(a-b). 例如：a=17, b=-8, n=5, 因为17=3×5 +2, -8 =-2×5 +2, 则17 mod 5≡-8 mod 5，通常记为：17≡-8 mod 5.

23 同余式实例 Q: 下面哪个是真的? 3  3 (mod 17) 3  -3 (mod 17) 172  177 (mod 5)

24 同余式实例 A: 3  3 (mod 17) True. (3-3 = 0, divisible by all)
3  -3 (mod 17) False. (3-(-3)) = 6 不能整除 17. 172  177 (mod 5) True = -5 能整除 5 -13  13 (mod 26) True: = -26 能整除by 26.

25 同余的基本性质 ① [(a mod n)+(b mod n)]mod n=(a+b)mod n

26 同余的基本性质 例 1 mod 8=3; 15 mod 8=7 ① [(11mod 8)+(15 mod 8)]mod 8=(3+7)mod 8 =2 =(11+15) mod 8=26 mod 8=2 ② [(11 mod 8)×(15 mod 8)]mod 8 =(3×7)mod 8 =21 mod 8=5 (11×15）mod 8＝165 mod 8＝5

27 同余性质 1. 若ab(mod m), cd(mod m), 则:
① ax+cy  bx+dy(mod m), 其中x和y为任给整数. ② ac  bd(mod m). ③ an  bn(mod m), 其中 n＞0. 上面的性质容易证明，以②为例： 设a=b+q1m,c=d+q2m ac=( b+q1m)( d+q2m)=bd+(bq2+dq1+q1q2)m, 等式两边同时模m可证。

28 同余性质 2. 设m是一个正整数， ① ad≡bd(mod m), 如果(d, m)=1, 则a≡b(mod m)
② a≡b(mod m), k>0, 则ak≡bk(mod mk) ③ a≡b(mod m), 如果d是m的因子，则a≡ b(mod d) 下面对①③进行证明。

29 同余性质 ① 证明：若ad≡bd(mod m), 则m|(ad-bd), 即m|d(a-b). 因(d, m)=1，故m|(a-b), 即a=b(mod m) ③ 证明：d是m的因子，故存在m’, 使得m=dm’. 因为a≡b(mod m), 存在k, 使得a=b+mk= b+ dm’k. 等式两边模d, 可得a≡b(mod d).

30 同余的一个应用--最大公因数 设a, b是整数，则a, b的所有公因数中最大的一个公因数叫做最大公因数，通常记为gcd(a,b)。
思考：用何种算法求最大公约数？ 如果两个整数的绝对值都比较小，求它们的最大公因数是比较容易的。如果两个数都比较大，可以用欧几里德算法，也称辗转相除法。

31 一个关于同余的性质 对任何非负整数a和非负整数b，设a≥b, a=bq+r, 0≤r<|b|, 则gcd（a, b ）=gcd(b, r). 证明：设gcd（a, b）=d, 则d|a, d|b, 则d|a-bq即d|r. 同理，设gcd(b, r)=k, 则k|b, k|r, 则k|bq+r, 即k|a. 所以，结论成立。 例如，96=28×3+12，故gcd(96,28)=gcd(28,12)=4. 又如，88=11×8+0，故gcd(88,11)=gcd(11,0)=11.

32 辗转相除法 设 a, b＞0, 且都为整数，进行下列计算: a=bq1+r1, 0＜rl＜b b=r1q2+r2, 0＜r2＜r1
r1=r2q3+r3, ＜r3＜r2 ……. rn-2=rn-1qn+rn, 0＜rn＜rn-1 rn-1=rnqn+1+0 则a,b的最大公因数为rn. 因为gcd(a,b)= gcd(b,r1)= gcd(r1,r2)=… =gcd(rn-1, rn)=gcd(rn,0)= rn.

33 辗转相除法 举例 例 求gcd(184, 136)。 184=1×136+48, gcd(184,136)= gcd(136,48)

34 辗转相除的伪代码 欧几里得算法 function gcd(a, b) a>b while b ≠ 0 t := b ;
b := a mod b ; a := t; return a ; 思考： 如何用程序实现辗转相除法？

35 逆元(倒数) a 模m，在什么情况下一定存在乘法逆元呢？ 对于正整数m，记集合
设m是正整数，a是整数，如果存在 , 使得a×b ≡1(modm)成立，则a叫模m的可逆元，b叫a模m的模逆元(模倒数)， b通常记为a-1。 例如，设m为11，则8模11的逆元为7，因为8×7≡1(mod11)，即8-1(mod 11)=7 例如： 2-1 mod 5 ＝3 2-1mod 26=？ a 模m，在什么情况下一定存在乘法逆元呢？

36 乘法逆实例 当a和m互素的情况下，即（a,m）=1,则a的模m的逆元总是存在的。 60-1 mod 89=？ 用何种算法求乘法逆元？

37 由定理，0—26中除13以外的奇数均可取作这里的a，下表为计算求得的逆元素
定理：若 ，则a必是关于模m可逆的。 由定理，0—26中除13以外的奇数均可取作这里的a，下表为计算求得的逆元素 作业：完成实验1-3题 2017/9/12 广东科学技术职业学院

38 我们回过头来，Hill密码加密算法的思想是将l各明文字母通过线性变换转换为l个密文字母，解密只要做一次逆变换就可以了，密钥就是变换矩阵本身，即一般取n=26。
其中 或写成 其中 解密 2017/9/12 广东科学技术职业学院

39 在具体实施时 ，我们很快会发现一些困难： (1) 为了使数字与字符间可以互换，必须使用取自0—25之间的整数
在具体实施时 ，我们很快会发现一些困难： (1) 为了使数字与字符间可以互换，必须使用取自0—25之间的整数 (2)由线性代数知识 ，其中 为A的伴随矩阵。由于使用了除法，在求A的逆矩阵时可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。 2017/9/12 广东科学技术职业学院

40 当l=2时，就得到Hill2密码。其具体过程为：
步骤1:根据明文字母的表值，将明文信息用数字表示，设明文信息只需要26个字母A～Z(也可以多于26个)，通信双方给出的字母表值见表1. 步骤2:选择一个二阶可逆整矩阵K，称为密码Hill2的加密矩阵，它是这个密码体制的密钥(是加密的关键，仅通信双方知道)。 步骤3:将明文字母依次两两分组，如最后一组只有一个字母，则补充一个没有实际意义的哑字母，使每一组都由两个明字母组成。查出每个明字母的表值，构成一个2维列向量a。 步骤4:计算b=Ka，由b的两个分量反查字母表值得到的两个字母就是密文。 解密过程就是上述过程的逆过程。 2017/9/12 广东科学技术职业学院

41 例 使用Hill2密码加密明文good bye。取
例 补充哑字母e，将明文分成:go,od,by,ee;对应的向量为 经计算得: 因此密文为:qknyexmc 2017/9/12 广东科学技术职业学院

42 Hill2 加密过程 分组 明文字母 一组向量 查表值 加密矩阵 左乘 模运算 密文 一组新的向量 反查表值 问题：怎样解密？

43 Hill2 解密过程 解密：加密的逆过程，将加密过程逆转回去即可。 例2：怎么得到密文 “qknyexmc ” 的明文?
上面的向量是由 经过模 26 运算得来的，现在的问题是怎样逆转回去？ 在模运算下解方程组： A = 

44 模逆矩阵 对于正整数m，记集合 定义：对于一个元素属于集合Zm的n阶方阵A，如果存在 一个元素属于Zm的n阶方阵B ，使得
称A为模m可逆，B为A的模m逆矩阵，记为 定理：若 ，则矩阵A必是关于模m 可逆的。 2017/9/12 广东科学技术职业学院

45 Hill2 解密过程 ？ 在模运算下解方程组： A =  问题：如何计算 ？

46 模 m 逆矩阵的计算 A*为 A 的伴随矩阵 设 B=k A*为 A 的 模 26 逆，其中 k 为待定系数
本计算方法可推广到求矩阵 A 的 模 m 逆矩阵

47 Hill2 解密过程 设加密矩阵 练习： 的模逆矩阵？例2该如何解密？(实验)

48 Hill2 加密过程总结 ① 通讯双方确定加密矩阵 ( 密钥) 和字母的表值对应表 ② 将明文字母分组，通过查表列出每组字母对应的向量
若明文只含奇数个字母，则补充一个哑元 ③ 令  = A mod(m) ，由  的分量反查字母表值表， 得到相应的密文字母

49 Hill2 解密过程总结 ① 将密文字母分组，通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 m 逆矩阵 B
③ 令  = B mod(m) ，由  的分量反查字母表值表， 得到相应的明文字母

50 Hill2 解密举例 甲方收到乙方（己方）的一个密文信息，内容为：
WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 按照甲方与乙方的约定，他们之间采用 Hill2密码，密钥 为 ，字母表值见下表，问这段密文的原文 是什么？ A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

51 Hill2 解密举例 ① 将密文字母分组，通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 26 逆矩阵
③ 用 B 左乘每组密文字母组成的向量，然后再反查字母表值表，得到相应的明文字母

52 Hill2 解密举例 序号 分组 密文 表值 明文 1 W K 23 11 7 21 G U 2 V A 22 4 9 D I 3 C P
16 14 N E 5 13 M O 15 6 X 24 19 8 S H 序号 分组 密文 表值 明文 7 G W 23 9 25 I Y 8 Z U R 21 18 6 F 10 O Q 15 17 11 A 1 5 E 12 B 2 J

53 Hill2 解密举例 序号 分组 密文 表值 明文 13 L O 12 15 2 5 B E 14 H D 8 4 10 N J K C
11 3 9 1 I A 16 M 17 F 6 18 W 23 25 Y 序号 分组 密文 表值 明文 19 W C 23 3 21 1 U A 20 V L 22 12 14 4 N D E M 5 13 I 9

54 WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC
Hill2 解密举例 WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 密文 GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA A 原文 即：“古典密码是以字符为基本加密单元的密码”

55 Hill2 密码破译举例 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 我方截获一段密文
经分析该密文是用 Hill2密码 加密，且密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )，问能否破译这段密文？ 破译这段密文的关键是找到“密钥”和字母对应的表值 猜测密文是由26个字母组成，即 m=26， 经破译部门通过大量的统计分析和语言分析确定表值 A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

56 P C Hill2 密码破译举例 密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )
查 字 母 表 值 P C

57 Hill2 密码破译举例 P、C 模26可逆 可唯一确定加密矩阵 A

58 Hill2 密码破译举例 得到加密矩阵的 模26逆矩阵 后，根据前面的解密方法即可得密文的原文
HE WI LL VI SI TA CO LL EG E T HI SA FT ER NO ON 相应的 Matlab 程序见附录 4

59 RSA公开密钥系统简介 公开密钥的原理其实很简单，我们以给上面的单词 Caesar 加解密来说明它的原理。
我们先把它变成一组数，比如它的 Ascii 代码 X= （每三位代表一个字母）做明码。 现在我们来设计一个密码系统，对这个明码加密。

60 1.找两个很大的素数（质数）P 和 Q，越大越好，比如 100 位长的, 然后计算它们的乘积 N=P×Q，M=（P-1）×（Q-1）。
2，找一个和 M 互素的整数 E，也就是说 M 和 E 除了 1 以外没有公约数。 3，找一个整数 D，使得 E×D 除以 M 余 1，即 E×D mod M = 1。

61 现在世界上先进的最常用的密码系统就设计好了，其中 E 是公钥谁都可以用来加密，D 是私钥用于解密，一定要自己保存好。乘积 N 是公开的，即使敌人知道了也没关系。
现在，我们用下面的公式对 X 加密，得到密码 Y。

62 好了，现在没有密钥 D，神仙也无法从 Y 中恢复 X。

63 这个过程大致可慨括如下： 2017/9/12 广东科学技术职业学院

64 公开密钥的好处有： 1.简单 2.可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说，不论给出多少份明文和对应的密文，也无法根据已知的明文和密文的对应来破译下一份密文。更重要的是 N,E 可以公开给任何人加密用，但是只有掌握密钥 D 的人才可以解密, 即使加密者自己也是无法解密的。这样，即使加密者被抓住叛变了，整套密码系统仍然是安全的。（而凯撒大帝的加密方法有一个知道密码本的人泄密，整个密码系统就公开了。） 3.灵活，可以产生很多的公开密钥E和私钥D 的组合给不同的加密者。

65 最后让我们看看破解这种密码的难度。首先，要声明，世界上没有永远破不了的密码，关键是它能有多长时间的有效期。
要破公开密钥的加密方式，至今的研究结果表明最好的办法还是对大字N 进行因数分解，即通过 N 反过来找到 P 和 Q，这样密码就被破了。 而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。 这实际上是在拼计算机的速度， 这也就是为什么 P 和 Q 都需要非常大。 一种加密方法只有保证 50 年计算机破不了也就可以满意了。

66 前几年破解的 RSA-158 密码是这样因数分解的
= ×