Beskrivning
1994, datavetaren Peter Shor upptäckt att om kvantdatorer någonsin uppfanns skulle de decimera mycket av den infrastruktur som används för att skydda information som delas online. Den skrämmande möjligheten har fått forskare att kämpa för att ta fram nya "post-quantum" krypteringssystem, för att rädda så mycket information de kunde från att hamna i händerna på kvanthackers.
Tidigare i år, National Institute of Standards and Technology avslöjade fyra finalister i sitt sökande efter en post-kvantkryptografistandard. Tre av dem använder "gitterkryptografi" - ett schema inspirerat av galler, regelbundna arrangemang av prickar i rymden.
Gitterkryptografi och andra postkvantmöjligheter skiljer sig från nuvarande standarder på avgörande sätt. Men de förlitar sig alla på matematisk asymmetri. Säkerheten för många nuvarande kryptografisystem är baserad på multiplikation och factoring: Vilken dator som helst kan snabbt multiplicera två tal, men det kan ta århundraden att inkludera ett kryptografiskt stort tal i dess primära beståndsdelar. Den asymmetrin gör hemligheter lätta att koda men svåra att avkoda.
Vad Shor avslöjade i sin algoritm från 1994 var att en egenhet med factoring gör den sårbar för attacker från kvantdatorer. "Det är en mycket specifik, speciell sak som kvantdatorn kan göra," sa Katherine Stange, en matematiker vid University of Colorado, Boulder. Så efter Shor hade kryptografer ett nytt jobb: Hitta en ny uppsättning matematiska operationer som är enkla att göra men nästan omöjliga att ångra.
Gitterkryptografi är ett av de mest framgångsrika försöken hittills. Ursprungligen utvecklad på 1990-talet, bygger den på svårigheten att göra omvänd konstruktion av poängsummor.
Här är ett sätt att beskriva gitterkryptografi: Föreställ dig att din vän har ett gitter, som bara är ett gäng punkter i ett vanligt, upprepande mönster över hela planet. Din vän vill att du ska nämna 10 av dessa punkter. Men han är svår, och han kommer inte att rita hela gallret. Istället listar han bara två punkter - den första med en x-värde 101 och en y-värde 19, den andra med koordinater [235, 44].
Som tur är är det lätt att hitta nya punkter på ett gitter, för när du adderar och subtraherar två punkter på ett gitter får du en tredje punkt i samma gitter. Så allt du behöver göra är att lägga ihop poängen som din vän gav dig, eller multiplicera dem med heltal och sedan lägga ihop dem, eller någon kombination av de två. Gör detta på åtta olika sätt och du kommer att kunna svara på din väns fråga.
Men din vän är fortfarande inte nöjd. Han ger dig samma två startpunkter och frågar dig sedan om punkten [2, 1] är på samma gitter. För att svara rätt på denna fråga måste du hitta kombinationen av [101, 19] och [235, 44] som ger [2, 1]. Det här problemet är mycket svårare än det första, och du kommer förmodligen bara att gissa och kolla för att få svaret.* Den asymmetrin är det som ligger till grund för gitterkryptografi.
Om du faktiskt vill använda gitterkryptografi för att dela information, skulle du göra följande. Föreställ dig att en vän (en trevligare!) vill skicka ett säkert meddelande till dig. Du börjar med ett kvadratiskt rutnät av tal. Säg att den har två rader och två kolumner och ser ut så här:
Nu kommer du på en privat "nyckel" som bara du känner till. I det här exemplet, låt oss säga att din privata nyckel bara är två hemliga nummer: 3 och −2. Du multiplicerar talen i den första kolumnen med 3 och talen i den andra kolumnen med −2. Lägg ihop resultaten i varje rad för att få en tredje kolumn med två poster.
Fäst den nya kolumnen på änden av ditt rutnät. Detta nya rutnät med tre kolumner är din publika nyckel. Dela det fritt!
(Ett scenario i verkligheten kommer att vara lite mer komplicerat. För att hindra hackare från att avkoda din privata nyckel måste du lägga till lite slumpmässigt brus i din sista kolumn. Men här kommer vi att ignorera det steget för enkelhetens skull. )
Nu kommer din vän att använda den offentliga nyckeln för att skicka ett meddelande till dig. Hon tänker på två egna hemliga siffror: 2 och 0. Hon multiplicerar talen i den första raden med 2 och talen i den andra raden med 0. Hon lägger sedan ihop resultaten i varje kolumn för att få en tredje rad.
Hon fäster nu den nya raden längst ner i rutnätet och skickar tillbaka den till dig. (Återigen, i ett riktigt system, skulle hon behöva lägga till lite ljud till sin rad.)
Nu ska du läsa meddelandet. För att göra detta kontrollerar du om din väns sista rad är korrekt. Använd din egen privata nyckel på de två första posterna i hennes rad. Resultatet bör matcha den senaste posten.
Din vän kan också välja att skicka dig en rad med fel nummer i den sista kolumnen. Hon vet att den här siffran inte stämmer överens med dina beräkningar.
Om din vän skickar en rad där den sista siffran är korrekt tolkar du detta som en 0. Om hon skickar en rad där numret är felaktigt tolkar du det som en 1. Raden kodar därför en singel bit: antingen 0 eller 1.
Observera att en utomstående angripare inte kommer att ha tillgång till varken din privata nyckel eller din väns. Utan dessa har angriparen ingen aning om det slutliga numret är korrekt eller inte.
I praktiken skulle du vilja skicka meddelanden som är längre än en bit långa. Så människor som vill ta emot, säg, ett 100-bitars meddelande kommer att generera 100 nya kolumner istället för bara en. Sedan kommer avsändaren av meddelandet att skapa en enda ny rad, och ändra de senaste 100 posterna för att koda antingen en 0 eller en 1 för varje post.
Om gitterkryptografi faktiskt implementeras kommer den att ha otaliga nyanser som inte täcks i detta scenario. Till exempel, om du vill att meddelandet verkligen ska vara säkert från nyfikna ögon, måste matrisen ha ett otänkbart antal poster, vilket gör det hela så otympligt att det inte är värt att använda. För att komma runt detta använder forskare matriser med användbara symmetrier som kan skära ner på antalet parametrar. Utöver det finns det en hel uppsättning justeringar som kan appliceras på själva problemet, på hur fel inkorporeras och mer.
Naturligtvis är det alltid möjligt att någon kommer att hitta ett fatalt fel i gitterkryptografi, precis som Shor gjorde för factoring. Det finns ingen garanti för att ett visst kryptografiskt system kommer att fungera inför eventuella attacker. Kryptografi fungerar tills det är knäckt. Faktiskt tidigare i sommar ett lovande post-kvantkryptografischema knäcktes använder inte en kvantdator, utan en vanlig bärbar dator. För Stange skapar hela projektet en obekväm paradox: "Det jag tycker är så fantastiskt med kryptografi är att vi har byggt den här infrastrukturen för mänskligheten på den fasta övertygelsen att vår förmåga som människor är begränsad", sa hon. "Det är så bakvänt."
*: Svaret, om du är nyfiken, är 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [tillbaka till artikeln]
