Verschlüsselung im Quantenrechnerzeitalter

[Mark]

Mal theoretisch angenommen ein Quantencomputer wäre konstruierbar.. dann wäre ja theoretisch auch jede herkömmliche Verschlüsselung hinfällig, weil ein Quantenrechner den Code selbst mit den dümmsten brute-force-Methoden in 0 Sekunden knacken kann..
Wie könnte dann die Verschlüsselung der Zukunft überhaupt noch laufen ?

[1von6,5Milliarden]

Könnte es sein, dass du "Passwörter" mit "Verschlüsselung" verwechselst?

[Klaus]

Offensichtlich verwechselt er das.
Herkömmliche Verschlüsselungsverfahren sind mit einem Quantencomputer leicht zu knacken, da dieser QC eben alle möglichen Ergebnisse liefert, im Gegensatz zum herkömmlichen Rechenknecht. Ein völlig anderes Problem ist die Quantenverschlüsselung.

[Nanna]

Die Quantenverschlüsselung ist ja keine Verschlüsselung, sondern eigentlich eine Methode, mit der man feststellen kann, ob der Datenverkehr abgehört wird (und zwar wegen physikalischer Gegebenheiten mit 100%iger Sicherheit). Vielleicht verschicken wir unsere Daten in Zukunft im Klartext, können aber sichergehen, dass sie nicht abgehört werden, weil die Übertragung in dem Moment abgebrochen werden kann, in dem sich jemand einklinkt. Was dadurch nicht gelöst wird, ist die Sicherheit von Daten auf physischen Medien, die in die falschen Hände geraten. Außerdem kann man das Problem des Abgehörtwerdens nur feststellen, nicht umgehen, man wird also vom Abhörenden zum Kontaktabbruch gezwungen. Darüberhinaus weiß ich nicht, ob ich absolut einbruchsichere Kommunikationssysteme in den Händen von Mafia- und Terrororganisationen sehen möchte.

Vielleicht wird es dann ja wieder so wie früher zu Papierzeiten und Daten werden wieder physisch gesichert: In Inselnetzwerken und auf tragbaren Datenträgern mit Schloss außenrum.

[Klaus]

Die Quantenverschlüsselung ist ja keine Verschlüsselung

Natürlich ist das eine Verschlüsselung. Du kannst nämlich sonst nicht feststellen ob jemand den Datenstrom mitlauscht, erst durch die entsprechenden Messpunkte und ihre Koordinaten, dass entsprechende Gegenstück hat der Empfänger, ist die Veränderung im Status der Quantenteilchen mess-und feststellbar.

[ujmp]

Offensichtlich verwechselt er das.

Mark hat nichts verwechselt. Eine Verschlüsselung basiert auf einem Schlüssel, der qualitativ nichts anderes ist als ein Passwort, nämlich irgendein String. Derzeit gängige Veschlüsselungen beruhen auf der relativen Unwahrscheinlichkeit den String zu erraten. Die brute force Methode würde beim sehr schnellen QC auch bei sehr langen Schlüsseln in Null komma nix fertig sein, weshalb solche Verschlüsselungen dann wertlos wären.

[1von6,5Milliarden]

Nein, eine Verschlüsselung und der Schlüssel (i.S.v. Passwort) sind zwei komplett unterschiedliche Sachen.
Um es dir mal simpel zu erklären:
Du hast ein WLAN und verschlüsselst dies mit WEP und nimmst das Passwort 1234567890123
Als Angreifer hast du zwei Möglichkeiten: Du kannst versuchen die Verschlüsselung zu knacken - dies geht heute sehr leicht und ist fast schon trivial - oder per Brute-Force-Angriff das Passwort zu "erraten"

Du hast ein WLAN und verschlüsselst dies mit WPA und nimmst den (identischen) Schlüssel (= Passwort) 1234567890123
Als Angreifer hast du zwei Möglichkeiten: Du kannst versuchen die Verschlüsselung zu knacken - dies geht heute unter bestimmten Bedingungen, ist aber nicht trivial - oder per Brute-Force-Angriff das Passwort zu "erraten"

Die Verschlüsselung zu knacken ist in beiden Fällen unterschiedlich zu bewerkstelligen, der Brute-Force-Angriff könnte identisch erfolgen.

[ujmp]

Mag sein, aber ein QC macht diese Verschlüsselungen allein deshalb wertos, weil er so schnell mit dem Durchprobieren von Milliarden Schlüsseln fertig ist. Etwa nicht?

[1von6,5Milliarden]

Jede(!) stärkere Rechenleistung hat das Potential gut oder schlecht eingesetzt zu werden. Gegen Passwortangriffe mit immer gigantischerer Rechenleistung hilft allerdings simpelste Vorrichtung die mit noch so extremer Rechenleistung nicht zu knacken ist. Deshalb ist dein und Marcs Ansatz einfach aber nur sehr kurz gedacht:
- Man erlaube nur x Abfragen pro Zeiteinheit
- Man erlaube nur x falsche Eingaben
--- sperre dann ganz
--- sperre dann für eine bestimmte Zeit (kann und wird auch mit wachsenden Zeitfenstern eingesetzt)
--- setze irgendeine andere Bremse (z. B. eine Wiederholung einer Anmeldeprozedur)
...

Extreme Rechenleistung selber kann allerdings selbstverständlich Brute-Force-Angriffe beschleunigen, wenn solche Maßnahmen nicht getroffen werden können, ebenso kann solche Rechenleistung auf das Knacken der Verschlüsselung an sich genutzt werden. Weil diverse GPUs (Grafikprozessoren) heute bestimmte Rechenoperationen mit sehr hoher Geschwindigkeit erledigen können, werden Angriffe z.B. auf die WPA-Verschlüsselung mit diesen Prozessoren durchgeführt.

[ujmp]

Wenn du z.B. eine passwortgeschützte Datei knacken willst, baust du dir in deinem QC einfach eine Umgebung, die es der Datei oder dem Programm nicht erlaubt, irgendetwas zu schreiben; oder eine Umgebung, die nach jedem Versuch den Ausgangszustand in Nullkommanix zurücksetzt. Und Simsalabim bist du drin. Jetzt gib schon zu, dass ich recht habe!

[1von6,5Milliarden]

Nein. Denn das Passwort knacken und die Verschlüsselung knacjen eben zwei unterschiedliche Sachen sind.
Auch wenn für beides eine höhere Rechenleistung vorteilhaft ist und das Ergebnis z.B. bei "deiner" passwortgeschützten Datei identisch werden sollte (die Datei liegt unverschlüsselt vor)
Aber ein Brute-Force-Angriff (Ausgangsposting, dein Posting von gestern) zielt eben auf das Passwort (alle theoretisch möglichen Passwörter werden durchgespielt) und nicht auf die Verschlüsselung.

Bedenken darf man aber auch, je höher die Rechenlesitung zum Knacken einer Verschlüsselung oder zum Herausfinden eines Passwortes, desto höher ist natürlich auch die einsetzbare Rechenleistung zum Verschlüsseln. Das Passwort (oder der Sicherungsschlüssel wie auch immer) ist davon aber nur bedingt betroffen (= höhere Rechenleistung schafft kein besseres Passwort).
Auch deshalb muss man ja sein Sicherungssystem bzw. sein zu sicherndes System bzw. dessen Daten auch physikalisch schützen.

[Klaus]

In der Quantenkryptografie werden einzelne Lichtteilchen speziell präpariert und zwischen den Partnern ausgetauscht. Nach der Messung der daten werden alle Lichtteilchen nachbearbeitet.Im Ergebnis haben alle beteiligten Partner den gleichen Quantenschlüssel.
Ein möglicher Lauscher kann prinzipiell keine Information über diesen Datenschlüssel bekommen - egal welche erdenklichen Möglichkeiten er zur Verfügung hat. Denn nach den Gesetzen der Quantenphysik, hinterlässt jede Messung dauerhafte Spuren und kann daher sofort registriert werden.

