Diskreetti logaritmi

4.1. M¨a¨aritelm¨a

T¨ass¨a kappaleessa m¨a¨aritell¨a¨an, mik¨a on diskreetti logaritmi ja esitet¨a¨an pari esi-merkki¨a selvent¨am¨a¨an m¨a¨aritelm¨a¨a. Esimerkeiss¨a on k¨aytetty symbolista laskentaoh-jelmaa jaottomien polynomien ja primitiivisten alkioiden etsimisess¨a ja tietysti loga-ritmin laskemisessa, sill¨a kyseess¨a on jo melko suuria kuntia, joten laskuissa kest¨aisi hyvin kauan ilman apuv¨alineit¨a. L¨ahteen¨a on k¨aytetty teosta [1].

Yksi t¨arkeimmist¨a lukuteorian ongelmista on potenssiin korottamisen ”yksisuun-taisuus” ¨a¨arellisiss¨a kunnissa. On siis melko helppoa laskea toistetun neli¨oinnin avulla esimerkiksi kunnassa F^q luvun b^x ratkaisu isoillekin luvuille x. Mutta jos on alkio y, jonka tiedet¨a¨an olevan muotoa b^x, niin miten saadaan selvitetty¨a potenssi x, toisin sanoen on x = log_by? T¨at¨a kusutaan diskreetin logaritmin ongelmaksi, miss¨a sana diskreetti tarkoittaa tapausta ¨a¨arellisiss¨a kunnissa ”tavallisen” logartimin sijasta.

M¨a¨aritelm¨a 4.1.1. Jos G on ¨a¨arellinen kunta, b ∈G ja y ∈ G siten, ett¨a y on alkion b potenssi, niin alkion y b-kantainen diskreetti logaritmi on kokonaisluku x, jolle b^x =y.

Kuten esimerkiss¨a 2.4.8 huomataan, kunnan primitiivist¨a alkiota voidaan k¨aytt¨a¨a logaritmin kantalukuna kunnassa, koska t¨all¨oin kaikki kunnan G alkiot ovat t¨am¨an luvun potensseja. Esimerkiksi jos otetaan kunta F₁₉^∗ ja valitaan kantaluvuksi kunnan viritt¨aj¨a 2, niin diskreetti logaritmi luvusta 7 on 6, eli log₂7 = 6. Toisin sanoen siis 7 = 2⁶. Nyt koska kantalukuna on kunnan primitiivinen alkio, niin diskreetin logaritmin avulla voidaan ilmaista kaikkille alkioille potenssix, jolle alkio on muotoa 2^x kunnassaF₁₉.

Seuraavassa esimerkiss¨a on asettettu kunnaksi F2²⁵, jolloin siis kunnan karakte-ristika on 2 ja viritt¨av¨a polynomi on astetta 25. Laskentaohjelma antaa jaottoman polynomin, joka viritt¨a¨a kunnan sek¨a kunnan primitiivisen alkion.

Esimerkki4.1.2. OlkoonF2²⁵ kunta, jonka viritt¨a¨a polynomix²⁵+x³+1, ja jonka primitiivinen juuri on x. Valitaan laskentaohjelmalla satunnaisesti jaoton polynomi p(x) = x²⁴+x²²+x¹⁹+x¹⁸+x¹⁶+x¹⁵+x¹¹+x¹⁰+x⁸ +x⁶ +x⁵ +x⁴ +x². Nyt ohjelma laskee logaritmin t¨ast¨a polynomista:

log_x(p(x)) = 5791578.

Toisin sanoen siis polynomip(x) kunnassaF2²⁵ saadaan, kun korotetaan primitiivinen juuri x potenssiin 5791578. Saatu vastaus voidaan viel¨a tarkistaa laskentaohjelman avulla laskemalla saatu potenssi x^5791578 ja sievent¨am¨all¨a se modulo x²⁵+x³+ 1.

41

42 4. DISKREETTI LOGARITMI

