Kvanttitietokone arvaa pankkitunnuksesi

Näyttää siis siltä, että pian tarvitaan uudenlaisia keinoja pitää luottamukselliset tiedot salassa. Onneksi kvanttimekaniikka voi auttaa siinäkin.

Edessä on siis kilpailu, jossa salauskoodien kehittäjät ja niiden murtajat käyttävät samoja hiukkasfysiikan maailmasta lainattuja välineitä.

Salauksen pitkä historia

Tietojen salaajien ja salauksen murtajien välinen kilpajuoksu alkoi jo kauan ennen nykyistä ajanlaskuamme. Aina kun on keksitty uusi tapa piilottaa tärkeitä tietoja ulkopuolisilta, on ollut vain ajan kysymys, milloin joku on keksinyt tavan kaivaa tiedot esiin.

Vuonna 1977 kilpailussa siirryttiin uuteen vaiheeseen, kun matemaatikot Ron Rivest, Adi Shamir ja Len Adleman kehittivät uuden salausmenetelmän, jota alettiin kutsua heidän sukunimiensä alkukirjainten mukaan RSA-salaukseksi.

RSA-järjestelmä perustuu kahteen avaimeen, joilla viestin sisältö salataan ja salaus avataan.

Viestin lähettäjä käyttää julkista salausavainta. Se muuttaa esimerkiksi tavallisen tekstin salakieliseksi. Salakielinen viesti voi päätyä ulkopuolisten haltuun, mutta he eivät saa muutettua sitä ymmärrettävään muotoon, vaikka heillä olisi julkinen avain.

Salakielisen viestin tulkitsemiseen tarvitaan salainen avain, joka on vain viestin vastaanottajalla.

RSA-salauksen matemaattinen perusta ovat alkuluvut eli luvut, jotka ovat jaollisia vain ykkösellä ja itsellään. Alkulukuja ovat muun muassa 2, 3, 5, 7, 11, 13 ja 17 – ja vähän isommista luvuista 971, 977, 983, 991 ja 997.

RSA-salauksen avainten luomiseen käytettään kuitenkin huomattavasti isompia, usein yli 100-numeroisia, alkulukuja. Salauksen julkinen avain muodostetaan niin sanotusta RSA-luvusta, joka saadaan kertomalla kaksi alkulukua keskenään. Salainen avain taas perustuu sekä RSA-lukuun että alkuperäisiin kahteen alkulukuun.

Salauksen teho perustuu siihen, että avainten muodostaminen on helppoa, mutta salaisen avaimen päätteleminen julkisesta on lähes mahdotonta.

Kaksi alkulukua on helppo kertoa keskenään, mutta on äärimmäisen hankalaa päätellä tulosta, mitkä luvut kerrottiin keskenään. Päättelyprosessia kutsutaan faktoroinniksi, ja siihen tarvitaan valtavasti laskentatehoa ja paljon aikaa.

Salausavaimet, joilla internetissä liikkuva tieto on suojattu, on laskettu niin isoista alkuluvuista, että nopeimmiltakin supertietokoneilta menee niiden murtamiseen tuhansia vuosia.

Tutkijat ovat kuitenkin yhtä mieltä siitä, että RSA-salausjärjestelmän loppu lähenee. Pian hakkereilla on käytössään uusi ase: kvanttitietokone.

Kvanttitietokone avaa hakkerille aivan uusia mahdollisuuksia, koska sitä ei jarruta tavallisten tietokoneiden klassinen rajoite.

Kaikki nykytietotekniikka, niin kännykät kuin supertietokoneetkin, perustuu binaariseen koodiin eli ykkösiin ja nolliin. Tietotekniikan perusyksikkö, bitti, voi olla vain yhdessä tilassa kerrallaan: ykkösenä tai nollana.

Kvanttitietokoneen bittiä kutsutaan kubitiksi. Sillä on ominaisuuksia, joita esiintyy vain kvanttimekaniikan maailmassa. Siellä atomia pienemmät hiukkaset, kuten elektronit ja fotonit, voivat olla niin sanotussa superpositiossa eli ne ovat monessa tilassa samanaikaisesti.

Kubitti voi siis olla ykkönen tai nolla mutta myös jotakin niiden väliltä. Tämä ominaisuus antaa kvanttitietokoneelle huiman laskentatehon.

Salausmenetelmien kehittäjät pelkäävätkin, että kvanttitietokoneet romuttavat RSA-salauksen suojan. Äskettäin kiinalaistutkijat osoittivat kokeellaan, että pelko on aiheellinen.

Kovinkin salaus uhattuna

Koetta johti Bao Yan Kiinan valtion matematiikan ja tietojenkäsittelyn tutkimuslaitoksesta. Hän oli kollegojensa kanssa kehittänyt algoritmin, joka osaa faktoroida RSA-lukuja jakamalla mutkikkaan laskutoimituksen niin, että osan siitä tekee tavallinen tietokone ja osan kvanttitietokone.

Kvanttitietokone hoitaa vain laskemisen aikaa vievimmän osan, joten tehtävään tarvittavien kubittien määrää voidaan vähentää.

