Quantum Computers: het einde van cryptografie?

Advertentie

Quantum computing is een van die technologieën die zo mysterieus is dat de naam van tv-personages het laat vallen als ze slim willen klinken.

Quantum computing als idee bestaat al een tijdje - de theoretische mogelijkheid werd oorspronkelijk geïntroduceerd door Yuri Manin en Richard Feynman in 1982. In de afgelopen jaren is het veld echter verontrustend dichter bij de bruikbaarheid gekomen.

Zowel bedrijven als Google en Microsoft als overheidsinstanties zoals de NSA streven al jaren koortsachtig naar quantumcomputers. Een bedrijf genaamd D-Wave heeft apparaten geproduceerd en verkoopt die (hoewel het geen echte computers zijn, dat wel kunnen slechts een paar algoritmen uitvoeren) gebruik maken van kwantumeigenschappen en zijn een volgende stap op weg naar a ten volle Turing-compleet Wat is de Turing-test en zal deze ooit worden verslagen?De Turing Test is bedoeld om te bepalen of machines denken. Heeft het Eugene Goostman-programma de Turing-test echt doorstaan ​​of hebben de makers gewoon vals gespeeld? Lees verder quantum machine.

Het lijkt niet onredelijk om te zeggen dat er doorbraken kunnen plaatsvinden waardoor de eerste grootschalige quantumcomputer binnen tien jaar kan worden gebouwd.

Dus waarom al die interesse? Waarom zou je erom geven? Computers worden steeds sneller Wat is de wet van Moore en wat heeft deze met jou te maken? [MakeUseOf Explains]Pech heeft niets te maken met de wet van Moore. Als dat de associatie was die je had, verwar je die met de wet van Murphy. Je was echter niet ver weg omdat de wet van Moore en de wet van Murphy ... Lees verder - wat is er zo speciaal aan quantumcomputers?

Om uit te leggen waarom deze machines zo belangrijk zijn, moeten we een stap terug doen en onderzoeken wat quantumcomputers precies zijn en waarom ze werken. Laten we om te beginnen eens praten over een concept genaamd 'runtime complexity'.

Wat is Runtime-complexiteit?

Een van de grote verrassingen in de begintijd van de informatica was de ontdekking dat, als je een computer hebt die een probleem van een bepaalde grootte in een bepaalde tijd, verdubbeling van de snelheid van de computer betekent niet noodzakelijkerwijs dat het problemen twee keer zo vaak aanpakt groot.

Sommige algoritmen verhogen de totale uitvoeringstijd heel, heel snel naarmate de omvang van het probleem toeneemt - sommige algoritmen kunnen snel worden voltooid gegeven 100 datapunten, maar het voltooien van het algoritme gegeven 1000 datapunten zou een computer ter grootte van de aarde nodig hebben voor een miljard jaar. Runtime-complexiteit is een formalisering van dit idee: het kijkt naar de curve van hoe snel de complexiteit van een probleem toeneemt en gebruikt de vorm van die curve om het algoritme te classificeren.

Over het algemeen worden deze moeilijkheidsgraden uitgedrukt als functies. Een algoritme dat verhoudingsgewijs moeilijker wordt wanneer de gegevensset waaraan het werkt toeneemt (zoals een eenvoudige telfunctie), zou een functie zijn met een runtime-complexiteit van "n " (zoals in, het duurt n te verwerken tijdseenheden n data punten).

Een andere mogelijkheid is dat het 'lineair' wordt genoemd, want als je het tekent, krijg je een rechte lijn. Andere functies zijn mogelijk n ^ 2 of 2 ^ n of n! (n faculteit). Deze zijn polynoom en exponentieel. In de laatste twee gevallen groeien de exponentiële gevallen zo snel dat ze in bijna alle gevallen voor niets anders kunnen worden opgelost dan voor zeer triviale voorbeelden.

Runtime-complexiteit en cryptografie

Als je dit spul voor het eerst hoort en het klinkt zinloos en geheimzinnig, laten we proberen deze discussie te gronden. Runtime-complexiteit is van cruciaal belang voor cryptografie, die afhankelijk is van het veel gemakkelijker maken van decodering voor mensen die een geheime sleutel kennen dan voor degenen die dat niet weten. In een ideaal cryptografisch schema zou decodering lineair moeten zijn als je de sleutel hebt, en 2 ^ k (waarbij k het aantal bits in de sleutel is) als je dat niet doet.

Met andere woorden, het beste algoritme voor het ontsleutelen van het bericht zonder de sleutel zou simpelweg mogelijke sleutels moeten raden, wat onhandelbaar is voor sleutels van slechts een paar honderd bits lang.

Voor symmetrische sleutelcryptografie (waarbij de twee partijen de kans hebben om een ​​geheim veilig uit te wisselen voordat ze beginnen met communiceren) is dit vrij eenvoudig. Voor asymmetrische cryptografie is het moeilijker.

Asymmetrische cryptografie, waarbij de coderings- en decoderingssleutels verschillend zijn en niet gemakkelijk van elkaar kunnen worden berekend, is een veel moeilijkere wiskundige structuur die moet worden geïmplementeerd dan symmetrische cryptografie, maar het is ook een stuk krachtiger: met asymmetrische crypto kunt u privégesprekken voeren, zelfs als u teveel tikt lijnen! U kunt er ook 'digitale handtekeningen' mee maken, zodat u kunt verifiëren van wie een bericht afkomstig is en of er niet mee is geknoeid.

Dit zijn krachtige tools die de basis vormen van moderne privacy: zonder asymmetrische cryptografie zouden gebruikers van elektronische apparaten geen betrouwbare bescherming hebben tegen nieuwsgierige blikken.

Omdat asymmetrische cryptografie moeilijker te bouwen is dan symmetrisch, zijn de standaardversleutelingsschema's die tegenwoordig worden gebruikt niet zo sterk zoals ze zouden kunnen zijn: de meest voorkomende versleutelingsstandaard, RSA, kan worden gekraakt als je de belangrijkste factoren van een zeer grote aantal. Het goede nieuws is dat dat een heel moeilijk probleem is.

Het bekendste algoritme voor het in rekening brengen van grote getallen in hun samengestelde priemgetallen wordt de algemene getalsveldzeef genoemd en heeft een runtime-complexiteit die iets langzamer groeit dan 2 ^ n. Als gevolg hiervan moeten sleutels ongeveer tien keer langer zijn om vergelijkbare beveiliging te bieden, iets dat mensen normaal gesproken tolereren als kosten van zakendoen. Het slechte nieuws is dat het hele speelveld verandert wanneer kwantumcomputers in de mix worden gegooid.

Quantum Computers: het Crypto-spel veranderen

Quantumcomputers werken omdat ze meerdere interne toestanden tegelijk kunnen hebben, door een kwantumfenomeen dat 'superpositie' wordt genoemd. Dat betekent dat ze verschillende delen van een probleem tegelijkertijd kunnen aanvallen, verdeeld over mogelijke versies van het universum. Ze kunnen ook zo worden geconfigureerd dat de takken die het probleem oplossen met de grootste amplitude eindigen, zodat wanneer u de doos opent op Schrodinger's kat, de versie van de interne staat die je waarschijnlijk te zien krijgt, is een zelfvoldane kat met een ontsleutelde bericht.

Voor meer informatie over quantumcomputers, check out ons recente artikel over dit onderwerp Hoe werken optische en kwantumcomputers?Het Exascale-tijdperk komt eraan. Weet u hoe optische en kwantumcomputers werken en zullen deze nieuwe technologieën onze toekomst worden? Lees verder !

Het resultaat hiervan is dat kwantumcomputers niet alleen lineair sneller zijn, zoals normale computers: twee of tien of honderd krijgen keer sneller helpt niet veel als het gaat om conventionele cryptografie dat je honderden miljarden keren te traag bent om te verwerken. Quantumcomputers ondersteunen algoritmen met een kleiner groeiende runtime-complexiteit dan anders mogelijk zou zijn. Dit is wat quantumcomputers fundamenteel anders maakt dan andere toekomstige computationele technologieën, zoals berekening van grafeen en memrister De nieuwste computertechnologie die u moet zien om te gelovenBekijk enkele van de nieuwste computertechnologieën die de wereld van elektronica en pc's de komende jaren zullen transformeren. Lees verder .

Voor een concreet voorbeeld kan Shor’s algoritme, dat alleen kan worden uitgevoerd op een kwantumcomputer, grote getallen in rekening brengen logboek (n) ^ 3 tijd, die drastisch beter is dan de beste klassieke aanval. Het gebruik van de algemene zeef voor het berekenen van een getal met 2048 bits kost ongeveer 10 ^ 41 tijdseenheden, wat neerkomt op meer dan een biljoen biljoen biljoen. Met behulp van het Shor-algoritme duurt hetzelfde probleem slechts ongeveer 1000 tijdseenheden.

