De dreiging van quantumcomputers

Inleiding

We maken met ons allen al eeuwen gebruik van encryptie. Door de komst van de computer is het gebruik daarvan aan de ene kant eenvoudiger geworden, aan de andere kant is het ook eenvoudiger om zwakke algoritmes te kraken. Er zijn door de jaren heen verschillende moderne encryptiealgoritmes ontstaan, aangevoerd door DES in de jaren zeventig. Daar zijn intussen de nodige gaten in geschoten en daarom doen we het nog steeds met de opvolger AES, dat zijn intrede deed in 2001. Dit algoritme mag dan nog steeds de koning zijn op het gebied van symmetrische encryptie, we maken ook dagelijks veelvuldig gebruik van een andere soort.

De jaren zeventig waren namelijk ook het toneel van een andere ontwikkeling op het gebied van encryptie: asymmetrische cryptografie. Deze moest een oplossing bieden voor het probleem van sleuteldistributie. Bij AES vinden encryptie en decryptie immers plaats aan de hand van dezelfde sleutel, wat tot problemen leidt als je de sleutel op een veilige manier met iemand wilt delen. De onderzoekers Whitfield Diffie en Martin E. Hellman presenteerden in 1976 hun paper New Directions in Cryptography, waarin ze de basis legden voor publiekesleutelcryptografie. Ze introduceerden het concept van een sleutelpaar met een publieke en een privésleutel, die onderling in wiskundig verband staan met elkaar. Op internet wordt dit principe veelvuldig gebruikt, bijvoorbeeld om https-verbindingen van encryptie te voorzien, maar ook om WhatsApp-chats te versleutelen.

gebroken slot 'Broken Rusty Lock', Nick Carter, CC BY 2.0

In de loop van de tijd zijn er verschillende aanvallen op het sleuteluitwisselingsprotocol van de twee wetenschappers verschenen, zoals Logjam. Tot nu is er echter nog geen aanval verschenen die de veiligheid van het volledige systeem ondermijnt. Toch weten we nu al dat veelgebruikte cryptosystemen als rsa en ecdsa een risico lopen door de komst van quantumcomputers, doordat ze gebruikmaken van wiskundige problemen die met behulp van een dergelijk systeem en de nodige algoritmes eenvoudig zijn op te lossen.

Daarom zouden we nu al actie moeten ondernemen, zo luiden de adviezen van wetenschappers en organisaties. Het is dan ook niet toevallig dat donderdag een deadline van het Amerikaanse NIST verliep om nieuwe cryptografische systemen in te sturen die ook tegen quantumcomputers zijn opgewassen. Het instituut maakte bekend dat het 82 inzendingen heeft gekregen van 75 universiteiten, 30 bedrijven en 10 overheidsorganisaties. De ingestuurde voorstellen worden besproken op de eerste conferentie voor de standaardisatie van deze ‘post-quantumcryptografie’, die in april plaatsvindt in Florida. Resultaten worden pas over drie tot vijf jaar verwacht. Genoeg aanleiding om eens op de achterliggende problematiek in te gaan en de effecten van quantumcomputers op encryptie nader te onderzoeken.

Quantumcomputers en encryptie

Tweakers sprak met wetenschapper Christian Schaffner over de komst van quantumcomputers en de gevolgen voor huidige vormen van encryptie. Schaffner is werkzaam bij de Universiteit van Amsterdam als universitair docent op het gebied van cryptografie en is betrokken bij QuSoft, het onderzoekscentrum voor quantumsoftware binnen het Centrum voor Wiskunde en Informatica, oftewel CWI. Daar houdt hij zich bezig met zowel de 'aanvallende' als de 'verdedigende' kant van quantumcryptografie. Het eerste betreft bijvoorbeeld het breken van versleuteling. Een voorbeeld van het verdedigende aspect is quantum key distribution, oftewel sleuteluitwisseling op quantumniveau.

