Quantum Computers Het einde van cryptografie?

Quantum computing is een van die technologieën die zo mysterieus is dat de naam van de tv-personages deze 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. De laatste paar jaar is het veld echter zorgwekkend dichter bij de praktische aspecten gekropen..

Bedrijven zoals Google en Microsoft, maar ook overheidsinstanties zoals de NSA zijn al jaren koortsachtig op zoek naar quantumcomputers. Een bedrijf genaamd D-Wave heeft apparaten geproduceerd en verkoopt die (hoewel ze geen geschikte computers zijn en maar een paar algoritmen kunnen uitvoeren) kwantumeigenschappen exploiteren, en zijn een verdere stap op weg naar een volledig Turing-compleet Wat is De Turing-test En zal het ooit worden verslagen? Wat is de Turing-test en zal het ooit worden verslagen? De Turing-test is bedoeld om te bepalen of machines denken. Heeft het Eugene Goostman-programma echt de Turing-test doorstaan, of hebben de makers gewoon vals gespeeld? Lees meer quantummachine.

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

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

Om uit te leggen waarom deze machines zo belangrijk zijn, moeten we een stapje terug doen en onderzoeken welke kwantumcomputers precies zijn en waarom ze werken. Om te beginnen, laten we het hebben over een concept genaamd “runtime-complexiteit.”

Wat is Runtime-complexiteit?

Een van de grote verrassingen in de begintijd van de computerwetenschap was de ontdekking dat, als je een computer hebt die een probleem van een bepaalde grootte binnen een bepaalde tijd oplost, het niet noodzakelijkerwijs problemen met de computer kan oplossen als je de snelheid van de computer verdubbelt twee keer zo groot.

Sommige algoritmes nemen de totale uitvoeringstijd zeer, zeer snel toe naarmate de omvang van het probleem toeneemt - sommige algoritmen kunnen snel worden voltooid op 100 gegevenspunten, maar als het algoritme voor 1000 gegevenspunten wordt voltooid, is een computer ter grootte van de aarde nodig die een miljard jaar. Runtime-complexiteit is een formalisering van dit idee: het kijkt naar de curve van hoe snel de complexiteit van een probleem groeit 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 gegevensverzameling werkt, stijgt (zoals een eenvoudige telfunctie), wordt gezegd dat het een functie is met een runtime-complexiteit van “n” (zoals in, het duurt n tijdseenheden om te verwerken n data punten).

Als alternatief kan het worden genoemd “lineair”, want als je een grafiek maakt, krijg je een rechte lijn. Andere functies kunnen zijn n ^ 2 of 2 ^ n of n! (n faculteit). Deze zijn polynomiaal en exponentieel. In de laatste twee gevallen groeien de exponentiële zo snel dat ze in bijna alle gevallen voor niets anders kunnen worden opgelost, behalve voor heel triviale voorbeelden.

Runtime-complexiteit en cryptografie

Als je dit spul voor de eerste keer hoort en het klinkt betekenisloos en geheimzinnig, laten we proberen deze discussie te baseren. Runtime-complexiteit is van cruciaal belang voor cryptografie, die ervan uitgaat dat het ontsleutelen veel gemakkelijker wordt voor mensen die een geheime sleutel kennen dan voor mensen die dit niet doen. In een ideaal cryptografisch schema moet de decodering lineair zijn als u de sleutel hebt, en 2 ^ k (waarbij k het aantal bits in de sleutel is) als u dat niet doet.

Met andere woorden, het beste algoritme voor het ontcijferen van het bericht zonder de sleutel zou gewoon mogelijke sleutels moeten raden, wat onbetaalbaar is voor toetsen die slechts een paar honderd bits lang zijn.

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

Asymmetrische cryptografie, waarbij de coderings- en decoderingssleutels verschillend zijn en niet eenvoudig uit elkaar kunnen worden berekend, is een veel moeilijkere wiskundige structuur om te implementeren dan symmetrische cryptografie, maar het is ook een stuk krachtiger: asymmetrische crypto kunt u privégesprekken voeren , zelfs over getapte lijnen! Het laat je ook toe om te creëren “Digitale handtekeningen” om u te laten verifiëren van wie een bericht afkomstig is en dat er niet mee is geknoeid.

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

Omdat asymmetrische cryptografie moeilijker te bouwen is dan symmetrisch, zijn de standaard versleutelingsschema's die momenteel in gebruik zijn niet zo sterk als ze zouden kunnen zijn: de meest voorkomende versleutelingsstandaard, RSA, kan worden gekraakt als je efficiënt de priemfactoren van een zeer groot nummer. Het goede nieuws is dat dat een heel moeilijk probleem is.

Het bekendste algoritme voor het verwerken van grote getallen in hun componentpriem is de algemene nummerveldzeef en heeft een runtime-complexiteit die iets langzamer groeit 2 ^ n. Als gevolg hiervan moeten sleutels ongeveer tien keer langer zijn om vergelijkbare beveiliging te bieden, iets dat mensen normaal tolereren als een kost om zaken te doen. Het slechte nieuws is dat het hele speelveld verandert wanneer kwantumcomputers in de mix worden gegooid.

Quantum Computers: het Crypto-spel veranderen

Kwantumcomputers werken omdat ze tegelijkertijd meerdere interne toestanden kunnen hebben, door middel van een kwantumfenomeen genaamd “superpositie”. 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, de meeste amplitude krijgen, zodat wanneer u de doos op de kat van Schrodinger opent, de versie van de interne toestand die u het meest waarschijnlijk krijgt gepresenteerd, een zelfvoldaan is uitziende kat met een gedecodeerd bericht.

