Echt jetzt? Wirklich? Die NSA forscht am Quantencomputer

Ein bisschen unverständlich ist es schon, dass die Medien sich auf die neueste NSA-Enthüllung stürzen, die gestern von der Washington Post veröffentlicht wurde. Demnach arbeite die NSA an der Entwicklung eines Quantencomputers, um Kryptoverfahren, die auf schwierigen mathematischen Problemen beruhen, brechen zu können.

Das würde funktionieren, weil mit Mitteln der Quanteninformatik bestimmte Probleme effizienter gelöst werden können als mit herkömmlichen Methoden – eines dieser Probleme ist die Bestimmung der Teiler einer zusammengesetzten Zahl. Auf einer solchen Faktorisierung beruhen Verfahren wie RSA, wo ausgenutzt wird, dass es extrem aufwändig ist, eine große Zahl, die aus einer Multiplikation zweier unbekannter Primzahlen entstanden ist, wieder in diese zu zerlegen.

Der Shor-Algorithmus für Quantencomputer könnte dieses Problem mit genügend „Quantenbits“ so schnell lösen, dass RSA und andere Verfahren, die auf dieser oder ähnlichen Grundlagen beruhen, gebrochen wären.

Aber die Forschung an Quantencomputern ist nicht Neues, es wurden sogar bereits Forschungsprototypen gebaut. Nur praktisch nutzbar sind diese noch nicht. Maximal wurden an der Universität Innsbruck 2011 14 Quantenbits ermöglicht. Damit lassen sich noch lange keine Schlüssel in der Größe von beispielsweise 4096 bit berechnen, wie sie heutzutage bei RSA üblich sind (oder sein sollten) – diese haben in etwa 1200 Dezimalstellen. 14 Quantenbits reichen unter der Annahme, dass man log(n) Bits benötigt, um eine n Stellen lange Zahl zu faktorisieren, gerade einmal aus, um circa 7-stellige Zahlen zu berechnen.

Kein Wunder also, dass die NSA ihre Forschung vorantreiben will – genau wie auch der Rest der Wissenschaftswelt. Die einzige wirkliche Neuigkeit dürfte sein, dass sie bisher auch nicht viel weiter gekommen sind als die Kollegen aus der zivilen Forschung. In der Beschreibung ihres „Penetrating Hard Targets“ genannten Forschungsprogramms heißt eines der Anliegen:

Durchführen von grundlegender Forschung zu Quantenphysik und -architektur, um herauszufinden ob und wie ein kryptographisch nutzbarer Quantencomputer gebaut werden kann.

Das hört sich nicht sehr fortgeschritten an. Aber vielleicht hat die „Neuigkeit“ dennoch einen Effekt und regt dazu an, unsere Beziehung zu der bisher in allen möglichen Bereichen angewandten Public-Key-Kryptographie zu überdenken. Denn im Wesentlichen basieren all diese Verfahren auf der Annahme, dass es zu schwierig ist, aus dem öffentlichen Schlüssel den privaten zu berechnen, mit dem der Empfänger eine Nachricht für sich entschlüsseln kann.

Für symmetrische Verfahren, wie passwortbasierte Verschlüsselung, würden heute bekannte Quantenverfahren wie der Grover-Suchalgorithmus die Sicherheit „nur“ halbieren, was aber relativ leicht durch Verdopplung der Schlüssellänge aufgehoben werden kann. Und dann bleibt noch die Quantenkryptographie selbst, die neue Möglichkeiten der Verschlüsselung bereithalten könnte, mit denen man sich auch gegen stärkere Angreifer verteidigen kann – ein sicheres Protokoll zum Quantenschlüsselaustausch wurde schon 1984 veröffentlicht. Eines der wenigen Dinge, die helfen können, um beim Rennen mit der NSA nicht gänzlich ins Hintertreffen zu geraten, dürfte die Förderung freier und transparenter Forschung sein.

Deine Spende für digitale Freiheitsrechte

