python - RSA实现解密/加密

Question

我正在尝试实现 RSA。但我对此有一些问题。我正在尝试用 2 个素数加密一个字符串。

p= 1606938044258990275541962092341162602522202993782792835301611
q= 3213876088517980551083924184682325205044405987565585670603103

首先，我做了 RSA 算法必须做的事情。在我加密字符串后，我也尝试解密它。但结果是这样的:ÜŞϟʐͶz̽ć

def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

def genKeypair(p, q):

    n = p * q
    phiN = (p - 1) * (q - 1)
    e = 65537

    d = egcd(phiN, e)
    return n, e, d


# encrypt message and return cipher
def encrypt(m, n, e):
    m1 = ""
    # Turn message string into ascii so it can be used for encryption
    for x in range(len(m)):
        m1 += '{0:03}'.format(ord(m[x]))
    # encrypt
    c = squareAndMultiply(int(m1), e, n)
    print(c)
    return c


# decrypt cipher and return message
def decrypt(c, n, d):
    # decrypt c
    m = squareAndMultiply(c, d, n) #% n
    # put decryption result into ascii format and use ascii to decode it
    m = str(m)
    tmp = ""
    message = ""
    i = 0
    if int(m[0] + m[1] + m[3]) > 255:
        m = "0" + m
    for x in range(len(m)):
        tmp = tmp + m[x]
        i += 1
        if i % 3 == 0:
            message += chr(int(tmp))
            tmp = ""
    return message

我的平方和乘法方法如下所示:

def squareAndMultiply(x, n, m=0):

# turn exponent into binary
bin = '{0:b}'.format(n)
r = x

# loop through the string representing the binary form of the exponent while ignoring the leftmost bit and perform
# the appropriate operations on r
for i in range(1, len(bin)):
    if (bin[i] == "0"):
        r *= r % m
    else:
        r *= r % m
        r *= x % m

# check for m being greater than 0, ignore it otherwise
if (m > 0):
    return r % m
else:
    return r

有谁知道什么可能是错误的以及必须更改什么，以便解密给出正确的答案？

Answer 1

在代码中，明文通过每个字符对应的十进制 ASCII 代码(格式为三位数字)编码为字符串，例如

ABCDEF -> 065066067068069070

然后，将字符串转换为整数m，用作消息并根据

进行加密

这个概念导致 m 随着明文长度的增加而变得越来越大。在某些时候 m 违反了 m < n 条件 并且算法失败(参见 RSA, Operation )!

算法失败的明文长度取决于 n，可以按如下方式确定: 在示例中，n 是 121 位数字。因为 121/3 = 40.33... ，在不违反 40 条件的情况下最多可以加密 m < n 字符，即从 incl 开始。 41 加密一般会失败。这可以通过以下代码进行验证:

p = 1606938044258990275541962092341162602522202993782792835301611
q = 3213876088517980551083924184682325205044405987565585670603103

n = p * q
phiN = (p - 1) * (q - 1)
e = 65537
d = egcd(phiN, e)[2]

encrypted = encrypt('0123456789012345678901234567890123456789', n, e);      # will succeed
#encrypted = encrypt('01234567890123456789012345678901234567890', n, e);    # will fail
decrypted = decrypt(encrypted, n, d);
print('>' + decrypted + '<')

解决这个问题的一个可能的解决方案是将明文分成具有相同字符数的 block (最后一个 block 通常包含较少的字符)。该数字应对应于最大可能的字符数，以便不违反 m < n 条件(= 发布示例中的 40)。然后每个 block 都被单独编码和加密(与之前的方式相同)。