Тема: Робота з великими цілими числами в Python 3
Порекомендуйте, будь ласка, фреймворк для цього.
Роблю реалізацію RSA, але при 32 бітних числах видає неправильні результати.
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Python → Робота з великими цілими числами в Python 3
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Порекомендуйте, будь ласка, фреймворк для цього.
Роблю реалізацію RSA, але при 32 бітних числах видає неправильні результати.
По-перше, не плутайте фреймворк і бібліотеку. Фреймворк - це коли вам дають місця, щоб вписувати код, а бібліотека - це коли ви пишете власний код із бібліотечними плюшками.
По-друге, довга арифметика вбудована в Python.
По-третє, 32 біти - це не довга арифметика, швидше за все ви щось інше не так робите.
Ось воно:
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
ну так у вас же довга арифметика, а ви її в рухому кому пхаєте, звісно точність падає...
k = 1
while (k*phi+1)%e != 0:
k += 1
d = (k*phi+1)//e
А цей ваш d % 1 != 0 фігню дає:
>>> (1781291892654952753/(1781291892654952753+1))%1==0
True
Про ефективність я взагалі мовчу, ну то таке.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися