Szyfrowanie RSA i podpis elektroniczny

RSA to najbardziej znany szyfr z kluczem publicznym: klucz do szyfrowania może znać każdy, a odszyfrować wiadomość może tylko właściciel klucza prywatnego. Cały algorytm składa się z trzech poznanych wcześniej elementów: liczb pierwszych, odwrotności modulo (rozszerzony algorytm Euklidesa) i potęgowania modulo (szybkie potęgowanie). Ten sam mechanizm daje podpis elektroniczny.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Prawdziwe klucze RSA mają setki cyfr; tu liczby są małe, żeby każdy krok dało się sprawdzić ręcznie.

Przejdź wyznaczanie kluczy RSA krok po kroku

Klucze RSA i odwrotność modulo

Z liczb pierwszych p = 61 i q = 53 powstaje moduł n = 3233 i fi = 60 · 52 = 3120. Wykładnik publiczny e = 17 nie ma wspólnych dzielników z fi. Wykładnik prywatny d to odwrotność e modulo fi: liczba, dla której e · d daje resztę 1 z dzielenia przez fi. Liczy ją rozszerzony algorytm Euklidesa:

def inverse(e, phi):
    a, b = e, phi
    x, y = 1, 0
    while b != 0:
        q = a // b
        a, b = b, a - q * b
        x, y = y, x - q * y
    return x % phi


p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
d = inverse(e, phi)
print(n, phi, d, e * d % phi)
print(pow(e, -1, phi))

3233 3120 2753 1
2753

W pętli para (a, b) zmienia się jak w zwykłym algorytmie Euklidesa, a x pilnuje, że a daje przy dzieleniu przez fi tę samą resztę co x · e. Na końcu a = 1, więc x · e daje resztę 1. Od Pythona 3.8 to samo liczy pow(e, -1, phi).

Szyfrowanie, odszyfrowanie i podpis

Szyfrowanie to c = mᵉ mod n (klucz publiczny), odszyfrowanie m = cᵈ mod n (klucz prywatny). Podpis działa odwrotnie: s = mᵈ mod n i sprawdzenie sᵉ mod n = m. Wszystko to potęgowanie modulo:

n, e, d = 3233, 17, 2753
message = 65
cipher = pow(message, e, n)
print(cipher, pow(cipher, d, n))

signature = pow(message, d, n)
print(signature, pow(signature, e, n) == message)
print(pow(signature, e, n) == 66)

2790 65
588 True
False

Zmiana wiadomości choćby o 1 sprawia, że podpis przestaje pasować. Dłuższy tekst szyfruje się literami albo blokami: każda liczba musi być mniejsza od n. Szybkie potęgowanie opisuje strona rekurencja i szybkie potęgowanie, a zwykły algorytm Euklidesa: algorytm Euklidesa.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Szyfrowanie, odszyfrowanie i podpis: potęgowanie modulo

Specyfikacja. Dane: liczby naturalne a (wiadomość), n (wykładnik klucza) i m (moduł klucza). Wynik: aⁿ mod m: szyfrogram (klucz publiczny), wiadomość (klucz prywatny) albo podpis.

Lista kroków:

1. Wczytaj a, n i m. Ustaw w = 1 i zastąp a resztą a mod m.
2. Jeśli n = 0, przejdź do kroku 5.
3. Jeśli n jest nieparzyste, zastąp w liczbą (w · a) mod m. Zastąp a liczbą (a · a) mod m.
4. Podziel n całkowicie przez 2 i wróć do kroku 2.
5. Wypisz w.

Pseudokod:

wczytaj a, n, m
w ← 1
a ← a mod m
dopóki n > 0 wykonuj
  jeżeli n mod 2 = 1 to
    w ← (w * a) mod m
  a ← (a * a) mod m
  n ← n div 2
wypisz w

Schemat blokowy:

Odwrotność modulo rozszerzonym algorytmem Euklidesa

Specyfikacja. Dane: liczby naturalne e i fi, NWD(e, fi) = 1 (w RSA fi = (p - 1)(q - 1)). Wynik: liczba d z przedziału 0..fi - 1, dla której (e · d) mod fi = 1 (wykładnik klucza prywatnego).

Lista kroków:

1. Wczytaj e i fi. Ustaw a = e, b = fi, x = 1, y = 0. Przez cały czas a daje przy dzieleniu przez fi tę samą resztę co x · e, a b tę samą co y · e.
2. Jeśli b = 0, przejdź do kroku 5.
3. Oblicz iloraz q = a div b. Zastąp parę (a, b) parą (b, a - q · b), a parę (x, y) parą (y, x - q · y), jak w algorytmie Euklidesa.
4. Wróć do kroku 2.
5. Teraz a = NWD(e, fi) = 1, więc x · e daje resztę 1. Wypisz x mod fi.

Pseudokod:

wczytaj e, fi
a ← e
b ← fi
x ← 1
y ← 0
dopóki b ≠ 0 wykonuj
  q ← a div b
  r ← a - q * b
  a ← b
  b ← r
  t ← x - q * y
  x ← y
  y ← t
wypisz x mod fi

Schemat blokowy:

Najczęstsze błędy

• Liczenie mᵉ, a potem reszty. Przy prawdziwych kluczach potęga ma miliony cyfr. Bierz resztę po każdym mnożeniu (pow(m, e, n)).
• e mające wspólny dzielnik z fi. Wtedy odwrotność modulo nie istnieje i nie da się wyznaczyć klucza prywatnego.
• Ujemny wynik rozszerzonego Euklidesa. Współczynnik x bywa ujemny: na końcu weź x % phi.
• Wiadomość większa od n. Liczba m ≥ n po odszyfrowaniu wraca jako m mod n.

Ćwicz w przeglądarce

W temacie o szyfrowaniu z kluczem publicznym kursu Algorytmy: zakres rozszerzony:

• szyfrowanie i odszyfrowanie,
• podpis elektroniczny,
• odwrotność modulo rozszerzonym algorytmem Euklidesa,
• sprawdzanie podpisów.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Prostszy szyfr z zakresu podstawowego: szyfr Cezara.

Dla nauczycieli

RSA na małych liczbach mieści się w jednej lekcji: uczniowie wyznaczają klucze, wymieniają się kluczami publicznymi i szyfrują sobie wiadomości. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.