Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Door Sander van Voorst

Nieuwsredacteur

De dreiging van quantumcomputers

En de noodzaak van resistente encryptie

Door , 61 reacties

Tot slot

De vraag of een quantumcomputer daadwerkelijk binnen handbereik is of niet, blijft moeilijk te beantwoorden. Desondanks staat vast dat als er eenmaal een geavanceerde quantumprocessor wordt gebouwd, deze een serieuze bedreiging vormt voor onze huidige varianten van publiekesleutelcryptografie. Het gebruik daarvan is wijd verspreid, waardoor de mogelijke risico's groot zijn. Gegevens die we nu versleutelen met kwetsbare encryptie, moeten volgens verschillende waarschuwingen nu al als 'verloren' worden beschouwd. Het algoritme van Shor brengt de grootste snelheidswinsten met zich mee bij het kraken van encryptie die gebaseerd is op grote priemfactoren. Het algoritme van Grover kan bij symmetrische encryptie een voordeel opleveren, maar dit is te ondervangen door grote sleutels te gebruiken.

Wetenschappers Grover en Shor

Daarom roepen wetenschappers al enige tijd op om nu al over te stappen op encryptievormen die betere bescherming bieden tegen quantumcomputers. Het Amerikaanse NIST heeft een competitie georganiseerd, waaruit geschikte kandidaten voor een standaard moeten voortkomen. Dit proces zal waarschijnlijk nog enkele jaren duren. Op dit moment bestaat daarom op veel plaatsen wel het bewustzijn dat er iets moet gebeuren, maar weten we nog niet precies waar de oplossingen liggen. De kans op de ontwikkeling van een quantumcomputer en het mogelijke risico dat deze systemen met zich meebrengen, is in elk geval groot genoeg om er serieus rekening mee te houden.

Reacties (61)

Wijzig sortering
Ik zie een aantal verschillende reacties die P=NP noemen, en er lijken toch wat misverstanden te bestaan tussen wat NP, NP-Complete, NP-Hard en zelfs P betekenen.

Mocht P = NP je niets zeggen; neem hier eens een kijkje: https://www.youtube.com/watch?v=YX40hbAHx3s. Een van de grootste (een coolste) problemen in Computer Science, uitgelegd in 10 minuten :)
Omdat vaak de vraag komt: hoe werkt quantum-computing precies, hier een actuele basis uitleg: http://www.explainthatstuff.com/quantum-computing.html
En hier een video met meer focus op de werking van qubits: https://www.google.nl/url...Vaw1xVJ5dwXZlxr0nKnMTmJeb
Ik denk dat deze clip ook essentieel is bij dit artikel: https://youtu.be/6H_9l9N3IXU
Vele malen dank hiervoor. Hoezeer deze achtergronden mij ook interesseren, mis ik een basiskennis om het goed te kunnen begrijpen. Dit helpt.
Doordat een quantumcomputer dit in polynomiale tijd kan - dat is je reinste BS. De huidige quantumcomputers hebben nog steeds geen algoritme dat het P=NP probleem oplost, anders zelfs 17 qubits zou dit al kunnen aangetoond hebben, misschien nog niet praktisch maar dan wel academisch. We hebben dan wel quantum-processoren maar het zijn nog steeds klassieke, dan wel meer richting analoge computers.

Als je al een systeem dat genoeg qubits heeft om AES-256 sneller op te lossen, de oplossing is nog steeds het aantal bits omhoog krikken want de O van Shor's algorithm (O log N, log, N ...) is nog steeds afhankelijk van het aantal bits in de berekening en je hebt nog steeds een klassieke computer nodig om de uitkomsten te controleren.

Aan de andere kant, tegen de tijd dat quantum computers snel en goed genoeg zijn om heel snel AES-256 te kunnen factoriseren, zullen we allemaal toegang hebben op quantum machines die AES-256Qubits (of equivalent) even snel te genereren.
Volgens mij snap je het idee achter P=NP en de statement van de schrijver niet. Er wordt ook zeker niet bedoeld dat een kwantum computer het P=NP probleem oplost. Dit zal ook niet gebeuren want een computer lost over het algemeen geen wiskundig theorieŽn op.
Waar het hier om gaat is dat NP problemen exponentieel stijgen in moeilijkheidsgraad. De rekenkracht van een kwantum computer stijgt echter ook exponentieel met het aantal qubits. Dit in tegenstelling tot de klassieke computers wiens rekenkracht polynomial stijgt. Dit maakt het mogelijk om complexe NP problemen die voorheen niet op te lossen waren met traditionele computers toch binnen afzienbare tijd op te lossen zijn op een kwantum computer.
NP zijn problemen die verifieerbaar zijn* in polynomiale tijd, NP-hard zijn problemen die minstens even moeilijk zijn als problemen in NPC (NP Compleet), die laatste set is alles dat zowel in NP zit als NP-hard is. Alles dat NP-hard is en niet in NP zit is dus potentieel nog 'moeilijker'.

