Quantencomputer könnte bald Realität werden

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Quantencomputer könnte bald Realität werden

      "An international research group led by scientists from the University of Bristol has developed a new approach to quantum computing that could soon be used to perform complex calculations that cannot be done by today’s computers."
      http://www.bristol.ac.uk/news/2010/7216.html

      Übersetzung:
      "Eine internationale Forschergruppe, geführt von Wissenschaftlern der Universität Bristol, hat einen neuen Ansatz zum Quanten-Computing entwickelt, der bald für komplexe Berechnungen verwendet werden könnte, die von heutigen Computern nicht ausgeführt werden können."

      Es handelt sich um einen Quanten-Chip. Ein qbit (quantum-bit) kann - im Gegensatz zu normalen Bits - mehrere Zustände und diese gleichzeitig darstellen. Konventionelle bits sind dagegen binär. Alleine aus dieser Tatsache erklärt sich das gewaltige Potenzial, welches in den Quanten-Rechnern stecken könnte, sollten sie dereinst serienreif sein. Noch ist es nicht absehbar, wann es so weit sein wird, aber ein weiterer Schritt auf dem Weg dorthin ist gemacht worden.
      Diese Rechenkraft könnte natürlich auch wesentlich schneller und effizienter Passwörter und Verschlüsselungen knacken.
      Wo wir sind, da ist immer auch Ägypten.
      ~☤~
    • RE: Quantencomputer könnte bald Realität werden

      Illuminatus schrieb:


      Diese Rechenkraft könnte natürlich auch wesentlich schneller und effizienter Passwörter und Verschlüsselungen knacken.


      Das stimmt so nicht ganz. Für Faktorisierung gibt es einen schnellen Algorithmus für Quantencomputer: den Shor-Algorithmus, welcher mit hoher Wahrscheinlichkeit in polynomialer Laufzeit eine Faktorisierung berechnet.
      Dieser benötigt allerdings ein paar tausend Qbits zur Ausführung. Da jedoch RSA (dessen Sicherheit darauf beruht, dass für bislang verwendete Rechnerarchitekturen bislang kein schneller Faktorisierungsalgorithmus bekannt ist) eine hohe Bedeutung für Absicherung von Banktransaktionen (und ein paar anderer Internet-Sicherheitsverfahren, die ich jedoch hier nicht aufzählen will) hat, stellt dies dennoch eine Bedrohung dar, insbesondere weil vermutet wird, dass man ähnliche Verfahren auch für andere asymmetrische Verschlüsselungsverfahren entwickeln könnte.

      Für symmetrische Verschlüsselungsverfahren gilt dies jedoch nicht unbedingt. Der Standard-Angriff auf DES basiert auf einer geschickten Brute-Force-Implementierung unter Ausnutzung der geringen Schlüssellänge von 56 Bits.

      Das mathematische Problem, was sich hinter diesem Angriff verbirgt, ist in einer ungeordneten Liste einen bestimmten Eintrag zu finden.

      Auf klassischen Rechnern braucht man hierfür offenbar O(n) (n - Anzahl Einträge der Liste) Schritte - man muss also jeden Eintrag betrachten.

      Auf Quantencomputern kann man das selbe Problem in O(sqrt(n)) Laufzeit mit hoher Wahrscheinlichkeit lösen.

      Das heißt jedoch nichts anderes, als dass man das selbe Sicherheitslevel halten kann (natürlich sofern kein besseres Verfahren gefunden wird), indem man einfach die Schlüssellänge quadriert.

      Ich bin Anhänger der These, dass eine große Gefahr auf aktuelle Verschlüsselungsverfahren nicht Quantencomputer darstellen, sondern algorithmische Durchbrüche (im Extremfall ein kompletter Zusammenbruch der vermuteten Komplexitätshierarchie - auch wenn daran niemand so wirklich glauben mag, weil die Konsequenzen zu unintuitiv wären).
    • RE: Quantencomputer könnte bald Realität werden

      Auch wenn die Folgerung stimmt, dass die Passwörter länger werden müssen, um das selbe Sicherheitslevel zu wahren (da man sonst einfach nach dem selben Verfahren Brute-Force über den Passwortraum machen kann), muss ich einen Fehler korrigieren: das Passwort bildet nicht den Schlüssel.

      Um die in den Verschlüsselungsverfahren verwendeten Schlüssel bestimmter Keylänge zu erzeugen, verwendet man niemals direkt das Passwort als Schlüssel, sondern man wendet auf das Passwort, ergänt um einen zufällig generierten Seed (um Rainbow-Table-Angriffe zu erschweren) eine geeignete Hash-Funktion (nach aktuellem Stand beispielsweise einen Algorithmus aus der SHA-2-Familie, z. B. SHA-256, SHA-384 o. ä.) an. Das Ergebnis bildet dann den Schlüssel.

      Ich muss zugeben, dass diese absoluten Grundlagen von sicherer Schlüsselverwaltung von einigen Webentwicklern leider nicht berücksichtigt werden (das führt dazu, dass wenn die Webseite gecrackt wird, man wahlweise (wenn Passwörter im Klartext abgespeichert wurden) sämtliche Passwörter zugreifbar sind oder - wenn nicht für jedes Passwort ein Seed verwendet wurde - viele häufig verwendete Passwörter per Rainbow-Tables rekonstruiert werden können (die Verwendung von Seeds macht die Nutzung von Rainbow-Tables nicht unmöglich, aber erschwert sie stark, wenn das Passwort hinreichend lang gewählt wurde)), aber das sollte man sich nicht als Vorbild nehmen.