esittely
Vuonna 1994 tietojenkäsittelytieteilijä Peter Shor löysi että jos kvanttitietokoneita koskaan keksittäisiin, ne tuhoaisivat suuren osan verkossa jaetun tiedon suojaamiseen käytetystä infrastruktuurista. Tämä pelottava mahdollisuus on saanut tutkijat yrittämään tuottaa uusia "post-kvantti" salausjärjestelmiä, säästääkseen mahdollisimman paljon tietoa joutumasta kvanttihakkereiden käsiin.
Aiemmin tänä vuonna National Institute of Standards and Technology paljasti neljä finalistia etsiessään post-kvanttisalausstandardia. Kolme niistä käyttää "hila kryptografiaa" - hilasta, säännöllisistä pisteiden järjestelyistä avaruudessa inspiroitunutta järjestelmää.
Hila kryptografia ja muut post-kvanttimahdollisuudet poikkeavat nykyisistä standardeista ratkaisevalla tavalla. Mutta he kaikki luottavat matemaattiseen epäsymmetriaan. Monien nykyisten salausjärjestelmien turvallisuus perustuu kertolaskuun ja tekijöihin: Mikä tahansa tietokone voi nopeasti kertoa kaksi lukua, mutta voi kestää vuosisatoja, ennen kuin kryptografisesti suuri luku otetaan huomioon sen tärkeimpiin ainesosiin. Tämä epäsymmetria tekee salaisuuksista helppo koodata, mutta vaikea purkaa.
Shor paljasti vuoden 1994 algoritmissaan, että factoringin omituisuus tekee siitä alttiin kvanttitietokoneiden hyökkäyksille. "Se on hyvin erityinen, erityinen asia, jonka kvanttitietokone voi tehdä", sanoi Katherine Stange, matemaatikko Coloradon yliopistosta, Boulderista. Joten Shorin jälkeen kryptografeilla oli uusi tehtävä: löytää uusi joukko matemaattisia operaatioita, jotka on helppo tehdä, mutta melkein mahdotonta kumota.
Hilasalaus on yksi menestyneimmistä yrityksistä tähän mennessä. Se kehitettiin alun perin 1990-luvulla, ja se perustuu pistesummien käänteissuunnittelun vaikeuteen.
Tässä on yksi tapa kuvata hila kryptografiaa: Kuvittele, että ystävälläsi on hila, joka on vain joukko pisteitä säännöllisessä, toistuvassa kuviossa kaikkialla tasossa. Ystäväsi haluaa sinun nimeävän 10 näistä kohdista. Mutta hän on vaikea, eikä hän piirrä koko hilaa. Sen sijaan hän luettelee vain kaksi kohtaa - ensimmäinen, jossa on an x-arvo 101 ja a y-arvo 19, toinen koordinaattein [235, 44].
Onneksi hilasta on helppo löytää uusia pisteitä, koska kun lisäät ja vähennät mitkä tahansa kaksi pistettä hilassa, saat kolmannen pisteen samaan hilaan. Joten sinun tarvitsee vain laskea yhteen ystäväsi antamat pisteet tai kertoa ne kokonaisluvuilla ja sitten laskea yhteen, tai jokin näiden kahden yhdistelmä. Tee tämä kahdeksalla eri tavalla, niin voit vastata ystäväsi kysymykseen.
Mutta ystäväsi ei ole vieläkään tyytyväinen. Hän antaa sinulle kaksi samaa lähtökohtaa ja kysyy sitten, onko piste [2, 1] samassa hilassa. Vastataksesi tähän kysymykseen oikein, sinun on löydettävä [101, 19] ja [235, 44] yhdistelmä, joka tuottaa [2, 1]. Tämä ongelma on paljon vaikeampi kuin ensimmäinen, ja luultavasti päädyt vain arvailemaan ja tarkistamaan saadaksesi vastauksen.* Tämä epäsymmetria on hila kryptografian taustalla.
Jos todella haluat käyttää hilakalausta tiedon jakamiseen, toimi seuraavasti. Kuvittele, että ystävä (mukavampi!) haluaa lähettää sinulle suojatun viestin. Aloitat numeroiden neliöruudukosta. Oletetaan, että siinä on kaksi riviä ja kaksi saraketta, ja se näyttää tältä:
Nyt keksit yksityisen "avaimen", jonka vain sinä tiedät. Oletetaan tässä esimerkissä, että yksityinen avaimesi on vain kaksi salaista numeroa: 3 ja −2. Kerrot ensimmäisen sarakkeen luvut kolmella ja toisen sarakkeen luvut −3:lla. Laske kunkin rivin tulokset yhteen saadaksesi kolmannen sarakkeen, jossa on kaksi merkintää.
Kiinnitä uusi sarake ruudukon päähän. Tämä uusi kolmisarakkeinen ruudukko on julkinen avaimesi. Jaa se vapaasti!
(Tosimaailman skenaario on hieman monimutkaisempi. Jotta hakkerit eivät dekoodaa yksityistä avaimesi, sinun on lisättävä viimeiseen sarakkeeseen hieman satunnaista kohinaa. Mutta tässä jätämme tämän vaiheen huomiotta yksinkertaisuuden vuoksi. )
Nyt ystäväsi käyttää julkista avainta lähettääkseen sinulle viestin. Hän ajattelee kahta omaa salaista numeroa: 2 ja 0. Hän kertoo ensimmäisen rivin luvut 2:lla ja toisen rivin luvut nollalla. Sitten hän laskee kunkin sarakkeen tulokset yhteen saadakseen kolmannen rivin.
Hän kiinnittää nyt uuden rivin ruudukon alaosaan ja lähettää sen takaisin sinulle. (Taas kerran, todellisessa järjestelmässä hänen pitäisi lisätä melua riviinsä.)
Nyt luet viestin. Voit tehdä tämän tarkistamalla, onko ystäväsi viimeinen rivi oikein. Käytä omaa yksityistä avaimesi rivin kahteen ensimmäiseen merkintään. Tuloksen tulee vastata viimeistä syötettä.
Ystäväsi voi myös lähettää sinulle rivin, jonka viimeisessä sarakkeessa on väärä numero. Hän tietää, että tämä luku ei vastaa laskelmiasi.
Jos ystäväsi lähettää rivin, jossa viimeinen numero on oikein, tulkitset tämän nollaksi. Jos hän lähettää rivin, jossa numero on väärä, tulkitset sen 0:ksi. Rivi siis koodaa yksittäisen bitti: joko 1 tai 0.
Huomaa, että ulkopuolisella hyökkääjällä ei ole pääsyä yksityiseen avaimesi tai ystäväsi avaimeen. Ilman niitä hyökkääjällä ei ole aavistustakaan, onko lopullinen luku oikea vai ei.
Käytännössä haluat lähettää viestejä, jotka ovat pitkiä kuin yhden bitin. Joten ihmiset, jotka haluavat saada esimerkiksi 100-bittisen viestin, luovat 100 uutta saraketta yhden sijasta. Sitten viestin lähettäjä luo yhden uuden rivin ja muokkaa viimeiset 100 merkintää niin, että jokaiselle merkinnälle on joko 0 tai 1.
Jos ristikkosalaus todella toteutetaan, siinä on lukemattomia vivahteita, joita tämä skenaario ei kata. Jos esimerkiksi haluat viestin olevan todella turvassa uteliailta silmiltä, matriisissa on oltava käsittämätön määrä merkintöjä, mikä tekee kokonaisuudesta niin hankalan, ettei sitä kannata käyttää. Tämän kiertämiseksi tutkijat käyttävät matriiseja, joilla on hyödyllinen symmetria, joka voi vähentää parametrien määrää. Tämän lisäksi on olemassa koko joukko parannuksia, joita voidaan soveltaa itse ongelmaan, tapaan, jolla virheet sisällytetään, ja paljon muuta.
Tietysti on aina mahdollista, että joku löytää kohtalokkaan virheen hila kryptografiassa, aivan kuten Shor teki factoringissa. Ei ole takeita siitä, että tietty salausjärjestelmä toimii mahdollisen hyökkäyksen edessä. Salaus toimii, kunnes se murtuu. Itse asiassa aiemmin tänä kesänä yksi lupaava post-kvanttisalausjärjestelmä murtui käyttämällä ei kvanttitietokonetta, vaan tavallista kannettavaa tietokonetta. Stangelle koko projekti luo epämiellyttävän paradoksin: "Minusta salakirjoituksessa niin hämmästyttävää on se, että olemme rakentaneet tämän infrastruktuurin ihmiskunnalle vakaalla uskolla, että kykymme ihmisinä ovat rajalliset", hän sanoi. "Se on niin taaksepäin."
*: Vastaus, jos olet utelias, on 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [takaisin artikkeliin]
