Klucze RSA

Szyfrowanie z kluczem publicznym i podpis elektroniczny - Algorytmy: zakres rozszerzony (Python)

W szyfrowaniu z **kluczem publicznym** każdy ma dwa klucze. Publiczny (e, n) może znać każdy i służy do szyfrowania, prywatny (d, n) zna tylko właściciel i służy do odszyfrowania. W RSA: - wybieramy dwie liczby pierwsze p i q, n = p * q, - phi = (p - 1) * (q - 1), - e jest względnie pierwsze z phi (NWD(e, phi) = 1), - d to odwrotność e modulo phi: (d * e) % phi == 1. Bezpieczeństwo opiera się na tym, że z n bardzo trudno odtworzyć p i q, gdy są to liczby o setkach cyfr. Tu używamy małych liczb, żeby było widać obliczenia.

from math import gcd

p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
print("n =", n, "phi =", phi, "NWD(e, phi) =", gcd(e, phi))
d = pow(e, -1, phi)
print("klucz publiczny:", (e, n))
print("klucz prywatny:", (d, n))
print("sprawdzenie:", d * e % phi)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.