Kriptogr´afia ´es Inform´aci´obiztons´ag 4. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2015
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
blokk-titkos´ıt´ o rendszerek, DES (Data Encryption Standard), tervez´esi szempontok, biztons´ ag, t´ amad´ asi m´ odszerek, 3DES, 2DES, XDES, blokk-titkos´ıt´ asi m´ odok (ECB, CBC, CFB, OFB, CTR).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol lesz sz´o?
Sz´ amelm´eleti alapfogalmak: az euklideszi algoritmus ´es v´ altozatai V´eges testek aritmetik´ aja AES (Advanced Encryption Standard)
k¨ or-kulcs gener´al´as, titkos´ıt´as, visszafejt´es, implement´aci´ o.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Sz´amelm´eleti alapfogalmak Az euklideszi algoritmus egyike a legr´egebbi, napjainkban is alkalmazott elj´ ar´ asoknak: k´et eg´esz sz´ am legnagyobb k¨ oz¨ os oszt´ oj´ at hat´ arozza meg. Az a ´es b eg´esz sz´ amok legnagyobb k¨ oz¨ os oszt´ oja, az a legnagyobb sz´ am amely osztja az a-t ´es b-t is. Jel¨ ol´ese: lnko(a, b), (a, b), vagy gcd(a, b). Az a ´es b eg´esz sz´ amok legnagyobb k¨ oz¨ os oszt´ oja az a d legkisebb eg´esz sz´ am, amely egyenl˝ o az a ´es b line´ aris kombin´ aci´ oj´ aval: d = x · a + y · b, ahol x, y eg´esz sz´ amok. Az a ´es b eg´esz sz´ amok relat´ıv pr´ımek, ha lnko(a, b) = 1. P´eld´ aul: lnko(101, 64) = 1 ⇒ 64 ´es 101 relat´ıv pr´ımek. Fel´ırhat´ o: 101 · (−19) + 64 · 30 = 1. P´eld´ aul: lnko(64, 52) = 4 ⇒ 64 ´es 52 nem relat´ıv pr´ımek. Fel´ırhat´ o: 64 · (−4) + 52 · 5 = 4.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az euklid´eszi algoritmus ´es v´altozatai Euklid´esz algoritmusa: legyenek r0 = a ´es r1 = b eg´esz sz´ amok, u ´gy hogy a ≥ b > 0. Ha az oszt´ asi algoritmust egym´ as ut´ an t¨ obbsz¨ or alkalmazzuk, akkor a k¨ ovetkez˝ o sz´ amsorozatot kapjuk: r0 , r1 , . . . , rn , rn+1 , ahol rj = rj+1 · qj+1 + rj+2 , 0 < rj+2 < rj+1 , j ∈ {0, 1, . . . , n − 2} ´es rn+1 = 0. Ekkor lnko(a, b) = rn . Euklid´esz kiterjesztett algoritmusa: legyenek a, b pozit´ıv eg´esz sz´ amok, akkor fel´ırhat´ o a k¨ ovetkez˝ oo ¨sszef¨ ugg´es: lnko(a, b) = xn · a + yn · b, n ∈ {0, 1, 2, . . . }, ahol xn ´es yn a k¨ ovetkez˝ o rekurz´ıv sz´ am´ıt´ asi sorozat n-ik tagjai: x0 = 1, y0 = 0 x1 = 0, y1 = 1 xj = xj−2 − qj−1 · xj−1 yj = yj−1 − qj−1 · yj−1 , ahol qj a megfelel˝ o h´ anyados, amelyet az euklid´eszi algoritmus sor´ an sz´ amolunk ki. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A kiterjesztett euklid´eszi algoritmus, p´elda
Hat´ arozzuk meg 84 ´es 35 legnagyobb k¨ oz¨ os oszt´ oj´ at, majd azokat az x ´es y eg´esz sz´ amokat, melyekre fenn´ all a k¨ ovetkez˝ oo ¨sszef¨ ugg´es: 84 · x + 35 · y = d, ahol d = lnko(84, 35) . a
b
r
q
84 35 14
35 14 7
14 7 0
2 2 2
x0 1 0 1
x1 0 1 −2
y0 0 1 −2
y1 1 −2 5
Teh´ at a megold´ as: d = 7, x = −2, y = 5, ´es fenn´ all a k¨ ovetkez˝ oo ¨sszef¨ ugg´es: 84 · (−2) + 35 · 5 = 7.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A kiterjesztett euklid´eszi algoritmus, p´elda Hat´ arozzuk meg 45 ´es 31 legnagyobb k¨ oz¨ os oszt´ oj´ at, majd azokat az x ´es y eg´esz sz´ amokat, melyekre fenn´ all a k¨ ovetkez˝ oo ¨sszef¨ ugg´es: 45 · x + 31 · y = d, ahol d = lnko(45, 31) . v a
b
r
q
45 31 14 3 2
31 14 3 2 1
14 3 2 1 0
1 2 4 1 2
x0 1 0 1 −2 9
x1 0 1 −2 9 −11
y0 0 1 −1 3 −13
y1 1 −1 3 −13 16
Teh´ at a megold´ as: d = 1, x = −11, y = −29, ´es fenn´ all a k¨ ovetkez˝ o o ¨sszef¨ ugg´es: 45 · (−11) + 31 · 16 = 1.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A kiterjesztett euklid´eszi algoritmus Az algoritmus bemenete az a ´es b eg´esz sz´ amok, kimenete pedig a d, x, y sz´ amok amelyekre fenn´ all: d = a · x + b · y . extEuclid (a, b): x0, x1, y0, y1 = 1, 0, 0, 1 while True: r = a % b if r == 0: d, x, y = b, x1, y1 return (d, x, y) q = a / b a = b b = r x = x0 - q * x1 y = y0 - q * y1 x0, x1, y0, y1 = x1, x, y1, y
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Modul´aris inverz meghat´aroz´asa Az a · x ≡ 1 (mod m) kongruenci´ anak a megold´ as´ at, ahol lnko(a, m) = 1 az a inverz´enek h´ıvjuk (mod m) szerint ´es a−1 -el, vagy 1a -val jel¨ olj¨ uk. A kongruencia megoldhat´ os´ agi felt´etele az, hogy lnko(a, m) = 1. P´elda: 17 inverze mod 27 szerint 8, mert fenn´ all: 17 · 8 = 1 (mod 27). A modul´ aris inverz meghat´ aroz´ as´ ahoz a kiterjesztett euklideszi algoritmust haszn´ aljuk, mert a kongruencia ´ at´ırhat´ o 1=a·x +m·y alakba. Ebben az esetben az x az a inverze lesz (mod m) szerint. invMod (a, m): (d, x, y ) = extEuclid (a, b) if (d != 1) error "inverse undefined" if (x < 0) return x + m else return x
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
V´eges-testek aritmetik´aja Az AES eset´eben olyan halmazt jelent, amelyben benne vannak a bin´ aris egy¨ utthat´ oj´ u, n − 1 foksz´ amn´ al kisebb polinomok: f (x) = an−1 x n−1 + an−2 x n−2 + · · · + a1 x + a0 . egy GF (2n ) feletti polinom egyedi m´ odon, az egy¨ utthat´ ok seg´ıts´eg´evel le´ırhat´ o, n biten: (an−1 an−2 . . . a0 ). P´elda x 6 + x 3 + x -nek megfelel˝ o bin´ aris alak: 0100 1010. n-ed fok´ u irreducibilis polinom: olyan polinom, amely nem bonthat´ o fel k´et n-n´el kisebb fok´ u polinom szorzat´ ara. A m˝ uveleteket a szab´ alyos polinomok feletti m˝ uveleti szab´ alyok szerint kell v´egezni, ahol az egy¨ utthat´ ok eset´eben (mod 2) kell sz´ amolni. Ha egy m˝ uvelet elv´egz´ese ut´ an nagyobb kitev˝ ot kapunk mint x n−1 , akkor meg kell hat´ arozni az eredm´eny m(x) szerinti oszt´ asi marad´ek´ at, ahol m(x) egy n-ed fok´ u irreducibilis polinom. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
V´eges-testek aritmetik´aja Ha n = 3, akkor o ¨sszesen 23 k¨ ul¨ onb¨ oz˝ o polinom szerkeszthet˝ o: 2 0, 1, x, x + 1, x , x 2 + 1, x 2 + x, x 2 + x + 1. GF (23 )-ban k´et irreducibilis polinom van: x 3 + x 2 + 1, x 3 + x + 1. Az alkalmazott m˝ uveleteket k¨ onny˝ u implement´ alni: Az o ¨sszead´ as megfelel a ⊕ m˝ uveletnek. A szorz´ as visszavezethet˝ o az x ´es hatv´ anyaival val´ o szorz´ asra, ami egy balra shift ´es egy felt´etelhez k¨ ot¨ ott konstanssal val´ o ⊕ m˝ uvelet elv´egz´es´et jelenti. Az alkalmazott technika a k¨ ovetkez˝ on alapszik: x n (mod m(x)) = m(x) − x n . A kivon´ as ekvivalens az o ¨sszead´ assal, mert 1 + 1 = 1 − 1 = 0, 1 − 0 = 1 + 0 = 1, 0 + 1 = 0 − 1 = 1, 0 + 0 = 0 − 0 = 0. Az oszt´ ashoz multiplikat´ıv inverzre van sz¨ uks´eg, amelyet egy adott irreducibilis polinom szerint kell meghat´ arozni, ez kiterjesztett Euklideszi algoritmussal hat´ arozhat´ o meg. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
V´eges-testek aritmetik´aja P´elda, o ¨sszead´ as: (x + 1) + x = 2 · x + 1 = 1, (011) ⊕ (010) = 001 P´elda, szorz´ as, m(x) = x 3 + x 2 + 1 szerint: (x 2 + x) · (x + 1) = x 2 + x + 1, mert (x 2 + x) · (x + 1) = x 3 + x 2 + x 2 + x = x 3 + x, ahol az m(x) = x 3 + x 2 + 1 szerinti oszt´ asi marad´ek x 2 + x + 1. P´elda, szorz´ asra, 8 biten (mod m(x)) szerint: legyen f (x) = a7 · x 7 + a6 · x 6 + a5 · x 5 + a4 · x 4 + a3 · x 3 + a2 · x 2 + a1 · x + a0 . meghat´ arozzuk: x · f (x) = (a7 · x 8 + a6 · x 7 + a5 · x 6 + a4 · x 5 + a3 · x 4 + a2 · x 3 + a1 · x 2 + a0 · x) (mod m(x)). meg´ allap´ıthat´ o: x · f (x) =
(a6 a5 a4 a3 a2 a1 a0 0), (a6 a5 a4 a3 a2 a1 a0 0) ⊕ (m(x) − x 8 ),
´ MARTON Gy¨ ongyv´ er
ha a7 = 0 ha a7 = 1
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
V´eges-testek aritmetik´aja Hat´ arozzuk meg (x 6 + x 3 + x 2 + 1) × (x 7 + x 2 + 1) szorzatot m(x) = x 8 + x 4 + x 3 + x + 1 szerint. Bin´ arisan ez azt jelenti, hogy mennyi: (01001101) × (10000101)? (01001101) × (00000001) = (01001101) (01001101) × (00000010) = (10011010) (01001101) × (00000100) = (00110100) ⊕ (00011011) = (00101111) (01001101) × (00001000) = (01011110) (01001101) × (00010000) = (10111100) (01001101) × (00100000) = (01111000) ⊕ (00011011) = (01100011) (01001101) × (01000000) = (11000110) (01001101) × (10000000) = (10001100) ⊕ (00011011) = (10010111) teh´ at: (01001101) × (10000101) = (01001101) × [(00000001) ⊕ (00000100) ⊕ (10000000)] = (01001101) ⊕ (00101111) ⊕ (10010111) = (11110101) ami megfelel: x 7 + x 6 + x 5 + x 4 + x 2 + 1-nek. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A kiterjesztett euklid´eszi algoritmus Az euklid´eszi algoritmus, a kiterjesztett euklideszi algoritmus alkalmazhat´ o a polinomok k¨ or´eben is a legnagyobb k¨ oz¨ os oszt´ o, illetve a multiplikat´ıv inverz meghat´ aroz´ as´ ara. Azt mondjuk, hogy a d(x) polinom az a(x) ´es b(x) polinomok legnagyobb k¨ oz¨ os oszt´ oja, ha fenn´ all, hogy d(x) a legnagyobb olyan foksz´ am´ u polinom amelyik osztja a(x)-t ´es b(x)-et is. az euklideszi algoritmus szerint fel´ırhat´ o: lnko[a(x), b(x)] = lnko[b(x), a(x) (mod b(x))]. 6
Pl: lnko(x + x 5 + x 4 + x 2 + x + 1, x 5 + x 4 + x 3 + x 2 + x + 1) = x 3 + 1. x 6 + x 3 + x multiplikat´ıv inverze, (mod x 8 + x 4 + x 3 + x + 1) szerint: x 7 + x 5 + x 3 + x + 1, mert (x 6 + x 3 + x) · (x 7 + x 5 + x 3 + x + 1) = 1 (mod x 8 + x 4 + x 3 + x + 1).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A kiterjesztett euklid´eszi algoritmus, p´elda Hat´ arozzuk meg a(x) = x 8 + x 4 + x 3 + x + 1 ´ es b(x) = x 6 + x 3 + x legnagyobb k¨ oz¨ os oszt´ oj´ at, majd azokat az v (x) ´ es u(x) polinomokat, amelyekre fenn´ all a k¨ ovetkez˝ o ¨ osszef¨ ugg´ es: a(x) · v (x) + b(x) · u(x) = 1. a x8 + x4+
b x6+
x3 + x + 1
x3 + x
x6 + x3 + x
x5 + x4+
q x2
x5 + x4+
x +1
x4 + x3+
x4 + x3+
x
x +1
x2 + x + 1
x
3
x1
y0
1
0
0
y1 1
0
1
1
x2
1
x +1
x2
x3+
x2 + x + 1
x5 + x4+ 3
x0
x +1
x +1
4
r
x
x2 + 1
x3 + x2 + 1 2
x +x +
x +
x2 + x + 1
x2 + 1
x +1
x3 + x2 + 1
x2 + 1
x +1
x
x2 + 1
x
x
1
x +1 2
x +x +1
x2+
x3+
x +1
x2 + 1
3
4
3
x4 + x3+ x2 + x 5
x + x4 + 1
x +
x +x +
x2 + 1
x2 + x
x3 + x2 + 1
x4
x5 + x4 + 1
x6 + x3+
x4 + x + 1
x5 + x3+
x6 + x3+
x7 + x5+
x2 + 1
+x 2 + 1
x3 + x + 1
x2 + 1
Teh´ at: (x 8 + x 4 + x 3 + x + 1) · (x 5 + x 3 + x 2 + 1) + (x 6 + x 3 + x) · (x 7 + x 5 + x 3 + x + 1) = 1. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES (Advanced Encryption Standard)
Daemen ´es Rijmen, belga kriptogr´ afusok tervezt´ek 1997-ben, 2001-ben fogadta el a NIST standardk´ent, kulcs-m´erete: 128, 192, 256 bit, blokk-m´erete: 128 bit, hat´ekonys´ aga: 109 Mb/sec, az AES-128 eset´eben: a k´etdimenzi´ os t¨ omb, a state oszlop-sz´ ama = 4, a k¨ orkulcsok ´es k¨ or¨ ok sz´ ama = 10, nem haszn´ alja a Feistel-s´em´ at.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES (Advanced Encryption Standard)
Helyettes´ıt´est ´es permut´ aci´ ot alkalmaz, v´eges testek felett alkalmaz aritmetikai ´es ⊕ m˝ uveletet, motiv´ aci´ o: kriptogr´ afi´ aban eg´esz sz´ amokkal dolgozunk, 0 ´es 2n − 1 k¨ oz¨ otti ´ert´ekekkel, ´es az o ¨sszes n-bit hossz´ us´ ag´ u sz´ amra sz¨ uks´eg van. Olyan halmazt kell v´ alasztani, ahol az o ¨sszead´ as, kivon´ as, szorz´ as, oszt´ as ut´ an is halmazbeli elemet kapunk → v´eges testek, pontosabban GF (2n ) feletti v´eges testek.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES
az AES minden m˝ uveletet 8 biten v´egez, az o ¨sszead´ as, kivon´ as, szorz´ as, oszt´ as a GF (28 ) feletti v´eges testben t¨ ort´enik, o ¨sszesen 30 irreducibilis polinom van, ahol az AES a k¨ ovetkez˝ ovel dolgozik: x8 + x4 + x3 + x + 1 h´ arom algoritmust kell defini´ alni: kulcsgener´ al´ as, titkos´ıt´ as, visszafejt´es.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, Kulcsgener´al´as a kulcsot egy 4 × 4-es, k´etdimenzi´ os t¨ ombbe rendezz¨ uk, oszloponk´ent → RK0 . minden i = 0, . . . 9-re: RKi−1 -t felosztjuk oszloponk´ent : w0 , w1 , w2 , w3 , meghat. nw0 , nw1 , nw2 , nw3 szavakat:
nw0 = temp ⊕ w0 , ahol temp: rw = RotWord(w3 ), , sw = SubWord(rw ), rcw = Rcon(i), temp = sw ⊕ rcw ,
nw1 = nw0 ⊕ w1 , nw2 = nw1 ⊕ w2 , nw3 = nw2 ⊕ w3 , nw0 ||nw1 ||nw2 ||nw3 → 128 bites ´ert´ekb˝ ol ´ all´ o sor, 4 × 4-es k´etdimenzi´ os t¨ ombbe rendezz¨ uk, oszloponk´ent → RKi . ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, Kulcsgener´al´as, p´elda legyen a kulcs: 2b7e1516 28aed2a6 abf 71588 09cf 4f 3c, 2 dimenzi´ os t¨ ombbe rendezve: w0 2b 7e 15 16 rw cf 4f 3c09
sw 8a84eb01
Az RK1 szavai:
rcw 01000000
nw0 a0fafe17
w1 28 ae d2 a6
w2 ab f7 15 88
w3 09 cf 4f 3c
temp 8b84eb01
nw1 88542cb1
nw2 23a33939
nw3 2a6c7605
k´etdimenzi´ os t¨ ombbe rendezve: w0 a0 fa fe 17 ´ MARTON Gy¨ ongyv´ er
w1 88 54 2c b1
w2 23 a3 39 39
w3 2a 6c 76 05
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, RotWord, SubWord, Rcon
RotWord, balra t¨ ort´en˝ o ciklikus eltol´ ast hajt v´egre: RotWord(a0 a1 a2 a3 ) = (a1 a2 a3 a0 ) SubWord, alkalmazza byte-onk´ent az S-boxot. Ha az ´ atalak´ıtand´ o byte p´eld´ aul a 4a, akkor az S-box t´ abl´ azat 4-ik sora ´es a-ik oszlop´ anak keresztez˝ od´es´en´el tal´ alhat´ o byte lesz az u ´j ´ert´ek: d6. Rcon az els˝ o byte-ra az x i−1 (mod x 8 + x 4 + x 3 + x + 1) hatv´ any´ert´eket sz´ amolja ki, a GF (28 ) v´eges testben, a tov´ abbi h´ arom byte ´ert´eke, azaz a 3 legbaloldalibb byte 0x00 lesz. i Rcon(i)
1 0x01
2 0x02
3 0x04
4 0x08
´ MARTON Gy¨ ongyv´ er
5 0x10
6 0x20
7 0x40
8 0x80
9 0x1b
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
10 0x36
AES-128, titkos´ıt´as a bemenetet egy 4 × 4-es, k´etdimenzi´ os t¨ ombbe rendezz¨ uk, oszloponk´ent → S. meghat´ arozzuk SS =AddRoundKey(S, RK0 ) minden i = 1, . . . 9-re: S1 S2 S3 SS
= SubBytes(SS), = ShiftRows(S1), = MixColumns(S2), = AddRoundKey(S3, RKi ),
az 10.k¨ orben: S1 = SubBytes(SS), S2 = ShiftRows(S1), a titkos´ıt´ o f¨ uggv´eny kimenete: AddRoundKey(S2, RK10 ).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, AddRoundKey, SubBytes, ShiftRows
AddRoundKey a bemeneti param´eterekre byte-onk´ent alkalmazza a ⊕ m˝ uveletet. SubBytes a 4 × 4-es t¨ omb byte-jaira alkalmazza az S-boxot, ShiftRows a 4 × 4-es t¨ omb¨ ot byte-jaira alkalmazza a k¨ ovetkez˝ o ciklikus eltol´ asokat: s11 s21 s31 s41
s12 s22 s32 s42
s13 s23 s33 s43
s14 s24 s34 s44
´ MARTON Gy¨ ongyv´ er
>>
s11 s22 s33 s44
s12 s23 s34 s41
s13 s24 s31 s42
s14 s21 s32 s43
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, MixColumns MixColumns a 4 × 4-es t¨ omb byte-jaira alkalmazza a k¨ ovetkez˝ o ´ atalak´ıt´ asokat: s11 s21 s31 s41
s12 s22 s32 s42
s13 s23 s33 s43
s14 s24 s34 s44
>>
ns11 ns21 ns31 ns41
ns12 ns22 ns32 ns42
ns13 ns23 ns33 ns43
ns14 ns24 ns34 ns44
ahol ns1i ns2i ns3i ns4i
= = = =
(0x02 ◦ s1i ) ⊕ (0x03 ◦ s2i ) ⊕ s3i ⊕ s4i s1i ⊕ (0x02 ◦ s2i ) ⊕ (0x03 ◦ s3i ) ⊕ s4i s1i ⊕ s2i ⊕ (0x02 ◦ s3i ) ⊕ (0x03 ◦ s4i ) (0x03 ◦ s1i ) ⊕ s2i ⊕ s3i ⊕ (0x02 ◦ s4i ).
a ◦ m˝ uvelet szorz´ ast jelent (mod x 8 + x 4 + x 3 + x + 1) szerint a GF (28 ) v´eges testben.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, S-box
Az S-box bemenet´enek bitjeit egy polinom egy¨ utthat´ oinak tekintj¨ uk, ´es meghat´ arozzuk a polinom multiplikat´ıv inverz´et (mod x 8 + x 4 + x 3 + x + 1) szerint a GF (28 ) v´eges testben, jel¨ olj¨ uk ezt: b = (b7 b6 b5 b4 b3 b2 b1 b0 )-vel. Ezut´ an egy affin transzform´ aci´ ot alkalmazunk, megkapva az S-box kimeneti bitjeit: nb = (nb7 nb6 nb5 nb4 nb3 nb2 nb1 nb0 ) nbi = bi ⊕ bi+4
(mod 8)
⊕ bi+5
(mod 8)
⊕ bi+6
(mod 8)
⊕ bi+7
(mod 8)
⊕ ci ,
ahol i = 0, . . . , 7 ´es c = (c7 c6 c5 c4 c3 c2 c1 c0 ) = (0110 0011) = 0x63.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda Hat´ arozzuk meg az S-box {4a} = (0100 1010) = x 6 + x 3 + x-ra alkalmazott ´ert´ek´et. {4a} multiplikat´ıv inverze: b = x 7 + x 5 + x 3 + x + 1 = (1010 1011) lesz, mert (x 6 + x 3 + x) · (x 7 + x 5 + x 3 + x + 1) = 1 (mod x 8 + x 4 + x 3 + x + 1), a keresett ´ert´ek nb = (1101 0110) = {d6}, mert: nb0 nb1 nb2 nb3 nb4 nb5 nb6 nb7
= b0 ⊕ b4 ⊕ b5 ⊕ b6 ⊕ b7 ⊕ c0 = b1 ⊕ b5 ⊕ b6 ⊕ b7 ⊕ b0 ⊕ c1 = b2 ⊕ b6 ⊕ b7 ⊕ b0 ⊕ b1 ⊕ c2 = b3 ⊕ b7 ⊕ b0 ⊕ b1 ⊕ b2 ⊕ c3 = b4 ⊕ b0 ⊕ b1 ⊕ b2 ⊕ b3 ⊕ c4 = b5 ⊕ b1 ⊕ b2 ⊕ b3 ⊕ b4 ⊕ c5 = b6 ⊕ b2 ⊕ b3 ⊕ b4 ⊕ b5 ⊕ c6 = b7 ⊕ b3 ⊕ b4 ⊕ b5 ⊕ b6 ⊕ c7
´ MARTON Gy¨ ongyv´ er
=1⊕0⊕1⊕0⊕1⊕1=0 =1⊕1⊕0⊕1⊕1⊕1=1 =0⊕0⊕1⊕1⊕1⊕0=1 =1⊕1⊕1⊕1⊕0⊕0=0 =0⊕1⊕1⊕0⊕1⊕0=1 =1⊕1⊕0⊕1⊕0⊕1=0 =0⊕0⊕1⊕0⊕1⊕1=1 =1⊕1⊕0⊕1⊕0⊕0=1
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, S-box
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
1 7c 82 fd c7 83 d1 ef a3 0c 81 32 c8 78 3e f8 a1
2 77 c9 93 23 2c 00 aa 40 13 4f 3a 37 25 b5 98 89
3 7b 7d 26 c3 1a ed fb 8f ec dc 0a 6d 2e 66 11 0d
4 f2 fa 36 18 1b 20 43 92 5f 22 49 8d 1c 48 69 bf
5 6b 59 3f 96 6e fc 4d 9d 97 2a 06 d5 a6 03 d9 e6
6 6f 47 f7 05 5a b1 33 38 44 90 24 4e b4 f6 8e 42
´ MARTON Gy¨ ongyv´ er
7 c5 f0 cc 9a a0 5b 85 f5 17 88 5c a9 c6 0e 94 68
8 30 ad 34 07 52 6a 45 bc c4 46 c2 6c e8 61 9b 41
9 01 d4 a5 12 3b cb f9 b6 a7 ee d3 56 dd 35 1e 99
a 67 a2 e5 80 d6 be 02 da 7e b8 ac f4 74 57 87 2d
b 2b af f1 e2 b3 39 7f 21 3d 14 62 ea 1f b9 e9 0f
c fe 9c 71 eb 29 4a 50 10 64 de 91 65 4b 86 ce b0
d d7 a4 d8 27 e3 4c 3c ff 5d 5e 95 7a bd c1 55 54
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
e ab 72 31 b2 2f 58 9f f3 19 0b e4 ae 8b 1d 28 bb
f 76 c0 15 75 84 cf a8 d2 73 db 79 08 8a 9e df 16
AES-128, visszafejt´es
a blokk titkos´ıt´ okra jellemz˝ oen a k¨ or-kulcsokat ford´ıtott sorrendbe alkalmazza, az alkalmazott f¨ uggv´enyeket ford´ıtott sorrendben veszi a titkos´ıt´ asn´ al alkalmazott sorrendhez k´epest, a SubBytes, ShiftRows, MixColumns, S-box f¨ uggv´enyek inverzeit haszn´ alja → a titkos´ıt´ as nem ugyanaz, mint a visszafejt´es, titkos´ıt´ asi sorrend: SubBytes, ShiftRows, MixColumns, AddRoundkey, visszafejt´esi sorrend: InvShiftRows, InvSubBytes, AddRoundkey, InvMixColumns, meg kell k¨ ul¨ on ´ırni a titkos´ıt´ o ´es visszafejt˝ o f¨ uggv´enyt → h´ atr´ any, de lehet ezt optimaliz´ alni.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
AES-128, S-box
Az inverz S-box bemenet´enek bitjeit szint´en egy polinom egy¨ utthat´ oinak tekintj¨ uk, ezen alkalmazzuk a k¨ ovetkez˝ o affin transzform´ aci´ ot, ami ut´ an meghat´ arozzuk a multiplikat´ıv inverzet: nbi = bi+2
(mod 8)
⊕ bi+5
(mod 8)
⊕ bi+7
(mod 8)
⊕ di ,
ahol i = 0, . . . , 7 ´es d = (d7 d6 d5 d4 d3 d2 d1 d0 ) = (0000 0101) = 0x05.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
