首页 / 知识

python RSA加密算法过程

2023-11-12 13:32:00

1，随机选取两个质数p和q

2，计算n=pq

3，选取一个与Ø(n)互质的小奇数e，Ø(n)=(p-1)(q-1)

4，对模Ø(n)，计算e的乘法逆元d，即满足(e*d)modØ(n)=1

5，公钥(e,n)，私钥(d,n)

详细解析如下：

RSA中的公钥和私钥需要结合在一起工作。公钥用来对数据块加密，之后，只有对应的私钥才能用来解密。生成密钥时，需要遵循几个步骤以确保公钥和私钥的这种关系能够正常工作。这些步骤也确保没有实际方法能够从一个密钥推出另一个。

开始前，首先要选择两个大的素数，记为p和q。根据当今求解大数因子的技术水平，这两个数应该至少有200位，这们在实践中才可以认为是安全的。

然后，开始计算n:

n=pq

接下来，选择一个小的奇数e，它将成为公钥的一部分。选择e最需要考虑的重点是它与(p-1)(q-1)不能有相同的因子。换句话说，e与(p-1)(q-1)是互为素数关系的。比如，如果p=11而q=19，那么n=11X19=209。这里选择e=17，因为(p-1)(q-1)=10X18=180，而17和180没有相同的因子。通常选择3、17、65、537作为e的值。使用这些值不会对RSA的安全性造成影响，因为解密数据还需要用到私钥。

一旦为e选择了一个值，接下来开始计算相对应的值d，d将成为私钥的一部分。d的值就是计算e的倒数对(p-1)(q-1)的取模结果，公式如下：

d=e-1mod(p-1)(q-1)

这里d和e是模乘法逆元的关系。

思考一下这个问题：当d为多少时可以满足edmod(p-1)(q-1)=1?比如在等式17dmod180=1中，d的一个可能值是53。其他的可能值是233、413、593等。在实践中，可以利用欧几里德算法来计算模乘法逆元。这里就不再展开。

现在有了e和d的值，将(e,n)作为公钥P，将(d,n)作为私钥S并保持其不可见。表示为：

P=(e,n),S=(d,n)

加密方使用P来加密数据，解密方使用S来解密。为了防止就算有人知道了P也无法推算出S，必须保证p和q的值绝对不能暴露。

P和S结合在一起提供的安全性来自于一个事实，那就是乘法是一种很好的单向函数。

单向函数是加密技术的基础。简单的说，单向函数就是在一个方向上能够很容易算出结果，但反向推导则是不切实际的。比如，在RSA算法中，计算p和q的成绩是一种单向函数，因为尽管计算p和q的成绩很容易，但将n反向因子分解为p和q则是极其耗时的。这里，选择的p和q的值要足够大才可以。

计算P和S的步骤起源于欧拉函数中的一些有趣性质。特别是，这些性质允许对模幂运算做一些有用的操作。

欧拉函数记为φ(n)，定义所有小于n的正整数里和n互素的整数的个数。

只有当两个整数的唯一公因子为1时，才说这两个整数是互素的。例如，φ(8)=4，因为一共只用4个比8小的整数是互素的，它们是1，3，5，7。

欧拉方程有两个性质对RSA算法来说是特别重要的。

第一，当n是素数时，φ(n)=n-1。这是由于n的唯一因子是1和n，因此，n与之前的所有n-1个正整数都是互素的。

另一个有趣的性质是对于任意小于n且与n互素的正整数a，都有aφ(n)modn=1。例如，14mod8=1,34mod8=1,54mod8=1,74mod8=1。对上述方程两边都乘以a，得到：

(a)(aφ(n)modn)=a，或者aφ(n)+1modn=a

因此，可以得到15mod8=1,35mod8=3,55mod8=5,75mod8=7。

调整之后得到的等式非常强大。因为对于某些等式c=memodn，该等于可以让我们找出一个d的值，使得cdmodn=m。

这就是RSA算法中允许加密数据，之后再解密回原文的恒等式。可以按照如下方式表示：

cdmodn=(me)dmodn=medmodn=mφ(n)+1modn=mmodn

欧拉函数和指数间的关系保证了加密的任意数据都能够唯一地解密回来。为了找出d的值，解方程d=e-1φ(n)+1。不巧的是，对于方程d=e-1φ(n)+1不一定总是有整数解。为了解决这种问题，转而计算dmodφ(n)的值。换句话说，d=(e-1φ(n)+1)modφ(n)，可以简化为：

d=e-1modφ(n)

我们可以得到这样的简化形式，因为(φ(n)+1)modφ(n)=(φ(n)+1)-φ(n)=1。可以用任意的正整数替代φ(n)来证明等式成立。注意这个方程式同之前计算密钥的过程中得出d的推导式之间的相似之处。这提供了一种通过e和n来计算d的方法。当然了，e和n是公开的，对于攻击者来说是事先可知的，因此就有人问，这难道不是给了攻击者相同的机会来计算出私钥吗?讨论到这里，是时候来探讨一下RSA算法安全性保障的由来了。

RSA算法的安全性保障来自一个重要的事实，那就是欧拉函数是乘法性质的。这意味着如果p和q是互素的，那么有φ(pq)=φ(p)φ(q)。因此，如果有两个素数p和q，且n=p*q，则φ(n)=(p-1)(q-1)，而且最重要的是：

d=e-1mod(p-1)(q-1)

因此，尽管攻击者可能知道了e和n的值，为了计算出d必须知道φ(n)，而这又必须同时得到p和q的值才能办到。由于p和q是不可知的，因此攻击者只能计算n的因子，只要给出的p和q的值足够大，这就是一个相当耗费时间的过程。

以上内容为大家介绍了pythonRSA加密算法过程，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注我们

培训指数数据工作第一