Proszę pamiętać, że muszę podkreślić, że przedstawiony tutaj kod i techniki są przeznaczone wyłącznie do celów edukacyjnych i nigdy nie powinny być wykorzystywane w rzeczywistych aplikacjach bez starannego rozważenia i wskazówek ekspertów.

Jednocześnie zrozumienie zasad kryptografii RSA i zbadanie różnych implementacji jest cenne dla celów edukacyjnych, a zrozumienie sposobu kodowania metod szyfrowania i budowania bezpiecznych systemów szyfrowania do praktycznego zastosowania wymaga przestrzegania standardów branżowych, najlepszych praktyk i dokładnych ocen bezpieczeństwa. Nieodpowiednia implementacja lub niewłaściwe wykorzystanie technik kryptograficznych może prowadzić do poważnych luk w zabezpieczeniach, zagrażając poufności i integralności wrażliwych danych.

Jestem pewien, że wielu programistów, zwłaszcza twórców stron internetowych, słyszało o systemie kryptograficznym RSA. RSA to asymetryczny system kryptograficzny, co oznacza, że jeden klucz jest używany do szyfrowania, a drugi do deszyfrowania. Widziałem wiele artykułów wyjaśniających ogólne zasady kryptografii asymetrycznej, ale nie widziałem żadnego, który zawierałby łatwe do zrozumienia wyjaśnienia matematycznych podstaw tych algorytmów, więc postanowiłem napisać ten artykuł.

Wyjaśnienie matematyki stojącej za RSA

Na początek, jak wspomniałem w powyższym akapicie, aby przesłać wiadomość zaszyfrowaną RSA, potrzebne są 2 klucze. Jeden, który może tylko szyfrować i jeden, który może odszyfrować. Niech klucz szyfrowania będzie oznaczony jako e, klucz deszyfrujący będzie oznaczony jako d a wiadomość będzie oznaczona jako m. Kluczową zasadą RSA jest następujące pojęcie:

(m^e)^d ≡ m (mod n)

Trudność znalezienia d, wiedząc e oraz n mogą być bardzo trudne, jeśli liczby te zostaną odpowiednio dobrane (co zostanie wykazane poniżej).

Najpierw jednak musimy wprowadzić kilka nowych pojęć z teorii liczb.

• a ≡ b (mod n) oznacza, że istnieje liczba całkowita x taka, że a + nx = b. Bardziej intuicyjnym wyjaśnieniem jest to, że przypomnienie o a / n jest równe przypomnieniu b / n.
• gcd(a, b) jest największą liczbą, która dzieli obie a i b.
• lcm(a, b) jest najmniejszą liczbą, która jest wielokrotnością obu liczb a i b.
• λ(n) jest liczbą taką, że x^λ(n) ≡ 1 (mod n) dla dowolnego x takich, że gcd(x, n) = 1. Z tego można wywnioskować, że x^a ≡ x^b (mod n) if a ≡ b (mod λ(n))

Generowanie kluczy

Proszę zrobić n = pq gdzie p oraz q są 2 liczbami pierwszymi. Ponieważ λ(p) = p - 1 oraz λ(q) = q - 1 (proszę sprawdzić dowód małego twierdzenia Fermata), λ(n) = (p - 1) * (q - 1).

Teraz musimy rozwiązać ed ≡ 1 (mod λ(n)). e może być pewną liczbą pierwszą (zwykle 65537), a d można obliczyć za pomocą rozszerzonego algorytmu Euklidesa (zostanie napisany i wyjaśniony w sekcji kodu) z równania ed + xλ(n) = gcd(e, λ(n)) (d oraz x są współczynnikami do obliczenia).

pair (e, n) jest używany do szyfrowania ((m^e) % n) i pair (d, n) służy do deszyfrowania ((m^d) % n)

Po obliczeniu kluczy, p i q można wyrzucić. Proszę zauważyć, że bez p i q, znajdując λ(n) oznaczałoby faktoryzację n, co nie jest łatwym problemem do rozwiązania dla wartości n do 2^2048, które są regularnie używane.

Implementacja RSA w Pythonie

Proszę najpierw wymienić procedury i ich kroki:

Generowanie kluczy

• Proszę znaleźć 2 losowe liczby pierwsze, p i q
• Proszę obliczyć n = p * q oraz λ(n) = (p - 1) * (q - 1)
• Marka e równą jakiejś liczbie pierwszej, np. e = 35537
• Proszę obliczyć d z równania ed + λ(n)x = gcd(e, λ(n)) = 1 przy użyciu Rozszerzonego Algorytmu Euklidesowego (od tego momentu będziemy go nazywać eucalg)

Szyfrowanie

• Proszę podzielić wiadomość na sekcje (po 256 bitów, jeśli n wynosi 2048 bitów).
• Każda sekcja (oznaczona jako m) jest szyfrowana jako (m^e) % n

Deszyfrowanie

• Proszę podzielić wiadomość na sekcje, tak samo jak powyżej.
• Każda sekcja (oznaczona jako m) jest odszyfrowywana jako (m^d) % n

