用Python测试RSA

Question

我创建了一个用于测试RSA的小代码，但是当我试图用6-7位长的密钥解密一条消息时，需要一段时间，并给出错误的结果。

from math import sqrt


def isPrime(n):
    x = int(sqrt(n)) + 1

    if n < 2:
        return False`

    for i in range(2, x):
        if (n / i).is_integer():
            return (i, False

    return True


def factor(num):
    hold = list()
    inum = int(sqrt(num) + 1)

    hold.append((1, num))
    if num % 2 == 0: hold.append((2, int(num / 2)))

    for i in range(3, inum, 2):
        x = num / i

        if x.is_integer():
            hold.append((i, int(x)))

    return hold


def egcd(a, b):
    #Extended Euclidean Algorithm
    x,y, u,v = 0,1, 1,0

    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b

    return y


def fastMod(n, e):
    if e == 0:
        return 1

    if e % 2 == 1:
        return n * fastMod(n, e - 1)

    p = fastMod(n, e / 2)
    return p * p


def decrypt(p, q, em):
    #Uses CRT for decrypting
    mp = em % p; mq = em % q;
    dp = d % (p-1); dq = d % (q-1);
    xp = fastMod(mp, dp) % p; xq = fastMod(mq, dq) % q

    log = egcd(p, q)
    cp = (p-log) if log > 0 else (p+log)
    cq = cp

    m = (((q*cp)*xp) + ((p*cq)*xq)) % n

    return m


def encrypt(pm):
    return fastMod(pm, e) % n

有什么方法可以提高速度或修正错误吗？我试图解密一些我用密钥9-10位长的信息，但太长了。

Answer 1

很多事情都需要改进，但最值得注意的是：

• 对于RSA加密/解密：fastMod( )应将模数作为输入参数，并将每次迭代时的模减小。我找到了这段代码，它说明了正确的方法。
• 对于参数生成:实际上，不能使用像isPrime( )这样的函数来确定素数，因为它是在指数时间内运行的。相反，您应该执行Miller-Rabin /强伪素数检验，它可以使用fastMod( )作为子例程。

顺便说一句，您正在这里实现教科书RSA，这是非常不安全的。您需要使用填充(如OAEP )来具有安全性，但您需要非常小心地执行它，以防止各种形式的攻击(如侧通道攻击)。

至于为什么你得到了错误的结果，很难不看到你所有的代码。也许您希望包含一个main函数，该函数生成params并尝试使用它们进行加密和解密。

编辑:我确实注意到了这个看起来可疑的地方：log = egcd(p, q)。不知道你在这里做什么。我建议您首先将d计算为e mod (p-1)*(q-1)的逆，并验证是否正确(即乘以d*e mod (p-1)*(q-1)并确保结果为1)。如果是这样的话，那么执行一个fastMod( )和d，看看它是否解密(它应该)。一旦你成功了，然后继续让CRT发挥作用。