Tässä kätkössä tarkastellaan, miten elliptisiä käyriä voi käyttää johonkin hyödylliseen eli salausmenetelmiin. Voit lukaista läpi Elliptiset kätköt (GC20VTK), niin saat esimakua käyristä. Tämän kätkön löytämiseksi tuota tehtävää ei kuitenkaan tarvitse ratkaista. Tämän pitäisi olla myös helpompi laskea, koska lopusta löytyy linkki sopivaan työkaluun.
Salausalgoritmien kuvauksessa on aina osapuolina Alice ja Bob - niin nytkin. Symmetrisessä salauksessa Alicen ja Bobin täytyy sopia yhteisestä avaimesta, jolla salaiset viestit koodataan ja puretaan. Avainta ei saa antaa ulkopuolisille, jotta salausta ei murreta. Esimerkiksi sopii Ceasar-salaus, jota kätköilypiireissä käytetään avaimella 13.
Epäsymmetrisessä salauksessa eli ns.julkisen avaimen salauksessa on kaksi avainta: julkinen ja salainen. Salainen pidetään vain omana tietona, mutta julkisen voi laittaa vaikkapa omalle weppisivulleen näkyville. Esimerkiksi sähköpostiohjelmienkin tukema PGP salausohjelma käyttää julkisen avaimen salausta. Nämä menetelmät perustuvat ns. yksisuuntaisiin funktioihin, jotka on helppo laskea toiseen suuntaan mutta käänteisfunktion laskeminen on vaikeaa. Vaikeus tarkoittaa sitä, ettei tunneta yhtään algoritmia, joka laskisi ongelman nopeasti - eli suomeksi: salausmenetelmät perustuvat siihen, että joidenkin ongelmien luullaan olevan vaikeita.
Jos Alice ja Bob haluasivat käyttää symmetristä salainta (esim. rot14) keskinäiseen kirjeenvaihtoon, heidän pitäisi ensin kommunikoida toisilleen salausavain (=14). Mutta tämä viesti pitäisi salata eli meillä on muna-kana-ongelma. Tähän tarkoitukseen Diffie ja Hellman keksivät avaimenvaihtoprotokollan, joka on julkisen avaimen systeemi. Nyttemin siitä on kehitetty elliptisiä käyriä käyttävä vaihtoehto, jota käytämme tässä tehtävässä. Elliptisiä käyriä käyttävissä systeemeissä turvallisen avaimen koko ja systeemin parametrit ovat yleensä pienempiä, mikä on tärkeää, jos muisti tai suorituskyky on rajallinen (esim. sirukorteissa).
Jos tarkastelisimme jonkin kokonaislukupisteen monikertoja kuten ykköskätkössä, niin saisimme joko korkeintaan 16 eri pistettä tai sitten äärettömästi. Ääretön on sovelluksissa hankala lukumäärä (ja 16 liian vähän) ja siksi joudumme rajoittamaan tarkastelua normaaleista kokonais- ja murtoluvuista ns. äärellisiin kuntiin. Jos olet joskus laskenut murtoluvuilla, olet tieten tai tietämättäsi laskenut rationaalilukujen kunnassa. Se tarkoittaa vain sitä, että normaalit neljä laskutoimitusta (+, -, *, /) toimivat ns. normaalisti.
Opettavainen osuus: Ota mikä tahansa alkuluku p (2,3,4,7,11,...) - vaikkapa 7 - ja listaa kaikki mahdolliset jakojäännökset tällä luvulla jaettaessa - esim. 0,1,2,3,4,5,6. Nämä luvut edustavat nyt äärellisen kunnan alkioita ja niillä lasketaan lähes normaalisti. Jos laskiessasi päädyt tämän joukon ulkopuolelle, lisää alkuluvun monikertoja kunnes pääset takaisin samaan joukkoon. Jos p = 7, niin voimme laskeskella
- 7 = 7 - 7 = 0
- 3 + 5 = 8 = 8 - 7 = 1
- 2 - 6 = -4 = -4 + 7 = 3
- 5 * 6 = 30 = 30 - 4 * 7 = 2
Jos haluaa korostaa, että kyseessä on normaalista kokonaislukulaskusta poikkeava lasku, voi kirjoittaa yhtälön perään (mod p), joka luetaan "modulo p". Jakolasku on vähän hankalampi: normaalisti 1 / x = y tarkoittaa, että 1 = x * y ja niin nytkin. Jos p on edelleen 7, niin
- 5 * 3 = 15 = 1 (mod 7), joten 1 / 5 = 3 (mod 7) ja 1 / 3 = 5 (mod 7)
- 2 * 4 = 8 = 1 (mod 7), joten 1 / 2 = 4 (mod 7) ja 1 / 4 = 2 (mod 7)
- 6 * 6 = 36 = 1 (mod 7), joten 1 / 6 = 6 (mod 7)
Lisäksi 1 / 1 = 1 (mod 7), joten olemme saaneet kaikille nollasta poikkeaville luvuille käänteisluvun samasta joukosta 1,...,6. Koska kaikki neljä peruslaskutoimitusta onnistuu, kyseessä on kunta.
Tehtävä: Tarkastellaan elliptistä käyrää
y2 = x3 - 25 x - 8
modulo 3001, jolloin sillä on piste P=(10,1009). Tämä piste ja sen monikerrat muodostavat ns. syklisen ryhmän 0, P, 2P, 3P, 4P, ..., 496P, 497P=0, jossa on 497 erisuurta pistettä. Käytetään tätä käyrää ja pistettä Diffien-Hellmanin avaimenvaihtoprotokollaan. Sinä olet Alice ja sinun salainen avaimesi on 6 - älä kerro sitä kellekään. Sinun julkinen avaimesi on A = 6P = (508, 2878) ja sen voit laittaa vaikka weppisivuillesi. Kaverisi Bob on antanut weppisivuillaan oman julkisen avaimensa B=(497, 515) ja haluasit keskustella hänen kanssaan salaisesti. Laske siis 6B ja se on teidän yhteinen salainen avaimenne. Koska Bob tietää oman salaisen avaimensa b (eli B= bP), hän voi puolestaan katsoa sinun weppisivulta julkisen A:n ja laskea bA= b6P = 6bP = 6B eli Bob saa saman avaimen, mutta kummankaan ei tarvitse paljastaa omaa salaista avaintaan.
Voit laskea tehtävän helpoiten elliptisten käyrien online-laskimella. Anna kohtaan "mod p" luku 3001 ja täytä käyrän parametrit. Laske ensin 2B, sitten 4B ja lopuksi 6B = 2B + 4B. Tämän salaisen avaimen koordinaattien pitäisi johdattaa sinut purkin luo.
Jos tuo online-laskin ei toimi, voi laskea Wolfram Alphalla käyttäen ykköskätkön laskukaavoja. Alpha ymmärtää syntaksia: "123 * 456 mod 3001" ja "1234^(-1) mod 3001" käänteisluvulle.
Oikeasti käyrän parametrien ja avainten täytyy olla paaaljon suurempia, jotta ne olisivat oikeasti turvallisia eli salaisia. Turvallisuus perustuu siihen, että halutessaan pystyy kohtuuajassa laskemaan annetun pisteen P monikerran mP, mutta toisinpäin ns. diskreetin logaritmin ongelma on lähes mahdoton: jos annetaan piste mP ja P, laske m. PlayStation-klusterilla on murrettu tämmöinen ongelma, jossa käyrä oli määritelty modulo 112-bittinen p - mikä vastaa kymmenjärjestelmässä 34-numeroista lukua.
Jos et saanut vielä laskea riittävästi, voit tarkistaa, että Bob saa saman avaimen. (Hys: Bobin salainen avain on 79, joten hän laskee 79A=A+2A+4A+8A+64A).
Briefly in English: Take the above elliptic curve and a point P=(10,1009) modulo 3001. Your secret key in elliptic curve Diffie-Hellman protocol is 6 and your public key is 6P=(508, 2878). Your friend Bob has a public key B=(497, 515) and your common secret key will be 6B. Count it with the online calculator by plugging in prime p=3001 and the parameters of the above curve. Count 2B, 4B, 6B = 2B + 4B and then you should have the coordinates for the cache.