[ujmp]

Halten wir fest: Herkömmliche Versschlüsselungstechniken werden durch Quantenrechner teilweise unbrauchbar. Für Quantenkryptografie braucht man keine Quantenrechner, das hat damit nichts zu tun.

[Klaus]

Es ist völlig egal, ob du Quantenkryptografie nur für die Datenleitung von vN-Architekturen einsetzt, oder aber bei Quantencomputern. Das Ergebnis ist dasselbe. Beim Mitlauschen der Verbindung werden die Quantenzustände verändert und damit sichtbar. Damit bleibt die Verschlüsselung von Daten im Zeitalter der Quantenrechner bestehen.

[Mark]

Könnte es sein, dass du "Passwörter" mit "Verschlüsselung" verwechselst?

Könnte es sein, daß jede Verschlüsselung auf einen Schlüssel zurückgeführt werden kann ?

[Mark]

Es ist völlig egal, ob du Quantenkryptografie nur für die Datenleitung von vN-Architekturen einsetzt, oder aber bei Quantencomputern. Das Ergebnis ist dasselbe. Beim Mitlauschen der Verbindung werden die Quantenzustände verändert und damit sichtbar. Damit bleibt die Verschlüsselung von Daten im Zeitalter der Quantenrechner bestehen.

Aha. Und wie sollen solche Daten von einem Platz zum anderen wenn sie nicht von Knoten weitergeleitet werden ? Wie soll das gehen wenn man den Datenstand nicht lesen darf, weil er sich sonst verändert ?
Da stecken noch viele theoretische Probleme in dieser Fantasietechnik. Das Problem ist ja aber auch nicht der Zustand wenn mal alles komplett umgestellt worden ist auf eine Supertechnik die per Definition alle Probleme löst, sondern der Übergang dorthin : sobald der erste Quantenrechner läuft kann jede Nachricht im Nullkommanix entschlüsselt werden.. rein theoretisch.

[Dissidenkt]

Das könnte dich interessieren Mark:
http://www.heise.de/tp/blogs/3/148161

Es scheint so, als wären die Möglichkeiten von Quantenrechnern begrenzt.
Kann jemand den Beweis verifizieren?

[Klaus]

@Mark
Ein Qunatencomputer arbeitet mit folgenden Prozessen.
1. Verschränkung
2.Superposition
3.Dekohärenz
Voraussetzung wir reden über Informationsverarbeitung.

Photon 1 am Ort A ist mit Photon 1+ am Ort B verschränkt. Das heißt beide Photonen besitzen die gleiche Polarität. Diese Polarität ist messbar.

Jetzt soll ein Photon X zum Ort B übermittelt werden. Am Ort A wird Photon 1 mit Photon X verschränkt, die Polarität des Photons X darf nicht gemessen werden. Es ist davon auszugehen, dass Photon X alle Informationen von Photon 1 enthält. Der Empfänger am Ort B kann aber nicht wissen wie er Photon X zu behandeln hat. Dies wird dem Empfänger durch den Ort A, ganz analog, mittels eines Briefes oder einer mail mitgeteilt.
Experimentell wurde das über eine Entfernung von 147km nachgewiesen. Würde am Ort A Photon X vermessen werden, würde die Messung allein eine Zustandsänderung des Photons bewirken.

[Mark]

Hi Klaus

Wenn man theoretisch unendliche CPU-Geschwindigkeit (und natürlich auch RAM usw..) hat, dann kann ein Programm natürlich auch aus jeder beliebigen Nachricht irgendwann mal eine Version transformieren, in der lesbare Wörter vorkommen, und ich meinte ja auch eigentlich damit die damit gegenüber dem Besitzer des Quantenrechners unbrauchbare Verschlüsselung in der herkömmlichen Architektur.
Bei Quantenrechnern die optisch kommunizieren kann man durch die Technik feststellen ob jemand die Photonen abgefangen hat, stimmt..aber dazu müssten direkte optische Verbindungen zwischen allen Rechnern erstellt werden, das ist ein technisches Unding..

