Kriptogr´afia ´es Inform´aci´obiztons´ag 8. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2017
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
A Crypto++ k¨ onyvt´ arcsomag A OpenSSL k¨ onyvt´ arcsomag Az NTL k¨ onyvt´ arcsomag Nagysz´ amok kezel´ese, C# Nagysz´ amok kezel´ese, Java Az RSA titkos´ıt´ o rendszer: specifik´ aci´ o, p´elda Val´ osz´ın˝ us´egi pr´ımtesztek A k´ınai marad´ekt´etel Faktoriz´ aci´ ohoz kapcsol´ od´ o probl´em´ ak
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol lesz sz´o?
a Rabin titkos´ıt´ o a diszkr´et logaritmus probl´ema, primit´ıv gy¨ ok (gener´ ator elem) meghat´ aroz´ asa. diszkr´et logaritmus probl´em´ an alapul´ o rendszerek: Diffie-Hellman kulcscsere
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Rabin titkos´ıt´o rendszer 1979-ben publik´ alta Michael O. Rabin, azt a lehet˝ os´eget vizsg´ alja, amikor az RSA titkos´ıt´ as sor´ an az e = 2 ´ert´eket v´ alasztjuk ha e = 2, akkor nem l´etezik inverz, mert phi mindig p´ aros, ez´ert lnko(e, phi) 6= 1 ⇒ a visszafejt´est m´ as aritmetikai m˝ uveletek hat´ arozz´ ak meg R
Gen, a kulcs-gener´ al´ o algoritmus: (p, q) ← − Gen(1k ), ahol p ≡ q ≡ 3 (mod 4), n = p · q, pk = (n), sk = (p, q), Enc(n) a rejtjelez˝ o algoritmus: c ← m2 (mod n), 1
Dec(p,q) a visszafejt˝ o algoritmus: m ← c 2 (mod n).
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Rabin titkos´ıt´o, biztons´ag
A visszafejt´es nem egy´ertelm˝ u: 4 lehets´eges visszafejtett sz¨ oveg k¨ oz¨ ul kell kiv´ alsztani a megfelel˝ ot, a visszafejt´es l´ep´essorozata, alkalmazzuk a k´ınai marad´ekt´etelt: mp = c (p+1)/4 (mod p), mq = c (q+1)/4 (mod q), kiterjesztett Euklideszi algoritmussal meghat´ arozzuk p −1 , q −1 -t, jel¨ olj¨ uk rendre x, y -al, azaz x · p + y · q = 1, m1 = (x · p · mq + y · q · mp ) (mod n), m2 = (x · p · mq − y · q · mp ) (mod n) m1 , −m1 , m2 , −m2 lesz a 4 megold´ as.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Rabin titkos´ıt´o rendszer, p´elda legyen p = 11, ´es q = 31 ⇒ n = 341, legyen m = 42, a ny´ılt-sz¨ oveg, titkos´ıt´ as: c = 422 = 59 (mod 341), visszafejt´es: 11 = 31 = 3 (mod 4) ⇒ 59(11+1)/4 = 9 (mod 11), 59(31+1)/4 = 20 (mod 31), kiterjesztett Euklideszi algoritmussal: 31−1 = 5, 11−1 = 17, azaz 31 · 5 + 11 · 17 = 341, m1 = (31 · 31−1 · 9 + 11 · 11−1 · 20) = 20 (mod 341), m2 = −(31 · 31−1 · 9 + 11 · 11−1 · 20) = −20 (mod 341), m3 = (31 · 31−1 · 9 − 11 · 11−1 · 20) = 42 (mod 341), m4 = −(31 · 31−1 · 9 − 11 · 11−1 · 20) = −42 (mod 341),
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Rabin titkos´ıt´o, biztons´ag
A visszafejt´es fenti k´eplet´et az´ert lehet alkalmazni, mert p ≡ q ≡ 3 (mod 4), sokkal hat´ekonyabb, mint az RSA, megmutathat´ o, hogy a Rabin rendszer felt¨ or´ese ugyanolyan neh´ezs´eg˝ u, mint a fakoriz´ aci´ os probl´ema, ez nem igaz a ”textbook” RSA-ra, az RSA-n´ al vett felt¨ or´esi strat´egi´ ak egy r´esze itt is alkalmazhat´ o, u ´jabb v´ altozata (2001, Boneh) ellen´ all a CCA t´ amad´ asnak (az egyik leger˝ osebb t´ amad´ asi m´ od), illetve egy´ertelm˝ u a visszafejt´ese hasonl´ oan az RSA-hoz kulcscsere ´es hiteles´ıt´esi protokollokban haszn´ alj´ ak.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A diszkr´et logaritmus (DL) probl´ema
Sz´ amos kriptorendszer biztons´ aga alapszik a DL probl´em´ an. Az eg´esz sz´ amok Z∗p multiplikat´ıv csoportja eset´eben, ahol p pr´ımsz´ am a DL probl´ema a k¨ ovetkez˝ o: az A, g -alap´ u diszkr´et logaritmusa (mod p) szerint azt jelenti, hogy megkeress¨ uk azt az a pozit´ıv eg´esz sz´ amot, melyre fenn´ all: g a ≡ A (mod p), ahol g primit´ıv gy¨ ok (gener´ ator elem), ´es g , A ∈ Z∗p . A g sz´ am primit´ıv gy¨ ok (mod p) szerint, ha g hatv´ anyai 1-t˝ ol, φ(p)-ig, azaz g , g 2 , g 3 , . . . , g φ(p) , k¨ ul¨ onb¨ oz˝ o marad´ekot adnak (mod p) szerint. A primit´ıv gy¨ ok egy saj´ atos eset´et jelenti a multiplikat´ıv csoportok gener´ ator elem´enek.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Adott primit´ıv gy¨ok meghat´aroz´asa
A p > 2 pr´ımsz´ am ´es g ∈ Z∗p eset´eben g akkor ´es csakis akkor primit´ıv gy¨ ok (mod p) szerint, ha g (p−1)/q 6= 1 (mod p), b´ armely q pr´ımsz´ am eset´eben, ahol q|(p − 1). Ha ismert a p − 1 pr´ımt´enyez˝ os felbont´ asa, akkor egyszer˝ u meghat´ arozni a primit´ıv gy¨ ok¨ ot → nem hat´ekony algoritmus. Ha p = 2 · q + 1, ahol p, q p´ aratlan pr´ımsz´ amok, akkor g primit´ıv gy¨ ok (mod p) szerint, ahol g 6= ±1 (mod p), akkor ´es csakis akkor, ha g q = p − 1 (mod p) → hat´ekony algoritmus.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Adott primit´ıv gy¨ok meghat´aroz´asa, p´elda Legyen p = 13, p − 1 = 12 = 22 · 3,
g = 7 primit´ıv gy¨ ok? Igen, mert 74 = 9 6= 1 (mod 13) ´es 76 = 12 6= 1 (mod 13). g = 9 primit´ıv gy¨ ok? Nem, mert 94 = 9 6= 1 (mod 13) ´es 96 = 1 (mod 13). Legyen p = 47, p − 1 = 46 = 2 · 23,
g = 13 primit´ıv gy¨ ok? Igen, mert 1323 = 46 (mod 47). g = 3 primit´ıv gy¨ ok? Nem, mert 323 = 1 (mod 47).
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Diffie-Hellman kulcscsere
1976-ban publik´ alt´ ak a szerz˝ ok, k´et t´ avoli egys´eg (sz´ am´ıt´ og´ep, mobileszk¨ oz, stb.) kulcscsere mechanizmus´ ara, hiteles´ıt´es´ere ad megold´ ast. Felt´etelezve, hogy a kommunik´ aci´ oban r´esztvev˝ o k´et leg´ alis f´el Alice ´es Bob, akkor a protokoll a k¨ ovetkez˝ o: 1. Alice ´es Bob egy k¨ ozponti szervert˝ ol lek´eri a p, k-bites pr´ımsz´ amot, ´es a g primit´ıv gy¨ ok¨ ot (mod p) szerint, 2. Alice a k, p, g ismeret´eben meghat´ arozza az a, A ´ert´ekeket, ahol: a ∈ {2, . . . , p − 2} v´eletlen sz´ am, A = g a (mod p), az a ´ert´ek´et titokban tartja, A-t pedig elk¨ uldi Bobnak.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Diffie-Hellman kulcscsere
3. Bob a k, p, g ismeret´eben meghat´ arozza a b, B ´ert´ekeket, ahol:
b ∈ {2, . . . , p − 2} v´eletlen sz´am, B = g b (mod p), a b ´ert´ek´et titokban tartja, B-t pedig elk¨ uldi Alicenak. 4. Alice a k¨ oz¨ os K kulcsot a k¨ ovekez˝ ok´eppen hat´ arozza meg: K = B a (mod p). 5. Bob a k¨ oz¨ os K kulcsot a k¨ ovekez˝ ok´eppen hat´ arozza meg: K = Ab (mod p). Helyess´eg: K = Ab = B a = g ab (mod p).
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Diffie-Hellman kulcscsere, p´elda
Legyen p = 47, g = 13,
Alice : v´ alasztja a = 12-t → A = g a (mod p) = 9 (mod 47), elk¨ uldi Bobnak az A = 9 ´ert´eket.
Bob: v´ alasztja b = 34-t → B = g b (mod p) = 21 (mod 47), elk¨ uldi Alicenak a B = 21 ´ert´eket.
Alice: K = B a (mod p) = 2112 = 16 (mod 47), Bob: K = Ab (mod p) = 934 = 16 (mod 47). a k¨ oz¨ os kulcs: K = 16.
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Diffie-Hellman kulcscsere, biztons´ag
lass´ u´ att´er´es a (mod p) aritmetik´ ar´ ol az elliptikus g¨ orb´ekre, nem biztons´ agos egy akt´ıv t´ amad´ o eset´eben (man in the meedle): egy C t´ amad´ o kiadja mag´ at A-nak, mint B, illetve kiadja mag´ at B-nek, mint A, ˆ A ir´ any´ aba, a k¨ oz¨ os kulcs K1 = g a·b , aˆ·b B ir´ any´ aba, a k¨ oz¨ os kulcs K2 = g ,
´ MARTON Gy¨ ongyv´ er
2017, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