4.2. Diffien ja Hellmanin avaintenvaihto

Koska julkisen avaimen salausj¨arjestelm¨at ovat usein melko hitaita verrattuna klassiseen salausj¨arjestelm¨a¨an, niit¨a k¨aytett¨an yleens¨a hieman yhdistettyn¨a klassiseen salausj¨arjestelm¨a¨an, miss¨a todelliset viestit l¨ahetet¨a¨an. Lis¨aksi klassisen salausj¨ arjes-telm¨an avain voidaan l¨oyt¨a¨a melko tehokkaasti k¨aytt¨am¨all¨a julkista avainta. T¨ass¨a kappaleessa esitell¨a¨an er¨as yksityiskohtainen keino tehd¨a se, W. Diffien ja H. E. Hell-manin mukaan, joka perustuu diskreetin logaritmin ongelmaan. L¨ahteen¨a on k¨aytetty teosta [1].

Oletetaan, ett¨a klassisen salausj¨arjestelm¨an avain on suuri sattumanvaraisesti va-littu positiivinen kokonaisluku (tai kokoelma t¨allaisia lukuja). Nyt siis Diffien ja Hell-manin menetelm¨all¨a etsit¨a¨an suuresta ¨a¨arellisest¨a kunnasta Fq sattumanvarainen al-kio. Oletetaan, ett¨a lukuqon julkinen: kaikki tiet¨av¨at, miss¨a kunnassa kyseinen avain on. Oletetaan my¨os, ett¨a g on jokin kiinnitetty alkio kunnassa Fq, joka ei my¨osk¨a¨an ole salainen. Ihannetilanteessa alkiogolisi kunnanF^∗qviritt¨aj¨a; t¨am¨a ei kuitenkaan ole t¨aysin v¨altt¨am¨at¨ont¨a. Seuraava menetelm¨a antaa ainoastaan kunnan Fq alkioita, jot-ka ovat alkiong potensseja; n¨ain ollen, jos todella halutaan t¨aysin sattumanvataisesti kunnan F^∗q alkio, niin alkiong tulee olla primitiivinen.

Oletetaan, ett¨a kaksi henkil¨o¨a A (Aida) ja B (Bernard) sopia avaimen, sattuman-varaisen alkion kunnasta F^∗q, jolla he salaavat toisilleen l¨ahetett¨av¨at viestins¨a. Aida valitsee sattumanvaraisen luvun a v¨alilt¨a 1 jaq−1, jonka h¨an pit¨a¨a salassa ja laskee g^a ∈ Fq, jonka h¨an julkaisee. Bernard tekee samoin: h¨an valitsee sattumanvaraisen luvun b ja julkaisee luvun g^b. Salainen avain, jota he k¨aytt¨av¨at, on g^ab. Molemmat henkil¨ot pystyv¨at laskemaan t¨am¨an avaimen, sill¨a esimerkiksi Aida tiet¨a¨a luvun g^b (joka on julkinen) ja luku a on h¨anen omaa tietoaan. Kuitenkin kolmas osapuoli tie-t¨a¨a vain luvut g^a ja g^b. Jos seuraava oletus p¨atee multiplikatiiviselle joukolle F^∗q, niin ulkopuolinen kolmas osapuoli ei pysty m¨a¨aritt¨am¨a¨an avainta.

Diffien ja Hellmanin oletus: On laskennallisesti mahdotonta ratkaista lukua g^ab ainoastaan lukujen g^a ja g^b avulla.

Diffien ja Hellmanin oletus on ainakin yht¨a t¨arke¨a kuin oletus siit¨a, ett¨a diskreet-ti¨a logaritmia ei voida helposti laskea ryhm¨ass¨a. Toisin sanoen, jos diskreetti logaritmi voidaan laskea, niin selv¨asti Diffien ja Hellmanin oletus ei p¨ade. Jotkut ihmiset ar-velevat, ett¨a my¨os p¨ainvastainen p¨a¨atelm¨a p¨atee, mutta siihen ei ole viel¨a todisteita.

