Dziś na tapet weźmiemy funkcję Eulera zwaną też tocjentem. Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje wartość będącą liczbą liczb od niej mniejszą, które są względem tej liczby względnie pierwsze. Na początek przypomnienie, czym są liczby względnie pierwsze. Liczby a oraz b nazwiemy względnie pierwszymi wtedy, gdy nwd(a, b) = 1. Jak powinniśmy pamiętać z lekcji matematyki w pierwszych klasach szkoły podstawowej, każdą liczbę złożoną można rozłożyć na iloczyn czynników pierwszych, np. 120 = 2 * 2 * 2 * 3 * 5. Taka reprezentacja liczby zgodnie z Wielki Twierdzeniem Arytmetyki jest zawsze możliwa i unikalna dla każdej liczby. Jeżeli teraz dokonamy tego dla dwóch liczb, np. a = 6 = 2 * 3 oraz b = 35 = 5 * 7, to jeżeli żadne z czynników się nie powtórzą, liczby a oraz b nazwiemy względnie pierwszymi, gdyż bez reszty mogą zostać wspólnie podzielone tylko przez 1. Jednak biorąc jeszcze, np. c = 10 = 2 * 5, widzimy, że ma zarówno taki sam czynnik wspólny z a(2), jak i z b(5). Stąd c nie będzie względnie pierwsze ani z a (bo 6 i 10, dzieli 2), ani z b (bo 35 i 10, dzieli 5). Tocjent zatem będzie określał dla danego A, ile liczb o wartościach od 1 do A-1 spełnia własność bycia względnie pierwszą do A. Np. dla A = 35 wartość tocjentu wyniesie 24, gdyż liczby, które nie mają wspólnych czynników większych niż 1 z 35 to: 1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34 i jest ich 24. Funkcję tę jako pierwszy opisał szwajcarski matematyk Leonhard Euler w 1763 roku i trzeba przyznać, że wygląda jak coś bez żadnego praktycznego zastosowania, ot taka matematyczna ciekawostka.

Sytuacja ta zmieniła się przeszło 200 lat później, kiedy znaleziono prawdopodobnie jedno z najbardziej użytecznych zastosowań tocjentu, a stało się to w roku 1977 za sprawą trzech kryptografów: Rona Rivesta, Adiego Szamira oraz Leonarda Adlemana, którzy opublikowali specyfikację algorytmu szyfrowania RSA (od pierwszych liter nazwisk autorów). Był to pierwszy algorytm szyfrowania, który nazwiemy asymetrycznym, gdyż korzysta on z faktu, że wykonanie funkcji oraz funkcji odwrotnej jest problemem niesymetrycznym. W tym przypadku łatwiej komputerowi pomnożyć dwie duże liczby przez siebie niż odwrócić to działanie rozkładając taki iloczyn na czynniki pierwsze.

Jego sposób działania wygląda na przykładzie następująco:
Przyjmijmy dwie losowe liczby pierwsze, np. p = 41 oraz q = 97. Następnie wybierzemy kolejną liczbę pierwszą e = 23 (przy czym nie jest to liczba dowolna, co wyjaśnię za chwilę). Obliczmy też liczbę n jako iloczyn liczb p oraz q: n = p*q = 41*97 = 3977. Załóżmy, że chcemy następnie zaszyfrować przy użyciu tych danych jakąś wiadomość reprezentowaną liczbą, np. M = 123. Możemy to zrobić w następujący sposób:
C = M^e (mod n) = 123^23 (mod 3977) = 902, czyli jak widzimy, aby ktoś mógł zaszyfrować dla nas wiadomość, musimy mu udostępnić liczby e oraz n.
Są to liczby, które stanowią część tzw. klucza publicznego, dostępnego do publicznej informacji, który można udostępnić każdemu.

Natomiast, gdybyśmy chcieli taką wiadomość C odszyfrować, też da się to zrobić łatwo przy jednym założeniu, znajomości liczb p oraz q. Są to liczby, które stanowią część klucza, który nazywamy prywatnym. Klucz taki powinien być dostępny tylko dla jego właściciela. Można to zrobić następująco, obliczając najpierw wartość klucza deszyfrującego k:
k = (fi(n) + 1) / e, gdzie fi(n), to nasza wartość funkcji Eulera (tocjentu) dla argumentu n=3977. Znalezienie wartości dla dowolnego dużego n to trudne zadanie, ale dla liczby będącej iloczynem dwóch liczb pierwszych można to sobie ułatwić, jeżeli znamy te liczby.

