Andrzej Majewski

Andrzej Majewski

Bezpieczeństwo Informacji w Internecie i Biznesie

O kluczach publicznych (prawie) wszystko

Ponieważ jest to zagadnienie dosyć obszerne, skupię się na najpowszechniej wykorzystywanym algorytmie RSA i kluczach do niego. Algorytm RSA nazwano od pierwszych liter nazwisk trzech profesorów z MIT z USA, którzy w 1977 opublikowali matematyczne podstawy nowego rodzaju szyfrowania danych. Uczeni ci to Ron L. Rivest, Adi Shamir i Leonard Adleman. RSA to niesymetryczny algorytm szyfrujący, oparty na znanym od dawna problemie matematycznym, jakim jest faktoryzacja, czyli rozkład na czynniki pierwsze dużych liczb.

Algorytm niesymetryczny, czyli taki, w którym do szyfrowania używa się innego klucza niż do rozszyfrowywania. Występuje w nim wiec para kluczy. Ten, który służy do szyfrowania, nazywany jest kluczem publicznym; klucz do rozszyfrowywania nazywany jest kluczem tajnym lub prywatnym.

W algorytmie RSA klucz publiczny to para liczb. Jedna z nich jest mała, druga, ta istotniejsza, ma długość od 512 bitów do ...
W praktyce nie używa się kluczy dłuższych niż 4096 bitów. Przy dłuższych kluczach czas szyfrowania i deszyfrowania bardzo znacząco się wydłuża. Na dzisiaj przyjmuje się, że klucze 2048 bitowe to tzw. military-grade cryptography. Czyli klucze do zastosowań wojskowych. W zastosowaniach cywilnych przeważają klucze 1024-bitowe. Krótsze, chociaż i tak bardzo, bardzo trudne do złamania, uważa się za „niebezpiecznie krótkie” Szeroki uśmiech.

Mówiąc językiem bardziej zrozumiałym i trochę upraszczjąc, klucz publiczny to liczba o 154 - 1233 cyfrach. Ale sama długość jeszcze nie decyduje o "sile" szyfru. Decydujący jest sposób, w jaki wybrano lub wyznaczono tą liczbę. Jak wcześniej wspomniałem siła algorytmu RSA opiera się na trudności obliczeniowej rozkładu iloczynu liczb na czynniki.

Żeby było jeszcze trudniej, liczby, które stanowią materiał wyjściowy do wyznaczenia pary kluczy, to liczby pierwsze, czyli takie, które dzielą się tylko przez 1 i przez siebie (np. 13). Dla liczb 10-cyfrowych sprawdzenie że liczba jest pierwsza, to pestka (dla komputera oczywiście), ale spróbujcie zrobić taki „myk” jeżeli liczba ma 75-80 czy 650 cyfr! Puszczenie oczka

Czytelnicy, którzy edukację kończyli niedawno, wszystko to pamiętają, ale wierzcie mi, w miarę upływu czasu łaskawa pamięć robi sobie miejsce na nowe doznania, a algebra gdzieś tam w niebyt ulatuje... Nie obrażajcie się więc, jeżeli coś wydaje się zbyt oczywiste.

Wracając do naszych kluczy. Zaczynamy wyznaczenie pary kluczy od wybrania dwóch liczb pierwszych o długości ok. ½ rozmiaru przyszłego klucza. Żeby dać szansę całemu światu, czyli wszystkim innym użytkownikom naszego algorytmu, wybieramy te liczby w sposób losowy! Po to, żeby wszyscy inni mieli różne od nas klucze. Inaczej założenie o unikalności klucza prywatnego, czyli że jest jeden taki na świecie, bierze w łeb!

Tu pojawiają się pierwsze dwa poważne problemy praktyczne w implementacji algorytmu RSA.

Po pierwsze: jak losowo znaleźć te olbrzymie liczby i po drugie: jak sprawdzić, że są to rzeczywiście liczby pierwsze? Bezwzględne sprawdzenie pierwszeństwa liczby (sito Erastotenesa) jest zbyt czasochłonne, potrzeba metody szybszej.

Niestety, w życiu często chadzamy na skróty. Tak samo w przypadku generowania kluczy. W praktyce stosowane są pseudolosowe generatory liczb (programy komputerowe). Chociaż nie mówię, że są prymitywne, jednak nie gwarantują, że przy wytwarzaniu wielu par kluczy przez takie same programy np. miliony kopii MS Windows, gdzieś na Świecie klucze się nie powtórzą.

