Artykuły dotyczące tematu: kryptografia

dodany: 12.03.2013 | tagi: , ,

Klucz publiczny RSA – jak to działa?

2

Większość kryptografii klucza publicznego oparta jest na trudności matematycznej. Równania matematyczne wykorzystywane do tworzenia kluczy publicznych są tak skomplikowane, że nawet jeśli ktoś z ciekawości spojrzał na strony Wikipedii na temat niektórych sposobów szyfrowania, to z pewnością przewraca mu się oczach, w głowie się kręci i nie do końca wie na co patrzy. Postaramy się wyjaśnić w możliwie przystępny sposób w  jak działają takie algorytmy.

 

Przyjrzyjmy się RSA

Nazwa algorytmu wzięła się od pierwszych liter nazwisk twórców – Rona Rivesta, Adi Shamira i Leonarda Adlemana. Opublikowany został w 1977 roku i jest powszechnie używany do dzisiaj. RSA składa się z trzech części:

  • generowania klucza,
  • szyfrowania,
  • i deszyfrowania.

W pierwszym etapie tworzona jest para kluczy – prywatny i publiczny.

Druga część zajmuje się zwykłą wiadomością – używa klucza publicznego odbiorcy i tworzy zaszyfrowaną treść.

Deszyfrowanie zaczyna się od dostarczenia szyfru, następnie używany jest klucz prywatny odbiorcy i uzyskujemy pierwotną wiadomość. Każdy z tych etapów zawiera w sobie trochę problemów matematycznych.

 

Generowanie klucza

Na potrzeby tego przykładu nasz klucz publiczny będzie zawierał dwie wartości: N i E. Klucz prywatny będzie składał się z liczb: N i D. Zabawa z generowaniem klucza zaczyna się od wybrania dwóch różnych liczb pierwszych. Dla ułatwienia naszych obliczeń weźmiemy małe liczby: P=11 i Q=17. (Siła takich algorytmów opiera się na odpowiednio dużych liczbach pierwszych, których odgadnięcie nie będzie zbyt proste).

Teraz musimy policzyć wartość N. Nic trudnego – wystarczy przemnożyć P i Q:

 

N = P*Q

N = 11*17 = 187

 

Dalej do wyliczenia jest funkcja φ (funkcja Eulera) – przypisuje ona każdej liczbie naturalnej ilość liczb względnie z nią pierwszych, nie większych od niej samej. W naszym przypadku sprowadza się to do wzoru (P-1)*(Q-1).

 

φ(N) = (P − 1)(Q − 1)

φ(N) = (11 − 1)(17 − 1)

φ(N) = 160

 

Jako E musimy wybrać liczbę, która pochodzi z przedziału 1 < E < 160 i jest względnie pierwsza do 160. Czyli – liczba E musi spełniać dwa warunki – być większa od 1, ale mniejsza od naszego φ(N) oraz być względnie pierwsza względem 160. Liczba względnie pierwsza to taka, że największy wspólny dzielnik (NWD) z φ(N) i E musi być równy 1.

Spróbujmy z 23. Spełnia pierwszy warunek – jest większa od 1 i jednocześnie mniejsza od 160. A co z drugim? Jedynym dzielnikiem 23 i 160 jest 1, więc są to liczby względnie pierwsze. W takim razie:

 

E = 23

 

Ostatnią wartością, którą musimy wyliczyć jest D. Do wyliczenia tej liczby musimy znaleźć 23-1 = D(mod 160), co jest tym samym co 23D = 1 mod(160). W takim razie potrzebna nam liczba (D), która po przemnożeniu przez 23 i modulo 160 da resztę 1. Najłatwiejszy sposób to po prostu sprawdzanie od zera póki nie otrzymamy odpowiedniej liczby. Są lepsze sposoby na znajdywanie takich liczb, ale są dużo bardziej skomplikowane. Odpowiednią liczbą u nas jest 7.

 

D*23 (mod 160) = 1

7 * 23 = 161

161 mod 160 = 1

D = 7

 

Koniec pierwszej części – mamy nasz klucz publiczny – liczby N i E, oraz klucz prywatny
– N i D.

 

Szyfrowanie

Zakończyliśmy generowanie kluczy. Teraz mamy wszystkie elementy potrzebne do szyfrowania i deszyfrowania wiadomości. W RSA ten proces opiera się na podniesieniu do potęgi i wykonaniu operacji modulo. Jak to wygląda?

 

C = B^E (mod N)

 

Ta funkcja może wyglądać przerażająco na pierwszy rzut oka, ale nie jest wcale taka trudna. Zaczynamy od liczby B i podnosimy ją do potęgi E, następnie liczymy resztę z dzielenia przez N. Wracając do naszego przykładu – naszą wiadomością do zaszyfrowania będzie 42. W takim razie mamy M=42. Wynikiem tego etapu będzie C – nasz szyfr. Nasza funkcja szyfrująca wygląda tak:

 

C = M^E (mod N)

 

Teraz wystarczy tylko podstawić nasze wartości z przykładu i otrzymamy:

 

C = 42^23 (mod 187)

C=168

 

Deszyfrowanie

Teraz mamy zaszyfrowaną wiadomość. Jak się z nią obchodzić? Dokładnie tak samo, jak w przypadku szyfrowania, tylko używamy innych liczb – teraz potrzeba nam klucza prywatnego:

 

M = C^D (mod n)

 

Po podstawieniu wartości:

 

M = 168^7 (mod 187)

M= 42

 

I mamy naszą oryginalną wiadomość. Całkiem ciekawa, prawda?

 

Jak wspomnieliśmy wcześniej – systemy kryptografii klucza publicznego opierają się na matematycznej trudności w celu zapewnienia bezpieczeństwa. Taką trudnością w przypadku algorytmu RSA jest rozkładanie na czynniki pierwsze dużych liczb. Bierze się to stąd, że dużą liczbą jest N. Ciężko znaleźć czynniki, które przemnożone przez siebie dają ogromną liczbę. A przynajmniej tak długo, jak nie znamy klucza prywatnego odbiorcy. Co jest ważne odnotowania – w praktyce liczby są o wiele większe niż te zastosowane jako przykład w artykule. Przeważnie klucze mają od 1024 do 4096 bitów długości – wtedy obliczenia są dużo trudniejsze i większe niż te pokazane wyżej. Jako przykład trudności złamania takich kluczy można podać, że w 2009 roku po prawie 2 latach przy pomocy setek komputerów otrzymało 232-cyfrową liczbę (768 bitów).

dodany: 29.01.2013 | tagi: , , ,

Bezpieczeństwo e-mail

10

Czy wiesz, że korzystanie z poczty elektronicznej poprzedza wynalazek Internetu?

Wiadomości elektroniczne były wysyłane przez przewód jeszcze długo zanim istniały sieci komputerowe. W rzeczywistości, e-mail utorował drogę dla Internetu, jaki znamy dzisiaj.

Czemu nie możesz do końca zaufać każdej wiadomości e-mail? Czy zawsze możesz być pewny, że informacje, jakie znalazłeś w swojej skrzynce pocztowej nie zostały sfałszowane i przyszły od wskazanego nadawcy?

Niestety, kiedy wymyślano e-mail, nie zastanawiano się nad jego bezpieczeństwem. Poczta elektroniczna oparta została o sieć peer-to-peer, gdzie wiadomości wysyłane są z serwera do serwera jako czysty tekst (z ang. plaintext), bez szyfrowania, póki nie osiągną swojego celu (nie dotrą do adresata).

Nawet jeśli łączysz się z dostawcą e-mail przez szyfrowane połączenia (SSL/TLS), żeby ściągnąć swoje wiadomości, nie oznacza to, że wiadomości nie zostały odczytane po drodze do Twojej skrzynki.

W przeciwieństwie do innych sposobów komunikacji w Internecie (sieci IM jak xmpp, gg, Skype czy sieci społecznościowe), w przypadku e-mail nie ma żadnych scentralizowanych serwerów, które kontrolują i zarządzają dostawą poczty, co może powodować problemy takie jak e-mail spoofing (wysyłanie wiadomości, która celowo wygląda jakby została wysłana przez kogoś innego – podszywanie się pod nadawcę).

Mimo to korespondencja przez e-mail wciąż jest wiążąca i może nawet zostać użyta jako dowód sądowy.

Jak więc bezpiecznie wysyłać wiadomości, tak żeby spełniały następujące wymagania:

  • odbiorca będzie przekonany, że e-mail jest od Ciebie,
  •  nikt poza odbiorcą nie będzie mógł przeczytać wiadomości,
  •  nie było możliwości, żeby ktoś zmienił treść wiadomości zanim dotrze do adresata?

W 1991 roku, Phil Zimmerman opublikował program nazwany PGP (z ang. Pretty Good Privacy – „całkiem niezła prywatność”), który gwarantuje wszystkie trzy wymienione punkty.

 Digital key in pixeled keyhole

Wiarygodność poprzez szyfrowanie

Na szczęście PGP i podobne oprogramowanie używające standardu OpenPGP (np. GPG) jest teraz legalnie dostępne w większości krajów i jest świetnym rozwiązaniem zabezpieczenia e-maili. Wysoki poziom bezpieczeństwa zostaje zapewniony przez szyfrowanie wiadomości i cyfrowe podpisywanie ich.

  • Szyfrowanie zapewnia poufność – zawartość wiadomości jest chroniona, więc może zostać odczytana tylko przez zamierzonego odbiorcę.
  • Cyfrowy podpis autoryzuje wiadomości – odbiorca może być pewny, że dostaje je właśnie od Ciebie.
  • Dodatkowo cyfrowy podpis zapewnia, że wiadomość nie została sfałszowana.
  • I na koniec upewnia, że nadawca w późniejszym terminie nie zaprzeczy wysłaniu wiadomości.

Szyfrowanie wiadomości oraz autoryzacja, które spełniają cztery wymagania bezpieczeństwa, oparte są o kryptografię klucza publicznego (ang. public-key cryptography).

