Kryptosystem McEliece'a

W kryptografii kryptosystem McEliece jest algorytmem szyfrowania asymetrycznego opracowanym w 1978 roku przez Roberta McEliece'a . Był to pierwszy taki schemat wykorzystujący randomizację w procesie szyfrowania. Algorytm nigdy nie zyskał dużej akceptacji w społeczności kryptograficznej, ale jest kandydatem do „ kryptografii postkwantowej ”, ponieważ jest odporny na ataki przy użyciu algorytmu Shora i – bardziej ogólnie – mierzenia stanów kosetowych za pomocą próbkowania Fouriera.

Algorytm opiera się na twardości dekodowania ogólnego kodu liniowego (o którym wiadomo, że jest NP-trudny ). Do opisu klucza prywatnego wybiera się kod korekcji błędów $, dla którego znany jest wydajny algorytm dekodowania i który jest w stanie$ błędy. Oryginalny algorytm wykorzystuje binarne kody Goppa (kody podpól geometrycznych kodów Goppa krzywej rodzaju-0 na polach skończonych o charakterystyce 2); kody te można skutecznie dekodować dzięki algorytmowi opracowanemu przez Pattersona. Klucz publiczny jest wyprowadzany z klucza prywatnego poprzez maskowanie wybranego kodu jako ogólnego kodu liniowego. $celu$$jest$ macierz generatora kodu zakłócana przez dwie losowo wybrane odwracalne macierze $i$ ( poniżej).

Istnieją warianty tego kryptosystemu, wykorzystujące różne typy kodów. Większość z nich okazała się mniej bezpieczna; zostały złamane przez dekodowanie strukturalne.

McEliece z kodami Goppa do tej pory opierał się kryptoanalizie. Najbardziej skuteczne znane ataki wykorzystują dekodowania zestawu informacji . Artykuł z 2008 roku opisuje zarówno atak, jak i poprawkę. Inny artykuł pokazuje, że w przypadku obliczeń kwantowych rozmiary kluczy muszą zostać zwiększone czterokrotnie ze względu na ulepszenia w dekodowaniu zbioru informacji.

Kryptosystem McEliece ma pewne zalety w porównaniu np. z RSA . Szyfrowanie i deszyfrowanie jest szybsze. Przez długi czas uważano, że McEliece nie może być używany do tworzenia podpisów . Jednak schemat podpisu można zbudować w oparciu o Niederreitera , podwójny wariant schematu McEliece. Jedną z głównych wad McEliece jest to, że klucze prywatny i publiczny są dużymi macierzami. Dla standardowego wyboru parametrów klucz publiczny ma długość 512 kilobitów.

Definicja schematu

McEliece składa się z trzech algorytmów: probabilistycznego algorytmu generowania klucza, który tworzy klucz publiczny i prywatny, probabilistycznego algorytmu szyfrowania i deterministycznego algorytmu deszyfrowania.

Wszyscy użytkownicy we wdrożeniu McEliece współużytkują zestaw wspólnych parametrów bezpieczeństwa: ${\ displaystyle n, k, t}$ .

Generowanie klucza

Zasada jest taka, że ​​​​Alicja wybiera kod liniowy $wiadomości$ pewnej rodziny kodów, dla których zna wydajny algorytm dekodowania, i podaje do $zachowuje$ algorytm dekodowania w tajemnicy. Taki algorytm dekodowania wymaga nie tylko znajomości $także$ znajomości parametrów używanych podczas określania $\ displaystyle C}$ w wybranej rodzinie kodów. Na przykład w przypadku binarnych kodów Goppa informacją tą byłby wielomian Goppa i lokalizatory kodu. $odpowiednio$ macierz generatora .

Dokładniej, kroki są następujące:

1. Alicja wybiera kod binarny ${\ Displaystyle (n, k)}$$-liniowy$ zdolny do (skutecznego) korygowania $z$ jakiejś dużej rodziny kodów, np. binarnej Goppa kody. Ten wybór powinien dać początek wydajnemu algorytmowi dekodowania. ${\ displaystyle A}$ . $displaystyle$ też będzie dowolną macierzą generatora dla $C}$ . Każdy kod liniowy ma wiele macierzy generatora, ale często istnieje naturalny wybór dla tej rodziny kodów. $więc$ o tym ujawniłaby, należy to zachować w tajemnicy.
2. Alicja wybiera losową macierz binarną inną niż pojedyncza . $razy$ \ $}$
3. Alicja wybiera losową macierz permutacji $}$$\ displaystyle n \ razy n$ .
4. Alicja oblicza $sol$${\ Displaystyle {\ hat {G}$ } .
5. Klucz publiczny Alicji to ${\ Displaystyle ({\ kapelusz {G}}, t)}$ ; jej klucz prywatny to ${\ Displaystyle (S, P, A)}$ . $wyboru$ , że można $zakodować$ i zapisać jako parametry używane .

Szyfrowanie wiadomości

Załóżmy, że Bob chce wysłać wiadomość m do Alicji, której kluczem publicznym jest ${\ Displaystyle ({\ kapelusz {G}}, t)}$ :

1. Bob koduje wiadomość jako ciąg binarny o długości $k}$$displaystyle$ .
2. Bob oblicza wektor $pierwsza} = m {\ kapelusz {G}}}$ .
3. Bob generuje losowy $}$ wektor zawierający dokładnie $displaystyle$ (wektor o długości i wadze $n$$n}$$\ displaystyle t$ )
4. Bob oblicza tekst zaszyfrowany jako $\ Displaystyle c = c ^ {\ liczba pierwsza} + z}$ .

Odszyfrowanie wiadomości

Po otrzymaniu Alice wykonuje następujące kroki, aby odszyfrować wiadomość: do $\ displaystyle c}$

1. Alice oblicza odwrotność (tj $.$${\ Displaystyle P ^ {-1}}$ .
2. Alicja oblicza $\ Displaystyle {\ kapelusz {c}} = cP ^ {- 1}}$ .
3. Alicja używa algorytmu dekodowania $do$ dekodowania do $\ Displaystyle$$}}$ .
4. Alicja oblicza ${\ Displaystyle m = {\ kapelusz {m}} S ^ {- 1}}$ .

Dowód odszyfrowania wiadomości

do $^ {-1}} i że jest macierzą$$= cP ^ {-1} = m { \ hat {G}}$${\ styl wyświetlania zP^{-1}}$$zP$ permutacji , więc ma wagę ${\ displaystyle t}$ .

Kod Goppa $a$ poprawić błędy do ${\ displaystyle t}$$,$ słowo znajduje się najwyżej w odległości od do $t}$$\ displaystyle$$styl wyświetlania cP^{-1}}$ . Dlatego uzyskuje się poprawne słowo kodowe ${\ displaystyle {\ hat {m}} = mS} .$

Mnożenie przez odwrotność daje $\ kapelusz {m}} S ^ {-1} = mSS ^ {-1} }$${$ , który jest zwykłą wiadomością tekstową.

Kluczowe rozmiary

Ponieważ macierz ma wolny wybór , często wyraża się $ją w „$$,$ tak aby ostatnie kolumny $displaystyle S$ odpowiadają macierzy tożsamości ${\ Displaystyle {\ kapelusz {G}} = ({\ tylda {G}} | ja)}$ . Zmniejsza to rozmiar klucza do ${\ Displaystyle (nk) \ razy k}$ . McEliece pierwotnie sugerował rozmiary parametrów bezpieczeństwa ${\ Displaystyle n=1024, k = 524, t = 50}$ , co skutkowało rozmiarem klucza publicznego 524 * (1024-524) = 262 000 bity. Niedawna analiza sugeruje rozmiary parametrów ${\ Displaystyle n=2048, k = 1751, t = 27}$ dla 80 bitów bezpieczeństwa przy użyciu standardowego dekodowania algebraicznego lub $przy użyciu$ rozmiary i odpowiednio 460 647 bitów. Aby uzyskać odporność na komputery kwantowe, rozmiary ${\ Displaystyle n = 6960, k = 5413, t = 119}$ z kodem Goppa, podając rozmiar klucza publicznego 8 373 911 bitów. W jego rundzie 3 przedłożenia do NIST po standaryzacji kwantowej najwyższy poziom bezpieczeństwa, poziom 5, jest podany dla zestawów parametrów 6688128, 6960119 i 8192128. Parametry to n = 6688 , $= 6688, k = 128, t = 13}$ , ${\ Displaystyle n = 6960, k = 119, t = 13}$ , ${\ Displaystyle n = 8192, k = 128, t = 13}$ odpowiednio.

