美文网首页
RSA算法实现

RSA算法实现

作者: 树懒啊树懒 | 来源:发表于2018-06-04 14:17 被阅读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成功分解就能获得d,从而破解密钥.

  • 但是:
    下文4会介绍,分解n只能暴力破解,目前声明破解最长的是768位的密钥,那么我们使用至少大于1024位的密钥,还是很安全的, 某种程度是越长越好.

只有这样, 在无法分解质数乘积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 (这里拿小数字测试) ,它们是互质关系

  • 质数 : 只能被1和本身整除
  • 互质关系 : 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是

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

  • 所谓“模反元素”就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
这个式子等价于
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。”加密–解密”的整个过程全部完成。

相关文章

  • RSA算法原理(作者: 阮一峰)

    RSA算法原理(一) RSA算法原理(二) RSA C算法实现【 看雪安全论坛】

  • 计算机安全学-第四次实践作业-2018/4/17

    [new] 1、用Python或Sage实现RSA算法的加密、解密、签名/验证签名使用sage实现RSA算法进行加...

  • RSA非对称加解密原理及示例代码

    RSA非对称加解密可以实现安全传输,本文简单介绍一下其原理和实现代码 RSA加密算法 RSA加密算法是一种非对称加...

  • RSA加密算法(java版)

    算法简介 RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。 算法实现 1、RSAU...

  • RSA算法实现

    1 非对称加密算法 (1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。(2)甲...

  • RSA 算法实现

    密码学基础 密码技术用于保证电子数据的安全性,完整性和真实性。 保密性:对数据进行加密,使得非法用户无法读懂数据信...

  • JAVA加解密16-非对称加密算法-RSA算法

    一、概述1.RSA是基于大数因子分解难题。目前各种主流计算机语言都支持RSA算法的实现2.java6支持RSA算法...

  • # RSA 公钥加密算法

    # RSA 公钥加密算法 # RSA 公钥加密算法

  • RSA加密

    RSA加密为非对称加密实现 对称加密:加密解密使用同一个算法 非对称加密:加密和解密使用不同算法 rsa加密原理 ...

  • 6.1 密码学专题 - 非对称加密算法 - RSA 算法

    密码学专题 - 非对称加密算法 - RSA 算法 6.1 RSA 算法 第一个较完善的非对称加密算法 RSA,它既...

网友评论

      本文标题:RSA算法实现

      本文链接:https://www.haomeiwen.com/subject/hvcifftx.html