Kryptografia klucza publicznego opisuje protokoły matematycznego szyfrowania i algorytmy, które pozwolą Ci bezpiecznie korzystać ze sklepów internetowych i z internetowej bankowości. Niestety, ten rodzaj kryptografii umożliwia malware wkradnięcie się do Twojego komputera i zaszyfrowanie go w celu wyłudzenia okupu (ransomware).

Ellis, Cocks i Williamson w 1973 roku w GCHQ (z ang. Government Communications Headquarters – ‚centrala łączności rządowej’) wymyślili pierwsze algorytmy klucza publicznego. Używały one matematycznej funkcji „trapdoor”, żeby przeprowadzać asymetryczne szyfrowanie wiadomości. To znaczy – sposoby szyfrowania i deszyfrowania są inne, żeby wiadomości nie dało się odkodować.

Każdy może zaszyfrować wiadomość – albo analogicznie zweryfikować cyfrowy podpis jako poprawny – za pomocą publicznej części klucza, ale tylko uprawniona osoba może deszyfrować wiadomość – albo cyfrowo podpisać – używając swojego sekretnego prywatnego klucza.

 

Jak to działa?

Wybierzmy sobie dwie osoby. Niech jedna ma na imię Alicja i druga Robert. Alicja chce bezpiecznie wysłać email do Roberta, bez możliwości, że Ewa odczyta albo zmodyfikuje jej wiadomość i chce, żeby Robert był przekonany, że wiadomość została wysłana właśnie przez nią.

Prosty przykład jak program PGP (albo podobny) zadziała (jak faktycznie protokoły działają, to sprawa dużo bardziej skomplikowana, ale sens jest ten sam):

Najpierw komputer Alicji szuka klucza publicznego Roberta w serwerze kluczy (z ang. key-server), który działa jak duża książka adresowa i szyfruje wiadomość używając jego klucza.

Następnie jej prywatny klucz użyty zostaje do cyfrowego podpisania wiadomości wysyłanej do Roberta.

Na koniec komputer Roberta deszyfruje wiadomość za pomocą jego prywatnego klucza i weryfikuje cyfrowy podpis używając publicznego klucza Alicji (pobranego z serwera kluczy).

Pada pytanie – skąd Alicja wie, że klucz publiczny Roberta, pobrany z serwera kluczy, jest poprawny i należy do niego, a nie np. do Ewy lub innej osoby? I tu pojawia się „web of trust” – mechanizm upewniający poprawność kluczy publicznych.

“Web of trust” jest alternatywą do infrastruktury klucza publicznego (z ang. public key infrastructure, w skr. PKI) używanego przez strony internetowe do zapewnienia bezpieczeństwa za pomocą certyfikatów SSL.

Idea jest prosta: załóżmy, że Alicja i Robert mają wspólnego znajomego o imieniu Marcin, któremu oboje ufają. Marcin może ręczyć za oboje – Alicję i Roberta, ponieważ zna ich osobiście i może zweryfikować ich tożsamość i ich powiązanie z kluczami publicznymi. Marcin podpisuje każdy z ich kluczy publicznych swoim własnym. Ponieważ Marcin ufa Robertowi i Alicja ufa Marcinowi (Alicja podpisała klucz publiczny Marcina) to pozwala Alicji uwierzyć w autentyczność klucza Roberta.

Takie realne uwierzytelnianie może brzmieć niewykonalnie i tworzyć kolejne problemy? Jest to jednak bardzo efektywny sposób zapewnienia bezpiecznej komunikacji (z systemami PGP albo podobnymi) bez potrzeby kupowania drogich certyfikatów bezpieczeństwa, jak te używane przez strony internetowe.

Często organizowane są nawet spotkania znane jako „key signing party”, żeby móc sprawdzić wzajemnie swoją tożsamość i podpisać klucze w celu propagacji sieciowego zaufania (web of trust).

 

Czemu bezpieczeństwo e-maili nie jest tak rozpowszechnione?

Prawdopodobnie powodem jest kombinacja wrażenia niewykonalności i braku świadomości zagrożeń. Nie zawsze jest proste zacząć używać klucza publicznego do szyfrowania e-maili, a utrzymanie klucza publicznego bezpiecznym może być kłopotliwe, jeśli używasz poczty z wielu urządzeń. Ponadto wiedza o problemach z e-mailami, spoofingu (podszywanie się pod nadawcę) nie jest tak duża jak powinna być.

Z pewnych względów tylko zdeterminowani, co do bezpieczeństwa w Internecie, będą się kłopotać używaniem tych systemów jako rutyny. Dla biznesu bezpieczeństwo korespondencji jest delikatną sprawą, często wymuszającą balansowanie na poziomie kosztów i ryzyka. Jednak dostawcy Internetu i poczty e-mail powinni poszerzać świadomość użytkowników i zachęcać do zabezpieczania wiadomości.

Pamiętaj następnym razem, kiedy strona Internetowa informuje, że „bezpiecznie” wysłała Ci przypomnienie hasła – jak faktycznie wygląda ten proces.