Raadpleeg ons recente artikel over het onderwerp Hoe werken optische en kwantumcomputers voor meer informatie over quantumcomputers? Hoe werken optische en kwantumcomputers? Het Exascale-tijdperk komt eraan. Weet jij 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 keer sneller krijgen, helpt niet veel als het gaat om conventionele cryptografie dat je honderden miljarden keren bent te traag om te verwerken. Kwantumcomputers ondersteunen algoritmen die complexiteit van runtime hebben met een kleinere groei dan anderszins mogelijk is. Dit is wat kwantumcomputers fundamenteel onderscheidt van andere toekomstige computationele technologieën, zoals grafeen en memristerberekening. De nieuwste computertechnologie die je moet leren kennen De nieuwste computertechnologie die je moet leren kennen. Bekijk enkele van de nieuwste computertechnologieën die zijn ingesteld om de wereld van elektronica en pc's de komende jaren te transformeren. Lees verder .

Voor een concreet voorbeeld kan het algoritme van Shor, dat alleen op een quantumcomputer kan worden uitgevoerd, grote aantallen in rekening brengen log (n) ^ 3 tijd, wat drastisch beter is dan de beste klassieke aanval. Het gebruik van de algemene nummerveldzeef om een ​​getal met 2048 bits te factoriseren kost ongeveer 10 ^ 41 tijdseenheden, wat uitkomt op meer dan een triljoen biljoen biljoen. Met behulp van het algoritme van Shor duurt hetzelfde probleem slechts ongeveer 1000 eenheden.

Het effect wordt meer uitgesproken naarmate de toetsen langer zijn. Dat is de kracht van quantumcomputers.

Begrijp me niet verkeerd - kwantumcomputers hebben veel potentieel niet-kwaadaardig gebruik. Quantum-computers kunnen het probleem van reizende verkopers efficiënt oplossen, waardoor onderzoekers efficiëntere verzendnetwerken kunnen bouwen en betere circuits kunnen ontwerpen. Kwantumcomputers hebben al krachtige toepassingen in kunstmatige intelligentie.

Dat gezegd hebbende, hun rol in de cryptografie zal catastrofaal zijn. De coderingstechnologieën die onze wereld in staat stellen om te blijven functioneren, zijn afhankelijk van het feit dat het gehele factorisatieprobleem moeilijk op te lossen is. RSA en gerelateerde versleutelingsschema's laten u vertrouwen op de juiste website, dat de bestanden die u downloadt niet met malware worden doorkruist en dat mensen uw surfen op internet niet bespioneren (als u Tor gebruikt).

Cryptografie houdt uw bankrekening veilig en beveiligt de nucleaire infrastructuur van de wereld. Wanneer quantumcomputers praktisch worden, werkt al die technologie niet meer. De eerste organisatie die een kwantumcomputer ontwikkelt, als de wereld nog steeds werkt aan 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? Zoals het blijkt ... ja.

Post-quantum cryptografie

Er zijn verschillende klassen van coderingsalgoritmen die, voor zover wij weten, niet significant sneller op te lossen zijn op een kwantumcomputer. Deze zijn gezamenlijk bekend als post-quantum-cryptografie en bieden enige hoop dat de wereld kan overstappen op cryptosystemen die veilig blijven in een wereld van kwantumversleuteling.

Veelbelovende kandidaten zijn onder meer op roosters gebaseerde encryptie, zoals Ring-Learning With Error, die zijn beveiliging ontleent aan een aantoonbaar complex probleem met het leren van computers, en multivariate cryptografie, die zijn beveiliging ontleent aan de moeilijkheid om zeer grote systemen van eenvoudige vergelijkingen op te lossen. Je kunt meer over dit onderwerp lezen op het Wikipedia-artikel. Pas op: veel van dit soort dingen zijn complex en je zult merken dat je wiskundeachtergrond aanzienlijk moet worden verbeterd voordat je echt in de details kunt graven.

De conclusie van veel hiervan is dat post-quantum cryptoschemes erg cool zijn, maar ook erg jong. Ze hebben meer werk nodig om efficiënt en praktisch te zijn, en ook om te laten zien dat ze veilig zijn. De reden dat we op cryptosystemen kunnen vertrouwen, is omdat we voldoende klinisch paranoïde genieën genoeg lang genoeg naar hen hebben overgeslagen, zodat er nu kennelijk tekortkomingen zijn ontdekt en onderzoekers verschillende kenmerken hebben bewezen die hen sterk maken.

Moderne cryptografie is afhankelijk van licht als een ontsmettingsmiddel en de meeste van de post-quantum cryptografische schema's zijn gewoon te nieuw om op de veiligheid van de wereld te vertrouwen. Ze komen er echter wel aan en met een beetje geluk en wat voorbereiding kunnen beveiligingsdeskundigen de overstap voltooien voordat de eerste kwantumcomputer ooit online komt.

Als ze falen, kunnen de gevolgen echter erg zijn. De gedachte aan iemand die zo'n kracht heeft, is verontrustend, zelfs als je optimistisch bent over hun intenties. De vraag wie voor het eerst een werkende kwantumcomputer ontwikkelt, is er een die iedereen heel nauwlettend in de gaten moet houden als we naar het volgende decennium gaan.

Maak je je zorgen over de onveiligheid van cryptografie voor kwantumcomputers? Wat neem je? Deel uw mening in de reacties hieronder!

Beeldcredits: binaire orb via Shutterstock

Ontdek meer over: Online beveiliging.