python - 以编程方式从 `d` 和 `p` (RSA) 生成 `q`

Question

我有两个数字，p 和 q。我知道我可以获得 phi = (p-1)*(q-1) 并且 ed = 1 (mod phi)... 但我不是我当然明白这意味着什么。

我写了一些 Python:

p = NUM
q = NUM
e = NUM
phi = (p-1)*(q-1)
d = (1 % phi)/float(e)

但我得到的总是小数，d 应该是一个整数。我做错了什么？

编辑:我可能只是不了解 RSA。现在，我正在查看此页面:http://www.di-mgt.com.au/rsa_alg.html

Answer 1

你对数学的理解是错误的。等式

ed ≡ 1 (mod φ)

表示 ed 除以 φ 的余数等于 1，即在 Python 中，

>>> (e*d) % phi
1

例如，如果 φ = (7 - 1)(11 - 1) = 60，并且 e = 17，那么如果我们选择 d = 53，那么我们会得到

>>> e = 17
>>> d = 53
>>> phi = 60
>>> (e*d) % phi
1

我们称 d 为 e 的模乘逆。

要从e 和φ 生成d，通常使用扩展欧氏算法。请阅读http://en.wikipedia.org/wiki/Modular_multiplicative_inverse或 https://stackoverflow.com/search?q=python+%22multiplicative+inverse%22&submit=search了解更多信息