Matematyka czysta i brudne tricki NSA (2006-2013)

Krzywe eliptyczne odegrały wielką rolę w dowodzie twierdzenia Fermata. Ten piękny obszar matematyki czystej ma także bardzo praktyczne zastosowania w kryptografii. Dzięki rewelacjom Edwarda Snowdena wyszły na jaw nadużycia techniki krzywych eliptycznych: amerykańska National Security Agency doprowadziła do rozpowszechnienia standardów szyfrowania zawierających furtkę ułatwiającą łamanie szyfrów – oczywiście w ramach wojny z terrorem i dla dobra społeczeństwa amerykańskiego (inne społeczeństwa powinny oczywiście pragnąć tego samego co Amerykanie).

Krzywe eliptyczne dla współrzędnych rzeczywistych

Zacznijmy od przykładu okręgu, który jest wykresem równania drugiego stopnia x^2+y^2=1. Jeśli punktom na okręgu przypiszemy kąty, to możemy zdefiniować dodawanie punktów tak, jak na rysunku. Aby otrzymać sumę dwóch punktów, dodajemy odpowiednie kąty, jeśli wyjdzie nam więcej niż 360º, należy odjąć tę wartość i zostawić resztę. Punkt odpowiadający kątowi 0º można dodać do każdego innego i nic się nie zmieni: jest więc elementem neutralnym dodawania. Dla każdego punktu P można też znaleźć punkt przeciwny -P. Jeśli punktowi P odpowiada kąt \alpha, to punktowi -P odpowiada kąt 360^{\circ}-\alpha.

200px-Circle-group.svg

Działania na punktach tworzą grupę: można je dodawać, istnieje element neutralny oraz każdy element ma element przeciwny. Zachodzi też prawo łączności.

Okazuje się, że podobny zabieg można przeprowadzić także na krzywych trzeciego stopnia. Krzywe eliptyczne są wykresami pewnych wielomianów trzeciego stopnia. Wykluczamy wielomiany, których wykres się zapętla albo ma ostrze. Pozostają na przykład takie.

500px-ECClines-3.svg

Dla punktów na tych krzywych można także wprowadzić dodawanie. Jeśli trzy punkty krzywej są współliniowe, to ich suma jest równa zeru (rysunek 1). Biorąc styczną do krzywej w punkcie Q, musimy go liczyć podwójnie: jakby dwa punkty Q były współliniowe z P: 2Q+P=0. Punkty leżące na tej samej prostej pionowej (równoległej do Oy) przecinają punkt w nieskończoności, który jest zerem naszej grupy. W ten sposób punkty P i Q na rysunku 3 są przeciwne do siebie (ich suma daje zero).

1000px-ECClines.svg

Można sprawdzić, że otrzymuje się w ten sposób grupę: mając dwa punkty można znaleźć trzeci, który jest ich sumą. Trudniej w tym przypadku znaleźć parametr, który się przy tej okazji dodaje (jak kąty w przykładzie z okręgiem). Okazuje się, że można to zrobić, traktując nasze punkty jako zespolone i używając funkcji eliptycznych. Jest to elegancki fragment dziewiętnastowiecznej analizy matematycznej.

Krzywe eliptyczne w arytmetyce modularnej

W zastosowaniach kryptograficznych nieco inaczej definiuje się krzywą eliptyczną. Wyrażenie algebraiczne pozostaje takie jak wyżej, zmieniamy jednak dziedzinę. Interesują nas liczby całkowite modulo p, gdzie p jest jakąś liczbą naturalną. Znaczy to, że mając dowolną liczbę całkowitą dzielimy ją przez p i obliczamy resztę z dzielenia. Dwie liczby są dla nas równe jeśli te reszty są równe:

23=2\cdot 11+1=1 \pmod{11}.

Otrzymujemy wtedy dokładnie p różnych liczb – bo tyle jest możliwych wyników na resztę dzielenia przez p. Jeśli liczba p jest liczbą pierwszą, mnożenie i dodawanie liczb w tej arytmetyce modularnej będzie miało takie same własności jak dla liczb rzeczywistych: można będzie wykonywać zwykłe cztery działania (oprócz dzielenia przez 0).
Do zastosowań w kryptografii używa się jakiejś krzywej eliptycznej (czyli wyrażenia kwadratowego w y i sześciennego w x) dla pewnej dużej liczby pierwszej p. Nasza płaszczyzna xy zawiera wówczas p^2 punktów (plus punkt w nieskończoności). Wykres naszej krzywej to pewien ich podzbiór, który niezbyt przypomina krzywą, ma jednak nadal jej własności: na punktach można wykonywać owo dziwne dodawanie, o którym mówiliśmy wyżej. Wyrażenia algebraiczne na współrzędne punktu Q będącego sumą punktów P i R są takie same, należy je tylko obliczać modulo p. Wzory są takie same jak w przypadku wykresu na zwykłej płaszczyźnie Oxy.
Możemy dodawać wiele razy ten sam punkt: P+P=P_2 \equiv 2P
Okazuje się, że stosunkowo szybko można uzyskać dowolne wielokrotności danego punktu. Chcąc np. obliczyć 16P obliczamy kolejno 2P, 4P=2P+2P, 8P=4P+4P, 16P=8P+8P.
W ten sposób w stosunkowo niedużej liczbie kroków możemy dojść szybko do bardzo wielkiej wielokrotności naszego początkowego punktu P. Istotne jest, że niełatwo jest tę operację odwrócić. Aby ustalić jakie jest rozwiązanie równania

