Kriptogr´afia ´es Inform´aci´obiztons´ag 5. 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?
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
Mir˝ol lesz sz´o?
A Crypto++ k¨ onyvt´ arcsomag Az NTL k¨ onyvt´ arcsomag Nagysz´ amok kezel´ese C# Nagysz´ amok kezel´ese Java Nyilv´ anos-kulcs´ u, aszimmetrikus (public-key, asymmetric cryptography) rendszerek: alapfogalmak, k¨ ovetelm´enyek, matematikai modell. Az RSA titkos´ıt´ o rendszer: specifik´ aci´ o, p´elda, helyess´eg, A Fermat-f´ele faktoriz´ aci´ os m´ odszer
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Crypto++ k¨onyvt´arcsomag
Kriptogr´ afiai s´em´ ak, a NIST ´ altal elfogadott standard implement´ aci´ okkal, http://www.cryptopp.com/\#download let¨ olt´es, kicsomagol´ as, projekt l´etrehoz´ as, build-el´es ⇒ statikus, dinamikus k¨ onyvt´ arak l´etrehoz´ asa, a statikus k¨ onyvt´ ar a cryptest solution build-el´esekor j¨ on l´etre, a \cryptopp\Win32\Output\Debug mapp´ aba: ⇒ cryptlib.lib,
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A Crypto++ k¨onyvt´arcsomag
Be´ all´ıt´ asok: Project/Properties/Configuration Properties/C/C++/Code generation/Runtime Library ⇒ Multi-threaded Debug (/MTd)-ra ´ all´ıtani, Project/Properties/Configuration Properties/C/C++/General/ ⇒ \cryptopp, a cryptlib.lib-et hozz´ aadni a projekthez, az alkalmaz´ as elej´ere be´ırni: #define CRYPTOPP DEFAULT NO DLL #include "dll.h"
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Nagy sz´amok kezel´ese, C++ Victor Shoup: NTL k¨ onyvt´ arcsomag, a statikus k¨ onyvt´ ar l´etrehoz´ asa 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
2015, 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
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az NTL k¨onyvt´arcsomag, haszn´alat a forr´ ask´ odba: #ifndef _ZZ_ #define _ZZ_ #include
#endif NTL_CLIENT ZZ a nagy sz´ amok kezel´es´ere szolg´ al´ o t´ıpus, to_ZZ string ´ atalak´ıt´ asa ZZ t´ıpus´ a, InvMod multiplikat´ıv inverz meghat´ aroz´ asa, XGCD kiterjesztett Euklideszi algoritmus, PowerMod modul´ aris hatv´ anyoz´ as, ZZFromBytes, BytesFromZZ, byte szekvenci´ ab´ ol k´esz´ıt ZZ t´ıpus´ u nagysz´ amot, ´es ford´ıtva, log logaritmus meghat´ aroz´ asa. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Nagy sz´amok kezel´ese, Java
import java.math.BigInteger; v´ altoz´ o deklar´ al´ as: BigInteger n = new BigInteger("101020229"); logaritmus sz´ am´ıt´ as: ln modul´ aris hatv´ anyoz´ as: modPow multiplikat´ıv inverz: modInverse ...
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Nagy sz´amok kezel´ese, C#
using System.Numerics; v´ altoz´ o deklar´ al´ as: BigInteger p = 0, q = 0; BigInteger number1 = BigInteger.Parse("7458753872387"); logaritmus sz´ am´ıt´ as: BigInteger.Log(), hatv´ anyoz´ as: BigInteger.Pow(), modul´ aris hatv´ anyoz´ as: BigInteger.ModPow(), ...
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A nyilv´anos-kulcs´u rendszerek, alapfogalmak
A titkos´ıt´ as ´es visszafejt´es nem ugyanazzal a kulccsal t¨ ort´enik: van egy titkos-kulcs ´es van egy nyilv´ anos-kulcs, nem helyettes´ıti a szimmetrikus kriptogr´ afi´ at, a rendszerek biztons´ aga matematikai probl´em´ akon alapszanak; az alapm˝ uveletek nem a helyettes´ıt´es ´es permut´ aci´ o, alkalmas bizalmas inform´ aci´ ocser´ere ´es hiteles´ıt´esre, illetve mindkett˝ ore; kulcscsere ´es digit´ alis al´ a´ır´ as protokollokban haszn´ alj´ ak.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A nyilv´anos-kulcs´u rendszerek, k¨ovetelm´enyek Hat´ekony algoritmussal lehessen meghat´ arozni a rendszerben haszn´ alt kulcsp´ art: a nyilv´ anos ´es titkos-kulcsot, a nyilv´ anos-kulcs ismeret´eben, hat´ekony algoritmussal lehessen meghat´ arozni az u ¨zenet rejtjelezett ´ert´ek´et, a titkos-kulcs ismeret´eben, hat´ekony algoritmussal lehessen visszafejteni a rejtjelezett u ¨zenetet, a nyilv´ anos-kulcs ismeret´eben ne lehessen hat´ekonyan meghat´ arozni a titkos-kulcsot, a nyilv´ anos-kulcs ´es rejtjelezett-sz¨ oveg ismeret´eben ne lehessen hat´ekonyan meghat´ arozni az u ¨zenetet, ne lehessen k¨ ovetkeztetni annak tartalm´ ara. Kev´es olyan rendszert siker¨ ult kidolgozni, amely eleget tesz a fenti k¨ ovetelm´enyeknek (kudarcos pr´ ob´ alkoz´ asok: a h´ atizs´ ak feladaton alapul´ o titkos´ıt´ o rendszer).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A legismertebb publikus-kulcs´u rendszerek
RSA (Rivest-Shamir-Adleman), biztons´ aga azon alapszik, hogy neh´ez meghat´ arozni valamely o ¨sszetett sz´ am pr´ımoszt´ oit, Diffie-Hellman kulcscsere, biztons´ aga a diszkr´et logaritmus probl´ema neh´ezs´eg´en alapszik, ElGamal titkos´ıt´ o, a Diffie-Hellman kulcscser´evel ´ all szoros kapcsolatban, elliptikus g¨ orb´en alapul´ o kriptogr´ afia.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A titkos-kulcs´u rendszerek matematikai modellje
jel¨ ol´es: SKE , ahol a (K , M, C ) halmaz-h´ armas felett ´ertelmez¨ unk 3 algoritmust: Gen, a kulcs-gener´ al´ o algoritmus, polinom idej˝ u, v´eletlenszer˝ u: R key ← − Gen(1k ), ahol key ∈ K , k ∈ Z≥0 a rendszer biztons´ agi param´etere (legt¨ obb esetben a gener´ alt kulcs bit-hossza), Enckey a rejtjelez˝ o algoritmus, polinom idej˝ u, v´eletlenszer˝ u: R
c← − Enckey (m), a Deckey a visszafejt˝ o algoritmus, polinom idej˝ u, determinisztikus: m ← Deckey (c). Helyess´eg: Deckey (Enckey (m)) = m, minden m ∈ M eset´eben.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
A nyilv´anos-kulcs´u rendszerek matematikai modellje
jel¨ ol´es: PKE , ahol a (K , M, C ) halmaz-h´ armas felett ´ertelmez¨ unk 3 algoritmus: Gen, a kulcs-gener´ al´ o algoritmus, polinom idej˝ u, v´eletlenszer˝ u: R (pk, sk) ← − Gen(1k ), ahol (pk, sk) ∈ K × K , k ∈ Z≥0 a rendszer biztons´ agi param´etere, Encpk a rejtjelez˝ o algoritmus, polinom idej˝ u, v´eletlenszer˝ u: R
c← − Encpk (m), a Decsk a visszafejt˝ o algoritmus, polinom idej˝ u, determinisztikus: m ← Decsk (c). Helyess´eg: Decsk (Encpk (m)) = m, minden m ∈ M eset´eben.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer, kulcsgener´al´as
Bemenet: a k biztons´ agi param´eter. Kimenet: a pk = (n, e) nyilv´ anos-kulcs ´es az sk = d titkos-kulcs. rsaKeyGen (k) p = primszam(k); q = primszam(k); n = p * q; phi = (p-1) * (q-1); e = rand(phi); d = inverz(e, pi); return n, e, d;
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer, kulcsgener´al´as a primszam(k) algoritmus gener´ al egy k bit hossz´ us´ ag´ u pr´ımsz´ amot, erre leggyakrabban a Miller-Rabin algoritmust haszn´ alj´ ak, l´ asd k´es˝ obb, a jelenlegi standard a k = 1024 ´ert´eket aj´ anlja, amely kb. 308 decim´ alis sz´ amjegyet jelent, a rand(phi) algoritmus egy v´eletlen sz´ amot gener´ al, ahol phi az Euler f´ele f¨ uggv´eny, a k¨ ovetkez˝ o tulajdons´ aggal 1 < e < phi, gcd(e, phi) = 1. az inverz(e, phi) algoritmus meghat´ arozza d-t a k¨ ovetkez˝ o tulajdons´ aggal: e · d = 1 (mod phi), erre a kiterjesztett Euklideszi algoritmust kell haszn´ alni, nem m˝ uk¨ odik az Affinn´ al ´es Hilln´el haszn´ alt, o ¨sszes lehets´eges ´ert´ek kipr´ ob´ al´ as´ anak, m´ odszere. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda, kulcsgener´al´as
p, q k´et pr´ımsz´ am: Legyen p = 3877, q = 1867. Meghat´ arozzuk: n = 3877 · 1867 = 7 238 359, phi = (p − 1) · (q − 1) = 3876 · 1866 = 7 232 616. Legyen e = 65 537, ahol gcd(65 537, phi) = 1. Meghat´ arozzuk e inverz´et (mod phi) szerint, kapjuk: d = 1 332 809, mert 65 537 · 1 332 809 = 1 (mod 7 232 616). A nyilv´ anos-kulcs : (65 537, 7 238 359). A titkos-kulcs : (1 332 809).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer, titkos´ıt´as
Bemenet: az u ¨zenet, mint egy m eg´esz sz´ am a [0, . . . , n − 1] intervallumb´ ol, az e, n nyilv´ anos-kulcs. Kimenet: a c titkos´ıtott sz´ am rsaencrypt (m, e, n) c = modpow(m, e, n); return c; Az u ¨zenetet(byte-szekvenci´ at, vagy sz¨ oveget) ´ at kell alak´ıtani sz´ amm´ a, l´ asd k´es˝ obb. A modpow(m, e, n) algoritmus meghat´ arozza az me (mod n) ´ert´eket.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer, visszafejt´es
Bemenet: a c titkos´ıtott sz´ am, d titkos-kulcs. Kimenet: az m visszafejtett ´ert´ek. rsadecrypt (c, d, n) m = modpow(c, d, n); return m; Az m ´ert´eket vissza kell alak´ıtani byte szekvenci´ av´ a, sz¨ ovegg´e, l´ asd k´es˝ obb. A modpow(c, d, n) algoritmus meghat´ arozza a c d (mod n) ´ert´eket.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer, helyess´eg
e · d = 1 (mod phi) ⇒ l´etezik x, eg´esz sz´ am, u ´gy hogy e · d = 1 + x · phi. felt´eve hogy: gcd(m, p) = 1 ⇒
m
mp−1 = 1 (mod p) ⇒ = m (mod p) ⇒ me·d = m (mod p).
1+x·(p−1)·(q−1)
hasonl´ oan: me·d = m (mod q) ⇒ me·d = m (mod n).
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda, titkos´ıt´as
Legyen az u ¨zenet MATHEMATICIAN, ´es a kulcsok a kulcsgener´ al´ asn´ al megadott ´ert´ekek. Felt´elezz¨ uk, hogy az alkalmazott ´ ab´ec´e az angol ´ ab´ec´e 26 nagybet˝ uje. A szok´ asos m´ odon hozz´ arendelj¨ uk a karakterekhez a sz´ amk´ odokat: 12 0 19 7 4 12 0 19 8 2 8 0 13, a karaktersorozatot 26-os sz´ amrendszerbeli sz´ amnak fogjuk tekinteni, a sz´ amokat ´ at´ırjuk 26l sz´ amrendszerbe, ahol l = dlog26 ne ´es n = 7 238 359 ⇒ l = 4, 4-es csoportokat form´ alunk, ´es 264 sz´ amrendszerben a k¨ ovetkez˝ o sz´ amjegyeket kapjuk: 135 888 334 260 5468 13, mert
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda, titkos´ıt´as 135 888 = 334 260 = 5468 = 13 =
7 · 263 + 19 · 262 + 0 · 261 + 12 · 260 19 · 263 + 0 · 262 + 12 · 261 + 4 · 260 0 · 263 + 8 · 262 + 2 · 261 + 8 · 260 0 · 263 + 0 · 262 + 0 · 261 + 13 · 260 .
mindegyik sz´ amjegyet titkos´ıtjuk a nyilv´ anos-kulccsal: (65 537, 7 238 359), az eredm´eny: 1 754 108 6 489 950 362 358 5 018 067, a kapott sz´ amokat 26l+1 = 265 -beli sz´ amoknak tekintj¨ uk ´es ´ at´ırjuk 26-os sz´ amrendszerbe, 5-¨ os csoportokat form´ altunk, az eredm´eny: 18 21 20 21 3 12 13 6 5 14 22 0 16 20 0 15 4 13 25 10, ahol
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda, titkos´ıt´as
1 754 108 = 6 489 950 = 362 358 = 5 018 067 =
3 · 264 + 21 · 263 + 20 · 262 + 21 · 261 + 18 · 260 14 · 264 + 5 · 263 + 6 · 262 + 13 · 261 + 12 · 260 0 · 264 + 20 · 263 + 16 · 262 + 0 · 261 + 22 · 260 10 · 264 + 25 · 263 + 13 · 262 + 4 · 261 + 15 · 260 .
A titkos´ıtott karaktersorozat: SVUVDMNGFOWAQUAPENZK .
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
P´elda, visszafejt´es a titkos´ıtott sz´ amk´ od-sorozat: 18 21 20 21 3 12 13 6 5 14 22 0 16 20 0 15 4 13 25 10. a sz´ amk´ odokat ´ at´ırjuk 265 -es sz´ amrendszerbe. Az eredm´eny: 1 754 108 6 489 950 362 358 5 018 067. Mindegyik sz´ amra k¨ ul¨ on alkalmazzuk a titkos-kulcsot: (1 332 809) c 1 332 809
c (mod 7 238 359)
1 754 108 135 888
6 489 950 334 260
362 358 5468
5 018 067 13
a kapott sz´ amokat ´ at´ırjuk 26-os sz´ amrendszerbe, megkapva a visszafejtett sz´ amk´ od-sorozatot: 12 0 19 7 4 12 0 19 8 2 8 0 13. behelyettes´ıtve: MATHEMATICIAN. ´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Az RSA titkos´ıt´o rendszer
Ha a titkos´ıt´ ast b´ ajtok felett v´egezz¨ uk, akkor a b´ ajtokat 256-os sz´ amrendszerbeli sz´ amoknak tekintj¨ uk egyszerre l b´ ajtot dolgozunk fel, u ´gy hogy a sz´ amokat ´ at´ırjuk 256l sz´ amrendszerbe, ahol l = dlog256 ne, majd a kapott ”nagy” sz´ amot hatv´ anyozzuk, hatv´ anyoz´ as ut´ an, a kapott ´ert´eket 256l+1 -os sz´ amrendszerbeli sz´ amnak tekintj¨ uk, amelyet ´ atalak´ıtunk 256-os sz´ amrendszerbe, kapunk l + 1 b´ ajtot. Visszafejt´eskor ford´ıtva j´ arunk el, l + 1 b´ ajtot dolgozunk fel egyszerre, amib˝ ol l b´ ajtot kapunk vissza.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Faktoriz´aci´ohoz kapcsol´od´o probl´em´ak
oszt´ asi pr´ oba m´ odszere (trial division), Fermat-f´ele faktoriz´ aci´ os m´ odszer, Pollard ρ f´ele faktoriz´ aci´ os m´ odszer ... Az oszt´ asi pr´ oba m´ odszere: vizsg´ aljuk a ”kis” pr´ımekkel val´ o oszthat´ os´ agot, ha k´et azonos nagys´ agrend˝ am szorzata a vizsg´ alt n o ¨sszetett √u pr´ımsz´ sz´ am, akkora k¨ ozel´ıt˝ oleg n oszt´ ast kell kipr´ ob´ alnunk a sikeres faktoriz´ al´ ashoz, akkor haszn´ aljuk, mikor egy o ¨sszetett sz´ am kis nagys´ agrend˝ u pr´ımoszt´ oit kell megkeresni.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Fermat-f´ele faktoriz´aci´os m´odszer Ha a p ´es a q pr´ımek k¨ ozel vannak egym´ ashoz, akkor az n faktoriz´ al´ asa lehets´eges a Fermat-f´ele faktoriz´ aci´ os m´ odszerrel. Felt´etelezz¨ uk, hogy az n = a2 − b 2 , ahol a, b tetsz˝ oleges eg´esz sz´ amok. Ekkor p = a − b, q = a + b. Az algoritmus a k¨ ovetkez˝ o: fermatfaktor(n) a = ceil(sqrt(n)); b1 = a * a - n; while (negyzetsz(b1) == 0) do a = a + 1; b1 = a * a - n; return (a + sqrt(b1)); A negyzetsz f¨ uggv´eny megvizsg´ alja, hogy a param´eterk´ent kapott sz´ am n´egyzetsz´ am-e, 0-t t´er´ıt vissza, ha a param´etere nem n´egyzetsz´ am.
´ MARTON Gy¨ ongyv´ er
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
Fermat-f´ele faktoriz´aci´o, p´elda
Hat´ arozzuk meg n = 6283 k´et pr´ımoszt´ oj´ at, a Fermat-f´ele faktoriz´ aci´ os m´ odszerrel: l√ m n a b = a2 − n n´egyzetsz´ am-e? 80
√
80 81 82
117 278 441
nem nem igen
441 = 21 ⇒ p q
= =
82 − 21 82 + 21
´ MARTON Gy¨ ongyv´ er
= 61, = 103
2015, Kriptogr´ afia ´ es Inform´ aci´ obiztons´ ag
