RSA，从列表中计算值

Question

我正在编写脚本，以便为我提供RSA公钥和私钥。我正在尝试计算"e"one_answers"d"的值，其中ed=1mod64。我知道这些值将是e=5和d=13。我有两个到64的素数列表，我想把这些列表相乘来计算"e"one_answers"d"。我相信它会涉及一个while循环，这样，当值不是65时，就可以继续。然而，我正在努力编写这段代码，因为我不知道如何使列表不并行计算。如果有人问我这个问题，我很抱歉，但我已经兜圈子很长一段时间了，如果被问到了，请发布链接，我会删除这个问题。

Answer 1

我是itertools模块的粉丝，所以这里有一个使用它的例子

Python:

import itertools
primes = [2, 3, 5, 7]
for p, q in itertools.combinations(primes,2):
    print ((p,q))

输出为：

(2, 3)
(2, 5)
(2, 7)
(3, 5)
(3, 7)
(5, 7)

Python:

primes = [2, 3, 5, 7, 11, 13, 17, 19]
for e, d in itertools.combinations(primes,2):
    if (e*d) % 64 == 1:
        print ((e,d))

输出：

(5,13)

注意，一般来说，这是一个非常低效的算法来寻找模逆。相反，对于任何大于玩具大小的参数，都应该使用某种版本的扩展欧几里德算法。

Answer 2

1=ed mod m等价于说存在一个整数k，使得1+k m=ed。由于您正在寻找正d<m、 还可以观察到，k<e.因此，以下代码应适用于

def invm(e,m):
   for k in range(e):
     if (k*m + 1) % e == 0:
        return (k*m+1)//e

只要e很小，这是相当有效的。因此，这甚至适用于大多数实际大小的RSA密钥，因为大多数RSA密钥使用e=65537。