NSA: – Kvantedatamaskiner er farlige

[Gjest medlem-329093]

Trenger en kvantedatamaskin i det hele tatt tilgang til Internett?

[G]

Interessant spørsmål -X7ENIANL

 

Tenker du at du på en eller annen måte skal kunne penetrere internett gjennom partikler?

[Gjest medlem-329093]

Heisann G :-)

 

Jeg har ikke tenkt gjennom det. Men kanskje det blir litt som project Montauk, at den genererer plausible virkeligheter og så handler etterretningen ut ifra det... blir litt som en superparanoid statsmakt som lager etterretningslover om en enkeltperson og overvåker denne i årevis og  venter på at han skal avsløre noe men det kommer aldri til noe for det eksisterer ikke noe "noe" bak denne personen... Så å koble den til internett blir kanskje kjedelig for da finner man ikke så mange morsomme alternative virkeligheter, bare en virkelighet og denne personen har aldri planlagt noe... Men det er jo bare ultrakjedelig for da har man jo ingen statsfiende, og da har man jo gjort alle de ulovlighetene til ingen nytte... ikke at jeg tror noen stat bryr seg om at den er "the bad guy", før den blir utsatt for pinlige høringer men men... :-P

[G]

Så du tenker at jeg er snill og grei, men der ute i et annet av multiversene, så finnes det en Evil G?

Samt i samme eller et annet multivers så har du Evil -X7ENIANL ?

 

Også kan man finne opp uendelige varianter av G og -X7ENIANL, og alle disse har sitt eget univers. Pornostjerne G, President G ..

Endret 7. februar 2016 av G

[David Brown]

Jeg skulle ønske at tek.no lagde en god artikel om kvantedatamaskiner som forklarte grunnlegende egenskaper og muligheter til slike systemer - da ville lesere sleppe å gjøre samme feil om og om igjen.

 

1. En kvantedatamaskin kan ikke gjøre NP-hard problemer til ikke-NP problemer. Den kan ikke "knekke de fleste krypteringer", den kan ikke gjøre noe som helst som en ikke-kvantedatamaskin kan gjøre. Det fins enkelte problemer - som faktorisering av store tall - som kan i teorien gjøres fortere med kvantedatamaskiner enn med vanlig datamaskiner. Men de har samme type skalleringsutfordringer som på vanlig datamaskiner. D.v.s., hvis en 2Kb nøkkel tar hundrevis av år å knekke i dag med vanlig datamaskiner, må man kanskje opp i 4Kb for å være sikkret mot kvantedatamskiner. Men det er ikke verre enn det.

 

2. Rekorden for faktorisering av tall med kvantealgoritmer er 143 = 13 x 11. Det vil si, tall man kan regne med i hodet i løpet av noen få sekunder. Skal man bygge noe som faktisk kan være nyttig (sammenlignet med en vanlig datamaskin) i faktorering av store tall, må vi ha noe mange ganger større (med tusenvis eller millioner av qubiter, istendenfor kanskje 6 qubiter) , og mange gange lengre (i dagevis istendenfor noen få millisekund). Personlig har jeg ingen tro at det noen gang kommer til å fungere, ihvertfall ikke på en måte som kan konkurrere med vanlig datamaskiner i pris, størrelse eller strøm for å få samme resultat. Og det er ihvertfall ikke noe å bekymre seg over i nærmeste tiårene. (Og nei, Google/D-Wave sine systemer er ikke ekte kvantedatamaskiner, og kan ikke brukes til slike algorithmer. Og selv om det er interessant teknologi, er det tusenvis av ganger dyrere enn å gjøre samme jobb raskere og mer nøyaktige med vanlig supercomputerer.)

 

3. Selv om jeg tar helt feil, og noen produsere en kvantedatamaskin som raskt og enkelt faktoriserer store tall, fins det allerede andre krypteringsmetoder som ikke lar seg knekke raskere med kvanteteknologi enn med vanlig datamaskiner. De er ikke så enkel som RSA, men fungere fint for det.

[Gjest medlem-329093]

Nei.

Endret 7. februar 2016 av medlem-329093

[nessuno]

 

NSA/CIA blir nok de aller første som får en slik datamaskin, nettopp for å knekke krypteringen de snakker om.

 

Og det finnes forsåvidt en krypteringsmetode alrede som er urgammel men sikkert, samt vrien til å implementere like lett som konvensjonelle krypteringsmetoder.

 

 

Går sikkert an å implementere PGP, bare at det kanskje ikke er blitt utbredt og implementert riktig elegant enda.

PGP er jo urgammelt 90-tallet elns. Tror du de (les:NSA) drømmer om å knekke PGP 2k bit?

 

https://www.digicert.com/TimeTravel/math.htm

