Indetemininisztikus algoritmus implementációja és az RSA tikositás 13_A osztály

Máig feltörhetetlen az RSA titkosítás, mert prímszámokat használ egy asszimetrikus kódolás során. Meghatározni egy számról hogy mely prímszámok szorzata megoldhatatalan feladat mamég.  A prímteszt az informatikában olyan determinisztikus algoritmust takar, ami véges sok lépésben el tudjuk dönteni, egy számról, hogy prímszám-e. Egy nagyon primitív pszeudokód formájában a következőképp „algoritmizálhatjuk” ezt:

    1). legyen s=2; és olvassuk be a tesztelendő n egész számot,

    2). ha n=0 vagy n=1, akkor sem nem prím, sem nem összetett; STOP; ha n>2, menjünk 3).-ra

    3). Képezzük az m=<n mod s> maradékot; ha ez 0 és m<n, akkor n nem prím, STOP; ha m=n, akkor n prím, STOP; ha pedig az előző esetek egyike sem teljesül, ekkor tehát m<n és m nem nulla, legyen s=s+1, és menjünk 3).-ra.

Nem kell a számnál kisebb összes természetes egésszel osztunk, hanem nyilván elegendő ezt csak a nála kisebb prímekkel megtenni. Ehhez készíteni kell egy prímszámtáblázatot, ami például az eratoszthenészi szita módszerén vagy más szitálási eljárásokon alapulhat. A számokat elég a négyzetgyökükig vizsgálni, hiszen a szorzás kommutatív művelet.
Mindegy milyen programozási nyelven kezdünk hozzá a probléma megoldásához, ugyanazt az eredményt kapjuk.

A Wilson-tesztet kihagyom mert zsákutca, mivel az n>1 szám csak akkor prím, ha n|(n-1)!+1.

mivel az n! faktoriális függvényt kellene számolni, eleve kudarcra van ítélve.

A  Fermat-tesztnél ha p prím akkor a p − a {\displaystyle a^{p}-a} {\displaystyle a^{p}-a} osztható p-vel, ahol p nem osztója a-nak.

A Solovay–Strassen-tesztnél egy adott páratlan n számról a következőképpen döntjük el, hogy prím-e: választunk véletlenszerűen egy 0<b<n egész számot. Ezután kiszámítjuk az euklideszi algoritmus segítségével a (b, n) legnagyobb közös osztót. Ha ez egynél nagyobb, akkor készen vagyunk: n összetett szám. Ha nem, akkor kiszámítjuk egyrészt b n − 1 2 {\displaystyle b^{\frac {n-1}{2}}} {\displaystyle b^{\frac {n-1}{2}}} n-nel vett legkisebb abszolút értékű maradékát, másrészt a : ( b n ) {\displaystyle \left({\frac {b}{n}}\right)} {\displaystyle \left({\frac {b}{n}}\right)} Jacobi-szimbólum értékét. Ha n prím, akkor a két értéknek, az Euler-kritérium értelmében, meg kell egyezni.

Fontos megjegyezni, hogy noha a Jacobi-szimbólum n prímfelbontása segítségével van definiálva, értéke anélkül is gyorsan kiszámítható. Ha n összetett, akkor legfeljebb 1/2 annak a valószínűsége, hogy véletlen b-re ez a két érték megegyezik. Ezért sokszor ismételjük a fenti próbát véletlenszerűen választott b értékekkel. Ha a két szám akár csak egyszer is eltér, akkor biztosak lehetünk benne, hogy n összetett. Ha viszont mindig megegyeznek, akkor igen nagy valószínűséggel prím.

A Miller–Rabin-tesztnél legyen n a tesztelendő páratlan szám, n − 1 = 2 s t {\displaystyle n-1=2^{s}t} {\displaystyle n-1=2^{s}t}, t páratlan. Legyen 0<b<n.

        b t ≡ 1 ( mod n ) {\displaystyle b^{t}\equiv 1{\pmod {n}}} {\displaystyle b^{t}\equiv 1{\pmod {n}}} vagy van olyan 0 ≤ r < s {\displaystyle 0\leq r<s} {\displaystyle 0\leq r<s}, hogy b 2 r t ≡ − 1 ( mod n ) {\displaystyle b^{2^{r}t}\equiv -1{\pmod {n}}} {\displaystyle b^{2^{r}t}\equiv -1{\pmod {n}}}.

Ha n prímszám, akkor a fenti állítás minden b-re teljesül; ha n összetett, akkor ez legfeljebb a b-k egynegyedére igaz. Ezért véletlenszerűen választunk b értékeket, és ha mondjuk 100 egymásutáni választásra igaz a fenti állítás, akkor n nagy valószínűséggel prím.

A BPSW-teszt nem megbízható hagyjuk.

Az AKS-algoritmusnál, legyen n ≥ 2 {\displaystyle n\geq 2} {\displaystyle n\geq 2} természetes szám, r olyan n-nél kisebb természetes szám, hogy n rendje r-rel osztva nagyobb, mint ( l o g 10 {\displaystyle log_{10}} {\displaystyle log_{10}} n)2. n pontosan akkor prím, ha:

    1. n nem teljes hatvány,

    2. n-nek nincs prímtényezője, ami ≤ r {\displaystyle \leq r} {\displaystyle \leq r},

    3. ( x + a ) n ≡ x n + a ( mod ( n , x r − 1 ) ) {\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {(n,x^{r}-1)}}} {\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {(n,x^{r}-1)}}}teljesül minden 1 ≤ a ≤ r log ⁡ n {\displaystyle 1\leq a\leq {\sqrt {r}}\log n} {\displaystyle 1\leq a\leq {\sqrt {r}}\log n}egész számra.

És végül a Pepin-teszt, ahol speciális alakú számokra vannak speciális prímtesztek. Például, ha N = 2 2 n + 1 {\displaystyle N=2^{2^{n}}+1} {\displaystyle N=2^{2^{n}}+1} alakú Fermat-szám (n≥ 1), úgy N prím pontosan akkor, ha

    3 N − 1 2 ≡ − 1 ( mod N ) . {\displaystyle 3^{\frac {N-1}{2}}\equiv -1{\pmod {N}}.} {\displaystyle 3^{\frac {N-1}{2}}\equiv -1{\pmod {N}}.}

