python - RSA 编码和解码 [e,d]。在 python 中查找 e 和 d.. 更新

Question

我一直在努力寻找编码数和解码数。我知道你需要找到这些的基本规则，并开始尝试创建一个 python 程序，它从前 150 个素数的随机选择中找到 e 变量和 d 变量。我这样做的方式是:

import random
from primesieve import *
from sympy.solvers import *
from sympy import *
f = 0
choiceOfPrimes = generate_primes(10)

p = random.choice(choiceOfPrimes)
q = random.choice(choiceOfPrimes)

while p == q:
    p = random.choice(choiceOfPrimes)

n = p * q
phiN = (p-1) * (q-1)
lista = []
listb = []
for naa in range(1, phiN):
    lista.append(naa)
for naaa in range(1, 35):
    listb.append(naaa)

e = random.choice(lista)


def finding_d():
    global phiN
    global e
    global f
    f = e
    abc = []
    abc = divmod(phiN, f)
    abc1 = f * abc[0]
    abc2 = abc[1]
    phiN = f * abc1 + abc2  # phiN = f * {how many it goes in} + {remainder}
    abc3 = divmod(f, abc2)
    f = abc2 * abc3[0] + abc3[1]  # (moved f to phiN) and (remainder to f)
    abc4 = divmod(abc2, abc3[1])
    e1 = abc3[1] * abc4[0]
    e2 = abc4[1]
    abc2 = e1 + e2
    e3 = abc2 + (e1*-1) # This bit I am struggling





d = f


while (e % n) == 0 and (e % phiN) == 0:
    for r in range(phiN, 0, -1):
        e = r

while ((d * e) % phiN) != 1:
    for r in range(1, 35):
        e = r

print(p, q, n, phiN, e, d)

它需要永远运行并且从未完成运行。我什至尝试将 generate_primes(150) 更改为 generate_primes(10) 但同样的问题发生了。

有没有人有解决方案，我很乐意听到(顺便说一下，primesieve 库不会自动包含在 python 库中，您必须自己下载)。谢谢。

编辑:

我做了: 而 p == q: p = random.choice(choiceOfPrimes) 但是我很难做欧几里德垫子

Answer 1

你的代码有很多问题:

首先，

while p == q:
   p = random.choice(choiceOfPrimes)

You should do this step before calculating the value of phiN as the value of phiN would change if you change the value of p.

---

其次，

d = random.choice(lista)

For calculating d you should find the Modular multiplicative inverse of e with respect to phiN using the Extended Euclidean algorithm, choosing values of e untill they work is very inefficient.