Nei, jeg tenkte på "one-time pad"

https://en.wikipedia.org/wiki/One-time_pad

det er som jeg sa vanskelig å implementere siden det betyr fysisk "nøkkelutveksling", men hvis den brukes korrekt er den umulig å knekke, selv med enkel kryptering. Hvis det gjøre "i flere lag", og med helt tilfeldig generert nøkkeldata fra forskjellige kilder + noen andre små finesser, så er den så å si "kvantesikker", og sikker for alt som er ikke funnet opp enda.

[G]

Dersom du i tillegg programmerte et virtuellt OS, som brukte et egetdesignet tegnsett som ikke var ASCII, så ville man vel også vært et stykke på vei. Men, det krever jo litt ekstra å først lage det, og også å lære seg en del taster i tegnsettet, slik at man kan få tastet inn passordet, som ikke er ASCII, men det bruker fremdeles en tabell som likner på ASCII, bare at tegnene er helt forskrudd. Kun til passordet selvfølgelig. Filene som blir kryptert bør jo være leselige fra vanlige PC'er.

 

Også finnes andre muligheter. Hvor lett er det å avsløre steganografi?

 

EDIT:

Når jeg tenker meg om så bør vel hele tegnsettabellen være inkompatibel, for ellers vil jo bare bokstavene være skiftet over f.eks. tegn 102 kan ha to forskjellige meninger, men er jo fremdeles 102 for det. Så det må vel dypere programmering til for den passordfasen. Man bør finne opp et nytt hjul.

Endret 7. februar 2016 av G

[LMH]

D.v.s., hvis en 2Kb nøkkel tar hundrevis av år å knekke i dag med vanlig datamaskiner, må man kanskje opp i 4Kb for å være sikkret mot kvantedatamskiner. Men det er ikke verre enn det.

 

Einig i det du skriver, men akkurat dette blir vel ei forenkling?

 

Shor's algorithm kan knekke RSA i polynomisk tid. Ein kan gjere dette vanskelegare ved å auke nøkkelstørrelsen, men det vil framleis vere "enkelt" og "raskt" for ei kvantedatamaskin å løyse problemet. I den forstand at det berre er snakk om ei relativt liten oppskalering av kvantemaskina sin ytelse eller berekningstid, sett i forhold til ei klassisk maskin som må ha ein eksponensiell auke i ytelse eller berekningstid for å "henge med".

 

Men som du seier, det er jo "berre" å bruke andre krypteringsmetodar.

[Villfaren]

Imponert over kunnskapen til enkelte!

[morten_b]

NSA er nok bare bekymret for at maskinen er så rask at de ikke klarer å avlytte den fort nok...

[AdNauseam]

Nettrafikken er jo synlig uansett hva du gjør (dvs. kryptert trafikk ses fortsatt, så et er et problem om kryptertingen lenger ikke skjuler det som ligger bak). Den eneste måten vi har å beskytte oss idag er jo kryptering som skjuler ruten samt informasjonen som sendes.

 

Jeg tror ikke strømforbruk og kostnader er noe som vil stoppe dem fra å satse på noe sånt. Jeg har inntrykk av at det er knyttet reelle forventninger til kvantemaskiner (det må da være en grunn for dette?). Det er jo bare til å se på utviklingen av den binære maskinen, ytelsen er astronomisk sammenlignet med bare noen år tilbake. En gang var den ikke kraftigere enn en kalkulator heller. Hva er det som tilsier at utviklingen på kvantemaskiner ikke vil avansere i samme grad?

 

Jeg spør fordi jeg vet ikke selv.

 

 

Jeg skulle ønske at tek.no lagde en god artikel om kvantedatamaskiner som forklarte grunnlegende egenskaper og muligheter til slike systemer - da ville lesere sleppe å gjøre samme feil om og om igjen.

 

1. En kvantedatamaskin kan ikke gjøre NP-hard problemer til ikke-NP problemer. Den kan ikke "knekke de fleste krypteringer", den kan ikke gjøre noe som helst som en ikke-kvantedatamaskin kan gjøre. Det fins enkelte problemer - som faktorisering av store tall - som kan i teorien gjøres fortere med kvantedatamaskiner enn med vanlig datamaskiner. Men de har samme type skalleringsutfordringer som på vanlig datamaskiner. D.v.s., hvis en 2Kb nøkkel tar hundrevis av år å knekke i dag med vanlig datamaskiner, må man kanskje opp i 4Kb for å være sikkret mot kvantedatamskiner. Men det er ikke verre enn det.

 

2. Rekorden for faktorisering av tall med kvantealgoritmer er 143 = 13 x 11. Det vil si, tall man kan regne med i hodet i løpet av noen få sekunder. Skal man bygge noe som faktisk kan være nyttig (sammenlignet med en vanlig datamaskin) i faktorering av store tall, må vi ha noe mange ganger større (med tusenvis eller millioner av qubiter, istendenfor kanskje 6 qubiter) , og mange gange lengre (i dagevis istendenfor noen få millisekund). Personlig har jeg ingen tro at det noen gang kommer til å fungere, ihvertfall ikke på en måte som kan konkurrere med vanlig datamaskiner i pris, størrelse eller strøm for å få samme resultat. Og det er ihvertfall ikke noe å bekymre seg over i nærmeste tiårene. (Og nei, Google/D-Wave sine systemer er ikke ekte kvantedatamaskiner, og kan ikke brukes til slike algorithmer. Og selv om det er interessant teknologi, er det tusenvis av ganger dyrere enn å gjøre samme jobb raskere og mer nøyaktige med vanlig supercomputerer.)

 

3. Selv om jeg tar helt feil, og noen produsere en kvantedatamaskin som raskt og enkelt faktoriserer store tall, fins det allerede andre krypteringsmetoder som ikke lar seg knekke raskere med kvanteteknologi enn med vanlig datamaskiner. De er ikke så enkel som RSA, men fungere fint for det.

Hvor tar du dette fra? Endret 9. februar 2016 av AdNauseam

[David Brown]

 

D.v.s., hvis en 2Kb nøkkel tar hundrevis av år å knekke i dag med vanlig datamaskiner, må man kanskje opp i 4Kb for å være sikkret mot kvantedatamskiner. Men det er ikke verre enn det.

 

Einig i det du skriver, men akkurat dette blir vel ei forenkling?

 

Shor's algorithm kan knekke RSA i polynomisk tid. Ein kan gjere dette vanskelegare ved å auke nøkkelstørrelsen, men det vil framleis vere "enkelt" og "raskt" for ei kvantedatamaskin å løyse problemet. I den forstand at det berre er snakk om ei relativt liten oppskalering av kvantemaskina sin ytelse eller berekningstid, sett i forhold til ei klassisk maskin som må ha ein eksponensiell auke i ytelse eller berekningstid for å "henge med".

 

Men som du seier, det er jo "berre" å bruke andre krypteringsmetodar.

(Jeg skal ikke påstå at jeg forstå alt av de tekniske detaljene her - dette er ut ifra forsjellige websider og artikler.)

 

Det som er lett å glemme er at kvante algoritmer som Shor's algoritm krever også skalering i antall qubits, ikke bare i tid. Skal man faktorisere N, må man ha en egen "quantum circuit" med minimum q qubits der N^2 <= 2^q <= 2.N^2. Det vil si, har man en 4 Kb nøkkel, trenger man en dedikert oppsett med 8K qubits. Man ca. 4K ^ 2, d.v.s., 16 M, steg - d.v.s., ca. 16 sekunder med 1 MHz klokke (som er vist en realistisk hastighet, ihverfall med små systemer). Men selv om du holde systemet kjølt ned til ekstremt lavt temperatur (f.eks. 20 mK), har du rundt 100 us før decoherence gjør operasjonen ubrukelig. For å ha sjans å holde kontroll på feilene, må man bruke 8K ^ 2, d.v.s., 64 M qubits i 16 sekunder.

 

Og ikke glem hvor langt tid det tar å lage til systemet - per i dag, må kvantemaskinen spesiellages for hver nummer man skal faktorisere. Selv om man finne algoritmer for å lage oppsett automatisk, er det ikke gitt at den kan kjøre i polynomial tid!

 