Eli kukaan ei pysty saamaan lukuag^ab luvuistag^ajag^b ilman, ett¨a ensin m¨a¨aritell¨a¨an luvut a ja b; mutta on mahdollista, ett¨a sellainen menetelm¨a olisi olemassa.

Esimerkki 4.2.1. Oletetaan, ett¨a k¨aytet¨a¨an siirtosalausta yksikirjaimisiin viestin yksik¨oihin 26-kirjaimisessa aakkostossa: C ≡ P +B mod 26. Valitaan B ottamalla pienin ep¨anegatiivinen j¨a¨ann¨os modulo 26 sattumanvaraisesta alkiosta kunnassaF53. Olkoon g = 2 (joka on kunnan F53 viritt¨aj¨a). Oletetaan, ett¨a Aida valtisi sattuman-varaisesti luvuna= 29 ja katsoi Bernardin julkisen luvun 2^b, joka oli vaikka 12∈F53. T¨all¨oin h¨an tiet¨a¨a, ett¨a salausavain on 12²⁹ = 21 ∈ F53, toisin sanoen B = 21. Sa-malla h¨an on tehnyt julkiseksi luvun 2²⁹= 45, jolloin Bernard voi my¨os saada selville avaimen B = 21 korottamalla luvun 45 potenssiin b (h¨anen salainen potenssinsa on b = 19). Tietenk¨a¨an ei ole j¨arke¨a valita n¨ain pient¨a kuntaa, koska ulkopuolinen voi helposti l¨oyt¨a¨a diskreetin 2-kantaisen logaritmin luvuista 12 ja 45 modulo 53. Lis¨aksi

4.4. DIGITAALINEN ALLEKIRJOITUS 43

siirtosalaus yksikirjaimisilla yksik¨oill¨a ei ole turvallinen salausmenetelm¨a. Mutta t¨all¨a esimerkill¨a havainnollistetaan Diffien ja Hellmanin avaintenvaihto menetelm¨a¨a.

4.3. ElGamalin salausj¨arjestelm¨a

T¨ass¨a kappaleessa tarkastellaan salausj¨arjestelm¨a¨a, joka k¨aytt¨a¨a Diffien ja Hell-manin avaintenvaihdon tapaisia menetelmi¨a, eli hy¨odynnet¨a¨an diskreetin logaritmin ongelmaa. L¨ahteen¨a on k¨aytetty teosta [1].

Aloitetaan kiinnitt¨am¨all¨a suuri ¨a¨arellinen kunta F_q ja alkio g ∈ F^∗q (mielell¨a¨an, mutta ei v¨altt¨am¨att¨a viritt¨aj¨a). Oletetaan, ett¨a k¨aytet¨a¨an selv¨akielisen viestin yksi-k¨oit¨a, joilla on numeerinen vastineP kunnassaFq. Jokainen henkil¨o A valitsee sattu-manvaraisesti kokonaisluvuna =aA, sanotaan v¨alill¨a 0< a < q−1. T¨am¨a kokonais-lukua on salainen avausavain. Julkinen salausavain on alkiog^a ∈F^q.

Jos halutaan l¨ahett¨a¨a viesti P henkil¨olle A, niin valitaan kokonaisluku k sattu-manvaraisesti ja l¨ahetet¨a¨an henkil¨olle A seuraava alkiopari kunnasta F^q:

(g^k, P g^ak).

Huomataan, ett¨a voidaan laskea lukug^ak ilman, ett¨a tiedet¨a¨an lukuaa, korottamalla luku g^a potenssiin k. Nyt henkil¨o A, joka tiet¨a¨a luvun a, voi selvitt¨a¨a viestin P korottamalla parin ensimm¨aisen alkiong^kpotenssiinaja jakamalla parin toisen alkion t¨ast¨a saadulla luvulla (yht¨a lailla voitaisiin korottaag^kpotenssiinq−1−aja kertoa se parin j¨alkimm¨aisell¨a alkiolla). Toisin sanoen henkil¨olle A l¨ahetet¨a¨an viesti salaisessa muodossa, luku g^ak on ik¨a¨an kuin viestinP ”valeasu”, jonka lis¨aksi annetaan ”vihje”, eli g^k, jolla valeasu saadaan riisuttua (mutta vihjett¨a voi k¨aytt¨a¨a vain henkil¨o, joka tiet¨a¨a luvun a).

