Quantumcomputers: het maken en breken van geheimschrift

Quantumcomputers: het maken en breken van geheimschrift

Al sinds de oudheid proberen mensen informatie te beschermen door het gebruik van geheime codes. Zo beschrijft Suetonius al een simpele manier die Julius Caesar gebruikte om zijn brieven te coderen: hij verving elke letter door de letter die drie plaatsen later in het alfabet komt. Dus elke ‘A’ wordt een ‘D’, elke ‘B’ wordt een ‘E’, enz. Hierdoor zag zijn tekst er voor een buitenstaander uit als wartaal, maar voor iemand die wist hoe Caesar de letters vervangen had, was de tekst makkelijk te decoderen. Sindsdien zijn er steeds betere systemen bedacht. De Duitsers gebruikten in de Tweede Wereldoorlog een ingewikkelde machine om hun communicatie mee te beveiligen, de beruchte ‘Enigma’. Het breken van deze code (door Alan Turing en anderen) hielp de geallieerden enorm, hierdoor wisten ze bijvoorbeeld waar de Duitse U-boten zich bevonden.

Vanaf de jaren ’70 wordt er systematisch wiskundig onderzoek gedaan naar ‘cryptografie’, de wetenschap van de versleuteling en beveiliging van informatie. Men realiseerde zich dat je coderingen kunt baseren op moeilijke wiskundige problemen. Zo is het makkelijk voor een computer om twee grote priemgetallen p en q met elkaar te vermenigvuldigen, maar is het moeilijk om een gegeven getal N te ontbinden in zijn priemfactoren. N=15 ontbinden in zijn priemfactoren 3 en 5 is nog wel te doen, maar als N heel groot is, bijvoorbeeld een getal van 1000 cijfers, dan kost het vinden van de priemfactoren zelfs met de beste methoden die we hebben veel te veel tijd.

Deze asymmetrie is de basis voor zogenaamde ‘public-key cryptography’. Hierbij kiest iemand die boodschappen wil ontvangen (laten we haar Alice noemen) twee sleutels: een publieke en een geheime sleutel. Iedereen kan de publieke sleutel zien, Alice kan hem bijvoorbeeld op haar publieke homepage zetten, en kan hiermee berichten aan Alice coderen; maar alleen wie in het bezit is van de geheime sleutel (Alice zelf dus) kan die berichten ook decoderen. Dit soort encryptie werkt, simpel gezegd, omdat je voor encodering alleen N nodig hebt (de publieke sleutel), maar voor decodering ook de priemfactoren p en q van N (de geheime sleutel). In principe zit alle informatie over de geheime sleutel al besloten ín de publieke sleutel, maar voor zover we weten hebben de huidige computers honderden jaren nodig om een getal N van bijvoorbeeld 1000 cijfers te ontbinden in zijn priemfactoren. Dat lijkt dus redelijk veilig – zo veilig dat allerlei geheime berichten, betalingsverkeer, e-commerce enz. tegenwoordig op deze manier versleuteld worden. Dit is een frappant voorbeeld van hoe grote praktische (en kostbare!) systemen soms gebaseerd zijn op een onbewezen wiskundig vermoeden. Misschien is er onverwachts toch nog een slimme methode waarmee de huidige computers snel grote getallen kunnen factoriseren, maar waarschijnlijk lijkt dat niet.

Maar wat zijn ‘de huidige computers’? Simpel gezegd zijn die gebaseerd op de klassieke natuurkunde van vóór 1900, waarin objecten duidelijk omschreven eigenschappen hebben: een specifieke locatie, snelheid, massa, enz. Zo horen de bits in het geheugen van een computer 0 of 1 te zijn, en niet allebei tegelijk. Maar de moderne natuurkunde, vooral de quantummechanica die na 1900 is ontwikkeld, heeft een heel ander wereldbeeld. Volgens de quantummechanica kunnen allerlei mogelijkheden naast elkaar bestaan, elk met een ‘amplitude’, een soort gewicht (wat zelfs negatief kan zijn!). Dit naast elkaar bestaan van allerlei mogelijkheden heet een ‘superpositie’. Doordat sommige amplitudes in een superpositie negatief kunnen zijn, kunnen er allerlei vreemde effecten optreden als we superposities combineren, net zoals golven elkaar kunnen versterken maar ook elkaar kunnen uitdoven.

