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

Size: px

Start display at page:

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

遍甘
5 years ago
Views:

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

2 RSA 的数论基础

3 质数 ( 素数 ) (prime number) 一个大于 1 的自然数, 除了 1 和它本身以外不再有其他的因数, 那么这个数为素数 ; 否则称为合数最小的质数是目前为止, 人们未找到一个公式可求出所有质数 3

4 质数检验检查一个正整数 N 是否为素数, 最简单的方法就是试除法, 将该数 N 用小于等于 N 的所有素数去试除, 若均无法整除, 则 N 为素数 00 年, 印度人 M. Agrawal N. Kayal 以及 N. Saxena 提出了 AKS 质数测试算法, 证明了可以在多项式时间内检验是否为素数 4

5 模运算同余式两个整数 a b, 若它们除以整数 m 所得的余数相等, 则称 a 与 b 对于模 m 同余或 a 同余于 b 模 m, 记作 : ab (mod m) 5

6 互质数两个整数 a b, 若它们的最大公因数 gcd(a,b)=1, 则称 a 和 b 互质 6

7 Euclid 算法求最大公因子又叫辗转相除法简单的描述就是, 记 gcd(a,b) 表示非负整数 a,b 的最大公因数, 那么 :gcd(a,b)=gcd(b,a%b) C 语言实现 : unsigned int gcd(unsigned int a,unsigned int b) { return (b>0)?gcd(b,a%b):a; } 7

8 Euclid 算法求最大公因子输入 : 两个正整数,b,c, 并假设 b >c 输出 :gcd(b,c) 算法 : b r (mod c) (1) 1 c r (mod r1 ) () r1 r3 (mod r ) (3) r r (mod r ) ( j ) j j j1 r j1 0(mod rj ) ( j 1) Return r j 8

9 (mod 1066) (mod 904) (mod 16) (mod 94) 94 6 (mod 68) (mod 6) 6 10 (mod 16) 16 6 (mod 10) 10 4 (mod 6) 6 (mod 4) 4 0 (mod ) 因此 gcd(1970, 1066)= 例求 gcd(1970, 1066) 9

10 乘逆若 ax 1 mod f, 则称 a 关于模 f 的乘法逆元为 x 当 a 与 f 互素时,a 关于模 f 的乘法逆元有唯一解如果不互素, 则无解如果 f 为素数, 则从 1 到 f-1 的任意数都与 f 互素, 即在 1 到 f-1 之间都恰好有一个关于模 f 的乘法逆元 10

11 Euclid 算法求乘逆输入 : 两个正整数,a,r, 满足 gcd(a,r)=1 输出 :b, 满足 ab 1(mod r) 算法 : r aq1 c1 (1) a c1q c () c1 cq3 c3 (3) c j1 c jq j1 1 ( j 1) 递推公式 : b b b ( 1) b q b j j1 j j Return b j 11

12 例求 701 对于 1848 的乘逆 701 a 1mod1848 b 0 b ( q ) b 1b q b ( q 1) b 1b q b q3 b3 b q3 b ( 1) ( q 1) b 1b q b ( q ) b 1b q b ( q 1) b 1b q b 9 d

13 中国剩余定理设 m 1,m,,m k 是两两互素的正整数, M 同余方程组 k i1 m, 则一次 i 对模 M 有惟一解 : 其中 e i 满足 a1 mod m1 x a mod m x a mod k mk x M M M x e 1a1 ea ekak mod M m1 m mk M e i 1 mod m i i 1,,, k m i 13

14 x 1(mod 5) x 5(mod 6) x 4(mod 7) x 10(mod11) M M M M M Miei 1(mod mi ) e 3, e e e x ( M e a M e a M e a M e a )mod M ( )mod 例 14

15 欧拉函数欧拉函数是指 : 对于一个正整数 n, 小于 n 且和 n 互质的正整数 ( 包括 1) 的个数, 记作 ( n) 对于一个正整数 n, 如果它的素因子有 i 个, 为 p1, p,, pi, 则 : ( n) n1 1 1 p p p 对于素数 p, ( p) = p -1 1 i 对于两个不同素数 p, q, 它们的乘积 n = p ( n) ( p 1) ( q 1) q, 则 : 15

16 费尔玛小定理 (Fermat Theory) 若 p 是素数,a 是正整数且 gcd(a, p)=1, 则 : a p-1 1 mod p 16

17 欧拉定理 (Euler Theorem) ( 称费马 - 欧拉定理或欧拉函数定理 ) 若 a 和 n 互素, 则 a φ(n) 1 mod n 17