Tocjent ma kilka ciekawych własności, ale przyjrzymy się dziś dwóm z nich. Pierwsza jest konsekwencją trywialną, mianowicie fi(a), gdzie a jest liczbą pierwszą, przyjmuje wartość a-1, co można zapisać fi(a) = a-1, gdy p|a. Wynika to z tego, że względem danej liczby pierwszej wszystkie liczby mniejsze od niej muszą być z nią względnie pierwsze, bo inaczej z definicji nie byłaby liczbą pierwszą (musi dzielić się tylko przez 1 i samą siebie). Druga natomiast mówi o rozdzielności iloczynu liczb względnie pierwszych, fi(a*b) = fi(a) * fi(b), wtedy gdy nwd(a, b) = 1. Łącząc te dwie własności łatwo zauważyć, że dla liczb p oraz q zachodzi: fi(p*q) = fi(p) * fi(q) = (p-1)*(q-1), gdyż dwie liczby pierwsze muszą być też względnie pierwsze między sobą, bo żadna liczba pierwsza nie może dzielić innej liczby pierwszej. Stąd możemy zapisać równanie na klucz deszyfrujący k w sposób tożsamościowy:
k = ((p-1)*(q-1) + 1) / e = 3841/23 = 167. Jak widzimy, e nie może być dowolne (o czym wspominałem na początku o jego doborze), bo musi dzielić fi(n) + 1 bez reszty.

Znając klucz deszyfrujący, pozostaje nam odszyfrować wiadomość według poniższej formuły:
M' = C^k (mod n) = 902^167 (mod 3977) = 123, co zwraca wartość wejściowej danej M.

