Näin toimii kvanttikryptografia

Vuonna 1994 tietojenkäsittelytieteilijä Peter Shor keksi että jos kvanttitietokone keksittäisiin, ne kykenisivät hajottamaan ison osan siitä infrastruktuurista, jota käytetään suojelemaan verkossa jaettua tietoa. Tuo pelottava mahdollisuus on saanut tutkijat rämpien tuottamaan uudenlaisia “kvanttien jälkeisiä” kryptausmenetelmiä, jotta pelastettaisiin informaatiota niin paljon kuin mahdollista ennen niiden päätymistä kvanttihakkereille.

Aiemmin vuonna 2022 National Institute of Standards and Technology kertoi neljästä finalistista sen post-kvanttikryptografiastandardille. Kolme niistä käyttää “hilakryptografiaa” — menetelmää, joka on saanut inspiraatiota hiloista, avaruuden säännönmukaisista pisterakenteista.

Hilakryptografia ja muut kvanttien jälkeiset mahdollisuudet eroavat nykyisistä standardeista monin tavoin. Mutta ne kaikki nojaavat matemaattiseen asymmetriaan. Nykyisten kryptografisten järjestelmien tarjoama turva perustuu kertolaskuun ja tekijähajotelmaan: mikä tahansa tietokone voi nopeasti kertoa yhteen kaksi lukua, mutta voi kestää vuosisatoja selvittää kryptografisesti suuren luvun alkulukutekijät. Tuo asymmetria tekee salaisuuksista helpon koodata, mutta vaikeaa purkaa.

Shor sai selville algoritmistaan, että tekijähajotelma tekee algoritmista haavoittuvaisen kvanttitietokoneiden hyökkäykselle.  “Se on erittäin tietty, erikoinen juttu jonka kvanttitietokoneet osaavat tehdä”, sanoo Katherine Stange,  Coloradon yliopiston matemaatikko Boulderissa. Shorin jälkeen kryptograafikoilla oli uusi homma: etsi uusi matemaattisten operaatioiden joukko, joita on helppo käyttää mutta lähes mahdoton purkaa.

Hilakryptografia on eräs tähänastisista kaikkein menestyksekkäimmistä. Alunperin se on kehitetty 1990-luvulla. Se nojaa pisteiden summien takaisinmallintamisen vaikeuteen.

Tässä on eräs tapa kuvata hilakryptografiaa: kuvittele, että ystävälläsi on hila, joka siis on pelkkä kuvion muodostava toistuvien pisteiden joukko tasolla. Ystäväsi haluaa nimetä 10 näistä pisteistä. Mutta hän on vastarannankiiski, ja ei piirrä koko hilaa. Sen sijaan hän mainitsee vain kaksi pistettä — ensimmäinen, jonka x-koordinaatti on 101 ja y-koordinaatti 19, ja toinen piste koordinaateissa [235, 44].

Onneksi hilalta on helppoa löytää uusia pisteitä, koska kun lisäät ja vähennät kaksi hilapistettä, saat kolmannen pisteen samasta hilasta. Eli tarvitsee vain summata pisteet yhteen, tai kertoa niitä jollain kokonaisluvulla ja summata, tai jokin näiden kombinaatio. Tämän kun tekee kahdeksalla eri tavalla, voit vastata ystäväsi kysymykseen.

Mutta ystäväsi ei ole tyytyväinen. Hän antaa sinulle samat kaksi alkupistettä ja sitten pyytää etsimään pisteen lähellä origoa [0, 0] samasta hilasta. Tähän kysymykseen vastaamiseksi tarvitsee löytää pisteiden [101, 19] ja [235, 44] kombinaatio, jolla päästään lähelle pistettä [0, 0]. Tämä ongelma on paljon vaikeampi kuin ensimmäinen, ja todennäköisesti päädyt vain arvailemaan päästäksesi lähelle vastausta. Tällainen asymmetria on hilakryptografian taustalla.

Jos oikeasti haluat käyttää hilakryptografiaa informaation jakamiseen, se tapahtuisi seuraavalla tavalla. Kuvittele, että ystävä (läheisempi!) haluaa lähettää sinulle turvallisen viestin. Aloitat lukujen neliömäisellä hilalla. Oletetaan, että siinä on kaksi riviä ja kaksi saraketta:

Nyt keksit yksityisen “avaimen”, jonka vain sinä tiedät. Tässä esimerkissä oletamme, että yksityinen avain on kaksi salaista lukua: 3 ja  −2. Kerrot ensimmäisen sarakkeen numerot 3:lla ja jälkimmäisen -2:lla. Summaat tulokset yhteen ja saat kolmannen sarakkeen, jossa on kaksi lukua.

Laitat tämän uuden sarakkeen oman hilasi laidalle. Tämä kolmas sarake on julkinen avaimesi. Tätä voit levitellä vapaasti!

(Oikean elämän skenaario olisi monimutkaisempi. Jotta voisit pitää hakkerit loitolla dekoodaamasta yksityistä avainta, tähän pitää lisätä hieman satunnaiskohinaa viimeiseen sarakkeeseen. Mutta tässä sivuutamme sen yksinkertaisuuden vuoksi.)

Nyt ystäväsi käyttää julkista avainta lähettämään sinulle viestin. Hän keksii itselleen omat salaiset numerot: 2 ja 0. Hän kertoo ensimmäisen rivin luvut 2:lla ja jälkimmäisen 0:lla. Sitten hän summaa tuloksen yhteen ja saa kolmannen rivin.

Nyt hän liittää uuden rivin hilan alle ja lähettää sen takaisin sinulle. (Todellisessa systeemissä taaskin pitäisi lisätä kohinaa.)

Nyt voit lukea viestin. Katso ensin onko ystäväsi alin rivi oikein. Sovella omaa salaista avaintasi rivin kahteen ensimmäiseen lukuun. Tulokseksi pitäisi tulla viimeinen luku.

Ystäväsi voi myös valita lähettää sinulle rivin ja väärän luvun viimeisessä sarakkeessa. Hän tietää, että tämä numero ei sovi laskelmiin.

Jos ystäväsi lähettää rivin, jossa viimeinen luku on oikein, voit tulkita tämän nollaksi. Jos hän lähettää rivin joka on väärin, voit tulkita sen ykköseksi. Rivi tällä tavoin koodaa yksittäisen bitin: joko 0 tai 1.

Ulkopuolinen hyökkääjä ei pääse käsiksi joko yksityiseen avaimeesi tai ystäväsi yksityiseen avaimeen. Ilman niitä hyökkääjällä ei ole ideaa siitä onko loppuluku oikein vaiko ei.

Käytännössä viestit ovat pidempiä kuin yhden bitin mittaisia. Joten ihmiset generoivat esim. 100 uutta saraketta yhden sijaan. Sitten viestin lähettäjä luo yksittäisen uuden rivin ja näin yksi rivi koodaa joko ykkösen tai nollan jokaisella rivin sarakkeella.

Jos hilakryptografia toteutettaisiin oikeasti, siihen liittyy lukemattomia pikkujuttuja joita tässä skenaariossa ei käsitelty. Esimerkiksi, jos haluat viestin olevan oikeasti salassa muilta, matriisissa pitää olla uskomattoman paljon lukuja, mikä tekee koko hommasta niin sekavaa ettei sitä voi käyttää. Tämän kiertämiseksi tutkijat käyttävät matriiseja, joilla on käyttökelposia symmetrioita, jotka voivat pienentää parametrien lukumäärää. Tuon lisäksi on kokonainen kokoelma erilaisia säätöjä, joita voidaan soveltaa itse ongelmaan ja siihen tapaan millä virheitä käsitellään, sekä muuta.

Tottakai aina on mahdollista, että joku löytää virheen hilakryptografiassa, niinkuin Shor tekijöiksi hajottamisessa. Mitään varmuutta ei ole siitä, että jokin tietty kryptograafinen menetelmäi toimii mahdollisen hyökkäyksen iskiessä. Kryptografia toimii niin kauan kunnes se rikotaan. Aiemmin eräs lupaava kvanttien jälkeinen kryptografiamenetelmä murrettiin, eikä siihen käytetty edes kvanttitietokonetta vaan ihan tavallista läppäriä.Stangelle koko projekti on paradoksi: “Se mitä pidän kryptografiassa kiehtovana on, että me olemme rakentaneet tämmöisen infrastruktuurin ihmisrodulle siinä uskossa, että ihmiset olisivat rajoitteellisia”, hän sanoo. “Se on niin nurinkurista.”

 

Artikkelin julkaissut Quanta Magazine

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *

This site uses Akismet to reduce spam. Learn how your comment data is processed.