幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

室靳
5 years ago
Views:

2 背景介绍与复习移位密码仿射密码课堂练习 2

3 信息加密的重要性战场商业竞争日常生活 3

4 藏头诗芦花丛里一扁舟俊杰俄从此地游义士若能知此理反躬逃难可无忧 4

5 反清复明 5

6 列宁的六个墨水瓶 6

7 凯撒密码恺撒大帝 7

8 凯撒密码 L O R Y H X 密文 I L O V E U 明文 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 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 密文明文 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 8

9 凯撒密码凯撒密码是移位密码的一个特例也是仿射密码的一个特例明文密文 9

10 互素同余定义设 a 1, a 2 是两个不为零的整数. 如果存在 d Z, 使得 d a i (i = 1,2), 则 d 叫做 a 1, a 2, 的公因数. 公因数中最大的一个叫做最大公因数, 记作 (a 1, a 2 ). 若 (a 1, a 2 ) = 1, 则称 a 1, a 2 互素. 例 : (3, 5) = 1, (7, 11) = 1, (15, 10) = 5. 定义设 a, b Z, m 是一个正整数. 如果用 m 分别去除 a 和 b 所得的余数相同, 则称 a 和 b 关于模 m 同余, 记作 a b (mod m). 例如 : 1 27 mod 26, mod 26. 同余方定理设 (a, m) = 1, 则一元一次同余方程 ax b (mod m) 有且仅有一个解 x ba φ m 1 (mod m). φ m 是欧拉函数, φ(m) 表示所有不大于 m 且与 m 互素的正整数的个数. 10 程

11 移位密码 (shift cipher) 的数学基础是同余和模运算. 模 m 同余意义下的等价类记为 Z m = {0, 1, 2,, m-1}. 英文字母共有 26 个, 所以移位密码一般定义在 Z 26 上, 这样可以建立所有英文字母和 Z 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

12 移位密码体制 : 令 P = C = K = Z 26. 对每个 K Z 26 以及任意 x, y Z 26, 定义如下加密函数和解密函数 : e K (x) = (x + K) mod 26 d K (y) = (y K) mod 26 P, C, K 分别表示明文空间密文空间和密钥空间. 当 K = 3 时, 移位密码体制通常叫做凯撒密码, 因为凯撒最早使用了这种密码. 12

13 13

14 例有一串明文为 : beijingchina, 假设用来加密的移位密码的密钥 K = 17, 求其密文. 解 : ( 为了区分, 这里约定小写表示明文, 大写表示密文 ): 明文密文 b e i j i n g c h i n a S V Z A Z E X T Y Z E R 查表模运算 e K (x) = (x + 17) mod 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

15 安全性分析 : 移位密码不安全. 密钥空间太小, 只有 26 种可能. 可用穷举攻击来破译, 穷举所有可能的密钥, 得到攻击者所希望的有意义的明文. 更安全的密码体制 : 仿射密码置换密码 RSA 密码等. 15

16 仿射密码 (Affine cipher) 是移位密码的一种推广, 其加密函数定义为 : e(x) = (ax + b) mod 26 其中 a, b Z 26. 因为这样的函数被称为仿射函数, 所以也将这样的密码体制称为仿射密码. 显然, 当 a = 1 时, 仿射密码退化为移位密码. 当 a = 1, b = 3 时, 仿射密码退化为凯撒密码.

17 仿射密码 (Affine cipher) 是移位密码的一种推广, 其加密函数定义为 : e(x) = (ax + b) mod 26 其中 a, b Z 26. 因为这样的函数被称为仿射函数, 所以也将这样的密码体制称为仿射密码. 显然, 当 a = 1 时, 仿射密码退化为移位密码. 当 a = 1, b = 3 时, 仿射密码退化为凯撒密码. 为了能对密文进行解密, 必须保证所选用的仿射函数是单射, 即要求对任意 y Z 26, 关于 x 的同余方程 ax + b y (mod 26), 也即 ax y b (mod 26) 有唯一解. 由定理知, 这等价于要求 (a, 26) = 1. 定理设 (a, m) = 1, 则一元一次同余方程 ax b (mod m) 有且仅有一个解 x ba φ m 1 (mod m). 17

18 因此, 由于我们要求仿射密码的加密函数是单射, 即等价于要求 (a, 26) = 1. 就是说 a 必须是不超过 26 并且与 26 互素的整数. 即 a 取值的个数等于欧拉函数 φ(26) = φ(2)φ(13) = 12. 又因为 b 可在 Z 26 中任意取值, 所以仿射密码的密钥空间 K = {(a, b) Z 26 Z 26 (a, 26) = 1}, 其中包含 = 312 个密钥. 当 (a, 26) = 1 时, 方程 ax y b (mod 26) 的唯一解为 x (y b)a φ 26 1 a 11 (y b) (mod 26), 因此相应的解密函数可定义为 : d(y) = a 11 (y b) mod 26 定理设 (a, m) = 1, 则一元一次同余方程 ax b (mod m) 有且仅有一个解 x ba φ m 1 (mod m). 18