Op de vraag of het nog onzeker is of quantumcomputers eraan komen en of ze een bedreiging voor encryptie vormen, antwoordt hij dat de wetenschappelijke consensus inmiddels wel is dat er iets moet gebeuren. Vijf jaar geleden waren er nog veel sceptici als het ging om het kraken van encryptie door quantumcomputers. “Als je kijkt naar wat de crypto-onderzoeksgemeenschap op dit moment doet, dan is er wel een grote focus op de vraag hoe we crypto kunnen maken die veilig blijft voor quantumaanvallers. Ik denk dat iedereen het ermee eens is dat er iets moet gebeuren. De vraag is alleen hoe snel dat moet. Als onderzoeker wil je toch graag de tijd vooruit zijn.”

IBM-quantumcomputer, via IBM

De NIST-competitie moet uitkomst bieden door voorstellen bijeen te brengen die versleutelingstechnieken bevatten om gegevens voor de voorzienbare toekomst te beveiligen tegen klassieke en quantumcomputers, en die compatibel zijn met bestaande protocollen en netwerken. Schaffner zegt over het NIST-programma: “NIST wil het geen competitie noemen, al is het dat in feite wel. Het geeft het alleen niet deze naam, omdat er niet één winnaar uitkomt, en NIST misschien ideeën uit verschillende hoeken wil gebruiken en deze tegelijk implementeren.“ Het staat vast dat het nog vele jaren gaat duren voordat de einduitslagen bekend zijn, aldus de onderzoeker. Het is nu nog onduidelijk welke kant we op moeten, omdat veel van de relevante wiskundige problemen nog niet voldoende zijn onderzocht.

Het Amerikaanse instituut verwoordt de noodzaak voor het in actie komen als volgt: “Het heeft ongeveer twintig jaar geduurd om onze huidige cryptografische publiekesleutelinfrastructuur op te bouwen. Daarom moeten we nu onze systemen van bescherming tegen quantumcomputers voorzien, los van de vraag of we precies kunnen schatten wanneer het tijdperk van die computers zal aanbreken.”

Meer waarschuwingen

NIST is niet de enige instelling die een waarschuwende toon aanslaat. In Nederland zijn dat bijvoorbeeld de AIVD en het NCSC, dat zich bezighoudt met de beveiliging van de overheid en kritieke sectoren. Onze inlichtingendienst publiceerde drie jaar geleden een informatieblad met daarin globale informatie over de verwachte komst van quantumcomputers. De dienst beroept zich op de TU Delft en schrijft dat die destijds de verwachting had om tussen 2030 en 2040 een quantumcomputer met duizenden qubits te bouwen. Als mogelijke oplossingen noemt de AIVD, of preciezer: het Nationaal Bureau voor Verbindingsbeveiliging van de dienst, het gebruik van quantumencryptie of van zogenaamde post-quantumcryptografie.

Het NCSC kwam in april van dit jaar met een factsheet over deze vorm van cryptografie. Deze publicatie grijpt terug op de verwachting uit het AIVD-informatieblad en plaatst de komst van ‘geavanceerde quantumcomputers’ minimaal dertien jaar in de toekomst. Ook uit deze publicatie komt naar voren dat er nu al actie nodig is, ook al zijn quantumcomputers misschien nog ver weg.

Op weg naar de quantumcomputer

Volgens Schaffner levert het bouwen van een quantumcomputer de grootste problemen op. “In theorie weten we heel goed hoe een quantumcomputer werkt. Als je zo’n perfecte quantumcomputer zou hebben, dan weten we dat we daarmee bijvoorbeeld een algoritme kunnen draaien en daarmee een enorme tijdwinst bij het kraken van encryptie kunnen behalen. De grote vraag is nu alleen hoe je zo’n computer bouwt.” Bij een kwantumprocessor wordt de kwantumstaat van deeltjes in superpositie gebracht, waardoor ze zowel een 1 als een 0 kunnen vertegenwoordigen.

Verschillende grote partijen werken intussen aan de ontwikkeling van een dergelijke computer, waaronder IBM, Google, Microsoft, Intel en het Delftse QuTech. Dat onderzoekscentrum ontving laatst een chip van zeventien qubits van Intel voor testdoeleinden. IBM kondigde vervolgens aan dat het een prototype ontwikkelt van een quantumchip met vijftig qubits, die het bedrijf wil aanbieden via zijn IBM Q-programma, dat zich richt op het ontwikkelen van een commerciële quantumcomputer.

