PRIROČNIK ZA TEORETIČNO RAČUNALNIŠTVO

Kriptografija

4. Matematične priprave

Veliko pred kratkim predlaganih kriptografskih tehnik temelji na pristopih teorije števil. V tem razdelku bomo pregledali nekaj dejstev teorije števil in izračunljivosti. Za globlji pogled v osnovno teorijo števil glej [122, 105, 8]. Odličen pregled problemov razcepa celih števil, preskušanja praštevilskosti in diskretnega računanja logaritmov je v [103, poglavje 12].

Le navidez izgleda kot slučaj, da je mnogo lažje povedati, ali je dano število sestavljeno ali praštevilo, kot pa dano sestavljeno število razstaviti na prafaktorje. Ta razlika v stopnji zahtevnosti je osnova za veliko kriptografskih metod. Iskanje velikih praštevil je uporabno za izgradnjo kriptografskih operatorjev, tako da je pri mnogo kriptografskih metodah naloga nasprotnika dokazano tako zahtevna, kot je razcep produkta dveh velikih praštevil.

Za generiranje naključnih k-bitnih praštevil obstajajo učinkoviti postopki polinomske zahtevnosti v k [152, 132, 78, 5, 3]. Poznamo jih dveh tipov. Verjetnostni postopki tipa Monte Carlo se lahko zmotijo z majhno verjetnostjo, so vedno polinomske časovne zahtevnosti in v praksi kar učinkoviti. Drugi tip postopkov je Las Vegas, ki pa je vedno točen in vrne kot odgovor determinističen dokaz pravilnosti, ki teče v polinomskem času. Sam postopek pa je pričakovane polinomske časovne zahtevnosti. Ne znamo generirati le velikih praštevil, ampak tudi naključna k-bitna sestavljena števila v razcepljeni obliki. Bach [11] uporablja pri tem preizkus praštevilskosti kot podprogram.

Po drugi strani izgleda, da potrebujemo za razcep števila n čas, ki je reda velikosti

e^{c\sqrt{\ln n \cdot \ln(\ln n)}} , \label{elog} kjer je konstanta c enaka 1 pri najhitrejših postopkih. Razcep več kot 100-mestnih števil je trenutno v splošnem prezahtevna naloga. Pomerance in drugi [127, 128], Piesel [135] in Dixon [56] razpravljajo o novejših metodah za razcep števil.

Naj bo ZZ_n množica naravnih ostankov po deljenju z n in ZZ_n* njena podgrupa za mno ženje (po modulu), ki vsebuje le do n tuja števila. Funkcijo varphi (n) = |ZZ_n*| , ki nam pove njeno mo č, imenujemo Eulerjeva funkcija. Naj QQ_n ozna čuje mno žico kvadratov ostankov pri deljenju z n , torej je x \in {\cal Q}_n natan čno tedaj, ko obstaja y , tako da velja

x\equiv y^2\pmod n .

Jacobijev simbol $ \left({x\above 1pt n}\right) $ je definiran za vsak x \in \ZZ_n* in ima vrednost iz množice {1, 1} . Ta vrednost je lahko izračunljiva z uporabo zakona o obratni kvadratnosti??, čeprav je razcep n neznan. Če je n praštevilo, je potem

x \in {\cal Q}_n \iff \left({x\above 1.5pt n}\right) = 1 , če pa je n sestavljeno število, velja x \in {\cal Q}_n \Longrightarrow \left({x\above 1.5pt n}\right)=1 .$$ Naj označuje {\cal J}_n množico $$ {\cal J}_n = \left\{ x : x \in \ZZ_n^* \land \left( {x\above 1.5pt n} \right) = 1 \right\} ,$$ \widetilde{\cal Q}_n pa množico psevdo-kvadratov po modulu n , torej tiste elemente iz {\cal J}_n , ki niso elementi {\cal Q}_n . Če je n zmnožek dveh praštevil, je |{\cal Q}_n| = |\widetilde{\cal Q}_n| in za vsako število y , ki je psevdo-kvadrat, je $$ f_y(x)=yx $$ bijekcija množice {\cal Q}_n na \widetilde{\cal Q}_n .

