Kryptografia Miroslaw Kutylowski, Willy B. Strothmann(1)

[ Pobierz całość w formacie PDF ]
.Dla przykładu, nasze powy\sze rozwa\ania wyznaczają charakterystykę dla3 rund z prawdopodobieństwem około 0.048.Wiele tego typu charakterystykmo\na znalezć, zadanie to jest tym trudniejsze, im większe ma byćprawdopodobieństwo i liczba rozwa\anych rund.Powróćmy teraz do prób złamania DES-a zło\onego z 4 rund.W tym celuwielokrotnie powtarzamy następujące kroki:187M.Kutyłowski, W.-B.Strothmann1.losowo wybieramy parę danych wejściowych o ró\nicy równej0080820060000000* i szyfrujemy oba ciągi,2.zakładając, \e ró\nica l XOR l wynosi 00808200, przeprowa-dzamy kryptoanalizę ró\nicową dla ostatniej rundy.Dla wszystkich prób prowadzimy statystykę otrzymanych mo\liwychkluczy".Dla ka\dego klucza prowadzimy statystykę, ile razy wystąpiłjako mo\liwy klucz".W przypadkach, gdy zało\enie co do ró\nicyL3 XOR L3 jest fałszywe, wszystkie klucze są podawane z podobnymiprawdopodobieństwami.Gdy jednak zało\enie to jest spełnione (azachodzi to dla około 4,8% przypadków), to prawdziwy klucz zostaniez pewnością wskazany jako jeden z mo\liwych kluczy".Wynika ztego, \e w naszych statystykach prawdziwy klucz powinien występo-wać wyraznie częściej ni\ inne klucze.Oczywiście, by tę statystycznąprawidłowość odkryć, trzeba dysponować odpowiednio du\ą liczbąeksperymentów.Poniewa\ dla charakterystyk opisujących du\ą ilośćrund prawdopodobieństwo jest bardzo małe, mo\emy być zmuszeni doprzeprowadzenia statystyki dla olbrzymiej liczby par danych wej-ściowych.12.2.2.Kryptoanaliza liniowaLiniowa kryptoanaliza jest dziś najbardziej efektywną metodą kryp-toanalizy DES-a.Wymaga średnio 243 par tekst jawny-kryptogram dlaznalezienia klucza (atak typu known plaintext).Metoda ta została od-kryta i opublikowana stosunkowo niedawno i, jak się okazało, nie byłabrana pod uwagę podczas projektowania DES-a.Tak jak kryptoanalizaró\nicowa okazała się bardzo efektywnym narzędziem do wykazy-wania, i\ wiele nowo projektowanych metod szyfrowania nie jest bez-piecznych.Liniowa aproksymacja S-boksów: chocia\ S-boksy nie obliczają ła-twych do przedstawienia funkcji (na przykład funkcji liniowych), nieznaczy to, \e funkcji tych nie da się przedstawić w przybli\eniu przezproste formuły.188KryptografiaDla pojedynczego S-boksu S rozwa\amy formuły postaciijx XOR ij2 XOR " " " XOR ije = ohl XOR 0hl XOR " " " XOR 0h ,gdzie odpowiednio is oraz os oznaczają s-ty bit danych wejściowych i danychwyjściowych.Ze względu na zasady konstrukcji S-boksów równość taka niemo\e zachodzić dla wszystkich danych wejściowych.Nam wystarcza jednak,gdy jest stosunkowo często albo stosunkowo rzadko spełniona.Jeśli takjest, to mówimy \e formuła ta liniowo aprok-symuje S-boks S.Na przykład, S-boks S5 mo\e być scharakteryzowany przez formułęz4 = o0 XOR Oi XOR 02 XOR 03.Równość ta zachodzi dla ok.19% danych wejściowych.Mo\na więczało\yć, \eZ4 = -n(o0 XOR Oi XOR 02 XOR 03)i będzie to prawdą dla ok.100% -19% = 81% przypadków (wa\ne jest więc,by udział procentowy przypadków, dla których dana równość zachodzi,odbiegał jak najbardziej od 50%).W powy\szej formule mo\na następniezastąpić z'4 poprzez XOR odpowiedniego bitu klucza i bitu danychwejściowych rundy.Z formuł aproksymujących liniowo pojedyncze S-boksy mo\na zbudowaćformuły opisujące związki pomiędzy danymi wejściowymi rundy, bitamiklucza oraz wynikami rundy.Oczywiście, związki te zachodzą tylkostatystycznie dla stosunkowo du\ej lub stosunkowo małej liczby danychwejściowych.Formuły dla poszczególnych rund mo\na powiązać ze sobą.Przykład: dla DES-a z trzema rundami mo\na wyprowadzić następująceformuły aproksymujące zachowanie algorytmu:XOR (p7, pw, p24, P29, P47, C7, Cis, C24, C29, C47) = k\2 XOR ^2 (12.1)gdzie pi oznacza i-ty bit tekstu jawnego, Cj oznacza /-ty bit krypto-gramu, k"zaś oznacza u-ty bit klucza w-tej rundy.Równość (12.1) zachodzi zprawdopodobieństwem q dla losowo wybranego tekstu jawnego (q jestznane, ale nie będziemy q podawać).189M.Kutyłowski, W.-B.StrothmannDla grupy m losowo wybranych tekstów jawnych wyliczamy wartość stojącąpo prawej stronie równości (12.1).Niech r będzie liczbą przypadków, wktórych otrzymaliśmy 1 (tym samym 0 otrzymujemy w m rprzypadkach).Na podstawie wartości r/m oraz ą przyjmujemy teraznastępującą wartość dla k -�% k\2 XOR k\2'-Przypadek 1: q > 0.5wtedy k := 0, jeśli r/m 0.5,Przypadek 2: q 0.5, oraz k := 1, jeśli r/m +w? = (^"-;)� �% (gfl)P = 1 mod p.Zatem g = 1 mod p,sprzeczność.�%A.2.7.Pierwiastki modulo nMówimy, \e y jest resztą kwadratową modulo n, jeśli istnieje x, takie \e xz y mod n.W takim przypadku mówimy te\, \e x jest pierwiastkiem z ymodulo n.Zacznijmy od wyznaczenia pierwiastków modulo liczba pierwsza.Lemat 29.Jeśli p jest liczbą pierwszą i x2 = 1 mod p, to x 1 mod p lub x 1 mod p.Dowód.Jeśli x2 1 mod /?, to x2 1 = 0 mod p, a zatem p dzieli x2 -1 = (x + l)(x 1) [ Pobierz całość w formacie PDF ]

Tematy