Kriptogr´afia ´es Inform´aci´obiztons´ag 2. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2016
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
F´el´evi ´ attekint˝ o K¨ onyv´eszet T¨ ort´enelmi h´ att´er Klasszikus kriptogr´ afiai rendszerek: Eltol´ asos rejtjelez´esek: Caesar-titkos´ıt´ o, Keyword Caesar
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Mir˝ol lesz sz´o?
Klasszikus kriptogr´ afiai rendszerek, matematikai modell Helyettes´ıt´eses rejtjelez´es: affin-titkos´ıt´ o, M´ atrixos rejtjelez´es: Hill m´ odszere. az NTL k¨ onyvt´ arcsomag
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A klasszikus titkos´ıt´as matematikai modellje Legyen M a ny´ılt-sz¨ ovegek egy v´eges halmaza, C a rejtjelezett-sz¨ ovegek egy v´eges halmaza, K a kulcsok egy v´eges halmaza. H´ arom algoritmust ´ertelmez¨ unk: Gen, a kulcs-gener´ al´ o algoritmus, meghat´ arozza a key kulcsot, Enckey a rejtjelez˝ o algoritmus, a key kulcs alapj´ an, meghat´ arozza az m ∈ M ny´ılt-sz¨ oveg rejtjelezett ´ert´ek´et: c ← Enckey (m), Deckey a visszafejt˝ o algoritmus, a key kulcs alapj´ an visszafejti a c rejtjelezett-sz¨ oveget: m ← Deckey (c). A rendszer helyess´ege ´erdek´eben megk¨ ovetelj¨ uk: Deckey (Enckey (m)) = m, minden m ∈ M eset´eben. Sz´ amos klasszikus titkos´ıt´ asi rendszer l´etezik: Caesar, Vigenere, Palyfair, Hill, stb. ´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az Affin rejtjelez´es helyettes´ıt´eses, monoalfabetikus rejtjelez´es, M = C = {0, 1, . . . , 25}∗ = Z26 , K = {(a, b) ∈ Z26 , gcd(a, 26) = 1}, key = (a, b): Enc(m) = (a · m + b) (mod 26), Dec(c) = a−1 · (c − b) (mod 26). Megjegyz´es: 1
a−1 , az a multiplikat´ıv inverze (mod 26) szerint: a · a−1 = 1 (mod 26).
Felt¨ or´esi m´ odszerek: 1 2 3
gyakoris´ ag vizsg´ alat, az o ¨sszes lehets´eges kulcs kipr´ ob´ al´ asa, kulcsok sz´ ama: 312, ismert ny´ılt-sz¨ oveg t´ amad´ as: ha rendelkez¨ unk k´et bet˝ u rejtjelezett ´ert´ek´evel. ´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az Affin rejtjelez´es - p´elda Ha a kulcs (5, 2) ´es a ny´ılt-sz¨ oveg a k¨ ovetkez˝ o: AMATHEMATICIAN,
akkor a titkos´ıtott-sz¨ oveg: CKCTLWKCTQMQCP,
ahol a titkos´ıtott-sz¨ oveg els˝ o 6 karakter´et a k¨ ovetkez˝ ok´eppen hat´ aroztuk meg: A M A T H E
−> −> −> −> −> −>
C : K : C : T : L: W :
(5 · 0 + 2) (5 · 12 + 2) (5 · 0 + 2) (5 · 19 + 2) (5 · 7 + 2) (5 · 4 + 2)
= = = = = =
2 (mod 26) 10 (mod 26) 2 (mod 26) 19 (mod 26) 11 (mod 26) 22 (mod 26)
A visszafejt´ eshez sz¨ uks´ eges kulcs: (21, 2), mert 5 · 21 = 105 = 1 (mod 26), azaz, 5 multiplikat´ıv inverze (mod 26) szerint 21.
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az Affin rejtjelez´es - ismert ny´ılt-sz¨oveg t´amad´as Ha ismertek az m1 , m2 , c1 , c2 , akkor a k¨ ovetkez˝ o kongruencia-rendszer megold´ as´ aval, meg´ allap´ıthat´ o a titkos´ıt´ ashoz haszn´ alt (a, b) kulcs: m1 · a + b m2 · a + b
= =
c1 c2
(m1 − m2 ) · a
=
(c1 − c2 )
a b vagy b
= =
(m1 − m2 )−1 · (c1 − c2 ) (mod 26) (c1 − m1 · a) (mod 26)
=
(c2 − m2 · a)
(mod 26) (mod 26). (mod 26)
(mod 26)
Ha l´etezik multiplikat´ıv inverz, akkor az meghat´ arozhat´ o: a kiterjesztett Euklideszi algoritmussal, az o ¨sszes ´ert´ek kipr´ ob´ al´ as´ aval (26 szorz´ as sz¨ uks´eges).
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Hill m´odszere, p´elda, titkos´ıt´as 1929-ben publik´ alta Lester S. Hill, polialfabetikus rendszer, az els˝ o blokk titkos´ıt´ ok egyike. Legyen d = 2, az egyszerre titkos´ıthat´ o szimb´ olumok sz´ ama, M = C = Z226 , ´es key =
3 −2
3 1
,
ha a ny´ılt sz¨ oveg: AM AT HE MA TI CI AN, akkor a titkos´ıtott sz¨ oveg: KM FT HQ KC DW EE NN, az els˝ o k´et bet˝ u-t¨ omb titkos´ıt´ asa:
3 −2
3 1
A 3 · = M −2
3 1
0 10 K · = = , 12 12 M
3 −2
3 1
A 3 · = T −2
3 1
0 5 F · = = . 19 19 T
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Hill m´odszere, p´elda, visszafejt´es a visszafejt´eshez meg kell hat´ aroznunk a kulcs inverz ´ert´ek´et, azaz a determin´ ans, majd az inverz m´ atrix ´ert´ek´et. key =
3 −2
3 1
eset´ eben (det key ) = 1 · 3 − (−2) · 3 = 9,
gcd(9, 26) = 1 ⇒ (det key )-nek l´ etezik inverze, ahol (det key )−1 = 3, mert 9 · 3 = 1 (mod 26). 1 −3 . az adjung´ alt m´ atrix: (adj key ) = 2 3 az inverz m´ atrix: key −1 = (det key )−1 · (adj key ) = 3 ·
1 2
−3 3
=
3 6
−9 9
.
az els˝ o k´et bet˝ u-t¨ omb visszafejt´ese:
3 6
−9 9
K 3 · = M 6
−9 9
10 0 A · = = , 12 12 M
3 6
−9 9
F 3 · = T 6
−9 9
5 0 A · = = . 19 19 T
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Hill m´odszere, ´altal´anos esetben
M = C = Zd256 , a key egy d × d-es m´ atrix, melynek elemei ∈ Z256 , jel¨ olj¨ uk a m´ atrix i, j elem´et ki,j -vel, legyen m = (m1 , m2 , . . . md ) ∈ M a ny´ılt sz¨ oveg egy d hossz´ us´ ag´ u blokkja, melyet egy l´ep´esben fogunk titkos´ıtani, a titkos´ıt´ as sor´ an meghat´ arozzuk a ny´ılt sz¨ oveg egy line´ aris transzform´ aci´ oj´ at: c = (c1 , c2 , . . . cd )-t,
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Hill m´odszere Enckey (m) : c = key · m (c1 , c2 , . . . cd ) =
Deckey (c) = key key
−1
−1
k1,1 k2,1 .. . kd,1
k1,2 k2,2 .. . kd,2
... ... ...
k1,d k2,d .. . kd,d
·
m1 m2 .. . md
·c
l´etezik, ha (det key ) · (det key )−1 = 1 (mod 256),
key −1 = (det key )−1 · (adj key ) (mod 256), ahol (adj key ) az adjung´ alt m´ atrix. ha d = 2, akkor egyszer˝ uen meghat´ arozhat´ o az inverz m´ atrix key =
k1,1 k2,1
k1,2 k2,2
´es key −1 = (det key )−1 ·
k2,2 −k2,1
−k1,2 k1,1
´ altal´ anos esetben t¨ obb algoritmus is l´etezik C++ alatt lehet haszn´ alni Shoup NTL k¨ onyvt´ arcsomagj´ at ´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az NTL k¨onyvt´arcsomag Victor Shoup: NTL k¨ onyvt´ arcsomag (Windows ´es Linux disztribuci´ ok). A statikus k¨ onyvt´ ar l´etrehoz´ asa (Win): t¨ olts¨ uk le ´es csomagoljuk ki a, pl. a WinNTL mapp´ aba: http://www.shoup.net/ntl/download.html hozzunk l´etre egy u ´j projektet: New → Project → Win32 ConsoleApplication, adjunk egy nevet a projektnek, legyen ez NTLLib, jel¨ olj¨ uk be a Static library opci´ ot. ne legyen bejel¨ olve a Precompiled header opci´ o, a Source Files-hoz az Add Existing Item men¨ upont seg´ıts´eg´evel adjuk hozz´ a a WinNTL\src mapp´ ab´ ol az o ¨sszes ´ allom´ anyt, a Project/NTLLib/Properties men¨ upontn´ al az Additional Include Directories-n´el adjuk meg a header ´ allom´ anyok el´er´esi u ´tvonal´ at: ... \WinNTL\include a Build\Bulid\Solution parancs megad´ as´ aval l´etrej¨ on a NTLLib\Debug mapp´ aban a statikus k¨ onyvt´ ar. ´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az NTL k¨onyvt´arcsomag, haszn´alat
Hozzunk l´etre egy u ´j projektet: New → Project → Win32 Console Application, adjunk egy nevet a projektnek, legyen ez Labor6, jel¨ olj¨ uk be a Empty project opci´ ot. a Labor6 project-hez az Add Existing Item men¨ upont seg´ıts´eg´evel adjuk hozz´ a az NTLLib Debug mapp´ ab´ ol a l´etrehozott statikus k¨ onyvt´ arat, a Project/NTLLib/Properties men¨ upontn´ al az Additional Include Directories-n´el adjuk meg a header ´ allom´ anyok el´er´esi u ´tvonal´ at: ...\WinNTL\include.
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az NTL k¨onyvt´arcsomag, haszn´alat a forr´ ask´ odba: #ifndef _ZZ_ #define _ZZ_ #include
#include #include #endif NTL_CLIENT ZZ d; a nagy sz´ amok kezel´es´ere szolg´ al´ o t´ıpus, Mat A; m´ atrix kezel´es´ere alkalmas t´ıpus, A.SetDims(n, n); az A m´ atrix m´eret´enek a be´ all´ıt´ asa, A.NumRows(); sorm´eret lek´erdez´es, A.NumCols(); oszlopm´eret lek´erdez´es, inv(d, invA, A, 0); meghat´ arozza az A m´ atrix determin´ ans´ at, a d v´ altoz´ oba illetve azt az invA m´ atrixot, amelyre teljes¨ ul: (A * invA) / d = I ´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Hill m´odszere - ismert ny´ılt-sz¨oveg t´amad´as, d = 2 Ha ismertek az m, m, ˆ c, cˆ, t¨ omb-p´ arok ´ert´ekei, ahol az m rejtjelezett ´ert´eke c ´es az m) ˆ rejtjelezett ´ert´eke cˆ), akkor a k¨ ovetkez˝ o rendszer megold´ as´ aval, meg´ allap´ıthat´ o a titkos´ıt´ ashoz haszn´ alt key kulcs,
legyen m =
m1 m2
,c=
c1 c2
,m ˆ =
mˆ1 mˆ2
, cˆ =
cˆ1 cˆ2
,
fel´ırhat´ o: key · key =
m1 m2 c1 c2
mˆ1 mˆ2 cˆ1 cˆ2
=
m1 · m2
c1 c2
cˆ1 cˆ2 mˆ1 mˆ2
−1
hasonl´ o t´ amad´ asi strat´ egia alkalmazhat´ o nagyobb blokk m´ eret eset´ eben.
´ MARTON Gy¨ ongyv´ er
2016, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