18 RSA 18

19 对称密码的局限性 RSA 的产生过程公钥密码的思想 Diffie, W. and M.E. Hellman (1976). New directions in cryptography. RSA 单向陷门函数的构造 19

20 参数 : N=pq. RSA 的单向陷门函数 e 加密指数 gcd(e, (N) ) = 1. 单向函数 : RSA(M) = Me (mod N) 其中 MZN * 陷门 : d 解密指数. 其中 ed = 1 (mod (N) ) 解密 : RSA(Y) d = M ed = M k(n)+1 = M (mod N) 0

21 RSA: 密钥的产生 1 选两个保密的大素数 p 和 q 计算 n=p q,φ(n)=(p-1)(q-1), 其中 φ(n) 是 n 的欧拉函数值 3 选一整数 e, 满足 1<e<φ(n), 且 gcd(φ(n), e)=1 4 计算 d, 满足 d e 1 mod φ(n), 即 d 是 e 在模 φ(n) 下的乘法逆元, 因 e 与 φ(n) 互素, 由模运算可知, 它的乘法逆元一定存在 5 以 {e, n} 为公开钥, {d, n} 为秘密钥 1

22 RSA: 加密加密时首先将明文比特串分组, 使得每个分组对应的十进制数小于 n, 即分组长度小于 log n 然后对每个明文分组 m, 作加密运算 : c m e mod n

23 RSA: 解密对密文分组的解密运算为 : m c d mod n 3

24 举例令 p 3, q 11, n 33, 则 : * n { 1,, 4, 5, 7, 8, 10, 13, 14, 16 17, 19, 0, 3, 5, 6, 8, 9, 31, 3} ( n) 0 * ( n) { 1, 3, 7, 9, 11, 13, 17, 19} 令 : b 7, a 3, 有 ba 1 1 (mod 0) 7 e K ( x) x mod33 令 : 3 d ( y) y mod33 K x y e ( x) x d ( y) b a 4

25 因子分解问题三种数学攻击方法分解 n=p.q, 因此可计算出 φ(n), 从而确定 d 直接确定 φ(n), 然后找到 d 直接确定 d 大家相信 : 由 n 确定 φ(n) 等价于因子分解 5

26 平方 - 乘算法平方 - 乘算法假定指数 c 用二进制表示, 即其中 ci 0或 1,0 i l 1 c l1 c i0 算法 Square-and-Multiply( x, c, n ) z 1 for i l 1 down to 0 z z mod n do if ci 1 then z ( z x)mod n return( z) i i c 计算 z x mod n的算法如下 : Douglas R.Stinson, 密码学原理与实践 ( 第三版 ) 6

27 举例 RSA 算法, 假设 n 11413, 公开的指数 b 3533 Alice 利用平方 - 乘算法, 通过计算 mod 来加密明文 976, 过程为 i b z i

28 RSA 解密算法的改进算法改进的 RSA 解密算法 ( n, p, q, a, y ) 1 计算 a a mod( p 1) p a a mod( q 1) q 计算 a p x p y mod p x p x mod p 可证 a q xq y mod q xq x mod q 由中国剩余定理可推出 x mod n, 具体运算为 : 1 h q ( x p xq )mod p x x h q mod n q Return (x) 维基百科 8

29 举例算法输入 ( n , p 61, q 53, a 753, y 790) 1 计算 a a mod( p 1) 753mod(61 1) 53 p a a mod( q 1) 753mod(53 1) 49 q 计算 a p 53 x p y mod p 790 mod 61 4 aq xq y q 1 1 q mod p 53 mod mod 790 mod h q x p xq p ( )mod 38 (4 1)mod 61 1 x x h q mod n q Return (x) 维基百科 9

30 RSA 中参数的选择 : 密钥长度估计在未来一段比较长的时期, 密钥长度介于 104 比特至 048 比特之间的 RSA 是安全的 NIST: AES 密钥长度 RSA 模长度 56 bits 51 bits. 80 bits 104 bits 11bits 048 bits 18 bits 307 bits 19 bits 7680 bits 56 bits (AES) bits 30

幻灯片 1

幻灯片 1 背景介绍与复习移位密码仿射密码课堂练习 2 信息加密的重要性战场商业竞争日常生活 3 藏头诗芦花丛里一扁舟俊杰俄从此地游义士若能知此理反躬逃难可无忧 4 反清复明 5 列宁的六个墨水瓶 6 凯撒密码恺撒大帝 7 凯撒密码 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

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

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