Kiinalaistutkijat saivat kolmella kubitilla faktoroitua luvun 1 961 ja viidellä kubitilla luvun 48 567 227. Kymmenellä kubitilla he onnistuvat palauttamaan kahteen alkulukutekijäänsä luvun 261 980 999 226 229.

Bao Yan kollegoineen uumoilee tutkimusraportissaan, että tämä on vasta alkua.

”Uskomme, että 372 kubitin kvanttipiiri pystyy haastamaan RSA-2048:n.”

RSA-2048 on suurin tunnettu RSA-luku. Siinä on 617 numeroa, ja sitä pidetään RSA-salauksen kovimpana koodina. Nimensä mukaisesti sen kuvaamiseen binaarikoodilla tarvitaan 2 048 bittiä.

RSA-2048 julkistettiin vuonna 1991 yhdessä 53 muun ison RSA-luvun kanssa. Sen loi yhdysvaltalaisyritys RSA Laboratories, joka osallistui ”RSA Factoring Challenge” -kilpailuun.. Kilpailun tarkoitus oli kannustaa matemaatikkoja yrittämään RSA-salauksen murtamista. Samalla haluttiin esitellä julkisuudessa RSA-salausmenetelmän turvallisuutta.

Palkinnoksi RSA-salauslukujen faktoroimisesta luvattiin isoja summia rahaa. Esimerkiksi RSA-2048:n murtamisesta oli tarjolla 200 000 dollarin palkkio.

Kilpailu päättyi vuonna 2007, mutta sen 54 RSA-luvusta 31 on yhä murtamatta.

Suurin tähän mennessä faktoroitu RSA-luku on 250-numeroinen. Sen mursivat vuonna 2020 ranskalaiset ja yhdysvaltalaiset tutkijat. Faktorointiin meni vain kuukausia, mutta työhön osallistui kymmeniätuhansia tietokoneita. Yhdeltä tietokoneelta olisi mennyt urakkaan huimat 2 700 vuotta.

RSA-2048:n 617 numeroon on vielä matkaa. Todennäköisesti sitä ei ole mahdollista faktoroida kohtuullisen ajan kuluessa tavallisilla tietokoneilla, vaan siihen tarvitaan kvanttitietokoneiden apua.

Yhdysvaltalainen matemaatikko Peter Shor esitteli jo vuonna 1994 algoritmin, jonka avulla kvanttitietokoneet periaatteessa voivat faktoroida isojakin RSA-lukuja lyhyessä ajassa. Sittemmin muut tutkijat ovat osoittaneet, että algoritmi toimii myös käytännössä – vaikkakin toistaiseksi vain hyvin pienillä luvuilla. Suurin luku, jonka se on saanut faktoroitua on 21. Se saadaan kertomalla 3 ja 7 keskenään.

Shorin algoritmin ongelma on se, että se tarvitsee äärimmäisen paljon kubitteja toimiakseen luotettavasti. RSA-2048:n murtamiseen se tarvitsisi arviolta miljardia kubittia.

Vuonna 2021 tutkijat saivat yksinkertaistettua Shorin algoritmia niin, että se voisi pystyä faktoroimaan RSA-2028:n 20 miljoonalla kubitilla. Sekin on paljon. Tällä hetkellä suurimmassa kvanttitietokoneessa, IBM:n Ospreyssa, oli viime vuonna 433 kubittia.

Uusi kiinalaistutkimus näyttää siis muuttavan tilanteen täysin. Jos Bao Yan kollegoineen on oikeassa ja 372 kubittia riittää, RSA-2048:n murtuminen voi olla käsillä paljon luultua aikaisemmin: ehkä jo kymmenen vuoden kuluessa.

Fotonit pitävät salaisuudet suojassa

Jos tai kun RSA-2048 murtuu, verkossa kulkevat tiedot eivät enää ole turvassa. Siksi RSA-salauksen tilalle tarvitaan uusi ratkaisu.

Paras ratkaisu olisi sellainen, joka perustuu hiukkasfysiikan maailman erityispiirteisiin samalla tavalla kuin kvanttitietokone. Tieto onkin salattavissa niin, että sitä ei saa esiin kukaan muu kuin luvallinen vastaanottaja. Menetelmän ydin on fotonien polarisaatio.

Jos hakkeri pääsisi käsiksi lähettäjältä vastaanottajalle matkalla oleviin fotoneihin, niiden polarisaatio muuttuisi niin, että tietomurto paljastuisi vastaanottajalle.

Kvanttisalauksen etu on se, että siihen tarvittava tekniikka on jo olemassa. Tietoliikenne kulkee jo nyt fotoneina valokuitukaapeleissa.

Vielä tarvitaan kuitenkin lähetys- ja vastaanottolaitteisto, joka on niin pieni ja edullinen, että se voidaan liittää kaikkiin tietoverkon osiin, joissa liikkuu salattavaa tietoa.

Uuden koodauslaitteiston kehittämisellä alkaa olla jo kiire. RSA-salaus, joka on turvannut tiedonsiirron neljä vuosikymmentä, on tulossa tiensä päähän, ja hakkereilla on käytössään samat kvanttityökalut kuin salaustekniikoiden kehittäjilläkin.