通过`p`和`q`程序生成`d`（RSA）

Question

我有两个数字，p和q。我知道可以通过公式phi = (p-1)*(q-1)来计算出phi，并且知道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

它返回的是小数，因为你在用一个浮点数进行除法运算。

float(e)

你可以通过把整个计算放在一个 int() 函数里来把最后的结果转换成整数，像这样：

d = int( (1 mod phi)/float(e) )

Answer 2

因为在除法运算中，下面的数字是一个小数，所以Python会把结果自动变成小数。

如果你想要结果是整数，就不要把任何一个运算符变成小数，使用“//”这个运算符，它可以防止结果自动变成小数，这样做是为了将来兼容。

d = (1 % phi)// e

Answer 3

你的数学理解有点问题。这个公式

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