Jos osattaisi ratkaista diskreetin logaritmin ongelma kunnassaF^q, niin ElGamalin salausj¨arjestelm¨a olisi helppo purkaa etsim¨all¨a salainen avausavain a julkisesta sa-lausavaimesta g^a. Teoriassa voisi olla keino ratkaista luku g^ak lukujeng^a jag^k avulla, ja n¨ain ollen ratkaista salaus, ilman diskreetin logaritmin ratkaisemista. On kuiten-kin arvailtu, kuten edell¨a jo mainittiin, ett¨a ei ole olemassa keinoa selvitt¨a¨a lukua g^ak luvuista g^a ja g^k ilman diskreetin logaritmin ongelman ratkaisua.

4.4. Digitaalinen allekirjoitus

My¨os digitaalisessa allekirjoituksessa k¨aytet¨a¨an hy¨odyksi diskreetin logaritmin on-gelmaa, jotta l¨ahetetyn viestin vastaanottaja voi olla varma, kuka on allekirjoittanut viestin. T¨ass¨a kappaleessa on k¨aytetty l¨ahteen¨a teosta [1].

M¨a¨aritelm¨a 4.4.1. Dokumentti voidaan allekirjoittaa tiivistefunktion avulla.

Tiivistefunktio on kuvaus f : x7→h, miss¨a sy¨ote on hyvin pitk¨a ja tuloste on paljon lyhyempi (esim. x voi olla 10⁶ numeroinen jono ja h taas 150 tai 200 numeroinen jo-no), jolla on ominaisuus: ei ole laskennallisesti mahdollista l¨oyt¨a¨a kahta eri sy¨otett¨a x ja x⁰ siten, ett¨a f(x) = f(x⁰).

Digitaalisen allekirjoituksen idea on sama kuin tavallisessa allekirjoituksessa. Haas-teena on kuitenkin tehd¨a se niin, ett¨a kukaan muu ei voi kopioida sit¨a. Kun viestin l¨ahett¨aj¨a siis allekirjoittaa viestins¨a, niin viestin vastaanottaja on varma, ett¨a kuka

44 4. DISKREETTI LOGARITMI

viestin on allekirjoittanut. Seuraavaksi esitell¨a¨an digitaalisen allekirjoituksen j¨ arjes-telm¨a, jossa k¨aytet¨a¨an diskreetin logartimin ogelmaa ¨a¨arellisiss¨a kunnissa ja se vastaa ElGamalin digitaalista allekirjoitusj¨arjestelm¨a¨a.

Siisp¨a digitaalisen allekirjoituksen j¨arjestelm¨an luomiseksi henkil¨on A valitsee suu-ren alkuluvun q, jossa on noin 160 numeroa (t¨am¨an h¨an tekee ohjelmalla, joka antaa satunnaisesti suuren luvun ja testaa, onko se alkuluku). Sitten h¨an valitsee toisen al-kuluvunp, jossa on noin 512 numeroa siten, ett¨ap≡1 mod q. T¨am¨an j¨alkeen henkil¨o A valitsee kunnan F_p^∗ yksik¨asitteisen syklisen aliryhm¨an viritt¨aj¨an, jonka kertaluku onq(laskemallag

p−1 q

0 mod qjollekin mielivaltaiselle kokonaisluvulleg₀; jos t¨am¨a luku on6= 1, niin se on ryhm¨an viritt¨aj¨a). Seuraavaksi henkil¨o A valitsee mielivaltaisen ko-konaisluvunx v¨alilt¨a 0< x < q salaiseksi avaimekseen ja asettaa julkiseksi avaimeksi luvun y siten, ett¨a y=g^x modp.