IBM Q-laboratorium

Schaffner zegt over de ontwikkeling: “Het is wel duidelijk dat we daarvoor errorcorrectie nodig hebben. Dat betekent dat er in feite meer qubits nodig zijn. Stel dat je encryptie kunt kraken met duizend perfecte qubits en je kunt een enkele perfecte qubit maken met nog eens duizend imperfecte qubits, dan loopt het aantal snel op. Bijvoorbeeld voor het kraken van rsa2048 is de huidige schatting dat je zo’n miljoen qubits nodig hebt.”

Hoewel we nog niet bij dat aantal in de buurt zijn, gaat de huidige ontwikkeling wel de kant op dat we niet meer eenvoudig simulaties kunnen uitvoeren. “Tot dertig of veertig qubits kun je ook nog wel op een laptop simuleren. In de buurt van vijftig wordt het heel moeilijk, omdat de toestandsruimte exponentieel groeit met elke qubit die je toevoegt. Zodra je het niet meer kunt simuleren, kom je in het gebied van wat mensen nu quantum supremacy noemen. Een betere term is trouwens quantum advantage. Op dat punt zijn we volgend jaar waarschijnlijk wel aangekomen”, aldus Schaffner.

Er is geen nauwkeurige schatting te maken van wanneer iemand beschikt over een gevorderde quantumcomputer die een bedreiging vormt voor huidige encryptietechnieken. Daarvoor is de ontwikkeling afhankelijk van te veel verschillende factoren. Neem bijvoorbeeld een ontwikkeling waardoor blijkt dat er snel opgeschaald kan worden naar een veel groter aantal perfecte qubits.

17qbit-quantumchip, via QuTech

Wat is precies het probleem?

Dat quantumcomputers als bedreiging voor encryptie worden gezien, moge duidelijk zijn. De vraag is waarom dat zo is. Tweakers sprak daarover met Tanja Lange, hoogleraar cryptologie aan de TU Eindhoven en hoofd van het Pqcrypto-onderzoeksproject. Samen met cryptoloog Daniel Bernstein publiceerde Lange dit jaar een paper over de staat van post-quantumcryptografie.

De dreiging die uitgaat van quantumcomputers heeft te maken met het zogenaamde algoritme van Shor. Lange zegt: “Dit algoritme schaalt op een dergelijke manier dat het verhogen van de sleutelgrootte niet voldoende is om een systeem te beveiligen. Een gebruiker die een systeem beveiligt, heeft daar net zoveel tijd voor nodig als een aanvaller die diezelfde beveiliging kraakt. Om het preciezer te zeggen maakt Shors algoritme het mogelijk om rsa in polynomiale tijd te kraken, terwijl versleuteling ook in polynomiale tijd gebeurt.”

Creatieve uitleg van publiekesleutelcryptografie. inleiding eindigt rond 2:00.

Dit heeft ermee te maken dat de kwetsbare cryptosystemen gebruikmaken van priemfactoren om een groot getal te produceren. Stel dat alleen het product van priemfactoren p en q bekend is, dan is het met een huidige computer zeer moeilijk om vanuit dat product terug te rekenen welke priemfactoren met elkaar vermenigvuldigd zijn. Doordat een quantumcomputer dit in polynomiale tijd kan, wat wil zeggen dat het efficiënt en snel uit te voeren is, is dit principe niet meer voldoende om het kraken van encryptie tegen te gaan. Maar, zoals eerder aangegeven, is een aanzienlijk aantal qubits vereist om bijvoorbeeld 2048bit rsa te kraken.

Schaffner legt uit dat de kracht van het algoritme van Shor voortkomt uit de quantumvariant van de zogenaamde Fouriertransformatie. “Die dient ertoe om signalen in elkaar te vertalen. Bijvoorbeeld om een bepaald signaal over tijd uit te drukken in frequentie. In de quantumvariant kun je de transformatie toepassen om een bepaalde periodiciteit vast te stellen in een quantumsignaal.” Een vergelijking die soms wordt gemaakt, is het effect dat golven elkaar kunnen opheffen of elkaar juist kunnen versterken. Dit versterkingseffect leidt ertoe dat de juiste oplossing van een probleem wordt uitvergroot.

