Kann die NSA einen Quantencomputer entwickeln, mit dem sich bisher unlösbare Codes knacken lassen? Falls ja, könnte die Welt im Chaos versinken.

Wenn es etwas Neues zum Thema Verschlüsselung gibt, ruft bei mir oft die Redaktion von FOCUS Online an und fragt, ob ich einen Artikel darüber schreiben kann. Vor ein paar Tagen war es wieder so weit. Die Washington Post hatte herausgefunden, dass in den Enthüllungsunterlagen von Edward Snowden auch von Quantencomputern die Rede ist. Das war eigentlich nichts Sensationelles. Überraschend wäre es eher, wenn sich die NSA nicht mit Quantencomputern beschäftigte – schließlich eignen sich diese hervorragend dazu, bestimmte Verschlüsselungscodes zu knacken. Eine interessante Meldung war es jedoch allemal. Und deshalb hat mich FOCUS Online gebeten, einen Artikel über Quantencomputer zu schreiben. Hier ist er.

Zum Thema Quantencomputer gibt es bei YouTube einige Videos. Hier ist eines (auf Englisch):

Kommentare (21)

  1. #1 Peter Lichtenberger
    Hinterland West, gleich Links.
    8. Januar 2014

    Dass die Amis jetzt plötzlich in Sachen “Quantencomputer” nervös werden hat nur einen Grund: Die EU (diesmal im selten einigen Verbund mit der Schweiz) arbeiten ebenfalls an den Grundlagen für einen Quantencomputer. Und da die hiesigen Köpfe ebenso schlau sind wie jene jenseits des grossen Teichs, ist man auf der anderen Seite eben nervös geworden. Während man kurioserweise auf der “unserigen” Seite mehr an kommerzielle Schutzmechanismen auf QT-Basis denkt, will man auf der anderen Seiten vor allem an das Knacken allmöglicher Verschlüsselungen. So einfach ist das 🙂

  2. #2 Svechak
    8. Januar 2014

    Soso, es geht also um einen “Monsterrechner, der alle erdenklichen, bisher unlösbaren Codes knacken könnte”. Ich nehme an, dass sich Focus diese Formulierungen ausgedacht hat. Klaus Schmeh wird wohl wissen, dass man mit einem Quantencomputer nicht “alle erdenklichen” Codes knacken kann, sondern nur bestimmte. Im Artikel steht das ja auch.

  3. #3 Hanno
    Berlin
    9. Januar 2014

    Gibt es eine Quelle dafür dass sich das BSI mit Post-Quanten-Kryptografie befasst? Das wär mir nämlich neu.

    • #4 Klaus Schmeh
      9. Januar 2014

      >Gibt es eine Quelle dafür dass sich das BSI mit Post-Quanten-Kryptografie befasst?
      Ich weiß nicht, ob es eine offizielle Quelle gibt. Bei der Recherche für mein Buch “Die Erben der Enigma” hatte ich mit dem BSI zu tun. Dabei ging es auch um Quantenrechner. Offensichtlich weiß man beim BSI über dieses Thema gut Bescheid, lässt sich aber naturgemäß nicht in die Karten schauen.

  4. #5 Dave
    9. Januar 2014

    Wenn die NSA einen Quantencomputer hätte, der dieser RSA gefährlich werden könnte, dann würden wir es bereits vermutlich wissen längst das es möglich ist.

    Denn:
    >Und da die hiesigen Köpfe ebenso schlau sind wie jene jenseits des grossen Teichs<

    Wenn eine neue Technik zum Knacken bereit steht, würde diese Technologie eben auch für die Codemacher zur Verfügung stehen.

  5. #6 threepoints...
    9. Januar 2014

    @ Dave #4

    Zitat:

    “Wenn die NSA einen Quantencomputer hätte, der dieser RSA gefährlich werden könnte, dann würden wir es bereits vermutlich wissen längst das es möglich ist.”

    -> Phantastisch, …. wie naiv man doch in die Welt schauen kann. Wer ist “wir”? Und warum suggeriert mir diese Aussage, dass “drüben” die Lösung gefunden wurde und hier davon auch gleich alle davon wissen werden sollen?

    Noch absurder wäre die Vision, dass die Technologie schon lange bekannt und im Einsatz ist, aber alle Beteiligten und suggerierte Konkurenten (die ja davon wissen) beharrlich über diese Tatsache schweigen und vorgeben, an der Sache dran zu sein, aber leider noch nicht so weit wären…?

    Derzeit wäre eine solche Wahrheit in der Öffentlichkeit wahrscheinlich tatsächlich Auslöser für Chaos und Katastrophe.

  6. #7 Dr. Webbaer
    9. Januar 2014

    Helfen Sie bitte mal kurz Ihrem Kommentatorenfreund: Q-Computer könnten asymmetrische Kryptosysteme unmöglich machen und bedingten die Rückführung auf symmetrische Kryptosysteme und Botendienste?

    MFG
    Dr. W

    • #8 Klaus Schmeh
      9. Januar 2014

      Man kann es so zusammenfassen:
      1) Quantencomputer könnten alle GÄNGIGEN ASYMMETRISCHEN Kryptosysteme wirkungslos machen (z. B. RSA, DH, DSA, ECC). Es gibt aber weniger gängige asymmetrische Kryptosysteme, die QC-resistent sind (z. B. NTRU, McEliece, HFE).
      2) Quantencomputer könnten alle SYMMETRISCHEN Kryptosysteme deutlich schwächen. Verwendet man ausreichend lange Schlüssel (z. B. 256 Bit), dann kann ein QC allerdings nichts ausrichten.

  7. #9 Dave
    9. Januar 2014

    >Phantastisch, …. wie naiv man doch in die Welt schauen kann. Wer ist “wir”? Und warum suggeriert mir diese Aussage, dass “drüben” die Lösung gefunden wurde und hier davon auch gleich alle davon wissen werden sollen?<

    Weil eben nicht nur einen Ort an dieser Technik geforscht wird ganz einfach. Wenn dies nicht so wäre würden wir uns ja garnicht darüber unterhalten können.

    Wenn die Zivile Forschung einen einfachen QComputer realisieren kann, kann man sich eben doch denken das z.B die NSA ihren Milliarden wohl weiter sein könnte.

    Genau Wissen kann man es natürlich nicht "nur vermuten"
    Kam in meinem Post vieleicht etwas falsch rüber.

  8. #10 threepoints...
    9. Januar 2014

    @ Dave #8

    Naja, von der Forschung zur Lösung sind es vor aller Lösung unbekannte Wege, selbst wenn man die Theorie in gröbsten Strukturen schon mal als Vision vorrätig hat – weltweit.

    Das “muß” man nicht zwingend daruf kommen, nur weil offenichtlich alle Forschung veröffentlicht werden.
    Mir fällt dazu aber ein, wie das mit der Concord damals war (und der russischen Maschine – TU 144). Wie sonderbar gleichzeitig und wie sonderbar gleichförmig die Ergebnisse in die Welt kamen.
    Man könnte meinen, die bösen Russen hätten eben spioniert, was das Zeug hält – oder umgekehrt.
    Man kann aber auch einen natürlichen Quantencomputer annehmen, der es ermöglichte, dass gleiche Zielsetzungen auch (fast) gleiche Ergebnisse liefern. Meint: Was die Ingeneure sich zielgesetzt hatten, ergab beim Stand der Technik und Erkenntnis gleiche Ergebnisse – heisst: sie haben gleiches gedacht – aber warum nur? Wie erscheinen hier Sinn und Zweck den verschiedenen Ingeneuren und wie aus der Natur?

    Daher bin ich gegen die Entwicklung eines Quantencomputers. Eine Maschine, die dazu fähig wäre, an die Gehirn-Computer-Schnittstelle angeschlossen zu werden oder diese Schnittstelle gar selbst ist.
    Aber andererseits diese Art Fortschritt nicht nur möglich ist, sondern zwingend sowieso eintritt – aus viellerlei scheinbar chaotisch sich bedingenden Gründen. Mindestens dieser: Wenn ich/wir es nicht machen, macht es wer anders. Dann besser ich/wir.

  9. #11 Jerry Who
    9. Januar 2014

    Sie schreiben, dass es QC-resistente Verfahren gibt. Ist das denn bewiesen oder weiß man nur nicht, wie ein QC helfen könnte. Meines Wissens sind die aktuellen Verfahren, die auf der Primfaktorzerlegung oder dem diskreten Logarithmus beruhen, nur deshalb sicher, weil man noch keinen effizienten Algorithmus (ohne QC) gefunden hat. Bewiesen, dass es solche nicht geben kann, ist das aber nicht.

    • #12 Klaus Schmeh
      9. Januar 2014

      Stimmt, es gibt keinen Beweis, dass die als QC-sicher geltenden Verfahren auch wirlich QC-sicher sind. Das ist nur eine Vermutung. Allerdings gibt es in der Kryptologie generell nur sehr wenige Sicherheitseigenschaften, die man beweisen kann. Man muss sich also auf den Grundsatz “sicher ist, was nicht als unsicher beweisen wurde” verlassen.

  10. #13 Dr. Webbaer
    10. Januar 2014

    @ Herr Schmeh

    Quantencomputer könnten alle GÄNGIGEN ASYMMETRISCHEN Kryptosysteme wirkungslos machen (z. B. RSA, DH, DSA, ECC). Es gibt aber weniger gängige asymmetrische Kryptosysteme, die QC-resistent sind (z. B. NTRU, McEliece, HFE).

    Danke für die Erläuterung. Wenn Sie mal Lust & Zeit haben können Sie gerne etwas dazu (z. B. NTRU, McEliece, HFE) schreiben.

    MFG
    Dr. W (der sich’s zwar selbst anlesen könnte, aber Sie wissen schon…)

    • #14 Klaus Schmeh
      10. Januar 2014

      >Wenn Sie mal Lust & Zeit haben können Sie
      >gerne etwas dazu (z. B. NTRU, McEliece, HFE) schreiben.
      Ich habe einen Artikel dazu in Arbeit, der im Frühjahr in einer Computer-Zeitschrift erscheinen wird. In meinem Buch “Kryptografie – Verfahren, Protokolle, Infrastrukturen” gibt es ebenfalls Infos dazu. Allerdings sind dieses Verfahren mathematisch recht komplex, wodurch ich jeweils nur die groben Ideen dahinter beschreiben kann.

  11. #15 b@tchman
    10. Januar 2014

    Es ist ja auch noch nicht vom Tisch, ob auf QCs nicht P=NP gilt, was praktisch jede Verschlüsselung brechen würde, außer eben die, bei denen man nicht ermitteln kann ob ein geratener Schlüssel der richtige ist, was ja genau die beweisbar sicheren Verfahren auszeichnet.
    Verfahren, bei denen die Entschlüsselung auf herkömmlichen Rechnern nicht in poly-Zeit geht lasse ich hier mal aus, die sind nicht praktikabel.

    Da QCs ja ein wenig Richtung “eingebauter Nichtdeterminismus” gehen, halte ich es für denkbar, das auf QCs P=NP gelten könnten.

    mfg,
    b@tchman

  12. #16 rolak
    10. Januar 2014

    halte ich es für denkbar, das auf QCs P=NP gelten könnten

    Das ist selbstverständlich eine Tautologie, b@tchman, da Du es geschrieben und damit unausweichlich auch vorher gedacht hast. Nichtsdestotrotz ist “auf QCs [gilt] P=NP”! unsinnig – entweder es gilt und alle, auch ‘normale’ Rechner können die Probleme angenehm knacken, wenn denn endlich der passende Algorithmus ausgetüftelt ist oder es gilt nicht (intuitiv näherliegend, doch was heißt das schon..) und alles bleibt wie es ist. Die bloße Tatsache, daß mit Quantencomputern Probleme rechtzeitig gelöst werden können, an denen sich selbst Tianhes die Zähne ausbeißen, läßt in keiner Weise automagisch den Schluß zu, daß sie alle NP-Probleme derart abarbeiten können (siehe auch wiki).

  13. #17 b@tchman
    14. Januar 2014

    @rolak
    Für die strenge Definition von P und NP hast du recht, denn in die geht der Begriff der (klassischen) Turingmaschine ein. Sollten QCs ein echt anderes Berechenbarkeitsmodell liefern (soweit ich weiß ist das noch offen), dann wären die Klassen P und NP für dieses Modell natürlich erstmal nicht definiert. Was ich gemeint habe ist:
    Es ist im Moment nicht ausgeschlossen, dass es für QCs einen effizienten Algorithmus gibt, der ein NP-vollständiges Problem löst. Zu deinem letzten Satz:

    “Die bloße Tatsache, daß mit Quantencomputern Probleme rechtzeitig gelöst werden können, an denen sich selbst Tianhes die Zähne ausbeißen, läßt in keiner Weise automagisch den Schluß zu, daß sie alle NP-Probleme derart abarbeiten können”

    Sollte das schnell lösbare Problem NP-hart sein, dann doch. Dann lässt sich genau dieser Schluss ziehen. Das ist ja grade der Trick an NP-Härte.

  14. #18 rolak
    14. Januar 2014

    Sollte das schnell lösbare Problem NP-hart sein, dann doch.

    Wie Dir vielleicht aufgefallen ist, b@tchman, benutzte ich im Gegensatz zu Dir keinen Konjunktiv – es gibt Probleme, die (wenn alles gut geht) nicht von klassischen, jedoch von Quantenkomputern effizient gelöst werden können – doch kein einziges davon ist NP-hart. Gibt auch keine Rauchzeichen, daß dergleichen demnächst (x Jahrzehnte) anstünde.

    Mittels falls/sollte/könnte ist schnell und manchmal sogar schön spekuliert, doch der von Dir zitierte Satz bezieht sich auf den aktuellen Stand und dort gilt er.

  15. #19 b@tchman
    15. Januar 2014

    Wenn Weltanschauungen auf einander treffen 😉
    Ich denke wir können uns einigen auf:
    Nach aktuellem Stand der Forschung können OCs RSA&Co gefährlich werden, aber zum Thema P=NP gibt es nichts.

    Wie lange das so bleibt / ob das so bleibt, da will ich mich nicht zu äußern, denn Shor hat seinen Algorithmus auch erst in den 1990’ern entwickelt. Vor 30 Jahren hatte das auch keiner auf dem Schirm und faktorisieren war noch “schwer”.

  16. #20 Fermat
    24. Januar 2014

    FOCUS-Artikel: “Die Quantenmechanik hat so manche seltsame Erkenntnis zu bieten. Je näher sich ein Gegenstand der Lichtgeschwindigkeit nähert, desto langsamer vergeht in ihm die Zeit.”

    Damit hat die Quantentheorie nichts zu Tun. Die Zeitänderung beschreibt schon die Spezielle Relativitätstheorie.

    • #21 Klaus Schmeh
      25. Januar 2014

      Stimmt, darauf haben mich schon mehrere Leute hingewiesen.