Priem-factorisatie, wat Shor's algoritme doet, is niet NP-hard. We weten echter niet hoe we dat 'efficient' moeten doen. Graph isomorphism was lange tijd onbekend of het NP-hard is, maar vorig jaar heeft Laszlo Babai een pseudo-polynomiaal algoritme gepresenteerd, waarmee het definitief als makkelijker te boek is komen te staan.

Het is niet bekend dat Quantum Computers alle problemen in NPC efficient zouden kunnen oplossen, maar wel een stuk efficienter. Statements hier over kwadratische speed-up zijn volgens mij correct, dat is dus niet exponentieel. Zeggen dat priem-factorisatie exponentieel veel sneller is vergelijkt het best gekende algoritme op klassieke computers (praktisch resultaat dus) met een theoretisch resultaat over QC.

Toevoeging: het is dus ook niet bekend of klassieke computers alle problemen in NPC efficient kunnen oplossen, dat is het P = NP vraagstuk.

* verifieerbaar betekent dat ieder 'ja'-antwoord een 'certificaat' oplevert dat in polynomiale tijd gecontroleerd kan worden.

[Reactie gewijzigd door Jefrey Lijffijt op 2 december 2017 13:47]

Dit is allemaal waar, maar waar theoretici vaak aan voorbij gaan is dat ook een probleem dat P en niet NP is in de praktijk nog steeds te lastig kan zijn om in voldoend korte tijd op te lossen. Leuk als je probleem nu niet in 100000 maar nog maar 10 keer de leeftijd van het heelal op te lossen is maar in de praktijk net zo onmogelijk. Deze verhoudingen ontbreken wat in het artikel: hoe snel is bv. een 4096 bits private RSA key te berekenen uit de public key met en zonder quantumcomputer?
Er zijn geen problemen in P die niet in NP zitten: P = NP of P is een subset van NP; je bedoelt denk ik problemen in P en niet in NPC.

Ik ben het volledig met je eens; ik ontwikkel zelf algoritmen, hoewel ik mezelf geen theoreet zou noemen, maar vaak genoeg zijn dingen niet fatsoenlijk te optimaliseren. Bijvoorbeeld submodular minimization kent een O(n^6) algoritme om optimaal op te lossen maar dat is natuurlijk zinloos in de praktijk. Eigenwaarde decompositie, wat extreem veel gebruikt wordt in data analyse is O(n^3), ook niet haalbaar voor middelgrote data of problemen.

Maar we moeten dus niet vergeten dat we voor NPC zowel op klassieke als quantum computers geen efficiŽnte algoritmes hebben en tegelijk niet bewezen is dat die niet bestaan.
Het wordt pas echt interessant als er een algorithme komt voor iets dat sneller is dan O(n), want dan kost het disproportioneel meer bits om de oplossingstijd van snellere hardware bij te houden. Hoewel dat natuurlijk ook niet alles zegt in de praktijk.
Dat is ook niet waar, QC lost die NP problemen slechts kwadratisch sneller op dwz als je van een NP probleem de key-length verdubbelt is een QC net zo snel als een normale computer nu. De enige uitschieter hier in prime factorisation wat RSA oplost, en dat is waarschijnlijk niet NPC: dat kan snel op een QC. Maar exponentiele problemen kan een QM dus ook niet snel genoeg oplossen voor hoe snel de moeilijkheid sijgt, ook niet binnen afzienbare tijd voor een groot genoeg probleem.
Sorry, maar deze hele reactie is je reinste bullshit. P=NP gaat over klassieke computers. Kwantumalgoritmes vallen in een compleet ander spectrum. Het is beween dat Shor's algoritme kan integers factorizeren in polynomiale tijd, en het valt daarmee in de complexiteitsklasse BQP. BQP is groter dan P. Dat betekent niet meteen dat ze alle NP problemen in polynomiale tijd kunnen oplossen.

Shor is overigens dan weer niet inzetbaar voor AES maar juist voor public key cryptography. AES maakt ook helemaal geen gebruik van integer factorisatie. AES is vatbaar voor Grover, een algoritme dat kan zoeken in een ongesorteerde dataset in O(sqrt N) tijd, waar een klassieke computer O(N) voor nodig heeft. En daarmee dus eigenlijk helemaal niet zo vatbaar, want dan kunnen we gewoon het aantal bits vergroten.