Implementacja rozszerzonego algorytmu euklidesowego

Algorytm ten opiera się na fakcie, że jeśli x dzieli zarówno a i b, będzie istniała para współczynników (k, l) takich, że:
a * k + b * l = x
Algorytm znajduje te współczynniki (oraz x) przez wielokrotne odejmowanie mniejszego argumentu od większego, aż mniejszy argument stanie się równy 0. Zamiast wielokrotnego odejmowania, można obliczyć, ile razy b można odjąć od a (k = a // b), a następnie podłożyć b*k. Ta optymalizacja sprawia, że algorytm działa w O(log max(a, b)), co jest znacznie szybsze.
Poniżej znajduje się implementacja algorytmu w Pythonie:

def eucalg(a, b):
     # make a the bigger one and b the lesser one
     swapped = False
     if a < b:
         a, b = b, a
         swapped = True
     # ca and cb store current a and b in form of
     # coefficients with initial a and b
     # a' = ca[0] * a + ca[1] * b
     # b' = cb[0] * a + cb[1] * b
     ca = (1, 0)     cb = (0, 1)
     while b != 0:
         # k denotes how many times number b
         # can be substracted from a
         k = a // b
         # a  <- b
         # b  <- a - b * k
         # ca <- cb
         # cb <- (ca[0] - k * cb[0], ca[1] - k * cb[1])
         a, b, ca, cb = b, a-b*k, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
     if swapped:         
return (ca[1], ca[0])
     else:
         return ca

Proszę zauważyć, że powyższa funkcja może generować liczby ujemne dla współczynników, więc w takim przypadku wszystko, co musimy zrobić, to ustawić d na λ(n) - d.

Implementacja szybkiego potęgowania z modulo

Niektórzy mogą sugerować po prostu użycie (b ** e) % n, ale to podejście nie jest zbyt dobre pod względem czasu i pamięci, ponieważ b ** e mogą być bardzo duże, mimo że potrzebne jest tylko około 2000 ostatnich bitów. Rozwiązaniem jest ponowna implementacja potęgowania poprzez obliczanie modulo po każdym dzieleniu.

Poniższa implementacja potęgowania ma logarytmiczną złożoność czasową. Zamiast iteracji od 1 do e i mnożenie r (wynik) przez b, iteruje od najbardziej znaczącego bitu e do najmniej znaczącego bitu ei na każdym bicie wykonuje r = r*r + bit. Działa to, ponieważ jeśli r równa się b^x i dołącza Pan bit do końca x, nowe x będzie miało postać x * 2 + bit.

def modpow(b, e, n):
     # find length of e in bits
     tst = 1
     siz = 0
     while e >= tst:
         tst <<= 1
         siz += 1
     siz -= 1
     # calculate the result
     r = 1
     for i in range(siz, -1, -1):
         r = (r * r) % n
         if (e >> i) & 1: r = (r * b) % n
     return r

Generowanie kluczy, szyfrowanie i deszyfrowanie

Generowanie kluczy, szyfrowanie i deszyfrowanie zostały wyjaśnione w sekcji matematycznej, a poniższy kod jest po prostu ich implementacją.

def keysgen(p, q):     n = p * q     lambda_n = (p - 1) * (q - 1)     e = 35537     d = eucalg(e, lambda_n)[0]     if d < 0: d += lambda_n        # both private and public key must have n stored with them     return {'priv': (d, n), 'pub': (e, n)} 
def numencrypt(m, pub):     return modpow(m, pub[0], pub[1]) 
def numdecrypt(m, priv):     return modpow(m, priv[0], priv[1])

Testowanie dotychczasowego kodu

Zapisałem kod w pliku o nazwie rsa.py i uruchomiłem następujące polecenie w powłoce Pythona:

>>> import rsa >>> keys = rsa.keysgen(31337, 31357) 
>>> keys {'priv': (720926705, 982634309), 'pub': (35537, 982634309)} 
>>> priv = keys['priv'] 
>>> pub = keys['pub'] 
>>> msg = 80087 >>> enc = rsa.numencrypt(msg, priv)
>>> enc 34604568 
>>> dec = rsa.numdecrypt(enc, pub) 
>>> dec 80087 
>>> 

Wnioski

Pod koniec pisania tego artykułu zdałem sobie sprawę, że implementacja użytecznego programu RSA w Pythonie jest bardziej skomplikowana niż początkowo spekulowałem. Z tego powodu postanowiłem podzielić ten temat na kilka artykułów. Dzięki kodowi przedstawionemu w tym artykule, mają Państwo napisane wszystkie podstawowe części RSA. Wciąż jednak potrzebny jest generator liczb pierwszych i szyfrowanie zwykłego tekstu (numencrypt i numdecrypt są odpowiednie tylko dla liczb m mniejszych niż n). Wszystkie te informacje zostaną zawarte w następnym artykule, który zostanie wkrótce opublikowany.