RSA 加密 python 不适用于小素数

Question

我已经实现了适用于值 p,q,d = 61,53,17 的 RSA 加密和解密代码。我采用了维基百科中提到的这些值。我相信 p 和 q 应该是质数，并且选择 d 使得 d 和 phi(n) 互质。

如果我将值更改为 p,q,d = 3,17,19，我的解密将不起作用。你能帮我解决这个问题吗？这是我的代码：

#!/usr/bin/python3
# -*- coding: utf-8 -*-

def main():
    str = 'computer'
    p,q,d = 61,53,17
    #p,q,d = 3,17,19
    cipher_text = list()
    plain_text = list()

    for c in str:
        cipher_char = EncryptCharRSA(c, p, q ,d)
        cipher_text.append(cipher_char)


    for x in cipher_text:
        plain_char = DecryptCharRSA(x, p, q, d)    
        plain_text.append(plain_char)

    print ('Original Message: ', str)

    print ('Encrypted Message(UTF-8 Unicode characters) : ', end='')
    for element in cipher_text:
        print(element,end = '')

    print ('\nDecrypted Message: ', end='')
    for element in plain_text:
        print(element,end='')

def EncryptCharRSA(msg , p, q, d):
    n = p * q
    phi = (p-1) * (q-1)            
    cipher_no = 0
    cipher_char = ''

    for c in msg:
        # conver char to ascii for calculation
        cipher_no = (ord(c)** d) % n
        cipher_char = chr(cipher_no) 
        return cipher_char   
        #print (cipher_no)
        #plain_no = (cipher_no ** d) % n

def DecryptCharRSA(msg,p, q,d):
    n = p * q
    phi = (p-1) * (q-1)
    e = ModularMultiplicativeInverse(d,phi)
    for c in msg:
        plain_no = (ord(c) ** e) % n
        plain_char = chr(plain_no)
        return plain_char   

# Get modular multiplicative inverse
def ModularMultiplicativeInverse(d,n):
    i = 1
    while True:
        if (d * i) % n == 1:
         return i
        i = i + 1

if __name__ == '__main__' : main()

Answer 1

你所说的d实际上是epublic指数，你所说的e实际上是d私有指数。

撇开命名不谈，您的问题是您正在加密大于或等于 n 的明文字符代码点。如果是，那么您实际上加密的不是 ord("A") (=65)，而是 ord("A") % n。对于小 n 如您的情况，这将导致无法恢复的密文：

>>> n = 3 * 17 # 51
>>> ord("A")
65
>>> ord("A") % n
14

这正是您能够解密的。 RSA 不是可以用来加密任意大数据的东西。通常，您会通过 hybrid encryption.

将它与安全快速的块密码（例如 AES）结合使用

RSA 加密 python 不适用于小素数

RSA encryption python not working with small primes

python

cryptography

rsa

python-3.x

modular-arithmetic