RSA algoritmus 1. Vegyünk véletlenszer˝uen két különböz˝o nagy prímszámot, p-t és q-t. 2. Legyen n = pq. 3. Vegyünk egy olyan kis páratlan e számot, amely relatív prím φ(n) = (p − 1)(q − 1)-hez. 4. Keressünk egy olyan d számot, amelyre ed = 1 mod φ(n). 5. Az RSA nyilvános kulcs a P = (e, n) pár lesz. 6. Az RSA titkos kulcs az S = (d, n) pár lesz. Ebben a sémában az elküldhet˝o üzenetek halmaza Zn = {0, 1, . . . , n−1}. A kódolás a P = (e, n) nyilvános kulccsal: P(M) = M e
mod n.
S(C) = Cd
mod n.
A dekódolás a titkos kulccsal:
A helyesség igazoláshoz szükséges számelméleti háttér Def: Zn∗ = {a ∈ Zn : lnko(a, n) = 1}. Def: Az Euler függvény a Zn∗ halmaz elemszáma, jele φ(n), értéke φ(n) = n ∏(1 − 1/p), p|n
ahol p prím. Tétel (Euler) Bármely n > 1 számra aφ(n) = 1
mod n,
a p−1 = 1
mod p,
minden a ∈ Zn∗ esetén. Tétel (Fermat) Minden p prímre
ha p nem osztója a-nak. Tétel (Kínai maradéktétel) Legyen n = n1 n2 . . . nk , ahol ni -k páronként relatív prímek. Tekintsük az a ∼ (a1 , a2 , . . . , ak ), megfeleltetést, ahol a ∈ Zn , és ai ∈ Zni , továbbá ai = a mod ni minden i = 1, 2, . . . , k-ra. A megfeleltetés kölcsönösen egyértelm˝u megfeleltetés a Zn halmaz és a Zn1 × Zn2 · · · × Znk direktszorzat között. A Zn elemein végezhet˝o m˝uveletek végrehajthatók a k-asokkal. Tehát, ha a ∼ (a1 , a2 , . . . , ak ) és b ∼ (b1 , b2 , . . . , bk ), akkor (a + b) mod n ∼ ((a1 + b1 ) mod n1 , . . . , (ak + bk ) mod nk ) (a − b) mod n ∼ ((a1 − b1 ) mod n1 , . . . , (ak − bk ) mod nk ) 1
(ab) mod n ∼ ((a1 b1 ) mod n1 , . . . , (ak bk ) mod nk ) Következmény Ha n1 , n2 , . . . , nk páronként relatív prímek és n = n1 n2 . . . nk , akkor minden a1 , a2 , . . . , ak , egész számra az x = ai
mod ni ,
i = 1, 2, . . . , k, kongruenciarendszernek modulo n az x ismeretlenre egyetlen megoldása van. Következmény Ha n1 , n2 , . . . , nk páronként relatív prímek és n = n1 n2 . . . nk , akkor az x és a egészekre x = a mod ni minden i = 1, 2, . . . , k-ra akkor és csak akkor teljesül, ha x = a mod n. Példa: Legyen n = 65, akkor n1 = 5 és n2 = 13. Ha a = 42 ∼ (2, 3) és b = 24 ∼ (4, 11) , akkor a + b = 1 ∼ (1, 1). RSA helyessége Tétel. (Az RSA helyessége.) Az RSA algoritmusban definiált függvények egymás inverzei. Bizonyítás. M ∈ Zn esetén P(S(M)) = S(P(M)) = M ed
mod n.
Mivel e és d egymás multiplikatív inverzei modulo φ(n) = (p − 1)(q − 1), ezért ed = 1 + k(p − 1)(q − 1), valamely alkalmas k egész számra. Ekkor M 6= 0 mod p esetén M ed = M(M p−1 )k(q−1)
mod p = M(1)k(q−1)
mod p
a Fermat tétel alapján. Tehát M ed = M mod p ha M 6= 0 mod p. Következésképpen M ed = M mod p teljesül. Hasonlóképpen kapjuk, hogy M ed = M mod q. Így a kínai maradéktétel következménye miatt, mivel n = pq ezért M ed = M mod n.
2
Lineáris kongruencia megoldása Az e elem inverzének megtalálásához meg kell oldanunk egy lineáris kongruenciát. Általánosan a feladat az, hogy oldjuk meg az ax = b mod n egyenletet. Jelölje G(a) az a elem által generált additív részcsoportját Zn -nek. Tehát G(a) = {ax
mod n : x > 0}.
A megoldandó kongruenciának akkor és csak akkor van megoldása, ha b ∈ G(a). Tétel. Legyen d = lnko(a, n). Ekkor G(a) = G(d) = {0, d, 2d, . . . , ((n/d) − 1)d}, így |G(a)| = n/d. Bizonyítás El˝oször igazoljuk, hogy d ∈ G(a). A B˝ovített-Euklidesz algoritmus olyan x és y számokat ad, amelyekre ax + ny = d, így ax = d mod n, azaz d ∈ G(a). Így d többszörösei is szerepelnek G(a)-ban, tehát G(d) ⊆ G(a). Belátjuk, hogy G(a) ⊆ G(d) is teljesül. Ha m ∈ G(a), akkor m = ax mod n valamely x-re, ezért m = ax + ny. De d|a és d|n, így adódik, hogy d|m, azaz m ∈ G(d). Következmény: Az ax = b mod n kongruencia akkor és csak akkor oldható meg, ha lnko(a, n)|b teljesül. Ha van megoldás, akkor pontosan d darab van. Tétel Legyen d = lnko(a, n) = ax0 + ny0 . Ha d|b, akkor az ax = b mod n kongruenciának az egyik megoldása x0 , amelyre: x0 = x0 (b/d) mod n. Bizonyítás: ax0 = ax0 (b/d) mod n = d(b/d) mod n = b
mod n.
Tétel: Legyen d = lnko(a, b). Tegyük fel, hogy az ax = b mod n kongruencia megoldható és x0 egy megoldása. Ekkor pontosan d különböz˝o megoldása van, az xi = x0 + i(n/d) i = 0, 1, . . . , d − 1 megoldások. Bizonyítás: Mivel n/d > 0 és 0 ≤ i(n/d) < n, i = 0, 1, . . . , d − 1-re, ezért az xi -k mind különböz˝ok mod n-re. Mivel x0 megoldás, ezért ax0 mod n = b. Ekkor az i = 0, 1, . . . , d − 1-re axi
mod n = a(x0 + in/d) mod n = (ax0 + ain/d) mod n = ax0
LINEÁRIS-KONGRUENCIA-MEGOLDÓ(A,B,N) (d,x0,y0):=B˝ ovített-Euklidesz(a,n) if d|b then x0:=x0(b/d) mod n for i := 0 to d-1 print(x0+i(n/d) mod n) else print(nincs megoldás) Példa 14x = 30
mod 100.
(d, x, y) = 2, −7, 1) , x0 = (−7)(15) mod 100 = 95, így a két megoldás 95 és 45. Prímtesztelés 3
mod n = b.
További kérdés miként találhatunk nagy prímeket. Ismert, hogy végtelen sok prím van, így tetsz˝olegesen nagy prím található. Továbbá a prímek nem helyezkednek el nagyon ritkán, ha π(n) jelöli az n-nél nem nagyobb prímek számát, akkor limn→∞ ln nπ(n)/n = 1. A prímek kereséséhez fontos részfeladat a prímtesztelés, amely során adott számról akarjuk eldönteni prím -e? √ A legegyszer˝ubb módszer az osztási próba. Az n számot rendre elosztjuk a 2, 3, 5, b nc egészek mindegyikével, ha valahol egész számot kapunk, akkor n összetett. Az algoritmus lassú, mivel az input mérete nem n, hanem log n. A továbbiakban olyan módszereket mutatunk be, amelyek nem feltétlenül adnak helyes választ. Ha azt kapjuk válaszként, hogy az adott szám összetett, akkor valóban összetett számról van szó, de a pozitív válasz nem garantálja, hogy valóban prímr˝ol van szó. Álprímek és Carmichael számok A Fermat tétel alapján, minden prímre és minden a = 1, . . . , p − 1-re a p−1 = 1 mod p. Az els˝o prímtesztel˝o algoritmus kiszámolja az MODULÁRIS-HATVÁNYOZÓ(2,n-1,n) értéket, és ha nem 1-et kapunk, akkor tudjuk, hogy n összetett szám. Az algoritmus, akkor hibázik, ha n olyan összetett szám, amelyre 2n−1 = 1 mod n. Általában azokat az összetett számokat, amelyekre an−1 = 1 mod n a alapú álprímnek nevezzük. Egy n számot a alapú álprímnek nevezünk, ha an−1 = 1 mod n. Természetesen adódik a kérdés, hogy milyen gyakran téved az algoritmus, azaz milyen gyakran fordulnak el˝o 2 alapú álprímek. 1000-nél kisebb 2 alapú álprím 22 van, az álprímek aránya tart a 0-hoz. Kézenfekv˝o ötlet, hogy használjunk a teszteléshez a 2 számon kívül más alapokat is. Ez nem oldja meg a problémát, mert vannak olyan számok, amelyek minden a-ra a alapú álprímek. Ezeket a számokat nevezzük Carmichael számoknak. Ezekb˝ol még kevesebb van, 109 -nél kisebb Carmichael szám 255 van, a legkisebb az 561. Miller Rabin valószínuségi ˝ prímteszt A prímteszt két lépésb˝ol áll, egyrészt véletlenül választott a értékekre ellen˝orzi, hogy a vizsgált szám a alapú álprím-e, továbbá megvizsgálja, hogy van -e nemtriviális négyzetgyöke 1-nek modulo n. A második részbeli elutasítás helyessége az alábbi tételen alpul. Tétel Ha p páratlan prím, akkor az x2 = 1 mod p kongruenciának, csak 2 megoldása van, az x = 1 és az x = −1. def: Az x szám 1 nem triviális négyzetgyöke modulo n, ha megoldása az x2 = 1 mod n kongruenciának, és nem egyezik meg a triviális −1, 1 négyzetgyökökkel. (Pl a 6 nem triviális négyzetgyöke 1-nek, modulo 35.) Következmény Ha az 1-nek létezik nemtriviális négyzetgyöke modulo n, akkor az n összetett szám. A prímteszt használja a következ˝o TANÚ(a,n) algoritmust. Ehhez legyen n − 1 = 2t u, ahol t ≥ 1 és u páratlan. TANÚ(a,n) x(0):=MODULÁRIS-HATVÁNYOZÓ(a,u,n) for i=1 to t x(i):=(x(i-1))(x(i-1)) mod n if x(i)=1 and x(i-1)!=1 and x(i-1)!=n-1 then return Igaz if x(t)!=1 then return igaz return hamis Lemma. Ha a TANÚ(a,n) eljárás Igaz értéket ad vissza, akkor az n szám összetett. Bizonyítás. Két esetben kaphatunk Igaz értéket, ha x(i − 1) nem triviális négyzetgyöke 1-nek modulo n, vagy ha nem teljesül n-re a Fermat tétel. Mindkét esetben egyb˝ol adódik, hogy n nem lehet prím.
4
Miller-Rabin(n,s) for j=1 to s a:=VeletlenGeneralt(1,n-1) If TANÚ(a,n) Then return ÖSSZETETT return PRÍM(Valószín˝ uleg) Tétel Az n páratlan összetett számnak legalább (n − 1)/2 darab összetettséget igazoló tanúja van. Következmény Legyen n > 2 páratlan egész, s pedig pozitív egész. A Miller-Rabin(n,s) teszt tévedési valószín˝usége legfeljebb 2−s . Bizonyítás A fenti tétel alapján ha n nem prím, akkor a Miller-Rabin(n,s) teszt minden iterációja 1/2 valószín˝uséggel felfedez egy tanút. Így annak a valószín˝usége, hogy s lépésben nem találunk egyetlen tanút sem, kisebb, mint 2−s . Példa: Legyen n = 561 a legkisebb Carmichael szám. Ekkor n − 1 = 24 · 35. Legyen a = 7, ekkor els˝oként kiszámoljuk az x(0) = 735 = 241 mod 561 értéket, majd ezt többször négyzetre emelve a (298, 166, 67, 1) sorozatot, amely utolsó el˝otti eleme talált egy nemtriviális négyzetgyökét 1-nek modulo 561. Mersenne prímek Def: Mersenne-prímnek nevezzük a kett˝o-hatványnál eggyel kisebb, azaz a 2n −1 alakban felírható prímszámokat, ahol n szintén prímszám. 2008-ban fedezték fel a 45-ödik Mersenne-prímet, ez a 243112609 -1 szám, amely 12 978 189 számjegy˝u. Ez a jelenleg ismert legnagyobb prímszám.
5
