|
[ Pobierz całość w formacie PDF ]
.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ć).189 M.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).Poniewa\ p jest liczbÄ… pierwszÄ…, wiÄ™c p dzieli x + lalbo x 1.Inaczej mówiÄ…c, x 1 mod p lub x 1 mod p.DLemat 30.Mec/t p bÄ™dzie liczbÄ… pierwszÄ…, g generatorem Z* , 0 [ Pobierz caÅ‚ość w formacie PDF ] |
Archiwum
|