@Dissidenkt
Das ist ja brandaktuell.. krasse Entdeckung, das würde die Frage beantworten
EDIT: oder auch nicht, der Kommentar macht Sinn..
http://www.heise.de/tp/blogs/foren/S-Wa ... 5392/read/

[Klaus]

Hi Mark,
ich kann mir in absehbarer Zukunft keine Quantencomputer-Netzwerk-Hierarchien vorstellen, wäre auch nicht notwendig. Das Hauptproblem was ich sehe, und damit kommen die Quantencomputer wieder auf ein normales Level, da alle möglichen Lösungen fast in Echtzeit dargestellt werden können, muss noch festgestellt werden welche von den Lösungen die zutreffende ist, also "wahr".

Die Probleme der Quantencomputer:

1. an Stelle der herkömmlichen Bits, die nur die Werte von 0 und 1 annehmen können, verwenden Quantencomputer Quantenbits. Ein solches Qubit kann durch ein Teilchen mit Spin repräsentiert werden, etwa ein Elektron, Spin aufwärts bedeutet 1, Spin abwärts bedeutet 0. Ausserdem gibt es die Superpositionen - Zustände, bei denen der Spin gleichzeitig nach unten und oben weist.

2.Superpositionszustände weniger Teilchen bergen damit eine enorme Informationsmenge. So können 1000 Teilchen eine Superposition bilden, die jede Zahl von 1 bis 2hoch 1000( rd. 10hoch300) repräsentieren. Ein Quantencomputer würde all diese Zahlen gleichzeitig be-und verarbeiten, z.B. durch Laserimpuls-Beschuss der Teilchen.

3.Misst man am Ende der Berechnung die Teilchenzustände verschwinden allerdings alle 10hoch300 parallelen Zustände bis auf einen einzigen, der zufällig übrig bleibt. Durch geschicktes Manipulieren der Teilchen lassen sich bestimmte Probleme - etwa das Faktorisieren einer großen Zahl - dennoch sehr schnell lösen.

P ungleich NP

Die im Beispiel von TP genannte Frage wurde bereits vor 50 Jahren gestellt. NP steht für die nichtdeterministische Polynomialzeit. NP ist die Klasse aller Probleme für eine bestimmte Lösung. Die Klasse P ist nicht in der Klasse NP enthalten.
Ein effizienter Algorithmus für ein NP-vollständiges Problem würde dem gegenwärtigen Bild der Klassen P, NP, und NP-vollständig radikal den Boden entziehen, denn dann wäre jedes NP-Problem - inklusive eine NP-vollständigen - in Wahrheit ein P-Problem. Mit anderen Worten, die Klasse P wäre gleich mit der Klasse NP, das hieße P=NP.
Will man nun NP-vollständige Probleme in Polynomialzeit lösen, muss man den Begriff des Computers erweitern. Man arbeitet dann mit Amplitudenüberlagerungen, sogenannter destruktiver Interferenz.
Bei allem bleibt zu sagen, bis jetzt wurde noch kein Quantenalgorithmus gefunden der NP-vollständige - Probleme verarbeitet, es gibt aber auch keinen Beweis dafür, dass er nicht existiert.
Der zweitwichtigste Quantenalgorithmus ist die sogenannte "Blackbox". Das zu berechnende Problem erhält dann den Status einer strukturlosen Blackbox. Ansonsten setzt man auf die "neue Physik" und beschäftigt sich mit "closed timelike curves" (CTCs)
Kurz gesagt ist eine CTC ein Weg durch Raum und Zeit, auf dem Materie oder Energie sich selbst in der Vergangenheit trifft und eine geschlossene Schleife bildet.David Deutsch hat 1991 ein Berechnungsmodell für CTCs formuliert, welches die Schwierigkeit de Großvater-Paradoxon geschickt umgeht.