Sinds het werk van Richard Feynman en David Deutsch in de jaren ’80 wordt ook onderzocht of je computers veel sneller kunt maken door middel van dit soort quantumeffecten. In sommige gevallen blijkt dit inderdaad mogelijk: quantumcomputers kunnen gigantisch veel berekeningen tegelijk doen, in superpositie, en in sommige (maar lang niet alle!) gevallen kan het eindantwoord van de berekening gevonden worden door een slimme meting te doen op de opgebouwde superpositie. We weten nog steeds niet zoveel van de mogelijkheden en beperkingen van quantumcomputers, maar Peter Shor ontdekte in 1994 al dat zo’n computer heel snel grote getallen in hun priemfactoren kan ontbinden – en dus die veelgebruikte versleuteling kan breken! Het is dan ook geen wonder dat behalve wetenschappers ook veel geheime diensten een opvallende interesse hebben in quantum computing. Tot nu toe zijn er nog geen grote quantumcomputers gebouwd, maar experimenteel natuurkundigen zijn hard aan het werk om dit mogelijk te maken, en wanneer dat eenmaal zover is dan valt veel van de huidige versleuteling in duigen. Ook wanneer er pas over bijvoorbeeld twintig jaar een grote quantumcomputer beschikbaar komt, dan zouden we daar nu al rekening mee moeten houden voor berichten die lang geheim moeten blijven: elk versleuteld bericht dat we nu versturen en dat nu door iemand wordt opgeslagen, kan dan over twintig jaar gedecodeerd en gelezen worden.

Gelukkig helpt de quantummechanica niet alleen bij het *breken* van sommige versleutelingen, maar maakt zij ook andere coderingen mogelijk die zelfs veilig zijn tegen spionnen die zelf een quantumcomputer hebben. Al in 1984 bedachten Charles Bennett en Gilles Brassard een manier waarop Alice en Bob via communicatie over een quantumkanaal een geheime sleutel kunnen delen, het zogenaamde ‘BB84’-systeem. Dit is gebaseerd op het fundamentele principe dat een quantumtoestand verstoord wordt als je hem meet: als de spion informatie over de sleutel probeert te krijgen door de quantumcommunicatie te meten, dan verstoort hij de quantumtoestanden en kunnen Alice en Bob hem detecteren. De geheime sleutel die ze op deze manier kunnen krijgen, kunnen Alice en Bob vervolgens gebruiken om veilig met elkaar te communiceren. De spion krijgt dan gegarandeerd geen informatie over de inhoud van het verstuurde bericht, ook niet wanneer hij nu of later de beschikking heeft over een quantumcomputer. De quantumoperaties die Alice en Bob nodig hebben voor BB84 zijn relatief simpel, veel simpeler dan die voor een algemene quantumcomputer, en liggen zelfs binnen het bereik van de huidige technologie. Je kunt tegenwoordig zelfs al zo’n BB84-systeem kopen, al zitten er nog allerlei praktische beperkingen aan.

Of er op termijn daadwerkelijk een grote quantumcomputer gebouwd kan worden is nog steeds een open vraag, maar ook nu al hebben deze ideeën veel invloed op hoe we informatie geheim proberen te houden: klassieke cryptografen proberen varianten van public-key cryptography te vinden die niet gekraakt kunnen worden door quantumcomputers, en aan de andere kant zullen quantumbeveiligingssystemen zoals BB84 waarschijnlijk steeds meer gebruikt gaan worden.

Ronald de Wolf

 

Ronald de Wolf studeerde informatica en filosofie aan de Erasmus Universiteit in Rotterdam en promoveerde in de informatica aan het Centrum Wiskunde en Informatica (CWI) en de Universiteit van Amsterdam. Na een aantal jaren als postdoc in Berkeley en het CWI is hij nu senior researcher aan het CWI en professor aan de Universiteit van Amsterdam. Zijn onderzoek richt zich op de theoretische informatica, met name quantum computing en complexiteitstheorie.

Leave a Reply

Your email address will not be published. Required fields are marked *