Problem kvadratov ostankov je: za dano sestavljeno število n in x \in{\cal J}_n določi, ali je x kvadrat ali psevdo-kvadrat po modulu n . Ta problem je zahteven in je tudi osnova nekaterih kriptografskih metod.

Kvadriranje in korenjenje po modulu n sta običajni operaciji pri načrtovanju kriptografskih operatorjev. Pravimo, da je x kvadratni koren od y po modulu n , če je

x² \equiv y mod n . Če ima število n t prafaktorjev, ima lahko x tudi do 2^t kvadratnih korenov. Rabin [131] je dokazal, da je iskanje kvadratnih korenov po modulu n enako zahtevno kot razcep n . Torej ob danem učinkovitem postopku za korenjenje po modulu n lahko sestavimo učinkovit postopek za razcep n in obratno. To dejstvo sta opazovala Williams in Blum in je pogosto uporabno: ***** "ce je $ n $ zmno"zek dveh pra"stevil, obeh kongruentnih 3 po modulu 4, potem kvadriranje po modulu $ n $ izvede permutacijo $ {\cal Q}_n $.

Pogosto je koristno uporabiti potence, ki so ve"cje od 2. Funkcijo $$ x^e \bmod n $$ imenujemo {\it potenciranje po modulu}, kjer je modul $ n $ lahko tako sestavljeno "stevilo kot pra"stevilo. V nasprotju z operatorjem kvadriranja je potenciranje po modulu bijekcija na $ \ZZ_n $, "ce je $ {\rm GCD}(e, \varphi(n))=1 $ [137].

Poznamo dva na"cina dolo"canja inverza k poteciranju po modulu, odvisno za katere $ e $ in $ x $ gledamo. V prvem primeru "zelimo za dane $ x, y $ in $ n $ izra"cunati $ e $ ("ce obstaja), tako da je \begin{eqnarray} x^e\equiv y\pmod n . \label{kong} \end{eqnarray} To imenujemo {\it diskretno logaritmiranje} $ y $ po modulu $ n $ (z logaritemsko osnovo $ x $) in ozna"cimo potenco kot $$e= {\rm index}_{x, n}(y) .$$ V primeru, ko je $ n $ pra"stevilo, opazimo, da ima ena"cba (\ref{kong}) pri mnogih $ x $ re"sitve za vse $ y\in\ZZ_n^* $ . Take $ x $ imenujemo generatorje. V splo"snem je diskretno logaritmiranje zahtevno, vseeno pa sta Pohlig in Hellman [126] predstavila u"cinkovite tehnike za re"sevanje tega problema, ko je $ n $ pra"stevilo in ko ima $ ~ n-1 ~ $ le majhne prafaktorje. Adleman [1] nam poka"ze kako izra"cunati diskretne logaritme v "casu (\ref{elog}), kar ka"ze na isto stopnjo zahtevnosti diskretnega logaritmiranja in razcepa "stevil, obakrat odvisno od velikosti uporabljenih "stevil. Zanimivo je, da je problem bistveno la"zji, "ce delamo na kon"cnem polju $ GF(2^k) $ namesto po modulu $ n $ (glej [43, 124]). Za nadaljne izbolj"save in splo"sno razpravo glej [45].

Drugi na"cin iskanja inverza k potenciranju po modulu je re"sevanje na $ x $: za dane $ y, e $ in $ n $ i"s"cemo $ x $ ("ce ta obstaja), tako da velja (\ref{kong}). Imenujemo ga {\it $e$-ti koren od $ y $ po modulu $ n $}. "Ce je $ n $ pra"stevilo, gre njegov izra"cun v polinomskem "casu [22, 4, 133], medtem ko postane v nasprotnem primeru problem tako zahteven kot je razcep $ n $ ali diskretno logaritmiranje po modulu $ n $.

Pravimo, da je dvoji"ska naklju"cna spremenljivka $ X $ {\it $\varepsilon$-biased}, "ce je verjetnost, da je $ X=0 $ v $\varepsilon$-okolici $1 \over 2$, torej $${\rm P}(X=0)\in\left[{1\over 2}-\varepsilon, {1\over 2}+\varepsilon\right] .$$ Ta oznaka bo uporabna v na"si razpravi o psevdo-naklju"cnem zaporedju bitov.