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:
kobylak94
Inne pliki z tego folderu:
Kryptografia - Wykład z podstaw klasycznej kryptografii z elementami kryptografii kwantowej.pdf
(352 KB)
Kryptografia - Szyfry.pdf
(178 KB)
Kryptografia z Elementami Kryptografii Kwantowej.pdf
(264 KB)
(Nie)bezpieczne aukcje.pdf
(1091 KB)
Piotr Majewski - Czas Na E-Biznes. Sprawdzone i skuteczne metody zarabiania w Internecie.pdf
(2849 KB)
Inne foldery tego chomika:
audiobook
C-S 1.6 non steam
dla laska
Dokumenty
Eska Live Rmx
Zgłoś jeśli
naruszono regulamin