Nyt oletetaan, ett¨a henkil¨o A haluaa allekirjoittaa viestin. Ensin h¨an lis¨a¨a tiivis-tefunktion selv¨akieliseen viestiins¨a, joka sis¨alt¨a¨a kokonaisluvun h v¨alilt¨a 0 < h < q.

Seuraavaksi h¨an valitsee sattumanvaraisen kokonaisluvun k samalta v¨alilt¨a, laskeeg^k mod p ja asettaa luvun r tarkoittamaan pienint¨a luvun g^k ep¨anegatiivista neli¨ one-p¨aj¨a¨ann¨ost¨a modulo q (ts. g^k lasketaan ensin modulo p ja saatu tulos supistetaan modulo pienempi alkuluku p). Lopulta henkil¨o A l¨oyt¨a¨a kokoneisluvun s siten, ett¨a sk ≡ h+xr mod q. H¨anen allekirjoituksensa on t¨all¨oin lukupari (r.s) kokonaislu-vuista modulo q.

Allekirjoituksen tarkastamiseksi vastaanottaja B laskeeu₁ =s⁻¹h mod qjau₂ = s⁻¹r modq. Sitten h¨an laskee g^u1y^u2 mod p. Jos tulos vastaa modulo q lukua r , niin h¨an on tyytyv¨ainen. (Huomataan, ett¨ag^u1y^u2 =g^s−1(h+xr) =g^k mod p.)

4.5. Diskreetin logaritmin etsiminen ¨a¨arellisiss¨a kunnissa

Vaikka diskreetti¨a logaritmia on l¨ahes mahdoton ratkaista, siihen on kehitetty erilaisia algoritmeja. T¨ass¨a kappaleessa esitell¨a¨an yksi t¨allaisista algoritmeista, mutta sit¨a ennen todistetaan t¨arke¨a lause, jonka tulosta k¨aytet¨a¨an diskreetin logaritmin etsimisess¨a. L¨ahteen¨a on k¨aytetty teosta [1].

Lause 4.5.1 (Kiinalainen j¨a¨ann¨oslause). Olkoot m₁, m₂, . . . , m_r kesken¨a¨an jaot-tomia, eli syt(m_i, m_j) = 1, kuni6=j. T¨all¨oin on olemassa ratkaisu x kongruenssiyh-t¨al¨oryhm¨alle:

x≡a₁ mod m₁ x≡a₂ mod m₂

...

x≡a_r modm_r

ja mitk¨a tahansa kaksi ratkaisua ovat kongruentteja kesken¨a¨an moduloM =m₁m₂· · ·m_r. [3], [1]

Todistus. Todistetaan ensin viimeinen lause, eli ett¨a ratkaisu on yksik¨asitteinen moduloM. Oletetaan, ett¨ax⁰jax⁰⁰ovat molemmat konruenssiyht¨al¨oryhm¨an ratkaisu-ja. Olkoon x=x⁰−x⁰⁰. T¨all¨oin luvunx on oltava kongruentti luvun 0 kanssa modulo mi kaikillei= 1,2, . . . , r ja n¨ain ollen my¨os moduloM. Seuraavaksi katsotaan, miten ratkaisu x saadaan.

4.5. DISKREETIN LOGARITMIN ETSIMINEN ¨A ¨ARELLISISS ¨A KUNNISSA 45

M¨a¨aritell¨a¨anM_i = _m^M

i olemaan tulo kaikista moduleista paitsii. modulista. Selv¨ as-ti syt(mi, Mi) = 1 jolloin on olemassa kokonaislukuNi siten, ett¨aMiNi ≡1 mod mi. Asetetaan nytx=P