Rekorden er faktorisering av 21 (faktorisering av 143 var vist med en adiabatic quantum computer, som kan ikke kjøre Shor's algorithm), ca. 10 år etter faktorisering av 15 med 7 qubits.

 

Jeg tror 4K RSA holder lenge - og vi har god tid til å bytte til andre krypteringsalgoritmer som ikke er avhengig av faktorisering.

[David Brown]

Nettrafikken er jo synlig uansett hva du gjør (dvs. kryptert trafikk ses fortsatt, så et er et problem om kryptertingen lenger ikke skjuler det som ligger bak). Den eneste måten vi har å beskytte oss idag er jo kryptering som skjuler ruten samt informasjonen som sendes.

 

Jeg tror ikke strømforbruk og kostnader er noe som vil stoppe dem fra å satse på noe sånt. Jeg har inntrykk av at det er knyttet reelle forventninger til kvantemaskiner (det må da være en grunn for dette?). Det er jo bare til å se på utviklingen av den binære maskinen, ytelsen er astronomisk sammenlignet med bare noen år tilbake. En gang var den ikke kraftigere enn en kalkulator heller. Hva er det som tilsier at utviklingen på kvantemaskiner ikke vil avansere i samme grad?

 

Jeg spør fordi jeg vet ikke selv.

 

 

Jeg skulle ønske at tek.no lagde en god artikel om kvantedatamaskiner som forklarte grunnlegende egenskaper og muligheter til slike systemer - da ville lesere sleppe å gjøre samme feil om og om igjen.

 

Hvor tar du dette fra?

 

 

Man kan alltid starte med Wikipedia (på engelsk) for å få litt grunnkunnskap om kvantedatamaskiner - noe som tek.no skribenten kunne jo ha prøvd.  Jeg har følgt med i blader - ikke faglitteratur, men gjerne et par hakk mer akademisk enn Illustrert Vitenskap (som jeg også leser).  Og jeg har gjerne lest en god del her og der på nettet.  Jeg skal ikke påstå at jeg forstår kvantemekanikk - veldig få egentlig forstår det - men det er interessant, og jeg liker å følge med hva som er nytt i fysikk verden.

 

Når det gjelder strømforbruk, fins det faktisk fysiske grenser på minimum energi som kreves for kalkulasjoner.  Jeg har ikke talene foran meg, men jeg mener å huske at det ikke var så fryktelig lange nøkkel som trengs for å gjøre klassiske faktoriseringsalgoritmer fordi selv den mest perfekte lavenergi datamaskin (vi snakker om ihvertfall milliard milliarder ganger mer effektive enn det vi klarer å lage) ville bruker mer energi enn vi har i solsystemet.  Nye algoritmer, som Shor's algoritm, kan unngå så mange kalkulasjoner og dermed bruker mindre energi - men bruker man store nøkler, treffer de samme type barriere.

 

Og kostnad er alltid en begrensning.  Når NSA ønsker å se hva du har gjort på nettet, har de mange angrepsmetoder.  Kodeknekking er bare én av dem - blir det for dyrt, bruker de heller andre kjente metoder som "the three B's" (bribery, burglary, blackmail) eller "rubber hose cryptoanalysis" (fin noen som kan svaret, slår dem på fotbladet med en gummislanget til de fortelle hemmelighetene).

[LMH]

Det som er lett å glemme er at kvante algoritmer som Shor's algoritm krever også skalering i antall qubits, ikke bare i tid. Skal man faktorisere N, må man ha en egen "quantum circuit" med minimum q qubits der N^2 <= 2^q <= 2.N^2. Det vil si, har man en 4 Kb nøkkel, trenger man en dedikert oppsett med 8K qubits. Man ca. 4K ^ 2, d.v.s., 16 M, steg - d.v.s., ca. 16 sekunder med 1 MHz klokke (som er vist en realistisk hastighet, ihverfall med små systemer). Men selv om du holde systemet kjølt ned til ekstremt lavt temperatur (f.eks. 20 mK), har du rundt 100 us før decoherence gjør operasjonen ubrukelig. For å ha sjans å holde kontroll på feilene, må man bruke 8K ^ 2, d.v.s., 64 M qubits i 16 sekunder.

Ja, absolutt. Eg vurderte å ha ei setning om: "kor praktisk mogleg det er er ein heilt anna sak" eller noko slikt, men lot vere.

 

Eg kommenterte fordi eg tolka det som om du meinte at klassiske og kvantemekaniske maskiner har dei same utfordringane med tanke på RSA. Det er eit viktig poeng synest eg, at ei klassisk maskin ikkje kan knekke RSA medan ei ideell kvantemekanisk maskin faktisk kan det. "Kan" i denne samanhengen betyr i polynomisk tid, som (slik at det er nemnt her) betyr at det er mogleg i praksis, at det er "lett", eller at det kan løysast i "rimeleg" tid.

 

Det er jo litt interessant eigentleg, at ei klassisk maskin må auke si reknekraft eksponensielt for å knekke RSA, noko som i prinsippet er lett for oss å gjere reint fysisk. Vi er jo ganske gode på oppskalering av tradisjonell reknekraft. Men ei kvantemaskin treng berre å bli "litt" betre/større, sett i forhold, for å knekke RSA, men det har vi veldig store problem med å faktisk få til fysisk. Det eine kan vi, men det fungerer dårlig, det andre fungerer bra, men det får vi ikkje til.

 

Med andre ord er vi nok ganske einige, RSA er trygt og godt i all overskueleg framtid!

 

Eg veit det er ein gjeng i Australia som prøver å bruke meir tradisjonell produksjonsteknikk basert på silisium til å lage qubits. Litt av tanken er vel at det skal gjere det lettare å oppskalere talet på qubits når ein først har klart å få til nokre få. Skulle dei faktisk klare å få til det på ein robust måte så har RSA eit problem, men dei er nok etter alt og døme svært langt derfrå.

Endret 11. februar 2016 av LMH