Załóżmy, iż dysponujemy superszybkim komputerem, który jest w stanie sprawdzić podzielność miliarda dużych liczb w ciągu jednej sekundy. Aby złamać szyfr RSA należy rozbić klucz publiczny na dwie liczby pierwsze będące jego dzielnikami. Znajomość tych liczb pozwala rozszyfrować każdą informację zakodowaną kluczem prywatnym i publicznym.
Brzmi dosyć prosto. Jednakże nie ma prostej metody rozbijania dużych liczb na czynniki pierwsze. Nie istnieje żaden wzór, do którego podstawiamy daną liczbę i w wyniku otrzymujemy wartości jej czynników pierwszych. Należy je znaleźć testując podzielność kolejnych liczb.
Z rozważań o liczbach pierwszych wynika, iż w przypadku dwóch różnych dzielników pierwszych jeden musi leżeć poniżej wartości pierwiastka z danej liczby, a drugi powyżej (dlaczego?). Zatem, aby go znaleźć musimy wyliczyć pierwiastek z rozkładanej liczby, a następnie testować podzielność przez liczby nieparzyste leżące poniżej tego pierwiastka.
Statystycznie poszukiwany czynnik pierwszy powinien znajdować się w górnej połówce zakresu od 2 do pierwiastka z n. Ile działań musimy wykonać? Policzmy.
Klucz 128 bitowy. Pierwiastek jest liczbą 64 bitową. W zakresie od 2 do 264 co druga liczba jest nieparzysta, zatem jest ich około
zajmie to około:
262 / 109 = 4611686018 sekund = 76861433 minut = 1281023 godzin = 53375 dni = 146 lat
Czy sądzisz, że ktoś będzie czekał przez prawie dwa życia na złamanie szyfru? Zatem można podać do publicznej wiadomości liczbę będącą iloczynem dwóch dużych liczb pierwszych i mieć prawie pewność, iż nikt jej nie rozbije na czynniki pierwsze w rozsądnym czasie. Ostatecznie zamiast 128 bitów możemy zwiększyć klucz do np. 1024 bitów, a wtedy czas łamania szyfru liczy się miliardami miliardów... miliardów lat.
Algorytm RSA składa się z trzech podstawowych kroków:
- Generacja klucza publicznego i tajnego. Klucz publiczny jest przekazywany wszystkim zainteresowanym i umożliwia zaszyfrowanie danych. Klucz tajny umożliwia rozszyfrowanie danych zakodowanych kluczem publicznym. Jest trzymany w ścisłej tajemnicy.
- Użytkownik po otrzymaniu klucza publicznego, np. poprzez sieć Internet, koduje za jego pomocą swoje dane i przesyła je w postaci szyfru RSA do adresata dysponującego kluczem tajnym, np. do banku, firmy komercyjnej, tajnych służb. Klucz publiczny nie musi być chroniony, ponieważ nie umożliwia on rozszyfrowania informacji - proces szyfrowania nie jest odwracalny przy pomocy tego klucza. Zatem nie ma potrzeby jego ochrony i może on być powierzany wszystkim zainteresowanym bez ryzyka złamania kodu.
- Adresat po otrzymaniu zaszyfrowanej wiadomości odczytuje ją za pomocą klucza tajnego.
- Znajdź dwie duże liczby pierwsze (mające np. po 1024 bity). Oznacz je jako p i q. Istnieją specjalne algorytmy generujące duże liczby pierwsze.
Oblicz:
Ø = (p - 1) • (q - 1)
oraz
n = p • qWygenerowane liczby pierwsze usuń, aby nie wpadły w niepowołane ręce. Ø to tzw. funkcja Eulera, n jest modułem.
- Wykorzystując odpowiednio algorytm Euklidesa znajdź liczbę e, która jest względnie pierwsza z wyliczoną wartością funkcji Eulera Ø
- Oblicz liczbę odwrotną modulo Ø do liczby e, czyli spełniającą równanie
d •e mod Ø = 1 . - Klucz publiczny jest parą liczb (e, n), gdzie e nazywa się publicznym wykładnikiem.
- Klucz tajny to (d, n), gdzie d nazywa się prywatnym wykładnikiem. Klucz ten należy przechowywać pod ścisłym nadzorem.
- Otrzymujesz od adresata klucz publiczny w postaci pary liczb (e, n).
- Wiadomość do zaszyfrowania zamieniasz na liczby naturalne t, które muszą spełniać nierówność
0 < style="font-style: normal;"> <> - Na tak otrzymanych liczbach wykonujesz operację szyfrowania i otrzymujesz liczby
c = t e mod n. - Liczby c są zaszyfrowaną postacią liczb t i przekazuje się je adresatowi wiadomości. Klucz (e, n) umożliwił ich zaszyfrowanie, lecz nie pozwala ich rozszyfrować.
- Jesteś adresatem zaszyfrowanych wiadomości. Wcześniej wszystkim korespondentom przesłałeś wygenerowany klucz publiczny (e,n), za pomocą którego mogą oni szyfrować i przesyłać ci swoje dane. Otrzymujesz więc zaszyfrowaną wiadomość w postaci liczb naturalnych c, które muszą spełniać warunek:
0 < style="font-style: normal;"><> - Liczbę c przekształcasz na pierwotną wartość t stosując wzór:
t = c d mod n - Z otrzymanej liczby t odtwarzasz wg ustalonego systemu znaki tekstu. Teraz możesz odczytać przesłaną wiadomość.
import random
import os
def cls():
os.system("cls")
def Czekaj():
raw_input("Zapisz te dane i nacisnij Enter")
# Funkcja obliczająca NWD dla dwóch liczb
def nwd(a, b):
while b: a, b = b, a % b
return a
# Funkcja obliczania odwrotności modulo n
def odwr_mod(a, n):
p0, p1, a0, n0 = 0, 1, a, n
q, r = n0 // a0, n0 % a0
while r:
t = p0 - q * p1
if t >= 0:
t = t % n
else:
t = n - ((-t) % n)
p0, p1, n0, a0 = p1, t, a0, r
q, r = n0 // a0, n0 % a0
return p1
# Procedura generowania kluczy RSA
def klucze_RSA():
tp = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
cls()
print "Generowanie kluczy RSA"
p = q = 0
while p == q:
p, q = tp[random.randint(0, 9)], tp[random.randint(0, 9)]
phi, n = (p - 1) * (q - 1), p * q
e = 3
while nwd(e, phi) != 1: e += 2
d = odwr_mod(e, phi)
print "KLUCZ PUBLICZNY"
print "wykladnik e = %4d" % e
print " modul n = %4d" % n
print "KLUCZ PRYWATNY"
print "wykladnik d = %4d" % d
Czekaj()
# Funkcja oblicza modulo potęgę podanej liczby
def pot_mod(a, w, n):
pot, wyn, q = a, 1, w
while q:
if (q % 2) == 1: wyn = (wyn * pot) % n
pot = (pot * pot) % n
q //= 2
return wyn
# Kodowania danych RSA
def kodowanie_RSA():
cls()
print "Kodowanie danych RSA"
e = int(raw_input("Podaj wykladnik = "))
n = int(raw_input(" Podaj modul = "))
print "----------------------------------"
t = int(raw_input("Podaj kod RSA = "))
print "Wynik kodowania =", pot_mod(t, e, n)
Czekaj()
w = 1
while w:
print "[ 0 ] - Koniec"
print "[ 1 ] - Generowanie kluczy RSA"
print "[ 2 ] - Kodowanie RSA"
w = int(raw_input("Jaki jest twoj wybor? (0, 1 lub 2) : "))
if w == 1: klucze_RSA()
elif w == 2: kodowanie_RSA()
2 komentarze:
Bardzo fajnie napisane. Jestem pod wrażeniem i pozdrawiam.
Bardzo fajnie napisane. Jestem pod wrażeniem i pozdrawiam.
Prześlij komentarz