[Reactie gewijzigd door .oisyn op 2 december 2017 10:09]

AES is vatbaar voor Grover, een algoritme dat kan zoeken in een ongesorteerde dataset in O(sqrt N) tijd, waar een klassieke computer O(N) voor nodig heeft.
Zijn de ordes van tijd voor klassieke computers en kwantumcomputers nog wel vergelijkbaar als ze "in een compleet ander spectrum" vallen? Voor zover ik ze heb begrepen, zijn kwantumcomputers inherent probabilitisch, wat ook terugkomt in de definitie van BQP, terwijl je op een theoretische klassieke computer gegarandeerd een antwoord krijgt in O(N) tijd. Probabilitische algoritmen bestaan overigens ůůk voor klassieke computers, en het is maar de vraag of daar een verschil tussen zit (BPP is een deelverzameling van BQP, maar het staat niet vast of het ook een strikte deelverzameling is).

[Reactie gewijzigd door RobbertTafels op 2 december 2017 20:31]

Kwantumcomputers lossen niet zozeer P=NP op, maar ze kunnen exponentieel rekenen voor een bepaalde groep problemen. Als je een factor x^y uit de tijdcomplexiteit kunt verwijderen, dan blijft polynomiale tijd over, dat is wat bedoeld wordt. Voor de "P=NP"-materie maakt dat niet uit: Een doorbraak op dat punt vereist dat een NP-volledig algoritme in polynomiale tijd uitgevoerd kan worden. Als een individueel algoritme, waarvan gedacht werd dat het tot de klasse NP behoort, in polynomiale tijd uitgevoerd blijkt te kunnen worden, dan heeft dat voor de NP-volledige algoritmen geen gevolgen.
NP betekent Niet Determinstisch Polynomiaal. En laat zo'n quantum computer vrij aardig niet-deterministisch zijn. Zo interpreteer ik het.
Helaas is dat niet helemaal correct; conventionele computers kan je (ongeveer, aangezien ze in de echte wereld leven zullen ze natuurlijk nooit perfect zijn, het immers mogelijk dat er bijvoorbeeld bits onbedoeld switchen als gevolg van bijvoorbeeld electromagnetische straling, en ze hebben zeker geen oneindig geheugen) zien als een model van een deterministische Turing-machine. Dit betekent dat bij iedere actie het bekend is naar welke staat de machine gaat, dat is het determinisme ervan. Een non-deterministische Turing-machine werkt echter net iets anders, die kan bij iedere actie naar een verzameling van nieuwe staten gaan. Dit kan je modelleren in een deterministische Turing-machine door al die staten virtueel parallel te draaien, maar dat kost duidelijk meer ruimte, en dat (ongeveer) is waarom non-deterministisch polynomiale problemen moeilijk zijn; voor een non-deterministische Turing-machine zijn ze makkelijk op te lossen, maar een deterministische moet een hele hoop parallellen tegelijk simuleren. Een quantumcomputer is echter geen model van een non-deterministische Turing-machine, hij kan niet hetzelfde als wat een non-deterministische Turing-machine kan. Ik ben bang dat mijn kennis hier zo'n beetje ophoudt, ik weet dat de problemen die een quantumcomputer "makkelijk" (polynomiaal) op kan lossen een eigen klasse vormen, maar ik weet niet waar die klasse ongeveer ligt ten opzichte van P, NP en de rest, het lijkt alsof @.oisyn hier meer vanaf weet.
Daarom dus QRL (quantum resistent ledger). Dat is de toekomst imo.
Dit is een ledger technologie dat een zogenaamde encryptiemethode gebruikt dat resistent is tegen quantumtechnologie. Is een volledig andere toepassing dan pure encryptie.

Enige probleem is: hoe test je effectief dat deze ledger technologie quantum resistent is ;)
Enige probleem is: hoe test je effectief dat deze ledger technologie quantum resistent is ;)
Op dezelfde manier als we nu testen of huidige technieken resistent zijn tegen "gewone" (niet-quantum) aanvallen: heel veel slimme mensen alles laten proberen wat ze kunnen bedenken en als ze niks vinden... er het beste van hopen. Zekerheid heb je echter nooit; er is geen manier om te bewijzen "er bestaat geen methode om dit efficiŽnt te kraken". In het algemeen is er geen manier om te bewijzen "er bestaat geen methode om X te doen", je kunt hooguit zeggen "we hebben nog geen methode gevonden om X te doen".
Precies, er kan ook in de tussentijd een nieuw algoritme bedacht worden dat een gevaar oplevert.

