Algorytm A5.pdf

Wykład-20.11.2006

AlgorytmA5

Wykorzystywanyjesttenalgorytmwtelefoniikomórkowej.

1.Próbkowanie:8kHz

2.Kwantyzacja

3.Kompresjadanych

4. Szyfrowanie

5.Kodowaniekoryguj¡cebł¦dy

AlgorytmA5jestzbudowany ztrzechliniowychrejestrówprzesuwnych.

Algorytmjest algorytmemmieszanym -macechyalgorytmublokowegoorazstrumieniowego.

Wykorzystywanes¡wtymalgorytmie114-bitoweramki.

Rysunek1:SchematdziałaniaalgorytmuA5

Zpól( mid-1,mid-2,mid-3 )pobieranes¡warto±ciiprzesyłanedozegarasteruj¡cegoukłademtychrejestrów

-pobieraontedaneidecydujeotym,którerejestryb¦d¡przesuwanewdanymcykluzegara.

Wdanymcykluprzesuwanes¡terejestry,któremaj¡wpolach mid „wi¦kszo±¢”.

Je±lis¡trzyzeralubtrzyjedynki-wówczaswszystkierejestrys¡przesuwane.

Doszyfrowaniajestu»ywany 64-bitowykluczsesyjny. Klucztenjestgenerowanypodczasnawi¡zywania

poł¡czenia.

Doinicjalizowaniarejestrówu»ywanyjest 32-bitowynumerramki.

Numerramkimo»epowtórzy¢si¦poupływie3,5godzinytransmisji.

Inicjowanierejestrów:

1.Dowszystkichrejestrówwprowadzanes¡równoleglebityklucza,bezstosowaniawyborurejestrów,

któres¡przesuwane.

2.Nast¦pniedorejestrówwprowadzanes¡22bitynumeruramki.

3.Wykonujesi¦100cyklimieszaj¡cych-zwykorzystaniemmechanizmuwyborurejestrówprzesuwnych.

114kolejnychbitówwyj±ciowychtworzykluczszyfruj¡cyramki.

1Kryptograﬁaasymetryczna

Szyfrysymetryczne Szyfryasymetryczne

1.Kluczszyfruj¡cyideszyfruj¡cys¡równelub

jedenłatwoobliczy¢zdrugiego

1.Wyznaczeniekluczadeszyfruj¡cegozklucza

szyfruj¡cegojestobliczeniowotrudne.

2.Kluczszyfruj¡cyjestpowszechnieznany.

Kluczdeszyfruj¡cyznatylkojegowła±ciciel.

3.Jestszybkie 3.Jestok.100razywolniejszeodszyfrowania

symetrycznego

4.Zapewniatylkopoufno±¢informacji 4.Zapewania: poufno±¢ ,umo»liwia uwierzy-

telnianie,integralno±¢iniezaprzeczalno±¢

Tabela1:Porównaniecechszyfrowaniasymetrycznegoiasymetrycznego

Podstaw¡konstrukcjialgorytmówasymetrycznychs¡:

1. Funkcjejednokierunkowe -funkcjeodwracalne;łatwoobliczy¢warto±¢funkcji,trudnoobliczy¢

warto±¢funkcjiodwrotnej(czyliwyznaczy¢argument x maj¡cwarto±¢ f ( x ))

2. Funkcjejednokierunkowezzapadk¡ -funkcjeodwracalne;łatwoobliczy¢warto±¢funkcji,trudno

obliczy¢warto±¢funkcjiodwrotnejbezu»yciapewnejdodatkowejinformacji.

3. Bezkolizyjnefunkcjeskrótu -funkcje,któreniekoniecznies¡odwracalne;wyznaczeniedwóchtakich

argumentów(ró»nych)dlaktórychwarto±¢funkcjijesttakasama,jestobliczeniowotrudne.

1.1Problemlogarytmudyskretnego

( G, • , 1)-grupaprzemiennasko«czona.

a 2 G izakładamy,»ezbiórró»nychelementówpostaci: a k ,k 2 N jestdu»y.

Podgrupacyklicznagenerowanaprzez a :

( a )= { a k : k 2 N }

2.Wymagauzgodnieniakluczyprzyu»yciubez-

piecznegokanału

Załó»my,»eliczbaelementówpodgrupy( a )jestrówna n .

Funkcjawykładnicza E X pa : Z n ! ( a ) jestzdeﬁniownanast¦puj¡co:

k 2 Z n −! E X pa = a k

E x p a jestodwracalna.Funkcj¦odwrotn¡nazywamy logarytmemdyskretnym:

Dlog a :( a ) −! Z n

Dla b 2 Z n :

Dlog a ( b )= k () b = a k

1.Je±li G = Z n towyznaczeniewarto±ciDlogjestłatwe.

2.Je±li p jestliczb¡pierwsz¡i G = Z p \{ 0 } (zoperacj¡mno»enia),towyznaczeniewarto±ciDlogjest

obliczeniowotrudne.

3.Je±li F q jestciałemsko«czonymi G = F q \{ 0 } towyznaczeniewarto±ciDlogjestobliczeniowotrudne.

4.Je±li G jestkrzyw¡punktównakrzywejeliptycznejnadciałemsko«czonym,towyznaczeniewarto±ci

Dlogjestobliczeniowotrudne.

y = ax 3 + bx + c

Równaniekrzywejeliptycznej:

y 2 = ax 3 + bx + c

G -zbiórpunktówkrzywejeliptycznej.

R = P + Q

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: