N17

17.

Nyilvános kulcsú titkosítás

Legyen a titkosítandó üzenetek halmaza. Tegyük fel, hogy Bob titkosítottan szeretné elküldeni Aliznak az M ∈ üzenetet. A nyilvános kulcsú titkosítás esetén Aliznak van egy SA titkos és egy PA nyilvános kulcsa, továbbá van egy K :→0 , D :0 → függvénypár (a kódoló és dekódoló függvények), amelyekre teljesül, hogy D(SA , K(PA , M)) = M Tehát adott PA nyilvános kulcsra a PA (M) = K(PA , M) függvénynek az SA titkos kulcsra vet SA (C) = D(SA ,C) függvény az inverze. (És fordítva is igaz, ha 0 ⊆). Digitális aláírás Bob

Aliz C = PA(M)

PA

M

M = SA(C)

SA

csatorna

Kódolás

Dekódolás

1. ábra.

SA M

σ = SA(M)

σ (M, σ)

PA M

PA(σ) M = PA(σ)?

2. ábra.

17.1.

Az RSA nyilvános kulcsú titkosítás (Rivest, Shamir és Adleman)

1. Ki kell választani véletlenszer˝uen két nagy prímszámot, p-t és q-t (p 6= q). 2. Ki kell számítani az n = p q értéket. 3. Választani kell egy olyan kis páratlan e számot, amely relatív prím φ(n) = (p − 1)(q − 1)-hez. 4. Ki kell számítani azt a d számot, amelyre e d ≡ 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 = Zn = {0, 1, . . . , n − 1}. A kódolás a P = (e, n) nyilvános kulccsal: P(M) = M e ( mod n)

(1)

S(C) = Cd ( mod n)

(2)

A dekódolás a titkos kulccsal:

17.1. tétel. (Az RSA helyessége.) Az (1) és (2) egyenletek által definiált függvények egymás inverzei.

Bizonyítás. M ∈ Zn esetén

P(S(M)) = S(P(M)) = M e d ( mod n)

Mivel e és d egymás multiplikatív inverzei modulo φ(n) = (p − 1)(q − 1), ezért e d = 1 + k(p − 1)(q − 1) 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) ≡ M ( mod p) .

(Fermat tétel miatt)

M ≡ 0 ( mod p) esetén Me d ≡ M teljesül minden e d-re. Hasonlóképpen kapjuk, hogy M ed ≡ M ( mod q) A kínai maradéktétel következménye miatt, mivel n = pq M ed ≡ M ( mod n) 

A bizonyítás során felhasznált tételek: 17.2. tétel. (Euler tétel) Bármely n > 1 számra aφ(n) ≡ 1 ( mod n) minden a ∈ Z∗n elemre. 17.3. tétel. (Fermat-tétel) Ha p prím, akkor a p−1 ≡ 1 ( mod p) minden a ∈ Z∗p elemre. Ahol Z∗n = {a ∈ Zn : lnko(a, n) = 1}. A φ Euler függvényre, amely definíció szerint a Z∗n halmaz elemszáma   1 φ(n) = n ∏ 1 − p p |n ahol p befutja n összes prímosztóját. 17.4. tétel. (Kínai maradéktétel) Legyen n = n1 n2 · · · nk , ahol ni páronként relatív prímszám. Tekintsük a a ↔ (a1 , a2 , . . . , ak ) ,

(3)

megfeleltetést, ahol a ∈ Zn , ai ∈ Zni , és ai = a mod ni minden i = 1, 2, . . . , k-re. A megfeleltetés kölcsönösen egyértelm˝u megfeleltetés a Zn halmaz és a Zn1 × Zn2 × · · · × Znk direktszorzat között. Zn elemein végezhet˝o m˝uveletek végrehajthatók a k-asokkal. Tehát, ha a ↔ (a1 , a2 , . . . , ak ) , 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 ) , (ab) mod n ↔ (a1 b1 mod n1 , . . . , ak bk mod nk ) . 17.5. következmény. Ha n1 , n2 , . . . , nk páronként leratív prím é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. 17.6. 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) . Az RSA titkosításhoz az alábbi m˝uveletek algoritmusára van szükség. Lineáris kongruencia megoldása: (Általánosan a x ≡ b mod n) a x ≡ 1 mod n Moduláris hatványozás: ab mod n kiszámítása. M ODULÁRIS - HATVÁNYOZÓ ( A , B , N ) c := 0; d := 1; legyen hbk , bk−1 , . . . , b1 , b0 i b bináris alakja; for i := k downto 0 do begin c := 2 ∗ c; d := (d ∗ d) mod n; if bi = 1 then begin c := c + 1; d := (d ∗ a) mod n end end

Ciklusinvariáns: 1. A c változó értéke megegyezik b bináris ábrázolásából a hbk , bk−1 . . . , bi+1 i kezd˝oszeletével. 2. d = ac mod n Kezdetben: i = k, c = 0, így d = 1 = a0 mod n. Megmarad: Jelölje c0 és d 0 a c ill. d változók értékét a for ciklusmag után. Minden ismétlés után c0 := 2 ∗ c, ha bi = 0, vagy c0 := 2 ∗ c + 1, ha bi = 1, tehát c értéke helyes. Ha bi = 0, akkor d 0 = d 2 mod n = (ac )2 mod n = a2c 0 0 mod n = ac mod n. Ha bi = 1, akkor d 0 = d 2 a mod n = (ac )2 a mod n = a2c+1 mod n = ac mod n. Befejez˝odik: A ciklus befejez˝odése után c = b, d = ac mod n = ab mod n. Az algoritmus futási ideje: ha a, b és n bináris ábrázolásához β bit kell, akkor O(β) aritmetikai m˝uvelet és O(β3 ) bitm˝uveletet hajt végre az algoritmus. Hatványozás: ab kiszámítása b = bk 2k + · · · + b1 21 + b0 k +···+b

ab = abk 2

1 +b

12

0

∏ a2

i

=

bi 6=0 i

i

i

i+1

