python - 为什么我的 RSA 代码中的加密/解密不起作用？

Question

我目前正在为学校的一个项目编写一个简化的 RSA 算法，但无法让它发挥作用。

我的代码基于公式 c = m^e(mod N) 和 (c^d)mod N。加密函数可以产生看起来可行的输出，但是当我将其放入解密函数时，它要么无法正确返回消息，要么给出以下错误:

ValueError: chr() arg not in range(0x110000)

我的代码:

import random
import math

def is_prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x % i == 0:
            return False
            break
    return  True

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

def generate_p_and_q(p,q):
    p_and_q = []
    p_and_q.append(p)
    p_and_q.append(q)
    return p_and_q

def generate_phi(p,q):
    p_and_q = generate_p_and_q(p,q)
    phi = (p_and_q[0] - 1)*(p_and_q[1] - 1)
    return phi

def generate_N(p,q):
    p_and_q = generate_p_and_q(p,q)
    N = (p_and_q[0])*(p_and_q[1])
    return N

def generate_e(p,q):
    phi = generate_phi(p,q)
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    for i in lines:
        if int(i) > 1 and int(i)< phi:
                if gcd(int(i), phi) == 1:
                    e = int(i)
                    break
    return e

def encrypt_RSA():
    encrypted = []
    message = input("Enter a message to encrypt:")
    message.lower()
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    valid = False
    choice = input("Do you want to: \nA: enter a key \nB: use a random key?\n")
    if choice.lower() == 'a':
        p = int(input("Enter a key - this must be a prime number between 0 and 500:"))
        q = int(input("Enter a key - this must be a prime number between 0 and 500:\n"))
        while valid != True:
            valid = is_prime(p) and is_prime(q)
            if valid == False:
                print("Your numbers were not prime!")
                p = int(input("Enter a key - this must be a prime number between 0 and 500:"))
                q = int(input("Enter a key - this must be a prime number between 0 and 500:\n"))
    else:
        x = random.randint(0, 499)
        y = random.randint(0, 499)
        p = int(lines[x])
        q = int(lines[y])
    generate_p_and_q(p,q)
    e = generate_e(p,q)
    N = generate_N(p,q)
    for char in message:
        encrypted.append((ord(char) ** e) % N)
    result = ''
    for i in encrypted:
        result = result + str(i)
    print("encrypted message: " + result)
    info = [encrypted, N, e]
    return (info)
encrypt_RSA()


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def calculate_d(a,m):
    g,x,y = egcd(a,m)
    if g != 1:
        return None
    else:
        return x%m

def calculate_phi(N):
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    for num in lines:
        if N%int(num) == 0:
            p = int(num)
            q = N/int(num)
    phi = (p-1)*(q-1)
    return int(phi)

def decrypt_RSA():
    encrypted = encrypt_RSA()
    encrypted_message, N, e = encrypted[0], encrypted[1], encrypted[2]
    print(N)
    phi = calculate_phi(N)
    d = calculate_d(phi,e)
    print("D: " + str(d))
    message = []
    encrypted_message = (encrypted[0])
    for c in encrypted_message:
        m = (c**d) % N
        print(m)
        message.append(chr(m))
    print(message)


decrypt_RSA()

我需要代码首先使用加密函数对消息进行加密，然后使用解密函数对其进行解密，因此应该显示加密的消息和原始消息。

有人可以告诉我我的代码有什么问题吗(因为我还在上学，可能需要简化)，任何额外的反馈将不胜感激。

Answer 1

经过一番调试后，问题是函数 calculate_d() 似乎没有计算出正确的数字。当我们反转函数之一的参数时，问题就解决了。更改此行

d = calculate_d(phi, e)

对此:

d = calculate_d(e, phi)

这对我有用。

<小时/>

此外，由于您询问了改进代码的建议，我做了一些(很多)改进。一些想法:

1. 我用素数生成器替换了读取素数文件的部分，但这只是因为我手头没有该文件。选择您最喜欢的。
2. 调用 if __name__ == '__main__': 内的主要函数。了解它 here .
3. 我将输入提示移至加密代码之外。根据需要实现这些部分(随机或提示用户输入)，然后将结果传递给函数进行加密。

我的版本:

def generate_primes():
    """
    Generate an infinite sequence of prime numbers.

    Sieve of Eratosthenes
    Code by David Eppstein, UC Irvine, 28 Feb 2002
    http://code.activestate.com/recipes/117119/
    https://stackoverflow.com/a/568618/9225671
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiples of its witnesses to prepare for larger
            # numbers
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

def choose_p_and_q():
    p_i = random.randint(0, 100)
    q_i = random.randint(0, 100)
    p = 0
    q = 0
    for i, n in enumerate(generate_primes()):
        if i <= p_i:
            p = n
        if i <= q_i:
            q = n

        if i > p_i and i > q_i:
            break

    return p, q

def generate_n(p, q):
    return p * q

def generate_phi(p, q):
    return (p - 1) * (q - 1)

def generate_e(phi):
    e = None

    for n in generate_primes():
        if math.gcd(n, phi) == 1:
            e = n

        if n >= phi:
            if e is None:
                raise ValueError('no suitable prime number found; reached {}'.format(n))

            # return the highest prime number found
            return e

def find_p_and_q_from_n(n):
    for i in generate_primes():
        if n % i == 0:
            p = i
            q, remainder = divmod(n, p)
            if remainder == 0:
                return p, q

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def calculate_d(phi, e):
    g, x, _ = egcd(phi, e)
    if g == 1:
        return x % e

    raise ValueError('no modular multiplicative inverse found')

def encrypt_rsa(msg):
    p, q = choose_p_and_q()
    n = generate_n(p, q)
    phi = generate_phi(p, q)
    e = generate_e(phi)
    print()
    print('ENCRYPT')
    print('p   ', p)
    print('q   ', q)
    print('n   ', n)
    print('phi ', phi)
    print('e   ', e)

    encrypted_list = []
    for char in msg:
        m = (ord(char) ** e) % n
        encrypted_list.append(m)

    print('msg           ', list(msg))
    print('encrypted_list', encrypted_list)

    return encrypted_list, n, e

def decrypt_rsa(encrypted_list, n, e):
    p, q = find_p_and_q_from_n(n)
    phi = generate_phi(p, q)
    d = calculate_d(e, phi)
    print()
    print('DECRYPT')
    print('p   ', p)
    print('q   ', q)
    print('n   ', n)
    print('phi ', phi)
    print('e   ', e)
    print('d   ', d)

    decrypted_list = []
    for elem in encrypted_list:
        m = (elem**d) % n
        decrypted_list.append(chr(m))

    print('decrypted_list', decrypted_list)

if __name__ == '__main__':
    msg = input('Enter a message to encrypt:').strip()

    data = encrypt_rsa(msg)
    decrypt_rsa(*data)