Nézzük az RSA algoritmust és a Miller-Rabin teszetet. Legyenek p és q különböző prímszámok, azaz olyan természetes számok, amelyeknek 1-en és önmagukon kívül nincs más osztójuk. Prímszámok például a 2,3,5,7,… Az ókori görög matematikus Eukleidész Elemek című könyvében szerepel annak bizonyítása, hogy végtelen sok prímszám létezik. A XIX. sz. vége óta azt is tudjuk, hogy a prímszámok elég gyakoriak. Annak a valószínűsége ugyanis, hogy egy véletlenszerűen kiválasztott x-nél kisebb szám prímszám legyen 1/ln x. A Miller-Rabin teszttel gyorsan eldönthető, hogy egy szám prímszám-e. (Pontosabban, ha egy szám átmegy a Miller-Rabin teszten, akkor csak azt mondhatjuk, hogy nagy valószínűséggel prímszám.Nagy prímszámokat tehát könnyű találni, de ha két ilyet összeszorzunk, akkor csak a szorzatot ismerve nagyon nehéz a tényezőket megtalálni. Ezt a faktorizáció problémájának nevezik, ami tudásunk szerint egy nagyon nehéz algoritmikus probléma, és még ma is komoly kihívást jelent nekünk. Legyenek p és q különböző prímszámok és n=qp. Ekkor az n-nél kisebb, n-hez relatív prím természetes számok száma φ(n) = (p-1)(q-1). Ezt az értéket p és q ismeretében könnyű kiszámítani. A φ függvényt Euler függvénynek nevezzük. Legyen most e egy olyan φ(n)-hez relatív prím természetes szám, amelyik kisebb φ(n)-nél. Akkor pontosan egy olyan 1 <= d < φ(n) természetes szám létezik, amelyre ed mod φ(n) = 1. Itt és a továbbiakban a mod m jelenti az a természetes szám maradékát m-mel osztva. Ezek után a nyilvános kulcs az e,n számpáros, a titkos kulcs pedig a d szám. A kulcsok meghatározása után a p és q értékét is titokban kell tartani vagy ezeket a számokat meg kell semmisíteni. A kódolás során az üzenetet először számok sorozatává alakítjuk olyan módon, hogy a számok mindegyike kisebb legyen, mint n. Ez könnyen megtehető, hiszen az üzenetet a számítógépben bináris alakban tároljuk és most ezt a bináris sorozatot, mint egy kettes számrendszerben megadott szám számjegyeit értelmezzük. Ezután az egyes m számokat azM = me mod nképlettel kódoljuk előállítva a rejtjelezett M üzenetet. A kódoláshoz csak a nyilvános kulcsot, az e,n számpárt kell ismerni! A titkos M üzenetet az   m = Md mod n

képlet alapján lehet dekódolni. A visszafejtéshez tehát a titkos d kulcs ismerete kell! A kódolás és dekódolás során is moduláris hatványozást kell végezni, amelyik az „intelligens” hatványozó algoritmussal elfogadható gyorsasággal elvégezhető. Az elemi számelméletből jól ismert Euler-Fermat tételből következik, hogy a dekódolás után tényleg az eredeti üzenetdarabot kapjuk vissza. Az algoritmus ismertetése után néhány megjegyzést teszünk az RSA paraméterek megválasztásával kapcsolatban. A titkos kulcs – d – mai ismereteink szerint csak a φ(n) birtokában számítható ki, φ(n) meghatározása viszont ugyanolyan nehézségű, mint n prímtényezőkre bontása. Az RSA biztonsága tehát azon múlik, hogy milyen gyorsan tudjuk az n számot faktorizálni. Ha p és q és így n is kicsi, akkor ez egyszerű feladat. Növelve azonban p-t és q-t egyre nehezebb, ma még megoldhatatlan problémához jutunk. A felhasznált számoknak olyan nagyoknak kell lenniük, hogy az n számot ne lehessen prímtényezőkre bontani. Ma azt mondhatjuk, hogy n-nek legalább 1024 bináris, azaz kb. 308 decimális jegyű számnak kell lennie. A faktorizáló algoritmusok pillanatnyi csúcsteljesítménye az RSA-200, egy 200 decimális jegyű szám tényezőkre bontása, amelyet közel két évig tart. A p és q megválasztása során nemcsak a nagyságukra kell figyelni, hanem arra is, hogy a különbségük is nagy legyen. Ellenkező esetben ugyanis a Fermat faktorizációs algoritmus gyorsan megtalálja a tényezőket. Feltéve, hogy az n 1024 bites szám, p és q-t 512 bitesnek célszerű választani úgy, hogy a különbségük legalább 400 bit nagyságú legyen. Az n szám megválasztása után áttérünk e és d közelebbi elemzésére. Fentebb leírtuk, hogy d értékét az e és φ(n) egyértelműen meghatározza. Az is jól ismert, hogy d értékét a kiterjesztett euklideszi algoritmussal könnyen ki tudjuk számítani. A nyilvános kulcsdarab – e – megválasztására általában kétféle módszert követnek: az e-t véletlenszerűen választjuk ki az [1, φ(n)-1] intervallumból vagy olyan kis, páratlan számnak választjuk, amelynek bináris felírásában kevés 1-es számjegy található, például 17 vagy 65537. Az első esetben nem biztos, hogy rögtön olyan számot választunk, amelyik relatív prím φ(n)-hez, ilyenkor meg kell ismételni a választást, amíg ez a feltétel nem teljesül. Be lehet bizonyítani, hogy néhány választás után ez igen nagy valószínűséggel teljesül. Az aszimmetrikus titkosítás elvének megfogalmazása óta eltelt több, mint 30 évben számos más algoritmust is javasoltak, például a diszkrét logaritmus kiszámításának nehézségén alapuló ElGamal, a diszkrét elliptikus görbéket alkalmazó algoritmus vagy a hibajavító kódok dekódolásának bonyolultságára építő Mc Ellise módszer. Jobb ha ezekkel nem foglalkozom. A nyilvános kulcsú titkosítás előnye, hogy a titkos kulcsot csak egy ember ismeri, így titkosított üzenetet nyilvános csatornán is lehet vele küldeni. A gyakorlatban azonban ez az előny csak korlátozottan aknázható ki, mert a jelenleg ismert módszerekkel a kódolás (és dekódolás) nagyságrendekkel tovább tart, mint a szimmetrikus algoritmusokkal. Ezért az aszimmetrikus módszereket csak rövid üzenetek kódolására célszerű alkalmazni. Ezen az észrevételen alapulnak az úgynevezett hibrid kriptorendszerek, amelyeknél egy szimmetrikus és egy aszimmetrikus módszert kombinálunk, mint az AES és az RSA.k.A távoli számítógépre való biztonságos bejelentkezésre szolgáló ssh (secure shell) szabványcsalád is ilyen. Az aszimmetrikus titkosításnak a kulcscserén kívül vannak más, fontos alkalmazásai is. Korábban már hangsúlyoztuk, hogy a titkos kulcsot csak egyetlen ember, a tulajdonosa ismeri, így a titkos kulcs egyértelműen azonosítja a tulajdonosát. A titkos kulcsot persze nem kérhetjük el igazoltatáskor a tulajdonosától, mert ha odaadná, akkor az igazoltató is megismerné azt és a tulajdonos többé már nem is használhatná. Olyan módszert kell tehát kitalálni, amely során a tulajdonos nem fedi fel titkos kulcsát, hanem csak bizonyítja, hogy ő rendelkezik a titkos kulccsal, ami nagyon hasonlít a digitális aláírásnál alkalmazott módszerhez.