Python 代码生成错误的加密消息

Question

我正在尝试加密消息“Hello World”，然后解密以获得原始消息，但我不断收到另一条消息。不知道哪里导致了这个问题。

def Euclidean_Alg(a, b):
    if not isinstance(a, int) or not isinstance(b, int):
        raise TypeError("Inputs must be integers")
    if a <= 0 or b <= 0:
        raise ValueError("Inputs must be positive integers")
    
    while b != 0:
        a, b = b, a % b
    
    return a

def EEA(a, b):
    if not isinstance(a, int) or not isinstance(b, int):
        raise TypeError("Inputs must be integers")
    if a <= 0 or b <= 0:
        raise ValueError("Inputs must be positive integers")
    
    if a < b:
        a, b = b, a

    s0, s1 = 1, 0
    t0, t1 = 0, 1

    while b != 0:
        q = a // b
        a, b = b, a % b
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1

    return a, (s0, t0)

def Find_Public_Key_e(p, q):
    if p <= 1 or q <= 1:
        raise ValueError("Inputs must be prime numbers greater than 1")

    n = p * q
    phi_n = (p - 1) * (q - 1)
    
    e = 2
    while e < phi_n:
        if Euclidean_Alg(e, phi_n) == 1 and e != p and e != q:
            break
        e += 1
    
    return n, e

def Find_Private_Key_d(e, p, q):
    if not isinstance(e, int) or not isinstance(p, int) or not isinstance(q, int):
        raise TypeError("Inputs must be integers")
    if p <= 1 or q <= 1:
        raise ValueError("Inputs must be prime numbers greater than 1")
    
    phi_n = (p - 1) * (q - 1)

    gcd, (s, t) = EEA(e, phi_n)
    if gcd != 1:
        raise ValueError("e and phi(n) are not coprime, so the modular inverse does not exist")

    d = s % phi_n

    return d


def Convert_Text(_string):
    return [ord(char) for char in _string]

def Convert_Num(_list):
    return ''.join(chr(i) for i in _list)



def Encode(n, e, message):
    integer_list = Convert_Text(message)
    cipher_text = [pow(char, e, n) for char in integer_list]
    return cipher_text

def Decode(n, d, cipher_text):
    decrypted_values = [pow(char, d, n) for char in cipher_text]
    original_message = Convert_Num(decrypted_values)
    return original_message



if __name__ == "__main__":
    # Key generation
    p = 61
    q = 53
    n, e = Find_Public_Key_e(p, q)
    d = Find_Private_Key_d(e, p, q)

    print(f"Public Key (n, e): ({n}, {e})")
    print(f"Private Key (n, d): ({n}, {d})")

    # Encode the message
    message = "Hello, World!"
    cipher_text = Encode(n, e, message)
    print("Encoded message:", cipher_text)

    # Decode the message
    decoded_message = Decode(n, d, cipher_text)
    print("Decoded message:", decoded_message)

这就是运行后的结果。

公钥 (n, e): (3233, 7) 私钥（n，d）：（3233, 3） 编码消息：[1087, 3071, 1877, 1877, 3183, 1129, 2774, 1298, 3183, 1797, 1877, 2872, 2417] 解码消息： дజौौп౻୥!п઱ौ˟ઝ

我尝试了上面的代码并生成了此消息

公钥 (n, e): (3233, 7) 私钥（n，d）：（3233, 3） 编码消息：[1087, 3071, 1877, 1877, 3183, 1129, 2774, 1298, 3183, 1797, 1877, 2872, 2417] 解码消息： дజौौп౻୥!п઱ौ˟ઝ

Answer 1

您的 RSA 加密和解密问题在于所选的公钥和私钥。具体来说，您的代码中计算的 d（私钥指数）值不正确。当 e 的值选择不正确或 d（e 模 φ(n) 的模逆）计算不正确时，经常会出现此问题。

def Euclidean_Alg(a, b):
if not isinstance(a, int) or not isinstance(b, int):
    raise TypeError("Inputs must be integers")
if a <= 0 or b <= 0:
    raise ValueError("Inputs must be positive integers")

while b != 0:
    a, b = b, a % b

return a

def EEA(a, b):
if not isinstance(a, int) or not isinstance(b, int):
    raise TypeError("Inputs must be integers")
if a <= 0 or b <= 0:
    raise ValueError("Inputs must be positive integers")

if a < b:
    a, b = b, a

s0, s1 = 1, 0
t0, t1 = 0, 1

while b != 0:
    q = a // b
    a, b = b, a % b
    s0, s1 = s1, s0 - q * s1
    t0, t1 = t1, t0 - q * t1

return a, (s0, t0)

def Find_Public_Key_e(p, q):
if p <= 1 or q <= 1:
    raise ValueError("Inputs must be prime numbers greater than 1")

n = p * q
phi_n = (p - 1) * (q - 1)

e = 2
while e < phi_n:
    if Euclidean_Alg(e, phi_n) == 1 and e != p and e != q:
        break
    e += 1

return n, e

def Find_Private_Key_d(e, p, q):
if not isinstance(e, int) or not isinstance(p, int) or not isinstance(q, int):
    raise TypeError("Inputs must be integers")
if p <= 1 or q <= 1:
    raise ValueError("Inputs must be prime numbers greater than 1")

phi_n = (p - 1) * (q - 1)

gcd, (s, t) = EEA(e, phi_n)
if gcd != 1:
    raise ValueError("e and phi(n) are not coprime, so the modular inverse does not exist")

d = s % phi_n

if d < 0:
    d += phi_n

return d


def Convert_Text(_string):
return [ord(char) for char in _string]

def Convert_Num(_list):
return ''.join(chr(i) for i in _list)



def Encode(n, e, message):
integer_list = Convert_Text(message)
cipher_text = [pow(char, e, n) for char in integer_list]
return cipher_text

def Decode(n, d, cipher_text):
decrypted_values = [pow(char, d, n) for char in cipher_text]
original_message = Convert_Num(decrypted_values)
return original_message



if __name__ == "__main__":
# Key generation
p = 61
q = 53
n, e = Find_Public_Key_e(p, q)
d = Find_Private_Key_d(e, p, q)

print(f"Public Key (n, e): ({n}, {e})")
print(f"Private Key (n, d): ({n}, {d})")

# Encode the message
message = "Hello, World!"
cipher_text = Encode(n, e, message)
print("Encoded message:", cipher_text)

# Decode the message
decoded_message = Decode(n, d, cipher_text)
print("Decoded message:", decoded_message)

希望这会有所帮助。