Introductie
In 1994, de computerwetenschapper Peter Shor ontdekt dat als kwantumcomputers ooit zouden worden uitgevonden, ze een groot deel van de infrastructuur zouden decimeren die wordt gebruikt om online gedeelde informatie te beschermen. Die angstaanjagende mogelijkheid heeft onderzoekers doen worstelen om nieuwe, "post-kwantum" encryptieschema's te ontwikkelen, om te voorkomen dat zoveel mogelijk informatie in de handen van kwantumhackers valt.
Eerder dit jaar publiceerde het National Institute of Standards and Technology onthuld vier finalisten in zijn zoektocht naar een post-kwantumcryptografiestandaard. Drie van hen gebruiken "roostercryptografie" - een schema geïnspireerd op roosters, regelmatige rangschikkingen van stippen in de ruimte.
Lattice-cryptografie en andere post-kwantummogelijkheden verschillen op cruciale punten van de huidige standaarden. Maar ze vertrouwen allemaal op wiskundige asymmetrie. De beveiliging van veel huidige cryptografiesystemen is gebaseerd op vermenigvuldigen en ontbinden: elke computer kan snel twee getallen vermenigvuldigen, maar het kan eeuwen duren om een cryptografisch groot getal in zijn hoofdbestanddelen te ontbinden. Die asymmetrie maakt geheimen gemakkelijk te coderen, maar moeilijk te decoderen.
Wat Shor in zijn algoritme uit 1994 onthulde, was dat een eigenaardigheid van factoring het kwetsbaar maakt voor aanvallen door kwantumcomputers. "Het is een heel specifiek, speciaal ding dat de kwantumcomputer kan doen," zei Katherine Stang, een wiskundige aan de Universiteit van Colorado, Boulder. Dus na Shor hadden cryptografen een nieuwe baan: een nieuwe reeks wiskundige bewerkingen vinden die gemakkelijk uit te voeren zijn, maar bijna onmogelijk ongedaan te maken.
Lattice-cryptografie is een van de meest succesvolle pogingen tot nu toe. Oorspronkelijk ontwikkeld in de jaren 1990, vertrouwt het op de moeilijkheid van reverse-engineering van puntensommen.
Hier is een manier om roostercryptografie te beschrijven: stel je voor dat je vriend een rooster heeft, wat gewoon een aantal punten is in een regelmatig, zich herhalend patroon over het hele vlak. Je vriend wil dat je 10 van deze punten noemt. Maar hij doet moeilijk, en hij wil niet het hele rooster tekenen. In plaats daarvan somt hij slechts twee punten op - de eerste met een x-waarde van 101 en een y-waarde van 19, de andere met coördinaten [235, 44].
Gelukkig is het gemakkelijk om nieuwe punten op een rooster te vinden, want als je twee willekeurige punten op een rooster optelt en aftrekt, krijg je een derde punt in hetzelfde rooster. Dus alles wat je hoeft te doen is de punten optellen die je vriend je heeft gegeven, of ze vermenigvuldigen met gehele getallen en ze dan optellen, of een combinatie van beide. Doe dit op acht verschillende manieren en je zult de vraag van je vriend kunnen beantwoorden.
Maar je vriend is nog steeds niet tevreden. Hij geeft je dezelfde twee startpunten en vraagt je vervolgens of het punt [2, 1] op hetzelfde rooster ligt. Om deze vraag correct te beantwoorden, moet je de combinatie van [101, 19] en [235, 44] vinden die [2, 1] oplevert. Dit probleem is veel moeilijker dan het eerste, en je zult waarschijnlijk alleen maar gissen en controleren om het antwoord te krijgen.* Die asymmetrie is wat ten grondslag ligt aan roostercryptografie.
Als u roostercryptografie daadwerkelijk wilt gebruiken om informatie te delen, doet u het volgende. Stel je voor dat een vriend (een aardigere!) je een beveiligd bericht wil sturen. Je begint met een vierkant raster van getallen. Stel dat het twee rijen en twee kolommen heeft en er zo uitziet:
Nu bedenk je een privé "sleutel" die alleen jij kent. Laten we in dit voorbeeld aannemen dat uw privésleutel uit slechts twee geheime nummers bestaat: 3 en −2. Je vermenigvuldigt de getallen in de eerste kolom met 3 en die in de tweede kolom met −2. Tel de resultaten in elke rij op om een derde kolom met twee ingangen te krijgen.
Plak de nieuwe kolom op het einde van je rooster. Dit nieuwe raster met drie kolommen is uw openbare sleutel. Deel het vrij!
(Een real-world scenario zal iets gecompliceerder zijn. Om te voorkomen dat hackers uw privésleutel decoderen, moet u een beetje willekeurige ruis toevoegen aan uw laatste kolom. Maar hier gaan we die stap negeren omwille van de eenvoud. )
Nu zal je vriend de openbare sleutel gebruiken om je een bericht te sturen. Ze bedenkt zelf twee geheime getallen: 2 en 0. Ze vermenigvuldigt de getallen in de eerste rij met 2 en die in de tweede rij met 0. Vervolgens telt ze de resultaten in elke kolom op om een derde rij te krijgen.
Ze bevestigt nu de nieuwe rij aan de onderkant van het rooster en stuurt deze naar jou terug. (Nogmaals, in een echt systeem zou ze wat ruis aan haar rij moeten toevoegen.)
Nu lees je het bericht. Om dit te doen, controleer je of de laatste rij van je vriend correct is. Pas uw eigen privésleutel toe op de eerste twee ingangen van haar rij. Het resultaat moet overeenkomen met de laatste invoer.
Je vriend kan er ook voor kiezen om je een rij te sturen met een verkeerd nummer in de laatste kolom. Ze weet dat dit aantal niet overeenkomt met je berekeningen.
Als uw vriend een rij stuurt waarvan het laatste cijfer correct is, interpreteert u dit als een 0. Als zij een rij stuurt waarvan het cijfer onjuist is, interpreteert u dit als een 1. De rij codeert dus een enkele bit: 0 of 1.
Houd er rekening mee dat een externe aanvaller geen toegang heeft tot uw privésleutel of die van uw vriend. Zonder deze heeft de aanvaller geen idee of het uiteindelijke getal correct is of niet.
In de praktijk wil je berichten versturen die langer zijn dan een bit lang. Dus mensen die bijvoorbeeld een 100-bits bericht willen ontvangen, genereren 100 nieuwe kolommen in plaats van slechts één. Vervolgens maakt de afzender van het bericht een enkele nieuwe rij, waarbij de laatste 100 ingangen worden gewijzigd om voor elke ingang een 0 of een 1 te coderen.
Als roostercryptografie daadwerkelijk wordt geïmplementeerd, zal het talloze nuances hebben die in dit scenario niet worden behandeld. Als u bijvoorbeeld wilt dat het bericht echt veilig is voor nieuwsgierige blikken, moet de matrix een ondenkbaar aantal ingangen hebben, waardoor het geheel zo log is dat het niet de moeite waard is om te gebruiken. Om dit te omzeilen, gebruiken onderzoekers matrices met bruikbare symmetrieën die het aantal parameters kunnen verminderen. Daarnaast is er een hele reeks tweaks die kunnen worden toegepast op het probleem zelf, op de manier waarop fouten worden verwerkt en meer.
Het is natuurlijk altijd mogelijk dat iemand een fatale fout vindt in roostercryptografie, net zoals Shor deed voor factoring. Er is geen garantie dat een bepaald cryptografisch schema zal werken bij een mogelijke aanval. Cryptografie werkt totdat het gekraakt is. Inderdaad, eerder deze zomer een veelbelovend post-kwantumcryptografieschema werd gekraakt niet met een kwantumcomputer, maar met een gewone laptop. Voor Stange creëert het hele project een ongemakkelijke paradox: "Wat ik zo verbazingwekkend vind aan cryptografie, is dat we deze infrastructuur voor de mensheid hebben gebouwd in de vaste overtuiging dat ons vermogen als mens beperkt is", zei ze. "Het is zo achterlijk."
*: Het antwoord, als je nieuwsgierig bent, is 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [terug naar artikel]
