为什么我在Python中的RSA实现不起作用?

问题描述 投票:2回答:2

出于学习目的,我试图在Python中实现RSA公钥加密。我已经看了一些示例代码,并通过整个stackoverflow搜索,试图找到答案。

我的实现工作不正常,我不知道为什么。

我可以轻松生成公钥和私钥。当我使用公钥进行加密时,我会得到类似的东西

16102208556492

我认为,这看起来是正确的。当我现在尝试解密密文时,它会给我随机的ASCII符号。所以我认为解密肯定是错的,但它看起来也很不错。

从我试图找到错误估计的几天!

我开始研究的是Darrel Hankerson,Alfred Menezes和Scott Vanstone所着的“椭圆曲线密码学指南”一书中的数学算法。

Algorithm 1.1: RSA key pair Generation

INPUT: Security parameter l
OUTPUT: RSA public key e, private key d and n
1. Randomly select two primes p and q with same bitlength l/2
2. Compute n = pq and phi = (p-1)(q-1)
3. Select an arbitrary integer e with 1 < e < phi and gcd(e, phi)==1
4. Compute the integer d satisfying 1 < d < phi and ed == 1 mod phi
5. Return(n, e, d)

Algorithm 1.2: Basic RSA encryption

INPUT: RSA public key e, n, plaintext m
OUTPUT: Ciphertext c
1. Compute c = m**e mod n
2. Return(c)

Algorithm 1.3: Basic RSA decryption

INPUT: RSA private d, n, ciphertext c
OUTPUT: Plaintext m
1. Compute m = c**d mod n
2. Return(m)

我理解它是如何在数学上工作所以我实现它像这样:

Algorithm 1.1 in Python

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, n)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

Algorithm 1.2 in Python

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

Algorithm 1.3 in Python

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

我在这里编码似乎并不是非常错误,但无论如何,无论是在这里还是在其他功能中都必须是错误的。

Here is my full python code

# RSA

# Imports
import random

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, n)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

def mrt(odd_int):
    odd_int = int(odd_int)
    rng = odd_int - 2
    n1 = odd_int - 1
    _a = [i for i in range(2,rng)]
    a = random.choice(_a)
    d = n1 >> 1
    j = 1
    while((d&1)==0):
        d = d >> 1
        j += 1
    t = a
    p = a
    while(d>0):
        d = d>>1
        p = p*p % odd_int
        if(d&1):
            t = t*p % odd_int
    if(t == 1 or t == n1):
        return True
    for i in range(1,j):
        t = t*t % odd_int
        if(t==n1):
            return True
        if(t<=1):
            break
    return False

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def Randomly_Select_Prime_w_Bitlength(l):
    prime = random.getrandbits(int(l))
    if (prime % 2 == 1):
        if (mrt(prime)):
            return prime
    return Randomly_Select_Prime_w_Bitlength(l)

def Arbitrary_Int_e(phi):
    _e = [i for i in range(1, phi)]
    e = random.choice(_e)
    if(gcd(e, phi) == 1 % phi):
        return e
    return Arbitrary_Int_e(phi)

def inverse(e, phi):
    a, b, u = 0, phi, 1
    while(e > 0):
        q = b // e
        e, a, b, u = b % e, u, e, a-q*u
    if (b == 1):
        return a % phi
    else:
        print("Must be coprime!")    
python algorithm encryption cryptography rsa
2个回答
3
投票

正如Marek Klein在他的评论中所说,我用“错误的参数”调用了“inverse()”函数。这是d = inverse(e, n)而不是d = inverse(e, phi)

但是从逻辑的角度来看,n是公共的,e是公共的,因此如果有效,任何人都可以计算应该是私有的d。

squeamish ossifrage也指出了这一点

Randomly_Select_Prime_w_Bitlength()函数经常生成比所需位数少的数字,有时会产生运行时错误(因为在mrt()中odd_int太小)。如果p和q太小,您将无法加密预期的数据位。

Randomly_Select_Prime_w_Bitlength()现在覆盖一个检查,如果随机素数大于3,那么它就不能通过小于可能的值来返回Runtime-Error。

Here is the corrected code:

# RSA 

# Imports
import random

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d statisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, phi)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

def mrt(odd_int):
    odd_int = int(odd_int)
    rng = odd_int - 2
    n1 = odd_int - 1
    _a = [i for i in range(2,rng)]
    a = random.choice(_a)
    d = n1 >> 1
    j = 1
    while((d&1)==0):
        d = d >> 1
        j += 1
    t = a
    p = a
    while(d>0):
        d = d>>1
        p = p*p % odd_int
        if(d&1):
            t = t*p % odd_int
    if(t == 1 or t == n1):
        return True
    for i in range(1,j):
        t = t*t % odd_int
        if(t==n1):
            return True
        if(t<=1):
            break
    return False

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def Randomly_Select_Prime_w_Bitlength(l):
    prime = random.getrandbits(int(l))
    if (prime % 2 == 1 and prime > 3):
        if (mrt(prime)):
            return prime
    return Randomly_Select_Prime_w_Bitlength(l)

def Arbitrary_Int_e(phi):
    _e = [i for i in range(1, phi)]
    e = random.choice(_e)
    if(gcd(e, phi) == 1 % phi):
        return e
    return Arbitrary_Int_e(phi)

def inverse(e, phi):
    a, b, u = 0, phi, 1
    while(e > 0):
        q = b // e
        e, a, b, u = b % e, u, e, a-q*u
    if (b == 1):
        return a % phi
    else:
        print("Must be coprime!")    

0
投票

有一种更简单的方法在python中实现RSA:

bits = 2048 # the bit length of the rsa key, must be multiple of 256 and >= 1024
E = 65537 # (default) the encryption exponent to be used [int]
from Crypto.PublicKey import RSA
key = RSA.generate(bits,E)
with open('my_key.pem','w') as file:
    file.write(key.exportKey())
    file.write(key.publickey().exportKey())

使用Crypto.PublicKey需要(在Windows CMD或mac TERMINAL中):

pip install pycrypto

对于一些运行python 3的系统(像我的一样):

pip3 install pycrypto

公钥(模数加密指数)和私钥(解密指数)都是base64格式,转换为十六进制用于其他用途:

from base64 import b64decode
base64_string = 'AAAAbbbb123456=='
hex_string = b64decode(base64string).hex()

在彼此之间的短时间内生成的两个密钥可能具有相同的最高有效数字:

MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpLVejQvo2xJwx04Oo2qotAge9 wWQDsk62hb0ua8r9+VM837+cArMStt9BoSTOCmNz7cYUXzGjQUsUi7tnHXM+Ddec EG7J3q/w12ox2QN3wTndsW+GO9BD2EHY674t8A3JLSJP/bcD/FGBtjzytyd5hmQJ Fife8rr4sAMkTXwoIwIDAQAB和(彼此之间约10秒)MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCz9un7Xq248zlmkwVuXze2tUMy a30BaodLJXYuAktGuiMAFwpprql0N9T06HdiphZmr+hT45gG57ZOlJn/yzN4U30Q DXevDVapq6aYJ/Q21CO2bkLkMjEMy5D4IdwMeBgK+5pJFYETB6TzLfDkEcTQMr++ f7EHosWd0iBGm01cKQIDAQAB

© www.soinside.com 2019 - 2024. All rights reserved.