Cryptosystem of McElece – Wikipedia

Kryptosystem McELEce to asymetryczny schemat szyfrowania, wynaleziony w 1978 roku przez Roberta McELEcece ^{[[[ Pierwszy ]} . Ten system, oparty na trudnym problemie teorii kodów, nie spotkał się z żadnym prawdziwym poparciem w społeczności kryptograficznej ^{[Ref. niezbędny]} , między innymi, ponieważ klucz szyfrowania jest szczególnie duży, a zaszyfrowana wiadomość jest dwa razy dłuższa niż oryginał. Jednak kryptosystem McELece ma interesujące właściwości: bezpieczeństwo rośnie znacznie szybciej wraz z wielkością kluczy niż dla systemu RSA, a szyfrowanie jest szybsze.

Kolejną zaletą jest oparcie się na zupełnie innym problemu zwykłych asymetrycznych algorytmów. Oznacza to, że teoretyczne przełom w dziedzinie faktoryzacji, osiągalne przez algorytmy kwantowe, które zrujnowałyby RSA, w żaden sposób nie wpłynąłby na ten system. Ta zaleta pozwala na wybór NIST jako kandydata do standaryzacji algorytmów szyfrowania ^{[[[ 2 ]} .

Skuteczne ataki zostały opublikowane przeciwko McElece Cryptosystem, a także na wiele wariantów. Zaproponowano jednak ulepszenia w celu uniknięcia tych ataków. Jest rzadko stosowany w praktyce ze względu na duży rozmiar klawiszy, ale był używany do szyfrowania w entropii, alternatywy dla Freenet.

Kod korekcji błędów umożliwia skorygowanie informacji, które zmieniłyby się podczas transmisji za pomocą kanału (sieć, CD-ROM, czas itp.). Aby to zrobić, słowo (seria symboli) jest przekształcane w słowo kodu poprzez dodanie informacji (zwanych redundancją). W wylotu kanału stosuje się redundancja do korygowania błędów, a tym samym znaleźć słowo kodowe przesłane na wejściu. To słowo jest następnie przekształcane, aby podać oryginalne słowo.

Ideą McELece polega na maskowaniu kodu słowa odpowiadającego komunikatowi poprzez dodanie jak największej liczby błędów przy jednoczesnym zachowaniu możliwości ich poprawienia. Jeśli metoda korekcji jest utrzymywana w tajemnicy, tylko odbiorca będzie mógł znaleźć oryginalną wiadomość. Metodę kodowania można pozostawić publicznie, o ile nie ujawnia informacji na temat dekodowania.

McEliiec Cryptosystem używa kodów GOPPA. Kody GOPPA są łatwe do dekodowania, ale gdy ich struktura zamaskowana przez permutację trudno jest je odróżnić od kodów liniowych. Ponadto trudno jest zdekodować losowy kod liniowy. Bezpieczeństwo systemu opiera się zatem na dwóch odrębnych problemach: gapie z jednej strony z jednej strony i problemu ograniczonego dekodowania z drugiej.

W 1986 r. Harald Niederreiter zaproponował kolejny kryptosystem oparty na teorii kodów ^{[[[ 3 ]} . Kryptosystem Niederreitera został udowodniony z kryptencją McELece w 1994 r. Przez Y.X. Li, R.H. Deng i X.M. Wang ^{[[[ 4 ]} .

Kryptosystem McELece składa się z trzech algorytmów: probabilistyczny algorytm generowania kluczy, który wytwarza tajny klucz i klucz publiczny, algorytm szyfrowania (probabilistycznego) i (deterministycznego) algorytmu rozszyfrowania. Wszyscy użytkownicy udostępniają parametry bezpieczeństwa:

${DisplayStyle N, K, T}$

.

Generowanie kluczy [[[ modyfikator |. Modyfikator i kod ]

1. Losowo wybierz
   ${displayStyle (n, k)}$

   -Linenowy kod

   ${DisplayStyle C}$

   zdolne do korygowania

   ${DisplayStyle T}$

   Błędy. Ten kod musi mieć skuteczny algorytm dekodowania.

2. Alice generuje macierz generującą
   ${DisplayStyle g}$

   dla kodu

   ${DisplayStyle C}$

   (matryca

   ${DisplayStyle ktimes n}$

   ).

3. Losowo wybierz matrycę binarną
   ${DisplayStyle ktimes k}$

   nieingularne

   ${DisplayStyle s}$

   .

4. Losowo wybierz macierz permutacji
   ${DisplayStyle P}$

   

   ${DisplayStyle n}$

   .

5. Obliczyć matrycę
   ${displayStyle {hat {g}} = sgp}$

   . To jest matryca

   ${DisplayStyle ktimes n}$

   .

6. Klucz publiczny to
   ${displayStyle ({hat {g}}, t)}$

   ; Klucz prywatny jest

   ${DisplayStyle (s, g, p)}$

   .

Szyfrowanie [[[ modyfikator |. Modyfikator i kod ]

Aby określić ilościowo kontynuację binarną

${DisplayStyle M}$

długość

${DisplayStyle K}$

:

1. Obliczyć wektor
   ${DisplayStyle C^{prime} = m {hat {g}}}$

   .

2. Wygeneruj wektor błędu
   ${DisplayStyle e}$

   waga

   ${DisplayStyle T}$

   (binarna sekwencja długości

   ${DisplayStyle n}$

   pojemnik

   ${DisplayStyle T}$

   1 i

   ${DisplayStyle N-T}$

   0).

3. Obliczyć zaszyfrowane
   ${DisplayStyle c = c^{prime}+e}$

   .

Rozszyfrowanie [[[ modyfikator |. Modyfikator i kod ]

1. Oblicz
   ${displayStyle {hat {c}} = cp^{-1}}$

   .

2. Użyj algorytmu dekodowania
   ${DisplayStyle C}$

   do dekodowania

   ${displayStyle {hat {c}}}$

   jednym słowem

   ${displayStyle {hat {m}}}$

   .

3. Oblicz
   ${DisplayStyle m = {hat {m}} s^{-1}}$

   

Pozytywne [[[ modyfikator |. Modyfikator i kod ]

Zasadniczo kody GOPPA są uważane za „dobre” kody liniowe, ponieważ pozwalają na skorygowanie

${DisplayStyle {n^{k}} Wybierz {log _ {2} n}}$

błędy; Są one skutecznie ozdobione, w szczególności przez algorytmy euklidu i Berlekamp-Massey.

Negatywny [[[ modyfikator |. Modyfikator i kod ]

Klucze publiczne i prywatne to świetne macierze, które stanowią jedną z największych wad tej postaci. Na przykład kluczem publicznym jest

${DisplayStyle 2^{19}}$

bity (64 Kio).

Wystąpiły próbki kryptanalizy algorytmu McELece, ale zmiany spowodowały, że były nieoperacyjne. Niemniej jednak algorytm ten nie jest używany w praktyce, z jednej strony ze względu na znaczny rozmiar jego kluczy, Ale także dlatego, że rozmiar szyfrowanego tekstu jest dwa razy więcej niż oryginalny tekst ^{[Ref. niezbędny]} .

Podobieństwo między tym problemem a problemem plecaka również martwi się częścią specjalistów ^{[Ref. niezbędny]} .

W 1991 roku E.M. Gabidulina i in. zaproponował poprawę ^{[[[ 5 ]} , które dwa lata później zostaną udowodnione bez przewagi przez J.K. Gibsona ^{4 To jest edition_de_la_conference _ ” IMA_Conference_ON_Cryptography_and_coding ” _ de_1993_6-0 “class =” reference “> [[[ 6 ]} .

Bibliografia [[[ modyfikator |. Modyfikator i kod ]

• [MCELIECE 1978] (W) Robert J. McElice, ‘ Kryptosystem publiczny oparty na teorii kodowania algebraicznego » W Raport postępowania DSN Laboratorium Jet Propulsion DSN W 1978 W P. 42–44 ( Czytaj online )
• [Niederreiter 1986] Harald Niederreiter, ” Kryptosystemy typu plecaków i teoria kodowania algebraicznego », Problemy kontroli i teoria informacji 15 W tom. Pierwszy, N ^O 6, 1986 W P. 159–166
• [Li, Deng et Wang 1994] Yuan Xing Li, Robert H. Deng et xin Mei Wang, « O równoważności kryptosystemów publicznych McELECES i », Transakcje IEEE dotyczące teorii informacji W tom. 40, N ^O 1, 1994 W P. 271–273
• [Gabidulin, Paramon’s Et Treetak 1991] E.M. Gabidulin, A.V. Paramonov i.v. Tretjakov, « Ideały nad niekomutacyjnym pierścieniem i ich zastosowaniem w kryptologii », Eurocrypt , Springer-Verlag, 1991 W P. 482-489 (Doi 10 1007/3-540-46416-6_41 )
• [Gibson 1995] J.K. Gibson, « Poważne wgniecenie wersji gabidulin McElece Public Cryptosystem », Projekt, kody i krypto W tom. 6, 1995 W P. 37–45 (ISSN 1573-7586 , Doi 10.1007/BF01390769 )

Powiązane artykuły [[[ modyfikator |. Modyfikator i kod ]