Overigens kan het ook best zo zijn dat er al iets dergelijks is, maar dat door bepaalde kringen geheim gehouden wordt aangezien dat groot voordeel kan betekenen tegenover potentiŽle vijanden.
De militaire wereld doet bijvoorbeeld ook zelf onderzoek, net als vele overheden.

[Reactie gewijzigd door Mathijs op 2 december 2017 16:31]

Wat ik eigenlijk bedoelde, is dat er vandaag onvoldoende quantum oplossingen beschikbaar zijn om een test uit te voeren op dergelijke technologie. Maw is het effectief doeltreffend of pure marketing?
mischien is het goed om meer aandacht te besteden aan anti flood, inplaats van langere wachtwoorden? Dat na 5 keer proberen de toegang voorlopig geblokkeerd wordt.
dat is leuk op websites, maar hoe ga je dat met je onderschepte TLS verkeer, je encrypted HDD etc doen ;)
Aan je onderschepte TLS verkeer kun je niks doen maar je HDD kun je laten overschrijven en wipen na x pogingen.
Je kan ook gewoon voor 1 gb data wat geencrypt moet worden, een sleutel van 1gb gebruiken.
De kans dat ze dan een porno filmpje kunnen decrypten is dan net zo groot als dat er een filmpje van de titanic tevoorschijn komt.
Of een film die pas over 100 jaar uit komt.
Het kost je alleen erg veel data, en je sleutel is gigantisch en niet erg mobiel.
Een soort RAID 1, 1 disk met de data en 1 disk met de keys. Zal lekker snel zijn not _/-\o_
mischien met de komst van quantum computers dat dat ook haalbaar is
Nee, want als sizeof(key) >= sizeof(data) dan heb je perfecte encryptie. Op het moment dat de key even groot is als de data, wordt het makkelijker om de data zelf te raden dan om de key te raden. Al was het maar omdat je niet kunt zien of je key goed is, of dat je nog een bitje gemist hebt.

Als je een systeem kan bouwen dat dit kan kraken, dan kun je ook de lotto winnen.

(Een quantum systeem zou wel een briefje in een envelop kunnen stoppen met daarop de winnende uitslag van de komende lottotrekking, maar alleen als je de envelop pas opent na die trekking. Open je de envelop eerder, dan is de inhoud onbruikbaar.)
Ik doelde meer om een quantum computer te gebruiken om zon key te genereren.
Met een gewone cpu zou het wel ff duren nameljjk voor je data geencrypt is.

Zoals jij ook al zij, is decrypten inpossible ,

[Reactie gewijzigd door itcouldbeanyone op 4 december 2017 12:25]

Nee hoor, de encryptie met sizeof(key) == sizeof(data) is supersnel, je hoeft alleen maar de key en data te XOR-en.

Overigens wordt dit principe al toegepast, door een reeks nullen te encrypten met AES (met een 256 bit key ofzo), en de output daarvan te XOR-en met de data. Dan kun je een CPU core (of hardware) gebruiken om de "key" alvast vooruit te rekenen, zodat wanneer er data arriveert die heel snel ingepakt kan worden.
Als ze nou direct de disks eruit halen en met een eigen controller uitlezen?
Dan kopieer ik de HDD en probeer het uit te voeren op de kopie.

Buiten Full Disk Encryption is elke vorm van beveiliging te breken wanneer je fysieke toegang hebt.
mischien is het goed om meer aandacht te besteden aan anti flood, inplaats van langere wachtwoorden? Dat na 5 keer proberen de toegang voorlopig geblokkeerd wordt.
En hou ga jij ervoor zorgen dat de aanvaller maar 5 keer een key mag proberen bij het uitpakken van een versleuteld zipfile?

Het gaat hier over encryptie, niet zozeer wachtwoorden.
Als je echt een versleuteld bestand wilt ontsleutelen ga je dat natuurlijk niet via de interface van Word of Winzip of Truecrypt of wat dan ook doen, dan werk je rechtstreeks op het binaire bestand met zelf geschreven software die geen anti-floodtechnieken bevat.
Ik had begrepen dat een quantum pc en wachtwoord in 1 keer raden goed had
Wat ik altijd heb begrepen is dat als men digitale gegevens encrypt met een even groot masker met willekeurige data en die over elkaar legt, dat het dan nooit te ontcijferen is ook niet met QC's.

