1

Тема: Робота з великими цілими числами в Python 3

Порекомендуйте, будь ласка, фреймворк для цього.
Роблю реалізацію RSA, але при 32 бітних числах видає неправильні результати.

2 Востаннє редагувалося koala (24.07.2018 11:08:35)

Re: Робота з великими цілими числами в Python 3

По-перше, не плутайте фреймворк і бібліотеку. Фреймворк - це коли вам дають місця, щоб вписувати код, а бібліотека - це коли ви пишете власний код із бібліотечними плюшками.
По-друге, довга арифметика вбудована в Python.
По-третє, 32 біти - це не довга арифметика, швидше за все ви щось інше не так робите.

3

Re: Робота з великими цілими числами в Python 3

Ось воно:

import secrets

#from wikipedia
def isprime(n):
    if not (n&1) or n % 3 == 0:
        return False
    i = 5
    while i*i <= n:
        if n%i == 0 or n%(i+2) == 0:
            return False
        i+=6
    return True

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

def genrandprime(bits):
    temp = secrets.randbits(bits)
    if not (temp&1):
        temp+=1
    while not isprime(temp):
        temp+=2
    return temp

def keygen(bits):
    p = genrandprime(bits)
    q = genrandprime(bits)
    n = p * q
    phi = (p-1)*(q-1)
    e = 3
    while gcd(e,phi) != 1:
        e += 2
    k = 1
    d = (k*phi+1)/e
    while d % 1 != 0:
        k += 1
        d = (k*phi+1)/e
    return {'priv':{'n':n,'d':int(d)},'pub':{'n':n,'e':e}}

def process(n,k,m):
    return pow(m,k,n)

keys = keygen(32)
print(keys)
print('Encrypting 12345...')
print('-----------------------------------------')
encrypt = process(keys['pub']['n'],keys['pub']['e'],12345)
print('Encrypted:',encrypt)
print('Decrypted:',process(keys['priv']['n'],keys['priv']['d'],encrypt))

Вивід:

{'priv': {'n': 1781291892654952753, 'd': 356258377921443072}, 'pub': {'n': 1781291892654952753, 'e': 5}}
Encrypting 12345...
-----------------------------------------
Encrypted: 1711635699843025145
Decrypted: 1076789031447638973

4 Востаннє редагувалося koala (24.07.2018 12:02:08)

Re: Робота з великими цілими числами в Python 3

ну так у вас же довга арифметика, а ви її в рухому кому пхаєте, звісно точність падає...

    k = 1
    while (k*phi+1)%e != 0:
        k += 1
    d = (k*phi+1)//e

А цей ваш d % 1 != 0 фігню дає:

>>> (1781291892654952753/(1781291892654952753+1))%1==0
True

Про ефективність я взагалі мовчу, ну то таке.

Подякували: /KIT\, leofun012

5

Re: Робота з великими цілими числами в Python 3

Тепер працює, дякую.