W swojej pracy, twórcy algorytmu RSA ponadto udowodnili, że inny sposób odwrócenia tego działania jest w zasadzie niemożliwy. Powyższy algorytm można mieć zapisany przed oczami, znać liczby n oraz e, ale i tak nie pozwoli nam to na odszyfrowanie danych w rozsądnym czasie. A najsłabszym punktem tego algorytmu (czyli tzw. wektorem ataku), na co w dokumencie zwracają uwagę sami autorzy, jest teoretyczna możliwość faktoryzacji (czyli rozkładu na czynniki pierwsze) klucza publicznego (liczby n) w celu uzyskania klucza prywatnego (liczb p oraz q). W świecie komputerów kwantowych powstały już nawet algorytmy, np. algorytm Shora ( https://pl.wikipedia.org/wiki/Algorytm_faktoryzacji_Shora ), które są teoretycznie w sposób wydajny dokonać takiej operacji, ale dziś je pominę, aby nie popaść w nieskończoną dygresję. Trzeba byłoby zapewne wyjaśnić, jak działa taki komputer, jakie są jego ograniczenia, a to też materiał na długi wpis. Czy jest się czego bać w świecie klasycznych, komputerów 4. generacji, które posiada w domu każdy z nas?

Odpowiedź to: well yes, but actually no.
Faktoryzacja liczb dla zwykłego komputera jest problemem, który w skali złożoności na dziś klasyfikujemy w informatyce teoretycznej jako NP (od ang. Non-Polynomial), czyli niewielomianowy, co też jest tożsame z tym, że taki problem nazywamy wykładniczym, gdyż wraz ze wzrostem danych do przetworzenia, jego problematyczność rośnie potęgowo. Łatwo to sobie wyobrazić na przykładzie legendy o mędrcu Ben Daher, który wymyślił szachy. W zamian za grę zażądał od panującego w Indiach radży, aby zapłacił zbożem, ale w taki sposób, że na pierwszym polu szachownicy położy jedno ziarno, a na każdym kolejnym dwa razy więcej niż na poprzednim. W ten sposób na szachownicę będą trafiać kolejno: 1,2,4,8,16,32 itd. ziarna. Władca, który był zachwycony grą, zdziwił się tak prostym żądaniem. Nakazał przygotować zapłatę, jednak szybko okazało się, że prośba nie jest możliwa do spełnienia. Początkowo może się to wydawać niewiele, ale już na samym 21 polu trzeba ich położyć ponad milion, a na 64 polu będzie trzeba ich położyć dokładnie 9223372036854775808. W sumie na całej szachownicy powinniśmy położyć ich 18446744073709551615, co według wyliczeń (źródło na końcu) wymagałoby silosu o podstawie kwadratu 4 na 10 m oraz wysokości 300 mln kilometrów. Alternatywnie, gdybyśmy osuszyli wszystkie oceany, pozbyli się wszystkich lodowców, tak by można było co do milimetra kwadratowego obsiać całą Ziemię, szacuje się, że trzeba byłoby to zrobić 8 razy, aby uzyskać powierzchnię wysiewu, która obrodzi tyloma ziarnami.

Jak widzimy problem, który początkowo, dla małych liczb jest bardzo łatwy, bardzo szybko przybiera skalę niemożliwą do zrealizowania, podobnie jest z faktoryzacją liczb. W algorytmie RSA używa się p oraz q, które nie wynoszą jak w przykładzie 41 czy 97, ale liczb, które w zapisie binarnym mają w standardzie 1024, 2048 czy nawet 4096 bitów. Liczby takie mają odpowiednio w zapisie dziesiętnym 309, 617, 1234 cyfr. Natomiast iloczyny takich liczb w kluczu publicznym muszą mieć ich około dwóch razy więcej. Liczby takie są zbyt duże, by przeprowadzić ich rozkład na czynniki pierwsze w rozsądnym, skończonym czasie. Dla 1024 bitów trwają co prawda prace nad łamaniem (czyli faktoryzacją wszystkich możliwych kombinacji liczb pierwszych o tym zakresie), ale dla np. 4096 bitów szacuje się, że dzisiejszy komputer uruchomiony w chwili wielkiego wybuchu nie byłby dziś nawet w połowie pracy nad jego złamaniem.

Czyli wszystko dobrze i można spać spokojnie, bo niemożliwym jest szybsze faktoryzowanie liczb? No właśnie nie do końca, problem ten ma status nieokreślonego, to znaczy nikt nie udowodnił, że istnieje algorytm lub formuła matematyczna, która pozwoli na szybki rozkład dowolnej losowej liczby na czynniki pierwsze, ale też nikt nie udowodnił, że takiego algorytmu znaleźć się nie da. Polegamy więc na czymś, o czym możemy powiedzieć: who knows?
Choć może się to wydawać dziwne, bo w istocie cała kryptografia oparta o liczby pierwsze upadłaby w momencie, gdyby ktoś odkrył sposób szybkiej faktoryzacji liczb (kolejny raz pomijam komputery kwantowe), to problem ten w zasadzie istnieje od początków nauki ludzkości i tego, gdy wymyślono matematykę. Już w starożytnej Grecji mówiono o liczbach pierwszych jako "atomach" (gr. atomos, czyli niepodzielny) wśród liczb, z których są zbudowane inne liczby. I choć od tego czasu udało się znaleźć kilka twierdzeń, które trochę pozwalają zrozumieć liczby pierwsze, jak np. Małe Twierdzenie Fermata, Liczby pierwsze Mersenna, czy Twierdzenie Eulera, to biorąc losowe duże losowe liczby pierwsze p i q, które nie są bardzo odległe co do wartości względem siebie, faktoryzacja znając tylko ich iloczyn, jest po prostu szalenie czasochłonna i trudna, nawet przy użyciu najwydajniejszego klastra komputerów klasycznych.

Możliwe, że część osób pamięta głośną sprawę Edwarda Snowdena, który był powiązany z wyciekiem różnych ściśle tajnych danych rządowych USA. Wśród opublikowanych notek była też jedna ze wzmianką o tym, że NSA próbowało wpływać na bezpieczeństwo algorytmu RSA, aby móc deszyfrować wiadomości na swoje potrzeby. Konkretnie chodziło o jeden z konkretnych programów oraz podsunięcie firmie RSA wątpliwego (jak się okazało po czasie, gdyż na tamten moment był on akredytowany przez NIST) algorytmu generowania liczb p oraz q, tak by NSA mogło łatwiej określić ich wartości na podstawie n, niż wynikałoby to z całkowicie losowego rozkładu. Już samo to powinno dać do myślenia, że matematyka jest tu bezwzględna i nawet jeden z największych (o ile nie największy) wywiadów wewnętrznych na świecie nie miał innej możliwości obejścia tego systemu szyfrowania, niż próbować umieścić w nim "furtkę" (ang. back-door), która pozwoli na łatwiejszą deszyfrację: https://en.wikipedia.org/wiki/Dual_EC_DRBG

Jak więc to wszystko ma się do życia codziennego? Można nie zdawać sobie sprawy, ale za każdym razem, kiedy wchodzimy na strony w internecie zaczynająca się od https, wykonywane są między innymi powyższe operacje. Programiści zadbali, aby przeglądarki internetowe robiły to oczywiście poza świadomością użytkownika dla jego wygody. Metoda ze względu na to, że można nią zaszyfrować limitowaną ilość danych ze względu na operację modulo, nie służy do zaszyfrowania samej treści strony, ale w zależności od wersji protokołu wymieniane są nią klucze symetryczne, które służą do szyfrowania końcowego oraz w bezpieczny sposób nawiązuje się połączenie z serwerem DNS, w celu zamiany przyjaznej nazwy jak na przykład fcbarca.com na adres IP, tak by można było nawiązać połączenie z serwerem. Dzisiaj jednak wszystko powoli zmierza w kierunku odejścia od tego bądź co bądź wysłużonego już algorytmu, głównie ze względu na obawy związane z technologią kwantową. Wciąż jednak można spotkać się z jego szerokim użyciem, gdyż według wszystkich dostępnych informacji nadal uważa się go za kryptograficznie bezpieczny. Postanowiłem więc sprawdzić jakaś losową stronę banku w internecie oraz naszą La Ramble pod tym kontem.

Dla fcbarca.com co ciekawe używana jest już metoda kryptograficzna, która w założeniach ma oprzeć się łamaniu metodami kwantowymi. Konkretnie wykorzystywany jest mieszany schemat X25519Kyber768. X25519 to metoda uzgodnienia kluczy starego typu, oparta o krzywe eliptyczne, ale można ją przełączyć w każdej chwili na Kyber768, czyli metodę nowej generacji dla kryptografii postkwantowej: https://zapodaj.net/images/40a8bd22b9caf.png
Natomiast na przykład mBank używa jeszcze wersji TLS 1.2 z opisanym wyżej RSA właśnie: https://zapodaj.net/images/1abd0873eb23c.png
Choć na pierwszy rzut oka może się to wydać dziwne, czemu "stronka sportowa" korzysta z nowszej metody kryptografii, niż strona poważnego (hehe) banku, to w istocie nie jest to dziwne. Z doświadczenia mogę powiedzieć, że instytucje finansowe muszą zachowywać tzw. compliance. Mówiąc prościej, jeżeli coś działa, jest sprawdzone przez dziesiątki lat, a oficjalnie nie jest uznane za przedawnione, niebezpieczne rozwiązanie, to lepiej użyć w takich miejscach sprawdzonego i pewnego rozwiązania. Zależność, w której uznajemy najnowsze za najlepsze, nie musi być zachowana w tak delikatnym obszarze, jak szyfrowanie. Serwis banku na pewno nie jest dobrym "poligonem doświadczalnym".


Jako bonusową ciekawostkę dodam, że dzięki funkcji Eulera poza szyfrowaniem otrzymaliśmy jeszcze jedną przydatną możliwość. Ponieważ kryptografia jest asymetryczna i tylko właściciel posiada klucz prywatny, możemy go także zastosować jako podpis elektroniczny/cyfrowy. Pojęcie, z którym zapewne mogliście się spotkać, jeżeli wysyłaliście kiedyś dokumenty do e-urzędu. Podpis cyfrowy wykorzystywany jest po to, aby poświadczyć autentyczność nadawcy oraz upewnić się, że nie została zmodyfikowana przez osoby trzecie po drodze. Jest to dość istotne, gdyż często możemy ulec mylnemu wyobrażeniu, że skoro dane są zaszyfrowane, to są też bezpieczne, jeśli chodzi o nieautoryzowaną modyfikację. W końcu jak zmodyfikować coś, czego nie możemy odczytać? Oczywiście jest to błędne myślenie, gdyż istnieją metody ataków na zaszyfrowane dane, jeżeli możemy domyślić się części treści, a o to przy np. protokole HTTP nie jest trudno ze względu na tzw. nagłówek wiadomości.

Aby wykorzystać RSA do cyfrowego podpisu, należy odwrócić kolejność operacji i dla poprzednich wartości p,q,n,k,e będzie to wyglądać następująco:
Najpierw należy obliczyć sygnaturę z użyciem klucza szyfrującego: S = M^k (mod n) = 123^167 (mod 3977) = 3075, którą następnie należy przesłać wraz z wiadomością do odbiorcy.
Druga strona może wtedy sprawdzić ten podpis, ustalając czy wiadomość nie została po drodze przez kogoś zmodyfikowana. Zrobi to w następujący sposób:
M' = S^e (mod n) = 3075^23 (mod 3977) = 123 = M. Jeżeli M = M', to możemy założyć, że nie doszło do modyfikacji wiadomości przez osoby trzecie. Oczywiście operacje szyfrowania i podpisu można ze sobą łączyć (a nawet należy!), aby zapewnić zarówno bezpieczeństwo przed modyfikacją (podpis), jak i odczytem (szyfrowanie).

Źródła:
Oryginalny dokument RSA: https://people.csail.mit.edu/rivest/Rsapaper.pdf
Legenda o mędrcu Ben Daher: https://www.chessforkids.pl/blog/blog/252_historia-szachow-i-legenda-z-nimi-zwiazana
Szyfrowanie z użyciem RSA: https://cryptobook.nakov.com/asymmetric-key-ciphers/the-rsa-cryptosystem-concepts
Podpis cyfrowy z użyciem RSA: https://cryptobook.nakov.com/digital-signatures/rsa-signatures

PS Morał z dzisiejszego wpisu: możesz spotkać w matematyce rzeczy, które dziś są do niczego nieprzydatne w praktyce, ale ludzie za kilkaset lat mogą sobie nie wyobrażać bez tego funkcjonowania.

PPS Ogólnie polecam w całości to "preview" książki, jeżeli kogoś interesuje kryptografia ogółem (nie tylko asymetryczna) z ukierunkowaniem na praktyczne zastosowanie w programowaniu. Jedna z lepszych i przystępniejszych, jakie czytałem na ten temat: https://cryptobook.nakov.com/

@misterio jak ktoś to przeczyta daje zielonego ...

@misterio szacun za ten cały wywód

@Bocheno1 oczywiście, że przeczytałem. @misterio pisze ciekawe rzeczy.

@misterio Brrr, jak ja nienawidzę matematyki.

@misterio Uzupełnię, że klasyfikujemy problem faktoryzacji, jako problem z przecięcia klas NP i co-NP, które raczej wierzymy że są w P co oznacza, że potrafimy rozwiązywać je w czasie wielomianowym (co oznacza, że kryptografia oparta na RSA byłaby mocno zagrożona, gdyby ktoś znalazł taki algorytm, choć niekoniecznie zawaliłaby się od razu).

Jeszcze z ciekawostek o nauce. W zeszłym roku został opublikowany niesamowity wynik na pograniczu fizyki i informatyki o powiązaniu promieniowanie Hawkinga i kryptografii. W uproszczeniu kryptografia istnieje wtedy i tylko wtedy gdy istnieje promieniowanie Hawkinga. Jakby ktoś chciał więcej o tym poczytać, to tu zamieszczona jest oryginalna praca https://arxiv.org/pdf/2211.05491

@VamosB dzięki za wstawkę na pewno się zapoznam z pracą.

Co do samej faktoryzacji i ogólnie wielu problemów liczb pierwszych, to wydaje mi się, że jeżeli zostaną kiedyś rozwiązane odpowiedzi będą negatywne (brak efektywnego wzoru na n-tą liczbę pierwszą, niemożliwość faktoryzacji, itd.). Może moje wnioskowanie jest naiwne, ale za przykład biorę tu liczby algebraiczne i liczby przestępne. Dopóki ktoś niewpadł na pomysł, że jedne liczby niewymierne są trochę inne niż pozostałe liczby niewymierne, nie dało się udowodnić braku konstrukcyjności kwadratury koła, a to problem też z początków matematyki. W sumie muszę o tym też kiedyś napisać osobno.

@misterio czy możesz mnie oznaczyć

@Seneka Jasne.

@misterio Dzięki, co prawda nie do końca czasem ogarniam o czym piszesz, ale prowokujesz do szukania i pogłębiania tematu, dzięki