Große Primzahl als verschlüsselung?
Mal angenommen ich habe einen Quantencomputer der mir eine sehr große Primzahl berechnet die mit normalen Computern nicht auffindbar oder berechenbar ist. Könnte man dann nicht mit dieser Zahl ein PC System als "Unhackbar" (oder auch verschlüsselung) machen da niemand diese verschlüsselung knacken könnte?
8 Antworten
Du brauchst keinen Quantencomputer, um eine sehr große Primzahl zu berechnen. Der aktuelle empfohlene RSA-Standard mit 2048 Bit Schlüssel benutzt z.B. zwei Primzahlen, die beide etwa 1024 Bit lang sind. Als Dezimalzahl wäre das eine Zahl mit 309 Ziffern. Die Erzeugung kriegt ein normaler Computer in einem Bruchteil einer Sekunde hin. Die Multiplikation der beiden Primzahlen geht sogar noch schneller.
Wofür ein Quantencomputer gut wäre, ist der umgedrehte Weg. Also das Produkt aus zwei großen Primzahlen wieder in die beiden Primzahlen zu zerlegen.
So als Rechenbeispiel: Gehen wir mal davon aus, ein normaler Computer kann pro Sekunde eine Milliarde mal den Schlüssel dividieren, um zu prüfen, welche Primzahlen sich darin verstecken. Und gehen wird mal davon aus, auf der Erde würden sich eine Milliarde Computer mit der gleichen Leistung gleichzeitig daran beteiligen, den Schlüssel zu knacken, dann hätten wir eine weltweite Gesamtleistung von einer Trillion Berechnungen pro Sekunde.
Das sind also 10^18 Zahlen, die pro Sekunde probiert werden können. Der Schlüssel hat aber 10^309 Möglichkeiten. Es dauert also mit der gesamten Rechenleistung von normalen Computern, die auf der Erde zur Verfügung steht, etwa 10^291 Sekunden. Das sind 3*10^283 Jahre. Das ist 2,3 * 10^273 mal so viel Zeit, wie seit der Entstehung des Universums vergangen sind. Die Schlüssel sind also jetzt schon nicht mit normalen Computern zu knacken.
Bei einem Quantencomputer ist es anscheinend so, dass die Qubits sich irgendwie automatisch so ausrichten, dass das richtige Ergebnis rauskommt. Die Details dazu habe ich leider selbst nicht verstanden, aber es soll damit jedenfalls wesentlich schneller gehen, solche Schlüssel zu knacken.
Eine Primzahl ist nur die Basis der Verschlüsselung aber noch nicht die Verschlüsselung selbst.
Je nach Algorithmus wird sie anders genutzt. Generell geht es aber darum aus der Primzahl ein Mathematisches Problem zu erstellen welches auf modernen Computern nicht effizient lösbar ist. Dazu zählen zB Primfaktorzerlegung und der diskrete Logarithmus.
Sie werden in diesem Sinne als Einwegfunktionen bezeichnet weil es bei großen Zahlen zwar möglich ist zwei große Primzahlen zu multiplizieren aber die Zerlegung in eben diese Primfaktoren nicht in realistischer Zeit erfolgen kann.
Das Problem dahinter ist jetzt aber, dass auf Quantencomputern alle diese Sachen relativ effizient lösbar sind und daher diese Dinge eben keine Einwegfunktionen mehr sind womit auch die Verschlüsselung an ihre Grenzen stößt. Insbesondere Asymmetrische Verfahren wie zB RSA sind davon betroffen weil man aus dem Verbindungsaufbau mit Quantencomputern in realistischer Zeit den Schlüssel berechnen kann. (Shor Algorithmus)
Es ist dabei Prinzipiell egal wie groß du deine Primzahlen wählst, sofern du sie in realistischer Zeit berechnen kannst, kann auch ein anderer Quantencomputer das Problem in realistischer Zeit lösen, weil hier im Gegensatz zum normalen Computer der Rechenaufwand nicht wirklich exponentiell steigt.
Du wirst ziemlich sicher niemals der einzige mit einem Quantencomputer sein. Außerdem ist alles ja nur von der Zeit abhängig. Auch ein normaler Computer kann diese Primzahl errechnen. Dauert dann halt z.B. 2000 Jahre. Aber allgemein fangen Programme zum entschlüsseln nicht als erstes damit an Primzahlen zu errechnen und dann einzufügen. Die werden gar nicht wissen ob es sich um eine Primzahl, welche sie einfügen, handelt oder nicht. Sie arbeiten einfach an einem Algorhytmus entlang.
Das stimmt so nicht, es gibt bereits mehrere Unternehmen die welche besitzen.
Du kannst keine Primzahl finden, die nicht von herkömmlichen Computern gefunden werden kann. "Unknackbar" wäre dann nur eine Frage der Zeit.
Soweit ich weiß, ist die Verschlüsselungsmethode One-Time-Pad die einzig absolut (mathematisch bewiesen) sichere Methode. Dabei verschlüsselst du jedes Zeichen deiner Nachricht mit jeweils einer perfekt zufälligen Zahl... Der Schlüssel ist genau so lang, wie die Nachricht und darf nie doppelt benutzt werden. Ist halt etwas unpraktisch.
Fine Zahl ist noch keine Verschlüsselung.
Es wird bereits erforscht wie man Verschlüsselungen angehen könnte im Zeitalter der Quantencomputer.