Python pow () возвращает неправильный ответ - PullRequest
Новая
       10

Python pow () возвращает неправильный ответ

0 голосов
/ 06 ноября 2018

Я создаю базовую программу шифрования RSA без использования библиотеки RSA, которая принимает секретное сообщение, преобразует каждый символ в строке в его значение ASCII, шифрует с помощью открытого ключа и объединяет значения, а затем расшифровывает его с помощью частного ключ и возвращает его в строку.

Все по принципу cipher = pow(plain,e,n) и plain = pow(cipher,d,n). Моя проблема заключается в том, что когда числа становятся очень большими, когда мне нужно, чтобы d и n были минимальными 16 цифрами, функция pow(), по-видимому, приводит к ошибке в вычислениях, которая дает значение ASCII, выходящее за пределы диапазона преобразовать в персонажа. Я изо всех сил пытался выяснить, где я иду не так уже несколько дней. Любая помощь приветствуется. Код ниже: 

from random import randrange, getrandbits

def is_prime(n, k=128):
    # Test if n is not even.
    # But care, 2 is prime !
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    # find r and s
    s = 0
    r = n - 1
    while r & 1 == 0:
        s += 1
        r //= 2
    # do k tests
    for q in range(k):
        a = randrange(2, n - 1)
        x = pow(a, r, n)
        if x != 1 and x != n - 1:
            j = 1
            while j < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    return False
                j += 1
            if x != n - 1:
                return False

    return True

def generate_prime_candidate(length):
    # generate random bits
    p = getrandbits(length)
    #p = randrange(10**7,9*(10**7))
    # apply a mask to set MSB and LSB to 1
    p |= (1 << length - 1) | 1

    return p

def generate_prime_number(length=64):
    p = 4
    # keep generating while the primality test fail
    while not is_prime(p, 128):
        p = generate_prime_candidate(length)
    return p

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

def generate_keypair(p, q):
    n = p * q

    #Phi is the totient of n
    phi = (p-1) * (q-1)

    #Choose an integer e such that e and phi(n) are coprime
    e = randrange(1,65537)

    g = gcd(e, phi)
    while g != 1:
        e = randrange(1,65537)
        g = gcd(e, phi)

    d = multiplicative_inverse(e, phi)
    return ((e, n), (d, n))

def multiplicative_inverse(e, phi):
    d = 0
    k = 1
    while True:
        d = (1+(k*phi))/e
        if((round(d,5)%1) == 0):
            return int(d)
        else:
            k+=1

def encrypt(m,public):
    key, n = public
    encrypted = ''
    print("Your original message is: ", m)
    result = [(ord(m[i])) for i in range(0,len(m))]
    encryption = [pow(result[i],key,n) for i in range(0,len(result))]
    for i in range(0,len(encryption)):
        encrypted = encrypted + str(encryption[i])
    #encrypted = pow(int(encrypted),key,n)
    print("Your encrypted message is: ", encrypted)
    #return result,encrypted
    return encrypted, encryption

def decrypt(e,c,private):
    key, n = private
    print("Your encrypted message is: ", c)
    print(e)
    decryption = [pow(e[i],key,n) for i in range(0,len(e))]
    print(decryption)
    result = [chr(decryption[i])for i in range(0,len(decryption)) ]
    decrypted = ''.join(result)
    print("Your decrypted message is: ",decrypted)
    return result,decrypted

def fastpow(x,y,p):
    res = 1
    x = x%p

    while(y>0):
        if((y&1) == 1):
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res



message = input("Enter your secret message: ")
p1 = generate_prime_number()
p2 = generate_prime_number()
public, private = generate_keypair(p1,p2)
print("Your public key is ", public)
print("Your private key is ", private)
encrypted,cipher = encrypt(message,public)
decrypt(cipher,encrypted,private)

Traceback: 

 File "<ipython-input-281-bce7c44b930c>", line 1, in <module>
   runfile('C:/Users/Mervin/Downloads/group2.py', wdir='C:/Users/Mervin/Downloads')

 File "C:\Users\Mervin\Anaconda3\lib\site-packages\spyder\util\site\sitecustomize.py", line 705, in runfile
   execfile(filename, namespace)

 File "C:\Users\Mervin\Anaconda3\lib\site-packages\spyder\util\site\sitecustomize.py", line 102, in execfile
   exec(compile(f.read(), filename, 'exec'), namespace)

 File "C:/Users/Mervin/Downloads/group2.py", line 125, in <module>
   decrypt(cipher,encrypted,private)

 File "C:/Users/Mervin/Downloads/group2.py", line 100, in decrypt
   result = [chr(decryption[i])for i in range(0,len(decryption)) ]

 File "C:/Users/Mervin/Downloads/group2.py", line 100, in <listcomp>
   result = [chr(decryption[i])for i in range(0,len(decryption)) ]

OverflowError: Python int too large to convert to C long

1 Ответ

0 голосов
/ 07 ноября 2018

Ваш метод multiplicative_inverse неверен. Я не уверен, что вы делаете в этом методе с круглым методом и делением с плавающей запятой, но даже если вы правильно выполнили эту часть, она все равно будет слишком медленной, требуя O (φ) шагов. Обычный метод вычисления модульных мультипликативных инверсий представляет собой адаптацию расширенного евклидова алгоритма , который выполняется в O (log (φ) 2 ) шагов. Вот прямое сопоставление psuedocode из статьи Wikipedia с кодом Python 3: 

def multiplicative_inverse(a, n):
    t, newt = 0, 1
    r, newr = n, a
    while newr:
        quotient = r // newr
        t, newt = newt, t - quotient * newt
        r, newr = newr, r - quotient * newr
    if r > 1:
        raise ZeroDivisionError("{} is not invertible".format(a))
    if t < 0:
        t = t + n
    return t
...