Schematische weergave van de Fouriertransformatie, via irenevigueguix

Zowel Lange als Schaffner zegt dat er geen twijfel is dat het algoritme van Shor effectief zal zijn op een quantumcomputer. “Shors algoritme heeft een grote quantumcomputer nodig om te draaien. Om een getal n te factoriseren rekent Shors algoritme met twee elementen met een waarde kleiner dan n. Zodra quantumcomputers dat op een voldoende stabiele manier kunnen doen, is gegarandeerd dat het algoritme de geheime sleutel van rsa zal vinden. Dit is in het klein al uitgevoerd en het is mogelijk om een quantumcomputer te simuleren, waardoor we kunnen testen of quantumalgoritmes kunnen werken”, aldus Lange.

Symmetrische encryptie en risico's

Het algoritme van Shor is goed in het vinden van priemfactoren en leent zich daardoor bij uitstek voor het aanvallen van publiekesleutelcryptografie. Er is echter nog een ander quantumalgoritme dat zich leent voor het kraken van encryptie, en wel de symmetrische variant, waarbij encryptie en decryptie aan de hand van dezelfde sleutel plaatsvinden. Een voorbeeld daarvan is AES. Het quantumalgoritme in kwestie is in de jaren negentig ontwikkeld door Lov Grover en leent zich voor het versnellen van ongestructureerde zoekopdrachten. Daardoor is het veel breder inzetbaar dan de variant van Shor.

Lange zegt over het algoritme van Grover: “Het algoritme versnelt de zoektocht naar de geheime sleutel, maar die versnelling is niet dramatisch en het verdubbelen van de sleutellengte is voldoende om ervoor te compenseren. Preciezer betekent dit dat een aanval op 256bit-AES in het beste geval in 2¹²⁸ operaties uit te voeren is in plaats van in 2²⁵⁶.” Op de vraag of 256bit-AES daarom als quantum secure moet worden gezien, zegt Lange: “Ik zou nooit iets quantum secure noemen, omdat we misschien iets over het hoofd hebben gezien. Maar tenzij een grote groep mensen iets over het hoofd heeft gezien, komt een aanval met Grover uit op 2¹²⁸ operaties bij 256bit-AES.”

De gevolgen van de komst van quantumcomputers voor bepaalde vormen van encryptie, volgens Lange en Bernstein

Waar ontstaan risico’s?

Het probleem is dat ecc en rsa op dit moment nog alomtegenwoordig zijn. De vraag is dan ook waar op den duur de grootste risico's ontstaan. Lange zegt daarover: "De gevoeligste doelwitten zijn applicaties die data op de lange termijn moeten beveiligen, omdat alle gegevens die nu worden opgeslagen en versleuteld, over vijftien jaar door een aanvaller met een quantumcomputer gelezen kunnen worden, als hij tenminste de vooruitziende blik had om die gegevens op te slaan. Dus elke dag die we wachten, is een nieuwe dag met verloren data. Denk daarbij bijvoorbeeld aan gezondheidsgegevens, overheids- en militaire communicatie, dissidenten of journalisten. Een andere categorie zijn apparaten in langdurig gebruik die van software-updates worden voorzien. Een aanvaller zou bijvoorbeeld een kwaadaardige update kunnen installeren, omdat hij in staat is het authenticatieproces van de updates te kraken."

Ook Schaffner noemt digitale handtekeningen als voorbeeld en zegt dat er genoeg aanwijzingen zijn dat overheden grote hoeveelheden gegevens opslaan. Hij beaamt dat het nodig is om actie te ondernemen. "Mensen moeten zich ervan bewust worden dat dingen die ze nu opslaan en versleutelen, op grote schaal worden verzameld. Als je die gegevens voor langere tijd veilig wilt houden, dan is het nu eigenlijk al te laat."

