Spis rzeczy
1Pierwszyrzutokanakryptogra e, 4
1.0.1Szyfrowaniedanych: : : : : : : : : : : : : : : : : : :4
: : : :
1.0.2Podstawowezastosowaniatechnikszyfrowania: : : : :5
: : : :
1.0.3Historiakryptogra i: : : : : : : : : : : : : : : : : : :8
: : : :
1.0.4Kontrowersjezwiazanezestosowaniemkryptogra i: :9
: : : :
,
1.0.5Korzystaniezprodukt owkryptogra cznych: : : : :10
: : : : :
2Podstawowetechnikiszyfrowania 12
2.0.6Podstawienie: : : : : : : : : : : : : : : : : : : : : :12
: : : : :
2.0.7XORione-timepad: : : : : : : : : : : : : : : : : :13
: : : : :
2.0.8S-boksy: : : : : : : : : : : : : : : : : : : : : : : : :15
: : : : :
3Algorytmysymetryczne 18
3.1DES{DataEncryptionStandard: : : : : : : : : : : : : :18
: : : : :
3.1.1SzyfrowanieDES-em: : : : : : : : : : : : : : : : : :19
: : : : :
3.1.2DeszyfrowanieDES-em: : : : : : : : : : : : : : : :21
: : : : :
3.2TrzykrotnyDES: : : : : : : : : : : : : : : : : : : : : : : :21
: : : : :
3.3Szyfrowanietekst owdowolnejdlugo sci: : : : : : : : : : : :21
: : : : :
3.3.1Elektronicznaksia_kodowa: : : : : : : : : : : :22
zka: : : : : :
,
3.3.2CipherBlockChaining: : : : : : : : : : : : : : : : :23
: : : : :
3.3.3CypherFeedback: : : : : : : : : : : : : : : : : : : :23
: : : : :
3.4IDEA: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :24
: : : : :
3.4.1SzyfrowaniepoprzezalgorytmIDEA: : : : : : : : :25
: : : : :
3.4.2GenerowaniepodkluczydlaalgorytmuIDEA: : : :25
: : : : :
3.4.3DeszyfrowanieprzezIDEA: : : : : : : : : : : : : :25
: : : : :
4Algorytmyniesymetryczne 29
4.0.4Teoriazlozono sciobliczeniowejakryptogra a: : : :29
_ : : : : :
4.0.5Szyfryplecakowe: : : : : : : : : : : : : : : : : : : :30
: : : : :
4.1RSA: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :32
: : : : :
4.1.1OpisalgorytmuRSA: : : : : : : : : : : : : : : : : :33
: : : : :
4.1.2Testypierwszo sci: : : : : : : : : : : : : : : : : : : :35
: : : : :
4.1.3AspektybezpieczenstwaRSA: : : : : : : : : : : : :37
: : : : :
4.1.4Trudnebitykryptogram owRSA: : : : : : : : : : :39
: : : : :
4.2AlgorytmElGamala: : : : : : : : : : : : : : : : : : : : : :41
: : : : :
5Funkcjejednokierunkowe 43
5.0.1Kandydacinafunkcjejednokierunkowe: : : : : : : :44
: : : : :
5.0.2Hard-corebit: : : : : : : : : : : : : : : : : : : : : :45
: : : : :
i
SPIS RZECZY ii
6Jednokierunkowefunkcjehashujace 46
,
6.0.3Wlasno sciizastosowaniafunkcjihashujacych: : : :46
: : : : :
,
6.0.4Atakiprzeciwfunkcjomhashujacym: : : : : : : : :47
: : : : :
,
6.1Technikiodowodliwychwlasno sciach: : : : : : : : : : : : :49
: : : : :
6.1.1Hashowanieprzypomocydyskretnegologarytmu: :49
: : : : :
6.1.2Rozszerzenienatekstydowolnejdlugo sci: : : : : : :50
: : : : :
6.2Praktycznealgorytmyhashujace: : : : : : : : : : : : : : :51
: : : : :
,
6.2.1MD5: : : : : : : : : : : : : : : : : : : : : : : : : : :51
: : : : :
6.2.2Hashowaniedowolniedlugichtekst ow: : : : : : : :52
: : : : :
7Ciagipseudolosowe 55
,
7.0.3Wlasno sciciag owpseudolosowych: : : : : : : : : :55
: : : : :
,
7.0.4Generatoryciag owpseudolosowych: : : : : : : : : :57
: : : : :
,
7.0.5Pseudolosowo s cgeneratoraBBS: : : : : : : : : : :59
: : : : :
7.1Zastosowaniaciag owpseudolosowych: : : : : : : : : : : : :59
: : : : :
,
7.1.1Szyfrowaniestrumieniowe: : : : : : : : : : : : : : :59
: : : : :
7.1.2Szyfrowanieprobabilistyczne: : : : : : : : : : : : :60
: : : : :
8Podpisycyfrowe 61
8.0.3PodpisycyfroweElGamala: : : : : : : : : : : : : :62
: : : : :
8.0.4DSA: : : : : : : : : : : : : : : : : : : : : : : : : : :63
: : : : :
8.0.5Slepepodpisy: : : : : : : : : : : : : : : : : : : : : :64
: : : : :
8.0.6Kanalpodprogowy: : : : : : : : : : : : : : : : : : :65
: : : : :
8.0.7Podpisyniezaprzeczalne: : : : : : : : : : : : : : : :66
: : : : :
9Uwierzytelnianie 69
9.0.8Protok olchallengeandresponse: : : : : : : : : : :69
: : : : :
9.0.9Dowodyinterakcyjne: : : : : : : : : : : : : : : : : :70
: : : : :
9.0.10Dowodyzwiedza,zerowa, : : : : : : : : : : : : : : :71
: : : : :
9.0.11Protok olFiege-Fiata-Shamira: : : : : : : : : : : : :73
: : : : :
9.0.12Protok olSchnorra: : : : : : : : : : : : : : : : : : :74
: : : : :
9.0.13Protok olGuillou-Quisquartera: : : : : : : : : : : :75
: : : : :
9.0.14Podpisycyfrowepoprzezuwierzytelnianie: : : : : :76
: : : : :
10Administracjakluczami 77
10.1Praktykagospodarkikluczami: : : : : : : : : : : : : : : : :77
: : : : :
10.1.1Urzadzeniekryptogra czne: : : : : : : : : : : : : :77
: : : : :
,
10.1.2Generowaniekluczy: : : : : : : : : : : : : : : : : :78
: : : : :
10.1.3Hierarchiakluczy: : : : : : : : : : : : : : : : : : : :79
: : : : :
10.1.4Przechowywaniekluczy: : : : : : : : : : : : : : : :79
: : : : :
10.2Protokolyuzgadnianiakluczy: : : : : : : : : : : : : : : : :80
: : : : :
10.2.1Uzgadnianiekluczypoprzezszyfrowaniesymetryczne:81
: : : :
10.2.2Uzgadnianiekluczaprzezszyfrowanieasymetryczne:82
: : : :
10.2.3Protok olDi e-Hellmanaijegopochodne: : : : : :82
: : : : :
11Protokolykryptogra czne 85
11.0.4Atakmaninthemiddle: : : : : : : : : : : : : : : :85
: : : : :
11.0.5Dzielenietajemnic: : : : : : : : : : : : : : : : : : :87
: : : : :
11.0.6Zobowiazaniebitowe: : : : : : : : : : : : : : : : : :88
: : : : :
,
11.0.7Pieniadzecyfrowe: : : : : : : : : : : : : : : : : : :90
: : : : :
,
11.0.8Elektronicznewybory: : : : : : : : : : : : : : : : :93
: : : : :
SPIS RZECZY iii
12Kryptoanaliza 95
12.0.9Kryptoanalizar o_: : : : : : : : : : : : : : :96
znicowa: : : : : :
12.0.10Kryptoanalizaliniowa: : : : : : : : : : : : : : : : :99
: : : : :
12.0.11R o_kryptoanalizabled ow: : : : : : : : : :100
znicowa : : : : : :
,
13Wybraneimplementacje 102
13.0.12Smartcards: : : : : : : : : : : : : : : : : : : : : :102
: : : : : :
13.0.13Krzyweeliptyczne: : : : : : : : : : : : : : : : : :103
: : : : : :
13.0.14Kerberos: : : : : : : : : : : : : : : : : : : : : : :103
: : : : : :
13.0.15Zabezpieczaniekomunikacjitelefonicznej: : : : : :106
: : : : : :
13.0.16PGP{PrettyGoodPrivacy: : : : : : : : : : : :107
: : : : : :
13.0.17Zabezpieczaniepocztyelektronicznej{PEM: : :108
: : : : : :
13.0.18BezpieczenstwowWWW: : : : : : : : : : : : : :109
: : : : : :
13.0.19Protokolyobrotu nansowego: : : : : : : : : : : :109
: : : : : :
AWybraneaspektyteoriiliczb 112
BTeoriaalgorytm ow 116
Przedmowa
Doniedawnakryptogra abylaobiektemzainteresowaniawwiekszymstopniusluzb
_
,
wywiadowczychiwojskanizprzedmiot owgospodarczychiprywatnychos ob.Postep
_
,
wdziedzinieelektronikiazwlaszczagwaltownyrozw ojsiecikomputerowychsytuacje,
te,zmienilywradykalnyspos ob.
Dawniej,gdyprywatnyuzytkownikdysponowaljedyniekomputeremPCnie
_
wlaczonymdosieci,ochronadanychbylastosunkowoprostaizapewnionaprzez
,
zycznydostepdokomputera.Natejsamejzasadziechronionebylydaneprzecho-
,
wywanewpostacielektronicznejprzezmale rmy,dzialy rm,organizacjepolitycz-
ne.Nieskomplikowaneprotokolykryptogra czne,alekluczdopomieszczeniazkom-
puterem,czykoperta,wkt orejprzesylanabyladyskietka,stanowilyochrone,przed
niepowolanymdostepem.Oczywi sciezdarzalysie,kradziezedyskietek,komputer ow,
_
,
wlamaniadosiedzibpartiipolitycznych:.Wiekszo s cuzytkownik ownieczulo
: : _
,
jednakpotrzebyskuteczniejszejochronyswychdanych.
Sytuacjazacze,lasie,radykalniezmienia czchwila,gwaltownegowzrostusieci
komputerowych.Dotyczylotonietylkosieciobejmujacychszeregdzial owpojedyn-
,
czych rm,aleisieciglobalne,takiejakInternet(wtymzwlaszczaWorldWide
Web).Zapewnieniebezpieczenstwawtychsieciachstalosie,jednymzpierwszo-
planowychzadandecydujacychoichdalszymrozwoju.Nowetechnikitelekomu-
,
nikacyjne,takiejaktelefoniakom orkowa,telewizjacyfrowa,telebanking,itp.,nie
moglybyznale z cswegomiejscawcodziennejpraktyce,gdybyniestosowanietechnik
kryptogra cznychdlaochronydostepu.
,
Najpierwrewolucjaobje,lakomunikacje,w srodowiskunaukowym.Pojawienie
sie,pocztyelektronicznejumozliwiloblyskawicznekontaktowaniesienaukowc owz
_
najdalszychkraj ow.Pozwolilotonaolbrzymiwzrostwydajno sciwwieludziedzi-
nachbadan.Moznabysie,spodziewa c,zekonkurencjaiostrawalkaoprzodownictwo
_ _
doprowadziw srodowiskunaukowymdowielunaduzy cpocztyelektronicznej.Tym
_
bardziej,zeniejesttrudnenaprzykladprzesla clistwtenspos ob,bynadawcapo
_
nagl owkum oglby cprzekonany,zepochodzionodinnejosoby.Mozliwejestr owniez
_ _ _
przechwytywaniekorespondencjiprzeznaczonejdoinnychadresat ow.Zjawiskate
jednakstanowilydotychczaswcalym srodowiskunaukowymbardzowaskimargines.
,
Powodemzapewnebyloto,izkomunikowalysie,osoby,kt oreitakobdarzalysie,
_
pelnymzaufaniem.Takwiecmetody,kt orepozwalalybynazabezpieczenieprzed
,
odczytem,mody kacja,czytezpreparowaniemlist owelektronicznychprzezosoby
_
trzecieniebylystosowane.
Teczasymine,ly.Wrazzpojawieniemsie,WorldWideWebInternetstalsie,
atrakcyjnydlaszaregouzytkownika\.WInterneciepojawilysie,interesujacezasoby
_
,
"
informacyjne,dziekiczemuilo s cuzytkownik owzacze,larosna cgwaltownie.Co
_
, ,
wiecej,Internetcorazcze sciejjestuzywanyniejakonarzedziezabawyczyrozwijania
_
, , ,
zainteresowa aledocel owkomercyjnych.Juzdzi sbiletylotniczekupuje,przez
n, _
Internet,literature,naukowa,wybieramprzezWorldWideWeb,azamiastkupowa c
gazete,zlokalnymiogloszeniamisiegamdojejelektronicznegoodpowiednika.W
,
takiejsytuacjibedziecorazwiecejos ob:hardwaretanieje,softwarestajesie,coraz
, ,
latwiejszydoobslugiprzezlaika,wwielukrajachpolaczeniatelefonicznewskutek
,
1
SPIS RZECZY 2
konkurencjinarynkutelekomunikacyjnymstaja,sie,tanszeiwyzszejjako sci.Coraz
_
latwiejszebedziezatemstaniesie,kolejnymuzytkownikiemInternetu.Zapare,lat
_
,
bedziemymie czapewnedoczynieniazsytuacja,gdyInternetbedzienajwiekszym
, , , ,
supermarketem,najobszerniejsza,gazeta,najwiekszymHydeParkiem,:{przynaj-
: :
, ,
mniejwkrajach,gdzieuslugitelekomunikacyjnebeda,wystarczajacotanie.
, ,
Jakka_wynalazek,rozw ojglobalnychsiecikomputerowychprzynosikorzy sci,
zdy
aleiniebezpieczenstwa.Wieledyskutujesie,naprzykladnatematmozliwo sci
_
wykorzystywaniaInternetuprzezorganizacjeprzestepcze.Sytuacjaprzypomina
,
niecosporypowynalezieniusamochodu.Niespos obcze sciowonieprzyzna cracji
,
przeciwnikomautomobilimajacprzedoczymatragicznestatystkiotysiacachludzi
, ,
zabitychnadrogach.Niecofne,lotojednakmotoryzacji,takjakniedoodwr ocenia
jestjuzrozw ojglobalnejsiecikomputerowejna swiecie.
_
Poniewa_poprzezInternetkomunikowa csie,beda,niedobrzyiufajacysobie
z
, ,
znajomi,leczczestoanonimowiczywrodzysobieuzytkownicy,mijaja,czasy,gdy
_
,
niezbytwielemy slanoobezpieczenstwiedanychikomunikacji.Zjednejstrony
podlaczeniedosiecikomputerowychstanowi cbedziewarunekwstepnyistnienia
, , ,
rm(takjakposiadanietelefonu,faxu,czyskrzynkipocztowej),zdrugiejstrony
podlaczenietostanowiomozliwo sciwlaman,dewastacjidanychiinnychdzialano
_
,
charakterzeprzestepczym.
,
Oczywi scieuzytkownicysiecikomputerowychbeda,siebroni cprzedniepowo-
_
,
lanymdostepemdodanychczymanipulacjamidokonywanyminanich.Pierwsza,
,
linia,obronybeda,oczywi sciesystemyoperacyjnezarzadzajacepraca,komputer owi
, , ,
wykonywaniemzlecennarzeczuzytkownik ow.Wwielumiejscachruchuwsieciach
_
komputerowych(kt oreuzyskalyjuzmodna,nazwe,)sprawdzanebeda,
_ infostrad
,
"
bilety\,apasazerowienagape,\beda,usuwanizruchu.R ownocze sniezadaniem
_
,
"
systemuoperacyjnegobedzieprzestrzeganie,czyuzytkownicydokonuja,jedyniedo-
_
,
zwolonychoperacji.
Wskutekzlozono scistawianychzadansystemyoperacyjnebeda,stawa csie,coraz
_ ,
bardziejskomplikowane.Tymsamymcoraztrudniejbedzieichtw orcomprzewidzie c
,
wszystkiemozliwo sci,takabyuniemozliwi cominieciezabezpieczenzainstalowanych
_ _
,
poprzezsystemoperacyjny.Dotychczasowedoniesieniaztegopolawalkisa,raczej
pesymistycznedlasystem owoperacyjnych.Stoja,onewobliczumiazdzacejprzewagi
__
,
wlamywaczyzwanychhackerami.Hackerzyniesa,jakbysie,chcialowierzy c,jedynie
,
grupa,nastoletnichmaniak owkomputerowych(czylagodniejm owiac,milo snik ow
,
technikkomputerowych).Jesttogrupaoolbrzymimpotencjaleintelektualnym,
nierzadkodoskonalymzapleczusprzetowymi nansowym.
,
Ostatnia,szansa,nazagwarantowaniebezpieczenstwadanychjestkryptogra a.
Niemozeonausuna cwszelkichniebezpieczenstw(jaknaprzykladzniszczenieda-
_
,
nychprzezwlamywaczakomputerowego),alewwielusytuacjachskuteczniepomaga
(naprzykladuniemozliwiaodczytdanychprzezniepowolana,osobe).Wodr o_
_ znieniu
,
doinnychmetodkryptogra adostarczametodwzgledniebezpiecznych.Takbez-
,
piecznych,zeliniamitelekomunikacyjnymidokonujesie,cochwilaprzelew ownie-
_
wyobrazalnychdlaszaregoczlowiekasum.Iniktsie,niemartwi,zekto swlaczysie,
_ _
,
nalinie,ita,droga,powiekszystanswegokontaoile smilion owdolar ow(zkt orymi
,
odlecinatychmiastnawyspypoludniowegoPacy kudokraju,zkt orymzapomniano
zawrze cumowe,oekstardycjiprzestepc ow).
,
MiroslawKutylowski
Wstep
,
Niniejszaksia_mazazadaniewbardzozwiezlyspos obprzedstawi cpodstawowe
zka
, ,
metodykryptogra czne.Wieleinteresujacychtechnikkryptogra cznychzostalow
,
niejpominietych.Naciskpolozonyzostalnateaspekty,kt oremaja,bad zmie cmoga,
_
, ,
praktycznezastosowanie.Wskutektegowieleteoretycznieciekawychzagadnien
swiadomienieporuszamywtejksia_Zdrugiejstrony,naszymzamyslembylo,na
zce.
,
tylenailetojestmozliwewtakkr otkiejpozycji,umozliwi cczytelnikowizrozumienie
_ _
matematycznychmechanizm owtkwiacychwkryptogra i.Tymksia_tar o_sie,
zkazni
, ,
naprzykladoddostepnejnapolskimrynkupozycjiBruce'aSchneiera[6],majacej
, ,
bardziejcharakterencyklopediinizpodrecznika.
_
,
Niniejszaksia_przeznaczonajestdlastudent owinformatykiipokrewnych
zka
,
dziedzin.Mozeby cwykorzystanajakopodrecznikdosemestralnegowykladuzkry-
_
,
ptogra i,jakr owniezjakomaterialdosamodzielnegostudiowania.Dozrozumie-
_
nianiekt orychcze sciksia_niezbednajestznajomo s cpewnychfakt owzalgebry.
zki,
, ,
Czytelniknieobeznanyztymizagadnieniamimozeznale z cbrakujaceinformacjew
_
,
DodatkuA.Niekiedykoniecznajestznajomo s cstandardowychfakt owzpodstaw
informatykiwykladanychnapierwszychlatachstudi owinformatycznych.Cze s c
,
tychpoje cskr otowoprzedstawiamywDodatkuB.
,
Niniejszaksia_opartajestnacze sciskryptudowykladuMiroslawaKutylow-
zka
, ,
skiego.Wykladtenodbylsie,naWydzialeMatematykiiInformatykiUniwersytetu
Paderbornwsemestrzezimowym1995roku.Wspomnianyskryptobejmujepr ocz
kryptogra izagadnieniakod owsamokorygujacychbledyikompresjidanych.Jest
, ,
ondostepnypoprzezWorldWideWebpodadresem
,
http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/ikk95/skript. ps.gz
Listazauwa_bled ow,uzupelnienia,itp.znajduja,sie,wWorldWideWeb
zonych,
podadresem
http: //www. uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/kryptogra a/
Pragniemypodziekowa clicznymstudentomzaudzielona,pomoc.Wszczeg olno-
,
sciwymieni cchcieliby smyGuidoHaeselera,kt oregonotatkidowykladuwLatex-u
bylypodstawa,pierwszejwersjiskryptu(iszeregurysunk owzawartychwksia_
zce).
,
Cze s crysunk owzostalawykonanaprzezFrankaBesteiEwe,Kutylowska.
, ,
3
Rozdzial1
Pierwszy rzut oka na
kryptogra e
,
1.0.1 Szyfrowanie danych
Najwa_polezainteresowa kryptogra i(aleobecniejuzniejedyne)toszyf-
zniejsze n _
rowaniedokument ow.Zorginalnegodokumentu(mozetoby ctekst,zakodowany
_
cyfrowoobraz,zakodowanycyfrowod zwiek,:)zwanegotekstemjawnymmozna
: : _
,
stworzy cjegozaszyfrowana,wersje,zwana,kryptogramem.Dozaszyfrowaniaide-
szyfrowanianiezbednyjestdodatkowokluczlubklucze.Zewzgledunawlasno sci
, ,
kluczyrozr o_nastepujacemetodyszyfrowania:
zniamy, ,
Algorytmysymetryczne:kluczdoszyfrowaniaideszyfrowaniasa,identyczne
(lublatwowyprowadzalnejedenzdrugiego).
szyfrowaniekluczemK
-
6
?
tekstjawny zaszyfrowanytekst(kryptogram)
6
?
deszyfrowaniekluczemK
Rysunek1.1:Symetrycznametodaszyfrowania
Algorytmyasymetryczne:(zwanetakzealgorytmamizkluczemjawnymlub
_
kluczempublicznym)kluczedoszyfrowaniaideszyfrowaniasa,r o_prak-
zne
tycznieniepowinnoby cmozliwewyprowadzeniezjednegoznichpasujacego
_
,
drugiegokluczaumozliwiajacegooperacje,odwrotna.
_
, ,
Jakopodstawowa,zasade,nalezyprzyja c,zedeszyfrowanieprzypomocyniewla s-
__
,
ciwegokluczaniepowinnopraktyczniedostarcza czadnychinformacjiotek scie
_
jawnym.
Wramachkryptogra irozwa_r owniezmetodylamaniaszyfr ow,lubina-
zamy_
czejkryptoanalizy.Chodziotoby,naprzyklad,napodstawiekryptogramu
znale z codpowiadajacymutekstjawnylubzastosowanydoszyfrowaniaklucz.
,
4
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 5
1.0.2 Podstawowe zastosowania technik szyfrowania
Ochronadanychprzedniepowolanymodczytem
Realizacjategocelunastepujepoprzezszyfrowaniedanychprzypomocyalgorytm ow
,
symetrycznych.
Polazastosowa
n:
Zapisdanychnano snikach(dyskiitp.)niegwarantujacychochronyprzedodczy-
,
temprzezniepowo laneosoby:Danetesa,zapisywanejedyniewpostacikrypto-
gramu tylkoposiadaczodpowiedniegokluczamozezkryptogramuodtworzy c
_
orginalnytekst.
Zabezpieczeniekomunikacjiprzeprowadzanejliniaminarazonaminapods luch:na
_
przykladtegorodzajuzabezpieczenieniezbednejestwprzypadkuelektro-
,
nicznegodokonywaniaoperacjigieldowych{podsluchdokonywanychzam o-
wiendostarczalbyinformacjipozwalajacynaefektywna,spekulacje,gieldowa.
, ,
Jeszczewiekszeniebezpieczenstwawiaza csie,moga,zmozliwo sciamizmianw
_
, ,
przesylanychinformacjach,naprzykladwwypadkuelektronicznegoobrotu
pieniedzypomiedzybankami.Szyfrowanienieeliminuje zycznejmozliwo sci
_
, ,
zakl oceniakomunikacjibad zdokonywaniawniejzmian.Jednakzmianydo-
,
konywanebezznajomo sciodpowiedniegokluczapowoduja,powstawaniechao-
tycznychtekst owpoodszyfrowaniuprzezprawowitegoodbiorce,uzywajacego
_
,
prawidlowegoklucza.Wtenspos obpr obaoszustwazostajewykryta.
Uwierzytelnianiedokument ow
Uwierzytelnianiedokument owmozenastapi cprzypomocyalgorytm owasymetry-
_
,
cznych.Alicepublikuje(naprzykladnaswejstroniewWorldWideWeb)jedenz
dwupasujacychdosiebiekluczy,mianowicietensluzacydodeszyfrowania(dlatego
_
, ,
klucztennazywamykluczemjawnymlubkluczempublicznym).Drugizpary
kluczyjestprzezAlicepilniestrzezonyiniejestpodawanydoniczyjejwiadomo sci.
_
Klucztennazywamykluczemprywatnym.Uwierzytelnianiedokument owprzez
Aliceodbywasie,poprzezszyfrowanieichprzypomocyjejprywatnegoklucza(patrz
rys.1.2).Jesttomozliweponiewa_
_ z:
KazdymozeprzypomocypublicznegokluczaAliceodzyska corginalnytekst.
__
Je slikryptogramniebylwygenerowanyprzypomocyprywatnegokluczaAlice,
todeszyfrowanieprzypomocykluczaAlicedajewwynikutekstbedacychao-
, ,
tycznymciagiemznak owbezzadnego sladusensu.Gwarantujeto,zejedynie
_ _
,
posiadaczprywatnegokluczaAlicemozeta,droga,uwierzytelnia cdokumenty
_
wimieniuAlice.
Natejsamejzasadziepomyleniekluczapublicznegowtrakciedeszyfrowania
r owniezdajewwynikutekstbedacychaotycznymciagiemznak ow.Dzieki
_
, , , ,
temuniejestmozliweprzypisanietekstuniewla sciwemuautorowi.
_
Ochronaprywatno scielektronicznejkorespondencji
Asymetrycznealgorytmyszyfrowaniamoznauzy cr owniezdlaochronyelektronicz-
___
nejkorespondencji.Przesylaniekorespondencjielektronicznejlaczysie,bowiemz
,
wielomaniebezpieczenstwami.Kto smajacykontrole,nadwezlemInternetu,przez
, ,
kt oryprzesylanyjestlist,mozelisttenzniszczy c,zmody kowa c,albowreszcie
_
przekaza cgokomu sinnemu.Abyzapobiecprzynajmniejdw omostatnimmoz-
_
liwo sciommoznauzy cscenariuszaopisanegoponizej.Przedniszczeniemlist ow
__ _
kryptogra aniejestnaswstanieuchroni c.
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 6
' $ $
'
-
tekstorginalny kryptogram
szyfrowanie
kluczem
deszyfrowanie
prywatnym
kluczem
K
publicznym
Alice 0
K
& %
?
tekstorginalny
Bob
& %
Rysunek1.2:Uwierzytelnianieprzezszyfrowanie
Zal o_izAlicechcebezpiecznieotrzymywa ckorespondencje.Wtymcelu
zmy,_
,
Alicemusidysponowa cpara,pasujacychkluczydlaasymetrycznegoalgorytmuszy-
,
frujacego.KluczdoszyfrowaniazostajeprzezAliceopublikowany,naprzykladpo-
,
przezWorldWideWeb.GdyBobpragniewysla clistdoAlice,wtedywykonywane
sa,nastepujacekroki(patrzrys.1.3):
, ,
Bobzaopatrujesie,wkluczK,publicznykluczAlice.
BobszyfrujetekstswegolistudoAliceprzypomocykluczaK.
Bobwysylazaszyfrowanylistpoczta,elektroniczna,doAlice(wzalezno sciod
_
stosowanegosystemu,koniecznamozeby ckonwersjazplikuzawierajacego
_
,
kryptogramzpostacibinarnejnatekstowa,byunikna czmianwprowadzanych
, ,
przezprogrampocztowy).
Alicedeszyfrujeotrzymanylistprzypomocyswegoprywatnegokluczaiotrzy-
mujewtenspos oborginalnylist.
Powyzszyprotok olgwarantuje,zetylkoAlicejestwstanieodkodowa cprze-
_ _
znaczonedoniejlisty.Takwiecprzechwyceniekorespondencjiprzezosobytrzecie
,
przestajeby cniebezpieczne.R owniezpr obywprowadzaniazmianwzaszyfrowanym
_
li scie(nawetna slepo)jestskazanananiepowodzenie{wszystkierozsadnealgo-
,
rytmyszyfrujacemaja,wlasno s c,zezmianacho cbyjednegobituwkryptogramie
_
,
powodujeolbrzymiezmianywtek sciepodeszyfrowaniu,wskutekczegotekstten
maposta cprzypadkowegociaguznak ow.
,
Oczywi sciebezpieczenstwokorespondencjimiedzyAliceiBobemmoznazagwa-
_
,
rantowa cpoprzezstosowanieszyfrowaniaalgorytmemsymetrycznymzkluczem
znanymjedynieAliceiBobowi.Zaleta,protokoluzuzyciemasymetrycznegoal-
_
gorytmujestto,zeAliceiBobniemusza,uzgadnia cstosowanychkluczy,oraz
_
zeAlicemozeograniczy csie,doposiadaniajednejparykluczydlakorespondencji
__
prowadzonejzduza,ilo scia,os ob.Protok olnadajesie,wiecdobrzedlakorespondencji
_
,
pomiedzyosobamisporadyczniekontaktujacymisie,orazgdyAliceotrzymujelisty
, ,
odduzejilo scios ob.
_
Elektronicznynotariusz
Donotariuszazglaszamysie,wdw ochwa_sytuacjach:
znych
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 7
' $ $
'
szyfrowanie
-
Kryptogram1
List1
kluczem
deszyfrowanieJ
publicznymK
prywatnymJ
0
J
^
kluczemK
Bob
& %
List1
' $
szyfrowanie
-
Kryptogram2
List2
kluczem
0
S
publicznymK
K
S
w
List2
Mike
& %
0
Alice,posiadaczkaK
& %
Rysunek1.3:Ochronakorespondencjiprzyuzyciuasymetrycznychalgorytm ow
_
szyfrujacych
,
1.Je slichcemyurzedowopotwierdzi cistnieniejakiego sdokumentu.Wtym
,
wypadkumozemydodatkowopragna cbyprocespotwierdzanianieujawnial
_
,
tre scidokumentu(bomozeby ctonaprzykladopisnowej,warto sciowejtech-
_
nologii).
2.Je slichcemyzagwarantowa cbywdokumencie(naprzykladumowiehandlo-
wej)niebylydokonywanep o zniejjakiekolwiekzmianyprzeznieuczciwego
partnera.
Wobuprzypadkachwystarczasporzadzeniedlawspomnianegodokumentuczego s
,
wrodzajuodcisk owpalc ow{kr otkiegociagusymboli,kt orypraktyczniejestdla
,
ka_tekstuinny.Takieodciskipalc ow\moznanaprzykladopublikowa cjako
zdego _
"
ogloszeniewcodziennejprasie.Zdobywamywtenspos obdow odistnieniadoku-
mentu.Abydow odtenbylniezaprzeczalnymusimyzagwarantowa ckilkawlasno sci.
Dosporzadzaniaodcisk owpalc ow\uzywamytakzwanychjednokierunkowych
_
,
"
funkcjihashujacych.M owimy,zeHjestjednokierunkowa,funkcja,hashujaca,o
_
, ,
ilespelnionesa,nastepujacewarunki:
, ,
Dlaka_Xlatwojestobliczy cH(X).
zdego
H(X)maustalona,dlugo s cdlawszystkichtekst owX(wtenspos obdlugo s c
H(X)niezdradzazadnychinformacjiotek scieX).
_
DlazadanegoYznalezienieXtakiego,zeH(X)=Y,jestpraktycznieniemo-
_
zliwe.Dotyczytowszczeg olno scisystematycznegoprzeszukiwaniawszystkich
_
mozliwychtekst ow.TakwiecciagiH(X)musza,by cwystarczajacodlugie,
_
, , ,
bytakiesystematyczneprzeszukiwaniebylopraktyczniebeznadziejne.Je sli
warto scifunkcjihashujacejskladaja,sie,z128bit owtomamydodyspozycji
,
2128mozliwychwarto sci.Jesttopraktycznieniesko ilo s c(dlapor ow-
_ nczona
naniacalkowityokresodpoczatkudoko Wszech swiatabywaszacowany
nca
,
wedlugniekt orychteoriina261sekund!).
Wrzeczywisto scinakladanesa,jeszczebardziejrygorystycznewarunkinawlasno sci
jednokierunkowychfunkcjihashujacych(patrzRozdzial6).
,
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 8
Wcelunotarialnego\potwierdzeniaposiadaniadokumentuXnalezyobliczy c
_
"
warto s cH(X)iopublikowa cja,lubumie sci cunotariusza(role,notariuszamoze
_
przeja codpowiednispecjalniezabezpieczonyprogramsieciowy).P o zniej,gdypra-
,
gniemyudowodni cposiadaniedokumentuX,przedstawiamyXiwskazujemyna
miejsce,gdziepodali smywcze sniejwarto s cH(X).Sprawdzeniepoleganaobliczeniu
warto sciH(X)dlapodanegotekstuXipor ownaniujejzwarto scia,opublikowana,
wcze sniejlubzlozona,unotariusza.
_
Wceluzagwarantowania,iztekstX(naprzykladumowa)nieulegniemody -
_
kacjom,r owniezobliczamywarto s cH(X).Warto s cte,mozemynastepniedolaczy c
_ _
, ,
dodokumentu(naprzykladdlawykryciaprzypadkowychbled owpowstalychw
,
trakcietransmisjidanych)lubopublikowa c,czyzlozy cunotariusza(dlaochrony
_
przedpostepowaniemnieuczciwegopartneraumowy).
,
Zauwa_zeopisanametodamoglabynaprzykladpozwala cnaprostespraw-
zmy,_
dzanieautentyczno sciprogram owkomputerowych.Jedenztrudniejszychdowy-
kryciaatak ownasystemkomputerowyjestwprowadzanietzw.konitrojanskich{
program owzachowujacychsie,zpunktuwidzeniauzytkownikawspos obdokladnie
_
,
takisamjakprogramyorginalne,jednakwykonujacepewnedodatkowefunkcje(na
,
przykladsamopowielaniewprzypadkuwirus ow,czyprzekazywanieinformacjina
zewnatrzwwypadkuszpiegostwagospodarczego).Oilejednakproducentprogramu
,
Xzamie sciwarto s cH(X)naprzykladwWorldWideWeb,wtedyosobaposiadajaca
,
programXmozewka_momencieobliczy cwarto s cfunkcjiHdlaposiadanego
_zdym
programuipor owna cja,zwarto scia,(X)dostepna,publicznie.Zauwa_ze
H zmy,_
,
metodatapozwalanawykryciezmiandokonywanychwprogramieprzezjakie-
kolwiekwirusy,teznanejakinieznanelubnienapisanejeszcze.Istotna,cecha,tej
metodyjestto,zeproducentniemusiupublicznia cprogramuX,amimowszystko
_
pelnawery kacjaorginalno scijestmozliwa.Tymsamymproducentmaszanse
_
sprzedazydalszychkopiiprogramuX.
_
Oilewybierzemyfunkcje,hashujaca,generujaca,kr otkieciagiliter,wtedytelefo-
, , ,
niczniemoznasprawdzi corginalno s cdokument owprzeslanychelektronicznie(osoby
_
znajacesie,poglosiemoga,sprawdzi cczywarto scifunkcjihashujacejdlawyslanego
, ,
iotrzymanegodokumentusa,takiesame).Ta,droga,moznanaprzykladdroga,
_
telefoniczna,sprawdzi corginalno s ckluczypublicznychgenerowanychprzezsystem
PGP.
|||||||||||||||||||||||||||||||||||
Przyklady,jakieprzedstawili smypowyzejtotylkoniekt orezdzisiejszychper-
_
spektywzastosowaniakryptogra i.Juzpotychprzykladachwida cjednak,zepole
_ _
zastosowa kryptogra iwykraczadalekopozaklasyczneszyfrowaniedanych(na
n
przykladdocel owmilitarnych).Niekt oreinnezastosowaniabeda,przedstawionew
,
dalszejcze scitejksia_PozatymCzytelnikmozeodwola csie,dobogatejliteratury
zki. _
, ,
fachowejdotyczacejkryptogra i.
,
1.0.3 Historia kryptogra i
Juzwstarozytno scistosowanebylypewnemetodyszyfrowaniawiadomo sciocha-
__
rakterzestrategicznym.Ciekawejest,zestopienwyra nowaniatychmetodbyl
_
znaczaconizszyodstanuwiedzymatematycznejwka_wla sciwieepoce.Sto-
_ zdej
,
sowanemetodybylydawniejzazwyczajdo s cprymitywneipozwalalynazlamanie
szyfr owdostateczniezdeterminowanemuprzeciwnikowi.Sytuacjauleglazmianie
juzwpierwszejpolowiedwudziestegowieku.Zbudowanowtedyszeregsystem ow
_
szyfrowaniaprzypomocyurzadzenmechanicznychwykorzystywanychpowszechnie
,
podczasIIWojnySwiatowej.Cze s cztychsystem owzostalaskuteczniezlamana
,
(naprzykladniemieckisystemEnigma).Prawdziwa,rewolucje,podwzgledempro-
,
jektowaniasystem owszyfrujacychprzyni oslrozw ojelektronikidajacyolbrzymie
, ,
mozliwo scioperacjiobliczeniowychniskimkosztem.
_
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 9
Rozw ojkryptogra iodswychpoczatk owbylbardzosilniezwiazanyzcelami
, ,
wojskowymi.Wzwiazkuztymwszelkiepracezdziedzinykryptogra imialycha-
,
raktertajnyiichrezultatyniebylypublikowanelubwykorzystywanewsektorze
cywilnymdolatsiedemdziesiatych.Naukowcyprowadzacybadaniawkryptogra-
, ,
iznajdowalisie,pod scisla,kontrola,organ owbezpieczenstwa.Publikowanieprac
nastepowalosporadycznieiniekiedyjedyniepoprzezniedopatrzenieorgan owkon-
,
trolnych.
Prawdziwyprzelompodwzgledemrozwojukryptogra inastapilwlatachsie-
, ,
demdziesiatychwrazzodkryciemasymetrycznychalgorytm owszyfrujacych.Ol-
, ,
brzymiezainteresowaniew srodowiskachnaukowychspowodowalolawinowywzrost
ilo sciprowadzonychbadan,juzpozakontrola,aparat owbezpieczenstwaposzcze-
_
g olnychpanstw.Wymianainformacjijakamamiejsceodtegoczasupozwolilana
ogromnyrozw ojwiedzywtejdziedzinie.
Wwielukrajachstosowaniemetodkryptogra cznychjestnadalzabronionelub
ograniczone.Wwielukrajach,skadinnaddemokratycznych,gdzieobywateleciesza,
, ,
sie,duzymzakresemwolno sci,podejmowanesa,pr obyustanowieniakontrolipanstwa
_
nadstosowaniemmetodkryptogra cznych.Wszczeg scidotyczytoprzyklad
olno
Wsp olnotyEuropejskiejiUSA(forsowanieuzywaniaClippera,tj.ukladuelektro-
_
nicznegosluzacegodoszyfrowania,jednakpozwalajacegonalamaniekryptogram ow
_
, ,
przezsluzbybezpieczenstwa).Doprowadzilototezdotakspektakularnychkrok ow
_ _
jakzakazuzywaniatechnikkryptogra cznychdocelowprywatnychwRosji.
_
Ograniczaniumozliwo scistosowaniametodkryptogra cznychsprzeciwiaja,sie,
_
bardzogwaltownie srodowiskabuzinessu.Wskazuja,naniezbedno s cjejstosowania
,
wgospodarcewniereglamentowanyspos ob.Wobecnejchwiliwydajesie,zejednym
_
,
zniezbednychwarunk owrozwojugospodarczegopanstwajestrozbudowaglobalnej
,
siecikomputerowejpelniacejfunkcje,infrastrukturyinformacyjnejgospodarki.Po-
,
niewa_wsieciachtegotypuniedasie,raczejzagwarantowa cbezpieczenstwaprzed
z
wlamaniamikomputerowymi,danemusza,by czabezpieczanewinnyspos ob.Jedyna
drogadorealizacjitegoceluwiedziepoprzezwykorzystanietechnikkryptogra-
cznych.Podnoszonesa,argumenty,izwprowadzenieograniczenstosowaniakry-
_
ptogra inieuchroniepowodujespadekatrakcyjno scidanegokrajudlainwestycji
gospodarczych.
1.0.4 Kontrowersje zwiazane ze stosowaniem kryptogra i
,
Kryptogra awobecnymstadiumrozwojupotra zagwarantowa cochrone,danych
przeddostepemniepowolanychos ob.Jesttomozliwenawetwtedy,gdywla sciciel
_
,
danychzatakoweuwa_organy scigania.Dopuszczeniestosowaniatychmetod
za
uniemozliwiazatemskuteczniedokonywanierewizji\policyjnychwsystemachkom-
_
"
puterowych.Umozliwiatodokonywanieelektronicznegoprzetwarzaniadanychw
_
ramachdzialalno sciprzestepczejbezniebezpieczenstwadostarczeniaorganom sci-
,
ganiamaterialudowodowegowwypadkuichprzechwycenia.Pozwalator owniez
_
nakorzystaniezpowszechniedostepnychsiecitakichjakInternetdodzialalno sci
,
przestepczej.Zmozliwo scitychkorzystaja,zapewnejuzterazorganizacjedzialajace
_ _
, ,
nakrawedziprawa,lubtezwbrewprawu.
_
,
Wobliczupowyzszychzagrozenwwielupanstwachorganybezpieczenstwa(cza-
__
samidemokratyczniewybrane,czasamibedaceaparatempolitycznejrepresji)stara-
, ,
ja,sie,zabroni cbad zograniczy cstosowaniemetodkryptogra cznych.Drugaztych
,
opcjipoleganadopuszczeniujedynietakichmetod,kt oremoga,zosta czlamane
przezorganybezpieczenstwa(wskutekslabo scitychmetod,konieczno sciprzekazy-
waniauzywanychkluczyorganombezpieczenstwa,bad zdziekiwbudowanymdo
_ , ,
algorytm owtylnymdrzwiom\pozwalajacymnadeszyfrowaniebezznajomo sci
,
"
kluczy).
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 10
Przeciwnicystosowaniaograniczenwstosowaniukryptogra iwskazuja,iz sro-
_
,
dowiskaprzestepczebylybyitakwstaniekorzysta cztechnikkryptogra cznych
,
bezmozliwo sciudowodnieniaimtegopoprzezorgany scigania.Problempolega
_
natym,izkryptogramymaja,charakterlosowychciag owznak owisa,odnich
_
,
nieodr o_Zdrugiejstronylosowycharaktermaja,szumyzawartewka_
znialne. zdym
kodowanymcyfrowoobrazieczyd zwieku.Tymsamymprzestepcadzialajacyw
, , ,
ramachzorganizowanychgrupmozeukry cprzekazywana,wiadomo s cnaprzykladw
_
zdjeciuTatrumieszczonymnaswejstronieWWW,czyteznadyskuCDspecjalniew
_
,
tymceluspreparowanym.Cowiecej,zniekt orychformkryptogra iniejeste smyw
,
staniejuzzrezygnowa c,cho cbywobrociebankowym.Poniewa_wielemetoduzywa
_ z _
jakoniezbednychparametr owlosowychciag owznak ow,przestepcamozezamiast
_
, , ,
nichuzywa ckryptogram owzprzestepczymiinformacjami.Zn ow,niewzbudzito
_
,
zadnychpodejrzen,awiadomo scitakprzekazywanebeda,odr o_odnaprawde,
_ ,znialne
losowychciag owjedyniedlaposiadaczytajnegoklucza(przykladtakiejsytuacji
,
opisujemydokladniejwRozdziale8.0.6).
Reasumujac,wydajesie,izpostulowaneograniczeniasa,wstanieby cskuteczne
_
,
jedyniewodniesieniudoos obczyorganizacjinieparajacychsie,dzialalno scia,prze-
,
stepcza.Spowodowalobytozatemskutekodwrotnydozamierzonego{stawialoby
, ,
organizacjeprzestepczewuprzywilejowanejpozycjiwobecresztyspoleczenstwa,
,
kt oraniebylabywstaniebroni cswychdanychwobecdzialankryminalnych.
1.0.5 Korzystanie z produkt ow kryptogra cznych
Upublicznieniekryptogra ipozwalanabardziejwiarygodna,wery kacje,oferowa-
nychprogram owisprzetukryptogra cznego.Niemoznabowiemwtymwzgledzie
_
, ,
polega cnareklamiesamych rm.Wadliwo s coferowanegoproduktuniejestwidocz-
nabowiemgolymokiem,aczestobeznieslychaniekosztownegobadaniaproduktu
,
niejestsie,r owniezwstanieotymprzekona c.
_
Sformulowa cmoznanastepujacezasadydotyczacepraktycznegostosowaniapro-
_
, , ,
dukt owkryptogra cznychwsytuacjach,gdyrzeczywi sciebezpieczenstwomaklu-
czoweznaczenie:
Jakowzgledniebezpiecznemoga,by cuznanejedynieprogramyczytezspe-
_
,
cjalnyhardwareoferowanypoprzezznane rmyoniezaprzeczalnejreputacji.
Najlepiej,gdyproduktyteposiadaja,certy katyodpowiednichpanstwowych
urzed owkontrolnych(jaknaprzykladNISTwUSA).
,
Programyiurzadzeniakryptogra cznepowinnyrealizowa cpowszechniezna-
,
ne,popularneiprzetestowanerozwiazania.Procestestowaniapowinienmie c
,
nastepujacyprzebieg:
, ,
1.Propozycjametody,wrazzjejszczeg o lowymopisemmusiby cpodanado
wiadomo scipublicznej.Bezpieczenstwometodyniemozeopiera csie,na
_
utajnieniujejsposobudzialania.Wiadomo,zeitakpewnagrupaos ob
_
uzyskadotakichinformacjidostep(cho cbypracownicy rmyoferujacej
, ,
produkt).Grupatamozenastepniewykorzystywa cjenaszkode,uzyt-
_ _
,
kownikaproduktu.
2.Propozycjamusiwzbudzi cpowszechnezainteresowanie srodowiskanauko-
wegoibusinessuimusza,by cprowadzonenadnia,intensywnebadania.
3.Je slipod luzszymczasieniemaznaczacychpostep owprowadzacychdo
_
, , ,
z lamaniametodyateoretycznebadaniazdaja,sie,potwierdza cjejbez-
pieczenstwo(naprzykladpoprzezredukcje,znanychtrudnychzagadnien
obliczeniowychdozagadnieniazlamaniaproponowanegoszyfru),wtedy
metode,te,moznauzna czawzgledniebezpieczna,idopu sci cdouzytku.
_ _
,
ROZDZIAL1.PIERWSZYRZUTOKANAKRYPTOGRAFIE, 11
Je slijakikolwiekzpowyzszychwarunk owniejestspelniony,algorytmnie
_
moznauzna czabezpieczny.
_
Niezbednejestciagle sledzenierozwojustanuwiedzykryptogra cznej.Poste-
, , ,
pywtejdziedziniemoga,spowodowa cmozliwo s clamaniaalgorytm owdawniej
_
uznawanychzabezpieczne.(Tegotypusytuacjanastapilanaprzykladw
,
odniesieniudodlugo scikluczydlasystemuRSAwskutekpostep owwzakresie
,
algorytm owrozkladajacychliczbynaczynnikipierwsze.)
,
Czasamijako s cofertysoftware'uihardware'ukryptogra cznegojestpowiazana
,
zczynnikamipolitycznymi,takimijakograniczeniaeksportowe.Naprzykladtak
zwanewersjemiedzynarodowe\program ow rmameryka majacedostarczy c
nskich,
",
prywatnemuuzytkownikowinarzedziakryptogra cznegwarantuja,jedyniebardzo
_
,
niskipoziombezpieczenstwa.Poziomtenjesttakniski,zeprogramyteniewyma-
_
gaja,zezwoleneksportowychwbardzorestrykcyjnymustawodawstwieUSA.
Rozdzial2
Podstawowe techniki
szyfrowania
Wniniejszymrozdzialeprzedstawiamykilkaklasycznychtechnikszyfrowania.Tech-
nikitebywaja,skladnikamiwielubardziejzaawansowanychalgorytm ow,dlatego
po swiecimyimchwile,uwagi.
,
2.0.6 Podstawienie
Niech : ! bedziepermutacja,za s zbioremuzywanychliter.Tekstjawny
_
, ,
a1(gdzieai )jestszyfrowanyjako (a1) (a2):(an).Kryptogram
a2 : : : an 2 : :
;1
b1odszyfrowywanyjestjako (b1):(bn).
: : : bn : : ;1
Przyklad:szyfryCesaraLiteryalfabetumoznautozsamia czliczbami.W
__
systemieCesarauzywanychjest26literodpowiadajacychliczbomod0do25.
_
,
(i):=i+3mod26dlai0 25g.
2 f : : :
Analizaczestotliwo sci
,
Slabo scia,szyfr owopartychnapodstawieniachjestto,zemoga,oneby czlamane
_
poprzezanalize,czestotliwo sciwystepowaniaposzczeg olnychliteralfabetu.Litery
, ,
alfabetuniewystepuja,bowiemzjednakowa,czestotliwo scia,{analizatychcze-
, , ,
stotliwo sciwzaszyfrowanychtekstachpozwalanazgadniecieniekt orychwarto sci
,
permutacji .Dlaprzykladuprzyjrzyjmysie,przecietnejczestotliwo sciwystepo-
, , ,
wanialiterwtekstachwjezykuangielskim(wedlug[1]):
,
E-12.31%L-4.03%B-1.62%
T-9.59%D-3.65%G-1.61%
A-8.05%C-3.20%V-0.93%
O-7.94%U-3.10%K-0.52%
N-7.19%P-2.29%Q-0.20%
I-7.18%F-2.28%X-0.20%
S-6.59%M-2.25%J-0.10%
R-6.03%W-2.03%Z-0.09%
H-5.14%Y-1.88%
Kryptoanalizapoleganasporzadzeniutabeliczestotliwo sciwystepowanialiter
, , ,
wzaszyfrowanymtek scieipor ownaniagozpowyzsza,tabela.Natejpodstawie
_
,
moznanaprzykladzlokalizowa cprawdopodobnewarto scidla (E), (T), (A).Po
_
przyjeciuhipotetycznychwarto scidlatychliterszukamywkryptogramiesekwencji
,
12
ROZDZIAL2.PODSTAWOWETECHNIKISZYFROWANIA 13
literodpowiadajacychtypowymslowomtakimjaknaprzykladthe\.Pozwala
,
"
tonazwery kowaniehipotezyiprzyjecieprawidlowychwarto scidlaE,T,A.Po
,
ustaleniutychwarto scimozemypokusi csie,oodgadniecie (H)-takbyutworzy c
_
,
odpowiednioduzokryptogram owdlathe\.Postepowanietokontynuujemydyspo-
_
",
nujaccoraztowiekszymiporcjamitekstujawnego.
, ,
Sposobemnautrudnienieanalizyczestotliwo scijestszyfrowaniepoprzezpodsta-
,
wienieniepojedynczychliter,aleblok owliterokre slonejdlugo sci(tj. : k k).
!
Mamywtedybowiemdoczynieniazmniejszymidysproporcjamiwzakresie sredniej
czestotliwo sciwystepowaniaposzczeg olnychkon guracjiliterwbloku wszczeg ol-
, ,
no sciposzczeg olneprawdopodobienstwasa,stosunkowomalymiliczbami.Utrudnia
toodgadnieciewarto scipodstawienia .Wszczeg olno scikryptoanalizawymaga
,
duzodluzszychkryptogram ow,abym ocskorzysta czjakichkolwiekstatystycznych
__
prawidlowo sci.
Przyklademsystemu,wkt orymkodujesie,blokidlugo sci2jestsystemFairplay'a
przedstawionynarys.2.1.Jesttoprostysystem,wkt orymwszelkieoperacjeszy-
frowaniaideszyfrowaniamoga,by czlatwo scia,dokonanerecznie.Systemoczywi scie
,
gwarantujetylkobardzoniewielkizakresbezpieczenstwaimozeby ctraktowanyjako
_
dygresjawstrone,metodhistorycznych(stosowanychwtrakcieIWojnySwiatowej).
Szyfrowaniupodlegaja,paryliter,przyczymuzywamy25liter(25duzychliter
_ _
alfabetuangielskiego,jednazliter,mianowicieJ,jestwtekstachzastapionaprzez
,
I).Doszyfrowaniaideszyfrowaniauzywamyjestkwadrat5 5,wkt orywpisujemy
_
kolejneliterywystepujacewha sle(narys.2.1haslemjestPOSZLAMALPA
, ,
"
DOPIWNICY\),przyczympomijamypowtarzajacesie,litery.Gdypowpisaniu
,
tychliterzostalyjeszczewolnemiejscawkwadracie,toumieszczamytamjeszcze
niewpisaneliterywkolejno scialfabetycznej.Wtenspos obwypelniamykwadrat
25literami.Szyfrowanieprzebieganastepujaco.Zal o_dlaprzykladu,zechcemy
zmy _
, ,
zaszyfrowa cpare,OHwedlugkluczazrys.2.1.LiteryOorazHwyznaczaja,pro-
stokat wkwadraciedoszyfrowania,wkt oregopozostalychrogachznajduja,sie,S
,
iG.Regulaszyfrowaniam owi,zeOHzastepujemywla snietymiliterami,tj.SG.
_
,
Gdyparaliterjaka,zamierzamyzaszyfrowa clezywjednejkolumnielubjednym
_
wierszu(iwobectegoniede niujeprostokata),toliterytezastepujemypara,liter
, ,
lezaca,naprawoodnich,naprzykladSYzastepujemyprzezZB,za sWEprzezAN
_
, ,
(literylezacewpierwszejkolumniezprawejstronyzastepujemyliteramizostatniej
_
, ,
kolumny).
Og olnierzeczbioracpodstawienienieoparteodlugieblokiluboprostych
,
zasadachgenerowaniapermutacjizkluczamozeby cpodatnenaanalize,czestotliwo-
_
,
sci.Ztegowzgledupodstawienienalezytraktowa craczejjakotechnike,pomocnicza,
_
,
dowykorzystaniajakoelementpomocniczybardziejzlozonychmetod.
_
2.0.7 XOR i one-time pad
OperacjaXOR(eXclusiveOR)jestzde niowanajaknastepuje:
,
0XOR0=1XOR1=0 1XOR0=0XOR1=1.
SzyfrowanieprzypomocyXOR:zal o_zetekstjawnyjestciagiembit-
zmy,_
,
: : : kn
owa1,za skluczciagiembit owk1.Wtedykryptogramemjestciag
: : : an
, ,
c1,gdzieci:=aidlai=1 Deszyfrowanieopartejestna
: : : cn XOR ki : : : n.
trzechlatwychdosprawdzeniar owno sciach:
x=0 0=x (y)=(x)XOR):
XOR x x XOR x XOR XOR z XOR y z
Stad
,
ci=(ai)XOR=ai(ki)=ai0=ai:
XOR ki XOR ki ki XOR XOR ki XOR
ROZDZIAL2.PODSTAWOWETECHNIKISZYFROWANIA 14
klucz:kwadrat5 5zawierawszystkieliteryzwajatkiemJ,
,
kt orewtek sciejawnymzastepujemypoprzezI
,
POSZL
haslo:
AMDIWPOSZLAMALPADOPIWNICY\
"
NCYBEpozostalelitery
Q
FGHKwkolejno scialfabetycznej
RTUVX
szyfrowanie:
POSZLOH-rogiprostokata OH
,
zastepowanyjestpoprzezlitery
,
AMDIW
znajdujacesiewpozostalychrogach
,
NCYBEprostokata ,
tj.przezSG
,
Q
FGHK
RTUVX
szyfrowanietekstujawnegoKRjOWjAIjWEjSZ
(KR)=FV, (OW)=LM,
(AI)=MW, (WE)=AN
(SZ)=ZL
Rysunek2.1:SystemPlayfair'a
SzyfrowanieprzypomocyXORmawielorakiezastosowania.Jednymznichjest
one-timepad.
One-timepadJesttometodaszyfrowania,wkt orejuzywanyjestlosowowy-
_
branykluczk1 .Samoszyfrowanieodbywasie,przypomocyXOR.Istotne
: : : kn
jest,bydoka_szyfrowaniauzywa cinnego,wygenerowanegoniezaleznie
zdego _ _
klucza.Zasadzietejmetodazawdzieczaswa,nazwe.
, ,
Nastepujacewlasno scisa,kluczowedlametodyone-timepad:
, ,
Kryptogramjesttakzeciagiemlosowymnbit ow,tzn.matensamrozklad
_
,
prawdopodobienstwacociagibit owwygenerowaneprzezrzucaniemoneta,
,
(wyrzuceniereszkipowodujedopisanie1,wyrzucenieorla{dopisanie0).
Bezznajomo scikluczazadnainformacjadotyczacatekstujawnegoniemoze
_ _
,
by cwydedukowanazkryptogramu(bezwzgledunazastosowanemoceobli-
,
czenioweitp.).Wlasno s ctabywanazywanabezpieczenstwemdoskonalym.
Dlaudowodnieniapierwszejwlasno scizauwa_zeje sliki=ai,toci=0,oraz
zmy,_
zeci=1wprzeciwnymwypadku.Zatemprawdopodobienstwo,zeci=0jestr owne
_ _
1
niezaleznieodwarto sciai.Zatemi-tybitkryptogramujestlosowy.Poniewa_
_ z
2
bitykisa,losowaneniezaleznieodsiebie,wiecibitykryptogramusa,niezalezne,tak
_ _
,
jakwprzypadkuciag owjakieotrzymujemyrzucajacmoneta.
, , ,
Niechc1bedziedowolnymciagiembit ow.Dlaudowodnieniadrugiejwlas-
: : : cn ,
,
no scizauwa_zedlaka_tekstujawnegod1istniejedokladniejeden
zmy,_zdego : : : dn
ROZDZIAL2.PODSTAWOWETECHNIKISZYFROWANIA 15
kluczk1taki,zepoprzezszyfrowanieotrzymujemykryptogramc1.Istot-
:_ : : : cn
: : kn
nie,dlai=1 spelnionamusiby cr owno s cci=di,skadki=di.
: : : n XOR ki , XOR ci
Poniewa_kryptogramc1odpowiadaka_mozliwemutekstowijawnemu
z : : : cn zdemu_
ztakimsamymprawdopodobienstwem,nicniemoznawywnioskowa coksztalcie
_
tekstujawnegobezznajomo sciklucza.
Zastosowaniaone-timepad:jedna,dziedzina,zastosowa jestszyfrowaniesto-
n
sunkowokr otkich,alebardzowa_informacji,jakrozkazywojskoweostrate-
znych
gicznymznaczeniu(naprzykladowystrzeleniurakietjadrowych).U_w
zywanie
,
tejsytuacjiszyfr owmozliwychdozlamania(cho cbyolbrzymimnaklademobliczen)
_
niesieniebezpieczenstwo,zefaktycznieszyfryzostana,zlamane.
_
Problemyzestosowaniemone-timepad:zasadyuzywaniaone-timepad
_
m owia,zeklucz
_
,
musiby czawczasuuzgodnionyprzezosobykomunikujacesie
, ,
musiby cwybranynaprawde,losowo(cotechnicznieniejestlatwe,
patrzrozdzial7)
musiby cprzechowywanywbezpiecznyspos ob
musiby cconajmniejtakdlugijakszyfrowanytekst.
Kazdyzpowyzszychwarunk owstwarzaniedogodno scidlauzytkownik owizawe_
__ _ za
,
polepraktycznychzastosowa one-timepad.
n
Niebezpieczenstwouzyciawielokrotnietegosamegoklucza:Zal o_ze
_ zmy,_
szyfrujemydlugiteksta0a1przypomocykluczadlugo scin.Poniewa_brakuje
: : : z
nambit owklucza,uzywamynastepujacejformuly:
_
, ,
ci=ai XOR kimodn:
Inaczejm owiac,blokidlugo scinszyfrujemyka_przypomocytegosamego
zdorazowo
,
kluczak0.Zauwa_zewtedy
: : : kn;1zmy,_
cj=(aj)XOR(an+j)=aj XOR an+j:
XOR cn+j XOR kj XOR kj
Zatemzlatwo scia,moznabezznajomo scikluczanapodstawiesamegokryptogramu
_
obliczy caj!
XOR an+j
Zlamanietakskonstruowanegokryptogramumozesie,odbywa cwedlugnaste-
_
,
pujacegoscenariusza.Zduzymprawdopodobienstwemka_tekstzawieradlugie
_ zdy
,
ciagispacji.Zakladajac,zeajjestspacja,moznaobliczy caj+n.Czyniactakdla
_ _
, , ,
ka_jotrzymujemypewientekst.Szukamywnimzrozumialychfragment ow.
zdego
Wmiejscach,gdzienpozycjidotyluwtek sciejawnymwystepujeblokspacji
,
otrzymamywtenspos obfragmentytekstujawnego.Je slipotra myjerozpozna c,
todysponujemybitamiai,cidlaodpowiednichi.Stadwyliczamykimodn=
,
ai.Znalezionewarto scikluczauzywamynastepniedlacalegokryptogramuw
XOR ci _
,
celuodszyfrowaniainnychfragment owtekstujawnego.Prace,moznakontynuowa c
_
pr obujaczgadna ckolejnewarto scikinagranicyodszyfrowanychregion owspraw-
, ,
dzajacczyprowadzitodosensownegouzupelnieniaodgadnietychfragment owtekstu
, ,
jawnego.
2.0.8 S-boksy
S-boksysa,nadzwyczajistotnymiskladnikamialgorytmuDES(DataEncryption
Standard)najwa_wpraktycealgorytmuszyfrujacegowmomenciepowsta-
zniejszego
,
waniatejksia_KazdyS-boksjestzde niowanypoprzezmacierzrozmiaru4 16
zki._
,
zawierajaca,liczbyzprzedzialuod0do15(patrzrys.2.2).
,
ROZDZIAL2.PODSTAWOWETECHNIKISZYFROWANIA 16
1441312151183106125907
0157414213110612119538
-
4114813621115129791050
1512824917511314100613
6
wiersz2,kolumna13
argument=111010,wynik=1010=10102
Rysunek2.2:SzyfrowanieprzypomocyS-boks ow(rysunekprzedstawiaS-bokso
nazwieS1)
Spos obdzialaniaS-boks ow.S-boksde niujefunkcje,kt orejargumentamisa,
,
ciagizlozonez6bit ow,awarto sciamiciagizlozonez4bit ow.Obliczeniewarto sci
_ _
, ,
dlaargumentuxmanastepujacyprzebieg:
, ,
pierwszyiostatnibitargumentuxtworza,liczbe,wsystemiedw ojkowymwy-
znaczajaca,numerwiersza(wierszenumerujemyod0do3),
,
pozostale4bityxwyznaczaja,numerkolumny(kolumnynumerujemyod0do
15),
naprzecieciuwyznaczonychkolumnyiwierszaznajdujesie,pojedynczyele-
,
ment,liczbatajestszukana,warto scia,funkcji.
Wyb orliczbznajdujacychsie,wS-boksiemafundamentalneznaczeniedlajako sci
,
szyfrowania.Wyb orS-boks owstosowanychwpraktyceniebyldoko procesem
nca
jawnym,znanychjestjednakkilkaregul,kt orewzietopoduwage.Niejestznana
, ,
zadnaprostaieleganckaanalizamatematyczna,kt oraprowadzilabydowyboru
_
takichanieinnychS-boks ow.Wpraktycestosowanesa,S-boksyonazwachS1,S2,
:,S8.
: :
Efektlawinowy:Jedna,zpodstawowychzasadszyfrowaniajestto,byzmiana
pojedynczegobituwtek sciejawnympowodowalazmiane,wielubit owwkryptogra-
mie.Widealnejsytuacjipowinnotopowodowa czmiane,mniejwiecejtylubit ow,
,
ileby smyzmieniliwwypadkuichustawieniawedlugrzut owmoneta.Tymsamym
,
podobnetekstyjawneniemaja,podobnychkryptogram ow!Wlasno s ctautrudnia
wznaczacyspos obkryptoanalize.Wtejsytuacjim owimyoefekcielawinowym,
, ,
dlapodkre slenia,zezmianapojedynczegobituwtek sciejawnympowodujelawine,
_
zmianwkryptogramie.
PrzypomocyS-boks owmozazrealizowa cefektlawinowy.OileS-boksstosujemy
_
dobit ow(x )tozmianaxlubwpowodujezmiane,numeruwiersza.Rzut
y z u v w
okanaS-bokszrys.2.2pozwalastwierdzi c,zewierszeniesa,dosiebiepodobne.
_
Dlategoniemazadnegopowodu,bypozmianiexlubwwynikprzypominalw
_
jakikolwiekspos obstarywynik.Podobnezjawiskoodnosisie,dokolumn,gdyz
_
kolumnyS-boksur owniezniesa,podobne.
_
GdyS-boksysa,uzywanewielokrotnie,wtedyefektlawinowyulegaspotegowaniu
_
,
ispos obwjakizmianapojedynczegobituwplywanazmiane,ko wynikujest
ncowego
corazbardziejskomplikowany.
KryteriawyboruS-boks ow:Ponizejomawiamyniekt orewa_wlasno sci,ja-
_ zne
kiepowinnyby cspelnioneprzezdobreS-boksy.Kazdaznichzostalasformulowana
_
nazasadzie\je sliwlasno s cniejestspe lniona,tokryptoanalizamozeby culatwiona\.
_
ROZDZIAL2.PODSTAWOWETECHNIKISZYFROWANIA 17
KazdywierszS-boksuzawierawszystkieliczbycalkowiteod0do15.
_
Wlasno s ctazapewnia,zesamaznajomo s cwierszaniedajezadnejinformacji
_ _
owarto sciko
ncowej.
FunkcjaobliczanaprzezS-boksniejestfunkcja,a niczna,
,
P
tzn.zadenbitwynikuniedasie,przedstawi cjakoc0+6,gdzie
_ ci xi
i=1
xioznaczai-tybitargumentu,za soperacjearytmetycznewykonywanesa,
modulo2.Gdybybitywynikubylywyrazalnezapomoca,funkcjia nicznych,
_
tokryptoanalizabylabypowa_ulatwiona.Istotnie,popierwszeskladanie
znie
S-boks owniemialobysensu{dalejporuszaliby smysie,wobrebiefunkcji
,
a nicznych,bozlozeniefunkcjia nicznychjestfunkcja,a niczna.Podrugie,
_
,
kryptoanalizaograniczalabysie,dorozwiazywaniauklad owr ownanliniowych,
,
coniejesttrudnymzadaniem.
Zmianajednegobituargumentuzmieniaconajmniejdwabitywyniku.
Wlasno s ctamazapewni cefektlawinowywprzypadkuwielokrotnegozasto-
sowaniaS-boks ow.
Dlaka_argumentuxwarto sciobliczaneprzezS-boksdlaargument owxoraz
zdego
x001100r o_a,sie,conajmniejnadw ochpozycjach.
XORzni
Dlaka_argumentuxoraze 0 1gwarto sciobliczaneprzezS-boksdla
zdego f 2 f
xorazx11ef00r o_a,sie,conajmniejnadw ochpozycjach.
XORzni
Je sliustalimywarto s cjednegobituargumentuorazjedna,pozycje,wyniku,todla
oko lopo lowyustawie npozosta lychbit owargumentunawybranejpozycjiwyniku
otrzymamy0.
Wlasno s ctagwarantuje,zenawetgdyznamywarto s cjednegobituargumentu,
_
tonadowolnejpozycjiwynikuotrzymujemy1wprzyblizeniuztakimiczesto-
_
,
sciamijakwwypadkulosowaniabit owprzypomocyrzut owmoneta.
,
Bardzowskazanyjestr ownieztakiwyb orwarto sciwtablicyS-boksu,byjaknajbar-
_
dziejutrudnionebylyznanetechnikikryptoanalizy,takiejakkryptoanalizar o_
zni-
cowailiniowa(patrzrozdz.12).
Rozdzial3
Algorytmy symetryczne
3.1DES{DataEncryptionStandard
ZanimprzejdziemydotechnicznegoopisualgorytmuDES,sformulujmykilkaog ol-
nychuwagnajegotemat:
DESjestsymetrycznymalgorytmemszyfrujacym,tensamkluczjestuzywany
_
,
doszyfrowaniaideszyfrowania.
Szczeg olowyopisalgorytmuDESzostalcelowoopublikowany.Chodziloo
przekonaniepotencjalnychuzytkownik ow,zebezpieczenstwometodynietkwi
_ _
wtajno scijejbudowy,alewkonstrukcjiodpornejnakryptoanalize.Bowiem
,
ka_metoda,kt orejszczeg olyniezostalyujawnione,mozezawiera cwsobie
zda _
tzw.tylne,czylimiejscewalgorytmie,kt oremozeby cwykorzystane
drzwi _
przezprzeciwnikaznajacegoszczeg olyalgorytmunazdobycieinformacjinie-
,
dostepnychwzwyklymtrybie(naprzykladdotyczaceuzywanychkluczy).
_
, ,
DESjestznaczacoszybszy,gdyjestzaimplementowanyjakohardwareanie
,
jakosoftware.Algorytmzostalcelowotakzaprojektowany,abyznieczeci cdo
,
u_implementacjisoftware'owychuwa_zabardziejpodatnena
zywania zanych
atak(latwiejjestsie,wlama cdosystemuiniepostrzezeniewymieni csoftware,
_
nizdokona c zycznegowlamaniabywymieni chardware).Ukladyrealizujace
_
,
DESsa,bardzoszybkie(naprzyklad1GB/sek.) dlapor ownaniadobrysoft-
warenaPCmozemie cpredko s ctysiacerazynizsza.
_ _
, , ,
DESszyfrujeblokizlozonez64bit ow,codaje8literASCII,ka_zao-
_ zda
patrzonawbitparzysto sci.Kluczeskladaja,sie,r owniezz64bit ow,przy
_
czym8bit owjestbitamiparzysto sci.Takwiecwistociewtrakciewyboru
,
kluczamoznaokre sli cjedynie56bit ow,resztajestgenerowanaautomatycznie.
_
Postepwdziedzinietechnologiiizwiazaneztymobnizeniekoszt owkry-
_
, ,
ptoanalizywyzwolilydyskusje,czydlugo s ckluczyDES-aniejestzamala.
Kosztyznalezieniakluczanapodstawiedostatecznejilo scipartekstjawny{
kryptogramzaszyfrowanytymkluczembywaja,szacowanejedynienamiliony
dolar owUSA.
DESzostalwUSAuznanyzastandarddlacel owniemilitarnych.Zostal
wstepniezaprojektowanywo srodkubadawczymIBMwYorktownHeights,
,
anastepniezmody kowanyprzezNSA(NationalSecurityAgency),rzadowy
, ,
organwUSAzajmujacysie,problemamibezpieczenstwanarodowego.Wywo-
,
lalotowielepodejrzen,zeNSAznatylneumozliwiajacejlamanieszyfr ow
_ drzwi_
,
generowanychprzypomocyDES-a.Poniewa_DESstalsie,wmiedzyczasie
z
,
18
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 19
standardemwzastosowaniachkomercyjnychnacalym swiecie,dawalobyto
USAolbrzymiekorzy sciewzakresiemilitarnymigospodarczym.
WodniesieniudoDES-aniezostalyopublikowanezadnepracedajacetej
_
,
metodziesolidnepodstawymatematyczne.Jednakzeponad20latbadan
_
akademickichpotwierdzaja,zekonstrukcjaDES-ajestbardzowyra nowana.
_
,
JakkolwiekwzakresiekryptoanalizyDES-aosiagnietoduzepostepy,nieza-
_
, , ,
grozilyoneznaczacostosowaniutejmetodywpraktyce.Zdrugiejstrony
,
uproszczonewersjeDES-amoga,by czlamaneznaczacomniejszymkosztem.
,
Interesujacejest,zepr obyulepszenDES-adotychczasniedoprowadzilydo
_
,
znaczacychpostep owiDESniedoczekalsie,nowej,lepszejwersji.
, ,
3.1.1 Szyfrowanie DES-em
SzyfrowanieideszyfrowanieprzypomocyDES-askladasie,z16rund.Wtrakcie
ka_rundydokonywanesa,tesameobliczenia,alenawynikachobliczenzpoprzed-
zdej
niejrundyispecjalnympodkluczugenerowanymz64-bitowegoklucza.Dodatkowo,
przedpierwsza,runda,ipoostatniejrundziebitysa,permutowanewustalonyspos ob.
Generowaniepodkluczy
Wceluuzyskaniapodkluczyuzywanychpodczasposzczeg olnychrundusuwamy
_
najpierw8bit owparzysto scizawartychwkluczu.Nastepniezpozostalych56bit ow
,
tworzonychjest16podkluczy,ka_skladajacysie,z48bit ow.Takutworzonyi-
zdy,
tykluczoznacza cbedziemyprzezKi bedzieonuzywanywtrakciei-tejrundy.
_
, ,
Kazdypodkluczskladasie,zezg oryokre slonychbit oworginalnegoklucza{dla
_
ka_podkluczasa,toinnebityiustawionewinnejkolejno sci.Spos obtworzenia
zdego
podkluczyjestjawnyizostalopublikowanywrazzopisemDES-a.Majacnauwadze
,
kosztyhardware'uwybranotakispos obwybieraniabit owpodkluczy,jakilatwo
daje,sie,zrealizowa chardware'owo.Interesujacejest,izznanemetodykryptoana-
_
,
lizyDES-awnajbardziejistotnymmomencieniewykorzystuja,zalezno scimiedzy
_
,
warto sciamibit owpodkluczy.
Permutacjapoczatkowaiko
ncowa
,
Napoczatkubitytekstujawnegosa,permutowane.Niematozadnegocelukry-
_
,
ptogra cznego.Zauwa_jednak,zepermutacjatamozeby czlatwo scia,zaim-
zmy_ _
plementowanahardware'owo.Poprostuposzczeg olnebitydoprowadzonesa,za
pomoca,drut ow(dokladniejpolaczenwukladzieVLSI)naodpowiedniemiejsca.
,
Czasobliczenpermutacjiodpowiadatujedynieczasowiwjakiminformacjedotra,
podrutachnamiejscaprzeznaczenia.Wprzeciwienstwiedotegoimplementacja
software'owawymagadlugichobliczen:ka_bitoddzielniemusiby cprzekopio-
zdy
wanynamiejsceprzeznaczenia.
Podkoniecszyfrowaniauzyskanebitysa,permutowanepermutacja,odwrotna,do
poczatkowej.Permutacjatajestnazywanapermutacja,.
ko ncow a,
,
RundaDES-a
Danewej sciowerundyi+1skladaja,sie,zdwuciag ow32-bitowych:Li(pierwszych
,
32bit owbedacychwynikiemrundyi)orazRi(pozostale32bityuzyskanewrundzie
, ,
i).Zachodza,nastepujacezwiazki:
, , ,
Li+1=Ri
Ri+1=Li(Ri ) (3.1)
XOR f Ki+1
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 20
gdziefjestfunkcja,kt oraposiadazasadniczeznaczeniedlaszyfrowania.Obliczenie
,
warto scifunkcjifjestprzedstawionenarys.3.2idokonujesie,wnastepujacyspos ob:
, ,
123456789101132numerybit ownawyj sciu
(
((
(((
@ ; @ ;
(((
polaczeniarealizujace
((( ,
@ ;
;
((( @ ...permutacjez,
; ;
@ @
((( ,
(((
rozszerzeniem
(((
12345678910111213141516numerybit ownawej sciu
Rysunek3.1:Permutacjazrozszerzeniem
1.Poprzeztzw.permutacje z rozszerzeniemotrzymujesie,ciagzlozonyz48
_
, ,
bit owz32bit owRi(32bityRisa,kopiowanena48pozycji,niekt oreznich
dwukrotnie,patrzrys.3.1).
2.Naotrzymanych48bitachjestdokonywanaoperacjaXORzodpowiadajacymi
,
imbitamipodkluczaKi+1.
3.Otrzymane48bit owdzielonejestna8gruppo6bit ow.Kazdagrupapod-
_
dawanajestdzialaniuS-boksu.(S-Boksuzywanyprzezi-ta,grupe,nazywany
_
jestSi.)
4.Otrzymane32bitysa,nakoniecpermutowane.
Ri
?
permut.zrozszerz.
?
Ki+1
HH
HH
H
H
j
XOR
?
? ? ? ? ? ? ? ?
S1 S2 S3 S4 S5 S6 S7 S8
H
Q
H S BB
Q
H s w
H N / +
j Q S
?
permutacja
?
f(Ri )
Ki+1
Rysunek3.2:FunkcjafDES-a
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 21
3.1.2 Deszyfrowanie DES-em
Nalezalobyoczekiwa c,zeabydeszyfrowa ckryptogramnalezycaleobliczenieskla-
_ _ _
dajacesie,naszyfrowanieodtworzy codko dopoczatku.AledlaS-boks ownie
nca,
,
jesttomozliwe!JednemuwynikowiotrzymanemuprzezS-boksodpowiadawiele
_
mozliwychargument ow.Pomagatujednaknastepujacywybieg:zr owno sci(3.1)
_
, ,
wynika,iz:
_
Ri;1=Li
Li;1=Ri(Ri;1)=Ri(Li )
XOR f Ki XOR f Ki
Je sliwiecznamyLi,RiorazpodkluczKi,tonapodstawiepowyzszychr owno sci
_
,
mozemyobliczy cLi;1iRi;1.Takwiecniemusimywcaleoblicza cfunkcjiodwrotnej
_
,
dofunkcjiobliczanychprzezS-boksy.
Latwowida c,zepodczasdeszyfrowaniadokonywanesa,tesameoperacjeco
_
podczasszyfrowania(tylkopodkluczewystepuja,wodwrotnejkolejno sci).Ztego
,
wzgledutensamhardwaremozeby cuzytydoszyfrowaniaideszyfrowania.
__
,
Zauwa_smy,zewzory(3.1)stwarzaja,dogodnemozliwo scideszyfrowania.Inte-
zyli _ _
resujacejest,zeszyfrowaniewedlugschematudanegotymiwzoramizdajesie,mie c
_
,
solidnepodstawyteoretyczne(por.[4]).Jesttojedenzargument owprzemawiaja-
,
cychnakorzy s cDES-a.
3.2TrzykrotnyDES
Wielko s ckluczauzywanegoprzezalgorytmDESwydajesie,by cniewystarczajaca.
_
,
Ztegowzgledupodjetoszeregpr obmody kacjiDES-a,takabywistotnyspos ob
, ,
wykorzystywa cdluzszeklucze.Wieletychpr obsko losie,niepowodzeniem.
_ nczy
Okazywalosie,bowiem,izkosztyzwiazanezezlamaniemkryptogram owutworzo-
_
,
nychprzypomocytychmetodsa,por ownywalnezkosztamizlamaniakryptogram ow
utworzonychprzypomocyDES-a(przynajmniejprzyuzyciuznanychmetodla-
_
maniaszyfr ow).Bardziejskomplikowanabudowaalgorytmuidluzszekluczenie
_
oferowalywiecwiekszegobezpieczenstwa.
, ,
Metoda,niekiedystosowana,wpraktycejesttrzykrotnyDES.Uzywamywnim
_
dw ochkluczyS1,S2,ka_bedacyzwyklymkluczemDES-a.Szyfrowanietekstu
zdy, ,
jawnegomanastepujacyprzebieg:
, ,
1.tekstjawnyszyfrowanyjestkluczemS1,
2.wynikkroku1jestdeszyfrowanykluczemS2,
3.wynikkroku2jestpowt ornieszyfrowanykluczemS1.
Abyzkryptogramuotrzyma czpowrotemtekstjawnywystarczyoczywi sciewyko-
na cnastepujacekroki:
, ,
1.kryptogramdeszyfrowanyjestkluczemS1,
2.wynikkroku1jestszyfrowanykluczemS2,
3.wynikkroku2jestpowt orniedeszyfrowanykluczemS1.
3.3Szyfrowanietekst owdowolnejd lugo sci
DESszyfrujetylkobardzokr otkieteksty(8literASCII!).AbyDESuczyni c
u_trzebaznale z cspos obnaszyfrowanietekst owdowolnejdlugo sci.Po-
zytecznym
nizejprzedstawiamytrzytakieog olnemetodyrozszerzajaceszyfrowanietekst ow
_
,
ustalonejdlugo sci,powiedzmyk,natekstydowolnejdlugo sci.
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 22
3.3.1 Elektroniczna ksia_ kodowa
zka
,
Elektronicznaksia_kodowa(inaczejECB,czyliElectronicfunkcjo-
zka Codebook)
,
nujejaknastepuje(patrzrys.3.3):tekstjawnydzielonyjestnablokidlugo scik.
,
Kazdyztychblok owjestoddzielnieszyfrowanyprzypomocytegosamegoklucza.
_
tekstjawny
blok1blok2blok3
? ? ?
- - -
KDESKDESKDES
? ? ?
kryptogram
Rysunek3.3:SchemattrybuECB
TrybECBmata,zalete,zeuszkodzenielubutratapojedynczychblok ownie
_
,
mawplywunamozliwo s cdeszyfrowaniapozostalychcze scikryptogramu.Zdrugiej
_
,
stronymozliwyjestatakniewymagajacyzlamaniaszyfru.Prze sledzimytona
_
,
nastepujacymprzykladzie:
, ,
PrzykladatakunaECB:Zal o_zekomunikacjapomiedzydwomabankami
zmy,_
,
odbywasie,wtrybieECB.Wtenspos obszyfrowanesa,przelewymiedzykontami
,
obubank ow.Zal o_zespecy kacjakont,najakienalezydokona cprzelew owma
zmy,_ _
nastepujaca,posta c:
, ,
przelew=kon-toodbior-cawarto s cprzelewu
kryptogram=blok1blok2blok3blok4blok5blok6
PrzestepcaMallet,kt oryjestwstaniemody kowa ctre s ckryptogram ownaply-
,
wajacychdobanku,mozeprzeprowadzi cnastepujacyatak:
_
, , ,
1.Malletdokonuje17przelew ownaswekonto,zawszete,sama,kwote,pieniedzy.
,
Nastepnieidenty kujewprzesylanychkryptogramachtakikryptogramkonta,
,
nakt orydokonanodokladnie17przelew owiwdodatkunate,sama,kwote.
,
Malletmozewtymmomenciezalozy c,zechodzituojegokonto.Wtenspos ob
_ __
poznajekryptogramnumeruswegokontamimo,iznieznakluczauzytegodo
_ _
szyfrowania.
2.Malletzamieniawpewnejilo sciprzeplywajacychkryptogram owkodnumeru
,
konta,wstawiajacnatomiejscekryptogramnumeruswegokonta.Dziekitemu
, ,
bankdopisujedokontaMalletakwotyprzeznaczonepierwotniedlainnych
os ob.
3.Malletsprawdzastanswegokontaidokonujeprzelewunaswekontowkraju,
zkt orymniepodpisanoumowyoekstradycji.Nastepnieudajesie, sladem
,
pieniedzyzanimkto ssie,zorientuje.
,
Abyunikna csytuacjiopisanejpowyzejtrzebauzy cbezpieczniejszegotrybuszy-
__
,
frowania.Dwatakietrybyopisujemyponizej.
_
Jakociekawostke,dodajmy,zemimowskazanychpowyzejzagrozeninstytucje
_ __
nansoweczestolekkomy slnieuzywaja,trybuECBdotransmisjiwa_danych.
_ znych
,
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 23
3.3.2 Cipher Block Chaining
CipherBlockChaining(CBC)jestmetoda,dziekikt orejtensambloktekstu
, ,
jawnegojestszyfrowanywr o_miejscachwr o_spos ob.Osiaganejestto
znych zny
,
wnastepujacyspos ob.Rozwa_algorytmszyfrujacyblokidlugo scik.Niech
zmy
, , ,
EK(X)oznaczakryptogramuzyskanyztekstujawnegoXprzypomocyklucza
K.Je slitekstjawnyskladasie,zblok owP1 dlugo scik,tokryptogram
P2 P3 : : :
uzyskanyprzypomocykluczaKskladasie,blok owC1(r owniezdlugo sci
C2 C3 _
: : :
k)zde niowanychnastepujaco:
, ,
C1=EK(P1)
XOR I
Ci=EK(Pi):
XOR Ci;1
CiagIwystepuja,cywpowyzszymwzorzejestgenerowanylosowoiprzesylanyw
_
, ,
spos obniezaszyfrowany.Zauwa_zekryptogramyposzczeg olnychblok owsa,ze
zmy,_
soba,powiazane:dlaotrzymaniaCiwykorzystujemyCi;1,anietylkoPi.Poniewa_
z
,
CizalezyodCi;1,aCi+1odCi,wiecpo srednioCi+1zalezyodCi;1.Zalezno sci
_ _ _
,
tegotypuprzenosza,sie,dalejiostatecznieka_blokCjjestzaleznyodwszystkich
zdy _
blok owC1 ,acozatymidzier owniezodI P2 .
: : : Cj;1 _P1 : : : Pj;1
Deszyfrowywanietakuzyskanychkryptogram owjeststosunkowoproste(ponizej
_
Doznaczafunkcje,deszyfrujaca,dlablok owdlugo scik):
,
P1=DK(C1)XOR I
Pi=DK(Ci)XOR Ci;1: (3.2)
Odnotujmykilkawlasno sciszyfrowaniawtrybieCBC:
Zaleta:takiesameblokizregulysa,reprezentowanezregulypoprzezbloki
r o_postaciwkryptogramie.Cowiecej,tensamtekstjawnyjestszyfrowany
znej
,
winnyspos ob,oilewybierzemyinnycia,gpoczatkowyI.
,
Wada:niemoznazadnegoblokuCiusuna czkryptogramu.Stwarzato
__
,
klopoty,oilepragneliby smyprzypomocyCBCszyfrowa czawarto s cbazda-
,
nych.Podobneproblemynapotykamyprzypr obiewprowadzeniadodatkowego
blokuw srodkutekstujawnego:odtegomiejscacalykryptogrammusiby c
utworzonynanowo.
Wada:podzialnablokimusiby codpornynazakl ocenia(dodatkowybitlub
utratapojedynczegobituprowadza,dodesynchronizacjiszyfrowaniaideszy-
frowania).
Zaleta:przeklamaniawewnatrzjednegobloku(bezzmianyilo scibit pro-
ow)
,
wadza,doprzeklamanpodeszyfrowaniu,alejedyniewbloku,wkt orymna-
stapiloprzeklamanieiblokunastepujacymponim.Wlasno s ctawynika
, , ,
bezpo sredniozwzoru(3.2).
3.3.3 Cypher Feedback
CFB,czylicypherjestdrugimbezpiecznymtrybemszyfrowaniadlugich
feedback,
tekst ow.Wodr o_doCBCszyfrowanesa,niecalebloki,alefragmentyzlozone
znieniu _
z8bit ow,czyliwpraktyce1litera.Trybtenmozeby cuzytynaprzykladdla
__
zabezpieczeniakomunikacjipomiedzyklawiatura,iserwerem.Oczywistejest,ze
_
,
wtejsytuacjiniezbednejestnatychmiastoweprzesylaniepojedynczychznak ow
,
bezczekanianazgromadzeniebloku8znak ow,jaktomialomiejscewprzypadku
korzystaniaztrybuCBC.Mozliwejestr owniezprzesylanieta,metoda,naprzyklad
_ _
pojedynczychbit ow.
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 24
SchematdzialaniaCFBprzedstawionyjestnarys.3.4,przyczymwykorzystano
DESjakometode,szyfrowaniapojedynczychblok ow.Jednymzzasadniczychsklad-
nik owCFBjestrejestrprzesuwajacy.Napoczatkuzawieraonlosowowygenerowany
, ,
ciag,kt oryjestprzesylanywniezaszyfrowanejpostaci.Wtrakcieka_taktu
zdego
,
pracyCFBprzyuzyciukluczaKwykonywanesa,nastepujaceoperacje:
_
, ,
1.Zawarto s crejestruprzesuwajacegojestszyfrowanaprzypomocykluczaK.
,
2.Zwytworzonegokryptogramupobieranychjestpierwszych8bit ow,bityte
sluza,dooperacjiXORz8bitamikodujacyminastepna,litere,podawana,
_ P
, ,
nawej sciu.Wwynikuotrzymujemyciago smiubit owZ.
,
3.CiagZtworzykolejnych8bit owwyniku.Ponadtowrejestrzeprzesuwajacym
, ,
wykonujemyprzesuniecieo8pozycji.Jesttoprzesuniecieniecykliczne{8
, ,
bit owzlewejstronyulegausunieciu.Zkoleinao smiuzwolnionychpozycjach
,
zapisywanyjestciagZ.
,
rejestrprzesuwajacy
,
?
-
kluczKDES
?
kryptogram
?
nastepnalitera8bit ow
,
? ?
Z
- -
P XOR
?
wyj scie
Rysunek3.4:SchemattrybuCFB
3.4IDEA
Wielepr obpodejmowanychbylonadzaprojektowaniemalgorytmu,kt oryzastapilby
,
DES.Jedna,zprzyczynbyloprzekonanie,zewielko s ckluczyDES-ajestzamala.
_
Inna,wa_a,przyczyna,bylyregulacjeprawnewUSAuznajaceDESzaprodukto
zn
,
znaczeniumilitarnymiuzywaniegopozagranicamiUSAbezstosownychlicencji
_
zaczynprzestepczy.Poniewa_utrudniatostosowaniekryptogra iwkontaktachz
z
,
partneramizUSAispozaUSA,istniejepotrzebaznalezieniaalgorytmu,kt orego
stosowanienieprowadzilobydokon ikt owzameryka organamibezpieczen-
nskimi
stwa.Celeteprzy swiecalypowstaniualgorytmu(InternationalDataEncryption
Standard),wskr ocieIDEA.
Wlasno sciIDEA:
IDEAjestalgorytmem,zkt oregomoznakorzysta cbezplatniedocel ownie-
_
komercyjnych.AlgorytmjestopatentowanywEuropie.
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 25
IDEAjestalgorytmemnowym,wprowadzonymwlatachdziewie cdziesiatych.
, ,
Algorytmspotkalsie,zduzymzainteresowaniem,wtymr owniezje slichodzi
_ _
opr obyjegokryptoanalizy.Wobecstosunkowokr otkiegookresuodmomentu
jegoopublikowanianalezyzostrozno scia,podchodzi cdojegobezpieczenstwa.
__
IDEAwchodzijakojedenzkomponent owwskladPGP,popularnegopakietu
kryptogra cznego(patrzrozdz.13.0.16).
KluczeuzywaneprzezIDEAsa,zlozonez128bit ow.Wpraktyceoznacza
_ _
to,zeposzukiwaniepasujacegokluczadoparykryptogram{tekstjawnypo-
_
,
przezwypr obowywaniewszystkichkluczypokoleijestniewykonalne.Mimo
wielko scikluczyprogramyszyfrujaceideszyfrujacewedlugalgorytmuIDEA
, ,
niesa,wolniejszenizprogramyrealizujaceDES.
_
,
3.4.1 Szyfrowanie poprzez algorytm IDEA
Szyfrowanieskladasie,z8rund.Pojedyncza,runde,schematycznieprzedstawia
rys.3.5.Opr ocztegopoostatniejrundziedokonywanejestprzeksztalcenie
ko (patrzrys.3.8).Jegoznaczeniestaniesie,jasne,gdyomawia cbedzie-
ncowe
,
mydeszyfrowanie.
Kazdarundaprzeprowadzarozmaiteoperacjena16-bitowychblokach.Trzy
_
operacjesa,uzywane:
_
{XORdokonywanynaposzczeg olnychbitach,
{dodawaniemodulo216(oznaczanedalejsymbolem+),
{mnozeniemodulo(216+1)(oznaczanedalejsymbolem ).
_
Kluczzawiera128bit ow.Zniegogenerowanychjestszeregpodkluczy.W
( (
trakcierundyiu_jestsze s cpodkluczyZ1i) .
zywanych : : : Z6i)
Wodr o_dokluczy,tekstjawnyzawiera64bit ow.
znieniu
PrzebiegrundyalgorytmuIDEAzostalprzedstawionynarys.3.5.Danewej sciowe
dlarundyiskladaja,sie,z4blok owpo16bit owoznaczonychX1.Rezultat
: : : X4
skladasie,zblok ow16-bitowychoznaczonychY1.
: : : Y4
3.4.2 Generowanie podkluczy dla algorytmu IDEA
SzyfrowanieprzypomocyalgorytmuIDEAwymaga6 8+4podkluczy(8jestilo scia,
rund,ka_zrundwykorzystuje6podkluczy,dodatkowoprzeksztalcenieko
zda ncowe
u_4kluczy).Podkluczesa,generowanewnastepujacyspos ob:
zywa
, ,
1.Kluczjestdzielonynabloki16-bitowe.Dajetopierwszych8podkluczy(6
podkluczydlapierwszejrundy,2dladrugiejrundy).
2.Nakluczuwykonujesie,przesunieciecykliczneo25pozycji.Wynikjestna
,
nowodzielonynablokidlugo sci16.Dajetonastepnych8podkluczy(4
,
brakujacepodkluczedladrugiejrundy,4dlatrzeciejrundy).
,
3.Operacjezpunktu2powtarzamyazwygenerujemywszystkiepotrzebnepod-
_
klucze.
3.4.3 Deszyfrowanie przez IDEA
TakjakwprzypadkuDES-apotrzebnajestjaka ssprytnametoda,albowiembez-
po sredniowyliczy cdanewej sciowedlarundynapodstawiedanychwyj sciowychdla
rundybylobytrudno(por ownajrys.3.5).
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 26
X1:16bit owX2:16bit owX3:16bit owX4:16bit ow
? ? ? ?
( ( -
( -
(
Z1i) - j Z2i)+j Z3i)+j Z4i) - j
r
h (r
hhhh
((((
(((( hhhh
? ?
r -Xj r
Xj
h (
h (
? ?
(
Z5i) - j -+j
? ?
(
+j j Z6i)
? ?
r -Xj
Xj
? ?
-Xj
Xj r
hhhh ((((
hhhh
((((
( h
? ? ? ?
Y1:16bit owY2:16bit owY3:16bit owY4:16bit ow
. . . .
. . . .
. . . .
j
mnozenie
_
+j
dodawanie
XOR
Xj
Z1(i) (i) -podkluczerundyi
Z2 :::
Rysunek3.5:RundaialgorytmuIDEA
Ideadeszyfrowaniadlajednejrundy:Wprowad zmynastepujaceoznaczenia
, ,
(patrzrys.3.6):
( ( ( (
A=X1=X2+Z2i) =X3+Z3i) =X4 Z4i):
Z1i) B C D
Niech
E=B XOR=C XOR Y2
Y3 F
(por ownajrys.3.6).Latwozauwa_ckorzystajaczrys.3.6,ze
zy ,_
Y3=(B)XOR(E)=B XOR D:
XOR Y4 XOR E XOR D
Zatemmozemyobliczy cwarto s cB.Podobniemoznaobliczy cA.
_ XOR D _ XOR C
Zauwa_zeBiAsa,wynikamiotrzymywanymiprzezdwawezly
zmy,_XOR D XOR C
,
obliczajaceXORw srodkowejcze sciukladuprzedstawionegonarys.3.6.Takwiec
, , ,
( (
znajackluczeZ5i)iZ6i)moznaobliczy cEiF.Przyichpomocyotrzymujemy:
_
,
A=Y1 XOR=Y3 XOR=Y2 XOR=Y4 XOR E:
F B E C F D
( (
ZnajacA ipodkluczeZ1i) moznanakoniecwyliczy cX1.
B C D :_ : : : X4
: : Z4i)
,
Wopisanypowyzejspos obznajacpodkluczewyprowadzili smydanewej sciowe
_
,
rundyzjejwyniku.Wceluprzeprowadzeniadeszyfrowaniaczynimytodlawszyst-
kichrund,poczynajacodostatniej.
,
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 27
X1 X2 X3 X4
? ? ? ?
( ( -
( -
(
Z1i) - j Z2i)+j Z3i)+j Z4i) - j
r
h (r
hhhh
((((
(((( hhhh
? ?
r -Xj r
Xj
A XOR C
h (
h (
? ?B XOR D
(
j j
l l
Z5i) - k -+k
? ?
(
+j j Z6i)
A B E F C D
? ?
r -Xj
Xj
? ?
-Xj
Xj r
hhhh ((((
hhhh
((((
( h
? ? ? ?
Y1 Y2 Y3 Y4
. . . .
. . . .
. . . .
Rysunek3.6:MetodadeszyfrowaniadlaalgorytmuIDEA
Realizacjadeszyfrowania:Powyzejzauwa_smyjakdeszyfrowa cwprzypadku
_zyli
algorytmuIDEA.Je sliwykonywaneoperacjeprzedstawimyschematycznie(patrz
rys.3.7),tozauwa_uderzajacepodobienstwodooperacjiwykonywanychpod-
zamy,
czasrundyszyfrowania.Jedynar o_poleganatym,zearytmetyczneoperacje
znica _
wykonywaneprzyuzyciu4podkluczysa,wykonywanenienapoczatku,alenako
_ ncu
,
rundydeszyfrowania.Dziekitemutensamukladelektronicznymozeby cuzytyw
__
,
celuszyfrowaniaideszyfrowania.Jedynielogicznypodzialnarundyjestniecoinny:
najpierwprzeprowadzamyoperacje,poczatkowa,odpowiadajaca,operacjiko
ncowej
, , ,
szyfrowania,anastepniewykonujemy8rund,ka_znichzaczynajacasie,od
zda
, ,
operacjiXOR.
Podkluczeuzywanepodczasdeszyfrowaniaodpowiadaja,podkluczomszyfrowa-
_
niawylistowanymwinnejkolejno sci.Ponadtobyotrzyma cpodkluczedeszyfrowa-
niamusimycze s cpodkluczyodwr oci c(teuzywanedomnozenia)lubzanegowa c(te
_ _
,
u_dododawania).
zywane
ROZDZIAL3.ALGORYTMYSYMETRYCZNE 28
Y1 Y3 Y2 Y4
? r ? ?
?
h
hhhh (r
((((
(((( hhhh
? ?
r -Xj r
Xj
h (
h (
? ?
- j -+j
;1
(
Z5i)
(
? ?
Z6i)
+j j;
? ?
r -Xj
Xj
? ?
-Xj
Xj r
hhhh ((((
hhhh
((((
( h
? ? ? ?
;1 ;1
( -
( -
(
;Z2i)+j ;Z3i)+j ( - j
Z1i) - j Z4i)
? ? ? ?
X1 X3 X2 X4
Rysunek3.7:SchematdeszyfrowaniawalgorytmieIDEA
16bit ow16bit ow
16bitow16bitow16bit ow16bit ow
? ? ? ?
(9) -
(9) -
(9) -
(9) -
Z1.j Z2+j Z3+j Z4.j
XXX
Z
XX
Z
~ =
X
z 9
kryptogram
Rysunek3.8:Przeksztalcenieko walgorytmieIDEA
ncowe
Spis rzeczy
1Pierwszyrzutokanakryptogra e, 4
1.0.1Szyfrowaniedanych: : : : : : : : : : : : : : : : : : :4
: : : :
1.0.2Podstawowezastosowaniatechnikszyfrowania: : : : :5
: : : :
1.0.3Historiakryptogra i: : : : : : : : : : : : : : : : : : :8
: : : :
1.0.4Kontrowersjezwiazanezestosowaniemkryptogra i: :9
: : : :
,
1.0.5Korzystaniezprodukt owkryptogra cznych: : : : :10
: : : : :
2Podstawowetechnikiszyfrowania 12
2.0.6Podstawienie: : : : : : : : : : : : : : : : : : : : : :12
: : : : :
2.0.7XORione-timepad: : : : : : : : : : : : : : : : : :13
: : : : :
2.0.8S-boksy: : : : : : : : : : : : : : : : : : : : : : : : :15
: : : : :
3Algorytmysymetryczne 18
3.1DES{DataEncryptionStandard: : : : : : : : : : : : : :18
: : : : :
3.1.1SzyfrowanieDES-em: : : : : : : : : : : : : : : : : :19
: : : : :
3.1.2DeszyfrowanieDES-em: : : : : : : : : : : : : : : :21
: : : : :
3.2TrzykrotnyDES: : : : : : : : : : : : : : : : : : : : : : : :21
: : : : :
3.3Szyfrowanietekst owdowolnejdlugo sci: : : : : : : : : : : :21
: : : : :
3.3.1Elektronicznaksia_kodowa: : : : : : : : : : : :22
zka: : : : : :
,
3.3.2CipherBlockChaining: : : : : : : : : : : : : : : : :23
: : : : :
3.3.3CypherFeedback: : : : : : : : : : : : : : : : : : : :23
: : : : :
3.4IDEA: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :24
: : : : :
3.4.1SzyfrowaniepoprzezalgorytmIDEA: : : : : : : : :25
: : : : :
3.4.2GenerowaniepodkluczydlaalgorytmuIDEA: : : :25
: : : : :
3.4.3DeszyfrowanieprzezIDEA: : : : : : : : : : : : : :25
: : : : :
4Algorytmyniesymetryczne 29
4.0.4Teoriazlozono sciobliczeniowejakryptogra a: : : :29
_ : : : : :
4.0.5Szyfryplecakowe: : : : : : : : : : : : : : : : : : : :30
: : : : :
4.1RSA: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :32
: : : : :
4.1.1OpisalgorytmuRSA: : : : : : : : : : : : : : : : : :33
: : : : :
4.1.2Testypierwszo sci: : : : : : : : : : : : : : : : : : : :35
: : : : :
4.1.3AspektybezpieczenstwaRSA: : : : : : : : : : : : :37
: : : : :
4.1.4Trudnebitykryptogram owRSA: : : : : : : : : : :39
: : : : :
4.2AlgorytmElGamala: : : : : : : : : : : : : : : : : : : : : :41
: : : : :
5Funkcjejednokierunkowe 43
5.0.1Kandydacinafunkcjejednokierunkowe: : : : : : : :44
: : : : :
5.0.2Hard-corebit: : : : : : : : : : : : : : : : : : : : : :45
: : : : :
i
SPIS RZECZY ii
6Jednokierunkowefunkcjehashujace 46
,
6.0.3Wlasno sciizastosowaniafunkcjihashujacych: : : :46
: : : : :
,
6.0.4Atakiprzeciwfunkcjomhashujacym: : : : : : : : :47
: : : : :
,
6.1Technikiodowodliwychwlasno sciach: : : : : : : : : : : : :49
: : : : :
6.1.1Hashowanieprzypomocydyskretnegologarytmu: :49
: : : : :
6.1.2Rozszerzenienatekstydowolnejdlugo sci: : : : : : :50
: : : : :
6.2Praktycznealgorytmyhashujace: : : : : : : : : : : : : : :51
: : : : :
,
6.2.1MD5: : : : : : : : : : : : : : : : : : : : : : : : : : :51
: : : : :
6.2.2Hashowaniedowolniedlugichtekst ow: : : : : : : :52
: : : : :
7Ciagipseudolosowe 55
,
7.0.3Wlasno sciciag owpseudolosowych: : : : : : : : : :55
: : : : :
,
7.0.4Generatoryciag owpseudolosowych: : : : : : : : : :57
: : : : :
,
7.0.5Pseudolosowo s cgeneratoraBBS: : : : : : : : : : :59
: : : : :
7.1Zastosowaniaciag owpseudolosowych: : : : : : : : : : : : :59
: : : : :
,
7.1.1Szyfrowaniestrumieniowe: : : : : : : : : : : : : : :59
: : : : :
7.1.2Szyfrowanieprobabilistyczne: : : : : : : : : : : : :60
: : : : :
8Podpisycyfrowe 61
8.0.3PodpisycyfroweElGamala: : : : : : : : : : : : : :62
: : : : :
8.0.4DSA: : : : : : : : : : : : : : : : : : : : : : : : : : :63
: : : : :
8.0.5Slepepodpisy: : : : : : : : : : : : : : : : : : : : : :64
: : : : :
8.0.6Kanalpodprogowy: : : : : : : : : : : : : : : : : : :65
: : : : :
8.0.7Podpisyniezaprzeczalne: : : : : : : : : : : : : : : :66
: : : : :
9Uwierzytelnianie 69
9.0.8Protok olchallengeandresponse: : : : : : : : : : :69
: : : : :
9.0.9Dowodyinterakcyjne: : : : : : : : : : : : : : : : : :70
: : : : :
9.0.10Dowodyzwiedza,zerowa, : : : : : : : : : : : : : : :71
: : : : :
9.0.11Protok olFiege-Fiata-Shamira: : : : : : : : : : : : :73
: : : : :
9.0.12Protok olSchnorra: : : : : : : : : : : : : : : : : : :74
: : : : :
9.0.13Protok olGuillou-Quisquartera: : : : : : : : : : : :75
: : : : :
9.0.14Podpisycyfrowepoprzezuwierzytelnianie: : : : : :76
: : : : :
10Administracjakluczami 77
10.1Praktykagospodarkikluczami: : : : : : : : : : : : : : : : :77
: : : : :
10.1.1Urzadzeniekryptogra czne: : : : : : : : : : : : : :77
: : : : :
,
10.1.2Generowaniekluczy: : : : : : : : : : : : : : : : : :78
: : : : :
10.1.3Hierarchiakluczy: : : : : : : : : : : : : : : : : : : :79
: : : : :
10.1.4Przechowywaniekluczy: : : : : : : : : : : : : : : :79
: : : : :
10.2Protokolyuzgadnianiakluczy: : : : : : : : : : : : : : : : :80
: : : : :
10.2.1Uzgadnianiekluczypoprzezszyfrowaniesymetryczne:81
: : : :
10.2.2Uzgadnianiekluczaprzezszyfrowanieasymetryczne:82
: : : :
10.2.3Protok olDi e-Hellmanaijegopochodne: : : : : :82
: : : : :
11Protokolykryptogra czne 85
11.0.4Atakmaninthemiddle: : : : : : : : : : : : : : : :85
: : : : :
11.0.5Dzielenietajemnic: : : : : : : : : : : : : : : : : : :87
: : : : :
11.0.6Zobowiazaniebitowe: : : : : : : : : : : : : : : : : :88
: : : : :
,
11.0.7Pieniadzecyfrowe: : : : : : : : : : : : : : : : : : :90
: : : : :
,
11.0.8Elektronicznewybory: : : : : : : : : : : : : : : : :93
: : : : :
SPIS RZECZY iii
12Kryptoanaliza 95
12.0.9Kryptoanalizar o_: : : : : : : : : : : : : : :96
znicowa: : : : : :
12.0.10Kryptoanalizaliniowa: : : : : : : : : : : : : : : : :99
: : : : :
12.0.11R o_kryptoanalizabled ow: : : : : : : : : :100
znicowa : : : : : :
,
13Wybraneimplementacje 102
13.0.12Smartcards: : : : : : : : : : : : : : : : : : : : : :102
: : : : : :
13.0.13Krzyweeliptyczne: : : : : : : : : : : : : : : : : :103
: : : : : :
13.0.14Kerberos: : : : : : : : : : : : : : : : : : : : : : :103
: : : : : :
13.0.15Zabezpieczaniekomunikacjitelefonicznej: : : : : :106
: : : : : :
13.0.16PGP{PrettyGoodPrivacy: : : : : : : : : : : :107
: : : : : :
13.0.17Zabezpieczaniepocztyelektronicznej{PEM: : :108
: : : : : :
13.0.18BezpieczenstwowWWW: : : : : : : : : : : : : :109
: : : : : :
13.0.19Protokolyobrotu nansowego: : : : : : : : : : : :109
: : : : : :
AWybraneaspektyteoriiliczb 112
BTeoriaalgorytm ow 116
Przedmowa
Doniedawnakryptogra abylaobiektemzainteresowaniawwiekszymstopniusluzb
_
,
wywiadowczychiwojskanizprzedmiot owgospodarczychiprywatnychos ob.Postep
_
,
wdziedzinieelektronikiazwlaszczagwaltownyrozw ojsiecikomputerowychsytuacje,
te,zmienilywradykalnyspos ob.
Dawniej,gdyprywatnyuzytkownikdysponowaljedyniekomputeremPCnie
_
wlaczonymdosieci,ochronadanychbylastosunkowoprostaizapewnionaprzez
,
zycznydostepdokomputera.Natejsamejzasadziechronionebylydaneprzecho-
,
wywanewpostacielektronicznejprzezmale rmy,dzialy rm,organizacjepolitycz-
ne.Nieskomplikowaneprotokolykryptogra czne,alekluczdopomieszczeniazkom-
puterem,czykoperta,wkt orejprzesylanabyladyskietka,stanowilyochrone,przed
niepowolanymdostepem.Oczywi sciezdarzalysie,kradziezedyskietek,komputer ow,
_
,
wlamaniadosiedzibpartiipolitycznych:.Wiekszo s cuzytkownik ownieczulo
: : _
,
jednakpotrzebyskuteczniejszejochronyswychdanych.
Sytuacjazacze,lasie,radykalniezmienia czchwila,gwaltownegowzrostusieci
komputerowych.Dotyczylotonietylkosieciobejmujacychszeregdzial owpojedyn-
,
czych rm,aleisieciglobalne,takiejakInternet(wtymzwlaszczaWorldWide
Web).Zapewnieniebezpieczenstwawtychsieciachstalosie,jednymzpierwszo-
planowychzadandecydujacychoichdalszymrozwoju.Nowetechnikitelekomu-
,
nikacyjne,takiejaktelefoniakom orkowa,telewizjacyfrowa,telebanking,itp.,nie
moglybyznale z cswegomiejscawcodziennejpraktyce,gdybyniestosowanietechnik
kryptogra cznychdlaochronydostepu.
,
Najpierwrewolucjaobje,lakomunikacje,w srodowiskunaukowym.Pojawienie
sie,pocztyelektronicznejumozliwiloblyskawicznekontaktowaniesienaukowc owz
_
najdalszychkraj ow.Pozwolilotonaolbrzymiwzrostwydajno sciwwieludziedzi-
nachbadan.Moznabysie,spodziewa c,zekonkurencjaiostrawalkaoprzodownictwo
_ _
doprowadziw srodowiskunaukowymdowielunaduzy cpocztyelektronicznej.Tym
_
bardziej,zeniejesttrudnenaprzykladprzesla clistwtenspos ob,bynadawcapo
_
nagl owkum oglby cprzekonany,zepochodzionodinnejosoby.Mozliwejestr owniez
_ _ _
przechwytywaniekorespondencjiprzeznaczonejdoinnychadresat ow.Zjawiskate
jednakstanowilydotychczaswcalym srodowiskunaukowymbardzowaskimargines.
,
Powodemzapewnebyloto,izkomunikowalysie,osoby,kt oreitakobdarzalysie,
_
pelnymzaufaniem.Takwiecmetody,kt orepozwalalybynazabezpieczenieprzed
,
odczytem,mody kacja,czytezpreparowaniemlist owelektronicznychprzezosoby
_
trzecieniebylystosowane.
Teczasymine,ly.Wrazzpojawieniemsie,WorldWideWebInternetstalsie,
atrakcyjnydlaszaregouzytkownika\.WInterneciepojawilysie,interesujacezasoby
_
,
"
informacyjne,dziekiczemuilo s cuzytkownik owzacze,larosna cgwaltownie.Co
_
, ,
wiecej,Internetcorazcze sciejjestuzywanyniejakonarzedziezabawyczyrozwijania
_
, , ,
zainteresowa aledocel owkomercyjnych.Juzdzi sbiletylotniczekupuje,przez
n, _
Internet,literature,naukowa,wybieramprzezWorldWideWeb,azamiastkupowa c
gazete,zlokalnymiogloszeniamisiegamdojejelektronicznegoodpowiednika.W
,
takiejsytuacjibedziecorazwiecejos ob:hardwaretanieje,softwarestajesie,coraz
, ,
latwiejszydoobslugiprzezlaika,wwielukrajachpolaczeniatelefonicznewskutek
,
1
SPIS RZECZY 2
konkurencjinarynkutelekomunikacyjnymstaja,sie,tanszeiwyzszejjako sci.Coraz
_
latwiejszebedziezatemstaniesie,kolejnymuzytkownikiemInternetu.Zapare,lat
_
,
bedziemymie czapewnedoczynieniazsytuacja,gdyInternetbedzienajwiekszym
, , , ,
supermarketem,najobszerniejsza,gazeta,najwiekszymHydeParkiem,:{przynaj-
: :
, ,
mniejwkrajach,gdzieuslugitelekomunikacyjnebeda,wystarczajacotanie.
, ,
Jakka_wynalazek,rozw ojglobalnychsiecikomputerowychprzynosikorzy sci,
zdy
aleiniebezpieczenstwa.Wieledyskutujesie,naprzykladnatematmozliwo sci
_
wykorzystywaniaInternetuprzezorganizacjeprzestepcze.Sytuacjaprzypomina
,
niecosporypowynalezieniusamochodu.Niespos obcze sciowonieprzyzna cracji
,
przeciwnikomautomobilimajacprzedoczymatragicznestatystkiotysiacachludzi
, ,
zabitychnadrogach.Niecofne,lotojednakmotoryzacji,takjakniedoodwr ocenia
jestjuzrozw ojglobalnejsiecikomputerowejna swiecie.
_
Poniewa_poprzezInternetkomunikowa csie,beda,niedobrzyiufajacysobie
z
, ,
znajomi,leczczestoanonimowiczywrodzysobieuzytkownicy,mijaja,czasy,gdy
_
,
niezbytwielemy slanoobezpieczenstwiedanychikomunikacji.Zjednejstrony
podlaczeniedosiecikomputerowychstanowi cbedziewarunekwstepnyistnienia
, , ,
rm(takjakposiadanietelefonu,faxu,czyskrzynkipocztowej),zdrugiejstrony
podlaczenietostanowiomozliwo sciwlaman,dewastacjidanychiinnychdzialano
_
,
charakterzeprzestepczym.
,
Oczywi scieuzytkownicysiecikomputerowychbeda,siebroni cprzedniepowo-
_
,
lanymdostepemdodanychczymanipulacjamidokonywanyminanich.Pierwsza,
,
linia,obronybeda,oczywi sciesystemyoperacyjnezarzadzajacepraca,komputer owi
, , ,
wykonywaniemzlecennarzeczuzytkownik ow.Wwielumiejscachruchuwsieciach
_
komputerowych(kt oreuzyskalyjuzmodna,nazwe,)sprawdzanebeda,
_ infostrad
,
"
bilety\,apasazerowienagape,\beda,usuwanizruchu.R ownocze sniezadaniem
_
,
"
systemuoperacyjnegobedzieprzestrzeganie,czyuzytkownicydokonuja,jedyniedo-
_
,
zwolonychoperacji.
Wskutekzlozono scistawianychzadansystemyoperacyjnebeda,stawa csie,coraz
_ ,
bardziejskomplikowane.Tymsamymcoraztrudniejbedzieichtw orcomprzewidzie c
,
wszystkiemozliwo sci,takabyuniemozliwi cominieciezabezpieczenzainstalowanych
_ _
,
poprzezsystemoperacyjny.Dotychczasowedoniesieniaztegopolawalkisa,raczej
pesymistycznedlasystem owoperacyjnych.Stoja,onewobliczumiazdzacejprzewagi
__
,
wlamywaczyzwanychhackerami.Hackerzyniesa,jakbysie,chcialowierzy c,jedynie
,
grupa,nastoletnichmaniak owkomputerowych(czylagodniejm owiac,milo snik ow
,
technikkomputerowych).Jesttogrupaoolbrzymimpotencjaleintelektualnym,
nierzadkodoskonalymzapleczusprzetowymi nansowym.
,
Ostatnia,szansa,nazagwarantowaniebezpieczenstwadanychjestkryptogra a.
Niemozeonausuna cwszelkichniebezpieczenstw(jaknaprzykladzniszczenieda-
_
,
nychprzezwlamywaczakomputerowego),alewwielusytuacjachskuteczniepomaga
(naprzykladuniemozliwiaodczytdanychprzezniepowolana,osobe).Wodr o_
_ znieniu
,
doinnychmetodkryptogra adostarczametodwzgledniebezpiecznych.Takbez-
,
piecznych,zeliniamitelekomunikacyjnymidokonujesie,cochwilaprzelew ownie-
_
wyobrazalnychdlaszaregoczlowiekasum.Iniktsie,niemartwi,zekto swlaczysie,
_ _
,
nalinie,ita,droga,powiekszystanswegokontaoile smilion owdolar ow(zkt orymi
,
odlecinatychmiastnawyspypoludniowegoPacy kudokraju,zkt orymzapomniano
zawrze cumowe,oekstardycjiprzestepc ow).
,
MiroslawKutylowski
Wstep
,
Niniejszaksia_mazazadaniewbardzozwiezlyspos obprzedstawi cpodstawowe
zka
, ,
metodykryptogra czne.Wieleinteresujacychtechnikkryptogra cznychzostalow
,
niejpominietych.Naciskpolozonyzostalnateaspekty,kt oremaja,bad zmie cmoga,
_
, ,
praktycznezastosowanie.Wskutektegowieleteoretycznieciekawychzagadnien
swiadomienieporuszamywtejksia_Zdrugiejstrony,naszymzamyslembylo,na
zce.
,
tylenailetojestmozliwewtakkr otkiejpozycji,umozliwi cczytelnikowizrozumienie
_ _
matematycznychmechanizm owtkwiacychwkryptogra i.Tymksia_tar o_sie,
zkazni
, ,
naprzykladoddostepnejnapolskimrynkupozycjiBruce'aSchneiera[6],majacej
, ,
bardziejcharakterencyklopediinizpodrecznika.
_
,
Niniejszaksia_przeznaczonajestdlastudent owinformatykiipokrewnych
zka
,
dziedzin.Mozeby cwykorzystanajakopodrecznikdosemestralnegowykladuzkry-
_
,
ptogra i,jakr owniezjakomaterialdosamodzielnegostudiowania.Dozrozumie-
_
nianiekt orychcze sciksia_niezbednajestznajomo s cpewnychfakt owzalgebry.
zki,
, ,
Czytelniknieobeznanyztymizagadnieniamimozeznale z cbrakujaceinformacjew
_
,
DodatkuA.Niekiedykoniecznajestznajomo s cstandardowychfakt owzpodstaw
informatykiwykladanychnapierwszychlatachstudi owinformatycznych.Cze s c
,
tychpoje cskr otowoprzedstawiamywDodatkuB.
,
Niniejszaksia_opartajestnacze sciskryptudowykladuMiroslawaKutylow-
zka
, ,
skiego.Wykladtenodbylsie,naWydzialeMatematykiiInformatykiUniwersytetu
Paderbornwsemestrzezimowym1995roku.Wspomnianyskryptobejmujepr ocz
kryptogra izagadnieniakod owsamokorygujacychbledyikompresjidanych.Jest
, ,
ondostepnypoprzezWorldWideWebpodadresem
,
http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/ikk95/skript. ps.gz
Listazauwa_bled ow,uzupelnienia,itp.znajduja,sie,wWorldWideWeb
zonych,
podadresem
http: //www. uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/kryptogra a/
Pragniemypodziekowa clicznymstudentomzaudzielona,pomoc.Wszczeg olno-
,
sciwymieni cchcieliby smyGuidoHaeselera,kt oregonotatkidowykladuwLatex-u
bylypodstawa,pierwszejwersjiskryptu(iszeregurysunk owzawartychwksia_
zce).
,
Cze s crysunk owzostalawykonanaprzezFrankaBesteiEwe,Kutylowska.
, ,
3