a2 ∗ a2 = a2∗2 = a2 /*Hatványozás */ static long Hatv(int a, int b){ long e=(b%2==1)? a:1; long a2=a;//2-hatványok b>>=1; while (b>0){ a2*=a2; if (b%2==1) e*=a2; b>>=1; } return e; } /* Moduláris hatványozás */ static long ModHatv(int a, int b, int n){ long e=(b%2==1) ? a%n:1; long a2=a; //2-hatványok mod n: a^(2^i) mod n b>>=1; while (b>0){ a2=(a2*a2) % n; if (b % 2==1) e=(e*a2) % n; b>>=1; } return e; } Az Euklideszi algoritmus LNKO kiszámítására. Az osztók tulajdonságai:

d|a és d|b ⇒ d|(a + b) és d|(a − b) .

(4)

d|a és d|b ⇒ d|s(ax + by)

(5)

Minden x and y egészre. Továbbá ha a|b, akkor |a| ≤ |b| vagy b = 0, tehát a|b és b|a ⇒ a = ±b .

lnko(a, b) lnko(a, b) lnko(a, b) lnko(a, 0) lnko(a, ka)

= = = = =

lnko(b, a) , lnko(−a, b) , lnko(|a|, |b|) , |a| , |a| minden k ∈ Z

(6)

(7) (8) (9) (10) (11)

17.7. tétel. Ha a és b valamelyike nem 0, akkor lnko(a, b) a {ax + by : x, y ∈ Z} halmaz legkisebb pozitív eleme. Bizonyítás. Legyen s = ax + by a legkisebb pozitív szám, x, y ∈ Z. Legyen továbbá q = ba/sc. Ekkor a mod s = a − qs = a − q(ax + by) = a (1 − qx) + b (−qy) , vagyis a mod s szintén az a és b lineáris kombinációja. De 0 ≤ a mod s < s , tehát a mod s = 0, hiszen s a legkisebb ilyen. Emiatt s|a, és hasonlóan s|b, tehát lnko(a, b) ≥ s. Ugyanakkor lnko(a, b)|s, mivel lnko(a, b) osztja a és b mindegyikét és s lineáris kombinációja a,b-nek. De lnko(a, b)|s és s > 0, ezért lnko(a, b) ≤ s. lnko(a, b) ≥ s és lnko(a, b) ≤ s ⇒ lnko(a, b) = s.  E UKLIDESZ ( A , B ) if b = 0 then Euklidesz:=a else Euklidesz:= Euklidesz(b, a mod b) static long LNKO(long a, long b){ long m; while (b>0){ m=a % b; a=b; b=m; } return a; } 17.8. lemma. Ha a > b ≥ 1 és az E UKLIDESZ ( A , B ) futása k iterációt végez, akkor a ≥ Fk+2 és b ≥ Fk+1 . Bizonyítás. k = 1-re nyilvánvaló. Indukciós feltevés szerint legyen igaz a lemma k − 1-re. Mivel k > 0, így b > 0, tehát lesz rekurzív hívás. Az ind. feltevés szerint b ≥ Fk+1 . Mivel a > b ≥ 1 ezért ba/bc ≥ 1, így b + (a mod b) = b + (a − ba/bcb) ≤ a

ahonnan a ≥ b + (a mod b) ≥ Fk+1 + Fk = Fk+2 . 

17.9. tétel. (Lame) Minden k-ra, ha a > b ≥ 1 és b ≥ Fk+1 , akkor E UKLIDESZ ( A , B ) k-nál kevesebb iterációt végez. Tehát E UKLIDESZ ( A , B ) futási ideje O(lg b). Az Euklidesi algoritmus b˝ovített változata. Olyan x és y együtthatók kiszámítása, amelyekre d = lnko(a, b) = ax + by A (d, x, y) hármas kiszámítása: ˝ B OVÍTETT -E UKLIDESZ ( A , B ) if b = 0 then return (a,1,0) (d,0 , x0 , y0 ):=B˝ovített-Euklidesz(b, a mod b); (d, x, y) := (d 0 , y0 , x0 − ba/bcy0 ) return (d,x,y) Ha b = 0, akkor x = 1 és y = 0 valóban megoldás, mert a = ax + by. Ha b 6= 0, akkor el˝obb a (d,0 , x0 , y0 ) hármast számítja ki, ahol d 0 = lnko(b, a mod b) és d 0 = bx0 + (a mod b)y0 ahogy az Euklideszi algoritmusnál, itt is d = lnko(a, b) = d 0 = lnko(b, a mod b). Ezt felhasználva d = bx0 + (a − ba/bcb)y0 = ay0 + b(x0 − ba/bcy0 ) így az x = y0 és y = x0 − ba/bcy0 választások kielégítik a d = ax + by egyenletet. Nemrekurzív megvalósítás public static long[] BLNKO(long x, long y) { long[] u = {y, 0, 1}, v = {x, 1, 0}, t = new long[3]; while (v[0] != 0) { long q = u[0]/v[0]; for (int i = 0; i < 3; i++) { t[i] = u[i] - v[i]*q; u[i] = v[i]; v[i] = t[i]; } } return u; }

Lineáris kongruenciák megoldása. ax ≡ b ( mod n) egyenlet megoldása a célunk. Jelölje hai az a elem által generált részcsoportját Zn -nek. Tehát hai = {a(x) : x > 0} = {ax mod n : x > 0} Tehát a megoldandó kongruenciának akkor és csak akkor van megoldása, ha b ∈ hai. 17.10. tétel. Legyen d = lnko(a, n). Ekkor hai = hdi = {0, d, 2d, . . . , ((n/d) − 1)d} és így |hai| = n/d. Bizonyítás. El˝oször belátjuk, hogy d ∈ hai. A B˝ovített-Euklidesz(a,n) algoritmus olyan x0 és y0 -t állít el˝o, amelyekre ax0 + ny0 = d, emiatt ax0 ≡ d( mod n), vagyis d ∈ hai. De d többszörösei is benne vannak hai-ban, így hdi ⊆ hai. Belátjuk, hogy hai ⊆ hdi is áll. Ha m ∈ hai, akkor m = ax mod n v.m. x-re, ezért m = ax + ny teljesül v.m. y-ra. De d|a és d|n- b˝ol következik, hogy d|m, azaz m ∈ hdi  17.11. következmény. Az ax ≡ b( mod n) akkor és csak akkor oldható meg, ha lnko(a, n)|b. 17.12. következmény. Az ax ≡ b( mod n) kongruenciának vagy d különböz˝o megoldása van, vagy nincs megoldása. 17.13. tétel. Legyen d = lnko(a, b). Ekkor hai = hdi = {0, d, ((n/d) − 1)d} Legyen d = lnko(a, n) = ax0 + ny0 . Ha d|b, akkor az ax ≡ b( mod n) kongruenciának az egyik megoldása x0 : x0 = x0 (b/d) mod n . Bizonyítás. Mivel ax0 ≡ ax0 (b/d) mod n ≡ d(b/d) mod n ≡ b mod n

(mivel ax0 ≡ d

mod n)



17.14. tétel. Legyen d = lnko(a, b). Tegyük fel, hogy a ax ≡ b( mod n) kongruencia megoldható és x0 egy megoldása. Ekkor pontosan d különböz˝o megoldása van, éspedig xi = x0 + i(n/d) i = 0, 1, . . . , d − 1.

Bizonyítás. Mivel n/d > 0 és 0 ≤ i(n/d) < n i = 0, 1, . . . , d − 1-re, ezért 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 mod n (mivel d|a) b 

L INEÁRIS - KONGRUENCIA - MEGOLDÓ ( A , B , N ) (d, x0 , y0 ):=B˝ovített-Euklidesz(a, n); if d|b then begin x0 := x0 (b/d) mod n; for i := 0 to d-1 do print(x0 + i(n/d) mod n); end else print(nincs megoldás);

public static void LKM(long a, long b, long n){ long[] t=BLNKO(a,n); if (b % t[0]==0){ long x0=t[1]*(b/t[0]) % n; for (int i=0; i