以“p”和“q”（RSA）方式编程生成`d'

问题描述

我有两个数字 p 和 q 。我知道我可以得到 phi =（p-1）*（q-1），而 ed = 1（mod phi） ...但我不知道我得到了什么意思。

I have two numbers, p, and q. I know that I can get phi = (p-1)*(q-1) and that ed = 1 (mod phi)... but I'm not sure I get what this means.

我写了一些Python：

I wrote some Python:

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

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

But I always get a decimal, and d is supposed to be an integer. what am I doing wrong?

编辑：我可能不明白RSA。现在，我在看这个页面：

I may just not understand RSA. Right now, I'm looking at this page: http://www.di-mgt.com.au/rsa_alg.html

推荐答案

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

Your understanding of the math is wrong. The equation

意味着，编号 > φ 等于1，即以Python为例，

means that, the remainder of number ed dividing φ is equal to 1, i.e. in terms of Python,

>>> (e*d) % phi
1

例如，如果&phi =（7 - 1）（11 - 1）= 60，而 e = 17，那么如果我们选择 d = 53，

For instance, if φ = (7 - 1)(11 - 1) = 60, and e = 17, then if we choose d = 53, then we'll get

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

我们调用 d e 的模块化乘法逆。

We call d a modular multiplicative inverse of e.

从 e 生成 d 通常使用扩展欧几里得算法。请阅读或更多信息

To generate d from e and φ, usually extended Euclidean algorithm is used. Please read http://en.wikipedia.org/wiki/Modular_multiplicative_inverse or https://stackoverflow.com/search?q=python+%22multiplicative+inverse%22&submit=search for more info

这篇关于以“p”和“q”（RSA）方式编程生成`d'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！