kryptografia wielu zmiennych.pdf

(280 KB) Pobierz
3971249 UNPDF
Kryptografia wielu zmiennych
NicolasTadeuszCourtois
Uniwersytet Paryz 6 i Uniwersytet w Toulon.
courtois@minrank.org
IV Krajowa Konferencja Zastosowan Kryptografii,
Enigma 2000
Warszawa, 22-25 maja 2000.
Slajdy i dodatkowe materialy:
http://www.minrank.org/~courtois/myresearch.html
,,Wszyscy matematycy wiedza, ze przejscie
z jednej do wielu zmiennych to nagly skok
ktoremu towarzysza wielkie trudnosci”
JeanDieudonn´e
wybitnyfrancuskimatematyk
1
3971249.001.png
1 Kryptografia klucza publicznego
Klasyczna kryptografia, nazywana obecnie kryptografia symetryczna,
pozwala osiagnac poufnosc danych wylacznie przy zalozeniu uprzed-
niego istnienia jakiegos pewnego kanalu komunikacyjnego np. wal-
izka dyplomatyczna albo spotkanie w parku bez swiadkow. Ten kanal
jest niezbedny do ustalenia tajnego klucza na ktorym polega bez-
pieczenstwo dalszej komunikacji.
Kryptografia klucza publicznego to systemy pozwalajace bez-
piecznie komunikowac bez uprzedniej wymiany klucza, nawet na linii
stale podsluchiwanej przez osoby trzecie. Wymaga ona tylko istnienia
tzw. kanalu publicznego ktory co prawda kazdy moze czytac, ale nikt
nie moze zmodyfikowac lub zablokowac. Na tym kanale mozemy opub-
likowac tzw. klucz publiczny, ktory pozwala zaszyfrowac wiadomosc,
ale nie pozwala jej odszyfrowac, do czego niezbedny jest odpowiedni
klucz tajny ktory nigdy nie opuszcza wlasciciela. Ta asymetria jest
zrodlem terminu kryptografia asymetryczna.
1.1 Historia idei klucza publicznego
W ramach otwartych uniwersyteckich badan naukowych zostala ona
wynaleziona w 1976 przez Die, Hellman i niezaleznie przez Merkle.
Najbardziej znany i stosowany kryptosystem to Rivest-Shamir-Adleman
(RSA) opublikowany w 1977.
W zamnkietych kregach specjalistow wojskowych i rzadowych byla
ona jednak znana duzo wczesniej. Wlasciwym wynalazca jest James
Ellis, jeden z filarow brytyjskiego biura szyfrow CESG przy GCHQ w
Cheltenham. Pierwszy (tajny) dokument na ten temat pochodzi ze
stycznia 1970 [1]. Nastepnie w 1973 Cliord Cocks wymysla wariant
pozniejszego RSA, a w 1974 Malcolm Williamson wynajduje wariant
pozniejszej metody wymiany klucza wedlug Die-Hellman. Szczegoly
opisuje Ellis w artykule z 1977 opublikowanym dopiero po jego smierci
[1], kiedy Cliord Cocks na nieoficjalnej sesji-niespodziance podczas 6-
tej konferencji IMA w Cirencester 17-go grudnia 1997 po raz pierwszy
ujawnia prawde.
2
1.2 Historia kryptografii wielu zmiennych
Wiele wczesnych systemow kombinatorycznych oparte na zagadnie-
niu plecakowym [Merkle-Hellman 1978], teorii grafow i wiele innych
zostalo szeroko skompromitowanych. Z drugiej strony, istnieja rownie
stare, algebraiczne kryptosystemy wielu zmiennych uzywajace rownan
liniowych wielu zmiennych nad cialami skonczonymi i zwykle opisywane
w terminach kodow korekcyjnych. Poczawszy od [McEliece 1978] i dla
wielu innych, oparly sie one dziesiecioleciom kryptoanalizy i pozwolily
na wyodrebnienie bardzo trudnych problemow zwanych SD i MinRank
dla ktorych wszystkie znane ataki sa wykladnicze.
Pozniej pojawily sie algebraiczne kryptosystemy wielu zmiennych
uzywajace rownan drugiego stopnia, najpierw w Japonii [Matsumoto,
Imai], potem w USA [Fell, Die, Cade], a nastepnie w Izraelu [Shamir]
i we Francji [Patarin, Goubin, Courtois]. Najnowsze badania pokazuja
ze niektore z tych systemow, np. HFE, opieraja sie rowniez na trudnych
problemach algebraicznych np. problemy MQ, IP i MinRank.
Sila wspolczesnej kryptografii wielu zmiennych polega na tym ze
istniejace kryptosystemy oparte na trudnych algebraicznie problemach
mozna przeksztalcic w kombinatoryczne wersje, jeszcze trudniejsze do
zlamania.
1.3 Zagadnienia kryptografii klucza publicznego
Kryptografia klucza publicznego zawiera nastepujace scisle ze soba powia-
zane zagadnienia:
[1] Ustalanie klucza: Dwie osoby ktore rozmawiaja przez publiczny
kanal ktory jest na podsluchu, ale nie moze byc przerwany, staraja
sie ustalic wspolny, tajny klucz sesyjny.
Jezeli nie ma pewnosci co do integralnosci kanalu, nie jest to ni-
estety mozliwe (w teorii) i wymaga uprzedniej identyfikacji [3].
W przeciwnym razie ktos moze wlaczyc sie pomiedzy (man-in-
the-middle attack) i skutecznie udawac kazda ze stron. W prak-
tyce jednak identyfikacja moze odbyc sie bez kryptografii, przez
wspolny kontekst nieznany innym (znajomosc drugiej osoby) lub
za pomoca danych biometrycznych (rozpoznanie glosu).
[2] Szyfrowanie z kluczem publicznym: Jak opisano poprzednio,
pozwala na szyfrowanie za pomoca opublikowanego klucza pub-
licznego ktorego nie mozna odczytac bez posiadania odpowied-
niego klucza tajnego. Cel [2] mozna tez uzyskac to za pomoca
[1] i vice versa.
3
[3] Identyfikacja, kontrola dostepu: Dowiesc ze to ja, a nie kto
inny chce wejsc do pomieszczenia, systemu, lub ze to ja jestem na
drugim koncu linii (protokoly w czasie rzeczywistym).
[4] Uwierzytelnienie, autentyzacja, autentykacja, certyfikacja:
Pozwala zagwarantowac ze to ja nie kto inny jestem autorem danego
dokumentu, lub wiadomosci (certyfikuje pochodzenie). Roznica
miedzy identyfikacja i uwierzytelnieniem jest taka ze w pierwszym
przypadku nie ma wiadomosci.
[5] Podpis cyfrowy: Tak jak powyzej gwarantuje pochodzenie. W
dodatku podpis powinien przekonac w sposob niezbity kazda trzecia
osobe (np w sadzie) o swojej autentycznosci.
Parametry dobrac tak, aby podpis byl byc wazny przez b. dlugi
okres czasu np. 20 lat (liczac sie z postepem kryptoanalizy).
Kto potrafi wiecej, potrafi i mniej, podpis cyfrowy zapewnia tez
funkcje [3] i [4]. Ale o ile [3] a nawet [4] mozna osiagnac w klasy-
cznej kryptografii symetrycznej np. z tajnym kluczem DES,
podpisu cyfrowego [5] nie mozna !
[6] Uwierzytelnienie z protokolami/dowodami wiedzy zerowej
(Zero-knowledge): Pozwala na osiagniecie celu [3] w sposob
nieskonczenie bardziej bezpieczny nia te opisane w [3], [4] i [5].
Zalozmy ze Peggy udowadnia swoja tozsamosc za pomoca pro-
tokolu wiedzy zerowej, osobie ktora ja sprawdza Victor. Daje
to matematycznie dowiedziona pewnosc ze Victor moze dokonac
sprawdzenia dowolna ilosc razy, zawsze byc w pelni przekonanym
ze to Peggy, ale nigdy ne zdola on uzyskac najmniejszej infor-
macji ktora pozwolilaby mu podanie sie za Peggy.
W polaczeniu z kryptograficzna funkcja haszujaca ktora zastepuje
pytania (queries), [6] pozwala osiagnac tez [5].
[7] Rozne zagadnienia rozproszone: Np. glosowanie elektron-
iczne.
4
2 Bezpieczenstwo kryptosystemow
Bezpieczenstwo to precyzyjnie sformulowane wymaganie co do trudnosci
jaka bedzie mial dany Przeciwnik aby skutecznie przeprowadzic atak
na dany kryptosystem. Przeciwnik jest zdefiniowany formalnie jako
probabilistyczna maszyna Turinga.
Bezpieczenstwo definiuje sie w ogolnosci w zaleznosci od trzech danych.
1. Jakie sa zasoby Przeciwnika (resources) ? Dotyczy to mocy oblicze-
niowej, dostepnej pamieci, i innych parametrow dostepnej tech-
nologii (np. posiadanie komputera kwantowego).
2. Jaki rodzaj bezpieczenstwa (security notion) chcemy osiagnac
? Jaki jest cel Przeciwnika (goal), tzw. grozba ?
Na przyklad odzyskac caly klucz lub tylko odszyfrowac niektore
wiadomosci. Inny przyklad: moc podac sie za kogos innego.
3. Jaki jest model ataku (attack model), tzn jaki rodzaj dostepu
lub interakcji istnieje miedzy Przeciwnikiem i konkretnym kryp-
tosystemem ktory chce on zalamac.
Na przyklad atak wybranym tekstem jawnym.
3 Bezpieczenstwo kryptosystemow klucza publicznego
3.1 Dla szyfrow asymetrycznych
Podstawowe rodzaje bezpieczenstwa to:
• Trudnosc znalezienia klucza tajnego: Celem przeciwnika jest odzyska-
nia klucza tajnego majac do dyspozycji klucz publiczny.
• Jednokierunkowosc (one-wayness, OW).
To niemoznosc obliczeniamdla danego szyfrogramuE(m).
• Bezpieczenstwo semantyczne (semantic security, polynomial secu-
rity, IND).
Sformalizowane przez Goldwasser i Micali. Oznacza niemozliwosc
rozroznienia pomiedzy dwoma zaszyfrowanymi tekstami jawnymi
E(m 1 ) iE(m 2 ). Odpowiada to bezpieczenstwu doskonalemu, w
kontekscie przeciwnikow o ograniczonej wielomianowo mocy obliczeniowej.
• Niedeformowalnosc (Non-malleability, NM).
Sformalizowane przez Dolev, Dwork i Naor. Oznacza niemozliwosc
wyprodukowania dla danego szyfrogramuy, innego waznego szyfro-
gramuy 0 , w taki sposob aby odpowiednie teksty jawnex,x 0 byly ze
soba zwiazane w jakis sprawdzalny sposob. Na przykladx=x 0 +1
albo rozniace sie na jednej tylko pozycji.
5
Zgłoś jeśli naruszono regulamin