iaiMiNi. T¨all¨oin jokaisellein¨ahd¨a¨an, ett¨a, ett¨a summan kaikki muut termit paitsi i. termi ovat jaollisia luvulla m_i, koska m_i | M_j, kun i 6=j. N¨ain ollen jokaiselle i saadaan: x≡a_iM_iN_i ≡a_i modm_i Oletetaan ensin, ett¨a kaikki luvunq−1 alkutekij¨at ovat pieni¨a. T¨all¨a oletuksella on olemassa nopea algoritmi diskreetinb-kantaisen logaritmin etsimiseen alkiolley∈F^∗q. Yksinkertaisuuden takia oletetaan, ett¨a b on kunnan F^∗q viritt¨aj¨a. T¨am¨an algoritmin ovat kehitt¨aneet Silver, Pohlig ja Hellman.

Ensin jokaiselle luvun q − 1 jakavalle alkuluvulle p lasketaan p. yksikk¨ojuuri r_p,j = b^jq−1p kaikille j = 0,1, . . . , p − 1. (T¨ass¨a k¨aytet¨a¨an toistettua neli¨ointi¨a lu-vun b korottamisessa suureen potenssiin.) Nyt juurien {r_p,j} avulla voidaan laskea diskreetti logaritmi mille tahansa alkiolle y ∈ F^∗q. (Huomataan, ett¨a jos b on kiinni-tetty, niin ensimm¨ainen laskutoimitus t¨aytyy tehd¨a vain kerran, jonka j¨alkeen samoja juuria voidaan k¨aytt¨a¨a mille tahansa alkiolle y.)

Tarkoituksena on l¨oyt¨a¨a x, 0 ≤x ≤ q−1, siten, ett¨a b^x = y. Jos q−1 = Q

pp^α on luvunq−1 alkutekij¨oihin jako, niin riitt¨a¨a l¨oyt¨a¨ax mod p^α jokaiselle luvunq−1 jakajalle p; t¨ast¨a saadaan yksik¨asitteinen x k¨aytt¨am¨all¨a kiinalaista j¨a¨ann¨oslausetta (lause 4.5.1). Joten kiinnitet¨a¨an luvun q−1 jakava alkuluku p ja n¨aytet¨a¨an, miten m¨a¨aritell¨a¨anx mod p^α.

on korotettu p. potenssiin, saadaany

q−1 Siisp¨a voidaan rinnastaa luvut y

q−1 lukux_i vastaamaan arvoa j, kun y

q−1 p+1

i =r_p,j.

Lopulta saadaanx modp^α. Kun t¨am¨a on tehty jokaisellep|q−1, niin k¨aytet¨a¨an lopuksi kiinalaista j¨a¨ann¨oslausetta saadaksemme luvun x.

T¨am¨a menetelm¨a toimii hyvin luvunq−1 jakajille, jotka ovat pieni¨a alkulukuja.

Mutta juurten joukon{r_p,j}laskeminen ja sen rinnastaminen lukuihiny

q−1 p+1

i vie paljon

46 4. DISKREETTI LOGARITMI

aikaa, jos luvunq−1 jakajat ovat suuria alkulukuja (”suurella” tarkoitetaan v¨ahint¨a¨an 20-numeroisia lukuja). Jos luku p | q−1 on pienempi kuin luku 10²⁰, niin voidaan yhdist¨a¨a Silverin, Pohligin ja Hellmanin algoritmi Shankin ”suuri askel - pieni askel”

menetelm¨a¨an; ks. Knuth, Art of Computer Programming vol. 2.

Kirjallisuutta

[1] N. Koblitz: A Course in Number Theory and Cryptography, toinen laitos, Springer, 1994.

[2] S. Lang: Undergraduate algebra. kolmas painos, Springer Science+Business Media Inc., 2005.

[3] A. Lehtonen: Salakirjoitukset. kurssimoniste, 2018.

[4] R. J. McEliece: Finite Fields for Computer Scientists and Engineers. Kluwer Academic Publishers, 1987.

47

In document Äärelliset kunnat ja niiden sovelluksia (sivua 45-51)