Het effect wordt sterker naarmate de toetsen langer zijn. Dat is de kracht van kwantumcomputers.

Begrijp me niet verkeerd - kwantumcomputers hebben veel potentiële niet-kwaadaardige toepassingen. Quantumcomputers kunnen het handelsreizigersprobleem efficiënt oplossen, waardoor onderzoekers efficiëntere verzendnetwerken kunnen bouwen en betere circuits kunnen ontwerpen. Quantumcomputers hebben al krachtige toepassingen in kunstmatige intelligentie.

Dat gezegd hebbende, hun rol in cryptografie zal catastrofaal worden. De coderingstechnologieën waarmee onze wereld kan blijven functioneren, zijn afhankelijk van het feit dat het probleem van de integerfactorisatie moeilijk op te lossen is. RSA en gerelateerde versleutelingsschema's laten u erop vertrouwen dat u zich op de juiste website bevindt, dat de bestanden u zijn download zit niet vol met malware en dat mensen je surfen op het internet niet bespioneren (als je gebruikt Tor).

Cryptografie houdt uw bankrekening veilig en beveiligt de nucleaire infrastructuur van de wereld. Als kwantumcomputers praktisch worden, werkt al die technologie niet meer. De eerste organisatie die een kwantumcomputer ontwikkelt, als de wereld nog steeds werkt met de technologieën die we vandaag gebruiken, zal zich in een angstaanjagend krachtige positie bevinden.

Dus, is de kwantumapocalyps onvermijdelijk? Kunnen we er iets aan doen? Het blijkt... ja.

Post-kwantumcryptografie

Er zijn verschillende klassen van versleutelingsalgoritmen die, voor zover we weten, niet significant sneller op te lossen zijn op een kwantumcomputer. Deze staan ​​gezamenlijk bekend als post-kwantumcryptografie en bieden enige hoop dat de wereld kan overstappen op cryptosystemen die veilig zullen blijven in een wereld van kwantumversleuteling.

Veelbelovende kandidaten zijn onder meer op roosters gebaseerde encryptie, zoals Ring-Learning With Error, dat de beveiliging ontleent aan een aantoonbaar complex machine learning-probleem en multivariate cryptografie, die zijn beveiliging ontleent aan de moeilijkheid om zeer grote systemen van eenvoudig op te lossen vergelijkingen. U kunt meer over dit onderwerp lezen op de Wikipedia-artikel. Pas op: veel van dit spul is complex en het kan zijn dat je je wiskundeachtergrond aanzienlijk moet versterken voordat je echt in de details kunt graven.

De afhaalmaaltijden van veel hiervan zijn dat post-kwantumcryptoschemieën erg cool zijn, maar ook erg jong. Ze hebben meer werk nodig om efficiënt en praktisch te zijn en ook om te bewijzen dat ze veilig zijn. De reden dat we cryptosystemen kunnen vertrouwen, is omdat we er lang genoeg genoeg klinisch paranoïde genieën naar hebben gegooid dat alle voor de hand liggende tekortkomingen inmiddels zouden zijn ontdekt, en onderzoekers hebben verschillende kenmerken bewezen die ze maken sterk.

Moderne cryptografie is afhankelijk van licht als ontsmettingsmiddel en de meeste post-kwantumcryptografische schema's zijn gewoon te nieuw om de wereldbeveiliging op te vertrouwen. Ze komen er echter wel, en met een beetje geluk en wat voorbereiding kunnen beveiligingsexperts de overstap voltooien voordat de eerste quantumcomputer ooit online komt.

Als ze niet slagen, kunnen de gevolgen ernstig zijn. De gedachte aan iemand met dat soort macht is verontrustend, zelfs als je optimistisch bent over hun bedoelingen. De vraag wie als eerste een werkende kwantumcomputer ontwikkelt, is er een die iedereen heel zorgvuldig moet bekijken als we het volgende decennium ingaan.

Ben je bezorgd over de onzekerheid van cryptografie voor kwantumcomputers? Wat is jouw mening? Deel uw mening in de onderstaande opmerkingen!

Afbeeldingscredits: Binaire bol Via Shutterstock