Wir berichten über aktuelle netzpolitische Entwicklungen, decken Skandale auf und stoßen Debatten an. Dabei sind wir vollkommen unabhängig. Denn unser Kampf für digitale Freiheitsrechte finanziert sich zu fast 100 Prozent aus den Spenden unserer Leser:innen.

46 Ergänzungen

  1. Naja D-Wave System hat ja bereits ihre 512-qubit Systeme an Google und US-Behörden verkauft. Die allgemeine Forschung hegt zwar immer noch Ihre Zweifel, aber das stört offenbar D-Wave nicht sonderlich. Solange die Amis und damit wohl auch die NSA ihnen die System abkaufen bauen die derzeit jedes Jahr neue Systeme mit noch mehr qubits.

    Mehr Infos dazu u.a. hier: http://readwrite.com/2013/12/30/d-wave-quantum-computing

    1. Jap, auf die D-Wave-Systeme bin ich bei der Recherche auch gestoßen. Habe aber davon abgesehen, sie zu erwähnen, eben weil sie, wie du gesagt hast, wissenschaftlich recht umstritten sind und ich dann eher dazu tendiere, sie nicht als „echte“ Quantencomputer zu sehen. Ich fand diesen Artikel dazu recht lesenswert.

      1. :) Ich hätte jetzt eher diese theoretischen Versuche wie von Innsbruck ignoriert und einzig D-Wave als „echte“ angesehn. Die haben schliesslich ein Produkt auf dem Markt und bereits NASA und Rüstungskonzerne (nebst Google und Amazon) als Kunden.

      2. Ein Freund arbeitete eine Zeit lang bei D-Wave. Er hat dort beim Schaltungsdesign mitgewirkt. Die Firma baut supraleitende QuBits auf Silizium-Wafern in Industriestandardgröße (30cm). Es geht hier um großflächige Schaltungen, die mit standardisierten Prozessen hergestellt werden. Der Freund ist ausgestiegen, als es eine Entlassungswelle aus Geldmangel gab. Seitdem ist allerdings einiges an Kapital in D-Wave geflossen.

        Meiner Erinnerung nach hat Northrop-Grumman das erste Gerät gekauft. Es wird gemunkelt, dass dieser Quantencomputer nicht funktioniert und es eher ein Scheinkauf war, um weitere Risikokapitalgeber zu motivieren. Außerdem darf man nicht vergessen, dass viel der tatsächlichen Operation auf viel Theorie basiert und wenig Erfahrung exisitert. Wenn aber jemand die Hardware an den Start kriegt, dann mit hoher Wahrscheinlichkeit D-Wave. Universitäten forschen gerade an einzelnen QuBits beziehungsweise der Verschränkung einiger weniger QuBits.

        Aber Universitäten haben auch andere Ziele, meistens jedenfalls. Wissenschaftler wollen verstehen, wie und warum es funktioniert. Einen Erfinder interessiert es nicht, solange es reproduzierbar funktioniert. Ja, das ist drastisch vereinfacht. Aber schon die Arbeitsweise ist verschieden, denn Universitäten arbeiten doch mehr oder weniger öffentlich. Ich weiß im Moment nicht, ob D-Wave überhaupt wissenschaftliche Veröffentlichungen macht.

        Vielleicht ist D-Wave auch nur ein roter Hering. Aber das wäre eine massive Verschwendung fähiger Köpfe…

    2. Hallo, kurz zu D-Wave: Das ist hier irrelevant.

      Jenseits dessen, dass umstritten ist, ob der D-Wave-Rechner wirklich tut was er soll: Es handelt sich – selbst wenn er funktioniert – NICHT um einen universellen Quantencomputer und er ist in jedem Fall nicht in der Lage, den Shor-Algorithmus auszuführen.

      Vielleicht ist der D-Wave-Rechner für andere Anwendungen interessant, vielleicht ist er nur ein großer Betrug. Für Krypto ist er auf jeden Fall irrelevant.

  2. Bei dem Etat der Geheimdienste gehe ich zwar vorsichtshalber (worst case) mal davon aus, dass sie sehr wohl (etwas) weiter mit ihrer Forschung sind als die zivilen Pendants. In allen weiteren Punkten stimme ich dem Artikel jedoch zu.

  3. Inhaltlicher Fehler:

    Für symmetrische Verfahren, wie passwortbasierte Verschlüsselung, würden heute bekannte Quantenverfahren wie der Grover-Suchalgorithmus die Sicherheit “nur” halbieren, was aber relativ leicht durch Verdopplung der Schlüssellänge aufgehoben werden kann.

    Halbierung wäre 2^(n-1), der Grover-Algorithmus reduziert den Suchraum auf 2^(n/2), somit wird die Sicherheit quasi „gewurzelt“.

    1. Hmm, das mit dem Zitat hat nicht so funktioniert, evtl. kann das der Mod/Redakteur korrigieren.

      1. Hab ich gemacht. Und danke für die Korrektur, ich meinte eigentlich auch die Halbierung des effektiven Schlüssels.

  4. Bleibt mal wieder ein Bauchweh-Gefühl bei mir hängen nach dem Lesen dieses Artikels – denn wir reden hier von einem Wettrüsten, dass unglaubliche Ressourcen verbrennt. Die folgen sind nicht absehbar: Wer kann garantieren, dass diese System ’nur‘ von des NSA benutzt werden?

    Die ethische Dimension der Ausspäh-Problematik und die gesellschaftlichen und politischen Folgen sind noch zu wenig im Fokus. Dazu:


    „Dieser ethische Diskurs ließe sich eins zu eins von Massenvernichtungswaffen auf die Informationstechnologie übertragen: Rechnersysteme werden infiziert, Kommunikationstechnologie wird verseucht und die Angst vor der Überwachung strahlt in den Alltag hinein. Unsere Schere im Kopf wird immer präsenter“

    http://wagnisdemokratie.wordpress.com/

    1. Hallo??
      Reicht es nicht aus, das NUR die NSA diese Technik benutzt???
      Mal ganz davon abgesehen, das natürlich auch andere Firmen und Geheimdienste sich wohl dieser Technik bald bedienen werden.

      1. Ich ziehe mal noch eine Parallele zu Massenvernichtungswaffen: ABC-Waffen sind geächtet und wer diese – außer den UN-Veto-Mächten – produziert, hat mächtigen Ärger. Da waren z.B. Libyen, Syrien, Irak, Iran und Nordkorea nur Beispiele aus jüngster Zeit.

        Solange es eine solche Ächtung nicht für Cyber-Waffen gibt, haben wir nun einmal eine Rüstungsspirale. Das perfid Neue ist nun aber, dass diese Krieg scheinbar ohne Blutvergießen, aber mit der Zerstörung von Freiheit geführt wird. Ein Grund, warum es noch keine soziale Bewegung gegen die Massenausspähung gibt.

      2. Ich denke nicht, dass eine Ächtung für „Cyber-Waffen“ wie den Quatenrechner hilfreich ist, Transparenz muss her!

        Technik, die auf Quantentheorie basiert, ist erstmal nichts schlechtes, sie kann z.B. auch helfen Kryptoverfahren zu Entwicklung, welche gegen Angriffe durch Quantencomputer resistent sind.

        „Hört auf schnellere Rechner zu bauen, damit keiner unsere Krypthographie knacken kann“ ist ein ganz schlechter Ansatz…

    2. Ich kann dir garantieren, dass dieses System NICHT nur von der NSA benutzt werden wird, sondern von jedem der es bezahlen kann – und das werden immer mehr, je besser und billiger die Technik wird. In 20-30 Jahren ist das wahrscheinlich ein Standardbauteil in jedem PC.
      Es bringt nichts, Technologie zu verbieten, sobald sie nicht nur von großen Nationen sondern auch von, sagen wir mal, einer mittelgroßen Firma bezahlbar wird. Das führt nur dazu, dass zwielichtige Organisationen diverser Art ein Monopol darauf haben, und Gegenmaßnahmen nur schwer entwickelt und getestet werden können (siehe Hackertoolverbot).

  5. Die einzige Forderung dürfte wohl sein:“Alle Geheimdienste abzuschaffen“!
    Was ist das denn für eine Welt in dem wir fordern Gesetze oder vorherrschende Bedingungen zu unterlaufen?

    1. und wie würde soetwas praktisch aussehen?
      Denkst du dass die Damen und Herren der Dienste sich einfach mal so wegschieben lassen? Bei dem Schadenspotential was die anrichten könnten traut sich doch keine Regierung dort Hand anzulegen.

    2. Solange es Islamisten und andere religiöse Fanatiker gibt die die Welt mit Terror überziehen solange wird man auf Geheimdienste wohl nicht verzichten können, leider.

      1. Nur gab es nie eine Festnahme aufgrund der Datenerhebungen irgendwelcher Geheimdienste.
        Da bist Du genau auf deren Propaganda Aufgesessen…:-(

      2. Ich möchte hinzufügen, dass es auch gut so ist dass es deswegen nie Festnahmen gab. Im Geheimen gesammelte „Beweise“ machen eine Verteidigung und einen fairen Prozess unmöglich und den Rechtsstaat (oder was davon noch übrig ist) zu einer Farce.

      3. lol, als würde die Polizei nicht im Geheimen Beweise sammeln. Ich glaube du hast da was Grundlegendes nicht verstanden :)

    3. @qwertzman
      Sicher tun sie das nur haben normalerweise eine völlig andere Aufgabe, als eine Milliardenschere NSA, die nur dafür da ist uns alle auszuspähen.

  6. Es gibt einige Möglichkeiten, aber letztendlich läuft es doch darauf hinaus diese System abzuschaffen.
    Eine echte Revolution wäre natürlich ein probates Mittel.
    Aber auch Generalstreiks oder einfach nur Passiven Widerstand zu leisten wäre ein kleiner Anfang; Passiver Widerstand, ein paar Gedanken dazu.
    Die Grundnahrungsmittel in der Umgebung kaufen, achtet auf „Faire Trade“, wie zum Beispiel bei der Teekampagne, in Berlin.
    Kauft keine neuen Autos mehr, denn die alten sind meist viel billiger. Das ist mein Spezialgebiet, ihr könnt mir glauben, dass die neuen Autos allesamt eine Hightech-Wegwerf-Ware darstellen.
    Glaubt nicht an den Quatsch von Abgasnormen, niedrigeren Co2 Ausstoß.
    Das ist wie mit der Feinstaubplakette und vielen Anderem auch, eine absolute Verarschung.
    Breitbandbildschirme, Handys, PC´s auch mal ein paar Jahre länger benutzen, viele technische Geräte braucht sowieso kein Mensch.
    Erteilt dem Konsum eine klare Absage, kauft keine „Apple“ Produkte mehr und kauft nicht bei Amazon, keine Markenklamotten, tankt kein E10 und spendet nicht an den WWF!!!(Der Pakt mit dem Panda anschauen).
    Reden, Diskutieren, Stellung beziehen….informiert euch….Und sucht nicht mehr mit „GOOGLE“ sondern z.B. mit „IXQUICK“ und stellt euer Betriebssystem endlich auf “LINUX” um.
    Keine Aktien und Börsenspekulationen, nehmt nicht vorschnell Kredite auf, am besten ihr verzichtet ganz darauf.
    Vergesst nicht, dass unser gesamtes System auf Kredite und unbegrenztes Wachstum aufgebaut ist.
    Treibt wieder Tauschhandel wenn irgend möglich.
    Das gleiche gilt für die Kreditkartenbenutzung, benutzt wieder Bargeld, das ist nicht zurück zu verfolgen.
    So bekommt man das System in die Knie.
    Schaut mal nach, ob ihr wirklich all Eure Versicherungen überhaupt braucht, die ihr Euch in all den Jahren angeschafft habt.
    Wenn die Menschen nur noch das kaufen würden, was sie wirklich benötigen, wird sich dieses System ganz schnell als ad acta bestätigen.
    Ach, und holt euer Geld von der Bank, falls ihr noch Welches habt…;-)
    Fazit: Die einzige Handlungsalternative sei „eine Kultur der Verweigerung“. Dies bedeute, „jede Mitverantwortung für ‚Marktwirtschaft und Demokratie‘ zu verweigern, nur noch ‚Dienst nach Vorschrift‘ zu machen und den kapitalistischen Betrieb zu sabotieren, wo immer das möglich ist“.

    1. Treibt wieder Tauschhandel wenn irgend möglich.

      Tauschhandel ist die Quelle des Problems, ob mit oder ohne Geld ist dabei ziemlich egal, Marx selbst hat das im Kapital I schon recht nüchtern festgestellt mit dem sarkastischen Vergleich

      Ebensowohl könnte man den Papst abschaffen und den Katholizismus bestehen lassen.

      1. Lach, es geht ja hier auch um das primäre Ziel diese System zu unterlaufen und scheitern zu lassen.
        ich würde auch gerne die Kirchen brennen sehen…;-)

      2. Im Übrigen halte ich den „Tauschhandel“ für die urspringlichste Form menschlicher Sozialisation.

      3. Und nochmal „qwertzman“
        Was hat „nachhaltig Leben“ mit „Kleinbürgertum“ zu tun?
        Im Übrigen fehlt es mir an nichts und ein schlechtes Gewissen habe ich auch nicht, das lässt mich wenigstens gut schlafen…;-)

    2. Revolution und dann doch nur FairTrade? :D Und dann sind natürlich Hightech-Wegwerf-Waren und niedriger CO2-Ausstoss Verarschung, klaaar.
      Achja, und Amazon ist auch ganz pöse.
      Und Börsenspekulationen und Wirtschaftswachstum auch ganz schlecht. xD
      Weißt du was du bist?
      Kommunist bist du garantiert nicht, sondern ein hohler kleinbürgerlicher Anarchist oder einfach Vollidiot.

      Wie wäre es einmal auf den Punkt zu kommen. Es geht nicht darum das System zu unterlaufen, sondern Bedürfnisse zu befriedigen und Fähigkeiten zu entfalten. Wenn ich damit FairTrade-Schokolade kaufe, schön, aber nur weil sie mir besser schmeckt. Oder wenn ich den Flachbildfernseher im Laden stehen lasse, nicht weil ich das System unterlaufen will, sondern weil ich mir überlege, dass ich ihn nicht brauche, wenn ich ihn aber brauche, kaufe ich ihn auch und lasse ihn nicht aus ideologischen „das System wargh-wargh-wargh“-Gründen bei Amazon stehen. Und nö, ich beute mich garantiert nicht selbst aus und renn wieder in den nächsten Laden um den schlechten Service zu „genießen“ und dessen Eigentümer zu „unterstützen“.

      1. @qwertzman..die 3.
        Ich schrieb, das eine echte Revolution ein probates Mittel wäre.
        Weiterhin betonte ich, das man selbst jederzeit anfangen könnte bestimmte Dinge einfach zu unterlassen um dem System nicht weiter dienlich zu sein
        Ich komme aus der Automobilbranche und wenn Du wüsstest wie die Messwerte festgelegt werden, und was sie letztlich bewirken, würdest Du nicht so blöd daher reden.
        das verhält sich ganz ähnlich wie bei der Feinstaubplakette, die Nachweislich nichts gebracht hat, außer, das sich die Leute eben neue Wagen gekauft haben…:-(
        Es geht mir um beides, nämlich „Nachhaltigkeit“ und den Boykott des Systems…
        Ich schieße meinen Eintrag mit einem Zitat von Robert Kurz, das ich schon weiter ober erwähnt habe und hier nochmal in voller Länge wiedergeben möchte: “ Bei der Lösung dieser Probleme handle es sich letztlich „weder um ein materielles noch um ein technisches oder organisatorisches Problem, sondern allein um eine Bewusstseinsfrage“. Es aber wahrscheinlich, dass der dazu notwendige „Bewusstseinssprung“ nicht mehr vollzogen wird. Der Kapitalismus sei aber dennoch nicht überlebensfähig, was „die unaufhaltsame Entzivilisierung der Welt“ nach sich ziehe. Die einzige Handlungsalternative sei „eine Kultur der Verweigerung“. Dies bedeute, „jede Mitverantwortung für ‚Marktwirtschaft und Demokratie‘ zu verweigern, nur noch ‚Dienst nach Vorschrift‘ zu machen und den kapitalistischen Betrieb zu sabotieren, wo immer das möglich ist“!
        Aber mit Einem hast Du Recht, ich bin ein Anarchist..;-)

  7. Vor etwa 2 Jahren war ich als Physikstudent an der Uni Aarhus an einem Workshop zu ultrakalten Atomen. Einer der beteiligten Profs erzählte damals, dass jeder Forscher auf dem Gebiet darauf hinweist, dass solche Forschung potentiell für Quantencomputer nützlich sein könnte, und einige, auch er selbst, dadurch Forschungsgelder von der NSA bekommen haben.
    Also in der Forschungsgemeinde auf dem Gebiet ist das schon lange bekannt …

    1. Die Forschung ist absolut zielgerichtet und arbeitet auch nur noch Systemimmanent.
      Eine freie Forschung ist heutzutage kaum noch möglich…:-(

      1. Ich hab‘ es schon mal zu dem Artikel über die angebliche Waffenforschung an deutschen Unis geschrieben, und ich schreibe es auch gerne wieder: So läuft das nicht. Geheimdienste, Rüstungsindustrie, etc gehen nicht zu den Profs und sagen „Forsch das!“ (zumindest habe ich das so noch nie gesehen). Die Profs haben schon ihre Interessen und Projekte, und suchen sich dann jemanden, der das (oder so was ähnliches) bezahlt. Da wird dann in der Bewerbung geschrieben was der Geldgeber hören will, aber am Ende ist es immer noch Grundlagenforschung, und die Arbeitsgruppe entwickelt genau das was sie sonst auch gemacht hätte.

      2. Forschung arbeitet immer systemimmanent. Produktionsmittel lassen sich aneignen und für das Ziel (ich glaub du findest Kommunismus garnicht so schlecht) Kommunismus einspannen, und genau das tun Profs, wie Autolykos sagt, auch. Denn du kannst nicht Wissen verbieten, irgendwann steht es immer tendenziell allen (vielleicht auch nur unbewusst als Produkt zu kaufen im Supermarkt) zur Verfügung. Und das ist sogar verdammt gut, denn dann lassen sich wirklich alle Bedürfnisse befriedigen und Fähigkeiten entfalten. Oder willst du doch lieber Verzicht üben? Na, dann viel Spaß in deiner pseudofriedlichen Welt.

  8. Das Pentagon hat bereits 1998 einen Etat von 300 millionen Dollar zur Erforschung der Quantenkryptographie aufgestellt.

  9. Mehrfach schon gelesen ist auch die einzige schlüssige Erklärung imho:

    Es ist ein Bluff damit man denkt verschlüsseln ist sinnlos ;)

    1. Hää? Verschlüsseln wäre doch sogar dann noch sinnvoll, oder verschlüsselst du nur, damit staatliche Stellen nicht mehr mitlesen können? Ehrlich gesagt verschlüssel ich auch deshalb, aber auch damit meine Daten nicht kriminellen in die Hände fallen.

Dieser Artikel ist älter als ein Jahr, daher sind die Ergänzungen geschlossen.