19 仿射密码体制 : 令 P = C = Z 26, K = {(a, b) Z 26 Z 26 (a, 26) = 1}. 对每个 K = (a, b) K, 以及任意 x, y Z 26, 定义如下加密函数和解密函数 : e K (x) = (ax + b) mod 26 d K (y) = a 11 (y b) mod 26 例如, 如果 K = (5, 7), 那么明文 x=iloveu 加密后的密文 y 是? VKZIBD 由欧拉定理知 a 12 1 (mod 26), 我们不难验证 : d K e k x = a 11 ax + b b = a 12 x x (mod 26). 19

20 因为仿射密码仅有 312 个可能的密钥, 所以可用穷举攻击破译仿射密码. 另外一种破译仿射密码的方法是对密文的字母出现的频率进行分析, 这种方法利用英文的如下统计特性, 下表由 H. Beker 和 F. Piper 给出 : 字母概率 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

21 下面利用英文的统计特性来分析一段用仿射密码体制得到的密文. 假设从仿射密码中获得了如下密文 : FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 上述密文中各英文字母出现的次数如下 : 字母 : 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 次数 : 我们关心其中出现次数较多的字母 : R 出现 8 次, D 出现 7 次, E H K 各出现 5 次, F 和 V 各 4 次. 21

22 首先, 因为 e 和 t 是一般英文中出现概率最大的字母, 所以我们猜测 R 由 e 加密而得, D 由 t 加密而得. 用函数表达即是 : e K (4) = 17 和 e K (19) = 3, 这里 e K (x) = ax + b, 而 a, b Z 26 待定. 于是有方程组 : 4a + b = 17, 19a + b = 3 ( 注意 mod 26 可略去, 下同 ) 在 Z 26 中这个方程组有唯一解 : a = 6, b = 19. 因为 (a, 26) 1, 所以这个密钥不合法, 我们猜测是错误的. 继续这个过程, 直到猜想 R 是 e 的加密, K 是 t 的加密, 此时 a = 3, b = 5, 因为 a, 26 = 1, 所以是合法的密钥. 计算知对应的解密函数是 d K (y) = 9y 19, 解密后得到有意义的明文如下 : algorithms are quite general definitions of arithmetic processes 22 密文 : FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH

23 计算 : 解密用移位密码加密的密文 : YFXMPCESPZCJ TDFDPQFWQZCPYNTASPCTYRXPDDLRPD 解 : 密文中字母出现次数排序 P(7 次 ), D(5 次 ) P e = 4 + K mod 26 ( 加密 ) K = 11 ( 密钥 ) d K (y) = y 11 mod 26 ( 解密函数 ) 密文查表解密查表明文 Y F X M P C n u m b e r y 11 mod 26 解密后得到有意义的明文 : number theory is useful for enciphering messages 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

24 计算 : 设使用仿射密码 e(x) = (ax + b) mod 26 加密后得到的一段很长的密文中, W 和 B 出现的次数最多, 求 a, b 最可能的取值. 解 : 因为 e 和 t 是一般英文中出现概率最大的字母, 所以我们猜测 W 由 e 加密而得, B 由 t 加密而得. 用函数表达即是 : e K (4) = 22 和 e K (19) = 1, 这里 e K (x) = ax + b, 而 a, b Z 26 待定. 于是有方程组 : 4a + b = 22, 19a + b = 1 在 Z 26 中这个方程组有唯一解 : a = 9, b = 12. 此外, 因为 (a, 26) = 1, 保证了加密函数是单射, 所以这个密钥是合法的. 24

25 小结主要内容 : 凯撒密码 e K (x) = (x + 3) mod 26 1 移位密码 e K (x) = (x + K) mod 仿射密码 e K (x) = (ax + b) mod 关键点 : 基于字母出现频率的密码破译仿射密码破译中同余方程的约束与求解 25

26 课后作业 1 用 C++ 编程实现仿射密码的加密解密过程. 2 已知用移位密码加密的长密文中出现频率最高的字母是 Q, 求移位密码最有可能使用的密钥. 3 解密用仿射密码加密的密文 : USLELJUTCCYRTPSURKLTYGGFVELYUSLRYXDJURTUULVCUURJRKQLLQLYXS RVLBRYZCYREKLVEXBRYZDGHRGUSLJLLMLYPDJLJ

RSA 图为 RSA 公开密钥算法的发明人, 从左到右 Ron Rivest, Adi Shamir, Leonard Adleman. 照片摄于 1978 年裴士辉 QQ:

RSA 图为 RSA 公开密钥算法的发明人, 从左到右 Ron Rivest, Adi Shamir, Leonard Adleman. 照片摄于 1978 年裴士辉 QQ:168159305 RSA 的数论基础质数 ( 素数 ) (prime number) 一个大于 1 的自然数, 除了 1 和它本身以外不再有其他的因数, 那么这个数为素数 ; 否则称为合数最小的质数是目前为止, 人们未找到一个公式可求出所有质数