Daarnaast noemt hij de blockchain als ander voorbeeld. Ook daar wordt momenteel over nagedacht, onder meer door onderzoekers van universiteiten in Frankrijk, Australië en Singapore. In een onlangs gepubliceerd onderzoek schrijven ze dat de digitale handtekeningen binnen de bitcoinblockchain afhankelijk zijn van encryptie op basis van elliptische krommen, zoals in ecdsa. Daardoor komen deze ook in het nauw zodra er een quantumcomputer is die het algoritme van Shor kan draaien. Het proof-of-workalgoritme van bitcoin loopt volgens de onderzoekers minder risico, omdat de tijdswinst die het algoritme van Grover oplevert bij het berekenen van hashes, kan worden opgevangen door de hoge snelheid van asics.

In de ogen van de onderzoekers heeft een aanval op een transactie de meeste gevolgen. Zo zou een aanvaller aan de hand van de publieke sleutel de privésleutel kunnen achterhalen die nodig is om een transactie uit te voeren. Doet hij dit snel genoeg, dus voordat de transactie in de blockchain is opgenomen, dan zou hij met de achterhaalde privésleutel een eigen transactie in de blockchain kunnen laten opnemen. De onderzoekers dragen daarom verschillende opties aan voor een alternatieve manier voor het uitwisselen van een publieke sleutel, die minder gevoelig is voor een aanval met een quantumcomputer.

Alternatieven en adviezen

De vraag is wat 'veilige' algoritmes anders doen dan de varianten die we nu gebruiken. Daarover zegt Lange: "Systemen voor post-quantumencryptie zijn gebaseerd op wiskundige problemen waarvoor nog niemand een manier heeft gevonden om het algoritme van Shor toe te passen. Aanvallen op ecc en rsa kunnen vertaald worden naar het vinden van een bepaalde frequentie waarmee zich iets herhaalt dat in verbinding staat met de geheime sleutel. Het algoritme van Shor is daar goed in."

Kijken we bijvoorbeeld naar een publicatie van NIST of aanbevelingen van het Pqcrypto-project, dan noemen deze documenten een aantal mogelijke kandidaten. Zoals we zagen, zijn de gevolgen voor symmetrische encryptie te overzien en voldoet het vergroten van de sleutelgrootte, bijvoorbeeld een 256bit-sleutel voor AES of Salsa20. Voor publiekesleutelcryptografie zijn er bijvoorbeeld lattice-based cryptosystems, oftewel systemen die gebruikmaken van een rooster en het shortest vector-probleem. Een voorbeeld is NTRU. Een andere mogelijkheid is het gebruik van een systeem als McEliece dat gebruikmaakt van foutherstellende codes. Voor digitale handtekeningen is er een mogelijkheid om over te gaan op handtekeningen die alleen zijn gebaseerd op het gebruik van hashfuncties, zoals Sphincs256.

Quantum key distribution

Hiervoor hebben we gekeken naar mogelijke kandidaten die de oplossing zoeken in andere vormen van de 'traditionele' sleuteluitwisseling. Het is echter ook mogelijk om daarvoor gebruik te maken van quantumeffecten, via quantum key distribution. Volgens Schaffner bestaat er over deze methode enige discussie, maar biedt zij een alternatieve oplossing voor het probleem van het uitwisselen van een sleutel. Deze methode laat twee partijen een sleutel uitwisselen door middel van een quantumkanaal, bijvoorbeeld door fotonen te versturen via glasvezel. Die kunnen ze vervolgens gebruiken om berichten via een ander kanaal te versleutelen. Schaffner zegt: "Deze vorm van versleuteling gaat niet uit van de aanname dat het oplossen van een bepaald wiskundig probleem moeilijk is, zoals bij traditionele publiekesleutelcryptografie." De kracht van deze techniek ligt er volgens de onderzoeker in dat een kwantumstaat niet zomaar te kopiëren is, vanwege het zogenaamde no-cloning theorem. Gebeurt dit wel door een actieve aanvaller, dan kunnen de communicerende partijen dit achteraf vaststellen.

Helaas!
De video die je probeert te bekijken is niet langer beschikbaar op Tweakers.net.

Schaffner over qkd op de CCC-conferentie in 2015

