Aszimmetrikus (nyílt) kulcsú titkosítás Wettl Ferenc 2014-06-25
1
Tartalomjegyzék Jelölések
4
Bevezetés
5
1. Elméleti alapok
6
1.1.
Algoritmikus számelméleti alapok . . . . . . . . . . . . . . . . Euklideszi algoritmus . . . . . . . . . . . . . . . . . . .
Z𝑁 Z*𝑁
és a moduláris hatványozás
8
és a moduláris inverz . . . . . . . . . . . . . . . . .
11
A modern kriptográ a alapja, a bizonyítható biztonság
15 17
. . . . . . . .
18
Az aszimmetrikus rejtjelez® és biztonsága . . . . . . . .
20
Makacs számelméleti problémák . . . . . . . . . . . . . . . . .
23
Faktorizáció . . . . . . . . . . . . . . . . . . . . . . . .
23
. . . . . . . .
24
Négyzetgyökvonás, a Rabin-probléma . . . . . . . . . .
26
Diszkrét logaritmus . . . . . . . . . . . . . . . . . . . .
27
Di eHellman-problémák
. . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . .
31
Egyirányú függvény a faktorizációs problémából . . . .
33
Az RSA-függvény . . . . . . . . . . . . . . . . . . . . .
33
Moduláris négyzetre emelés, a Rabin-függvény . . . . .
33
Diszkrét logaritmus . . . . . . . . . . . . . . . . . . . .
34
Di eHellman függvény
34
Egyirányú kiskapufüggvények
. . . . . . . . . . . . . . . . .
Kriptográ ai hash függvények 1.5.
12 14
Számítási biztonság gyakorlati megközelítés
Moduláris gyökvonás, az RSA-probléma
1.4.
. . . .
Tökéletes biztonság . . . . . . . . . . . . . . . . . . . . Számítási biztonság aszimptotikus megközelítés 1.3.
6
. . . . . . . . . . . . .
Kínai maradéktétel . . . . . . . . . . . . . . . . . . . . 1.2.
6
. . . . . . . . . . . . . .
34
A Di eHellman hash függvény . . . . . . . . . . . . .
36
Támadások az RSA-függvény ellen
. . . . . . . . . . . . . . .
36
kicsi . . . . . . . . . . . . . . . . . . . . . . .
37
közös üzenettel . . . . . . . . . . . . . . . . . . .
37
Hastad támadása . . . . . . . . . . . . . . . . . . . . .
37
Amikor Kis
𝑒
Amikor Amikor
𝑒
𝑑 kicsi . . . . . . . . . . . 𝑥 kicsi gyökös támadás
Közös modulus
. . . . . . . . . . . .
38
. . . . . . . . . . . .
39
. . . . . . . . . . . . . . . . . . . . . .
39
2
Megváltoztathatóság
. . . . . . . . . . . . . . . . . . .
Implementációk elleni támadások 1.6.
. . . . . . . . . . . .
40
Ciklikus csoportok az elliptikus görbéken . . . . . . . . . . . .
41
Elliptikus görbék
. . . . . . . . . . . . . . . . . . . . .
42
A végtelen távoli pont: a n és projektív koordináták .
42
Pontm¶velet az elliptikus görbén
. . . . . . . . . . . .
45
Az elliptikus görbe csoport . . . . . . . . . . . . . . . .
47
Er®s és biztonságos prímek . . . . . . . . . . . . . . . .
49
2. A nyílt kulcsú titkosítás alapfogalmai 2.1.
40
50
El®zmények, kezdetek . . . . . . . . . . . . . . . . . . . . . . . Merkle's puzzle
. . . . . . . . . . . . . . . . . . . . . .
50 50
Di e-Hellman kulcscsere . . . . . . . . . . . . . . . . .
50
2.2.
Aszimmetrikus rejtjelez® egyirányú kisk.-permutációból . . . .
52
2.3.
OAEP Optimal Asymmetric Encryption Padding
2.4.
Hibrid rejtjelez®k
Véletlen orákulum
. . . . . . . . . . . . . . . . . . . .
57
. . . . . . . . . . . . . . . . . . . . . . . . .
60
3. Nyílt kulcsú rejtjelezők 3.1.
3.2.
RSA
62
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
RSA rejtjelez® . . . . . . . . . . . . . . . . . . . . . . .
62
CCA-biztonságú RSA
. . . . . . . . . . . . . . . . . .
62
. . . . . . . . . . . . . . . . . . . . . . . . .
66
ElGamal és ECC
Az ElGamal rejtjelez®
. . . . . . . . . . . . . . . . . .
Csoport generálása az ElGamal számára 3.3.
54
. . . . . .
. . . . . . . .
66 67
Elliptikus görbére épül® rejtjelez® . . . . . . . . . . . .
68
Összehasonlítások . . . . . . . . . . . . . . . . . . . . . . . . .
71
3
Jelölések
𝑎 mod 𝑁 𝑎 ≡ 𝑏 (mod 𝑁 ) Z𝑁
az
Z*𝑁
az
GF(𝑞), F𝑞 F𝑞 [𝑥] F𝑞 [𝑥]𝑁 1𝑛
𝑞 elem¶ véges test F𝑞 feletti polinomok gy¶r¶je 𝑁 -nél kisebb fokú F𝑞 feletti polinomok 𝑛 csupa 1-esb®l álló bitlánc, általában a
az az
𝑎 egész 𝑁 -nel való osztási maradéka 𝑎 és 𝑏 egészek 𝑁 -nel való osztási maradéka azonos 𝑁 -nel való osztás maradékosztályainak additív csoportja
(vagy gy¶r¶je)
𝑁 -hez
relatív prímek maradékosztályainak multiplikatív
csoportja
biztonsági paramé-
ter átadására
|𝑥| ℓ(𝑥) exp(𝑎, 𝑏, 𝑁 ) inv(𝑎, 𝑁 ) log, ln log𝑔 𝑎
az az
𝑥 𝑥
karakterlánc hossza bináris ábrázolásban
szám bináris alakjában a számjegyek száma 𝑏 moduláris hatványozás, értéke 𝑎 mod 𝑁 −1 moduláris inverz, értéke 𝑎 mod 𝑁 2-es és természetes alapú logaritmus diszkrét logaritmus,
𝑎 = 𝑔𝑏
(ciklikus csoport-
kulcsgenerátor,
függvénygenerá-
log𝑔 𝑎 = 𝑏,
ha
ban)
𝒢 𝒢 RSA 𝒢 mod 𝒢 group 𝒢 prime E𝑘 D𝑘
Expxx 𝐴,𝐵 Advxx 𝐴,𝐵
generátorfüggvény
(pl.
tor,. . . ) RSA paramétergenerátor két prím szorzatát generáló algoritmus (𝑁
= 𝑝𝑞 )
ciklikus csoportot generáló algoritmus prímet generáló algoritmus a
𝑘
kulccsal rejtjelez®/kódoló függvény (encoding )
dekódoló függvény (decoding ) kísérlet
(experiment ):
𝐴
támadja
𝐵 -t
az
xx
cél/feltétel/körülmény mellett az
𝐴
támadó el®nye a
ellen az
𝐵
(algoritmus/kriptorendszer/. . . )
xx cél/feltétel/körülmény mellett
𝑥←𝑋 𝑦 ← 𝑓 (𝑥)
egy véletlen
𝑦 = 𝑓 (𝑥) ‖ ⊕
értékadás determinisztikus
𝑥
elem választása az
értékadás, melyben
𝑓
𝑋
halmazból
értéke egy véletlen algoritmus eredmé-
nye
𝑓
függvénnyel
az összef¶zés (konkatenáció) m¶velete bitenkénti XOR m¶velet
4
Bevezetés E jegyzet célja, hogy a nyilt kulcsú titkosítás ma használt, és használatra ajánlható típusait, és az azokkal kapcsolatos biztonsági kérdéseket, mindenekel®tt a bizonyítható biztonság kérdéseit áttekintse, és a felhasználás szempontjai szerint értékelje. A kriptográ a történetében mérföldk®nek számít a nyilvános vagy nyílt kulcsú rejtjelezés 70-es évekbeli föltalálása. Ebben az üzenet titkosítása olyan kulccsal történik, melynek megszerzése nem jelent segítséget a támadónak, olyannyira nem, hogy akár nyilvánosságra is lehet hozni. A rejtjelezett üzenet visszafejtése ugyanis másik kulccsal történik. Els® alkalmazói a titkosszolgálatok voltak, a kémeknek adott kulcs ellenséges területen való használata nem jelentett biztonsági kockázatot, csak a kémközpontban ®rzött titkos kulcsra kellett vigyázni. A nyílt kulcsú rejtjelezés ötletét Kerckhos elvének kiterjesztéseként is felfoghatjuk.
Az ® XIX. században megfogalmazott elve az volt, hogy a
titkosítás módja nem lehet a titok része, nem okozhat veszélyt, ha azt az ellenség megszerzi, így akár teljesen nyilvános is lehet. A 80-as évekt®l kezd®d®en a kriptográ ában több további forradalmi változás történt.
∙
Korábban a kriptográ a f® alkalmazói a katonai biztonsági szervezetek, a szerelmes párok és a magányos naplóírók voltak. Mára a kommunikáció formáinak radikális megsokszorozódása legf®képpen az internet kialakulása után a kriptográ a eszközeinek használata általánossá, és mindannyiunk életét nem elhanyagolható módon befolyásoló tényez®vé vált.
∙
Korábban a kriptográ a alkalmazása a titkos üzenetküldésre szorítkozott, a kriptográ a csak minél feltörhetetlenebbnek hitt rejtjelez®k kitalálásából, és megszerzett titkos üzenetek feltöréséb®l állt.
Mára a
kriptográ a az adatkezelésnek egy lényegesen szélesebb körét öleli fel. Egyrészt nem csak a titkosság meg®rzése, de a küld® azonosíthatósága, az üzenet sértetlensége, hitelessége, az elküldött üzenet utólagos letagadhatatlansága is a kívánalmak közé került. Másrészt számtalan új protokoll jelent meg a kriptográ ában. felsorolunk néhányat:
– titokmegosztás, 5
A teljesség igénye nélkül
– digitális pénz, – digitális hitelesítés, digitális id®pecsét, – biztonságos közös sokrésztvev®s számítások (pl. elektronikus választás),
– digitális jogok kezelése, biztosítása,. . .
∙
Végül egy rendkívül fontos változás: a bizonyítható biztonság fogalmának és matematikai technikáinak megszületésével a kriptográ a elmés m¶vészetb®l, tapasztalatokra épül® mesterségb®l egzakt tudománnyá vált a 2000-es évekre. Ma ezt tekintjük a modern kriptográ ának.
E rövid írásban igyekszünk a modern kriptográ a tudományának alapfogalmait precízen de niálni és a gyakorlati alkalmazások szempontjából is fontos eredményeit áttekinteni.
1. Elméleti alapok
1.1. Algoritmikus számelméleti alapok A nyílt kulcsú titkosítás szinte minden ma használt eljárása az algoritmikus számelmélet nehéz problémáira épül. Ezért els®ként e téma alapismereteit foglaljuk össze.
Euklideszi algoritmus
Két egész szám legnagyobb közös osztóját
gcd(𝑎, 𝑏)
gratest common divisor kifejezésb®l). Ez az a legnagyobb pomely 𝑎 és 𝑏 mindegyikének osztója. Ha a két szám egyike 0,
jelöli (az angol zitív egész,
a másik abszolút értéke lesz a legnagyobb közös osztó.
Kiszámítására lé-
tezik hatékony algoritmus, mely arra az egyszer¶ összefüggésre épül, hogy bármely két
𝑎, 𝑏
egészre
gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 mod 𝑏).
Könnyen igazolható,
hogy a következ® rekurzív algoritmusban a rekurzív függvényhívások száma legföljebb
2 · ℓ(𝑎),
azaz az input hosszának lineáris függvénye. Mivel
voltának ellen®rzése,
𝑎
abszolút értékének és
𝑎 mod 𝑏
𝑏
zérus
értékének kiszámítása,
polinom id®ben elvégezhet®, így az euklideszi algoritmus is polinom id®ben befejez®dik. A kriptográ ai alkalmazásokban az euklideszi algoritmust általában csak pozitív egészekre használjuk. Az algoritmus kib®vített változata nem csak a
6
function gcd(𝑎, 𝑏) input: 𝑎, 𝑏 ∈ Z output: az if
𝑎
és
𝑏
legnagyobb közös osztója
then return |𝑎|
𝑏=0
else return
gcd(𝑏, 𝑎 mod 𝑏)
end end 1. algoritmus: Euklideszi algoritmus
legnagyobb közös osztót, de azt a mindig létez® két
𝑥
és
𝑦
egész számot
is megadja, melyekre
gcd(𝑎, 𝑏) = 𝑥𝑎 + 𝑦𝑏. A 2. algoritmusban az el®z®n annyit változtatunk, hogy csak pozitív egészekre szorítkozunk, így az utolsó lépés melyben a maradék 0 elmarad, viszont a
𝑏
zérus voltának ellen®rzése helyett azt vizsgáljuk, hogy
𝑎
osztható-e
𝑏-vel.
function gcdx(𝑎, 𝑏) input: 𝑎, 𝑏 ∈ Z, 𝑎 output: if
>𝑏>0 ((gcd(𝑎, 𝑏), 𝑥, 𝑦), ahol gcd(𝑎, 𝑏) = 𝑥𝑎 + 𝑦𝑏
𝑏|𝑎
then return (𝑏, 0, 1)
else
𝑞 = ⌊ 𝑎𝑏 ⌋, 𝑟 := 𝑎 mod 𝑏 (𝑑, 𝑥, 𝑦) = gcdx(𝑏, 𝑟) return (𝑑, 𝑦, 𝑥 − 𝑞𝑦)
(ez az
𝑎 = 𝑞𝑏 + 𝑟
maradékos osztás)
end end 2. algoritmus: Kib®vített euklideszi algoritmus
1.1. példa. Kövessük végig a 2. algoritmust
Megoldás.
gcdx(40, 18)
kiszámításán!
A lépéseket egy táblázatba írjuk. Az (1)(3) lépések a rekurzív
függvényhívásokat és a mellékszámítások eredményeit, a sorban következ® (4)(6) lépések a visszaadott számhármasokat mutatják.
7
(1) (2) (3)
gcdx(40, 18), gcdx(18, 4), gcdx(4, 2),
Eszerint tehát
40 = 2 · 18 + 4, 18 = 4 · 4 + 2,
𝑞 = 2, 𝑟 = 4 𝑞 = 4, 𝑟 = 2
(6) (5) (4)
(𝑑, 𝑥, 𝑦) = (2, −4, 9) (𝑑, 𝑥, 𝑦) = (2, 1, −4) (𝑑, 𝑥, 𝑦) = (2, 0, 1)
gcdx(40, 18) = (2, −4, 9), azaz gcd(40, 18) = 2 és 2 = −4 · 40 +
9 · 18. és a moduláris hatványozás
A nyílt kulcsú titkosítás szinte min𝑏 den típusában szerepet kap a moduláris hatványozás. Ezen az 𝑎 mod 𝑁
Z𝑁
hatványmaradék kiszámítását értjük, melyre az
exp(𝑎, 𝑏, 𝑁 )
függvényjelölést
használjuk (az argumentumok száma miatt nem téveszthet® össze a valós 𝑏 exponenciális függvénnyel). Kiszámításának nyilván ügyetlen módja az 𝑎 hatvány kiszámítása után venni az
való osztási maradékot, hisz az al-
𝑏 többszáz jegy¶ is lehet. Hasonlóképp nem elég hatékony az sem, ha az 𝑎-t 𝑏-szer megszorozzuk önmagával, de a számolás egyszer¶sítésére minden szorzás után vesszük a szorzat 𝑁 -nel való osztási maradékát. Ez az algoritmus exponenciális idej¶, hisz 𝑏 − 1 az ℓ(𝑏)-nek expokalmazásokban tipikusan
𝑎
𝑁 -nel
és
nenciális függvénye, és a hatvány kiszámításához ennyi szorzásra van szükség. Polinomiális idej¶vé válik az algoritmus, ha a szorzást nem csak az
𝑎-val való
szorzásra, hanem négyzetre emelésre is használjuk. Ennek módját mutatja a 3. algoritmus. Könnyen igazolható, hogy az itt ismertetett algoritmussal a moduláris hatványozás az inputok hosszának polinomja id®ben lefut. Legyen
𝑛 = ℓ(𝑁 ).
Mivel a függvényhívások száma a kitev® bináris jegyeinek számával egyenl®, egy moduláris összeadás m¶veletigénye 𝑂(𝑛), a szorzás pedig elvégezhet® 𝑂(𝑛2 ) lépésben1 , így a moduláris hatványozás m¶veletigénye 𝑂(𝑛3 ).
1.2. példa. Számítsuk ki
Megoldás.
1341 mod 53
értékét!
El®bb hatványozva, majd a maradékot véve (számítógéppel szá-
molva) ezt kapjuk:
1341 = 4695452425098908797088971409337422035076128813 ≡ 10
(mod 53).
41 bináris alakja 101001, így a rekurzív algoritmust a kiértékelésekt®l kezdve akár kézzel számolva is követhetjük:
1 Kifinomult algoritmusokkal ennél is jobb, aszimptotikusan 𝑂(𝑛 log 𝑛) korlát is elérhető.
8
function exp(𝑎, 𝑏, 𝑁 ) input: 𝑁 ∈ Z+ a modulus, kitev® output: 𝑎𝑏 mod
if
𝑎 ∈ Z𝑁
a hatványozás alapja,
𝑏 ∈ Z+
a
𝑁
then return 𝑎
𝑏=1
else if
2 | 𝑏 then 𝑥 := exp(𝑎, 𝑏/2, 𝑁 ) return (𝑥2 mod 𝑁 )
else
𝑥 := exp(𝑎, (𝑏 − 1)/2, 𝑁 ) return (𝑎 · 𝑥2 mod 𝑁 ) end end end 3. algoritmus: Moduláris hatványozás
bit
számolandó
1 10 101 1010 10100 101001 Minden részletszámítás
7 szorzás és 5 mod 53 = 10.
mellett 41
13
13 = (13)2 = (10)2 13 = (28)2 = (42)2 = (15)2 13 =
3000
eredmény
13 = 169 ≡ 1300 ≡ 784 ≡ 1764 ≡ 2925 ≡
alatt maradt, és a
6
mod 53 13 10 28 42 15 10 bináris jegyb®l álló kitev®
maradék kiszámolására volt szükség.
Az eredmény:
𝑁 > 1, akkor Z𝑁 = {0, 1, . . . , 𝑁 − 1} halmaz elemein a bináris (𝑎, 𝑏) ↦→ 𝑎 + 𝑏 mod 𝑁 m¶velet kommutatív, asszociatív és minden elemnek van inverze a 0-ra, mint zéruselemre nézve (azaz Z𝑁 e m¶velettel kommutatív csoportot alkot). Hasonlóképp tudjuk, hogy Z𝑁 a bináris (𝑎, 𝑏) ↦→ 𝑎𝑏 mod 𝑁 m¶velettel kommutatív, asszociatív, egységelemes algebrai struktúrát ad, de e m¶velet nem invertálható (azaz Z𝑁 e m¶velettel egységelemes kommutatív félcsoport, Z pedig e két m¶velettel kommutaTudjuk, hogy ha
9
tív
gyűrűt2 alkot). Nem fog zavart okozni, ha a
e két m¶veletét is az
Z𝑁
egészeknél használt m¶veleti jelekkel fogjuk jelölni, tehát e jelöléssel például
Z5 -ben Z𝑁
számolva
2 + 3 = 0, 2 · 3 = 1.
egy másik reprezentációjához jutunk, ha elemeivel azt a maradék-
osztályt jelöljük, amelynek az adott szám is tagja. jük, e rövid bekezdés alatt
Z𝑁
Z𝑁 := {[0], [1], . . . , [𝑁 − 1]},
ahol
Hogy a zavart elkerül-
elemeit szögletes zárójelbe tesszük, tehát
[𝑎] = {. . . , 𝑎 − 2𝑁, 𝑎 − 𝑁, 𝑎, 𝑎 + 𝑁, 𝑎 + 2𝑁, . . . }, tehát
[𝑎]
azon egészek halmaza, melyek
𝑁 -nel
osztva
𝑎
maradékot adnak. E
halmazokat hívjuk maradékosztályoknak. A köztük lév® m¶veletek tehát a
[𝑎]+[𝑏] := [𝑎+𝑏 mod 𝑁 ], [𝑎]·[𝑏] := [𝑎𝑏 mod 𝑁 ]. E de níció azért vezet egy értelmes matematikai fogalomhoz, mert ha [𝑎] + [𝑏] = [𝑐] és [𝑎] · [𝑏] = [𝑑], akkor bármely [𝑎]-beli és [𝑏]-beli egész szám összege a [𝑐] halmazba, szorzata a [𝑑] halmazba, azaz maradékosztályba fog esni. A fenti Z5 -beli számolások tehát e jelöléssel felírva a [2] + [3] = [0], [2] · [3] = [1] alakot öltik. Mindenezek alapján mondhatjuk azt is, hogy Z𝑁 elemei az 𝑁 következ®képp de niálhatók:
modulusú maradékosztályok, melyek közt az összeadás és szorzás m¶velete kompatibilis az egészek közti m¶veletekkel. A moduláris hatványozással valójában a
Z𝑁
multiplikatív félcsoportban
végzünk hatványozási m¶veletet. A 3. algoritmus tetsz®leges (multiplikatív) félcsoportban és így csoportban is használható.
Ha egy
𝑆
félcsoportban a
m¶velet polinom id®ben elvégezhet® akkor egy tetsz®leges 𝑔 ∈ 𝑆 elemre és + 𝑏 egy 𝑏 ∈ Z pozitív egészre a 𝑔 hatvány kiszámításához szükséges id® az ℓ(𝑏) és
𝑆
méretének polinomjával becsülhet®.
hogy tovább számol, ha egy részhatvány
Bár a fenti algoritmus gyengéje,
0,
de a kriptográ a gyakorlatában
ez nem fordul el®, mivel ott az alap és a modulus általában relatív prímek, err®l szól a következ® néhány bekezdés. Végül megjegyezzük, hogy additív csoportban is használható az algoritmus, ha egy elem konstansszorosát kell kiszámolni. A
𝑏
𝑏·𝑔
kiszámolásához a
bináris alakjából ismételt összeadásokkal kapjuk meg az eredményt. Ez az
írásmód az elliptikus görbe kriptográ ában szokásos.
2 A matematikai pontosság kedvéért mindig jelezhetnénk, hogy épp mely algebrai struktúrára gondolunk, a szokásos megoldások egyike, hogy az elemek halmaza mellé a műveleti
Z𝑁 egy halmaz, ⟨Z𝑁 , +⟩ az additív csoport, ⟨Z𝑁 , ·⟩ a multip⟨Z𝑁 , +, ·⟩ a gyűrű. E jelölések használatára nem lesz szükségünk, ha
jeleket is fölsoroljuk, ekkor likatív félcsoport és
szükséges, meg fogjuk mondani, melyik struktúrára gondolunk.
10
Z*𝑁
és a moduláris inverz
verzén azt a
0
és
𝑁
közé es®
Az
𝑏
𝑎
1.
𝑁
modulus szerinti moduláris in-
számot értjük, melyre
𝑎𝑏 ≡ 1 Moduláris inverz csak
elem
(mod 𝑁 ).
𝑁 -hez relatív prím 𝑎 számokra létezik, azaz ha gcd(𝑎, 𝑁 ) = 𝑥 és 𝑦 egész,
Ekkor a kib®vített euklideszi algoritmus szerint létezik olyan
hogy
𝑥𝑎 + 𝑦𝑁 = gcd(𝑎, 𝑁 ) = 1, ahonnan
𝑁.
𝑥𝑎 = 1 − 𝑦𝑁 ≡ 1 (mod 𝑁 ),
és így
𝑎
moduláris inverze
𝑏 = 𝑥 mod
A moduláris inverz a kib®vített euklideszi algoritmus leegyszer¶sítésével
közvetlenül is számolható a 4. algoritmussal.
Az algoritmus helyességét az
𝑎𝑥𝑖 ≡ 𝑦𝑖 (mod 𝑁 ) összefüggés 𝑎𝑥2 ≡ 𝑦2 (mod 𝑁 ), ami 𝑦2 folyamatosan lépésen belül vagy az 𝑦2 = 1 vagy az 𝑦2 = 0
bizonyítja, hogy minden lépésben fennáll az (𝑖
= 1, 2),
így az algoritmus végén
csökkenése miatt véges sok értéket eléri.
function inv(𝑎, 𝑁 ) input: 𝑎 ∈ Z, 𝑁 output:
∈ Z+ , 𝑁 > 1 𝑏 mod 𝑁 , ahol 𝑎𝑏 ≡ 1 (mod 𝑁 )
és
0 < 𝑏 < 𝑁,
vagy egy
üzenet, hogy Nincs ilyen szám
𝑥1 , 𝑦1 := 0, 𝑁 𝑥2 , 𝑦2 := 1, 𝑎 mod 𝑁 while 𝑦2 > 1 do 𝑞 := ⌊ 𝑦𝑦12 ⌋ 𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 := 𝑥2 , 𝑦2 , 𝑥1 − 𝑞𝑥2 , 𝑦1 − 𝑞𝑦2 , if 𝑦2 = 0 then return „Nincs ilyen szám” end end return end
𝑥2 mod 𝑁 4. algoritmus: Moduláris inverz kiszámolása
Mint láttuk,
a moduláris szorzással nem alkot csoportot, mert e m¶* velet nem invertálható. Tekintsük tehát a Z𝑁 := {𝑎 ∈ Z𝑁 : gcd(𝑎, 𝑁 ) = 1} halmazt. Ez tehát a 0 és 𝑁 közé es®, 𝑁 -hez relatív prím számokból áll.
Z𝑁
11
Például
Z*5 = {1, 2, 3, 4}, Általában, ha
𝑝
Z*12 = {1, 5, 7, 11},
Z*14 = {1, 3, 5, 9, 11, 13}.
Z*𝑝 = {1, 2, . . . , 𝑝 − 1}. Z*𝑁 elemeinek száma fí függvény. Ha 𝑁 törzstényez®s alakja 𝑁 =
prím, akkor
𝜙(𝑁 ), ahol 𝜙 az Euler-féle 𝑝𝑒11 𝑝𝑒22 . . . 𝑝𝑒𝑚𝑚 , ahol a 𝑝𝑖 számok
különböz® prímek, akkor
)︂ 𝑚 (︂ ∏︁ 1 . 𝜙(𝑁 ) = 𝑁 1− 𝑝 𝑖 𝑖=1 Használni fogjuk ezt az összefüggést abban az esetben, ha
𝑁
két prím szor-
𝜙(𝑁 ) = (𝑝 − 1)(𝑞 − 1). 𝑁 -hez relatív prím egésznek van moduláris inverze, * fontos következménye, hogy Z𝑁 a Z𝑁 -ben már bevezetett szorzásm¶velettel * * csoportot alkot, azaz minden Z𝑁 -beli elemnek van inverze, és Z𝑁 -ban minden 𝑎 · 𝑥 = 𝑏 egyenletnek egyetlen 𝑥 megoldása van, vagyis a szorzásm¶velet
zata, azaz
𝑁 = 𝑝𝑞 ,
ekkor
Annak, hogy minden
3
invertálható. * A Z𝑁 csoport ciklikus, ha osztóval rendelkez®
𝑁
esetén
𝑁 egy páratlan prím hatványa. Több prímZ*𝑁 szerkezetét a kínai maradéktételr®l szóló
következ® részben tárgyaljuk.
* További következmény, hogy a moduláris hatványozás Z𝑁 -ban tovább 𝑏 * egyszer¶södik, nevezetesen ha 𝑔 ∈ Z𝑁 , és 𝑏 egy pozitív egész, akkor 𝑔 = 𝑏 mod 𝜙(𝑁 ) 𝑔 . Itt kihasználtuk az Euler-tételt, mely szerint ha 𝑔 és 𝑁 relatív 𝜙(𝑁 ) prímek, akkor 𝑔 ≡ 1 (mod 𝑁 ). Általánosságban, ha 𝐺 egy csoport, melynek rendje (azaz elemszáma) 𝑛, 𝑔 𝑏 = 𝑔 𝑏 mod 𝑛 , hisz egy 𝑛-edrend¶ csoportban bármely 𝑔 elemre 𝑔 𝑛 = 𝑒,
akkor ahol
𝑒
a csoport egységelemét jelöli.
Kínai maradéktétel
Az RSA kriptorendszerben is alkalmazott kínai ma-
radéktétel legegyszer¶bb alakjában azt állítja, hogy az
𝑥 ≡ 𝑎 (mod 𝑝) 𝑥 ≡ 𝑏 (mod 𝑞) ekvivalenciarendszer minden egész
𝑎
és
𝑏
esetén megoldható ha
prímek, és e megoldás egyértelm¶ modulo
𝑁 = 𝑝𝑞 ,
𝑝
és
(︀ )︀ 𝑥 = 𝑎(𝑞 −1 mod 𝑝)𝑞 + 𝑏(𝑝−1 mod 𝑞)𝑝 mod 𝑁, 3 Az előző lábjegyzetben bevezetett jelölést használva írhatjuk, hogy
12
𝑞
relatív
nevezetesen (1)
⟨Z*𝑁 , ·⟩
csoport.
ahol
𝑞 −1 mod 𝑝 a 𝑞
moduláris inverze a
moduláris inverze modulo
𝑞.
𝑝 modulus szerint, míg 𝑝−1 mod 𝑞
a
𝑝
Annak ellen®rzése, hogy ez valóban megoldás,
behelyettesítéssel ellen®rizhet®, hisz
𝑎(𝑞 −1 𝑎(𝑞 −1 𝑏(𝑝−1 𝑏(𝑝−1 Tekintsük a következ®
𝑓
mod 𝑝)𝑞 ≡ 𝑎 mod 𝑝)𝑞 ≡ 0 mod 𝑞)𝑝 ≡ 0 mod 𝑞)𝑝 ≡ 𝑏
(mod 𝑝) (mod 𝑞) (mod 𝑝) (mod 𝑞).
leképezést:
𝑓 : Z𝑛 → Z𝑝 × Z𝑞 ; 𝑥 ↦→ (𝑥 mod 𝑝, 𝑥 mod 𝑞). Annak ellen®rzése, hogy az (1) egyenletbeli
𝑥
(2)
az egyetlen megoldás mod
𝑁,
𝑓 bijekció, és adott (𝑎, 𝑏) párhoz az (1) képlettel 𝑥, mint leképezés épp az 𝑓 inverze. Ennek igazolása arra épül, hogy |Z𝑁 | = |Z𝑝 × Z𝑞 | = 𝑝𝑞 , így ha volna olyan (𝑎, 𝑏) ∈ Z𝑝 × Z𝑞 pár, mely semmilyen 𝑥 ∈ Z𝑁 -re sem lenne egyenl® 𝑓 (𝑥)-szel, akkor létezne olyan (𝑎, 𝑏) épp azzal ekvivalens, hogy
rendelt
pár is, melyre a kongruenciarendszer nem lenne megoldható. Szemléltessük ezt egy egyszer¶ példán, legyen és a
Z3 × Z5
elemei közt
𝑓
𝑝 = 3, 𝑞 = 5.
Ekkor a
Z15
a következ® bijekciót létesíti:
0 ↔ (0, 0) 6 ↔ (0, 1) 10 ↔ (1, 0) 1 ↔ (1, 1) 5 ↔ (2, 0) 11 ↔ (2, 1) A táblázatba az elemeket a
12 ↔ (0, 2) 3 ↔ (0, 3) 9 ↔ (0, 4) 7 ↔ (1, 2) 13 ↔ (1, 3) 4 ↔ (1, 4) 2 ↔ (2, 2) 8 ↔ (2, 3) 14 ↔ (2, 4)
Z3 × Z5
elempárjai szerint rendeztük, az egy
sorban lév® párok els®, az egy oszlopban lév®k második eleme azonos. A * * * bekeretezett részbe a Z15 , illetve a Z3 × Z5 elemei kerültek. Ez az észrevétel sejteti, hogy több igaz egyszer¶ bijekciónál. Az 𝑓 m¶velettartó is.
Legyen 𝑝 és 𝑞 két relatív prím egész, és legyen 𝑁 = 𝑝𝑞 . Ekkor a (2) képlettel definiált 𝑓 függvény izomorfizmust létesít a Z𝑁 és Z𝑝 × Z𝑞 gyűrűk, valamint a Z*𝑁 és Z*𝑝 × Z*𝑞 csoportok közt, azaz Z𝑁 ∼ = Z𝑝 × Z𝑞 , Z*𝑁 ∼ = Z*𝑝 × Z*𝑞 . 1.3. tétel (Kínai maradéktétel).
Ez azt jelenti, hogy 𝑓 bijekció Z𝑁 és Z𝑝 × Z𝑞 közt, valamint Z*𝑁 és Z*𝑝 × Z*𝑞 közt is, és bármely két 𝑥1 , 𝑥2 ∈ Z𝑁 esetén 𝑓 (𝑥1 + 𝑥2 ) = 𝑓 (𝑥1 ) + 𝑓 (𝑥2 ) és 𝑓 (𝑥1 · 𝑥2 ) = 𝑓 (𝑥1 ) · 𝑓 (𝑥2 ). 13
Z𝑝 ×Z𝑞 elemei közti m¶veletek de níciói természetes módon, az (𝑎, 𝑏)+ (𝑐, 𝑑) = (𝑎 + 𝑐, 𝑏 + 𝑑) és az (𝑎, 𝑏) · (𝑐, 𝑑) = (𝑎 · 𝑐, 𝑏 · 𝑑) képletekkel vannak A
de niálva. Megjegyezzük, hogy az (1)-beli
𝑥 = 𝑓 −1 (𝑎, 𝑏)
képlet a kínai maradékté-
telb®l adódó
𝑓 −1 (𝑎, 𝑏) = 𝑓 −1 (𝑎(1, 0) + 𝑏(0, 1)) = 𝑎𝑓 −1 (1, 0) + 𝑏𝑓 −1 (0, 1) felbontásból érthet®bbé válik, hisz
𝑓 ((𝑞 −1 mod 𝑝)𝑞) = (1, 0),
𝑓 ((𝑝−1 mod 𝑞)𝑝) = (0, 1).
A kínai maradéktétel szemléltetésére és használatának bemutatására szolgál a következ® példa:
1.4. példa. Számítsuk ki az
15
értékeket, mind
Megoldás.
Az
𝑓 -re
Z15 -ben,
(a) 13+7 mod 15, (b) 13·7 mod 15, (c) 137 mod mind Z3 × Z5 -ben számolva!
és inverzére vonatkozó képleteket fogjuk használni, de
𝑓 (13) = (13 mod 3, 13 mod 5) = (1, 3), 𝑓 (7) = (7 mod 3, 7 mod 5) = (1, 2), azaz 13 ↔ (1, 3), 7 ↔ (1, 2). Másrészt 𝑓 −1 (1, 0) = (5−1 mod 3) · 5 = 2 · 5 = 10, 𝑓 −1 (0, 1) = (3−1 mod 5) · 3 = 2 · 3 = 6. (a) 13 + 7 = 20 ≡ 5 (mod 15), másrészt (1, 3) + (1, 2) = (2, 0) ↔ 5, ugyanis 𝑓 −1 (2, 0) = 2 · 𝑓 −1 (1, 0) = 2 · 10 = 20 ≡ 5 (mod 15). (b) 13 · 7 = 91 ≡ 1 (mod 15), másrészt (1, 3) · (1, 2) = (1, 1) ↔ 1, ugyanis 𝑓 −1 (1, 1) = 𝑓 −1 (1, 0) + 𝑓 −1 (0, 1) = 10 + 6 = 16 ≡ 1 (mod 15). (c) 137 = 62748517 ≡ 7 (mod 15), másrészt (1, 3)7 = (17 mod 3, 37 mod 5) = (1, 2) ↔ 7, ugyanis 𝑓 −1 (1, 2) = 𝑓 −1 (1, 0) + 2 · 𝑓 −1 (0, 1) = 10 + 2 · 6 = 22 ≡ 7 (mod 15). a fenti táblázatban ellen®rizhetjük is az eredményeket.
Az utolsó feladat azt is mutatja, hogy a moduláris hatványozás tovább egyszer¶síthet® a kínai maradéktétel alkalmazásával. Ezt az RSA titkosításnál használni fogjuk.
1.2. A modern kriptográfia alapja, a bizonyítható biztonság A bevezet®ben említett bizonyítható biztonság, mint a modern kriptográ a megteremtésének alapfogalma szükségessé teszi, hogy a biztonság lehetséges szintjeit áttekintsük.
A tökéletes biztonság fogalmát el®ször Shannon
14
fogalmazta meg, aki erre vonatkozó tételével megalapozta a kriptográ a tudománnyá válását. A teljesség és az egységes tárgyalás kedvéért felidézzük a szimmetrikus kulcsú rejtjelezés de nícióját:
1.5. definíció. Legyen adva az algoritmusokból álló
(𝒢, E, D)
𝑛
biztonsági paraméter.
A polinom idej¶
hármasról azt mondjuk, hogy szimmetrikus
(privát kulcsú) rejtjelez® vagy titkosító rendszer, ha 𝑛 1. 𝑘 ← 𝒢(1 ), azaz 𝒢 egy véletlen polinom idej¶ algoritmus, mely a biztonsági paraméter függvényében visszaad egy legalább
𝑛
hosszú sztringet,
ez lesz a szimmetrikus kulcs. 2.
3. 4.
𝑐 ← E𝑘 (𝑚), azaz a véletlen polinom idej¶ E algoritmus a 𝑘 kulcshoz és * az 𝑚 ∈ {0, 1} nyílt szöveghez (|𝑘| + |𝑚|-ben polinom id®ben) hozzárendel egy 𝑐 sztringet, az ún. kriptoszöveget. 𝑚 = D𝑘 (𝑐), azaz a polinom idej¶ determinisztikus D algoritmus 𝑘 -hoz és 𝑐-hez (|𝑘| + |𝑐|-ben polinom id®ben) hozzárendel egy 𝑚 sztringet. Minden 𝑛, 𝒢 által generált 𝑘 és tetsz®leges 𝑚 esetén fönnáll az D𝑘 (E𝑘 (𝑚)) = 𝑚
(3)
összefüggés.
* Az 𝑚 gyakran nem a {0, 1} halmaznak, hanem a x hosszú sztringek 𝑀 (𝑛) {0, 1} halmazának eleme, ahol 𝑀 (𝑛) polinomja 𝑛-nek. A lehetséges 𝑚
ℳ halmazát nyílt szöveg térnek, a lehetséges kriptoszövegek 𝒞 halmazát kripto szöveg térnek, míg a lehetséges kulcsok 𝒦 halmazát kulcstérnek nevezzük. Szokásos az a megfogalmazás is, hogy (𝒢, E, D) szimmetrikus kulcsú rejtjelez® a (𝒦, ℳ, 𝒞) hármas fölött. sztringek
Tökéletes biztonság ha
𝑐
Egy rejtjelez®t tökéletesen biztonságosnak nevezünk,
ismeretében semmilyen információt nem tudhatunk meg
𝑚-r®l.
E foga-
lomnak több precíz, egymással ekvivalens matematikai de níciója is létezik. Mi itt most azt említjük, mely a további biztonsági de níciókhoz a legjobban illeszkedik, bár nem ez volna a legegyszer¶bb vagy legkézenfekv®bb.
ExpindCPA 𝒜,Σ (𝑛) nyílt szöveg megkülönböztethetetlenségi kísérlet).
1.6. kísérlet ( Legyen
Σ = (𝒢, E, D)
egy szimmetrikus kulcsú rejtjelez®,
𝒜
algoritmus, itt (1) most a támadó, melyet két különböz® állapotában hívunk meg, ezeket 𝒜 (2) és 𝒜 jelöli.
15
(𝑚0 , 𝑚1 ) ← 𝒜(1) (1𝑛 ), ahol 𝑚0 , 𝑚1 ∈ ℳ, és |𝑚0 | = |𝑚1 |. 𝑛 2. 𝑘 ← 𝒢(1 ), 𝑏 ← {0, 1} egy véletlen bit, 𝑐 ← E𝑘 (𝑚𝑏 ). (2) ′ 3. 𝑏 ← 𝒜 (𝑐) ′ ExpindCPA 𝒜,Σ (𝑛) = 1, ha 𝑏 = 𝑏, egyébként = 0 (az indCPA jelölés indistinguishability under chosen-plaintext attack ) 1.
1.7. definíció (Tökéletes biztonság). A
Σ = (𝒢, E, D)
eredete:
szimmetrikus kulcsú
rejtjelez® tökéletesen biztonságos, ha bármely korlátlan számítási kapacitással rendelkez®
𝒜
Σ rejtjelez®vel szemben 0, ⃒ ⃒ ⃒ ⃒ 1 indCPA ⃒ = 0. Adv𝒜,Σ (𝑛) = ⃒⃒P[ExpindCPA (𝑛) = 1] − 𝒜,Σ 2⃒ algoritmus el®nye a
A de nícióbeli
Adv (az advantage
lenti, amekkora valószín¶séggel
𝑐-t ismerve. szemben 0,
𝒜
szóból) jelölés azt a valószín¶séget je-
𝒜
𝑚0 és 𝑚1 közt csak 𝒜 el®nye a Σ rejtjelez®vel
különbséget tud tenni
A tökéletes biztonság azt jelenti, hogy még akkor is, ha
azaz
korlátlan számítási kapacitással rendelke-
zik. Más szóval 𝒜 el®nye Σ-val szemben 𝜀, ha a 𝑐 kriptoszöveg ismeretében 1 + 𝜀 valószín¶séggel eltalálja, hogy 𝑐 = E𝑘 (𝑚0 ) vagy 𝑐 = E𝑘 (𝑚1 ). Azaz 2 ekkora valószín¶séggel jut a kriptoszöveg alapján a nyílt szövegre vonatkozó információhoz. A tökéletes biztonság elérhet®, és például a one time pad (OTP) nev¶
4
rejtjelez® meg is valósítja . A tökéletes biztonság elérésének azonban súlyos ára van.
Legyen Σ = (𝒢, E, D) egy szimmetrikus kulcsú rejtjelező a (𝒦, ℳ, 𝒞) hármas fölött. 1.8. tétel (Shannon tétele).
1. Ha Σ tökéletesen biztonságos, akkor |ℳ| 6 |𝒦|, és Σ elveszíti tökéletes biztonságát, ha (𝒢 -t megkerülve) egy 𝑘 kulcsot többször használunk. 2. Ha |ℳ| = |𝒞| = |𝒦|, akkor Σ pontosan akkor tökéletesen biztonságos, ha 𝒢 egyenletes eloszlás szerint választ |𝒦|-ból (azaz minden 𝑘 kulcs kiválasztásának 1/|𝒦| a valószínűsége), és minden 𝑐 ∈ 𝒞 és 𝑚 ∈ ℳ elemhez pontosan egy 𝑘 ∈ 𝒦 kulcs létezik, melyre E𝑘 (𝑚) = 𝑐. Azonnal következik Shannon tételéb®l, hogy nyílt kulcsú rejtjelez® nem lehet tökéletesen biztonságos, hisz a rejtjelezést végz® nyílt kulcs többször használatos, egy támadó maga tetsz®leges sokszor meghívhatja.
4 Alkalmazásának híres történelmi esete a kubai atomválság után Moszkva és Washington közt kiépített forró drót, az is az OTP-t használta.
16
Számítási biztonság – gyakorlati megközelítés
A szimmetrikus kul-
csú titkosítás esetén is nagyon ritkán vannak olyan körülmények, amelyek lehet®vé teszik tökéletesen biztonságos protokoll használatát.
Ezért akár a
szimmetrikus, akár az aszimmetrikus kulcsú rejtjelezésben szükség van a biztonságnak egy más, nem tökéletes, de elegend® szintjét elérni, azaz ha matematikailag lehetséges is a rejtjelez® feltörése, ez a gyakorlatban ne sikerülhessen. E biztonság a számítási biztonság (computational
security ),
mely
arra épül, hogy a támadónak ugyan lehet®sége van a rejtjelez® feltörésére, de a valóságban a ma és a várható közeljöv®ben számára rendelkezésre álló er®források igénybevétele mellett belátható id®n belül csak elhanyagolható valószín¶séggel érhessen el sikert. Egy algoritmus elvégzéséhez szükséges id®t legjobb gépi ciklusokban számolni. Szokásos mértékegység a ops (floating pont
operation per second),
vagyis az egy másodperc alatt elvégzett lebeg®pontos m¶veletek száma. A mai szuperkomputerek 10-es nagyságrend¶ peta ops sebesség¶ek, ez azt je16 lenti, hogy egy másodperc alatt nagyságrendileg 10 m¶veletet végeznek el. 80 Például ha egy algoritmus elvégzéséhez 2 op (floating pont operation) m¶80 16 velet elvégzésére van szükség, akkor ehhez egy szuperkomputernek 2 /10 másodpercre, azaz kb.
46
hónapra van szüksége.
Ennél is ki nomultabb
megközelítés, ha azt próbáljuk meg egy algoritmusról megbecsülni, hogy amennyiben adott
𝑡
op elvégzésére van lehet®sége, akkor mekkora a siker
valószín¶sége.
1.9. definíció. Azt mondjuk, hogy egy kriptográ ai rendszer (𝑡, 𝜀)-biztonságú, ha bármely legföljebb
𝑡
opot végrehajtó támadó algoritmus legföljebb
𝜀
va-
lószín¶séggel sikeres.
128 A manapság legelterjedtebb kulcshossz 2 . Ha például egy algoritmus 10 egyetlen kulcs ellen®rzését 2 op alatt elvégzi, akkor annak valószín¶sége, hogy egy
brute force
támadással 100 év alatt megtalálja a kulcsot egy mai
szuperkomputerrel
100 · 365 · 24 · 60 · 60 · 1016 ≈ 9 · 10−17 , 2128 · 210 ami elegend® biztonságnak t¶nik, még akkor is, ha
1000-szeresére
gyorsítjuk
az algoritmust. E gyakorlati megközelítésben nehéz de niálni azt, hogy mit kell elég biztonságosnak, és mit nem biztonságosnak tekintenünk.
Egyrészt a hardve-
rek képességei gyorsan n®nek (Moore 40 éve megfogalmazott sejtése szerint
17
exponenciálisan, leggyakrabban idézett formájában azt állítja, az integrált áramkörökben lév® tranzisztorok száma másfél évente duplázódik).
Más-
részt teljesen más a biztonsági igénye egy szerelmes levélnek és egy kényes 80 hadititoknak. Annyit azért általában mondhatunk, hogy ha 𝑡 · 𝜀 < 1/2 , 40 akkor a technika jelen állása szerint még biztonságos, ha 𝑡 · 𝜀 > 1/2 , akkor már nem biztonságos a rendszer.
Számítási biztonság – aszimptotikus megközelítés
A gyakorlati al-
kalmazásokhoz készült algoritmusok megvalósításakor gyelembe kell venni az el®z® pontban de niált biztonsági fogalmat, a bizonytalanul min®síthet® tartalma miatt viszont más megközelítésre lesz szükségünk. Az els® szempont, hogy a megközelítésnek függvényalapúnak kell lennie, hisz a rendszer használhatósága változik, ha annak biztonsági paramétere (leegyszer¶sítve az input sztring, pl. a kulcs hossza) változtatható. A második szempont, hogy a támadó rendelkezésére álló er®forrás nem lehet korlátlan, s®t kimondható, a támadó algoritmusának hatékonynak kell lennie, így az is a biztonsági paraméter függvényében vizsgálandó. Végül mérnünk kell a támadó sikerességének valószín¶ségét, annyit kívánunk, hogy az elhanyagolható legyen. A függvényalapú megközelítés kényelmesen és jól kezelhet®en fölépíthet® a véletlen polinomidej¶ algoritmus fogalmára. idej¶, ha létezik egy olyan
𝒜(𝑥)
algoritmus
𝑝(|𝑥|)
𝑝
𝒜 algoritmus polinom 𝑥 ∈ {0, 1}* inputra az |𝑥| az 𝑥 hosszát jelöli. Az 𝒜 Egy
polinom, hogy bármely
lépésben véget ér, ahol
algoritmus véletlen polinom idej¶, ha polinom idej¶, és az algoritmus hoz1 1 valószín¶séggel 0, záfér egy véletlen függvényhez, mely meghívásakor 2 2 valószín¶séggel 1 választ ad (a Turing gépek nyelvén az algoritmus hozzáfér egy elegend®en hosszú véletlen
0-1 sorozatot tartalmazó szalaghoz).
Azt tud-
juk, hogy vannak olyan problémák, melyekre van olyan véletlen polinomidej¶ algoritmus, mely gyorsabb bármely ismert determinisztikusnál, az azonban nincs bizonyítva, hogy volna olyan probléma, melynek megoldására van véletlen polinomidej¶ algoritmus, de nincs determinisztikus. Így nem biztos, hogy szükség van-e a véletlen jelenlétére, de hátrányt nem okoz. A polinomidej¶ algoritmusok használatának f® el®nye, hogy ha egy polinom sok függvényhívásból álló
𝒜
algoritmus csupa polinom idej¶ algoritmussal kiszámolható
függvényt hív meg, akkor maga is polinom idej¶.
1.10. definíció. A
𝜈
függvény elhanyagolható, ha minden pozitív f®együtt-
18
hatójú
𝑝
polinomhoz létezik olyan
𝑛𝑝
küszöbindex, hogy ha
0 6 𝜈(𝑛) <
𝑛 > 𝑛𝑝 ,
akkor
1 . 𝑝(𝑛)
𝑛−2 , 𝑛−3 , 𝑛−1000 , 𝑛6 −𝑛1 4 +2 függvények nem elhanyagolhatók, míg a 2−𝑛 , √ 2− 𝑛 , 𝑛− log 𝑛 függvények elhanyagolhatók.
Az
3−𝑛 ,
Könnyen igazolható, hogy elhanyagolható függvények összege, és polinomszorosa is elhanyagolható. Miel®tt az aszimmetrikus kulcsú titkosítás biztonságát vizsgálnánk, egy pillanatra térjünk vissza a szimmetrikus kulcsú rejtjelez® és a tökéletes biztonság de níciójára (1.5. és 1.7. de níciók). A valóságos alkalmazások nagy részében le kell mondanunk a tökéletes biztonságról, mert nehézségekbe ütközik minden üzenetváltás el®tt egy az üzenet hosszánál nem rövidebb kulcsot cserélni, cserébe viszont a valóságos támadónak is le kell mondania a korlátlan számítási kapacitás lehet®ségér®l, mert a valóságban ilyen nincs. Így a tökéletes biztonság de níciójának minimális megváltoztatása elvezet minket egy gyakorlatban használhatóbb új fogalomhoz, a számítási biztonság fogalmához. Ezen belül a biztonságnak több szintje is van. A következ® fogalomra több ekvivalens de níció is létezik, ennek megfelel®en különböz® neveken is szokás említeni.
A nyíltszöveg-megkülönböztethetetlenség alap-
vet® volt a tökéletes biztonság de níciójában is, itt is erre fogjuk építeni a biztonság-fogalmunkat, melyet szokás még szemantikai biztonságnak is nevezni, mert mint látni fogjuk, azt fejezi ki, hogy egyetlen hatékony támadó sem tudhat meg nem elhanyagolható valószín¶séggel semmit a kriptoszöveg alapján a nyílt szövegr®l.
1.11. definíció (Szemantikai biztonság). A
Σ = (𝒢, E, D) szimmetrikus kul-
csú rejtjelez®t szemantikailag biztonságosnak nevezzük, ha bármely véletlen
𝒜 támadó el®nye a Σ rejtjelez®vel szemben elhanyagolható, 𝒜 algoritmushoz van olyan elhanyagolható 𝜈 függvény, hogy ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv𝒜,Σ (𝑛) = ⃒⃒P[Exp𝒜,Σ (𝑛) = 1] − ⃒⃒ 6 𝜈(𝑛). 2
polinom idej¶ azaz bármely
A szemantikai biztonság fenti de níciójára pontosabb kifejezés az üzenetmegkülönböztethetetlenség vagy még pontosabban a nyíltszöveg-megkülönböztethetetlenség lehallgató jelenlétében kifejezések, amit az vidítés is jelöl.
indCPA
rö-
De mivel ekvivalens fogalmakról van szó, egyszer¶bb ezt
19
használni. E lehallgató (eavesdropper ) kifejezés arra a valóságban el®forduló helyzetre utal, amelyben a támadónak van sejtése arról, hogy mi lehet az üzenetben (pl.
𝑚0 =
igen
↔ 𝑚1 =
nem;
𝑚0 =
támadunk
↔
𝑚1 = maradunk,. . . ), és lehallgatja az elküldött kódolt üzenetet, azaz megszerzi a 𝑐 = E𝑘 (𝑚𝑏 ) kriptoszöveget, és abból próbál információhoz jutni a nyílt szöveg kiválasztásához.
Az aszimmetrikus rejtjelező és biztonsága
Az aszimmetrikus kulcsú
rejtjelezés de níciója csak annyiban különbözik a szimmetrikus kulcsúétól, hogy a kulcsgenerálás során nem egy, hanem két kulcsot kell kapnunk, egyet az
E,
egyet a
D
algoritmus részére.
1.12. definíció (Aszimmetrikus kulcsú rejtjelez®). Legyen adva az sági paraméter.
𝑛 biztonA polinom idej¶ algoritmusokból álló Π = (𝒢, E, D) hármas-
ról azt mondjuk, hogy aszimmetrikus (nyílt kulcsú) rejtjelez® vagy titkosító rendszer, ha 1.
(𝑝𝑘, 𝑠𝑘) ← 𝒢(1𝑛 ), azaz 𝒢
egy véletlen polinom idej¶ algoritmus, mely a
biztonsági paraméter függvényében visszaad két (legalább sztringet,
𝑝𝑘
lesz a nyílt,
𝑠𝑘
𝑛 bit hosszú)
a titkos kulcs.
2.
𝑐 ← E𝑝𝑘 (𝑚), azaz a véletlen polinom idej¶ E algoritmus a 𝑝𝑘 kulcshoz és az 𝑚 ∈ ℳ nyílt szöveghez (|𝑝𝑘| +|𝑚|-ben polinom id®ben) hozzárendel egy 𝑐 sztringet.
3.
𝑚 = D𝑠𝑘 (𝑐), azaz a determinisztikus polinom idej¶ D algoritmus 𝑠𝑘 -hoz és 𝑐-hez hozzárendel egy 𝑚 sztringet.
4. Minden
𝑛, 𝒢
által generált
(𝑠𝑘, 𝑝𝑘) és tetsz®leges 𝑚 ∈ ℳ esetén fönnáll
az
P[D𝑠𝑘 (E𝑝𝑘 (𝑚)) = 𝑚] = 1 − 𝜈(𝑛) összefüggés, ahol Az
E
és
D
𝜈
(4)
elhanyagolható.
algoritmusokra föltehet® ami a gyakorlatban is megeshet ,
hogy a dekódolás valamilyen ok miatt meghiúsul, ekkor a
D
megkülönböztetett jelet küld (a kriptográ ai irodalomban a
algoritmus egy
⊥
jelet szokás
erre használni). A (4) biztonságos megfogalmazása az elvárt
D𝑠𝑘 (E𝑝𝑘 (𝑚)) = 𝑚
egyenl®-
ségnek, amely arra is számít, hogy akár a kulcsgenerálás, akár a rejtjelezés véletlen algoritmusában valamilyen elhanyagolható esély¶ hiba történik.
20
A megkülönböztethetetlenségi kísérlet itt is elvégezhet®, de a kulcsgeneráláson kívül ez abban is különbözik a szimmetrikus kulcsú esett®l, hogy itt a támadó folyamatosan hozzáfér a nyílt kulcshoz, így maga nyílt szövegeket rejtjelezhet tetszése szerint.
ExpindCPA 𝒜,Π (𝑛) nyílt szöveg megkülönböztethetetlenségi kísér-
1.13. kísérlet ( let). Legyen
Π = (𝒢, E, D)
egy aszimmetrikus kulcsú rejtjelez®,
goritmus, melyet két különböz® állapotában hívunk meg, ezeket jelöli, és amely közben polinom sokszor meghívhatja
𝒜 olyan al𝒜(1) és 𝒜(2)
E𝑝𝑘 -t.
∙ (𝑝𝑘, 𝑠𝑘) ← 𝒢(1𝑛 ) ∙ (𝑚0 , 𝑚1 ) ← 𝒜(1) (1𝑛 , 𝑝𝑘, E𝑝𝑘 ), ∙ 𝑏 ← {0, 1}
egy véletlen bit,
ahol
𝑚0 , 𝑚1 ∈ ℳ,
és
|𝑚0 | = |𝑚1 |.
𝑐 ← E𝑝𝑘 (𝑚𝑏 ).
∙ 𝑏′ ← 𝒜(2) (𝑐, E𝑝𝑘 ) ′ ExpindCPA 𝒜,Π (𝑛) = 1, ha 𝑏 = 𝑏, egyébként
= 0.
1.14. definíció (Szemantikai biztonság, CPA-biztonság). A
Π = (𝒢, E, D)
aszimmetrikus kulcsú rejtjelez®t szemantikailag biztonságosnak vagy CPAbiztonságosnak nevezzük, ha bármely véletlen polinom idej¶ a
𝒜 támadó el®nye
Π rejtjelez®vel szemben elhanyagolható, azaz bármely 𝒜 algoritmushoz van 𝜈 függvény, hogy ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv𝒜,Π (𝑛) = ⃒⃒P[Exp𝒜,Π (𝑛) = 1] − ⃒⃒ 6 𝜈(𝑛). 2
olyan elhanyagolható
Szokás az
ExpindCPA 𝒜,Π (𝑛) kísérletet kicsit másként de niálni.
argumentumos, második argumentuma a
𝑏
Exp
Ekkor 2′ bit, és kimenete a 𝑏 bit, azaz
𝑏′ = ExpindCPA 𝒜,Π (𝑛, 𝑏). Ekkor, az
𝒜 algoritmus Π-vel szembeni el®nyére a fenti de nícióbelivel lénye-
gében ekvivalens más de níció adható:
indCPA indCPA ⃒ ⃒ AdvindCPA 𝒜,Π (𝑛) = P[Exp𝒜,Π (𝑛, 0) = 1] − P[Exp𝒜,Π (𝑛, 1) = 1]
⃒
⃒
E de níció kicsit életszer¶bbnek t¶nik, itt
𝒜 nem a 𝑏 bitet próbálja eltalálni,
hanem csak az a kérdés, van-e olyan statisztikai próba, mely különbséget tud
21
tenni a
𝑏 = 0 esetére adott 1-es válaszok és a 𝑏 = 1 esetére adott 1-es válaszok
között? Mert ha igen, akkor a rejtjelezés nem biztonságos! Még er®sebb támadásra ad lehet®séget, ha a támadó valamilyen módon hozzá tud jutni maga által el®állított kriptoszövegekek dekódoltatásával kapott nyílt szövegekhez, vagy legalább azokról némi információhoz juthat. A nem elég gondosan megtervezett kriptográ ai protokollokban számtalan olyan lehet®ség adódhat, amikor erre a támadónak lehet®sége nyílik. Például ha a támadó lehallgat egy titkosított üzenetet tartalmazó emailt, majd azt a saját nevén is elküldi a címzettnek, lehet, hogy a címzett válaszában mellékeli a dekódolt üzenetet.
ExpCCA 𝒜,Π (𝑛)
1.15. kísérlet ( Legyen
Π = (𝒢, E, D)
választott kriptoszöveg alapú támadás (CCA)).
egy aszimmetrikus kulcsú rejtjelez®,
𝒜
olyan algo(1) (2) ritmus, melyet két különböz® állapotában hívunk meg, ezeket 𝒜 és 𝒜 jelöli, és amely közben polinom sokszor meghívhatja utóbbit anélkül, hogy magát az
𝑠𝑘 -t
E𝑝𝑘 és a D𝑠𝑘 algoritmust,
is megkapná.
∙ (𝑝𝑘, 𝑠𝑘) ← 𝒢(1𝑛 ) ∙ (𝑚0 , 𝑚1 ) ← 𝒜(1) (1𝑛 , 𝑝𝑘, E𝑝𝑘 , D𝑠𝑘 ), ∙ 𝑏 ← {0, 1}
egy véletlen bit,
∙ 𝑏′ ← 𝒜(2) (𝑐, E𝑝𝑘 , D𝑠𝑘 ),
ahol
𝑚0 , 𝑚1 ∈ ℳ,
és
|𝑚0 | = |𝑚1 |.
𝑐 ← E𝑝𝑘 (𝑚𝑏 ). 𝒜 (2) továbbra is hozzáfér a D𝑠𝑘 alD𝑠𝑘 (𝑐) függvényhívásra nincs lehet®sége.
ahol tehát
goritmushoz, egyedül csak a
′ ExpCCA 𝒜,Π (𝑛) = 1, ha 𝑏 = 𝑏, egyébként
= 0.
1.16. definíció (nyílt szöveg megkülönböztethetetlenség választott kriptoszöveg alapú támadás mellett, CCA-biztonság). A
Π = (𝒢, E, D)
aszimmetri-
kus kulcsú rejtjelez®t CCA-biztonságosnak nevezzük (szokásos elnevezés még: CCA2-biztonság, adaptív CCA-biztonság), ha bármely véletlen polinom idej¶
𝒜
𝒜
algoritmushoz van olyan elhanyagolható
támadó el®nye a
Adv
Π
rejtjelez®vel szemben elhanyagolható, azaz bármely
CCA 𝒜,Π (𝑛)
𝜈
függvény, hogy
⃒ ⃒ = ⃒⃒P[ExpCCA 𝒜,Π (𝑛) = 1] −
⃒ 1 ⃒⃒ 6 𝜈(𝑛). 2⃒
A CCA-biztonságnak van egy olyan gyengébb támadást feltev® de níciója is, ahol a támadónak csak az
𝑚0 és 𝑚1 kiválasztásáig van lehet®sége meghívni 22
a dekódolót, ekkor ezt CCA1-biztonságnak hívják, a fenti de niált fogalmat pedig CCA2-biztonságnak. A fenti kísérletet és de níciót aszimmetrikus rejtjelez®re fogalmaztuk meg, de ezek egyszer¶en módosíthatóak, hogy szimmetrikus rejtjelez®re is érvényesek legyenek, egyszer¶en
(𝑝𝑘, 𝑠𝑘)
pár a közös
𝑘
Π
egy
Σ
szimmetrikus rendszerre cserélend®, és a
kulcsra, minden más marad.
Hogyan lehet aszimmetrikus kulcsú rejtjelez®t konstruálni?
Az összes
fontosabb ilyen konstrukció valamelyik makacs számelméleti problémára, és abból származó ún. egyirányú kiskapu-függvényre, illetve egyirányú kiskapupermutációra épül. Ezért el®ször ezeket vesszük sorra.
1.3. Makacs számelméleti problémák Makacs számelméleti problémáknak nevezzük azokat a kérdéseket, melyek megválaszolására eddig nem találtunk hatékony algoritmust, eddig makacsul ellenálltak minden próbálkozásnak, de ugyanakkor az sincs bizonyítva, hogy ilyen algoritmus nem létezik. Ráadásul nem elég, hogy a probléma bizonyos esetekben legyen nehéz, hanem hogy az esetek egy pontosan és egyszer¶en de niálható tartományán belül elhanyagolható számú esetet leszámítva mindig.
Faktorizáció
A számelmélet leg®sibb problémáinak egyike az egészek fak-
torizációja. Egész számok összeszorzása polinomidej¶ algoritmus, tényez®kre bontására ezidáig hatékony algoritmust nem ismerünk (nem számítva a Shoralgoritmust, mely polinom id®ben fogja megoldani e problémát kvantumkomputeren ha valamikor lesz olyan).
1.17. kísérlet (
ExpFactor 𝒜,𝒢 (𝑛) faktor kísérlet).
𝒢
egy polinomidej¶ algoritmus,
mely a biztonsági paraméter függvényében el®állít két szorzatát. A két szám prím.
𝒜
𝑛
𝑛-bites számot és azok
függvényében elhanyagolható valószín¶séggel nem
egy algoritmus, mely egy számpárt ad vissza:
∙ (𝑝, 𝑞, 𝑁 ) ← 𝒢(1𝑛 ) ∙ (𝑝′ , 𝑞 ′ ) ← 𝒜(𝑁 ) ′ ′ ExpFactor 𝒜,𝒢 (𝑛) = 1, ha 𝑝 𝑞 = 𝑁 , egyébként
23
= 0.
1.18. definíció. Azt mondjuk, hogy a faktorizáció nehéz, ha bármely véletlen polinomidej¶ vény, hogy
𝒜 algoritmushoz létezik olyan elhanyagolható 𝜈(𝑛) függ-
Factor AdvFactor 𝒜,𝒢 (𝑛) = P[Exp𝒜,𝒢 (𝑛) = 1] 6 𝜈(𝑛).
Moduláris gyökvonás, az RSA-probléma
Bár a faktorizáció nehéz prob-
lémának t¶nik, még sincs széles körben elterjedt kriptográ ai alkalmazása, van azonban olyan, amely szoros kapcsolatban áll vele. Ezek legismertebbike az RSA-probléma. Ez bizonyos korlátozó feltevések mellett lényegében az is-
𝑒 kitev®vel végzett moduláris hatványozás inverzének, azaz a moduláris 𝑒-edik gyökvonás elvégzésének nehézségét feltételezi, ha a modulus két prím
mert
szorzata.
𝑓 : Z*𝑁 → Z*𝑁 ; 𝑥 ↦→ 𝑥𝑒 függvény invertálható, ha 𝑁 tetsz®leges 1-nél nagyobb egész, és gcd(𝑒, 𝜙(𝑁 )) = 1. Másként fogal−1 * mod 𝜙(𝑁 ), mazva 𝑓 a Z𝑁 egy permutációja. Megmutatjuk, hogy ha 𝑑 = 𝑒 𝑑 * −1 * akkor 𝑓 inverze az 𝑓 : Z𝑁 → Z𝑁 ; 𝑦 ↦→ 𝑦 függvény. Ennek ellen®rzéséhez csak azt kell látnunk, hogy ha 𝑑 moduláris inverze 𝑒-nek, azaz 𝑒𝑑 ≡ 1 (mod 𝜙(𝑁 )), akkor van olyan 𝑘 > 0 szám, hogy 𝑒𝑑 = 1 + 𝑘𝜙(𝑁 ), és így * tetsz®leges 𝑥 ∈ Z𝑁 számra Könnyen igazolható, hogy az
(𝑥𝑒 )𝑑 = 𝑥𝑒𝑑 ≡ 𝑥1+𝑘𝜙(𝑁 )
(mod 𝑁 )
≡ 𝑥(𝑥𝜙(𝑁 ) )𝑘 ≡ 𝑥1𝑘 = 𝑥. Kérdés, hogy határozható meg
𝑒
(mod 𝑁 )
(mod 𝑁 )
ismeretében
𝑑.
Ha
𝑁 = 𝑝𝑞 ,
ahol
𝑝
és
𝑞
két különböz® prím és mostantól csak erre az esetre szorítkozunk , akkor
𝜙(𝑁 ) = (𝑝 − 1)(𝑞 − 1),
az
𝑒
polinomidej¶ algoritmusunk.
moduláris inverzének kiszámítására pedig van A nehézséget az okozza, hogy
határozni épp oly nehéz, mint faktorizálni
𝑁 -et.
tényez®it, akkor polinom id®ben ki tudjuk számolni a értéket, ha pedig ismerjük
𝑁
és
𝜙(𝑁 )
𝜙(𝑁 )-et
meg-
𝑁 𝜙(𝑁 ) = (𝑝 − 1)(𝑞 − 1)
Ha ugyanis ismerjük
értékét, akkor az
𝑁 = 𝑝𝑞 𝜙(𝑁 ) = (𝑝 − 1)(𝑞 − 1) egyenletrendszerb®l meghatározható
𝑝
és
𝑞,
nevezetesen a
sítés után a második egyenletb®l a másodfokú
𝑝2 − (𝑁 − 𝜙(𝑁 ) + 1)𝑝 + 𝑁 = 0 24
𝑞 = 𝑁/𝑝
helyette-
egyenletet kapjuk, ami polinom id®ben megoldható. A kérdés tehát az, vane olyan algoritmus, mely 𝑁 , 𝑒 és 𝑦 ismeretében kiszámítja azt az 𝑥 számot, 𝑒 melyre 𝑥 ≡ 𝑦 (mod 𝑁 ). Mindmáig nyitott kérdés, hogy ez a probléma ekvivalens-e a faktorizációs problémával, csak annyit tudunk, hogy nyilvánvalóan nem nehezebb nála. Nem ismeretes olyan algoritmus, mely az
𝑒-edik
𝑁 -et. A függvény inverze egyszer¶ 𝑑-edik hatványozás modulo 𝑁 . Ez az eljárás
gyököt visszaadó függvény ismeretében faktorizálni tudná
az RSA-függvény esetén kb. négyszer olyan gyors algoritmusra cserélhet® Legyen 𝑑𝑝 = 𝑑 mod 𝑝 − 1, és 𝑑𝑞 = = 𝑝 − 1 és 𝜙(𝑞) = 𝑞 − 1, ezért 𝑦 𝑑 ≡ 𝑦 𝑑𝑝 (mod 𝑝) és (mod 𝑞), és a kínai maradéktétel szerint az
a kínai maradéktétel alkalmazásával.
𝑑 mod 𝑞 − 1. hasonlóképp
Mivel 𝜙(𝑝) 𝑑 𝑑𝑞
𝑦 ≡𝑦
𝑥 ≡ 𝑦 𝑑𝑝
(mod 𝑝)
𝑑𝑞
(mod 𝑞)
𝑥≡𝑦
egyértelm¶en megoldható, nevezetesen az (1) képletet használva
(︀ )︀ 𝑥 = 𝑦 𝑑𝑝 (𝑞 −1 mod 𝑝)𝑞 + 𝑦 𝑑𝑞 (𝑝−1 mod 𝑞)𝑝 mod 𝑁, ahol a
𝑑𝑝 , 𝑑𝑞 , 𝑞 −1 mod 𝑝 és 𝑝−1 mod 𝑞 mind el®re számolhatók.
(5)
Szemléltetésül
lássunk egy példát.
1.19. példa. Legyen
𝑒 = 3
és
𝑥 = 16.
𝑝 = 11, 𝑞 = 17, így 𝑁 = 187 𝑦 = 𝑓𝑁,𝑒 (𝑥) és
Számítsuk ki az
és az
𝜙(𝑁 ) = 160. Legyen −1 𝑓𝑁,𝑑 (𝑦) értékeket, az
utóbbit a kínai maradéktétellel!
Megoldás. 𝑦 = 𝑓187,3 (16) = 163 mod 187 = 4096 mod 187 = 169 még könnyen számolható. Az inverz függvényhez meg kell határoznunk 𝑑 értékét: 𝑑 = 3−1 mod 160 = 107. Az el®re kiszámolható paraméterek:
𝑑𝑝 = 107 mod 10 = 7, 𝑑𝑞 = 107 mod 16 = 11, −1 𝑞 mod 𝑝 = 17−1 mod 11 = 2, 𝑝−1 mod 𝑞 = 11−1 mod 17 = 14 Ha csak egyszer¶ moduláris hatványozással próbáljuk az inverzet kiszámolni, akkor
𝑓𝑁,𝑑 (𝑦) = 𝑓187,107 (169) = 169107 mod 187 = 16. 25
Mivel
107
bináris alakja
ritmusa szerint
12
darab
1101011, ezért a moduláris hatványozás a 3. algo187-es modulusú szorzás elvégzése után megkapjuk
az eredményt. Ha a kínai maradéktétellel próbálkozunk, akkor a következ® számításokat kell elvégezni, ahol a moduláris hatványozások modulusai csak
11
és
17:
𝑥𝑝 = 𝑦 𝑑𝑝 mod 𝑝 = 1697 mod 11 = (169 mod 11)7 mod 11 = 47 mod 11 = 5 𝑥𝑞 = 𝑦 𝑑𝑞 mod 𝑝 = 16911 mod 17 = (169 mod 17)11 mod 17 = 1611 mod 17 = 16 )︀ (︀ 𝑥 = 𝑦 𝑑𝑝 (𝑞 −1 mod 𝑝)𝑞 + 𝑦 𝑑𝑞 (𝑝−1 mod 𝑞)𝑝 mod 𝑁 = (5 · 2 · 17 + 16 · 14 · 11) mod 187 = 16. Nagyságrendileg negyed annyi m¶veletet igényel ez utóbbi módszer alkalmazása.
1.20. kísérlet (
ExpRSA 𝒜,𝒢 (𝑛) RSA kísérlet).
𝒢
egy véletlen polinomidej¶ algo-
ritmus, mely a biztonsági paraméter függvényében el®állít két számot, azok
𝑁
számot, melyre
𝑛-bites
prím-
𝜙(𝑁 )-hez relatív prím 𝑒 számot és azt a 𝑑 𝑒𝑑 ≡ 1 (mod 𝜙(𝑁 )). Az 𝒜 algoritmus egy Z*𝑁 -beli számot szorzatát, egy
ad vissza.
∙ (𝑁, 𝑒, 𝑑) ← 𝒢(1𝑛 ) ∙ 𝑦 ← Z*𝑁 ∙ 𝑥 ← 𝒜(𝑁, 𝑒, 𝑦) 𝑒 ExpRSA 𝒜,𝒢 (𝑛) = 1, ha 𝑥 ≡ 𝑦
(mod 𝑁 ),
egyébként
= 0.
1.21. definíció. Azt mondjuk, hogy az RSA probléma nehéz, ha bármely véletlen polinomidej¶
𝒜
algoritmushoz létezik olyan elhanyagolható
𝜈
függvény, hogy
RSA AdvRSA 𝒜,𝒢 (𝑛) = P[Exp𝒜,𝒢 (𝑛) = 1] 6 𝜈(𝑛).
Négyzetgyökvonás, a Rabin-probléma Ha
𝑁 = 𝑝𝑞
Érdekes a helyzet a gyökvo-
két páratlan prím szorzata, akkor 𝜙(𝑁 ) páros, így a * * 2 négyzetre emelés, azaz az 𝑓 : Z𝑁 → Z𝑁 ; 𝑥 ↦→ 𝑥 függvény nem invertálható, s®t, minden négyzetszámnak 4 négyzetgyöke van. * Euler tételéb®l azonnal következik, hogy ha 𝑝 páratlan prím, akkor Z𝑝 ban egy 𝑦 elem pontosan akkor négyzetelem (kvadratikus maradék mod 𝑝),
nással.
26
𝑦 (𝑝−1)/2 ≡ 1 (mod 𝑝), ugyanis ha van olyan 𝑥, hogy 𝑥2 ≡ 𝑦 (mod 𝑝), (𝑝−1)/2 akkor 𝑦 ≡ 𝑥𝑝−1 ≡ 1 (mod 𝑝). Ebb®l adódik, hogy Z*𝑝 elemeinek fele négyzetelem, fele nem négyzetelem, továbbá ha 𝑝 ≡ 3 (mod 4), akkor 𝑦 (𝑝+1)/4 * mod 𝑝 számok, ugyanis négyzetgyökei Z𝑝 -ban a ±𝑦 ha
(±𝑦 (𝑝+1)/4 )2 ≡ 𝑦 (𝑝+1)/2
(mod 𝑝)
≡ 𝑦 (𝑝−1)/2 𝑦 (mod 𝑝) ≡ 𝑦 (mod 𝑝) 𝑝
Legyen tehát
és
𝑞 ≡ 3 (mod 4), 𝑥2 ≡ 𝑦
és
𝑁 = 𝑝𝑞 .
Ekkor az
(mod 𝑁 )
kongruencia megoldása a kínai maradéktétel szerint ekvivalens az
𝑥2 ≡ 𝑦 𝑥2 ≡ 𝑦
(mod 𝑝) (mod 𝑞)
kongruenciarendszer megoldásával. Mindkett®nek két-két megoldása van, így a következ®, valójában négy különböz® kongruenciarendszer négy megoldást ad:
𝑥 ≡ ±𝑦 (𝑝+1)/4
(mod 𝑝)
𝑥 ≡ ±𝑦 (𝑝+1)/4
(mod 𝑞).
𝑁 modulusú négyzetre emelés inverze könnyen szá𝑁 prímtényez®s felbontását. Meglep® módon a négy-
Azt látjuk, hogy az molható, ha ismerjük
zetgyökvonás nehézségér®l tudjuk, hogy ekvivalens a faktorizációs probléma nehézségével (ellentétben az
𝑒-edik
gyökvonással), az erre épül® Rabin krip-
torendszer mégsem terjedt el, mert a
4
gyök közül az egyetlen helyes kivá-
lasztásához az üzenetbe valamilyen redundáns információt kell tenni.
Diszkrét logaritmus és
𝑔
Legyen
egy generátoreleme, azaz
𝐺
𝐺
𝑞 -elem¶ ciklikus csoport, 0 2 𝑞−1 halmaza {𝑔 = 1, 𝑔, 𝑔 , . . . , 𝑔 }.
egy tetsz®leges
elemeinek
ExpDlog 𝒜,𝒢 (𝑛), diszkrét logaritmus kísérlet).
1.22. kísérlet (
𝒢 group
egy véletlen
polinomidej¶ algoritmus, mely a biztonsági paraméter függvényében el®állít egy
𝑞 -adrend¶
ciklikus csoportot, és annak egy
csoportban a m¶velet hatékonyan számolható. Az elemet ad vissza.
27
𝑔 generátorelemét, mely 𝒜 algoritmus egy 𝐺-beli
∙ (𝐺, 𝑞, 𝑔) ← 𝒢 group (1𝑛 ), ∙ ℎ←𝐺
ahol
ℓ(𝑞) = 𝑛,
egy egyenletes eloszlás szerint választott véletlen elem
∙ 𝑥 ← 𝒜(𝐺, 𝑞, 𝑔, ℎ) 𝑥 ExpDlog 𝒜,𝒢 group (𝑛) = 1, ha 𝑔 = ℎ, egyébként
= 0.
1.23. definíció. Azt mondjuk, hogy az diszkrét logaritmus probléma 𝒢 group -ra nézve nehéz, ha bármely véletlen polinomidej¶ 𝒜 algoritmushoz létezik olyan elhanyagolható
𝜈
függvény, hogy
Dlog AdvDlog 𝒜,𝒢 group (𝑛) = P[Exp𝒜,𝒢 group (𝑛) = 1] 6 𝜈(𝑛). A diszkrét logaritmus feltevés azt jelenti, hogy van olyan
𝒢 group
algorit-
mus, melyre nézve a diszkrét logaritmus probléma nehéz. A modern kriptográ a több
𝒢 group
algoritmusról is feltételezi ezt.
Diffie–Hellman-problémák
A diszkrét logaritmus problémához szorosan
kapcsolódik a Di eHellman kulcscserénél szerepl® probléma néhány válto𝑎 zata. A számítási Di eHellman probléma lényege, hogy ha ismerjük a 𝑔 𝑏 és 𝑔 elemeket egy 𝑔 generátorú ciklikus 𝐺 csoportban, akkor ki tudjuk-e 𝑎·𝑏 számítani a 𝑔 elemet? Ha a diszkrét logaritmust könnyen ki tudjuk számolni, akkor igen! Azt azonban nem tudjuk, hogy ha a diszkrét logaritmus probléma nehéz, akkor a számítási Di eHellman probléma is nehéz-e.
ExpCDH 𝒜,𝒢 group (𝑛), számítási (computational) Di eHellman kí-
1.24. kísérlet ( sérlet).
𝒢 group
egy véletlen polinomidej¶ algoritmus, mely a biztonsági para-
méter függvényében el®állít egy
𝑔
generátorelemét. Az
𝒜
𝑞 -adrend¶ ciklikus csoportot, és 𝐺-beli elemet ad vissza.
algoritmus egy
∙ (𝐺, 𝑞, 𝑔) ← 𝒢 group (1𝑛 ),
ahol
ℓ(𝑞) = 𝑛,
∙ 𝑎, 𝑏 ← Z𝑞 ∙ 𝑥 ← 𝒜(𝐺, 𝑞, 𝑔, 𝑔 𝑎 , 𝑔 𝑏 ) CDH 𝑎·𝑏 ExpCDH 𝒜,𝒢 group (𝑛) = 1, ha 𝑥 = 𝑔 , egyébként Exp𝒜,𝒢 group (𝑛) = 0.
28
annak egy
1.25. definíció. Azt mondjuk, hogy a számítási Diffie–Hellman probgroup léma 𝒢 -re nézve nehéz, ha bármely véletlen polinomidej¶ 𝒜 algoritmushoz létezik olyan elhanyagolható
𝜈
függvény, hogy
CDH AdvCDH 𝒜,𝒢 group (𝑛) = P[Exp𝒜,𝒢 group (𝑛) = 1] 6 𝜈(𝑛). Még érdekesebb és er®sebb a döntési (decisional) Di eHellman probléma 𝑎 𝑏 (DDH)! Az el®bb de niált kísérletben megkonstruált (𝐺, 𝑞, 𝑔, 𝑔 , 𝑔 ) ismere𝑎·𝑏 tében itt nem az a kérdés, hogy ki tudjuk-e számítani 𝑔 -t, hanem hogy egyáltalán meg tudjuk-e különböztetni egy véletlenül választott elemt®l! Legyen tehát egy
𝑏
𝒢 group
ugyanaz, mint el®bb, az
𝒜
algoritmus pedig adjon vissza
bitet, azaz legyen
𝑏 ← 𝒜(𝐺, 𝑞, 𝑔, 𝑔 𝑎 , 𝑔 𝑏 , 𝑟) Ha e bit statisztikai jellemz®i nem elhanyagolható eséllyel különböznek egy 𝑎·𝑏 véletlen 𝑟 elemre és az 𝑟 = 𝑔 elemre, akkor e probléma nem nehéz.
1.26. definíció. Azt mondjuk, hogy a döntési Diffie–Hellman probléma 𝒢 group -re nézve nehéz, ha bármely véletlen polinomidej¶ 𝒜 algoritmushoz
𝜈 függvény, hogy ⃒ ⃒ 𝑎 𝑏 𝑎 𝑏 𝑎·𝑏 ⃒ 6 𝜈(𝑛), ⃒ group AdvDDH (𝑛) = P[𝒜(𝐺, 𝑞, 𝑔, 𝑔 , 𝑔 , 𝑟) = 1] − P[𝒜(𝐺, 𝑞, 𝑔, 𝑔 , 𝑔 , 𝑔 ) = 1] 𝒜,𝒢 létezik olyan elhanyagolható
ahol
𝑟 ← 𝐺.
𝒢 group -re nézve könny¶, akkor group -re nézve, akkor a DDH a CDH probléma is. Ha pedig a CDH könny¶ 𝒢 probléma is. Az állítás megfordítása nem igaz, van olyan 𝐺 csoport, melyben Az világos, hogy ha a diszkrét log probléma
a diszkrét logaritmus és a CDH nehéznek t¶nik, de a DDH könny¶. Bár vannak olyan
𝒢 group
algoritmusok, melyekre nézve a DDH problémát
nehéznek hisszük, mégis nem alaptalan az a félelem, hogy esetleg kés®bb 𝑎·𝑏 valaki talál olyan matematikai algoritmust, mely képes 𝑔 bizonyos tulaj𝑎 donságai alapján nem elhanyagolható valószín¶séggel jól tippelni a 𝑔 -val 𝑏 és 𝑔 -vel való kapcsolatára. Ennek esélyét csökkenti a hash Di eHellman 𝑎·𝑏 feltevés. Itt egy hash-függvénnyel próbáljuk a 𝑔 esetlegesen nem teljesen véletlenszer¶ viselkedését egy véletlenszer¶ hash függvénnyel eltakarni.
𝐻 : 𝐺2 → 𝐺 egy hash-függvény. Azt mondjuk, hogy a hash Diffie–Hellman probléma 𝒢 -re nézve nehéz, ha bármely véletlen polinomidej¶ 𝒜 algoritmushoz létezik olyan elhanyagolható 𝜈 függvény, hogy ⃒ ⃒ 𝑎 𝑏 𝑎 𝑏 𝑏 𝑎·𝑏 ⃒ ⃒ AdvHDH 𝒜,𝒢 (𝑛) = P[𝒜(𝐺, 𝑞, 𝑔, 𝑔 , 𝑔 , 𝑟) = 1] − P[𝒜(𝐺, 𝑞, 𝑔, 𝑔 , 𝑔 , 𝐻(𝑔 , 𝑔 )) = 1] 6 𝜈(𝑛),
1.27. definíció. Legyen
29
ahol
𝑎, 𝑏 ← Z𝑞 , 𝑟 ← 𝐺, azaz ezek egyenletes eloszlás szerint véletlenül válasz-
tott elemek.
𝑏 𝑎·𝑏 Hogy miért épp a 𝐻(𝑔 , 𝑔 ) értéket választjuk, miért nem csak például 𝑎·𝑏 a 𝐻(𝑔 )-t, az csak a Di eHellman feltevésekre épül® ElGamal-rejtjelez®k konstrukciójából lesz világos, ugyanis ez teszi majd lehet®vé a rendszer adott feltevések mellett való biztonságának bizonyíthatóságát. A kés®bb ismertetend® ElGamal rendszerek választott kriptoszöveg alapú támadása elleni biztonságának bizonyíthatóságához még er®sebb feltevés szükséges. Ebben a támadó hozzáfér egy
𝐹
függvényhez is, melyet többször
is meghívhat, és amely megmondja, hogy két 𝑢, 𝑣 ∈ 𝐺 elem közt fennáll-e az 𝑢𝑎 = 𝑣 összefüggés a rögzített, de a támadó számára ismeretlen 𝑎 mellett.
ExpIDH 𝒜,𝒢 (𝑛), interaktív Di eHellman kísérlet). 𝒢 egy véletlen
1.28. kísérlet (
polinomidej¶ algoritmus, mely a biztonsági paraméter függvényében el®állít egy
𝑞 -adrend¶ ciklikus csoportot, és annak egy 𝑔 generátorelemét. Az 𝒜 al𝐺-beli elemet ad vissza, miután 𝑘 -szor meghívja az 𝐹 függvényt
goritmus egy
az általa választott paraméterekkel.
∙ (𝐺, 𝑞, 𝑔) ← 𝒢(1𝑛 ),
ahol
ℓ(𝑞) = 𝑛,
∙ 𝑎, 𝑏 ← Z𝑞 ∙ 𝐹 (𝑢, 𝑣) = 1,
ha
𝑢𝑎 = 𝑣 ,
egyébként
= 0.
∙ 𝑥 ← 𝒜(𝐺, 𝑞, 𝑔, 𝑔 𝑎 , 𝑔 𝑏 , 𝐹 (𝑢1 , 𝑣1 ), . . . , 𝐹 (𝑢𝑘 , 𝑣𝑘 )) IDH 𝑎·𝑏 ExpIDH 𝒜,𝒢 (𝑛) = 1, ha 𝑥 = 𝑔 , egyébként Exp𝒜,𝒢 (𝑛) = 0.
1.29. definíció. Azt mondjuk, hogy az interaktív Diffie–Hellman probléma
𝒢 -re nézve nehéz, ha bármely véletlen polinomidej¶ 𝒜 algoritmushoz 𝜈 függvény, hogy
létezik olyan elhanyagolható
IDH AdvIDH 𝒜,𝒢 (𝑛) = P[Exp𝒜,𝒢 (𝑛) = 1] 6 𝜈(𝑛). Az el®z®ekben felsoroltuk a legismertebb és legfontosabb makacs számelméleti problémákat.
Csak azokkal foglalkoztunk, amelyek legalább emlí-
tés szintjén, vagy az összefüggések megvilágítása érdekében szükségeseknek t¶nnek ahhoz, hogy a legelterjedtebb nyílt kulcsú rejtjelez®ket megismerjük. Nem foglalkoztunk azokkal a makacs problémákkal, amelyek csak elméleti vagy történeti szempontból érdekesek, például nem ismertettük a hátizsákfeladatra épül® nyílt kulcsú titkosító rendszert, amelyet végül sikerült föltörni az LLL-algoritmussal.
30
1.4. Egyirányú kiskapufüggvények Az egyirányú függvények a legalapvet®bb kriptográ ai primitívek közé tartoznak.
Lényegük, hogy a függvény kiértékelése könny¶, invertálása vagy
ha nem invertálható, akkor az ®skép bármelyik elemének kiszámítása viszont nehéz.
Azaz adott
𝑥-re
𝑓 (𝑥)-et, de melyre 𝑓 (𝑧) = 𝑦 .
könny¶ kiszámolni
ismeretében nehéz olyan
𝑧 -t
találni,
egy
𝑦 = 𝑓 (𝑥)
érték
Használatuk szám-
talan helyen és számtalan módon el®fordul kriptográ ai protokollokban, a szimmetrikus titkosítás egésze lényegében ezekre épül. Elég visszautalnunk arra, hogy a Feistel-tipusú szimmetrikus rejtjelez®k (pl. a DES) arra az ötletre építenek, mely egy nem invertálható egyirányú függvényb®l invertálható egyirányú függvényt képez. A bijektív egyirányú függvényeket szokás egyirányú permutációknak is nevezni. Az angol elnevezések:
one-way permutation.
one-way function
és
A nyílt kulcsú rejtjelez®kben az egyirányú függvény és permutáció egy speciális változata, az egyirányú kiskapufüggvény, illetve az egyirányú kiskapupermutáció játssza a kulcsszerepet. olyan információ
𝑓 -r®l,
Ezek is egyirányúak, viszont van egy
melynek birtokában már könny¶
letve egy elem valamely ®sképét megkeresni.
információhoz nem lehet könnyen hozzájutni csak ilyen
𝑓
𝑓 -et
invertálni, il-
Természetesen ehhez a plusz
𝑓
ismeretében, de könny¶
függvényt létrehozni a kiskapu-információval együtt. A formális de -
níció a következ®.
1.30. definíció (Egyirányú függvény). Az
𝑓 : {0, 1}* → {0, 1}*
függvény
egyirányú, ha 1. könnyen számolható, azaz létezik egy olyan polinom idej¶ hogy bármely
ℱ
algoritmus,
𝑥-re ℱ(𝑥) = 𝑓 (𝑥);
2. nehezen invertálható, azaz tetsz®leges
𝑥-re,
𝑦 = 𝑓 (𝑥), 𝑛 = ℓ(𝑥) jelö𝒜 algoritmushoz, mely * egy {0, 1} -beli elemet ad
az
lések mellet, tetsz®leges véletlen polinomidej¶ a biztonsági paraméter és
𝑦
függvényében
vissza, létezik olyan elhanyagolható
𝜈
függvény, hogy
P[𝑓 (𝒜(1𝑛 , 𝑦)) = 𝑓 (𝑥)] 6 𝜈(𝑛). Az egyirányú függvény fogalma úgy is de niálható, hogy nem egy függvényt, hanem függvények egy egész osztályát de niáljuk. Ekkor a függvényosztály de níciójában a függvényeket indexel® algoritmusnak is szerepet kell
31
kapnia. Ezt az általánosabb fogalomalkotást a következ® de níciókban meg is tesszük, de már csak az egyirányú függvények egy speciális osztályán, a kiskapu-függvényeken.
1.31. definíció (Egyirányú kiskapu-függvény és kiskapu-permutáció). Egyirányú
kiskapu-függvények egy családján algoritmusoknak azt a (𝒢, 𝑓, 𝑓 −1 )
hármasát értjük, melyre: 1.
(𝑘, 𝑡, 𝒟𝑘 , ℛ𝑘 ) ← 𝒢(1𝑛 ), ahol 𝒢 véletlen polinom idej¶ algoritmus, mely egy (𝑘, 𝑡) párt, és a 𝑘 -val indexelt 𝑓𝑘 függvényhez a 𝒟 𝑘 értelmezési tartományt és az ℛ𝑘 értékkészletet generálja.
2.
𝑦 = 𝑓𝑘 (𝑥), ahol 𝑓 determinisztikus polinom idej¶ algoritmus, mely a 𝒢 által generált 𝑘 indexhez és egy 𝑥 ← 𝒟𝑘 elemhez az 𝑦 ∈ ℛ𝑘 elemet rendeli.
3.
𝑓𝑘
egyirányú, azaz tetsz®leges véletlen polinomidej¶
mely a biztonsági paraméter és
𝑦
függvényében egy
vissza, létezik olyan elhanyagolható
𝜈
𝒜 algoritmushoz, 𝒟𝑘 -beli elemet ad
függvény, hogy
P[𝑓𝑘 (𝒜(1𝑛 , 𝑦)) = 𝑓𝑘 (𝑥)] 6 𝜈(𝑛). 𝑓 −1 algoritmus determinisztikus polinom idej¶, mely a 𝒢 által ge−1 nerált 𝑡 indexhez és az 𝑦 = 𝑓𝑘 (𝑥) értékhez olyan 𝑓𝑡 (𝑦) értéket (esetleg
4. Az
több ilyen értéket) rendel, mely(ek)re
𝑓𝑘 (𝑓𝑡−1 (𝑦)) = 𝑦. Ha
𝑓𝑘
minden
𝑘 -ra
bijekció, egyúttal
𝒟𝑘 = ℛ𝑘 ,
akkor a
mast egyirányú kiskapu-permutációnak nevezzük. Ilyenkor
(𝒢, 𝑓, 𝑓 −1 ) hár𝒢(1𝑛 ) kimenete
(𝑘, 𝑡, 𝒟𝑘 ). Az egyirányú kiskapu-függvény, illetve kiskapu-permutáció angol nevéb®l származó rövidítések TDF (oneway
trapdoor permutation ).
trapdoor function ),
illetve TDP (oneway
Hamarosan látni fogunk példát egyirányú függvényre, egyirányú kiskapufüggvényre és egyirányú kiskapu-permutációra is.
Ilyenek konstrukcióihoz
legkönnyebben és az alkalmazásokban is ezek a legfontosabbak a makacs számelméleti problémák segítségével juthatunk.
32
Megjegyezzük,
egyirányú függvény létezése nincs bizonyítva! Annyit
tudunk, hogy ha sikerülne létezésüket bizonyítani, akkor abból következne,
𝐹 𝑃 ̸= 𝐹 𝑁 𝑃 , abból pedig, hogy 𝑃 ̸= 𝑁 𝑃 . tudjuk, hogy 𝑃 ̸= 𝑁 𝑃 -b®l következik-e egyirányú
hogy
Meglep® módon azt nem függvény létezése. Azokra
a problémákra, amelyekre a legfontosabb egyirányú kiskapufüggvények épül-
𝑁 𝑃 -teljesek lennének, azt sejtik, hogy ezek 𝑁 𝑃 -köztes (𝑁 𝑃 -intermediate) osztályba tartoznak. Ér-
nek, az sincs bizonyítva, hogy
𝑃 ̸= 𝑁 𝑃
esetén egy
dekes módon az NP-teljes problémákat (pl. a hátizsákfeladatot) nem sikerült igazán fölhasználni kriptográ ai célokra, mert bár a legrosszabb esetekben nehéz ®ket megoldani, egy átlagos feladatra lehet, hogy könny¶.
Egyirányú függvény a faktorizációs problémából tunk az, hogy az
𝑓 : (𝑝, 𝑞) → 𝑝𝑞
Az els® gondola-
egyirányú függvény, és valóban, ha a
faktorizáció nehéz, akkor e függvény egyirányú.
Szépséghibája, hogy ele-
ve csak prímpárokra van értelmezve. Némi ügyeskedéssel de niálható olyan függvény, mely pozitív egész prímek kiválasztása
𝑥-t®l
𝑥 számokra van értelmezve, és amelyben a 𝑝 és 𝑞
determinisztikusan függ, de mivel nincs gyakorlati
kriptográ ai alkalmazása, ismertetését mell®zzük.
Az RSA-függvény letben de niált
𝒢
Ha az RSA-probléma nehéz, akkor az 1.20. RSA-kísér-
generátorral el®állított paramétereket használva az
𝑓𝑁,𝑒 (𝑥) = 𝑥𝑒 mod 𝑁 függvény
egyirányú kiskapu-permutáció a Z*𝑁 halmazon, melynek inverze
az
−1 𝑓𝑁,𝑑 (𝑦) = 𝑦 𝑑 mod 𝑁 függvény. Nyilvánvaló, hogy itt a
𝑑
a kiskapu-információ. Ezt az
𝑓𝑁,𝑒
függ-
vényt szokás tankönyvi RSA-nak is nevezni, miután több tankönyv e függvényt, mint az RSA rejtjelez®t mutatja be.
Fontos megjegyezni, hogy ez
csak egy egyirányú kiskapu-permutáció, rejtjelezésre önmagában nem használható, amint azt kés®bb részletesen indokolni fogjuk.
Moduláris négyzetre emelés, a Rabin-függvény
(mod 4),
és
𝑁 = 𝑝𝑞 .
Legyen
𝑝
és
𝑞 ≡ 3
Amennyiben a faktorizációs probléma nehéz, akkor az
𝑓𝑁 (𝑥) = 𝑥2 mod 𝑁 33
függvény az
𝑁
egyirányú kiskapufüggvény. Nem invertálható, a kiskapu-információ
felbontása, azaz
𝑝
és
𝑞.
Egy
𝑦
szám mind a négy ®sképe kiszámolható
az
𝑥 ≡ ±𝑦 (𝑝+1)/4
(mod 𝑝)
𝑥 ≡ ±𝑦 (𝑝+1)/4
(mod 𝑞).
kongruenciarendszer megoldásával. Erre a függvényre épül a Rabin-féle kriptorendszer.
Diszkrét logaritmus ben de niált
𝐺
𝒢
Ha a diszkrét logaritmus probléma az 1.22. kísérlet-
generátorra nézve nehéz, akkor a
𝑞 -adrend¶, 𝑔
által generált
ciklikus csoportbeli exponenciális függvény, azaz az
𝑓 : Z𝑞 → 𝐺; 𝑥 ↦→ 𝑔 𝑥 egyirányú permutáció, ahol az inverz függvény 𝑓 −1 (𝑦)
= Dlog𝑔 (𝑦). E függvény tehát nem egyirányú kiskapu-permutáció, de a Di eHellman-
leképezés
féle ötlettel ilyen is konstruálható bel®le. Tekintsük az 1.24. kísérletben de niált 𝒢 által 𝑞 -adrend¶, 𝑔 által generált ciklikus 𝐺 csoportot, legyen 𝑎 ∈ Z𝑞 olyan, 𝑎 hogy a ℎ = 𝑔 is generátora legyen 𝐺-nek (azaz 𝑎 és 𝑞 − 1 legyenek relatív prímek). Ekkor, ha a számítási Di eHellman probléma 𝒢 -re nézve nehéz,
Diffie–Hellman függvény generált
akkor az
𝑓𝐺,𝑞,𝑔,ℎ : 𝐺 → 𝐺; ℎ𝑏 ↦→ 𝑔 𝑏 függvény
egyirányú kiskapu-permutáció. A kiskapu-információ az
v®, a függvény inverze az ℎ𝑏 elemet rendeli.5
𝑎 kite−1 𝑓𝐺,𝑞,𝑔,𝑎 (𝑥) = 𝑥𝑎 , mely tehát 𝑔 𝑏 -hez a (𝑔 𝑏 )𝑎 = (𝑔 𝑎 )𝑏 =
Kriptográfiai hash függvények
Az egyirányú függvények egy különle-
gesen fontos osztályát alkotják a kriptográ ai hash függvények (magyarítása hasító függvény). Egy
𝐻
függvény
hash függvény, ha
𝐻 : {0, 1}* → {0, 1}𝑚 .
Fogalmazha-
tunk úgy, hogy a hash függvény egy tetsz®leges véges hosszú sztringet adott
5 Megjegyezzük, itt az 𝑏
ℎ
𝑓
függvényt az értelmezési tartomány, azaz
𝐺
elemeinek csak
alakban megadott formáján tudjuk polinom időben végrehajtani. Ez a „szépséghiba”
azonban nem akadályozza meg, hogy jól használható rejtjelező készüljön belőle.
34
hosszúságúra tömörít, vagy hogy róla adott hosszúságú lenyomatot készít. 𝑀 Ha 𝐻 : {0, 1} → {0, 1}𝑚 , ahol 𝑀 > 𝑚, akkor x hosszú hash függvényr®l beszélünk. Hash függvényeket használnak az adatok számítógépes tárolásában, kezelésében. A hash-tábla egy olyan rögzített méret¶ táblázat, mely az tumra vonatkozó valamilyen adatot a táblázat az üres, ahol
𝐻
𝐻(𝑥)-edik
𝑥
és
𝑦
objek-
cellájába tesz, ha
𝐻 függvény, ha 𝐻(𝑥) = 𝐻(𝑦) két külön-
a hash függvény. Nyilván akkor jó egy ilyen
ritkán fordul el® ütközés, azaz ritkán esik meg, hogy böz®
𝑥
objektumra. A kriptográ ai (vagy kriptográ ailag biztonságos)
hash függvényekre sokkal er®sebb kikötéseket kell tennünk, nem elég, hogy ütközés ritkán forduljon el®, hanem nehézzé (a gyakorlatban reménytelenné) kell tenni, hogy egy támadó egy ütköz® párt szándékosan találhasson.
Az
ilyen hash függvényeket ütközésállónak fogjuk nevezni. A kriptográ ai, tehát ütközésálló hash függvény de níciójában függvények egy családját fogjuk de niálni. A függvényeket egy kulccsal indexeljük, ez a kulcs azonban nem a titokban tartandó kulcsot jelenti, csak a függvények megkülönböztetésére szolgál.
A kulcsot pedig a szükségleteknek megfelel®en választjuk, nem
feltétlenül egyenletes eloszlás szerint véletlenszer¶en. Szokás az így de niált hash függvényt kulcsolt hash függvénynek is nevezni.
1.32. definíció. Hash függvényen (hash függvények egy családján) egy olyan véletlen polinomidej¶ algoritmusokból álló 1.
𝑘 ← 𝒢(1𝑛 ),
𝐻 = (𝒢, ℋ)
párt értünk, ahol
azaz a biztonsági paraméter függvényében
𝒢
generál egy
kulcsot, 2. van olyan 𝑚 polinom, hogy ℋ a 𝑘 és 𝑚(𝑛) függvényében tetsz®leges 𝑥 ∈ {0, 1}* sztringhez egy {0, 1}𝑚(𝑛) -beli sztringet rendel, melyet 𝐻𝑘 (𝑥)-szel jelölünk. Nem fog zavart okozni, ha
𝐻𝑘 -ra,
mint
{0, 1}* → {0, 1}𝑚(𝑛)
függvényre te𝑀 (𝑛) kintünk. 𝐻 -t x hosszúságú hash függvénynek nevezzük, ha 𝑥 ∈ {0, 1} , 𝑀 (𝑛) 𝑚(𝑛) azaz 𝐻𝑘 : {0, 1} → {0, 1} , ahol 𝑀 (𝑛) > 𝑚(𝑛). A hash-függvény kriptográ ai alkalmazhatóságához szükséges, hogy a függvény ütközésálló (további elnevezések: ütközés-ellenálló, ütközésmentes,
collision resistant ) legyen, mely azt 𝑧 sztringet, melyre 𝐻𝑘 (𝑥) = 𝐻𝑘 (𝑧).
jelenti, hogy nehéz találni két olyan
𝐻 = (𝒢, ℋ) hash polinomidej¶ 𝒜 algoritmusra
1.33. definíció. A
függvény
véletlen
melynek inputja a
35
𝑥 és
ütközésálló ha tetsz®leges
𝒢
által generál
𝑘
kulcs, kimenete egy
(𝑥, 𝑧)
pár , létezik olyan elhanyagolható
𝜈
függvény,
hogy
P[𝐻𝑘 (𝑥) = 𝐻𝑘 (𝑧)] 6 𝜈(𝑛). 𝐻𝑘 függvény szükségképha ismerünk egy (𝑥, 𝐻𝑘 (𝑥)) párt, akkor nehéz hogy hash értéke, azaz 𝐻𝑘 (𝑥) ne változzék (erre
A de nícióból egyrészt világos, hogy egy ilyen pen
egyirányú, másrészt
megváltoztatni
𝑥-et
úgy,
a tulajdonságra használják a gyenge ütközésálló, második ®skép ellenálló, angolul a
second preimage resistant
kifejezéseket).
Az ütközésálló hash függvények számtalan kriptográ ai protokollban kapnak szerepet, a hitelesítési eljárásokban, így a nyílt kulcsú rejtjelezésben is nélkülözhetetlenek.
A Diffie–Hellman hash függvény
A Di eHellman függvényb®l konst-
ruálható ütközésálló hash függvény, mely szerepet kap az ElGamal kriptorendszer bizonyos változataiban is.
1.34. konstrukció (Di eHellman hash függvény). Tekintsük az 1.24. kísérletben de niált
𝒢
(𝐺, 𝑞, 𝑔) ← 𝒢(1𝑛 ), 𝑘 = (𝐺, 𝑞, 𝑔, ℎ) a 𝐻 = (𝒢 ′ , ℋ)
algoritmust. Legyen
legyen
ℎ←𝐺
egy véletlen elem, és legyen hash függvény ′ de níciójában szerepl® 𝒢 generátor algoritmus kimenete, azaz a kulcs. A ℋ algoritmus eredménye legyen
𝐻𝑘 : Z𝑞 × Z𝑞 → 𝐺; (𝑥, 𝑦) ↦→ 𝑔 𝑥 ℎ𝑦 . Az így de niált hash függvényt Di eHellman hash függvénynek nevezzük.
Ha a diszkrét logaritmus probléma nehéz az 1.22. kísérletben definiált 𝒢 algoritmusra nézve, akkor az 1.34. konstrukcióban megadott Diffie– Hellman hash függvény ütközésálló. 1.35. tétel.
1.5. Támadások az RSA-függvény ellen Az egyirányú (kiskapu)függvények és permutációk elleni támadáson mindazoknak a körülményeknek és lehet®ségeknek az áttekintését értjük, amelyek mellett megsz¶nik a jelölt függvény egyirányúsága. A legtöbb és legérdekesebb támadás az RSA-függvény ellen készült, ezekre koncentrálunk mi is.
36
Amikor
𝑒
kicsi
𝑒
választása mellett az szól, hogy ekkor igen gyors a 𝑒 rejtjelezés. Ekkor azonban az 𝑓 (𝑥) = 𝑥 mod 𝑁 függvény könnyen invertál√ 3 ható, ha 𝑒 és 𝑥 is kicsi. Például ha 𝑒 = 3, és 𝑥 < 𝑁 , akkor 𝑦 = 𝑥𝑒 = 𝑥3 < 𝑁 , így
Kis
𝑦 -ból 𝑥 egy egészek fölött elvégzett egyszer¶ köbgyökvonással megkapha-
tó. Coppersmith a fenti elemi példának egy mély, és sok alkalmazással rendelkez®, bizonyításában az LLL-algoritmusra épít® általánosítását bizonyította:
Legyen 𝑁 pozitív egész, 𝑓 ∈ Z[𝑥] egy 𝑑edfokú polinom, és 𝑀 = 𝑁 , ahol 𝜀 > 0. Ekkor az összes olyan 𝑥 hatékonyan megtalálható, amelyre |𝑥| < 𝑀 és 𝑓 (𝑥) mod 𝑁 = 0. A futási idő az LLL-algoritmusnak egy 𝑂(min( 1𝜀 , log 𝑁 ))-dimenziós rácson való futási idejétől függ. 1.36. tétel (Coppersmith, 1997). 1/𝑑−𝜀
Mindennek ellenére van az RSA-függvényre épül® rejtjelez®nek olyan implementációja, ahol
𝑒 = 3,
Kis
𝑒 közös üzenettel 𝑁2 , 𝑁3 három páronként
𝑥
de így természetesen
garantáltan nem kicsi.
Az egyszer¶ség kedvéért legy
𝑒 = 3,
és legyen
𝑁1 ,
relatív prím egész. A
𝑐𝑖 = 𝑥3 mod 𝑁𝑖 ,
𝑖 = 1, 2, 3
függvényértékekb®l bár külön-külön nem tudnánk megkapni
𝑥
értékét, e
három egyenletb®l már igen, ugyanis a kínai maradéktétel szerint van olyan 𝑐* < 𝑁1 𝑁2 𝑁3 = 𝑁 * egész, melyre
𝑐* ≡ 𝑐1 𝑐* ≡ 𝑐2 𝑐* ≡ 𝑐3 De mivel
(mod 𝑁1 ) (mod 𝑁2 ) (mod 𝑁3 )
𝑐* = 𝑥3 mod 𝑁 * , 𝑥 < 𝑁𝑖 (𝑖 = 1, 2, 3),
ezért
𝑥3 < 𝑁 * .
Tehát ismét
egy egyszer¶ egészek fölötti köbgyökvonás segít.
Hastad támadása ha a közös
Az el®z® gyenge megoldás látszólag könnyen javítható,
𝑥 érték elé megkülönböztet® jelzést, paddinget teszünk, pl. legyen 𝑐𝑖 = (𝑖 · 2𝑚 + 𝑥)3 mod 𝑁𝑖 ,
Meglep® módon ekkor is meghatározható
𝑥
a
𝑖 = 1, 2, 3 𝑐𝑖
értékekb®l. S®t, még akkor
is, ha
𝑐𝑖 = (𝑝𝑖 (𝑥))𝑒 mod 𝑁𝑖 , 37
𝑖 = 1, 2, . . . , 𝑘
ahol
𝑝𝑖
mindegyike polinom és
𝑘
elegend®en nagy. Az alábbi egészen általá-
nos eredmény fontos kriptográ ai következménye, hogy a paddingnek mindig véletlennek kell lennie.
Legyen 𝑁1 ,. . . ,𝑁𝑘 páronként relatív prím és jelölje 𝑁min közülük a legkisebbiket. Legyen 𝑔𝑖 ∈ Z𝑁𝑖 [𝑥] legföljebb 𝑑-edfokú polinom (𝑖 = 1, . . . , 𝑘 ). Tegyük fel, hogy egyetlen olyan 𝑥 < 𝑁min létezik, hogy
1.37. tétel (Hastad).
𝑔𝑖 (𝑥) ≡ 0
(mod 𝑁𝑖 ) minden 𝑖 = 1, 2, . . . , 𝑘 indexre.
Ha 𝑘 > 𝑑, akkor 𝑥 hatékonyan meghatározható az (𝑁𝑖 , 𝑔𝑖 ) párok ismeretében. E tétel egyszer¶en fogalmazva azt mondja, hogy egyváltozós polinomkongruenciák relatív prím modulusok mellett megoldhatóak, ha elegend® számú kongruencia áll rendelkezésre. Ezt az RSA-függvény invertálásához a következ®képp használhatjuk. Te-
𝑓𝑁𝑖 ,𝑒𝑖 RSA-függvényeket (𝑖 = 1, 2, . . . , 𝑘 ). Kiszámoljuk az 𝑐𝑖 = 𝑓𝑁𝑖 ,𝑒𝑖 (𝑝𝑖 (𝑥)), ahol a 𝑝𝑖 polinomok alkalmazásával kívánjuk megakadályozni 𝑥 𝑒𝑖 kiszámíthatóságát a 𝑐𝑖 értékekb®l. Legyen 𝑔𝑖 = 𝑝𝑖 − 𝑐𝑖 mod 𝑁𝑖 . Az el®z® tétel szerint ha 𝑘 > max𝑖 (𝑒𝑖 deg 𝑝𝑖 ), akkor e kongruenciarendszer megoldható,
kintsük az
tehát az RSA-függvényekb®l még ilyen módosítással is felfedhet® a kiértékelésre szánt közös
Amikor
𝑑
𝑥.
kicsi
Ahogy kis
𝑒
𝑑 a dekódoló futási idejét 𝑁 = 𝑝𝑞 szám ismeretében meg-
a rejtjelez®, kis
csökkenti. Meglep® módon, csak az
𝑒
szerezhet® a kiskapu-információ, azaz
és az
𝑑,
ha az kicsi.
Ha 𝑁 = 𝑝𝑞 , 𝑞 < 𝑝 < 2𝑞 és 𝑑 < és 𝑒 ismeretében 𝑑 polinom időben meghatározható. 1.38. tétel (Wiener, 1990).
1 3
√ 4 𝑁 , akkor 𝑁
𝑒 Az algoritmus arra a számelméleti tételre épít, hogy ha az törthöz 𝑁 𝑘 létezik olyan tört, hogy 𝑑 ⃒ ⃒
⃒𝑒 ⃒ ⃒ − 𝑘⃒ < 1 , ⃒𝑁 𝑑 ⃒ 𝑑2
𝑘 𝑒 tört csak az lánctörtalakjának egy szelete lehet. A 𝑑 𝑁 fenti egyenl®tlenség pedig könnyen bizonyítható a tétel feltételeib®l. 𝑒 Az lánctörtalakja összes szeletének végigpróbálása hatékonyan elvégez𝑁 √ √ 1 4 het® tapasztalatok szerint még a 𝑁 -es korlát fölött, de azért 𝑁 alatt. 3 (A fels® korlát pontos meghatározása nyitott kérdés.)
és
𝑑 < 𝑁,
akkor a
38
Amikor
𝑥
kicsi – gyökös támadás
Az világos, hogy ha
𝑥-r®l
tudjuk,
𝑀 -elem¶ halmazba esik, akkor 𝑀 -ben lineáris lépésben az 𝑦 = 𝑓 (𝑥) értékb®l meghatározhatjuk 𝑥-et. Tegyük fel, hogy tudjuk, 0 6 𝑥 < 𝑚 𝑀 ötletes algoritmus √ = 2 , azaz 𝑥 egy legföljebb 𝑚-bites szám. A következ® 𝑀 lépésben nagy valószín¶séggel megtalálja a 𝑐 = 𝑥𝑒 mod 𝑁 rejtett szöveg ismeretében 𝑥-et! Az ötlet sok egyéb támadásnak is alapötlete. hogy egy adott
input: a nyilvános kulcs output:
𝑥,
ahol
(𝑁, 𝑒); a rejtett szöveg 𝑐; 𝑥 mod 𝑁 = 𝑐 és 𝑥 hossza 𝑚.
a szöveg hossza
𝑚
𝑒
𝜇 ← ( 12 , 1) 𝑅 = 2𝜇𝑚 for 𝑟 = 1 to 𝑅 do 𝑐𝑟 = 𝑟𝑐𝑒 mod 𝑁 end
(𝑟, 𝑐𝑟 )|𝑅 𝑟=1 a második elemek szerint for 𝑠 = 1 to 𝑅 do if 𝑠𝑒 mod 𝑁 = 𝑐𝑟 valamelyik 𝑟 -re then return 𝑟 · 𝑠 mod 𝑁 sort
end end 5. algoritmus: Gyökös támadás az RSA-függvény inverzének kiszámítására
𝑚 Ha választunk egy véletlen 𝑥 < 2 üzenetet, akkor nagy valószín¶séggel 𝜇𝑚 van két olyan 1 < 𝑟, 𝑠 6 2 egész, hogy 𝑥 = 𝑟 · 𝑠. Így
𝑐 ≡ 𝑥𝑒 ≡ 𝑟 𝑒 · 𝑠 𝑒
(mod 𝑁 ),
𝑐/𝑟𝑒 ≡ 𝑠𝑒 (mod 𝑁 ). Az algoritmus idejéb®l 𝑂(𝑚2𝜇𝑚 ) lépés a rendezéshez, 𝑂(𝑚) lépés a bináris kereséshez kell. 80 Ez rendkívül er®s támadás, ha belegondolunk, egy 2 bites 𝑥-b®l képzett 𝑦 = 𝑓 (𝑥) invertálása kimerít® kereséssel a mai technikai körülmények közt 40 belátható id®n belül kivitelezhetetlen, viszont 2 lépés már nem! azaz
Közös modulus
Két különböz® RSA-függvénynek nem szabad közös mo-
dulust választani, mert az egyik kiskapu-információját ismerve a másik is
39
𝑓𝑁,𝑒𝑖 RSA-függvények 𝑒𝑖 értékeit, és csak egyikük, kiskapu-információját, pl. 𝑑1 -et, akkor abból az összes többit is ki tudjuk számolni, hisz 𝑒1 𝑑1 ≡ 1 (mod 𝜙(𝑁 )), ahonnan 𝑁 felbontása, abból pedig a többi függvény 𝑑𝑖 -értéke (𝑖 = 2, 3 . . . ) kiszámolható. Kérdés, egy tulajdonos használhat-e egy modulushoz különböz® 𝑒𝑖 -ket? A
megszerezhet®.
Ugyanis ha
𝑁 = 𝑝𝑞 ,
és ismerjük az
válasz erre is határozott nem! Az RSA-függvény egyirányú kiskapu-permutáció
𝑐𝑖 = 𝑓𝑁,𝑒𝑖 (𝑥) értékeket relatív prím 𝑒1 és 𝑒2 𝑒1 és 𝑒2 relatív prímek, ezért létezik 𝑢𝑒1 + 𝑣𝑒2 = 1, így viszont
volta azonnal megsz¶nik, ha az
kitev®vel is hozzáférhet®vé válnak. Mivel olyan
𝑢
és
𝑣,
hogy
𝑐𝑢1 𝑐𝑣2 = 𝑥𝑢𝑒1 𝑥𝑣𝑒2 = 𝑥𝑢𝑒1 +𝑣𝑒2 ≡ 𝑥1 = 𝑥 mod 𝑁. Megváltoztathatóság
𝑁
Ha csak annyit tudunk, hogy
argumentuma egy olyan
tathatjuk
𝑦
𝑥
𝑦 = 𝑓 (𝑥) = 𝑥𝑒 mod
érték, mely egy számadat, akkor megváltoz-
értékét úgy, hogy a változás hatását el®re ki tudjuk számolni.
Például ha azt tudjuk, hogy
𝑥
egy árajánlat, akkor ugyan nem tudjuk meg
mennyi az 𝑥, de alá tudunk ígérni, ha ugyanis 𝑥 19 𝑒 𝑦 · ( 20 ) mod 𝑁 dekódolás után 0.95𝑥-et ad.
Implementációk elleni támadások
5%-a egész szám, akkor
Egy-egy egyirányú függvény megva-
lósítása valamely valós rendszerben sok olyan támadásra ad lehet®séget, melyek az implementációval kapcsolatosak. Ezek egy része ki nomult m¶szaki megoldásokra épít, de az ezek elleni védelem nem szükségképpen m¶szaki megoldást igényel. Itt csak két egyszer¶ támadást említünk. A legfontosabb, leggyakoribb, és bizonyos esetekben igen hatékony az id®méréses (timing) támadás.
Ez
nem csak az egyirányú függvények ellen, de szinte bármilyen kriptográ ai protokoll ellen m¶ködik, ahol egy program futási ideje, korrelációba kerülhet érzékeny adatokkal.
Például az RSA-függvény dekódolásakor alkalmazott
moduláris hatványozásban használt
𝑑
kitev®, bitr®l bitre kitalálható a dekó-
dolónak küldött megfelel®en kiválasztott üzenetek visszafejtésére fordított id®b®l. Az egyik általánosan elterjedt védekezés ez ellen a
vakítás. A vakításnál
𝑦 -t emeli 𝑑-edik hatványra, hanem választ egy 𝑟 𝑧 = 𝑦𝑟𝑒 mod 𝑁 számot hatványozza, mely a támadónak 𝑑 𝑑 már ismeretlen. Ekkor a számítás 𝑧 = 𝑦 𝑟 mod 𝑁 , vagyis a keresett 𝑥 = 𝑑 𝑑 𝑦 mod 𝑁 számot a 𝑧 /𝑟 mod 𝑁 képlet adja.
a dekódoló nem a kapott véletlen számot, és a
40
Természetesen lehet próbálkozni azzal is, hogy minden programrész úgy legyen megírva, hogy semelyik futási ideje se kerüljön korrelációba érzékeny adatokkal. Ilyesmi elérhet® pl. felesleges ciklusok beszúrásával, melyek révén elérhet®, hogy a program mindig azonos ideig fusson. Ha támadónak nem csak a futási id®t, de az elektronikus eszköz áramfelhasználását, vagy bármely más zikai id®ben változó jellemz®jét mérni tudja, további támadási lehet®ségekhez jut! Még érdekesebb és veszélyesebb a helyzet, ha a támadó be is tud avatkozni az eszköz m¶ködésébe. Az ilyen támadások egyike, mely pl. smart kártyákon viszonylag könnyen megvalósítható, RSA-függvény kiskapu-információjának megszerzése futási hiba okozásával.
Az 1.4. példa
(c)
pontjában, illetve
az 1.19. példában láttuk, hogyan lehet moduláris hatványozást a kínai maradéktételre építve kiszámolni. Tegyük fel, hogy egy támadó annyira nyomon tudja követni egy smart kártya m¶ködését, hogy tudja mikor számolja ki az 𝑥𝑝 = 𝑦 𝑑𝑝 mod 𝑝, illetve az 𝑥𝑞 = 𝑦 𝑑𝑞 mod 𝑞 értékeket. Elég e számolás közben valamilyen gyors küls® beavatkozással megzavarni a program m¶ködését! Tegyük fel, hogy
𝑥𝑝
korrekt, de
𝑥¯𝑞
nem, azaz a bel®lük kiszámított
𝑥¯
sem
korrekt, nevezetesen
𝑥¯𝑒 ≡ 𝑦
(mod 𝑝),
Ebb®l pedig következik, hogy
de
𝑥¯𝑒 ̸≡ 𝑦
gcd(𝑁, 𝑥¯𝑒 −𝑦) = 𝑝.
(mod 𝑞). Ezzel pedig hozzájutottunk
a kiskapu-információhoz.
1.6. Ciklikus csoportok az elliptikus görbéken Az eddigi számításainkat, akár a moduláris aritmetikára, akár a diszkrét logaritmus problémára gondolunk, mindig valamely ciklikus csoportban végeztük.
A ciklikus csoportok egy kriptográ ai szempontból különösen fontos
osztályával ismerkedünk meg, melyek az elliptikus görbék segítségével de niálhatók. Fontosságukat az adja, hogy a diszkrét logaritmus problémára e csoportban eddig nem ismerünk szubexponenciális algoritmust, míg a moduláris aritmetika ciklikus csoportjaiban igen.
41
Elliptikus görbék nem
3.
6
Legyen
F
egy test, melynek karakterisztikája nem
Tipikus alkalmazásokban e test az F𝑝 véges test, ahol 𝑎, 𝑏 ∈ F olyan, hogy 4𝑎3 + 27𝑏2 ̸= 0. Az
𝑝>3
2
és
prím.
Legyen
𝑦 2 = 𝑥3 + 𝑎𝑥 + 𝑏 egyenletet kielégít® nevezett
𝒪
(6)
(𝑥, 𝑦) ∈ F × F
pontok, valamint egy végtelen távolinak 7 3 2 pont halmaza elliptikus görbét alkot . A 4𝑎 + 27𝑏 ̸= 0 kikötés
azt biztosítja, hogy az elliptikus görbén ne legyen ún. szinguláris pont, azaz 3 hogy az 𝑥 + 𝑎𝑥 + 𝑏 = 0 egyenletnek ne legyen többszörös gyöke. El®ször két valós test fölötti elliptikus görbe ábráját mutatjuk (ld. 1. ábra), majd három
F11 fölötti görbéjét, melyek pontjait 11×11-es négyzetrácson
ábrázolunk (ld. 2. ábra). Az utóbbi ábrán látható piros pontok a végtelen távoli
𝒪
pontot ábrázolják, a pontok közt futó vonalak magyarázatát kés®bb
adjuk meg. 2 Az 𝑦 = esetben
𝑥3 + 𝑎𝑥 + 𝑏 egyenletb®l világos, hogy a függvény gra konja valós szimmetrikus az 𝑥-tengelyre. Ha véges test fölötti elliptikus görbét
egy négyzetrácson ábrázolunk, akkor ez a szimmetriatulajdonság megmarad, 𝑝−1 , . . . , −1, 0, 1, . . . , 𝑝−1 } elemekkel reprezentálamennyiben Z𝑝 elemeit a { 2 2 juk. Saját ábráinkon inkább a Z𝑝 = {0, 1, . . . , 𝑝 − 1} reprezentációt választottuk, így az
(𝑎, 0)
alakú pontok kiesnek a szimmetriából.
A végtelen távoli pont: affin és projektív koordináták sík legyszer¶bben úgy modellezhet®, hogy a
3-dimenziós
A projektív
tér origón átmen®
egyeneseit tekintjük a projektív sík pontjainak, és az origón átmen® síkokat a projektív sík egyeneseinek. Egy origón átmen® egyenest bármely irányvektorával jellemezhetünk, tehát az
[𝑋, 𝑌, 𝑍] vektor és a [𝑐𝑋, 𝑐𝑌, 𝑐𝑍] vektor (𝑐 ̸= 0)
ugyanazt az egyenest vagyis a projektív síknak ugyanazt a pontját hatá-
[𝑋, 𝑌, 𝑍] vektornak megfelel egy projektív pont, kivéve a 𝑍 ̸= 0, akkor végigosztva vele, az [𝑋/𝑍, 𝑌 /𝑍, 1] vektort kapjuk, mely a 𝑍 = 1 egyenlet¶ sík egy pontjába mutat, vagyis ezek a pontok megfeleltethet®k egy a n sík pontjainak. Ezt az [𝑥, 𝑦, 1] ↔ (𝑥, 𝑦) megfeleltetéssel fejezzük ki. Ha egy projektív pont koordinátás alakja [𝑋, 𝑌, 0], akkor
rozza meg. Minden nullvektort. Ha
6 Az elliptikus görbék tárgyalása némileg különbözik e két karakterisztikára. Ugyan a 2karakterisztikájú, tehát
2-hatvány
elemű testekre épített elliptikus görbéket is használják
kriptográfiai célokra, az utóbbi időben ellenük talált bizonyos támadások okán ezeket itt nem fogjuk tárgyalni.
7 Elliptikus görbéket más alakú egyenletekből is kaphatunk, nekünk azonban ez a spe-
ciális, ún. Weierstrass-alak mindenre elég lesz.
42
1. ábra. Valós test fölötti
𝑦 2 = 𝑥3 − 4𝑥 és 𝑦 2 = 𝑥3 − 2𝑥 + 4 egyenlet¶ elliptikus
görbék gra konjai
a
𝑍=1
egyenlet¶ sík egyik pontja sem feleltethet® meg e pontnak: az ilyen
pontokat nevezzük végtelen távoli vagy ideális pontoknak. Ha az
𝑦 2 = 𝑥3 + 𝑎𝑥 + 𝑏
(7)
𝑌 2 𝑍 = 𝑋 3 + 𝑎𝑋𝑍 2 + 𝑏𝑍 3
(8)
egyenlet helyett az
𝑍= ̸ 0 esetén, 𝑍 3 -bel való leosztás (︂ )︂2 (︂ )︂3 (︂ )︂ 𝑌 𝑋 𝑋 = +𝑎 +𝑏 𝑍 𝑍 𝑍
egyenletet tekintjük, akkor
után az
a (7) egyenlettel. Ha viszont
= 𝑥, 𝑌𝑍 = 𝑦 helyettesítés után megegyezik 𝑍 = 0, akkor 𝑋 -nek is 0-nak kell lennie, így a
̸= 0)
megfelel® végtelen távoli pont is kielégíti a (8)
egyenlethez jutunk, ami az
[0, 𝑌, 0]
vektoroknak (𝑌
𝑋 𝑍
egyenletet. Ezt a végtelen távoli pontot
𝒪-val jelöljük, és úgy tekintjük, hogy
ez is rajta van a (7) egyenlettel megadott elliptikus görbén.
43
6 7 8 9 10 0 1 2 3 4 5
6 7 8 9 10 0 1 2 3 4 5
(𝑎) 𝑦 2 = 𝑥3 + 2𝑥 + 4
(𝑏) 𝑦 2 = 𝑥3 − 4𝑥
6 7 8 9 10 0 1 2 3 4 5
(𝑐) 𝑦 2 = 𝑥3 + 𝑥 + 1 2. ábra. Az
F11 = Z11
test fölötti három különböz® elliptikus görbe gra-
(𝑎) a görbének 17 pontja van (a pontm¶velet csoportja 17 elem¶ (𝑏) a görbe 12-elem¶ (csoportja egy 6 elem¶ ciklikus és egy 2-elem¶ ciklikus csoport direkt szorzata), (𝑐) a görbe 14-elem¶ (csoportja ciklikus, melynek van egy nagy prímelem¶ nevezetesen 7-elem¶ ciklikus részcsoportja). Mindhárom ábrán a tengelyeket −5-t®l 5-ig számoztuk, de mivel Z11 elemeit szívesebben jelöljük a 0-tól 10-ig terjed® számokkal, a tengelyeken is e számokat használtuk, tehát −5 = 6,. . . , −1 = 10. Az ábrán látható piros konja:
ciklikus),
pontok a végtelen távoli pontot jelölik, a pontokat összeköt® színes vonalak a pontok egy ciklikus sorrendjét adják meg a következ®kben bevezetend® pontm¶veletre nézve. 44
Például az
F11
fölötti
𝑦 2 = 𝑥3 + 2𝑥 + 4
egyenlet¶ elliptikus görbe pont-
halmaza (2. (a) ábra) a n koordinátás alakú pontokkal megadva:
𝒪 ∪ {(3, 2), (6, 1), (7, 3), (10, 10), (2, 7), (9, 6), (8, 2), (0, 9), (0, 2), (8, 9), (9, 5), (2, 4), (10, 1), (7, 8), (6, 10), (3, 9)}. Ugyanennek a görbének a pontjai projektív koordinátákkal a pontokat azonos sorrendben felsorolva:
{[0, 1, 0],[3, 2, 1], [6, 1, 1], [7, 3, 1], [10, 10, 1], [2, 7, 1], [9, 6, 1], [8, 2, 1], [0, 9, 1], [0, 2, 1], [8, 9, 1], [9, 5, 1], [2, 4, 1], [10, 1, 1], [7, 8, 1], [6, 10, 1], [3, 9, 1]}. Pontművelet az elliptikus görbén
Az elliptikus görbe egy szép tulaj-
donsága, hogy minden egyenes, mely két pontban metszi (a metszetszámot multiplicitással számolva), metszi azt egy harmadik pontban is. A 3. ábra bal gra konja azt mutatja, hogy ha
𝑃
és
𝑄
a görbe két különböz® pontja,
akkor a rajtuk átmen® egyenesen lév® harmadikat összegén ennek
𝑥-tengelyre
𝑅-rel
𝑃 és 𝑄 𝑃 = 𝑄, akkor
jelölve, a
való tükörképét fogjuk jelölni. Ha
az összeköt® egyenesen az érint®t kell érteni. Két olyan pont, melyek egymás tükörképei, a végtelen távoli pontban metszik a görbét, mely megegyezik az
𝑦 -tengelyen
lév® ideális ponttal.
A klasszikus algebrai geometria elemi ismeretei közé tartozik, hogy e m¶velettel az elliptikus görbe pontjai kommutatív csoportot alkotnak, azaz e m¶velet kommutatív, asszociatív, invertálható, zéruseleme az
𝒪
pont.
Az
asszociativitás geometriai eszközökkel szépen igazolható, a többi azonosság bizonyítása egyszer¶, de itt mell®zzük. Legyen
𝑃 = (𝑥1 , 𝑦1 )
és
𝑄 = (𝑥2 , 𝑦2 )
az
ℰ
elliptikus görbe két tetsz®leges
a n pontja. Három esetet különböztethetünk meg: 1.
𝑥1 ̸= 𝑥2 ,
2.
𝑥1 = 𝑥2
és
𝑦1 = −𝑦2 ,
3.
𝑥1 = 𝑥2
és
𝑦1 = 𝑦2 .
Az 1. esetben legyen a két ponton átmen® egyenes egyenlete Az egyenes iránytangense
𝜇=
𝑦2 − 𝑦1 , 𝑥2 − 𝑥 1 45
𝑦 = 𝜇𝑥 + 𝜈 .
𝑅
𝑅 𝑃
𝑄 𝑃
−𝑃 2𝑃
𝑃 +𝑄 3. ábra.
𝑃 + 𝑄, 2𝑃 = 𝑃 + 𝑃
és
−𝑃
megszerkesztése
és
𝜈 = 𝑦1 − 𝜇𝑥1 = 𝑦2 − 𝜇𝑥2 . Az elliptikus görbe és az egyenes metszéspontja kielégíti az
(𝜇𝑥 + 𝜈)2 = 𝑥3 + 𝑎𝑥 + 𝑏 egyenletet, azaz harmadfokú egyenletalakba rendezve
𝑥3 − 𝜇2 𝑥2 + (𝑎 − 2𝜇𝜈)𝑥 + 𝑏 − 𝜈 2 = 0. 𝜇2 (az 𝑥2 𝑥2 , ezért a
A gyökök és együtthatók összefüggése szerint a gyökök összege együtthatójának
−1-szerese),
és mivel a másik két gyök
𝑥1
és
harmadik
𝑥3 = 𝜇 2 − 𝑥 1 − 𝑥2 . Ha
𝑃 +𝑄
koordinátás alakja
(𝑥3 , 𝑦3 ),
van, ahonnan
𝜇=
akkor az egyenesen az
−𝑦3 − 𝑦1 , 𝑥3 − 𝑥 1
ahonnan
𝑦3 = 𝜇(𝑥1 − 𝑥3 ) − 𝑦1 . 46
(𝑥3 , −𝑦3 )
pont
A 2. esetben
𝑃 + 𝑄 = 𝒪.
Ez az elliptikus görbe projektív alakjából
könnyen ellen®rizhet®, ennek részletezését mell®zzük. Az utolsó, 3. esetben 𝑃 = 𝑄, így az érint® egyenletére van szükségünk. ′ Valós test fölött 𝜇 = 𝑦 , de a deriválási szabályokat formálisan értelmezve ugyanez a módszer m¶ködik véges testek fölött is. A 7 egyenlet deriválásával kapjuk, hogy
2𝑦𝑦 ′ = 3𝑥2 + 𝑎. 𝑃
koordinátáit behelyettesítve kapjuk, hogy
𝜇=
3𝑥21 + 𝑎 . 2𝑦1
Innen a többi formula azonos az els® esetben megkapottakkal. Végül már csak azokat az eseteket kell áttekinteni, amikor legalább az egyik pont a végtelen távoli
𝒪
pont. A pontok projektív alakjából azonnal
adódnak a következ® összefüggések:
𝒪+𝒪 =𝒪 𝑃 + 𝒪 = 𝑃, 𝑃 − 𝑃 = 𝒪,
(𝑥, 𝑦) ∈ ℰ esetén (𝑥, 𝑦) + 𝒪 = (𝑥, 𝑦) bármely (𝑥, 𝑦) ∈ ℰ pontra − (𝑥, 𝑦) = (𝑥, −𝑦)
azaz bármely azaz
{0, 1, . . . , 𝑝 − 1} számokkal reprezentált F𝑝 test esetén úgy kell érteni, hogy −(𝑥, 𝑦) = (𝑥, 𝑝 − 𝑦). Azt kapjuk tehát, hogy az ℰ elliptikus görbe pontjai a fönt bevezetett pontm¶velettel additív csoportot alkotnak, amit szokás az ⟨ℰ, +⟩ jelöléssel Az utóbbi összefüggést az
kifejezni. Ráadásul láttuk, hogy e m¶velet eredménye igen egyszer¶ képletekkel igen gyorsan számolható.
Az elliptikus görbe csoport
E csoport mérete és struktúrája is megha-
tározható. Méretére a híres nem triviális Hasse-tétel ad becslést, mely szerint az
F𝑝
fölötti
ℰ
elliptikus görbe pontjainak száma:
√ √ 𝑝 + 1 − 2 𝑝 6 |ℰ| 6 𝑝 + 1 + 2 𝑝. A pontos érték a hatékony Schoof-algoritmussal számolható. Ha
ℰ
egy
F𝑝
fölötti elliptikus görbe (𝑝
porthoz létezik két olyan
𝑛1
és
𝑛2
> 3),
szám, hogy
⟨ℰ, +⟩ ∼ = Z𝑛1 × Z𝑛2 , 47
akkor a rajta de niált cso-
ahol
𝑛2 | 𝑛1
és
𝑛2 | (𝑝 − 1).
A csoport struktúrájára tehát néhány különböz® esetet tudunk fölsorolni. Ha
𝑛2 = 1, akkor a csoport ciklikus!
Szerencsés esetben akár prímrend¶, ami
azért érdekes, mert a diszkrét logaritmus problémához prímrend¶ csoportot használunk. A 2. ábrán az els® görbe
17 pontos, így csoportja izomorf Z17 -tel.
Elemeit az egyik ciklikus sorrend szerint fölsorolva:
Z17 ∼ = ℰ = {𝒪,(3, 2), (6, 1), (7, 3), (10, 10), (2, 7), (9, 6), (8, 2), (0, 9), (0, 2), (8, 9), (9, 5), (2, 4), (10, 1), (7, 8), (6, 10), (3, 9)}, azaz
(3, 2)
egy generátorelem.
𝑦 2 = 𝑥3 + 𝑥 + 1 az generátoreleme (1, 6):
A harmadik elliptikus görbe, melynek pontú, csoportja izomorf
Z14 -gyel,
egyik
egyenlete,
14
Z14 ∼ = ℰ = {𝒪,(1, 6), (3, 8), (8, 9), (6, 6), (4, 5), (0, 1), (2, 0), (0, 10), (4, 6), (6, 5), (8, 2), (3, 3), (1, 5)}, E csoportból kiválasztható egy
7-edrend¶ 𝐺
részcsoport:
Z7 ∼ = 𝐺 = {𝒪, (3, 8), (6, 6), (0, 1), (0, 10), (6, 5), (3, 3)},
(9)
Egy primitív elemet és azok többszöröseit egy vékony piros vonal mentén végig követhetjük a végtelen távoli pontból, azaz a zéruselemb®l indulva, és végül oda érkezve.
(Emlékeztetünk rá, hogy e csoport additív, azaz a
m¶velet az összeadás, nem a szorzás, így a generátorelemnek nem a hatványait, hanem a többszöröseit kell számolnunk. A moduláris hatványozás technikája minden probléma nélkül átvihet® skalárral szorzásra.) E példában a
14-edrend¶
csoport
7-edrend¶
részcsoportjának elemeit kékkel jelöltük, a
többit halványabb színnel különböztettük meg. 2 3 A második gra konon látható 𝑦 = 𝑥 − 4𝑥 egyenlet¶ elliptikus görbe két ciklikus csoport direkt szorzata, az egyik
ℰ Z2 Z6 és valóban,
2 | 12
2-elem¶,
a másik
6-elem¶:
∼ = Z2 × Z6 , ∼ = {𝒪, (2, 0)}, ∼ = {𝒪, (4, 2), (4, 9), (9, 0), (10, 5), (10, 6)},
és
2 | 6.
48
Erős és biztonságos prímek
Az összes konstrukcióban fontos szerepet
játszik a prímek megfelel® kiválasztása. Bármelyik rendszer elleni jöv®beni támadás lehet®sége függhet a megfelel® prímek kiválasztásától.
Az ismert
támadások akár a faktorizációs, akár a diszkrét logaritmus ellen közt vannak olyanok, amelyek sikerét csökkenti, ha a prím úgynevezett biztonságos vagy ha er®s prím. A
𝑝
prím
biztonságos (safe
prime ),
ha
𝑝 = 2𝑞 + 1
alakú, ahol
𝑞
is prím.
Ezek a diszkrét logaritmus problémában fontosak. Az 500 alatti biztonságos prímek: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479 (a sorozat sorszáma a sorozatok OEIS katalógusában A005385) A
𝑝
erős prím, ha
1.
(𝑝 − 1)-nek van egy nagy prím, és 𝑎 pozitív egész,
2.
(𝑝1 − 1)-nek is van nagy prím, és 𝑏 pozitív egész,
3.
𝑝 + 1-nek is van nagy prímfaktora, azaz 𝑝 = 𝑐𝑝3 − 1, ahol 𝑝3 és 𝑐 pozitív egész.
𝑝 = 𝑎𝑝1 + 1,
ahol
𝑝1
nagy
𝑝1 = 𝑏𝑝2 + 1,
ahol
𝑝2
nagy
prímfaktora, tehát
prímfaktora, azaz
nagy prím,
A biztonságos prímek és az er®s prímek kapcsolata világos, hisz
𝑝 = 2𝑞 +1
esetén az er®s prímekre vonatkozó els® feltétel teljesül. A faktorizáció elleni támadásokban valójában nem nyújt nagy segítséget, ha a két prím er®s prím, mert bár a Pollard
𝜌
algoritmus ellen véd, de az
újabb és er®sebb számtest szita, és a Lenstra elliptikus görbe faktorizációs módszere ellen nem. Mindennek ellenére akad olyan szabvány, mely az RSAhoz er®s prímek választását javasolja, általában azonban a szabványok ezt nem írják el®, úgy t¶nik, szükségtelen RSA-hoz er®s prímeket választani. A diszkrét logaritmus probléma esetén más a helyzet. PohlingHellmantétele szerint, ha
𝑝−1
minden prímosztója kicsi, akkor polinom id®ben ki-
számolható a diszkrét logaritmus. Ez annak következménye, hogy a Pohling ∏︀ 𝑒𝑖 Hellman- vagy SilverPohlingHellman-algoritmus futási ideje az 𝑛 = 𝑖 𝑝𝑖 )︀ (︀∑︀ √ 𝑝𝑖 ) . Így minden diszkrét logaritmus problémára számra 𝑂 𝑖 𝑒𝑖 (log 𝑛 + épül® kriptográ ai rendszer esetén legalább
𝑝 − 1-nek
kell, hogy legyen nagy
prímosztója. A gyakorlatban biztonságos prímeket szoktak választani. A SECG csoport keretében a Certicom cég által a paraméterválasztáshoz adott javaslatok szerint a diszkrét logaritmus problémára épül® elliptikus görbéhez olyan ki kell elégítse
𝑝 választandó, melyre 𝑝 − 1 és 𝑝 + 1 legnagyobb 𝑞 19 a log𝑝 (𝑞) > feltételt. 20 49
prímfaktora
2. A nyílt kulcsú titkosítás alapfogalmai
2.1. Előzmények, kezdetek Évszázadokon át a szimmetrikus kulcsú titkosítás volt maga a titkosítás, ahol a két kommunikáló fél mindegyikének birtokolnia és ®riznie kellett a kulcsot. E kulcs cseréje és ®rzése sok nehézséget okozott és okoz ma is. Ezek megoldására az els® próbálkozások az 1970-es években születtek.
Az els®
aszimmetrikus algoritmust valószín¶leg 1973-ban az angol titkosszolgálatnál (Government Communications Headquarters, GVHQ) James H. Ellis, Cliord Cocks és Malcolm Williamson készítette el. Ez az információ csak 1997-ben került nyilvánosságra. 1974-ben egy Merkle nev¶ diák egy szemináriumon olyan ötlettel állt el®, mely lehet®vé tenné a kulcscserét nyilvános csatornán. A remek ötlet gyengéje az volt, hogy a kulcscserét végz®k számítási igényének a négyzetével arányos id® alatt egy hallgatózó támadó meg tudta szerezni a kulcsot, és ez még nem t¶nt elég biztonságosnak. Az ötletet azonban Di e és Hellman továbbfejlesztette, algoritmusukban már a négyzetes helyett exponenciális volt a két igény közti függvénykapcsolat. E kulcscsere-protokollokban megjelent az aszimmetria! Innen már csak egyetlen lépés volt az aszimmetrikus kulcsú titkosítás titkosszolgálaton kívüli feltalálása.
Merkle’s puzzle
Merkle ötlete a következ® volt: Aliz Bobbal kíván kom30 munikálni, amihez közös kulcsot kell találni. Aliz nagy számú, mondjuk 2 darab kulcsot generál, és mindegyiket titkosítva elrejti egy üzenetben: Az 𝑖-edik kulcs 𝑘𝑖 , ahol az 𝑖 sorszám 1-t®l 230 -ig változik. A titkosítás azonban annyira gyenge, hogy bármelyik feltörhet® belátható id®n belül, mondjuk 30 néhány perc alatt! Ezután a különböz® kulcsokkal titkosított 2 darab szöveget Aliz véletlen sorrendben elküldi Bobnak, aki véletlenül választ közülük egyet, azt feltöri, és a nyilvános csatornán visszaküldi Aliznak közös kulcs
𝑘𝑖
𝑖
értékét. A
lesz. A támadónak átlagosan a feladványok felét fel kell törnie,
hogy megtudja, melyik az
𝑖-edik
Diffie-Hellman kulcscsere
üzenet és ezzel megtudja a
𝑘𝑖
kulcsot.
Merkle ötletét tovább fejlesztve Di e és Hell-
man a következ® igen egyszer¶ protokollt találta ki:
2.1. konstrukció (Di eHellman kulcscsere). Adva van az paraméter.
50
1𝑛
biztonsági
𝒢 algoritmussal el®állít egy 𝑝-edrend¶ 𝐺 ciklikus csoportot és annak egy 𝑔 generátorelemét: (𝐺, 𝑝, 𝑔) ← 𝒢(1𝑛 ). Egyenletes eloszlás szerint választ egy véletlen 𝑎 ← Z𝑞 elemet, és kiszá𝑎 mítja a ℎ1 = 𝑔 elemet, végül üzenetet küld Bobnak
1. Aliz: egy véletlen polinomidej¶
Aliz
→ Bob : (𝐺, 𝑝, 𝑔, ℎ1 ).
2. Bob: fogadja Aliz üzenetét, választ egy véletlen 𝑏 ← Z𝑞 elemet, kiszá𝑏 𝑏 mítja ℎ2 = 𝑔 és 𝑘𝐵 = ℎ1 értékét, végül üzenetet küld Bobnak: Bob
→ Aliz : ℎ2
3. Aliz: fogadja Bob üzenetét, kiszámolja
𝑘𝐴 = ℎ𝑎2
értékét.
A protokoll lényege, hogy az Aliz és Bob közt zajló beszélgetést passzívan hallgató támadó ismeri
(𝐺, 𝑝, 𝑔, ℎ1 , ℎ2 )
elemeit, azonban ha ezekre a CDH-
probléma nehéz, nem tudja kiszámolni a
𝑘𝐴 = ℎ𝑎2 = (𝑔 𝑏 )𝑎 = 𝑔 𝑎𝑏 = (𝑔 𝑎 )𝑏 = ℎ𝑏1 = 𝑘𝐵 értéket, amely Aliz és Bob közös kulcsa lesz a további kommunikációhoz. Ennél több is igaz!
Végezzük el azt a kísérletet a hallgatózó támadóval,
hogy miután végighallgatta Aliz és Bob kulcscsere-kommunikációját, kap egy 1 1 valószín¶séggel egy véletlen bitsorozat, valószín¶séggel a kulcsot, mely 2 2 𝑘𝐴 = 𝑘𝐵 kulcs. A támadó el®nye a kulcscsereprotokollal szemben 𝜈(𝑛), ha 21 t®l 𝜈(𝑛)-nel eltér® valószín¶séggel el tudja találni, hogy melyik a valódi kulcs. Biztonságosnak fogjuk nevezni a Di e-Hellman kulcscserét, ha bármely
𝒜
hallgatózó támadóra ez az el®ny elhanyagolható.
Ha a DDH probléma nehéz, akkor a Diffie-Hellman kulcscsere protokoll biztonságos egy hallgatózó jelenlétében.
2.2. tétel.
E protokollt szellemessége ellenére nem használják, mert ugyan a passzív hallgatózó ellen véd, de nem véd az aktív támadó ellen, aki képes Aliz és Bob üzeneteit fogadni, és magát Aliz számára Bobnak, Bob számára Aliznak kiadni. E támadás neve man-in-the-middle. Tehát e támadás tömören leírva: 1. Aliz:
(𝐺, 𝑝, 𝑔) ← 𝒢(1𝑛 ), 𝑎 ← Z𝑞 , ℎ1 = 𝑔 𝑎 , Aliz
2. Támadó:
→
Támadó:
(𝐺, 𝑝, 𝑔, ℎ1 ).
𝑥 ← Z𝑞 , ℎ𝑥 = 𝑔 𝑥 , 𝑘𝐴 = ℎ𝑥1 51
Támadó 3. Bob:
(𝐺, 𝑝, 𝑔, ℎ𝑥 ).
Bob:
𝑏 ← Z𝑞 , ℎ2 = 𝑔 𝑏 , 𝑘𝐵 = ℎ𝑏𝑥 = 𝑔 𝑏𝑥 Bob
4. Támadó:
→
ℎ2
Támadó:
𝑦 ← Z𝑞 , ℎ𝑦 = 𝑔 𝑦 , 𝑘𝐵 = ℎ𝑥1 = 𝑔 𝑏𝑥 , 𝑘𝐴 = ℎ𝑦1 = 𝑔 𝑎𝑦
Támadó 5. Aliz:
→
→
ℎ𝑦
Aliz:
𝑘𝐴 = ℎ𝑎𝑦 = 𝑔 𝑎𝑦 .
Így a Támadónak van Alizzal és Bobbal is egy-egy közös kulcsa, a köztük lév® kommunikációt kedvére módosíthatja magát Aliz felé Bobnak, Bob felé Aliznak kiadva.
2.2. Aszimmetrikus rejtjelező egyirányú kiskapu-permutációból El kell oszlatnunk egy közkelet¶ tévedést! Az egyirányú kiskapufüggvények önmagukban nem használhatók titkosításra úgy, hogy az egyirányú függvény a rejtjelez®, a kiskapu-információ a titkos kulcs és a függvény inverze a dekódoló.
De más nehézségekkel is szembe kell nézni nyílt kulcsú rejtjelez®
konstrukciójakor. 1. Egy aszimmetrikus rejtjelez®
E
függvénye nem lehet determinisztikus,
hisz az azonnal tönkreteszi a szemantikai biztonságot: ha a támadó is-
E𝑝𝑘 (𝑚𝑖 ) értékeket is, így el tudja dönteni, hogy melyikük egyezik meg a 𝑐 = E𝑝𝑘 (𝑚𝑏 ) kriptoszöveggel. Tehát E-nek véletlen algoritmusnak kell lennie! meri az
𝑚0
és
𝑚1
sztringeket, akkor ki tudja számolni az
2. Mivel az egyirányú kiskapufüggvények determinisztikusak, ha bel®lük akarunk aszimmetrikus rejtjelez®
E
algoritmust konstruálni, az argu-
mentumuknak kell véletlennek lennie, tehát nem az üzenetre kell ®ket alkalmazni, hanem vagy egy véletlenül választott számra kell ®ket alkalmazni, vagy az üzenetek mellé véletlen üzenetet kell paddingbe tenni. 3. Abból, hogy az
𝑓
egyirányú kiskapufüggvény nehezen invertálható, nem
következik, hogy az
𝑦 = 𝑓 (𝑥)
nem szerezhet® meg. Valahogy az
𝑥-r®l
az
𝑓
𝑥-r®l semmi információ E nem determinisztikus!
ismeretében az
Így az sem elég, hogy
ismeretén keresztül megszerezhet® információt
is el kell rejteni, amihez ugyancsak a véletlent lehet segítségül hívni!
52
Els® próbálkozásként próbáljunk meg egy egyirányú kiskapu-permutációt használva rejtjelez®t konstruálni, melyben a tökéletes biztonságot nyújtó
time pad
one
(OTP) is visszaköszön.
2.3. konstrukció (Aszimmetrikus rejtjelez®). Legyen (𝒢
TDP , 𝑓, 𝑓 −1 ) az 1.31. de-
níció szerinti kiskapu-permutációk egy családja. De niáljuk a
Π = (𝒢, E, D)
aszimmetrikus kulcsú, az 1.12. de níciónak megfelel® rejtjelez®t a következ®képp: 1.
𝒢 : (𝑘, 𝑡, 𝒟𝑘 ) ← 𝒢 TDP (1𝑛 ), azaz választunk az egyirányú kiskapu-permutációk családjából egy (𝑘, 𝑡) indexpárt, és megadjuk az értelmezési tartományt. 𝒢 választ egy 𝐻 : 𝒟𝑘 → 𝒟𝑘 hash függvényt, és publikálja a 𝑝𝑘 = (𝑘, 𝑓𝑘 , 𝐻) nyílt kulcsot. A titkos kulcs az 𝑠𝑘 = (𝑡, 𝑓𝑡−1 ) lesz.
2.
E: 𝑟 ← 𝒟𝑘 , E𝑝𝑘 (𝑚) = (𝑓𝑘 (𝑟), 𝐻(𝑟) ⊕ 𝑚), 𝒟𝑘 × 𝒟𝑘 .
3.
D: D𝑠𝑘 (𝑐1 , 𝑐2 ) = 𝐻(𝑓𝑡−1 (𝑐1 )) ⊕ 𝑐2 .
Könnyen ellen®rizhet®, hogy
tehát
E𝑝𝑘 : 𝒟𝑘 × 𝒟𝑘 →
D𝑠𝑘 E𝑝𝑘 (𝑚) = 𝑚, ugyanis 𝑟 = 𝑓𝑡−1 (𝑐1 ) és 𝐻(𝑟) ⊕
𝑐2 = 𝑚. Látható, hogyan épül e konstrukcióba korábban szerzett tudásunk:
az
egyirányú függvényt egy véletlenül választott elemre használjuk. E ponton folytathatnák a rejtjelezést úgy is, hogy a nyílt szöveget az OTP-hez hasonló módon
𝑟 ⊕ 𝑚-mel
rejtjeleznénk.
nem itt és most kéne az
𝑟-et
Ez tökéletes biztonságot nyújtana, ha
is átadni.
Azt csak úgy tudjuk átadni, hogy
elhanyagolható eséllyel megszerezhet®, ezt nyújtja az egyirányú
𝑓𝑘
kiskapu-
permutáció. Csakhogy láttuk, az egyirányú permutációk nem biztonságosak abban az értelemben, hogy semmi információ ne lenne megszerezhet® az argumentumáról, azaz jelen esetben
𝑟-r®l.
(Pl. láttuk, az RSA-függvény értékéb®l
megmondható az argumentumának Jacobi-jele.) Ezért az
𝑟
használata sem
nyújt elég biztonságot az OTP-ben való használathoz, ezért egy véletlen függvénnyel el kell rejteni még azt a kevés információt madó megszerezhet róla. Erre szolgál a
𝐻
𝑟-r®l,
amit egy tá-
hash-függvény. Világos, hogy az
egész rendszer biztonsága az egyirányú kiskapu-permutáció biztonságától (az inverz kiszámításának nehézségét®l) és a hash függvény véletlenszer¶ségét®l függ.
53
Véletlen orákulum
A véletlen orákulum modell kriptográ ai rendszerek,
protokollok biztonságának megfogalmazásában és bizonyításában segít. Azt fejezi ki, hogy a rendszer az adott biztonsággal rendelkezik, amennyiben a véletlen orákulumot helyettesít® függvény valóban elég véletlenszer¶ módon m¶ködik. E fogalom használata azért terjedt el, mert egyrészt
∙
a mai kriptográ ai rendszerek nagy részének biztonsága nem bizonyítható precízen, mivel olyan számelméleti feltevésekre épül, amelyek mindmáig bizonyítatlanok, másrészt
∙
számtalan olyan kriptográ ai protokoll született/születik, amelyben kés®bb valaki biztonsági rést talál, azaz kiderül, hogy a rendszer könnyen támadható, de a támadás nem a bizonyítatlan számelméleti feltevések valamelyikének összeomlására épül, hanem egyszer¶en a konstrukció más elemei voltak rosszul kitalálva.
Mindezek miatt nagy szükség van arra, hogy valahol a precízen, minden kétséget kizáróan bizonyított biztonság és a megérzésre biztonságos között találjunk olyan matematikailag precízen bizonyítható állításokat, amelyek pontosan megfogalmazzák a bizonyított biztonság feltételeit. E feltételek egyike a nyílt kulcsú titkosításban használt makacs számelméleti probléma nehézsége!
Világos, amint egy ilyen problémára találnak hatékony algorit-
must, a rá épül® kriptográ ai rendszerek összeomlanak. A másik fontos, és gyakran el®forduló feltétel, az alkalmazott véletlen függvények, tipikusan a hash függvények közelsége a valódi véletlenhez. E feltétel kikerülésére használjuk a véletlen orákulum alkalmazását. Ez úgy képzelhet® el, hogy van egy olyan képzeletbeli résztvev®je a protokollnak, aki minden neki küldött számra válaszul küld egy véletlen följegyez, így ha kés®bb ugyanaz az laszul ugyanazt az
𝑟-et
𝑥
𝑟 számot, azonban minden üzenetváltást 𝑥 érkezik, mint egyszer már korábban, vá-
küldi. Mintha mindent följegyezne, és minden válasz
el®tt megnézné a nagykönyvben, hogy nem kapta-e már valakit®l korábban ugyanezt a számot. A véletlen orákulum modell legf®bb gyengéje, hogy a valóságban a véletlen orákulum helyén egy hash függvény van, amely nem csak hogy determinisztikus, de többnyire a támadó el®tt ismert, ezért el®re tudhatja annak válaszát bármely bemenetre, s®t elemezheti annak programkódját is! Mindennek ellenére mára alapvet®vé vált, hogy a kriptográ ai protokollok biztonsága legalább ilyen szinten bizonyítva legyen. A nyílt kulcsú titkosítás fönti de níciójáról a következ® tétel bizonyítható:
54
Amennyiben az egyirányú kiskapu-permutációk (𝒢 TDP , 𝑓, 𝑓 −1 ) családjában az inverz kiszámítása a kiskapu-információ ismerete nélkül nehéz, és a 2.3. konstrukcióban definiált Π = (𝒢, E, D) rejtjelezőben 𝐻 -t véletlen orákulummal helyettesítjük, akkor Π szemantikailag biztonságos. Egyszerűen fogalmazva: a fenti rejtjelező szemantikailag biztonságos a véletlen orákulum modellben.
2.4. tétel.
Bizonyítás. Megmutatjuk, hogy ha a véletlen orákulum modellben létezik egy olyan 𝒜 véletlen polinomidej¶ algoritmus, mely nem elhanyagolható valószín¶séggel cáfolja Π szemantikai biztonságát, akkor létezik olyan hatékony ℬ algoritmus is, mely nem elhanyagolható valószín¶séggel invertálja 𝑓 -et, azaz 𝑓 nem egyirányú. Megmutatjuk tehát, hogy ha van olyan 𝒜, melyre ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv𝒜,Π (𝑛) = ⃒⃒P[Exp𝒜,Π (𝑛) = 1] − ⃒⃒ = 𝜈(𝑛) 2 nem elhanyagolható, akkor van olyan
ℬ
algoritmus, melyre
P[𝑓 (ℬ(1𝑛 , 𝑓, 𝑦)) = 𝑓 (𝑥)] > 𝜈(𝑛). 𝐻 helyébe fogja jelölni (RO a random oraculum
E bizonyításhoz magunk de niálunk egy orákulumot, melyet a helyettesítünk. Ezt az algoritmust
ℋRO
kifejezésb®l). Legyen tehát 𝑚0 és 𝑚1 a két üzenet, E𝑝𝑘 (𝑚𝑏 ) = (𝑐1 , 𝑐2 ), ahol 𝑏 egy véletlen bit.
melyekre Az
𝒜
|𝑚0 | = |𝑚1 |.
algoritmus az
Legyen
ExpindCPA 𝒜,Π (𝑛)
nyílt szöveg megkülönböztethetetlenségi kísérlet közben sokszor meghívja a
𝐻 -t,
vagyis e modellben lefuttatja a
A
ℋRO
ℋRO
algoritmust.
algoritmus egy listában följegyez minden hozzá beérkez®
ket, ennek a listának a neve RL lesz, míg a visszaadott
ℋRO (𝑟)
𝑟
érté-
értékeket egy
másik, HL nev¶ listába jegyzi. Így valóban orákulumként fog tudni viselkedni, hisz emlékezni fog minden korábbi hívására. Ha véletlenül egy olyan 𝑟 -et RO kap, melyre ℋ (𝑟) = 𝑦 , és 𝑟 még nem szerepel az RL listában, akkor olyan értéket fog visszaadni, melyre a az
𝑚1
(𝑐1 , 𝑐2 )
pár véletlenszer¶en vagy az
𝑚0
vagy
valamelyikének titkosított változata lesz. Egyébként mindig véletlen
választ ad, tehát valóban véletlen orákulumként viselkedik.
ℬ algoritmus legalább 𝜈 valószín¶séggel Megbecsüljük annak valószín¶ségét, hogy 𝒜 sikeres
Végül meg kell mutatnunk, hogy a megtalálja
𝑦
inverzét.
55
ℬ(1𝑛 , 𝑓, 𝑦) global RL, HL, ℎ function ℋRO (𝑟) 𝑖=1
function
(az RL és HL listák aktuális hossza
ℎ)
InRL = FALSE
while if
𝑖 6 ℎ AND NOT RL[𝑖] = 𝑟 then InRL = TRUE
InRL
do
else
𝑖=𝑖+1 end end if
then return HL[𝑖]
InRL
end if
𝑓 (𝑟) = 𝑦 then 𝑏 ← {0, 1} (egy 𝑜 = 𝑐2 ⊕ 𝑚 𝑏
véletlen bit)
else
𝑜 ← 𝒟𝑘
(egy véletlen elem)
end
ℎ=ℎ+1 RL[ℎ] = 𝑟 HL[ℎ] = 𝑜 end function main
𝑐1 = 𝑦 𝑐2 ← 𝒟 𝑘 ℎ=1
ExpindCPA 𝒜,Π (𝑛) for
𝑖 = 1 to ℎ do if 𝑓 (RL[𝑖] = 𝑦 then return RL[𝑖] end
end return „nem sikerült invertálni” end end 6. algoritmus: Az
𝑓
algoritmus pszeudokódja, melyet az kísérlet közben
RO algoritmus, és benne a ℋ indCPA sokszor meghívhat az 𝒜,Π (𝑛)
inverzét kiszámító 56
𝒜
ℬ
Exp
lesz
𝑚0
𝑚1 [︀
és
P
megkülönböztetésében:
ExpindCPA 𝒜,Π (𝑛) = 1 = [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (𝑟) ∈ 𝑅𝐿 · P 𝑓 −1 (𝑟) ∈ 𝑅𝐿 + 𝒜,Π (𝑛) = 1 | 𝑓 [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (𝑟) ̸∈ 𝑅𝐿 · P 𝑓 −1 (𝑟) ̸∈ 𝑅𝐿 𝒜,Π (𝑛) = 1 | 𝑓 ]︀
Világos, hogy
P ugyanis
𝑓 −1 (𝑦)
[︀
−1 ExpindCPA (𝑟) ̸∈ 𝑅𝐿 𝒜,Π (𝑛) = 1 | 𝑓
]︀
1 = , 2
𝑚1 és 𝑚1 [︀ ]︀ −1 P ExpindCPA (𝑟) ∈ 𝑅𝐿 6 1, 𝒜,Π (𝑛) = 1 | 𝑓
ismerete nélkül nem lehet választani
és feltételezhetjük, hogy a kísérlet
közül. Mivel
1 -nél nagyobb valószín¶séggel sikeres, azt 2
kapjuk, hogy
[︀ ]︀ 1 + 𝜈(𝑛) 6 P ExpindCPA 𝒜,Π (𝑛) = 1 2 [︀ ]︀ 1 [︀ ]︀ 6 P 𝑓 −1 (𝑟) ∈ 𝑅𝐿 + P 𝑓 −1 (𝑟) ̸∈ 𝑅𝐿 2 [︀ −1 ]︀ 1 6 P 𝑓 (𝑟) ∈ 𝑅𝐿 + . 2 Így
[︀ ]︀ P 𝑓 −1 (𝑟) ∈ 𝑅𝐿 > 𝜈(𝑛), 𝑓 -et. A szük𝒜, 𝑡𝑓 az 𝑓 futási
vagyis nem elhanyagolható valószín¶séggel sikerült invertálni séges lépések száma pedig polinomidej¶, hisz ha ideje, és 𝒜 ℎ-szor 𝑡𝒜 + 𝑂(ℎ2 + ℎ𝑡𝑓 ).
𝑡𝒜
az
hívja meg az orákulumot, akkor az invertálás futási ideje
2.3. OAEP – Optimal Asymmetric Encryption Padding E módszer nevét nem magyarítjuk, az OAEP rövidítést fogjuk használni. A padding általában egy sztring szükséges hosszúságúra való föltöltését jelenti valamilyen el®re megadott módon, pl. csupa
0-val.
Kés®bb látni fogjuk,
hogy a paddinget használhatjuk arra is, hogy az üzenetet kib®vítsük véletlen bitekkel, ezzel azt legalább részben véletlenszer¶vé téve. Az e fajta padding
57
𝑛 − 𝑘0 − 𝑘1
𝑘1
bit
𝑚
𝑘0
bit
bit
0000
𝑟
G
H
𝑛 − 𝑘0
𝑘0
bit
bit
𝑥
𝑦
4. ábra. Az OAEP diagramja
nem bizonyult teljesen biztonságosnak, a sztring egy része ugyan véletlen bitekb®l áll, de a másik felén lév® bitekre nyert információ a rendszer gyengéjét jelzi.
Ezt küszöböli ki e szellemes, a Feistel-típusú rejtjelez® ötletére épít®
megoldás. El®ször csak magát a paddingelést mutatjuk meg, majd azt, hogy hogyan építhet® felhasználásával biztonságos nyílt kulcsú rejtjelez®. A 4. ábra az OAEP diagramja jól mutatja m¶ködését.
2.5. definíció (OAEP). Az OAEP egy Feistel-típusú
𝑚
nyílt szöveget egy
𝑟
𝒫
algoritmus mely egy
véletlen szöveggel és nullákkal kiegészít, majd a nyílt
szöveget és a hozzáadott véletlen valamint
0
elemeket két véletlen orákulum
véletlen elemekkel helyettesíti, de oly módon, hogy ezután e két orákulum meghívásával visszakaphatók is legyenek az eredeti elemek. Legyen
𝑛
bithossza, és
𝑘0 a véletlen 𝑟 𝑛 − 𝑘0 − 𝑘1 bites.
bites a paddingelt szöveg hossza, ebb®l
𝑘1
a zérusok száma. Így az
𝐺 : {0, 1}𝑘0 → {0, 1}𝑛−𝑘0
és
𝑚
üzenet
szám
𝐻 : {0, 1}𝑛−𝑘0 → {0, 1}𝑘0
két véletlen orákulum (a gyakorlatban egyirányú függvények). A 𝒫 algorit𝑛−𝑘0 −𝑘1 mus bemenete az 𝑚 ∈ {0, 1} sztring, kimenete egy 𝑛-hosszú sztring,
58
az algoritmus lépései:
𝑟 ← {0, 1}𝑘0 𝑖 = 𝑚 ‖ 0𝑘1 ‖ 𝑟 𝑥 = (𝑚 ‖ 0𝑘1 ) ⊕ 𝐺(𝑟) 𝑦 = 𝑟 ⊕ 𝐻(𝑥) E
𝒫
algoritmus eredménye tehát az
(𝑥, 𝑦)
pár. Ebb®l visszanyerhet®
𝑚
és
𝑟
is az orákulumok segítségével:
𝑟 = 𝑦 ⊕ 𝐻(𝑥) 𝑚 ‖ 0𝑘1 = 𝑥 ⊕ 𝐺(𝑟) Ezután bármely egyirányú kiskapu-permutációval kombinálva az OAEP-t egy nyílt kulcsú titkosítóhoz jutunk.
2.6. definíció (Aszimmetrikus rejtjelez® (OAEP + TDP)-b®l). Legyen (𝒢 az 1.31. de níció szerinti kiskapu-permutációk egy családja.
Π = (𝒢, E, D)
TDP , 𝑓, 𝑓 −1 )
De niáljuk a
aszimmetrikus kulcsú 1.12. de níciónak megfelel® rejtjelez®t a
következ®képp: 1.
𝒢 : (𝑘, 𝑡) ← 𝒢 TDP (1𝑛 ), ahol 𝑓𝑘 és 𝑓𝑡−1 mindketten {0, 1}𝑛 → {0, 1}𝑛 függvények. 𝒢 választ egy 𝑘0 és egy 𝑘1 számot, melyekre 𝑘0 + 𝑘1 < 𝑛, 𝑘 𝑛−𝑘0 𝑛−𝑘0 valamint egy 𝐺 : {0, 1} 0 → {0, 1} és egy 𝐻 : {0, 1} → {0, 1}𝑘0 hash függvényt, és publikálja a 𝑝𝑘 = (𝑘, 𝑓𝑘 , 𝐻, 𝐺) nyílt kulcsot. A titkos −1 𝑛−𝑘0 −𝑘1 kulcs az 𝑠𝑘 = (𝑡, 𝑓𝑡 ) lesz. A nyílt szöveg 𝑚 ∈ {0, 1} .
2. Az
E
algoritmus lépései:
𝑟 ← {0, 1}𝑘0 𝑖 = 𝑚 ‖ 0𝑘1 ‖ 𝑟 𝑥 = (𝑚 ‖ 0𝑘1 ) ⊕ 𝐺(𝑟) 𝑦 = 𝑟 ⊕ 𝐻(𝑥) 𝑐 = E𝑝𝑘 (𝑚) = 𝑓𝑘 (𝑥 ‖ 𝑦) 3. A
D
algoritmus lépései:
𝑟 = 𝑦 ⊕ 𝐻(𝑥) 𝑚 ˆ = 𝑓𝑡−1 (𝑥 ⊕ 𝐺(𝑟))
59
A
D
algoritmus e ponton ellen®rzi, hogy az
𝑚 ˆ
utolsó
𝑘1
bitje valóban
0-e, ha nem, ⊥-et ad vissza, a dekódolás sikertelen, egyébként 𝑚 ˆ =𝑚‖ 0𝑘1 így E𝑠𝑘 (𝑐) megegyezik az 𝑓𝑡−1 (𝑥 ⊕ 𝐺(𝑟)) els® 𝑛 − 𝑘0 − 𝑘1 bitjéb®l álló sztringgel. Bizonyítható, hogy e rejtjelez® megfelel®
𝑘0
megválasztása mellett sze-
mantikailag biztonságos a véletlen orákulum modellben. Az ugyanakkor nem bizonyítható, hogy a választott kriptoszöveg alapú támadás ellen is biztonságos lenne.
Másrészt a gyakorlatban különösen fontos RSA esetére ez a
biztonság is bizonyítható, nevezetesen az RSA-függvényre épül® ún. RSAOAEP két független véletlen orákulum esetén bizonyos
𝑒
kitev®kre CCA-
biztonságos. Erre az RSA-ról szóló részben visszatérünk.
2.4. Hibrid rejtjelezők Az aszimmetrikus rejtjelez®k egyik komoly hátránya a szimmetrikusokkal szemben, hogy lényegesen lassabbak.
Nagyobb szöveg titkosítására ezért
praktikusabbnak t¶nik a szimmetrikus rejtjelez®k használata. A két rendszer el®nyeit ötvözik a hibrid rendszerek, amelyekben az egyirányú függvényt vagy az aszimmetrikus rejtjelez®t csak annak a kulcsnak a titkosítására és cseréjére használják, amellyel aztán az valódi üzenetet titkosítják egy szimmetrikus rejtjelez®vel. Két megoldást mutatunk, az els® csak a 2.3. konstrukció egy továbbfejlesztett változata, melyben az aszimmetrikus rejtjelez® konstrukciójának részévé válik a szimmetrikus kulcsú, míg a második megoldásban két létez® rendszert ötvözünk, egy aszimmetrikusat és egy szimmetrikusat.
2.7. konstrukció (Hibrid aszimmetrikus rejtjelez® TDP-b®l). Tekintsük a
(𝒢 TDP , 𝑓, 𝑓 −1 ) az 1.31. de níció szerinti kiskapu-permutációk egy családját. De niáljuk a Π = (𝒢, E, D) aszimmetrikus kulcsú, az 1.12. de níciónak megfelel® rejtjelez®t a következ®képp: 1.
2.
𝒢 : (𝑘, 𝑡, 𝒟𝑘 ) ← 𝒢 TDP (1𝑛 ), azaz választunk az egyirányú kiskapu-permutációk családjából egy (𝑘, 𝑡) indexpárt, és megadjuk az értelmezési tartományt. 𝒢 választ egy 𝐻 : 𝒟𝑘 → 𝒟𝑘 hash függvényt, valamint egy szimmetris s s kus kulcsú Σ = (𝒢 , E , D ) rejtjelez®t, és publikálja a 𝑝𝑘 = (𝑘, 𝑓𝑘 , 𝐻, Σ) −1 nyílt kulcsot. A titkos kulcs az 𝑠𝑘 = (𝑡, 𝑓𝑡 ) lesz. (︀ )︀ E: 𝑟 ← 𝒟𝑘 , E𝑝𝑘 (𝑚) = 𝑓𝑘 (𝑟), Es𝐻(𝑟) (𝑚) , tehát a szimmetrikus kulcsú rejtjelez® kulcsa a 𝐻(𝑟) érték lesz, ahol 𝑟 egy véletlen elem. 60
3.
D: 𝑦 = 𝐻(𝑓𝑡−1 (𝑐1 )), D𝑠𝑘 (𝑐1 , 𝑐2 ) = Ds𝑦 (𝑐2 ).
D𝑠𝑘 E𝑝𝑘 (𝑚) = 𝑚, ugyanis az üzenethez mind kó−1 doláskor, mind dekódoláskor az 𝑦 = 𝐻(𝑟) = 𝐻(𝑓𝑡 (𝑐1 ) szimmetrikus kulcsot Könnyen ellen®rizhet®, hogy használtuk. Ha valamilyen fejlett, ki nomult szimmetrikus és aszimmetrikus rejtjelez®k állnak rendelkezésünkre, egyszer¶bb, ha a kett® összeolvasztásával konstruálunk új hibrid rendszert.
2.8. konstrukció (Hibrid rejtjelez®). Legyen
Π = (𝒢 a , Ea , Da )
egy aszim-
Σ = (𝒢 s , Es , Ds ) egy szimmetrikus kulcsú rejtjelez®. Az * tetsz®leges 𝑚 ∈ {0, 1} sztring. De niáljuk a Π = (𝒢, E, D)
metrikus kulcsú, és üzenet egy
aszimmetrikus kulcsú rejtjelez®t a következ®képp: 1.
𝒢 : (𝑝𝑘, 𝑠𝑘) ← 𝒢 a (1𝑛 ),
2. Az
E
algoritmus lépései:
∙ 𝑟 ← {0, 1}𝑛 , ∙ 𝑐1 ← Ea𝑝𝑘 (𝑟), 𝑐2 ← Es𝑟 (𝑚), így 3. A
E𝑝𝑘 (𝑚) = (𝑐1 , 𝑐2 ).
D
algoritmus lépései:
∙ 𝑟 = Da𝑠𝑘 (𝑐1 ), ∙ 𝑚 = Ds𝑟 (𝑐2 ), azaz
D𝑠𝑘 (𝑐1 , 𝑐2 ) = 𝑚.
Egyszer¶ számítás mutatja, hogy elegend®en hosszú üzenet esetén a hibrid rendszer egyrészt nyújtani tudja az aszimmetrikus rendszer funkcionalitását és annak el®nyeit, másrészt a szimmetrikus rendszer hatékonyságát. Bizonyítható az is, hogy ha
Π
és
Σ
a hibrid rendszer is.
61
szemantikailag biztonságosak, akkor
3. Nyílt kulcsú rejtjelezők
3.1. RSA Az RSA a legelterjedtebb, legtöbbet vizsgált nyílt kulcsú titkosító rendszer. Ron Rivest, Adi Shamir és Leonard Adleman publikálta 1977-ben, a rendszer az ® neveik kezd®bet¶it tartalmazza.
RSA rejtjelező
A korábbiakban részletesen tárgyaltuk az RSA-függvényt,
és az egyirányúsága elleni támadásokat. Ugyancsak a korábbi fejezetek alapján könnyen készíthetünk az RSA-függvényb®l nyílt kulcsú rejtjelez®t. Most azonban el®ször egy olyan ötletet mutatunk, amely történetileg is az els® valódi aszimmetrikus kriptorendszer alapját képezte.
3.1. konstrukció (RSA véletlen paddinggel). Legyen az üzenet 1.
𝜇(𝑛)
𝑚 ∈ {0, 1}
𝜇(𝑛) < 2𝑛 − 1,
ahol
.
𝒢 : (𝑁, 𝑒, 𝑑) ← 𝒢 RSA (1𝑛 ), 𝑝𝑘 = (𝑁, 𝑒), 𝑠𝑘 = (𝑁, 𝑑).
2.
E: 𝑟 ← {0, 1}ℓ(𝑁 )−𝜇(𝑛)−1 , E𝑝𝑘 (𝑀 ) = (𝑟 ‖ 𝑚)𝑒 mod 𝑁 , * olyan, hogy (𝑟 ‖ 𝑚) ∈ Z𝑁 ,
3.
D: D𝑠𝑘 (𝑐) = (𝑐𝑑 mod 𝑁
Bár azt sejtenénk, hogy ha
utolsó
𝜇(𝑛)
ahol
𝑟
választása
bitje).
𝜇(𝑛) ≈ 𝑛, pl. 𝜇(𝑛) = 𝑐𝑛 valamilyen 𝑐 < 2 kons-
tansra, akkor a 3.1. konstrukció szemantikailag biztonságos, ezt eddig nem sikerült bizonyítani. Csak annyit tudunk, hogy ha
𝜇(𝑛) = 𝑂(log 𝑛),
akkor
a konstrukció szemantikailag biztonságos. Egy hasonló, kissé ki nomultabb
8
konstrukció került a PKCS #1 v1.5 standardba .
A biztonsága mindmáig
annak sincs bizonyítva, de miután egy ötletes kriptoszöveg alapú támadással sikerrel járt ellene Daniel Bleichenbacher, a PKCS #1 v2 standardba már a bizonyítottan biztonságos OAEP padding került, amit korábban már bemutattunk.
CCA-biztonságú RSA
A 2.3. konstrukció RSA-függvényre alkalmazott
speciális esetét kiemeljük, mint olyat, amely már CCA-biztonságú, legalábbis a véletlen orákulum modellben.
8 PKCS = Public-Key Cryptography Standards, melyeket az RSA Security Inc., ma RSA Security LLC bocsát ki és gondoz. A #1 standard maga az RSA.
62
3.2. konstrukció (RSA egy hash-függvénnyel, FergusonSchneier-RSA). Legyen
𝐻
𝐻 = SHA256 ∘ SHA2569 , és Σ = (𝒢 s , Es , Ds ) rejtjelez®. De niáljuk a Π = (𝒢, E, D) aszimmetri-
egy hash-függvény, pl.
egy szimmetrikus kulcsú
kus kulcsú rejtjelez®t a következ®képp: 1.
𝒢 : (𝑁, 𝑒, 𝑑) ← 𝒢 RSA (1𝑛 ), 𝑝𝑘 = (𝑁, 𝑒), 𝑠𝑘 = (𝑁, 𝑑), 𝑙 = ⌈log(𝑛 + 1)⌉, 𝑟 ← [0, 2𝑙 − 1], 𝑘 = 𝐻(𝑟)
2.
E: E𝑝𝑘 (𝑚) = (𝑟𝑒 mod 𝑁, Es𝑘 ),
3.
D: 𝑟 = 𝑐𝑑1 mod 𝑁 , 𝑘 = 𝐻(𝑟), D𝑠𝑘 (𝑐1 , 𝑐2 ) = D𝑘 (𝑐2 ).
Ferguson és Schneier az 𝑒 = 3 értéket javasolja digitális aláíráshoz és az 𝑒 = 3 értéket rejtjelezéshez. Ezért természetesen a gcd(3, (𝑝 − 1)(𝑞 − 1)) = 1 és a gcd(5, (𝑝 − 1)(𝑞 − 1)) = 1 feltételeknek is fönn kell állniuk. A PKCS #1 v2 standardba került RSA részletes ismertetésére itt nincs lehet®ség, de a lényege bemutatható.
Az OAEP leírásában megadott két
független hash függvény helyett a protokollban MGF (ún.
on function )
mask generati-
szerepel, ami egy fajta hash függvény, ahol az output mérete
is rugalmasan változtatható. függvényeket használnak.
Konstrukciójukhoz gyakran szabványos hash
Counter-módú konstrukciójának biztonsága bi-
zonytalan. A PKCS standardok nyelvében az oktett (octet ) egyszer¶en 8-bites bájtot jelent, az oktett sztring bájtok egymásutánját jelenti. Általában hexadecimális formában vannak megadva. Mi egyszer¶en bájtot írunk helyette. A lényeg, a standardban minden adat valahány bájtos, tehet bitben mért hossza 8-nak egész számú többszöröse.
A PKCS #1 v2.2 egy egyszer¶sí-
tett változatát megadjuk az alábbiakban. Az egyszer¶sítés abból áll, hogy a konverziós részek és a hibaüzenetek részletezését, továbbá néhány apróbb technikai részt kihagyunk vagy kissé leegyszer¶sítünk. Az RSA-ban használt OAEP-változatot az 5. ábrán szemléltetjük.
3.3. definíció (RSA-OAEP, a PKCS #1 2.2 egyszer¶sített változata). Az algoritmusban használt jelölések:
EM
az OAEP kimenete
H
hash függvény
9 A SHA256 egy 256-bites értéket adó szabványos hash függvény, mely a ma ismert legerősebbek egyike.
63
DB =
lHash
PS
01
seed
00 MGF
MGF
EM =
00
maskedSeed
maskedDB
5. ábra. Az RSA-ban használt OAEP diagramja
64
𝑚
HLen L MGF
H kimenetének hossza bájtban opcionális címke maszkot generáló függvény (változó hosszú hash)
Az üzenet egy tetsz®leges niáljuk a 1.
Π = (𝒢, E, D)
𝑚 ∈ {0, 1}8MLen
sztring (MLen bájt hosszú). De-
aszimmetrikus kulcsú rejtjelez®t a következ®képp:
𝒢 : (𝑁, 𝑒, 𝑑) ← 𝒢 RSA (1𝑛 ), 𝑝𝑘 = (𝑁, 𝑒), 𝑠𝑘 = (𝑁, 𝑑).
2. Az
E
algoritmus bemenete a
onális
𝐿
𝑝𝑘
nyílt kulcs, az
𝑚
üzenet és egy opci-
címke. Az algoritmus (a standardban RSAES-OAEP a neve)
lépései:
lHash = H(𝐿) ha 𝐿 üres, értéke el®re meg van adva PS = 00 . . . 0 összesen ℓ(𝑁 ) − MLen − 2HLen − 2 DB = lHash ‖ PS ‖ 0𝑥00 ‖ 𝑚
bájt
seed ← {0, 1}8HLen maskedDB = DB ⊕ MGF(seed, ℓ(𝑁 ) − HLen − 1) maskedSeed = seed ⊕ MGF(maskedDB, HLen) EM = 0𝑥00 ‖ maskedSeed ‖ maskedDB
E𝑝𝑘 (𝑚[, 𝐿]) = (EM)𝑒 mod 𝑁 . 3. A
D
algoritmus bemenete a
opcionális
𝐿
𝑐
kriptoszöveg, a titkos
𝑠𝑘
kulcs és az
címke. Az algoritmus lépései:
EM = 𝑐𝑑 mod 𝑁 = 𝑌 ‖ maskedSeed ‖ maskedDB seed = maskedSeed ⊕ MGF(maskedDB, HLen) DB = maskedDB ⊕ MGF(seed, ℓ(𝑁 ) − HLen − 1) = lHash’ ‖ PS ‖ 0𝑥00 ‖ 𝑚
D𝑠𝑘 (𝑐, [, 𝐿]) = 𝑚. Természetesen, ha hiányzik az 0𝑥01 bájt, ha lHash’ ̸= lHash, ha 𝑌 ̸= 00, akkor a dekódolás sikertelen. A PKCS #1 2.2 CCA-biztonságát Fujisaki, Okamoto, Pointcheval és Stern bizonyították.
Egyrészt az OAEP-re épül® nyílt kulcsú rejtjelez®k
CCA-biztonsága nem áll fenn, Shoup bizonyította, hogy ha az egyirányú
65
kiskapu-permutáció invertálása ugyan nehéz, de részlegesen nem, akkor az OEAP CCA-biztonsága nem bizonyítható. Másrészt viszont az OAEP CCAbiztonságos, ha a részleges invertálás is nehéz. Ezt sikerült az RSA esetén bizonyítani. ha egy
𝒜
Némi óvatosságra int, hogy a CCA-biztonság bizonyításában,
támadó
𝑡
id®ben
𝜀
eséllyel sikeres az RSA-OAEP ellen, akkor az 2 18 2 RSA inverz sikerének esélye 𝜀 /2 , és az algoritmus 𝑡 ideig fut. Tehát e
bizonyítás alapján elvileg nem elképzelhetetlen, hogy könnyebb támadni az RSA-OAEP ellen, mint az egyirányú RSA-függvényt invertálni. (Ez csak elvi lehet®ség, semmi jel nem mutat arra, hogy ilyen támadás létezne.)
3.2. ElGamal és ECC A Certicom nev¶ cég fontos szerepet játszik a diszkrét logaritmusra épül® kriptográ ai legf®képpen az elliptikus görbékre épül® rendszerek elméletének kidolgozásában, szabványosításában, szabadalmazásában és terjesztésében. Legalább 30 szabvány f¶z®dik a nevükhöz. A Certicom 1998-ban alapított egy
Standards for Efficient Cryptography Group (SECG)
nev¶ cso-
portot, melynek tagjai közt olyan cégek találhatóak, mint Entrust, Fujitsu, NIST, Pitney Bowes, Unisys, Visa. A diszkrét logaritmus probléma, pontosabban a Di eHellman-probléma nehézségére épül® rejtjelez®k kiindulópontja az ElGamal rendszer.
Az ElGamal rejtjelező
Taher Elgamal (nevét szokás ElGamal vagy El
Gamal formában is irni, de maga az Elgamal alakot preferálja) egyiptomi származású kriptográfus. Mindennek ellenére a róla elnevezett rejtjelez®t a széles körben elterjedt formában ElGamal-nak fogjuk írni.
3.4. konstrukció (ElGamal rejtjelez®). Legyen
𝒢 group
az 1.22. kísérletben
de niált, ciklikus csoportot generáló algoritmus. Aszimmetrikus rejtjelez®t de niálunk a következ®képp: 1.
2.
𝒢 : (𝐺, 𝑞, 𝑔) ← 𝒢 group (1𝑛 ), majd választunk egy véletlen 𝑥 ← Z𝑞 elemet, 𝑥 és kiszámoljuk ℎ = 𝑔 értékét. A nyílt kulcs 𝑝𝑘 = (𝐺, 𝑞, 𝑔, ℎ), a titkos kulcs 𝑠𝑘 = (𝐺, 𝑞, 𝑔, 𝑥). E: 𝑟 ← Z*𝑞 , 𝑚 ∈ 𝐺,
E𝑝𝑘 (𝑚) = (𝑔 𝑟 , ℎ𝑟 · 𝑚).
66
D:
3.
Jelölje
(𝑐1 , 𝑐2 )
az
E𝑝𝑘 (𝑚)
kimenetét, ekkor
D𝑠𝑘 (𝑐1 , 𝑐2 ) = Könnyen ellen®rizhet®, hogy
D𝑠𝑘 E𝑝𝑘 (𝑚) = 𝑚,
𝑐2 . 𝑐𝑥1 ugyanis
𝑐2 ℎ𝑟 · 𝑚 (𝑔 𝑥 )𝑟 · 𝑚 𝑔 𝑥𝑟 · 𝑚 = = = = 𝑚. 𝑐𝑥1 (𝑔 𝑟 )𝑥 (𝑔 𝑟 )𝑥 𝑔 𝑥𝑟 Fontos eleme e rejtjelez®nek az az egyszer¶ megoldás, hogy a nyílt szöveg meg van szorozva egy a DDH-probléma nehézsége esetén véletlennek tekinthet® elemmel. Ha pedig ′ egy tetsz®leges 𝑔 elemére
𝑔 ∈𝐺
egy véletlen elem, akkor a
P[𝑚 · 𝑔 = 𝑔 ′ ] = P[𝑔 = 𝑚−1 · 𝑔 ′ ] = vagyis itt is arról van szó, hogy ha elküldeni, akkor az
𝑚·𝑔
𝐺
csoport
1 , |𝐺|
𝑔 -t nem a rejtjelezett szöveggel együtt kéne
tökéletes biztonságot nyújtana. Így bizonyítható az
alábbi tétel:
Ha a DDH-probléma nehéz, akkor a 3.4. konstrukcióban megadott ElGamal rejtjelező szemantikailag biztonságos. 3.5. tétel.
Csoport generálása az ElGamal számára
Kérdés, hogy generálunk
olyan csoportot, amelyben könnyen találunk generátorelemet! Els® jelölt a Z*𝑝 , mely ciklikus, van hatékony algoritmus egy generátorelemének megtalálására és e csoportban a diszkrét logaritmus problémát nehéznek hisszük. Céljainknak mégsem fog e csoport megfelelni, mivel egyrészt rendje nem prím, másrészt mint azt nem nehéz belátni e csoportban a döntési Di e Hellman-probléma (DDH) nem nehéz!
Ezért másik csoport után kell néz-
nünk. Kézenfekv® megoldás lasztani.
Z*𝑝
helyett annak egy megefelel® részcsoportját vá-
Ha a kvadratikus maradékok (azaz a négyzetelemek) csoportját
választjuk, akkor egy
(𝑝 − 1)/2-elem¶
részcsoportot kapunk, mivel négyzet-
elemek szorzata és inverze is négyzetelem. Ha ráadásul azaz
𝑝 = 2𝑞 + 1
alakú, ahol
𝑞
𝑝
biztonságos prím,
is prím, akkor e csoport már prímrend¶.
Ráadásul generátorelemet is könny¶ benne találni, hisz minden egységt®l
67
* különböz® eleme generátorelem. Így elég egy 𝑟 ← Z𝑝 elemet választani, ha 2 2 𝑟 mod 𝑝 ̸= 1, akkor 𝑔 = 𝑟 mod 𝑝 egy generátorelem.
𝑝-t és 𝑞 -t úgy választjuk, hogy ℓ(𝑝) = 𝑛 + 1, ℓ(𝑞) = 𝑛. Így az üzenetek is egy 𝑞 -elem¶ halmazból vehet®k, praktikusan 𝑚 ¯ ∈ {1, 2 . . . , 𝑞}. Ezek az elemek viszont nincsenek 𝐺-ben, ezért négyzetre kell ®ket emelni. Az 𝑚 = 𝑚 ¯ 2 megfelel® lesz az algoritmus számára. Kérdés már csak az, hogy dekódolunk. Miután a D algoritmus visszaadja 𝑚-et, abból négyzetgyököt vonunk Z𝑝 -ben. A két négyzetgyök összege 𝑝, 𝑝−1 ] intervallumba. Mindenzt egy így ki tudjuk választani, melyik esik az [1, 2 A biztonsági paraméter függvényében tehát
példán szemléltetjük:
3.6. példa. Legyen
𝑝
mellett
𝑞
is
𝑝 = 359, 𝑝 = 2𝑞 +1, ahol 𝑞 = 179 (a példa szépségéért itt biztonságos prím). A Z𝑝 = Z359 csoport egy 𝑞 = 179-edrend¶
elemét megkapjuk egy tetsz®leges (egységt®l különböz®) elem négyzetre eme2 lésével, legyen a 𝐺 csoport egy generátora 𝑔 = 5 = 25. Legyen a titkos kulcs az
53 ∈ Z179 ,
így a publikus kulcs
𝑝𝑘 = (359, 179, 25, 2553 mod 359) = (359, 179, 25, 340). Legyen az üzenet az {1, 2, . . . , 179} halmaz egy eleme, mondjuk 𝑚 ¯ 2 Így 𝑚 = 103 mod 359 = 198 ∈ 𝐺. Legyen a véletlen elem 𝑟 = 138
= 103. ∈ Z179 ,
így a rejtjelezett üzenet:
(25138 mod 359, 340138 · 198 mod 359) = (187, 235). A visszafejtéshez a titkos kulcsot használva
𝑚 = 235 · 187−53 mod 359 = 198. 198
négyzetgyökei
±198
𝑝+1 4
mod 𝑝 = ±19890 mod 359 = ±256 mod 359 = {256, 103}
Mivel e két szám közül
103 < 179,
ezért
Elliptikus görbére épülő rejtjelező
103
az üzenet.
Az elliptikus görbékre épül® rejtje-
lez®k konstrukciójának használata mögött az a tény rejlik, hogy a diszkrét * logaritmus problémára a Z𝑝 -gal ellentétben nem ismeretes szubexponenciális algoritmus.
Így az ElGamal-rendszerek valamilyen változatát elliptikus
görbéken érdemes megvalósítani. Ez annyi el®nyt ad az elliptikus görbékre
68
épül® kriptográ ai rendszereknek, hogy ma ezeket tekinthetjük a leghatékonyabbnak. Az ECIES (Elliptic Curve Integrated Encryption Scheme) meglehet®sen bonyolult rendszer. Kiváló kriptográfusok alkotása, Abdalla, Bellare és Rogaway, majd Shoup munkája után nyerte el ma használt alakját. Itt most csak egy leegyszer¶sített változatát ismertetjük.
(𝑥, 𝑦) a n alak használható, azonban 𝑥-tengelyre, ezért 𝑥 ismeretében csak két 𝑦 érték jöhet szóba. Ha (𝑥, 𝑦) az egyik pontja a görbének, akkor (𝑥, 𝑝 − 𝑦) a másik, és mivel 𝑝 páratlan, ezért 𝑦 és 𝑝 − 𝑦 mindig különböz® paritású (ha nem 0). Ezért 𝑏𝑦 -nal jelölve 𝑦 paritását, a pontokat az (𝑥, 𝑦) ∈ Z𝑝 ×Z𝑝 helyett a kb. felényi (𝑥, 𝑏𝑦 ) ∈ Z𝑝 × Z2 alakban tárolhatjuk. Egy pont ilyen módon A görbe pontjainak tárolására az
tudjuk, hogy a görbe szimmetrikus az
való tömörítése nagyon egyszer¶, de a tömör alakból való visszaszámolás is egyszer¶en és hatékonyan számolható.
3.7. konstrukció (ECIES leegyszer¶sített változat). Legyen fölötti
ℰ
𝒢
egy
Z𝑝
elliptikus görbét generáló algoritmus, mely az elliptikus görbe cso-
portban talál egy
𝑞 -adrend¶ ciklikus 𝐺 részcsoportot, melyet egy 𝑃
pont által
reprezentált elem generál. Aszimmetrikus rejtjelez®t de niálunk a következ®képp: 1.
𝒢 : (ℰ, 𝑝, 𝐺, 𝑞, 𝑃 ) ← 𝒢 group (1𝑛 ), ahol ℓ(𝑞) > 𝑛. 𝑥 ← Z*𝑞 a titkos azaz 𝑠𝑘 = (𝑥). 𝑄 = 𝑥𝑃 az ℰ egy másik pontja, a publikus kulcs
kulcs,
𝑝𝑘 = (ℰ, 𝑝, 𝐺, 𝑞, 𝑃, 𝑄). 2.
E: 𝑟 ← Z*𝑞 , 𝑚 ∈ Z*𝑝 , E𝑝𝑘 (𝑚) = (𝑟𝑃, 𝑚 · 𝑥𝑟 mod 𝑝), ahol
3.
𝑟𝑄 = (𝑥𝑟 , 𝑦𝑟 ),
és
𝑥𝑟 ̸= 0.
D: Jelölje (𝑐1 , 𝑐2 ) az E𝑝𝑘 (𝑚) (𝑥𝑟 , 𝑦𝑟 ) = 𝑥 · 𝑐1 jelöléssel
kimenetét, ahol
D𝑠𝑘 (𝑐1 , 𝑐2 ) =
𝑐1 ∈ ℰ , 𝑐2 ∈ Z*𝑝 .
Ekkor az
𝑐2 mod 𝑝. 𝑥𝑟
Biztonsági szerepe nincs, hogy számolás közben a pontot tömörített vagy tömörítetlen formájában kezeljük.
69
𝒪
𝑄 = (0, 1) 6 7 8 9 10 0 1 2 3 4 5
𝑃 = (3, 8)
(𝑐) 𝑦 2 = 𝑥3 + 𝑥 + 1 14-pontú elliptikus görbe egy 7-pontú része, melyen a pontm¶velet Z7 -tel izomorf csoportot ad. A görbe 𝐺 csoporthoz nem tartozó pontjait
6. ábra. A egy
halvány színnel jelöltük.
3.8. példa. A 2. ábra harmadik görbéje
14-pontú,
csoportjának
7-elem¶
részcsoportját a (9) egyenletben megadtuk, itt felidézzük:
Z7 ∼ = 𝐺 = {𝒪, (3, 8), (6, 6), (0, 1), (0, 10), (6, 5), (3, 3)}. 𝑝 = 11, 𝑞 = 7, 𝑃 = (3, 8). Legyen a titkos kulcs 𝑠𝑘 = 3, így 𝑄 = 3𝑃 = (0, 1). Legyen az üzenet 𝑚 = 4 ∈ Z*11 . A titkosításhoz * válasszunk egy véletlen elemet: 𝑟 = 2 ∈ Z7 . Ezzel
A paraméterek tehát:
𝑟𝑃 = 2 · (3, 8) = (6, 6), tehát
𝑥𝑟 = 3,
𝑟𝑄 = 2 · (0, 1) = (3, 3),
így
(𝑟𝑃, 𝑚 · 𝑥𝑟 mod 11) = ((6, 6), 1). (𝑐1 , 𝑐2 ) = ((6, 6), 1) párt, és a titkos kulcsot, ami 3, (𝑥𝑟 , 𝑦𝑟 ) = 3 · (6, 6) = (3, 3), tehát
A dekódoláshoz vegyük a így
𝑐2 1 mod 𝑝 = mod 11 = 4 𝑥𝑟 3 4. (Ha számolás közben a pontok tömör formáját használjuk, 𝑃 = (3, 0), 𝑄 = (0, 1), 2𝑃 = (6, 0), 2𝑄 = (3, 1).)
tehát az üzenet akkor
70
3.3. Összehasonlítások Megismerve az RSA rejtjelez®t, az ElGamal rejtjelez®t, valamint annak elliptikus görbéken megvalósított változatát, egy rövid összefoglalást adunk ezek m¶ködésének hatékonyságáról. A biztonsági szint az
𝑛
biztonsági pa-
raméter értékét jelenti. A szimmetrikus kulcsú rejtjelez®k lényegében ezzel azonos, vagy esetleg néhány bittel kisebb biztonságot el tudnak érni, azaz a feltöréshez
𝑛-ben
exponenciális idej¶ algoritmus kell.
Az elliptikus gör-
békre épül® kriptorendszerek a leghatékonyabbak, az els® generációs RSA és ElGmal rendszerek csak jóval nagyobb kulcshossz esetén nyújtanak azonos biztonságot.
Ugyanakkor még ma is óvatosságból sokan döntenek az RSA
mellett, mivel a mögött már több évtizedes tapasztalatok gy¶ltek össze, az elliptikus görbe kriptográ a pedig a mögötte lév® összetettebb matematikai módszerek és fogalmak miatt nagyobb bizonytalanságban tartja a felhasználók egy részét.
Biztonsági
szimmet-
szint
rikus
ECC
RSA/DH
Meddig véd?
80
80
160
1024
2010
112
112
224
2048
2030
128
128
256
3072
2040
192
192
384
7680
2080
256
256
512
15360
2120
1. táblázat. Kulcsméretek összehasonlítása (forrás: Certicom Research, Elliptic Curve Cryptography, SEC 1, 2009-05-21, v2.0) E fejezetben a gyakorlatban ma használt két egyértelm¶en legelterjedtebb rendszerre koncentráltunk.
Megjegyzésekben azonban jeleztük, hogy mely
más megoldások lehetségesek, és hogy azok miért nem terjedtek el.
Igye-
keztünk a modern kriptográ a szemléletmódjával közelíteni a nyílt kulcsú kriptográ a e két legfontosabb példájához. Ez azt jelenti, hogy világos fogalmunk van arról, hogy e rendszerek milyen biztonsági szintet nyújtanak, és hogy azok pontosan milyen matematikai feltételek esetén állnak fenn. Megközelítésünk az volt, hogy a makacs számelméleti problémák felsorolása után a bel®lük képzett egyirányú függvények és kiskapu-permutációk segítségével általános konstrukciókat adtunk nyílt kulcsú rejtjelez®kre.
Így azt is meg
tudtuk mutatni, hogy speciálisan miért épp az RSA-függvényre épül® ma-
71
radt máig is az egyik legfontosabb rejtjelez® (pl. a mögötte lév® tapasztalat, és a bizonyított CCA-biztonsága miatt), másrészt láthattuk azt is, hogy e pillanatban az ismert matematikai támadási lehet®ségek adta keretek közt az elliptikus görbékre épül® rendszerek nyújtanak egy adott biztonsági szintet a leghatékonyabban.
72
Tárgymutató
(𝑡, 𝜀)-biztonság
17
aszimmetrikus rejtjelez® 20, 53 biztonság szemantikai 19, 21 tökéletes 16
kulcsolt 35 hash függvény 34 hibrid rejtjelez® 60 kiskapu-függvény 32 lehallgató (eavesdropper) 20
biztonságos prím 49 Merkle's puzzle 50 CCA-biztonság 22
moduláris hatványozás 8
CPA-biztonság 21
moduláris inverz 11
csoport 9 Di eHellman-problémák 28 Di eHellman hash függvény 36 Di eHellmann függvény 34
moduláris négyzetgyökvonás 26 moduláris négyzetreemelés 33 nehéz problémák 23 OAEP 57
Di e-Hellman kulcscsere 50 diszkrét logaritmus 27, 34
Rabin-probléma 26 RSA-függvény 33
ECIES 69
RSA probléma 24, 26
egyirányú függvény 31
RSA rejtjelez® 62
egyirányú kiskapufüggvény 32 egyirányú kiskapupermutáció 32
szemantikai biztonság 19, 21
ElGamal rejtjelez® 66
szimmetrikus rejtjelez® 15
elhanyagolható függvény 18 elliptikus görbe pontm¶velet 45 elliptikus görbék 42 er®s prím 49 faktorizáció 24 félcsoport 9 op, ops 17
TDF 32 TDP 32 tökéletes biztonság 16 ütközésálló 35 vakítás 40 véletlen orákulum 54
gy¶r¶ 10 hash függvény
73
