RSA 简述

RSA算法

1）选择两个大的素数p，q，计算出模数 N = p * q
2）计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质（互质：公约数只有1的两个整数）
3）取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) （模反元素：如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。）
4）对明文m进行加密：c = pow(m, e, N),可以得到密文c。
5）对密文c进行解密：m = pow(c, d, N),可以得到明文m。

 已知p，q，e，求d

设欧拉函数 fn， fn = (p-1)(q-1)

d * e mod fn == 1 ， 用gmpy2写一个

在一次RSA**对生成中，假设p=473398607161，q=4511491，e=17求解出d

# -*- coding:utf8 -*-
import gmpy2

p = gmpy2.mpz(473398607161)  # 初始化
q = gmpy2.mpz(4511491)
e = gmpy2.mpz(17)
fn = (q-1)*(p-1)  # 求fn
d = gmpy2.invert(e,fn)  # gmpy2.invert(x,m) 就是 x*y mod m == 1，得到的结果是y
print(d)

后续······