Er kleven wel bezwaren aan deze vorm van sleuteluitwisseling, omdat er bijvoorbeeld een infrastructuur aanwezig moet zijn en er maar een beperkte afstand overbrugd kan worden. Lange maakte haar bezwaren tegen deze vorm, ook wel qkd genoemd, onder meer kenbaar bij een consultatie over het zogenaamde Quantum Manifesto van de EU. Daar schrijft ze: "Quantumcryptografie werkt niet met bestaande netwerken, beveiligt niet bestaande gevoelige informatie en beschermt niet de last mile tussen de quantum node en het apparaat van de eindgebruiker." Daarnaast zou de techniek niet geschikt zijn voor authenticatiedoeleinden, zoals digitale handtekeningen.

De praktijk

Tweakers sprak met Joachim Schipper over wat de verwachte komst van quantumcomputers voor zijn werkzaamheden betekent. Schipper is principal research engineer bij Fox-IT en werkt daar onder meer als cryptograaf aan de beveiliging van Nederlandse staatsgeheimen. Over de komst van quantumcomputers zegt hij: "Ik ben heel sceptisch, maar ook dan moet je aan het werk. Als er één procent kans is dat er over dertig jaar een bruikbare quantumcomputer bestaat, is dat waarschijnlijk de grootste cryptodreiging voor onze staatsgeheimen. En zó klein is de kans op een quantumcomputer nou ook weer niet."

Een van die beveiligingstechnieken is een vpn. Schipper zegt: "Fox-IT werkt nú aan post-quantumcryptografie binnen bijvoorbeeld OpenVPN-NL. Dat is een door Fox onderhouden versie van de opensource-OpenVPN-software, die goedgekeurd is voor gebruik door de Nederlandse overheid. We volgen de ontwikkelingen in de post-quantumwereld al jaren nauwlettend. Zo waren we in 2016 een van de eerste commerciële partijen die de academische Pqcrypto-conferentie bijwoonden. En natuurlijk spreken we uitgebreid met onze partners bij de overheid."

Binnen de vpn-software wil Fox-IT bijvoorbeeld het eerder besproken McEliece gaan gebruiken. "Dat is een algoritme uit 1978 dat al vele aanvallen heeft doorstaan, maar als je mobieltje een beetje slechte verbinding heeft, zit je wel echt te wachten tot McEliece alle benodigde data heeft verstuurd. Alternatieven zijn veel zuiniger", aldus Schipper. Volgens de onderzoeker is het vakgebied van post-quantumcryptografie nog zeer in ontwikkeling. Over zijn verwachting voor de toekomst zegt hij: "Daarnaast zullen veilige implementaties in hard- en software meer aandacht krijgen, juist ook nadat NIST een standaard heeft gekozen. Een wiskundig sterk algoritme valt vaak tóch ten prooi aan zogenaamde side-channelaanvallen. Fox-IT doet, met onze Delftse collega’s van Riscure, actief onderzoek naar zulke aanvallen."

Schipper wijst erop dat momenteel stappen worden genomen in de academische wereld, bij grote bedrijven en bij de bescherming van staatsgeheimen. Op de vraag of dit ook de plekken zijn waar actie nodig is, antwoordt hij: "Dit zijn de juiste sectoren. Voor vitale infrastructuur zijn andere problemen dringender, maar de sectoren die dit soort dingen niet zélf kunnen ontwikkelen, moeten ook mee. Daarvoor is het belangrijk dat de academici en NIST een standaard ontwikkelen, en dat goede implementaties beschikbaar komen als kant-en-klare componenten."

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. shor en grover

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.

Inhoudsopgave

Multipage-opmaak

IT-banen

Reacties (61)

Laloeka 2 december 2017 16:57

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

Playa del C. 2 december 2017 08:01

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

Anoniem: 423815 @Playa del C. • 2 december 2017 11:40

Ik denk dat deze clip ook essentieel is bij dit artikel: https://youtu.be/6H_9l9N3IXU

a3aanm @Anoniem: 423815 • 3 december 2017 08:10

Vele malen dank hiervoor. Hoezeer deze achtergronden mij ook interesseren, mis ik een basiskennis om het goed te kunnen begrijpen. Dit helpt.

Guru Evi 2 december 2017 08:26

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.

iLaurens @Guru Evi • 2 december 2017 09:50

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.

