SZYFROWANIE I LICZBY PIERWSZE

Liczby pierwsze to liczby, które mają jedynie dwa dzielniki – dzielą się one bowiem przez 1 i samą siebie. Przykładami takich liczb są: 7, 563, 7919, 82889, 2^82589933 - 1 (*) . Ta ostatnia to największa do tej pory znana nam liczba pierwsza, która posiada dokładnie 24 862 048 cyfr, a została ona odkryta 7 grudnia 2018 roku przez Patricka Laroche’a. Możesz ją zobaczyć w całości na stronie podanej w literaturze.

Liczb tych jest nieskończenie wiele, co stwierdził już grecki matematyk Euklides, ok. roku 300 p.n.e. Niestety, nie znamy ich wszystkich, a wiele komputerów i ludzi ciągle pracuje nad ich znajdowaniem. Jest to bardzo trudne, ponieważ nie mamy wzoru na ich generowanie. Powstał nawet „konkurs”, którego nagrodą są pieniądze. Organizacja Electronic Frontier Foundation wyznaczyła nagrodę 150 tysięcy dolarów dla odkrywcy liczby pierwszej która ma więcej niż 100 milionów cyfr. Wcześniej zostały wypłacone już podobne nagrody za krótsze liczby pierwsze.

Liczby pierwsze przydają nam się w wielu sprawach, a szczególnie w szyfrowaniu. Tylko po co tak w zasadzie szyfrujemy, i dlaczego akurat tymi liczbami pierwszymi? Otóż robimy to, by ochronić się np. przed podsłuchem lub kradzieżą danych. Przyjrzyjmy się teraz metodom szyfrowania. Metody szyfrowania dzielimy na  asymetryczne i symetryczne. W szyfrowaniu symetrycznym algorytmy używają tego samego klucza (czyli w pewnym uproszczeniu hasła) zarówno do szyfrowania jak i deszyfrowania informacji. Ma to jednak pewną ważną wadę – problemem jest tu przekazywanie klucza między dwoma użytkownikami.

W szyfrowaniu asymetrycznym generowane są dwa klucze – prywatny i publiczny. Osoba, która ma zamiar wysłać zaszyfrowane dane czy wiadomość do drugiej, otrzymuje od niej klucz publiczny, za pomocą którego będzie mogła je zaszyfrować. Klucza publicznego nie trzeba w tym przypadku chronić i można go przekazywać go w dowolny sposób, bo nie umożliwia on odszyfrowania informacji. Po wysłaniu takich danych druga osoba może je odszyfrować za pomocą swojego własnego, prywatnego klucza.

Znaną metodą szyfrowania asymetrycznego, które wykorzystuje liczby pierwsze jest RSA, której nazwa pochodzi od trzech nazwisk jej autorów: Rivest, Shamin i Adleman. Polega ona na tym, że bierzemy dwie bardzo duże liczby pierwsze, które następnie mnożymy. Dzięki temu działaniu otrzymujemy liczbę n, czyli część klucza prywatnego i publicznego. Następnie na jej podstawie wyliczamy również liczby d oraz e. Sposób wyznaczania tych liczb można znaleźć w podanej literaturze. Są to operacje łatwe do przeprowadzenia, typu mnożenie czy dzielenie, nawet na dużych liczbach (przynajmniej dla komputerów).

Teraz przejdźmy do tego, z jakich dokładnie liczb są zbudowane klucze. Klucz publiczny tworzą liczby e oraz n, a klucz prywatny liczby d oraz n. Na podstawie samego klucza publicznego (liczby n oraz e), gdy mamy do czynienia z dużymi liczbami pierwszymi, bardzo trudnym zadaniem jest dojście do tego, jakich liczb pierwszych użyliśmy na samym początku do generowania naszych dwóch kluczy. Jest zadaniem niezwykle trudnym (nawet dla największych komputerów) rozłożenie takiej dużej liczby n z powrotem na dwa czynniki, z których powstała. Dlatego właśnie nikt (o ile nasze liczby są oczywiście długie, o tym trzeba pamiętać) nie będzie w stanie wygenerować (inaczej mówiąc wyliczyć) klucza prywatnego na podstawie liczb zawartych w kluczu publicznym. Szyfrowanie więc opiera się na trudności rozkładu dużych liczb na czynniki pierwsze.

Gdzie i kiedy możemy się spotkać z takim rodzajem szyfrowania? Cóż, jest to dość popularna i powszechna metoda zabezpieczania danych. Wystarczy udać się na stronę banku, internetowe zakupy czy po prostu zwyczajnie porozmawiać czy popisać ze znajomymi w Internecie. Metoda ta jest też stosowana w podpisach cyfrowych. Tak, we wszystkich tych czynnościach stosowane jest właśnie szyfrowanie asymetryczne wykorzystujące liczby pierwsze. Dziś szyfrujemy za pomocą dużych liczb pierwszych, które mają nierzadko ponad trzysta cyfr, podczas gdy kilkanaście-kilkadziesiąt lat temu miały one ich o wiele mniej, co wskazuje na rozwój technologii. Naprawdę ciekawą obserwacją może być to, że przecież jeszcze w starożytnym Rzymie używano szyfru Cezara, który dziś da się banalnie złamać bez większego wysiłku, tak samo jak z Enigmą – niemiecką maszyną szyfrującą, która była używana w czasach drugiej wojny światowej. Jest jeszcze jedna ważna rzecz – rozwój komputerów kwantowych może się przyczynić do łamania szyfrów takich jak RSA, co sprawia, że powstanie przez to dużo zagrożeń i niebezpieczeństw. JB

 (*) zapis 2^7 oznacza 2 do potęgi 7

Literatura:

1.    Marek Świerkota, Zastosowania liczb pierwszych, https://home.agh.edu.pl/~zobmat/2017/wyr_swierkotmarek/zastosowanie.html

2.    Dariusz Kulma, Kryptografia a liczby pierwsze, http://matematykainnegowymiaru.pl/open/lekcje.php?mode=pokaz&id=71

3.    Wojciech Karpowicz, Liczby pierwsze i szyfrowanie, http://konikowo.info/kolo/szyfrowanie.html

4.    Programowalny, Podstawy kryptografii w 12 minut, https://www.youtube.com/watch?v=CnegWWOPOKE

5.    emce□, N U B S W R J U D I L D, https://www.youtube.com/watch?v=ONcjKxMH80E

6.    Archipelag Matematyki, Kryptografia z kluczem publicznym, https://www.youtube.com/watch?v=mZfzs0aIPNw

7.    The PrimePages: prime number research & records, https://primes.utm.edu/

8.     is prime, http://lcn2.github.io/mersenne-english-name/m74207281/prime-c-e.html