Druga kwestia to pierwszeństwo liczby. Bada się pewien zbiór cech liczby, zaczynając od tego czy jest nieparzysta i na tej podstawie przyjmuje się, ze jest to liczba „wystarczająco pierwsza”.

Tak jak wcześniej napisałem, skuteczność szyfru RSA wynika z trudności rozkładu iloczynu dwóch liczb na składniki pierwsze

Z rozważań o liczbach wynika, iż w przypadku dwóch różnych dzielników pierwszych danej liczby, jeden musi leżeć poniżej wartości pierwiastka z danej liczby, a drugi powyżej. 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. Zróbmy to za pomocą superkomputera, który wykona miliard sprawdzeń w ciągu 1 sekundy

Statystycznie, dla liczby N (iloczynu) poszukiwany czynnik pierwszy powinien znajdować się w górnym przedziale zakresu liczb od 2 do pierwiastka z N. Ile obliczeń musimy wykonać żeby znaleźć czynnik?

Załóżmy dla uproszczenia, że klucz jest tylko 128 bitowy. Pierwiastek jest liczbą 64 bitową. W zakresie od 2 do 264 co druga liczba jest nieparzysta, zatem jest ich około 264/2 = 263. Ponieważ interesuje nas tylko górna połówka tego zakresu liczb, to ilość liczb do sprawdzenia jest dwa razy mniejsza, czyli wynosi 263/2 = 262. Ile czasu zajmie superkomputerowi sprawdzenie podzielności liczby N przez około 262 liczb? Odpowiedź brzmi: maksymalnie 4,611,686,018 sekund, czyli około 146 lat. Statystycznie rzecz ujmująć, bo przecież możemy trafić na właściwą liczbe w pierwszej próbie! 

Zatem można podać do publicznej wiadomości liczbę będącą iloczynem dwóch dużych, losowo wybranych liczb pierwszych i mieć prawie 100% pewność, iż nikt, kto nie dysponuje astronomicznym budżetem, nie rozbije jej na czynniki pierwsze w rozsądnym czasie. Ostatecznie zamiast 128 bitów możemy użyć klucza 1024-bitowego, a wtedy czas łamania szyfru liczy się w erach a nie w latach.

Żeby dłużej się nad tym nie rozwodzić, metoda RSA z kluczami 512-bitowymi byłaby na dzisiaj super bezpieczna, gdyby nie uproszczenia w generowaniu kluczy. Dlatego powszechnie stosujemy klucze 1024-bitowe!

A teraz już trochę na skróty, żeby nie zanudzić Czytelników.

W metodzie RSA klucz publiczny to para liczb (e,n). Klucz prywatny „od pary” to dwie liczby (d,n).

Liczba n, czyli moduł, to iloczyn dwóch bardzo długich liczb pierwszych p i q. Liczba e to tzw. wykładnik publiczny. Wybieramy go z liczb nieparzystych o pewnych cechach względem czynników liczby n. Np. 3, 7, 13 lub 65537.

Liczba d, czyli wykładnik prywatny, jest wyznaczana obliczeniowo z liczb p i q oraz e.

To, co w całej sprawie najważniejsze:

  • e i n podajemy do publicznej wiadomości,
  • d trzymamy w ścisłej tajemnicy!

Co dzięki temu osiągamy?

Każda osoba, która wejdzie w posiadanie klucza publicznego, może nim zaszyfrować dowolną wiadomość. Tylko jedna osoba, która zna klucz prywatny, może ta wiadomość odszyfrować. Nikt nie potrafi w rozsądnym czasie wyznaczyć klucza prywatnego, znając klucz publiczny.

Bazując na tym kanonie możemy stworzyć środowisko, w którym wymieniamy się swobodnie i bez obaw, ze wszystkimi potencjalnymi korespondentami, naszymi kluczami publicznymi. Dzięki temu wszyscy możemy otrzymywać komunikaty od dowolnego nadawcy, czytelne tylko dla jednego odbiorcy – tego który ma klucz prywatny od pary.

Odpowiedzi na inne postawione pytania już wkrótce!

Pozdrawiam Czytelników,

Andrzej J. Majewski




 Blog  Memos



© 2007-2018 Ekademia.pl | Polityka Prywatności | Regulamin


Produkty i Szkolenia Online

Nie jesteś zalogowany(a) Zaloguj się Utwórz konto


forked from Moodle