Python

Question

所以我正在尝试创建一个非常简单的 RSA encryption/decryption 程序，其中我只 encrypt/decrypt int 数字。除一个问题外，一切正常。有时我的解密号码（消息）与我的原始号码（我需要加密和解密的消息）不匹配。只要我输入的数字（消息）接近我的 'n' 变量中的数字（n=p*q，其中 p 和 q 是素数），这似乎就会发生。我现在浏览了一下 Whosebug，发现 RSA 算法无法正确解密大于 'n' 的消息。但就我而言，它无法解密接近 'n' 的消息。如果 n=35 并且我的输入数字（encrypt/decrypt 的数字）是 32，尽管 32 低于 35（但适用于 31、30 ... 虽然），但程序无法正确地将其解密回 32。为什么？

代码：

import math

def isPrime(n):
    if n>=2:
        for m in range(2, int(math.sqrt(n)+1)):
            if n%m == 0:
                return False
        return True
    else:
        return False   

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x


def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount

def findPubE(n, phiN):
    for e in range(3, n, 2):
        if gcd(e,phiN)==1:
            return e
    else:
        raise AssertionError("cannot find 'e'")


def multiplicative_inverse(a, b):
    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
    """
    # r = gcd(a,b) i = multiplicitive inverse of a mod b
    #      or      j = multiplicitive inverse of b mod a
    # Neg return values for i or j are made positive mod b or a respectively
    # Iterateive Version is faster and uses much less stack space
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a  # Remember original a/b to remove
    ob = b  # negative values from return results
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lx) = ((lx - (q * x)), x)
        (y, ly) = ((ly - (q * y)), y)
    if lx < 0:
        lx += ob  # If neg wrap modulo orignal b
    if ly < 0:
        ly += oa  # If neg wrap modulo orignal a
    # return a , lx, ly  # Return only positive values
    return lx

def encrypt(m,e,n):
    return (m^(e)) % n

def decrypt(M, d):
    return M^(d)




def main():
    p=int(input("Input first prime number (p): "))
    q=int(input("Input second prime number (q): "))
    n=p*q
    print("n = ",n)
    msg= int(input("Input message: "))
    assert msg < n
    phiN=(p-1)*(q-1)
    e = findPubE(n,phiN)
    d = multiplicative_inverse(e,phiN)
    encryptedMsg = encrypt(msg,e,n)
    decryptedMsg = decrypt(encryptedMsg,d)



    assert isPrime(p) and isPrime(q)

    print("phi(n) = ",phiN)
    print("e = ",e)
    print("d = ",d)
    print("Encrypted message: ",encryptedMsg)
    print("Decrypted message: ",decryptedMsg)


main()

Answer 1

解决了！我在代码中犯了两个小错误。第一个是我假设“^”符号表示 Python 中的 "to the power of"（正确的符号是“**”），第二个是我忘记添加 "mod n"我的 decrypt() 函数中的行（所以 return M**(d) % n 而不是 return M^(d)）。

Python - RSA解密不return原始消息（很简单，短程序）

Python - RSA decryption does not return original message (very simple, short program)

encryption

cryptography

rsa