Aloitan sarjan helppolukuisia päivittäisiä postauksia post-kvanttiturvallisuudesta. Mutta minulla ei ole aavistustakaan, kuinka monta päivää se kestää :). Katsotaanpa. PÄIVÄ 1: Shorin algoritmi ja kvanttimaailmanloppu(?) Suurin osa tietoturvapinostamme—RSA, ECC, Diffie-Hellman—perustuu yhteen oletukseen: kokonaislukujen faktorisointi ja diskreetit lokit ovat "vaikeita". Klassisella piillä ne ovat. RSA-2048:n murtamiseen tarvittaisiin yksinkertaisesti enemmän aikaa kuin universumin ikä. Mutta tämä ei ole fysiikan laki. Se on klassisen laskennan rajoitus. Vuonna 1994 Peter Shor osoitti, että ne voidaan ratkaista tehokkaasti kvanttitietokoneella. Shorin algoritmi ei vain käytä näppäimiä raakavoimalla; se käyttää kvantti-Fourier-muunnosta (QFT [ei kvanttikenttäteoriaa lol]) löytääkseen funktion f(x) = a^x mod N. Kun sinulla on kuukautiset, sinulla on tekijät. Ja kun sinulla on tekijät, yksityinen avain on kuollut. Koska yksityinen avain voidaan rekonstruoida julkisesta avaimesta. Monimutkaisuuden muutos on todellinen "maailmanloppu." Siirrymme alieksponentiaalisesta ajasta polynomiaikaan O((log N)^3). Emme puhu 10-kertaisesta nopeutuksesta; puhumme siirtymisestä biljoonista vuosista muutamaan tuntiin CRQC:ssä. Samoin kuin RSA, ECC (elliptinen käyräkryptografia) ei myöskään ole turvallinen. Tehokkaan algebrallisen ryhmärakenteensa ansiosta 256-bittisen ECC-avaimen murtaminen vaatii itse asiassa vähemmän loogisia kubittejä kuin RSA-2048. --- Kiitos lukemisesta! Huomenna keskustelemme siitä, miksi HNDL-uhka (harvest-now-decrypt-later) tarkoittaa, että post-kvanttisiirtymä on tapahduttava nyt. (Kuva: Peter Shor)