4. Előadás Titkosítás, RSA algoritmus

Számítástudomány

Széchenyi István Egyetem

4. Előadás Titkosítás, RSA algoritmus

Dr. Kallós Gábor

2014–2015 11



Tartalom A kriptográfia meghatározása, alaphelyzete Szimmetrikus (titkos) kulcsú titkosítás A Caesar-eljárás

Aszimmetrikus (nyilvános) kulcsú titkosítás Az RSA algoritmus Alapötlet Lépések Alkalmazási példák

Feladatok Irodalom

2



Titkosítás Kriptográfia Több ezer éves tudomány (művészet) Írások és üzenetek olyan (titkos anyagba történő) átalakításával/rejtjelezésével foglalkozik, amely illetéktelen személyek számára megakadályozza a visszafejtést

Titkosító rendszer/módszer (kriptográfiai protokoll) Szövegek rejtjelezésére szolgáló eljárás, úgy, hogy a jogosult fogadó képes legyen hatékonyan és egyértelműen visszafejteni a szöveget

Kriptoanalízis Szintén több ezer éves tudomány (művészet) Rejtjelezett üzenetek (illetéktelen) visszafejtésével/feltörésével foglalkozik

A kriptográfia tipikus alaphelyzete: Kommunikáció két szereplő között (Alice és Bob) nem biztonságos csatornán, amelyet lehallgathat egy külső szereplő (Eve) Ezért az üzenetküldés egy kulcs segítségével kódolva (titkosítva) történik (encoding – E függvény), a titkosított üzenet pedig egy (másik) kulccsal visszafejthető (decoding – D függvény) A titkosítás lehet szimmetrikus (titkos) kulcsú és aszimmetrikus (nyilvános) kulcsú

3



Szimmetrikus (titkos) kulcsú titkosítás Itt a titkosításhoz és a visszafejtéshez használt kulcs megegyezik, vagy az egyik könnyen kiszámolható a másikból A kulcsot feltétlenül titokban kell tartani! Amennyiben valaki hozzáfér a kulcshoz, úgy képes az összes korábbi üzenetet dekódolni, illetve bármelyik fél nevében üzenetet hamisítani

A régi korok titkosító eljárásai mind ilyenek voltak Pl. betűeltolásos titkosítás (a nyílt szöveg minden betűjének ugyanaz a betű felel meg a titkosított szövegben) – egyszerű feltörni Javított változatok: a szövegbeli elhelyezkedéstől függően más és más a kódkarakter – de ezek is feltörhetők voltak →

A módszer napjainkban is jól alkalmazható sok esetben (pl. ott, ahol a küldés és a fogadás egy helyen történik – titkosító fájlrendszer) Hátrányok/nehézségek (két vagy több kommunikáló partner esetén): A kulcsot az adatátvitel előtt valahogy el kell juttatni egyik féltől a másikig Minden kommunikációs partnerhez különböző kulcsot kell használni, hisz közös kulcs esetén el tudnák olvasni egymás üzeneteit

4



Szimmetrikus kulcsú titkosítás Klasszikus titkosító eljárások szemléltetése

Feltörés lehetősége a 2. esetben: periódus meghatározása, majd utána gyakorisági elemzés (sokszor nehéz végrehajtani, időigényes!) Betűk, betűpárok, betűhármasok, stb. előfordulását vizsgálják

Lényegében ezen az elven (csak jóval bonyolultabban, „csavarosabban” – több tárcsa) működött az Enigma titkosító eljárása 5



Aszimmetrikus (nyilvános) kulcsú titkosítás A nagyobb teljesítményű számítógépek korszakában már nem voltak megfelelőek a hagyományos, klasszikus titkosító eljárások Felkészült, jó eszközökkel (szuperszg.) rendelkező feltörő

Forradalmian új ötlet (Diffie és Hellman, 1976): nyilvános kulcsú titkosítás e – nyilvános kulcs, d – titkos/privát kulcs Itt d ≠ e, a titkosítás és a visszafejtés a kulcsokkal gyors, de csak „nagyon nehezen végezhető el” az a feladat, hogy d-t e-ből kiszámítsuk (feltörés) A visszafejtő függvény/eljárás a titkosító inverze

Mit jelent az, hogy „nagyon nehezen végezhető el”? Néhány válaszlehetőség: A kriptorendszer kialakítója nem ismer polinomiális megoldó algoritmust Senki sem ismer polinomiális megoldó algoritmust Aki feltöri a kriptorendszert, „valószínűleg” megoldott már jól ismert „nehéz” problémát Aki feltöri a kriptorendszert, biztosan megoldott már jól ismert „nehéz” problémát Aki feltöri a kriptorendszert, biztosan megoldott már egy NP-teljes problémát Bizonyítottan nem létezik (valószínűségi) polinomiális megoldó algoritmus

Jelen pillanatban senki sem ismer olyan kriptorendszert, amely kielégíti az utolsó három feltétel valamelyikét is, de a „nagyon nehezen végezhető el” az ilyen esetekben matematikailag jól leírható 6



Aszimmetrikus (nyilvános) kulcsú titkosítás

Lépések: Egy nyilvánosan elérhető, megbízható forrásból (pl. magától a címzettől, vagy kulcsszerverről) megszerezzük a címzett nyilvános kulcsát Az üzenetet kódoljuk ezzel a kulccsal, majd elküldjük A kódolt üzenet csakis a címzett privát kulcsával nyitható (!)

A megkapott üzenetet a címzett saját privát kulcsával visszafejti, a végeredmény az eredeti, titkosítatlan szöveg lesz

A legtöbb ma használt kommunikációs protokoll (pl. SSL, SSH) ilyen típusú megoldást alkalmaz a biztonságos adatcseréhez Ugyanezen a módon digitális aláírás is készíthető és ellenőrizhető

7



Az RSA titkosítás Az RSA az egyik leggyakrabban használt nyilvános kulcsú algoritmus Rövidítés: Ron Rivest, Adi Shamir, Leonard Adleman; ők találták ki, 1977-78-ban (MIT) Itt szerepelt először nyilvános kulcs (!) (jól alkalmazható módon)

Alapötlet Legyenek p és q különböző nagy prímek és n = p⋅q. Tfh. van két egészünk, d (decryption) és e (encryption) úgy, hogy d ⋅ e ≡ 1 (mod φ(n)). Az n és e számok nyilvánosak, p, q és d pedig titkosak. Legyen M a küldendő üzenet (pozitív egész szám, kódolás után). [A módszer akkor biztonságos, ha M < p és q, de a gyakorlatban megfelel, ha M < n és annak esélye, hogy p | M vagy q | M, elhanyagolható.] [Az üzenet könnyen számmá alakítható, pl. A = 10, B = 11, …, Z = 35, space = 99, így HELLO = 1714212124.] A küldő kiszámolja és elküldi az E = Me mod n számot. A fogadó kiszámítja az Ed mod n számot. Euler-tétele (bφ(n) ≡ 1 (mod n)) miatt Ed ≡ (Me)d ≡ Me ⋅ d ≡ M„φ(n) többszöröse” + 1 ≡ 1 ⋅ M ≡ M (mod n). Mivel M és Ed mod n egyaránt 0 és n között van, ezért megegyeznek. Kérdés: Hogyan válasszuk meg e-t és d-t? 8



Az RSA titkosítás Alapötlet (folyt.) Ha e-t úgy választjuk, hogy lnko(e, φ(n)) = 1, akkor található megfelelő d. Segédállítás 1.: Legyenek a és m relatív prím egészek. Ekkor található olyan mod m egyértelmű b egész, hogy a ⋅ b ≡ 1 (mod m). [Definíció: Ha a ⋅ b ≡ 1 (mod m), akkor azt mondjuk, hogy b az a inverze mod m. Feladat: Írjuk fel Z5-ben az elemek összeadási és szorzási tábláját. Ellenőrizzük a táblázat segítségével az inverzek létezését!] Bizonyítás: A kiterjesztett Euklideszi algoritmussal tudunk találni olyan b és c egészeket, hogy a ⋅ b + m ⋅ c = 1. Ez azt jelenti, hogy a ⋅ b ≡ 1 (mod m). Legyen e tetszőleges másik egész, amelyre a ⋅ e ≡ 1 (mod m). Ekkor e ≡ e ⋅ (a ⋅ b) ≡ (a ⋅ e) ⋅ b ≡ b (mod m). Ahogy láttuk, ha ismerjük n felbontását (n = p⋅q, p és q különböző prímek), akkor könnyen kiszámítható φ(n) = (p – 1)(q – 1). Ennél egyszerűbb módon φ(n) nem állítható elő. Továbbá, ha ismerjük φ(n)-t, akkor n felbontását is, mert p + q előáll: p + q = n – φ(n) + 1 = p⋅q – (p⋅q – p – q + 1) + 1, és így p – q is megkapható: p − q = ( p + q ) 2 − 4n =

p2 + 2 p ⋅ q + q2 − 4 p ⋅ q =

p2 − 2 p ⋅ q + q2

végül pedig: p = ((p + q) + (p – q))/2, q = ((p + q) – (p – q))/2. A d titkos kulcs megtalálásának problémáját visszavezettük n felbontására. 9



Az RSA titkosítás Az algoritmus lépései Kulcsgenerálás Bob választ véletlenszerűen két (nagy) prímszámot, p-t és q-t (itt p ≠ q), és kiszámítja az N = p⋅q számot A következő lépésben választ egy e kitevőt úgy, hogy 1 < e < φ(N) = (p – 1)(q – 1) és lnko(e, φ(N)) = 1 Ezután meghatározza azt az egyértelmű d számot, amelyre 1 < d < φ(N) és e ⋅ d ≡ 1 (mod φ(N)) (d itt az e inverze modulo φ(N))

Az (N, e) pár Bob nyilvános kulcsa, d pedig Bob titkos kulcsa

Rejtjelezés [Legyen m < N az üzenet egyik blokkjának megfelelő szám, amelyet Alice szeretne Bobnak elküldeni] Alice ismeri Bob nyilvános kulcsát, így m-et a következő módon rejtjelezi: E(m) = me mod N

Visszafejtés [Legyen c < N a rejtjelezett üzenet egyik blokkjának a kódja, amit Bob megkapott] Bob vissza tudja fejteni az üzenetet a következő módon: D(c) = cd mod N

D(E(m)) = m, azaz a visszafejtéskor az eredeti üzenetet kapjuk vissza 10



Az RSA titkosítás Egyszerű RSA példa

11



Az RSA titkosítás Az RSA lépéseinek alkalmazásával kapcsolatos fontos kérdések Hogyan válasszuk meg a p és q prímszámokat? Ezeknek nagyoknak kell lenniük, hiszen különben az üzenetet elcsípő Eve az n számot faktorizálni tudná, és így meg tudná határozni a d titkos kulcsot (d az e-ből a kiterjesztett euklideszi algoritmussal meghatározható)

Ezért a gyakorlatban (a mostani nagy gépek teljesítményét és a feltörő algoritmusok tudását figyelembe véve) p-t és q-t legalább 80-100 (decimális) jegyű számnak kell választani

Hol/hogy találunk ilyen nagy prímeket? Javaslat: véletlenül generálunk ilyen sok jegyű számokat, és teszteljük, hogy prímek-e A prímek elég „sűrűn” helyezkednek el ahhoz, hogy az eljárás működhessen (tudjuk: N/ln N darab N-nél kisebb prímszám van) De: a prímtulajdonság biztos/pontos tesztelése nehéz feladat (!) Ugyanakkor ismertek elég gyors valószínűségi prímtesztek, amelyek gyakorlati szempontból teljesen megbízhatóan igazolják, hogy a jelölt prím (pl. Miller-Rabin-féle teszt)

Hogyan tudunk hatékonyan nagy hatványra emelni számokat? Elég modulo N dolgozni, és 2 hatványok szerinti csoportokat képezhetünk, azaz Pl. 69730 = 69716 ·6978 ·6974 · 6972

12



Az RSA titkosítás Az RSA lépéseinek alkalmazásával kapcsolatos fontos kérdések (folyt.) Mennyire biztonságos az RSA kódolás? A biztonság döntő módon azon alapszik, hogy a nagy számok faktorizációja „igen nehéz” feladat Így az algoritmus feltörése általános esetben, megfelelően nagy p és q választásával olyan sok ideig tartana, hogy nem érdemes megpróbálni (!) Ez a tulajdonság általánosan igaz, de egyes speciális esetekben („ügyetlen” prímválasztás) meg lehet találni az osztókat, nagy N (összetett szám) esetében is Egy példa: Pollard-(p – 1) algoritmusa azon alapulva találja meg az n szám p prímosztóját, hogy p – 1 minden prímosztója viszonylag kicsi, pl. kisebb 1 milliónál. Ezért figyelnünk kell arra, hogy (p – 1)-nek és (q – 1)-nek egyaránt legyen nagy p' és q' prímosztója. Más betartandó (lásd Bressoud, Gathen–Gerhard, itt nem részletezzük): φ(φ(p⋅q)) legyen nagy, és osztható legyen nagy prímekkel, azaz: lnko(p – 1, q – 1) legyen kicsi és (p' – 1) ill. (q' – 1) mindegyike legyen osztható nagy prímekkel

További tipikus feltörést segítő hibák az RSA kódolásnál Kis vagy nagyon speciális e szám választása (ekkor az e-edik gyökvonás E(m) = me mod N-re nem túl nehezen elvégezhető) p és q túl közel van egymáshoz (ez segíti a „brute force” feltörést, lásd Fermat alg.) Szöveg karakterenkénti vagy kis blokkonkénti kódolása A karakterenkénti titkosítás itt is minden azonos karakterre ugyanazt a kimenetet adja

13



Az RSA titkosítás RSA példa (prímválasztás, d és e, kódolás) Eml. (feltételek): lnko(p – 1, q – 1) legyen kicsi és (p' – 1) ill. (q' – 1) mindegyike legyen osztható nagy prímekkel (p – 1)-nek és (q – 1)-nek egyaránt legyen nagy p' és q' prímosztója p és q ne legyen túl közel egymáshoz, e ne legyen nagyon kicsi

1. lépés Válasszunk két darab 1 milliónál nagyobb prímet p'' = 4 813 309, q'' = 1 162 957 (p' – 1 és q' – 1 prímosztói)

2. lépés A p'' és q'' páros többszörösei + 1 alakú számokat vizsgáljuk, addig, amíg nem teljesítik a jelölt számok a pszeudoprím tesztet, majd ellenőrizzük, hogy a jelöltek valóban prímek (a próbaosztásos algoritmus megfelelő) p' = 22 · 4 813 309 + 1 = 105 892 799, q' = 6 · 1 162 957 + 1 = 6 977 743 (p – 1 és q – 1 prímosztói)

3. lépés Mint az előbb, a p' és q' páros többszörösei + 1 alakú számokat vizsgáljuk … p = 20 · 105 892 799 + 1 = 21178 55981 q = 4 · 6 977 743 + 1 = 27 910 973 n = p ⋅ q = 59 11142 11035 79513 φ(n) = (p – 1) ⋅ (q – 1) = 59 11141 89578 12560

14



Az RSA titkosítás RSA példa (folyt.) Eml. (eddig): p = 20 · 105 892 799 + 1 = 21178 55981 q = 4 · 6 977 743 + 1 = 27 910 973 n = p ⋅ q = 59 11142 11035 79513 φ(n) = (p – 1) ⋅ (q – 1) = 59 11141 89578 12560

4. lépés (e és d) e legyen relatív prím (p – 1)-hez és (q – 1)-hez: e = 123 (vagy e = 12345678) A kiterjesztett euklideszi algoritmussal kell: e ⋅ d ≡ 1 (mod φ(n)) (ha d negatívnak adódna, akkor hozzáadunk φ(n)-et) d = 18 26206 43934 70547 (vagy d = 12 95799 57385 71239)

5. lépés (kulcstárolás) Közzétesszük n-et és e-t, biztonságos helyre elzárjuk d-t Biztonsági okokból célszerű törölni p, q és φ(n) értékét

6. lépés (kódolás) Az üzenetet 16 jegyű blokkokra tördeljük (így minden darab < n) Annak esélye, hogy egy tetsz. 1016-nál kisebb m egész osztható lesz p-vel vagy q-val kb. 1: 3 ⋅ 108 (elhanyagolható) Elvégezzük a kódolást az ismert módon 15



Feladatok Tudjuk, hogy n = 19 74936 15358 94833 és φ(n) = 19 74936 12325 17120, továbbá azt is, hogy n két prím szorzata. Határozzuk meg a két prímet anélkül, hogy faktorizálni kéne n-t! Minden lenti a, m párra keressük meg az a inverzét modulo m, vagy mutassuk meg, hogy ilyen inverz nem létezik (ha lnko(a, m) > 1): a = 25, m = 928 102; a = 315, m = 864 247 a = 1001, m = 2 671 835; a = 2643, m = 23 175 586 A bemutatott RSA példa forgatókönyve szerint kódoltuk a Hamlet egy részét (angolul). Állítsuk elő az eredeti szöveget, ha a kód: 39 25736 57380 83976 8 66571 70599 56870 14569 39934 49451 14 57541 36754 04137 Találjuk meg a d rejtett kulcsot, ha n = 233 570 063, e = 125. Az Euler-féle φ függvény tulajdonságai alapján határozzuk meg φ(n)-t n következő értékeire: 51 005, 107 653, 1 294 704, 1 494 108, 614 739 125. *Konstruáljunk RSA alapszámokat úgy, hogy (p' – 1) ill. (q' – 1) mindegyike tartalmaz 1 milliónál nagyobb prímfaktort, és p, q 12-13 jegyű számok. Közöljük a szomszéddal (többiekkel) n és e értékét, d-t tartsuk titokban. Próbáljuk a többiek kódját feltörni (saját felbontó algoritmussal)! 16



Ajánlott irodalom David M. Bressoud: Factorization and Primality Testing, Springer, New York, 1989 Joachim Gathen, Jürgen Gerhard: Modern Computer Algebra (3rd ed.), Cambridge Univ. Press, 2013 Donald E. Knuth: A számítógép-programozás művészete 2. (2. kiadás), Műszaki Könyvkiadó, Budapest, 1994 Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003 Iványi Antal (szerk.): Informatikai algoritmusok 1., ELTE Eötvös Kiadó, Budapest, 2004

17

4. Előadás Titkosítás, RSA algoritmus

Recommend Documents