xP=Q,

gdzie x jest liczbą naturalną, a P, Q punktami krzywej eliptycznej, należy w zasadzie sprawdzać kolejne możliwości, co przy dużych p jest niewykonalne. Podsumowując: mnożenie punktów przez dużą liczbę całkowitą daje się wykonać szybko, znalezienie natomiast liczby spełniającej ostatnie równanie może być sprawą beznadziejną, gdy w grę wchodzą duże liczby.

Co takiego zrobiło NSA?

Krzywe eliptyczne dla dużych p można wykorzystać do generowania liczb losowych. Ściśle biorąc żadne liczby generowane w deterministycznej procedurze nie mogą być zupełnie przypadkowe. Ale ze współrzędnych krzywej eliptycznej da się wygenerować bardzo dobre liczby tzw. pseudolosowe.
Amerykańska agencja NIST (National Institute of Standards and Technology) zaproponowała algorytm oparty na krzywych eliptycznych. Podała parametry takiej krzywej

y^2=x^3-3x+b\pmod{p},

a także współrzędne dwóch punktów krzywej P i Q.

QValue256Jak widać, liczby są gigantyczne.
Do generowania liczb pseudolosowych potrzebne są dwa punkty krzywej. NIST „pomogła” użytkownikom, podając te współrzędne. Wszystko wskazuje na to, że NSA, czyli agencja zajmująca się bezpieczeństwem, podsunęła dwa odpowiednio zmajstrowane punkty takie, że kP=Q i liczba k jest im znana. Bardzo trudno to sprawdzić, ponieważ nie ma na to szybkiej metody.

Do czego można wykorzystać taką wiedzę?

Obserwując ciąg liczb generowanych przez program, można ustalić jakie będą następne liczby. W ten sposób ciąg wyglądający na losowy jest przewidywalny dla kogoś, kto zna k. Ponieważ NIST w 2006 r. zaproponowała algorytm, a znana firma od zabezpieczeń RSA wprowadziła ten algorytm do swego oprogramowania, wszyscy, którzy go używają są narażeni na szpiegowanie przez NSA. Algorytm używany jest np. przy tworzeniu bezpiecznych połączeń z bankami, płatnościach kartami kredytowymi itd. itp. Firma RSA sama zaproponowała użytkownikom, aby nie stosowali tego algorytmu, wcześniej prawdopodobnie zarobiła 10 mln. dolarów od rządu na wprowadzeniu go w życie.

Film na Youtube, w którym znakomity matematyk Edward Frenkel wyjaśnia przystępnie, na czym polega problem

Więcej odsyłaczy na blogu Not Even Wrong

6 myśli nt. „Matematyka czysta i brudne tricki NSA (2006-2013)

  1. Pingback: Weekendowa Lektura | Zaufana Trzecia Strona

    • Najkrócej o to, że umieścili backdoor w oprogramowaniu służącym do szyfrowania połączeń. Dzięki temu mogą np. obejrzeć czyjeś połączenia z bankiem nie bawiąc się w procedury sądowe itd. itp.

      Lubię

  2. Końcówka jest typowym medialnym szukaniem sensacji, niewiele mającym wspólnego z prawdą. Macki RSA co prawda sięgają daleko, ale nie na tyle daleko aby umieścić swoje oprogramowanie (BSAFE) w przeglądarkach czy serwerach WWW. Jest to zresztą software kosztujący dość sporo kasy, więc tylko spore firmy go kupowały. W otwartym oprogramowaniu OpenSSL ten algorytm nie jest domyślny. Zatem NSA nie może póki co wykorzystać DualEC do podsłuchiwania komunikacji HTTPS z bankami itp. Natomiast niewykluczone, że wykorzystuje w tym celu inne metody, np. dziury w przeglądarkach.

    Lubię

    • Nie całkiem. Matematycy w USA, którzy pracują m.in. w grantach finansowanych przez NSA, widzą problem. W ogóle wprowadzanie ludzi w błąd przez rząd jest problemem w kraju demokratycznym. Ile jest jeszcze takich dziur, nie wiadomo. Ta została wykryta i firma RSA sama poprosiła, żeby użytkownicy przestali stosować ten algorytm, przyznając się pośrednio, że została zmanipulowana albo przymknęła oczy na backdoor. Linki można znaleźć na blogu Not even wrong. Nie ma tu sensacji, ja nie pracuję w mediach, ale też problem widzę.

      Lubię

      • Ale ja nie odnosiłem się do całego artykułu, który jest sensowny, tylko do fragmentu „Algorytm używany jest np. przy tworzeniu bezpiecznych połączeń z bankami, płatnościach kartami kredytowymi itd. itp.” który jest typowym szumem medialnym.

        Lubię

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s