Ataki

Atak polega na tym, że przeciwnik, który zna klucz publiczny, $,$${\ Displaystyle y \ w \ mathbb {F} _ {2} ^ {n}}$ tekst jawny z przechwyconego tekstu zaszyfrowanego . Takie próby powinny być niewykonalne.

Istnieją dwie główne gałęzie ataków na McEliece:

Brute-force / ataki nieustrukturyzowane

Atakujący wie $\$$}$ generatora kodu do $}$${\ hat {$$,$ który jest kombinatorycznie w stanie poprawić . Atakujący może zignorować fakt, że ${\ Displaystyle {\ hat {C}}}$ jest tak naprawdę zaciemnieniem kodu strukturalnego wybranego z określonej rodziny, a zamiast tego po prostu użyj algorytmu do dekodowania z dowolnym kodem liniowym. Istnieje kilka takich algorytmów, takich jak przeglądanie każdego słowa kodowego kodu, dekodowanie zespołu lub dekodowanie zbioru informacji .

Wiadomo jednak, że dekodowanie ogólnego kodu liniowego jest NP-trudne , a wszystkie wyżej wymienione metody mają wykładniczy czas działania.

W 2008 roku Bernstein, Lange i Peters opisali praktyczny atak na oryginalny kryptosystem McEliece przy użyciu metody dekodowania zbioru informacji autorstwa Sterna. Wykorzystując parametry pierwotnie sugerowane przez McEliece'a, atak można było przeprowadzić w 2 operacjach ^{60,55 bitowych.} Ponieważ atak jest żenująco równoległy (nie jest wymagana komunikacja między węzłami), można go przeprowadzić w kilka dni na skromnych klastrach komputerowych.

Ataki strukturalne

$zamiast$ tego próbować odzyskać „strukturę” $,$ odzyskując w ten sposób wydajny algorytm dekodowania inny wystarczająco silny, wydajny algorytm dekodowania

Rodzina kodów, z których jest $wybierana, całkowicie określa, czy$ to możliwe dla atakującego. Zaproponowano wiele rodzin kodów dla McEliece, a większość z nich została całkowicie „zepsuta” w tym sensie, że znaleziono ataki, które odzyskują wydajny algorytm dekodowania, takie jak kody Reeda-Solomona .

Pierwotnie proponowane binarne kody Goppa pozostają jedną z nielicznych sugerowanych rodzin kodów, które w dużej mierze oparły się próbom opracowania ataków strukturalnych.

Kandydat na szyfrowanie postkwantowe

Wariant tego algorytmu połączony z NTS-KEM został zgłoszony i wybrany podczas trzeciej rundy konkursu NIST na szyfrowanie postkwantowe .

Linki zewnętrzne

•   Alfreda J. Menezesa; Scott A. Vanstone; AJ Menezes; Paul C. van Oorschot (1996). „Rozdział 8: Szyfrowanie kluczem publicznym” . Podręcznik kryptografii stosowanej . Prasa CRC. ISBN 978-0-8493-8523-0 .

• „Komputery kwantowe? Złamany internetowy kod bezpieczeństwa przyszłości” . Nauka Codzienna . Politechnika w Eindhoven . 1 listopada 2008 r.

• „Klasyczny McEliece” . (Zgłoszenie do projektu standaryzacji kryptografii postkwantowej NIST )