программно генерировать `d` из` p` и `q` (RSA)

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 (мод φ )

означает, что остаток числа 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 .

Для генерации d из e и φ , обычнорасширенный евклидов алгоритм.Пожалуйста, прочитайте http://en.wikipedia.org/wiki/Modular_multiplicative_inverse или https://stackoverflow.com/search?q=python+%22multiplicative+inverse%22&submit=search для получения дополнительной информации

Answer 2

Поскольку знаменатель в делении - это число с плавающей точкой, Python всегда будет переводить результат деления в число с плавающей точкой.

Если вы хотите явно получить результат в виде целого числа, не рекламируйте ни одно изоператоры, чтобы плавать, и использовать вместо этого оператор "//" - это предотвращает, "совместимым с будущим" способом, автоматическое преобразование результата деления в число с плавающей точкой.

d = (1 % phi)// e

Answer 3

Возвращается десятичное число, потому что вы делите на число с плавающей запятой

float(e)

Конечное число можно преобразовать в целое число, обернув все вычисления в функцию int () следующим образом:

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