En zolang het niet bekend is hoe groot het masker is, en als het maar groot genoeg is, het masker steeds opnieuw gebruikt kan worden, daar de verstuurde gegevens echt random zijn.

Nadeel is dat je dan wel een data drager fysiek moet uitwisselen tussen punt A & B, maar dan is wel je data altijd veilig.

En als op locatie B eenmaal een veilige verbinding is opgezet, je dan meerdere of nieuwe maskers kan genereren, op locatie A, en die uploaden naar B.

Dit werkt ook voor mobiele data apparatuur daar daar ook zo een bestand op gezet kan worden.

Uiteraard blijf je het probleem houden van diefstal/toegang tot het fysieke apparaat houden, maar dat is er nu ook.

Of zie ik nu iets over het hoofd?

[Reactie gewijzigd door player-x op 3 december 2017 09:32]

Dat heet OTP (One Time Pad) en is inderdaad niet te ontcijferen, maar heeft als nadeel dat de sleutel net zo groot is als de data die moet overgezonden worden. Dat is erg onhandig.

[Reactie gewijzigd door ArtGod op 3 december 2017 12:17]

Dat masker kan toch verscheidende keren gebruikt worden, zeker als het uit willekeurige kleine deel maskers bestaat van verschillende grote, want de uitkomst is toch steeds weer willekeurig.
Ik zou er toch maar wat meer over gaan lezen. Eťn van de standaard no-no's van OTP is dat je nooit een sleutel (of een gedeelte daarvan) mag hergebruiken.
Vaak als het over kwantumcomputers gaat, dan gaat het over encryptie. Maar zijn er eigenlijk nog andere problemen waarbij we baat hebben bij kwantumcomputers? Voorzover wordt de techniek naar mijn idee alleen tegen de samenleving gebruikt...
Een andere toepassing die ik las is het simuleren van complexe moleculen. We kunnen dan bv. Beter medicijnen ontwikkelen omdat we die werking ervan kunnen simuleren, in plaats van moeten uitproberen.
Quantum computing zou dus ook voor een revolutie in de gezondheidszorg kunnen zorgen.
De eerste digitale computers werden voornamelijk gebruikt voor berekeningen aan ballistische banen van kanonskogels. Ook werden de eerste primitieve computers al gebruikt voor ontcijferen van encryptie codes zoals de Enigma. Dat is ook waar overheden natuurlijk erg geÔnteresseerd in zijn, en dat is waar ook de grootste impact is omdat versleuteling een belangrijk aspect is in ons dagelijks leven (denk aan internet bankieren en webwinkels).

Maar kwantum computers kunnen natuurlijk voor van alles gebruikt worden, net als 'normale' computers. De impact is nu nog onduidelijk, maar ik kan mij voorstellen dat simulaties dermate complex worden dat bijvoorbeeld computer graphics niet meer van echt te onderscheiden zullen zijn. Je zou dan inderdaad zoiets als The Matrix kunnen bouwen als je ook kon interfacen met het menselijk brein als in de film.

[Reactie gewijzigd door ArtGod op 3 december 2017 15:19]

Dwave heeft 4 quantum annealing machines in t veld staan. 1 van die 4 heeft m er staan tbv cryptografische berekeningen. Met de nieuwe reverse annealing techniek op 2000 qbits word het gemakkelijker om collisions op te sporen. Die 3 jaar is IMHO te kort. De berekeningskracht van die machines word nog steeds zwaar onderschat. Ben nu een quantum emulatie projectje begonnen met (maar) 8 qbits; die heeft al 40k states, entangled. Heel leuk projectje hoor, maarrehm... IMHO zijn 2k certs volgend jaar al serieus de sjaak. Of we er gelijk iets over horen ? #manhattenproject
Ik las ooit bij de openpgp devs dat iemand vroeg waarom we nog geen post quantum cryptografie gebruiken. Het antwoord was dat deze algoritmen nog niet zo lang bestaan, en dus minder vertrouwd zijn.

Op de vraag waarom we dan niet meerdere algoritmen gebruiken, was het antwoord dat dat overkill zou zijn.
Allemaal aan de QRL dus! Gister heeft het project een video gelanceerd:

https://www.youtube.com/watch?v=Ck-sHNNYFlQ


Om te kunnen reageren moet je ingelogd zijn


Apple iPhone X Google Pixel 2 XL LG W7 Samsung Galaxy S9 Google Pixel 2 Far Cry 5 Microsoft Xbox One X Apple iPhone 8

© 1998 - 2017 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Hardware.Info de Persgroep Online Services B.V. Hosting door True

*