Jefrey Lijffijt @iLaurens • 2 december 2017 13:43

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 22 juli 2024 14:02]

Anoniem: 890159 @Jefrey Lijffijt • 2 december 2017 15:49

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?

Jefrey Lijffijt @Anoniem: 890159 • 2 december 2017 16:19

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.

Anoniem: 890159 @Jefrey Lijffijt • 2 december 2017 17:06

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.

Zoijar @iLaurens • 2 december 2017 12:29

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.

.oisyn Moderator Devschuur®

Quantummechanica
Encryptie

@Guru Evi • 2 december 2017 10:03

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 22 juli 2024 14:02]

Anoniem: 956915 @.oisyn • 2 december 2017 20:27

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 Anoniem: 956915 op 22 juli 2024 14:02]

dmantione @Guru Evi • 2 december 2017 09:44

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.

pkuppens @Guru Evi • 2 december 2017 11:54

NP betekent Niet Determinstisch Polynomiaal. En laat zo'n quantum computer vrij aardig niet-deterministisch zijn. Zo interpreteer ik het.

WCas @pkuppens • 2 december 2017 17:15

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.

Yzord 2 december 2017 08:00

Daarom dus QRL (quantum resistent ledger). Dat is de toekomst imo.

[Stan] @Yzord • 2 december 2017 08:16

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

robvanwijk

Encryptie
Netwerk en systeembeheer

@[Stan] • 2 december 2017 13:47

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".

Mathijs @robvanwijk • 2 december 2017 16:15

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 22 juli 2024 14:02]

[Stan] @robvanwijk • 2 december 2017 21:09

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?

WokeBroke 2 december 2017 08:56

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.

aadje93 @WokeBroke • 2 december 2017 11:54

dat is leuk op websites, maar hoe ga je dat met je onderschepte TLS verkeer, je encrypted HDD etc doen

Ventieldopje @aadje93 • 2 december 2017 12:37

Aan je onderschepte TLS verkeer kun je niks doen maar je HDD kun je laten overschrijven en wipen na x pogingen.

itcouldbeanyone @Ventieldopje • 3 december 2017 01:36

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.

Ventieldopje @itcouldbeanyone • 3 december 2017 10:23

Een soort RAID 1, 1 disk met de data en 1 disk met de keys. Zal lekker snel zijn not $_/-\o_$

itcouldbeanyone @Ventieldopje • 3 december 2017 13:06

mischien met de komst van quantum computers dat dat ook haalbaar is

cdwave @itcouldbeanyone • 4 december 2017 11:45

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.)

itcouldbeanyone @cdwave • 4 december 2017 12:24

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 22 juli 2024 14:02]

cdwave @itcouldbeanyone • 4 december 2017 14:55

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.

svenk91 @Ventieldopje • 2 december 2017 13:16

Als ze nou direct de disks eruit halen en met een eigen controller uitlezen?

Stoelpoot @Ventieldopje • 4 december 2017 09:25

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.

Anoniem: 310408 @WokeBroke • 2 december 2017 09:47

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.

Mr777 @WokeBroke • 2 december 2017 10:02

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.

Anoniem: 167912 @WokeBroke • 2 december 2017 09:41

Ik had begrepen dat een quantum pc en wachtwoord in 1 keer raden goed had

player-x 3 december 2017 08:49

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 22 juli 2024 14:02]

Anoniem: 636203 @player-x • 3 december 2017 12:16

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 Anoniem: 636203 op 22 juli 2024 14:02]

player-x @Anoniem: 636203 • 3 december 2017 12:36

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.

Anoniem: 636203 @player-x • 3 december 2017 12:43

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.

gekkeh3nk 2 december 2017 10:58

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...

wallagh @gekkeh3nk • 2 december 2017 11:23

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.

Anoniem: 636203 @gekkeh3nk • 3 december 2017 15:17

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 Anoniem: 636203 op 22 juli 2024 14:02]

ataryan 2 december 2017 08:24

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

rjberg 2 december 2017 10:59

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.

Rikuge 2 december 2017 12:18

Allemaal aan de QRL dus! Gister heeft het project een video gelanceerd:

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

Op dit item kan niet meer gereageerd worden.