Kryptografia - Szyfry.pdf

(178 KB) Pobierz
12379071 UNPDF
Notatkizkryptografii—szyfry
StanisławKlekot
11kwietnia2004
1Konwencje
Konwencjeprzyj¦tedalejwtek±cie:
funkcj¦boole’owsk¡XORb¦d¦oznacza¢symbolem
wiadomo±¢niezaszyfrowan¡b¦d¦nazywa¢jawnymtekstem,otwartymtekstem, plaintext albo
poprostuwiadomo±ci¡ioznacza¢symbolem M
przyszyfrachblokowychdługo±¢słowawej±ciowegob¦d¦oznacza¢symbolem w ,ailo±¢rund
algorytmusymbolem r
wiadomo±¢pozaszyfrowaniub¦d¦nazywa¢kryptogramemioznacza¢symbolem C
kluczu»ytydoszyfrowaniab¦d¦oznacza¢symbolem K ,ajegodługo±¢symbolem b
processzyfrowaniawiadomo±ci M przyu»yciuklucza K b¦d¦oznacza¢ C =E K ( M ),proces
odszyfrowywaniaza± M =D K ( C )
2Prostealgorytmydladanychdowolnejdługo±ci
2.1 One-timepad
Szyfry one-timepad s¡chybanajprostsz¡inajszybsz¡metod¡szyfrowania,je±limasi¦klucz.
Najcz¦±ciejstosowanymschematemjest C = M K (XORbitpobicie),cho¢mo»nau»ywa¢
innych: C = M + K mod n , C = M · K mod n albojakiejkolwiekinnejfunkcji1-1.
Wtymalgorytmiekluczjesttakdługijakwiadomo±¢,któr¡mazaszyfrowa¢.Zapewniato
bezpiecze«stwodoskonałe—dosłownie.adnemoceprzerobowenies¡wstaniezłama¢szyfru,
boka»dawiadomo±¢(sensownaczynie)jestrównoprawdopodobna,tzn.istniejedlaniejklucz
szyfruj¡cyj¡dorozpatrywanegokryptogramu.Bezznajomo±cikluczaniedajesi¦odszyfrowa¢
wiadomo±ci,jedyn¡informacj¡oryginalnegotekstu,którasi¦przedostaje,jestjegodługo±¢,aito
niejestpewne,bowiadomo±¢mo»naskompresowa¢albouzupełni¢losowymidanymi.
Wadyalgorytmu:
1.kluczjestniesamowiciedługi
1
2.kluczjestjednorazowy—doka»degoszyfrowaniatrzebagenerowa¢nowy(inaczejbezpie-
cze«stwowiadomo±cijestmocnonara»one)
3.łatwozmieni¢tekst,je±liznamyjegoformat(tojestwadawszystkichalgorytmówszyfruj¡-
cychstrumieniedanych)
2.2Szyfrystrumieniowe
Szyfry one-timepad s¡niewygodne,je±litrzebaprzesyła¢sporeilo±cidanych,któreniemusz¡by¢
idealnie bezpieczne,przedewszystkimzpowodudługo±cikluczau»ytegodoszyfrowania.Mo»na
u»y¢kluczakrótszegoigopowtarza¢,aletoniejestbezpieczne.Obecnieu»ywasi¦generato-
rówci¡gówpseudolosowych.Ustawiasi¦takigenerator,awyrzucanystrumie«bitówXORujesi¦
ztekstemjawnym.Jesttodo±¢dobrametodaprzesyłaniad¹wi¦kuiobrazu(ogólnie:danych„nie-
dokładnych”),alenienadajesi¦dotransmisjinp.fragmentówbazdanych,gdy»manipulowanie
danymiustalonegoformatujestproste(patrz:wada3wsekcji2.1)
2.2.1LFSR
We¹mypocz¡tkowywektor(tablic¦bitów)długo±ci n : IV = V 0 ,V 1 ,V 2 ,...,V n iwpiszmygodo
rejestru R otejsamejdługo±ci.Wektortengenerujeci¡g(pseudo)losowychbitów b 0 ,b 1 ,b 2 ,... :
w k -tymkrokuobliczamy R n +1 u»ywaj¡cniektórychbitówspo±ród R 0 ,R 1 ,...,R n iprzesuwamy
całyrejestrojednomiejsce( R 0 R 1 , R 1 R 2 ,..., R n − 1 R n , R n R n +1 ).Usuni¦tybit R 0
tojestnasz(pseudo)losowybit b k .
Tensposóbnosinazw¦ linearfeedbackshiftregister .Niejesttonajlepszysposóbgenerowania
losowychbitów.Wystarczypozna¢odpowiedniodu»obitówwyj±cia(2 n ),»ebypozna¢wewn¦trzn¡
struktur¦rejestru(tzn.rozpozna¢,którebity R k s¡u»ywanedogenerowania R n +1 ).
2.2.2A5
A5jestalgorytmemstosowanymwsieciachGSM.Opierasi¦naLFSR.U»ywatrzechrejestrów
odługo±ciach19,22i23bitów.Ci¡giemwynikowymA5jestXORwyj±¢rejestrów.Niewszyst-
kierejestrysi¦przesuwaj¡zaka»dymrazem.Stosowanejest„głosowanie”:branyjest±rodkowy
bitka»degorejestru(odpowiednio9-tyidwa11-te),aprzesuwanes¡terejestry,któreoddały
„wi¦kszo±ciowy”głos,tzn.je±liwypadło1,toprzesuwaj¡si¦rejestryz1na±rodkowejpozycji,
wprzeciwnymwypadkuprzesuwaj¡si¦rejestryz0.
3Szyfryblokowe
3.1Wymaganiadlaszyfrówblokowych
Szyfryblokoweró»ni¡si¦do±¢znacznieodszyfrówstrumieniowych.Przedewszystkimoperuj¡na
całychblokachdanych,nienapojedynczychbitach.Dodatkowowszystkiedobreszyfryblokowe
charakteryzuj¡si¦tzw.efektemlawinowym(zmianadowolnegobitukluczalubtekstujawnego
skutkujezmian¡okołopołowylosowychbitówkryptogramu).Obietecechyznacznieutrudniaj¡
modyfikacj¦pojedynczegobituwbloku—jakakolwiekzmianarozsypiesi¦pocałymtek±ciepo
odszyfrowaniu.Efektlawinowyzapobiegaatakowiprzezlokalneprzeszukiwanie,bokryptogramy
2
powstałeprzezzaszyfrowaniepodobnychwiadomo±citymsamymkluczem(albojednejwiadomo±ci
dwomapodobnymikluczami)ró»ni¡si¦praktycznielosowo,zatemniemo»nanatejpodstawie
oceni¢,jakbliskojeste±myzłamaniaklucza.
3.2SchematFeistela
Wi¦kszo±¢algorytmówblokowychopierasi¦oschematFeistela,czasemnazywanysieci¡Feistela.
Pomysłjestdo±¢prosty.Wiadomo±¢dzielimynadwierównecz¦±ci,zwyczajowonazywane L 0 i R 0 .
Nast¦pnieobliczamywarto±ci L 1 i R 1 :
L 1 = R 0
R 1 =f( K,R 0 ) L 0
Jakwida¢, R 0 pojednymkrokuwyst¦pujewtakimkryptogramiejawnie,zatemmusimywykona¢
conajmniejdwieiteracje.
Odszyfrowanieodbywasi¦analogicznie:
R n − 1 = L n
L n − 1 =f( K,R n − 1 ) R n =f( K,L n ) R n
Schemattenjestcałkiemwygodny,gdy»niewymaga,abyu»ytafunkcjafbyłaodwracalna.Nie
zakładamyoniejabsolutnieniczego,mogłabynawetby¢okre±lonajakof( K,M ) 0(cho¢taka
funkcjaniebyłabyzbytdobrymzabezpieczeniemdladanych).Całebezpiecze«stwoalgorytmujest
oparteodobrzedobran¡funkcj¦f.
3.3DESi3-DES
AlgorytmDESjestpodr¦cznikowymzastosowaniemschematuFeistela.Działana64-bitowych
blokach,u»ywaj¡c56-bitowego(8 × 7bitów)klucza,wykonuj¡c16cykli(podstawie«w/gsche-
matuFeistela).Przedpierwszymcyklemtekstjawnyjestpermutowany(permutacjajeststała).
Wsamymcyklupołówkadanych—32bity—jestrozszerzanado48bitów(tzw.permutacja
rozszerzaj¡ca).WynikjestXORowanyzpodkluczemdanegocyklu,atakwyliczonawarto±¢jest
dzielonanasze±¢o±miobitowychcz¦±ci,zktórychka»dajestprzepuszczanaprzeztzw. S-box .
S-box ytotablicerozmiaru4 × 16,wktórychwka»dymwierszuwyst¦puj¡wszystkieliczbyod
0do15.Pierwszyiostatnibit6-bitowegowej±ciakoduj¡numerwiersza,pozostałekoduj¡nu-
merkolumny.Poł¡czonewyj±cia S-box óws¡nast¦pniepermutowane(permutacjajeststała).Po
ostatnimcyklublokszyfrogramujestprzepuszczanyprzezpermutacj¦odwrotn¡dopermutacji
pocz¡tkowej.
Kluczdługo±ci56bitówjestdzisiajstanowczozbytkrótki.Niestety,znalezienie S-box ówdu»ych
rozmiarówirównieodpornychnaataki,cooryginalne,jesttrudne,zatembezpo±redniewydłu»anie
DESajestwykluczone.Zamiasttegostosujesi¦szyfrowaniewielokrotnezu»yciemró»nychkluczy:
3-DES K 1 ,K 2 ,K 3 ( M )= E K 3
D K 2 E K 1 ( M )
przyczym K 3 cz¦stojesttakisam,jak K 1 —wtedykluczmadługo±¢112bitów,agdy K 2 = K 1
albo K 2 = K 3 —mamyszyfrowanieklasycznymDESem(cotłumaczydeszyfrowaniewdrugim
kroku).
Dlaczegoniedwukrotneszyfrowanie?Atak knownplain-text napodwójnyDESniejestzna-
cz¡cotrudniejszyni»naDES.Szyfrujemyznan¡wiadomo±¢wszystkimi(2 56 )kluczamidlaDES,
akryptogramdeszyfrujemywszystkimikluczami.Wystarczyterazznale¹¢kryptogrampo±redni
3
wyst¦puj¡cywobutablicach.Tametodaatakunosinazw¦ meetinthemiddle .Zło»ono±¢tego
atakuwynosizaledwie2 · 2 56 szyfrowa«+przeszukiwaniedwóchdu»ychtablic.Nietegosi¦spo-
dziewali±mypodwukrotnymwydłu»eniuklucza.
3.4RC5
RonRivestzaproponowałzgrabnyalgorytmszyfrowania.Ilo±¢cykli r ,długo±¢szyfrowanegobloku
w idługo±¢klucza b s¡tusparametryzowane,coczyniszyfrbardzoelastycznym.Napocz¡tku
kluczjestdzielonynapodklucze K 0 ,K 1 ,...,K 2 r ,K 2 r +1 ,awiadomo±¢nadwiepołówki L 0 + S 0
i R 0 + S 1 ,doktórychs¡dodanepierwszedwapodklucze.Pojedynczarundajestbardzoprosta:
L i = ( L i − 1 R i − 1 ) n R i − 1 + K 2 i
R i = ( R i − 1 L i ) n L i + K 2 i +1
Mo»natozapisa¢przyu»yciudwóchrejestrów:
L = ( L R ) n R + K 2 i
R = ( R L ) n L + K 2 i +1
Symbol n oznaczaoperacj¦przesuni¦ciacyklicznegowlewo.Wszystkieoperacjeodbywaj¡si¦
modulo2 w .
3.5Szyfrowaniedługichtekstów
Algorytmyblokoweniepotrafi¡samezsiebieszyfrowa¢tekstówjawnychoinnejdługo±cini»
przewidzianadlaalgorytmu,jednakumiej¦tniedziel¡cmo»naszyfrowa¢danetak»einnejdługo±ci.
Poni»szesposobyzakładaj¡,»ewiadomo±¢składasi¦zpełnychblokówwej±ciowychdlaszyfru.T¡
własno±¢mo»nauzyska¢naprzykładuzupełniaj¡cwiadomo±¢zerami( padding ).
3.5.1 ElectronicCodeBook
Najprostszymsposobemjestpodzieli¢wiadomo±¢ M nabloki M 0 ,M 1 ,M 2 ,...,M n po w bitów,
poczymzaszyfrowa¢ka»dyblokniezale»nie:
C i =E K ( M i )
Szyfruj¡ctymsposobemjedendu»yplikdostarczamyatakuj¡cemudu»o(dokładnie n )krypto-
gramów,conapewnonieutrudniazłamaniaklucza.Pozatym,je±liszyfrujemytaktransmisj¦,
atakuj¡cemujestłatwoj¡zmodyfikowa¢wstawiaj¡cfragmentwcze±niejszy—niezorientujemy
si¦,»eco±jestnietak,oileniezastosowali±myinnychmetodkontrolispójno±cidanych.Zdrugiej
strony,je±lipodczasszyfrowaniaalbotransmisjikryptogramunast¡pibł¡dnajednymbicie,stra-
conyjesttylkojedenblokwiadomo±ci,zmiananiewpływanapozostałebloki(cho¢przezjeden
bittracimy cały bloktekstu).
3.5.2 CipherBlockChaining
Mo»emyuzale»ni¢fragmentkryptogramu C i odwynikuszyfrowaniapoprzedniejrundy C i − 1 .
Sposóbjestdo±¢łatwy:
C − 1 = IV
C i =E K ( C i − 1 M i )
4
IV jestlosowymwektorempocz¡tkowym( initialvector ).Niemawi¦kszegosensugoszyfrowa¢.
E K ( IV )jesttaklosowy,jaksam IV ,pozatym C 0 trzebabytraktowa¢wszczególnysposób.
Ponadto,je±liuzna¢pierwszyblokwiadomo±ci M 0 zanieistotny,to IV 0 =E K ( M 0 )dlaci¡gu
M 1 ,M 2 ,...,M n jestpodanyjawnymtekstem.
CBCmakilkaciekawychwłasno±ci.
1.Wiadomo±¢dwukrotnieszyfrowanatymsamymkluczemdaró»nekryptogramy,atakuj¡cy
niemo»ezatemstwierdzi¢,czywysyłanajestdokładnietasamawiadomo±¢,coostatnio.
2.Je±lipodczasszyfrowaniauszkodzeniuuległjedenblokkryptogramu,straconyjesttylkoten
jedenblok:doszyfrowanianast¦pnegozostału»ytytenuszkodzonyblok,wi¦cje±lizostanie
u»ytydodeszyfrowania,bł¡d„zniknie”.
3.Je±li i -tyblokkryptogramuuległuszkodzeniupodczastransmisji,straconyjestwtek±cie
jawnymblok M i iuszkodzonebityzbloku M i +1 .
4.Utratasynchronizacji(zgubienielubznalezienienadmiarowegobitu)wbloku i powoduje
utrat¦ wszystkich blokówpocz¡wszyod i .
3.5.3 CipherFeedBack
Szyfryblokowemo»nazamieni¢naszyfrystrumieniowe„sprz¦rzone”zszyfrowanymidanymi.
C i = P i E K ( C i − 1 )
Dzi¦kitejtechnicemo»naprzesyła¢nawetniepełneblokidanych,np.pojednymznakuASCII
(8-bitowyCFB).Wystarczyutworzy¢rejestr R owielko±ci w (długo±¢blokuwej±ciowegoalgo-
rytmuszyfruj¡cego)iwypełni¢golosowym IV .Poprzesłaniuporcjidanych(naszegoo±miobi-
towegoznaku)ustawiamywysłanykryptogramnapocz¡tkurejestruprzesuwaj¡creszt¦.Porcj¦
danychnatomiastnale»yzXORowa¢ztym,cowyjdziepozaszyfrowaniurejestru: c = m E K ( R )
( m —porcjadanychdowysłania).
3.5.4 OutputFeedBack
Mo»najeszczeszyfrblokowyzamieni¢nageneratorbitówpseudolosowych.Niechlosowy R − 1 = IV
mawielko±¢ w .Wtedy
R i =E K ( R i − 1 )
Takigeneratordajemaksymalnie2 ( b + w ) cykli,coju»dlaDESadaje2 120 mo»liwychci¡gów
(pseudo)losowych 1 .
Wynikdziałaniatakiegogeneratora,jaknietrudnosi¦domy±li¢,jestaplikowanydotekstujawnego
bitpobicie.
1 taknaprawd¦b¦dzieichmniej,boDESmaparykluczy,któremo»nastosowa¢wymiennie,jednakniezdarzaj¡
si¦onezbytcz¦sto
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin