Main

rcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
1.4. Lucifer/DES 5
1.4 Lucifer/DES
IBM vytvoˇrila n´avrh ˇsifry, kterou pot´e NSA upravila. Standardem se v´ysledn´a ˇsifra
stala v roce 1976. Jaka standard fungova DES aˇz do roku 2001.
ˇSifra se stala absolutn´ım pr˚ulomem v kryptologii. D´ıky ˇspatn´e dohodˇe mezi
NSA a NIST nebyla ˇsifra pouˇzita jen pro hardwarovou implementaci (schovan´a v
bezpeˇcn´em pouzdru), ale publikov´ana s ´upln´ym popisem jako otevˇren´y standard.
Spoleˇcnˇe s asymetrickou kryptografi´ı to byl hlavn´ı impuls pro rozvoj kryptologie v
otevˇren´em prostˇred´ı a literatuˇre.
...
1.5 Kryptologie v Informaˇcn´ı bezpeˇcnost
1.5.1 Kryptologie
• language theory
• number theory
• algebra – theory of groups
• combinatorial logic
• complexity theory
• ergodic theory – group statistical properties
• theory of information
• ...
1.5.2 Informaˇcn´ı bezpeˇcnost
• communication protocols
• software engineering
• programming languages
• data formats
• operating systems
• random numbers
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
6 Kapitola 1. ´Uvod
• distributed systems
• computer architectures ...
See things differently from designers
1.6 Protokoly
Hlavn´ımi dvˇema c´ıli jsou
• authentication
• secure data exchange
Na protokoly existuje velk´e mnoˇzstv´ı r˚uzn´ych ´utok˚u – pˇrehr´an´ı (replay), odraz
(reflection), muˇz uprostˇred (man-in-the-middle), vkl´ad´an´ı chyb (fault-injection).
Uk´azka – Needham-Schroeder protokol s veˇrejn´ym kl´ıˇcem
A→B: A, B, (NA, A)PKB
B→A: B, A, (NA, NB)PKA
A→B: A, B, (NB)PKB
Autentizaˇcn´ı protokoly jsouzaloˇzeny natˇrech implicitn´ıch sd´ılen´ych tajemstvt´ıch.
Podle toho, co mus´ı splnit uˇzivatele rozdˇelujeme tajemstv´ı na:
• what you know
• what you have
• what you are
1.7 Digit´aln´ı podpis
problemareas cryptographicprotocols engineeringprocedural/administrativearchiv-
ing
Does asymmetric cryptography really helps?
1.8 Soukrom´ı
big brother v citizens
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
1.9. Dalˇs´ı literatura 7
1.9 Dalˇs´ı literatura
Bohuˇzel, v ˇcesk´em jazyce neexistuje kvalitn´ı uˇcebn´ı text. Pro ty, kteˇr´ı maj´ı o bez-
peˇcnost a kryptografii z´ajem tak doporuˇcuji n´asleduj´ıc´ı knihy, kter´e jsou zhruba
seˇrazeny od praktiˇctˇejˇs´ıch k nejteoretiˇctˇejˇs´ım.
• R. Anderson. Security Engineering: A Guide to Building Dependable Distributed
Systems. Wiley Computer Publishing, 2001.
• B. Schneier. Beyond Fear: Thinking Sensibly About Security in an Uncertain
World. Springer-Verlag New York Inc., 2003.
• B. Schneier. Secrets and Lies: Digital Security in a Networked World. Hungry
Minds Inc, 2004.
• H. X. Mel. Cryptography Decrypted. Addison Wesley, 2001.
• B. Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C.
John Wiley & Sons, 1995.
• A.J.Menezes, P.van Oorschot,S.A.Vanston. Handbook of Applied Cryptography.
CRC Press, 1996. Nebo http://www.cacr.math.uwaterloo.ca/hac/
• D. Kahn. The Codebreakers: The Comprehensive History of Secret Communica-
tion from Ancient Times to the Internet. Simon & Schuster, 1996.
• F. L. Bauer. Decrypted Secrets: Methods and Maxims of Cryptology. Springer-
Verlag Berlin and Heidelberg, 2002.
• O. Goldreich. Foundations of Cryptography: Basic Tools Vol 1. Cambridge Uni-
versity Press, 2001.
• O. Goldreich. Foundations of Cryptography: Basic Applications Vol 2. Cambridge
University Press, 2004.
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
DRAFT Not Proofread
9
ˇC´ast I
Kryptologie
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
DRAFT Not Proofread
11
Kapitola 2
Z´aklady kryptologie
2.1 O ˇcem vlastnˇe je kryptografie
we will have parties A (Alice), and B (Bob) cryptography enables two parties to
securely communicate protocol distributed algorithm goals v threats, we need to
think about Eve security as strong as the weakest link
2.2 Bezpeˇcnostn´ı vlastnosti – c´ıle
confidentiality Eve shouldn’t find out the content
integrity Eve shouldn’t be able to change the content
authentication Eve shouldn’t be able to masquerade as Alice
non-repudiation one can prove all Alice/Bob has done
Q: what is the difference between authentication and non-repudiation
2.3 Symetrick´a kryptografie
Alice and Bob share a key Eve doesn’t know
key – a random string of k bits
how many bits is enough?
• number of people 5×109
• mass of the earth 5.98×1027 grams
• visible space – 1.7×1077 hydrogen atoms
DRAFT Not Proofread
12 Kapitola 2. Z´aklady kryptologie
currently, 128 bits of randomness is assumed secure
2.4 Kryptografie s veˇrejn´ym kl´ıˇcem
Alice and Bob each generate public and secret key
only public keys are exchanged – Eve may know them
key size 1024-2048 bits
problem is to link keys to users⇒one still has to ensure integrity – how much
easier is it compared to confidentiality?
2.5 Symetrick´a v asymetrick´a kryptografie
2.5.1 key distribution
2.5.2 computational complexity
2.5.3 key revocation
2.6 Kryptografie v protokolech
A→B : A, B, (NA,A)PKB
B→A : B, A, (NA,NB)PKA
A→B : A, B, (NB)PKB
attack goes as follows:
A→I: A, I, (NA,A)PKI
I(A)→B: A, B, (NA,A)PKB
B→I(A): B, A, (NA,NB)PKA
I→A: I, A, (NA,NB)PKA
A→I: A, I, (NB)PKI
I(A)→B: A, B, (NB)PKB
2.7 Teorie pravdˇepodobnosti
...
Jedn´ım z nejˇcastˇeji pouˇz´ıvan´ych fakt˚u je ˇreˇsen´ı tzv. narozeninov´eho probl´emu.
ˇCist´a definice je n´asleduj´ıc´ı.
Mˇejme urnu s m kuliˇckami, kter´e jsou oˇc´ıslovan´e 1 aˇz m. Nyn´ı budeme postupnˇe
tahat celkem n kuliˇcek s n´avratem (taˇzenou kuliˇcku vrac´ıme zp´atky do urny. Jak´a je
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
2.8. Teorie informace – entropie 13
pravdˇepodobnost alespoˇn jedn´e shody – kuliˇcka se stejn´ym ˇc´ıslem je taˇzena alespoˇn
dvakr´at?
Nejdˇr´ıve definujeme funkci P(m,n): P(m,n) = 1−m!n! mn. Nyn´ı, jestliˇze n =√m,
pak pro m→∞plat´ı, ˇze
P(m,n)≈1−exp(−n
2
2m )
tak´e plat´ı, ˇze
P(m,n) = 1−exp(−m2m ) =
radicalbig
((pim)/2) = 1.25√m
2.8 Teorie informace – entropie
ˇReknˇeme, ˇze X = x1,x2,...,xn je n´ahodn´a promˇenn´a, pro kterou d´ale plat´ı, ˇze
P(X = xi) = pi a Σipi = 1.
Entropy je definov´ana jako H(X) = −Σpi lgpi = Σpi lg(1/pi). Pouˇz´ıvan´a kon-
vence pro hraniˇcn´ı hodnoty je, ˇze pi lg(1/pi) = 0 pr´avˇe kdyˇz plat´ı, ˇze pi = 0.
Nˇekter´e z´akladn´ı vlastnosti:
• H(X)∈〈0,lgn〉
• H(X) = 0 pr´avˇe kdyˇz existuje pi : pi = 1
• H(X) = lgn pr´avˇe kdyˇz∀i : pi = 1/n
2.9 Sloˇzitost
Algoritmus je dobˇre definovan´a v´ypoˇcetn´ı procedura (postup). Algoritmus m´a vs-
tupn´ı promˇenn´e a vˇzdy se v koneˇcn´em ˇcase zastav´ı a vr´at´ı v´ystupn´ı hodnoty.
Velikost dat, tj. vstupu a v´ystupu algoritmu je minim´aln´ı poˇcet bit˚u potˇrebn´y
pro reprezentaci hodnot pˇr´ısluˇsn´ych dat.
Z hlediska sloˇzitosti n´as zaj´ım´a sloˇzitost ˇcasov´a a prostorov´a. V obou pˇr´ıpadech
je moˇzn´e spoˇc´ıtat: nejhorˇs´ı pˇr´ıpad a pr˚umˇernou hodnotu.
Aby bylo moˇzn´e abstraktnˇe uvaˇzovat o sloˇzitosti definujeme asymptotick´e ohra-
niˇcen´ı. Tj. hranice pro nekoneˇcn´e mnoˇzstv´ı hodnot, nebo nekoneˇcnou velikost dat.
2.9.1 Asymptotick´a sloˇzitost
asymptotic upper bound f(n) = O(g(n)) if there exists a positive constant c
and integer n0 such that 0≤f(n)≤cg(n), for all n≥n0
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
14 Kapitola 2. Z´aklady kryptologie
asymptotic lower bound f(n) = Ω(g(n)) ...0≤cg(n)≤f(n), for all n≥n0
asymptotic tight bound f(n) = Θ(g(n)) constants c1,c2, ...c1g(n) ≤ f(n) ≤
c2g(n), for all n≥n0
o-notation f(n) = o(g(n)) if for any positive constant c ...0≤f(n) < cg(n), for
all n≥n0
2.9.2 Tˇr´ıdy sloˇzitosti
Druhou oblast´ı, kde n´as zaj´ım´a definice sloˇzitosti je definice sloˇzitosti probl´em˚u, coˇz
je abstraktnˇejˇs´ı pojem, neˇz u algoritm˚u. V tomto pˇr´ıpadˇe n´as zaj´ım´a jen nˇekolik
z´akladn´ıch mnoˇzin sloˇzitosti. Hranic´ı je pro n´as algoritmus s polynomi´aln´ım ˇcasem
O(nk), kde k je konstanta nez´avisl´a na n, coˇz je velikost vstupn´ıch dat.
Algoritmus, kter´y nen´ı moˇzn´e ohraniˇcit pomoc´ı funkce O(nk) naz´yv´ame algorit-
mem s exponenci´aln´ım ˇcasem.
Pozn: ˇr´ıkali jsme, ˇze hranice pro odhad sloˇzitosti jsou asymptotick´e, kter´a z n´asle-
duj´ıc´ıch sloˇzitost´ı (O(nlnnlnn) a O(n100)) je lepˇs´ı pro rozumnˇe mal´e hodnoty vs-
tupn´ıch dat?
Z´akladn´ı tˇr´ıdy sloˇzitosti jsou:
complexity class P -– polynomial time complexity
complexity class NP -– polynomial time complexity, given a certificate
complete NP problems -– e.g. subset sum problem
Zcela samostatnou kapitolou, kter´a uˇz je mimo r´amec tohoto dokumentu jsou
randomizovan´e probl´emy.
2.10 Faktorizace cel´ych ˇc´ısel
Libovoln´e cel´e ˇc´ıslo n je moˇzn´e rozepsat na souˇcin prvoˇc´ısel n = pe11 pe22 ...pekk , kde
pi jsou prvoˇc´ısla. V souˇcasn´e dobˇe je hled´an´ı souˇcinu prvoˇc´ısel pov´aˇzov´ano ze sloˇzit´y
probl´em, tedy probl´em tˇr´ıdy NP. Specifickou podtˇr´ıdou probl´emu je RSA probl´em.
RSA probl´em je definov´an jako hled´an´ı rozkladu pro n = p.q, kde p a q jsou
prvoˇc´ısla. ˇSifra postaven´a na obt´ıˇznosti tohoto probl´emu je n´asleduj´ıc´ı.
Mˇejme n = p.q, d´ale pak e takov´e, ˇze gcd(e,(p−1)(q−1)) = 1. Zlomen´ı ˇsifry
znamen´a, ˇze pro cel´e ˇc´ıslo c najdeme m takov´e, ˇze me≡c(modn).
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
2.11. Klasick´a kryptografie 15
2.11 Klasick´a kryptografie
crypto-world.info CryptoWorld 9-12/04, nebo roˇcn´ık 2000
substituce – ˇsifry, kter´e zamˇeˇnuj´ı znaky za jin´e podle definovan´ych abeced. Bud’
m´amejenjednuabecedu(monoalfabetick´e), nebov´ıceabeced,kter´e stˇr´ıd´ame(polyal-
fabetick´e). Pˇr´ıklad monoalfabetick´e ˇsifry je Caesarova ˇsifra, pro polyalfabetick´e jsou
to Vigenere a Beaufort.
permutace – prohazov´an´ı znak˚u, jejich pozic. ˇSifrov´y text obsahuje stejn´e znaky
jako otevˇren´y text, ale jsou prom´ıchan´e.
2.12 Modern´ı kryptografie
pouˇz´ıv´an´ı poˇc´ıtaˇc˚u – obrovsk´y n´arust poˇctu operac´ı, kter´e jsme schopni prov´adˇet
pˇri ˇsifrov´an´ı.
ˇsifry st´ale pouˇz´ıvaj´ı dva p˚uvodn´ı principy. Substituce je realizov´ana pomoc´ı S-
box˚u, permutace jsou pak pevnˇe definovan´e v n´avrhu ˇsifry.
Kerckhoff˚uv princip–kryptosyst´em by mˇel b´ytbezoeˇcn´y iv pˇr´ıpadˇe, kdy vˇsechno
ohlednˇe konstrukce a fungov´an´ı syst´em˚u je veˇrejnˇe zn´am´e – kromˇe kl´ıˇce.
security through obscurity ...
2.12.1 One-time pad
ˇSifra s bezpeˇcnostn´ı dok´azanou na ´urovni teorie informace. Alice a Bob se pˇredem
dohodnou na dlouh´e n´ahodn´e sekvenci a. ˇSifrov´an´ı prob´ıh´a tak, ˇze kaˇzd´a zpr´ava je
xorov´ana s jeˇstˇe nikdy nepouˇzitou ˇc´ast´ı sekvencea.
D˚ukaz o bezpeˇcnosti ˇsifry je zaloˇzen na n´asleduj´ıc´ıch pˇredpokladech:
• a a ani ˇz´adn´a jej´ı ˇc´ast nen´ı nikdy pouˇzita dvakr´at
• a je opravdu n´ahodn´a – toto bylo poruˇseno bˇehem WWII, kdy n´ahodn´e sekvence
generovaly sekret´aˇrky napsac´ıch stroj´ıch.Ty pˇrirozenˇe pouˇz´ıvaly nˇekter´a p´ısmena
ˇcastˇeji a souˇcasnˇe vytv´aˇrely sekvence, kter´e se ˇcasto opakovaly.
Poruˇsen´ı prvn´ıho principu umoˇzˇnuje z´ıskat ˇc´asteˇcnou znalost o otevˇren´ych tex-
tech M1 a M2, a to M1⊕M2. Vzhledem k tomu, ˇze pˇrirozen´y jazyk obsahuje velkou
redundanci, tak tato ˇc´asteˇcn´a znalost umoˇzˇnuje rekonstruovat oba p˚uvodn´ı texty.
2.12.2 Gener´atory n´ahodn´ych ˇc´ısel – RNG
Vˇzdy potˇrebujeme nˇejak´e n´ahodn´e bity, ˇc´ısla, nebo sekvence.
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
16 Kapitola 2. Z´aklady kryptologie
Generov´an´ı n´ahodn´ych ˇc´ısel je moˇzn´e dˇelat hardwarovˇe za pouˇzit´ı fyzik´aln´ıch
zdroj˚u n´ahodnosti, nebo programovˇe pomoc´ı nˇejak´eho deterministick´eho algoritmu.
Gener´atory pseudon´ahodn´ychˇc´ısel (pseudorandom number generators – PRNG).
Z´akladn´ı pravidlo pro rozezn´an´ı n´ahodn´e sekvence je:
Libovoln´a koneˇcn´a sekvence je n´ahodn´a, jestliˇze neexistuje ˇz´adn´a kratˇs´ı sekvence,
kter´a by ji plnˇe popisovala v nˇejak´em jednoznaˇcn´em matematick´em z´apisu.
I pro RNG je moˇzn´e prov´adˇet anal´yzu bezpeˇcnosti jejich n´avrhu, kdy hodnot´ıme
vlastnosti PRNG n´avrhu a jeho principy fungov´an´ı.
Druhou moˇznost´ı testov´an´ı kvality gener´ator˚u, tentokr´at TRNG je statistick´e
testov´an´ı v´ysledn´ych n´ahodn´ych sekvenc´ı.
Jestliˇze m´ame k dispozici kvalitn´ı RNG, kter´y je pouze vych´ylen tak, ˇze generuje
vˇetˇs´ı mnoˇzstv´ı nul, neˇz jedniˇcek, tak m˚uˇzeme pouˇz´ıt jednu z nˇekolika metod.
• Von Neumann metoda
• xor
2.13 Kryptografick´e ´utoky
Kryptografick´e ´utoky a kryptoanal´yzu budeme podrobnˇeji prob´ırat pozdˇeji. V t´eto
chv´ıli si pouze definujeme tˇr´ıdy moˇzn´ych ´utok˚u.
pasivn´ı – napˇr. pro sch´emata veˇrejn´e kryptografie, kdy ´utoˇcn´ık zn´a veˇrejn´y kl´ıˇc
• key-oblivious (nez´avisl´e na kl´ıˇci) -– v´ybˇer ˇcist´eho textu pro ´utok je nez´avisl´y
na zn´am´em veˇrejn´em kl´ıˇci
• key-dependent (z´avisl´e na kl´ıˇci)
aktivn´ı – ´utoˇcn´ık se v tomto pˇr´ıpadˇe st´av´a aktivn´ım ´uˇcastn´ıkem protokolu/sch´e-
matu
• volen´y otevˇren´y text (chosen plaintext)
• volen´y ˇsifrov´y text (chosen ciphertext) – je tˇreba dalˇs´ıho pˇr´ıstupu k vˇeˇst´ırnˇe
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
17
Kapitola 3
Stavebn´ı bloky kryptografie
Vˇsechny postupy v kryptografii, vˇsechny algoritmy je moˇzn´e vytvoˇrit z nˇekolika m´alo
z´akladn´ıch funkc´ı. Tyto funkce velmi pˇeknˇe definoval Oded Goldreich ve sv´e knize
Foundations of Cryptography. Dva z´akladn´ı stavebn´ı bloky jsou jednosmˇern´e funkce
a hard-core predik´aty. Tyto dva z´akladn´ı bloky umoˇzˇnuj´ı vytvoˇrit vˇsechny dalˇs´ı typy
funkc´ı, kter´e bˇeˇznˇe pouˇz´ıv´ame - blokov´e ˇsifry, proudov´e ˇsifry, algoritmy s veˇrejn´ym
kl´ıˇcem, ....
3.1 Z´akladn´ı bloky
Pokusme si nejdˇr´ıv ˇr´ıci nˇeco o dvou jiˇz zm´ınˇen´ych primitiv´ach na kter´ych stoj´ı cel´a
modern´ı kryptografie.
3.1.1 Jednosmˇern´e funkce
Z´akladem souˇcasn´e kryptografie je rozd´ıl v´ypoˇcetn´ı obt´ıˇznost´ı mezi efektivn´ımi al-
goritmy, kter´e m˚uˇze pouˇz´ıvat vlastn´ık urˇcit´eho tajemstv´ı a n´aroˇcnost´ı stejn´ych al-
goritm˚u pro ´utoˇcn´ıka, kter´y potˇrebn´e tajemstv´ı nezn´a. Napˇr. u ˇsifrovac´ıch funkc´ı je
tˇreba, aby opr´avnˇen´y pˇr´ıjemce mohl zpr´avu rychle odˇsifrovat, ale ´utoˇcn´ık toto nesm´ı
b´yt schopen efektivnˇe udˇelat bez znalosti kl´ıˇce.
Jednosmˇern´a funkce je zvl´aˇstnˇe konstruovan´a funkce kterou je, velmi volnˇe ˇre-
ˇceno, snadn´e vypoˇc´ıtat, ale velmi obt´ıˇzn´e invertovat. Obt´ıˇzn´ym invertov´an´ı m´ame
na mysli situaci, kdy je tˇreba zkouˇset vˇsechny moˇzn´e vstupy, abychom nalezli ten,
kter´y d´av´a konkr´etn´ı v´ystupn´ı hodnotu.
3.1.2 Hard-core predik´aty
Je moˇzn´e vytvoˇrit z jednosmˇern´ych funkc´ı...
DRAFT Not Proofread
18 Kapitola 3. Stavebn´ı bloky kryptografie
3.2 Haˇsovac´ı funkce
Pˇrehled z´akladn´ıch mnoˇzin funkc´ı, kter´e pouˇz´ıv´ame pro kryptografii zaˇcneme haˇso-
vac´ımi funkcemi. Haˇsovac´ı funkce jsou jiˇz funkce, kter´e jsou pˇr´ımo pouˇz´ıv´any v
aplikac´ıch, kter´e obsahuj´ı nˇejak´e kryptografick´e funkce. V principu se jedn´a o jed-
nosmˇern´e funkce, kter´e ovˇsem mus´ı splˇnovat pˇresnˇe definovan´e podm´ınky. Z´akladn´ı
haˇsovac´ı funkce mapuj´ı ˇretˇezce o libovoln´e d´elce na ˇretˇezce o konstantn´ı d´elce.
Pˇr´ıkladem mohou b´yt kontroln´ı souˇcty, napˇr. CRC.
Kryptografick´e haˇsovac´ı funkce (oznaˇcme je na n´asleduj´ıc´ıch ˇr´adc´ıch f(.)) musej´ı
nav´ıc splˇnovat n´asleduj´ıc´ı ˇctyˇri podm´ınky:
1. je to jednosmˇern´a funkce
2. je obt´ıˇzn´e naj´ıt dva vstupy, kter´e se mapuj´ı na stejnou v´ystupn´ı hodnotu
3. jestliˇze m´ame danou v´ystupn´ı hodnotu y, tak je obt´ıˇzn´e naj´ıt vzor x, pro kter´y
plat´ı, ˇze y = f(x)
4. jestliˇze m´ame urˇcit´y vzor x1, je obt´ıˇzn´e naj´ıt jin´y vzor x2, pro kter´y by platilo,
ˇze f(x1) = f(x2).
V souˇcasn´e dobˇe existuje ˇrada kryptografick´ych haˇsovac´ıch funkc´ı, ale je prav-
dou, ˇze ty nejˇcastˇeji pouˇz´ıvan´e proch´azej´ı kriz´ı zapˇr´ıˇcinˇenou vynikaj´ıc´ımi kryp-
tografick´ymi v´ysledky v posledn´ıch dvou letech. Z nejbˇeˇznˇeji pouˇz´ıvan´ych funkc´ı je
tou nejstarˇs´ı MD5, kter´a m´a v´ystup dlouh´y 128 bit˚u. D´ıky narozeninov´emu paradoxu
je tedy efektivn´ı bezpeˇcnost haˇsovac´ı funkce 64 bit˚u, coˇz je pro bˇeˇzn´e aplikace st´ale
dostaˇcuj´ıc´ı. Druhou funkc´ı je SHA-1, kter´a m´a v´ystup dlouh´y 160 bit˚u. Tato funkce
m´a ovˇsem dalˇs´ı varianty SHA-256, SHA-384 a SHA-512, kde ˇc´ıslo oznaˇcuje d´elku
v´ystupu. Jako dalˇs´ı m˚uˇzeme jmenovat RIPEMD, coˇz je haˇsovac´ı funkce poch´azej´ıc´ı
z Evropy.
3.2.1 SHA-1
Funkce SHA-1 jeje definov´ana standardem !!!!!!! naz´akladˇe p˚uvodn´ıdefiniceSHA, ve
kter´e byly nalezeny bezpeˇcnostn´ı probl´emy. N´asleduj´ıc´ı obr´azek zn´azorˇnuje vnitˇrn´ı
strukturu funkce SHA-1, abychom demonstrovali jak takov´a funkce m˚uˇze vnitˇrnˇe
vypadat. Jak jsem se uˇz zm´ınili, tak v´ystup SHA=1 tvoˇr´ı 160 bitov´a ˇc´ısla. Jak´ykoliv
vstupn´ı blok se tedy rozdˇel´ı na ˇc´ast´ı po 20 bajtech. Pro vnitˇrn´ı zpracov´an´ı je tˇechto
20 bajt˚u rozdˇeleno na pˇet 32 bitov´ych slov, kter´e se zpracov´avaj´ı samostatnˇe. Kdyˇz
se d˚ukladnˇe pod´ıv´ame na obr´azek, tak se slovem se prov´ad´ı bud’ jednoduch´a rotace,
nebo se xoruje s dalˇs´ımi bloky a konstantami, nebo se aplikuje jednoduch´a neline´arn´ı
funkce D, kter´a se neust´ale mˇen´ı. Aˇckoliv je operace XOR rozklreslena ve ˇstyˇrech
Dan Cvrcek, DRAFT VERSION; printed on 29. ledna 2006
DRAFT Not Proofread
3.3. Autentizaˇcn´ı k´ody zpr´av – MAC 19
bloc´ıch, tak je moˇzn´e ji nakreslit jako jeden XOR seˇctyˇrmi vstupy. Velmi podstatnou
ˇc´ast´ı kaˇzd´eho kola je posun mezi slovy. Slovo A se po skonˇcen´ı stane slovem B, B se
stane slovem C, atd.
!!!!!!!!SHA 1 !!!!!!!!!!!!!
Zpracov´an´ı kaˇzd´ych 160 bit˚u vstupu se skl´ad´a z celkem osmdes´ati opakov´an´ı
bloku z obr. !!!!. Pro z´avˇereˇcnou ilustraci se pod´ıvejme, jak bude vypadat v´ystup
SHA-1 pro dvˇe vˇety, kter´e se liˇs´ı jen v jednom p´ısmenku:
SHA1(”The quick brown fox jumps over the lazy dog”) =
2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
SHA1(”The quick brown fox jumps over the lazy cog”) =
de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
3.3 Autentizaˇcn´ı k´ody zpr´av – MAC
MAX (message authentication code) je velmi kr´atk´a zpr´ava (o velikosti v´ystupu
haˇsovac´ı funkce, kter´y umoˇzˇnuje autentizovat obsah urˇcit´e zpr´avy. Obvykle je z´akla-
dem v´ypoˇctu haˇsovac´ı funkce, kter´a se aplikuje nˇekolikr´at a vstupem je kromˇe
samotn´e zpr´avy jeˇstˇe urˇcit´e tajemstv´ı. Toto tajemstv´ı zaruˇcuje, ze MAC nem˚uˇze
spoˇc´ıtat nikdo jin´y, neˇz ten kdo zn´a toto tajemstv´ı – tajemstv´ı/ heslo je obvykle
nˇejak spojeno se zpr´avou.
Alternativnˇe m˚uˇze b´yt MAC zaloˇzen na blokov´eˇsifˇre, V tomto pˇr´ıpadˇe m´ame dvˇe
moˇznosti jak pouˇz´ıthsslo–bud’budepouˇzito jako kl´ıˇc, kter´ym sezpr´avaˇsifruje,nebo
je opˇet nˇejak´ym zp˚usobem zkombinov´ano se zpr´avou a hodnota kl´ıˇce je nemˇenn´a a
je souˇc´ast´ı specifikace dan´eho algoritmu pro v´ypoˇcet MAC.
MAC je pro zpr´avy schopen zajistit dvˇe funkce. Jednak ho je moˇzn´e pouˇz´ıt k
ovˇeˇren´ı autentiˇcnosti zpr´avy a jednak umoˇzˇnuje ovˇeˇrit integritu pˇrijat´e zpr´avy – tj.
jestli nebyla od okamˇziku vytvoˇren´ı MAC nˇejak zmˇenˇena.
3.3.1 PMAC/OMAC
OMAC jsou funkcezaloˇzen´e nablokov´eˇsifˇre, napˇr. DES,neboAES. ˇSifrajepouˇzita v
m´odu CBC. Tento m´od znemoˇzˇnuje paraleln´ı zpracov´an´ı, takˇze jeden procesor mus´ı
zpracovat celou zpr´avu, abychom z´ıskali MAC hodnotu. Na rozd´ıl od tohoto, PMAC
je paralelizovateln´y MAC a sch´ema v´ypoˇctu je takov´e, ˇze kl´ıˇc generuje n´ahodnou
sekvenci, kter´a je xorov´ana se zpr