RSA算法实现

2018-06-04  本文已影响106人  树懒啊树懒

1 非对称加密算法

(1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
(2)甲方获取乙方的公钥,然后用它对信息加密。
(3)乙方得到加密后的信息,用私钥解密。

如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。

三位数学家Rivest、Shamir 和 Adleman

2 发明者

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

3 如何生成公钥和密钥?

RSA算法密钥需要生成下面六个数字 (如何生成在👇 的6中解释)

p = 质数 (最好大于1024位)
q = 质数 (最好大于1024位 , 两个不相等的质数p和q)
n = p和q的乘积 (公开的)
φ(n) = n的欧拉函数
e = 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质 (公开的)
d = e对于φ(n)的模反元素d

上面6个数字会保证一点 : 公钥加密的信息只有私钥解得开

只有这样, 在无法分解质数乘积n时,公钥加密的信息只有私钥解得开

4 破解RSA算法的核心 : 分解质数乘积n

根据已经披露的文献,目前被破解的最长RSA密钥是 768 个二进制位。

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

它等于这样两个质数的乘积:

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

5 如何获得上面满足要求的6个数字?

1 : 随机选择质数p= 77 和 q = 91 (这里拿小数字测试) ,它们是互质关系

2 : 质数乘积 n = p x q = 77 x 91 = 7007

3 : 计算n的欧拉函数φ(n) = (p-1)(q-1) = 76 x 90 = 6840

4 : 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
这里假设选择 e = 777

5 : 计算e对于φ(n)的模反元素d

这个式子等价于
ed – 1 = kφ(n)
于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1
已知 e = 777 , φ(n) = 6840,
777 x + 6840 y = 1

这个方程可以用“扩展欧几里得算法”求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。

5 公钥如何加密? 私钥如何解密?

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓”加密”,就是算出下式的c:

  me ≡ c (mod n)

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

  6517 ≡ 2790 (mod 3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

  cd ≡ m (mod n)

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

  27902753 ≡ 65 (mod 3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。”加密–解密”的整个过程全部完成。

上一篇 下一篇

猜你喜欢

热点阅读