Wie bricht Prime Factorization ECDSA?

Question

Ich habe gehört, dass ECDSA in nicht allzu ferner Zukunft (ungefähr 15 bis 25 Jahre) von Quantencomputern, die Shors Algorithmus ausführen, gebrochen wird. Nach meinem Verständnis besteht der einzige Zweck von Shors Algorithmus darin, schnell die Primfaktoren sehr großer Zahlen zu finden. Obwohl zeitaufwändig, ist eine solche Faktorisierung auf modernen Computern keineswegs unmöglich. Die Hauptfaktoren öffentlicher Schlüssel auf der Secp256k1-Kurve können mit dem richtigen Algorithmus in wenigen Stunden ermittelt werden. Gibt es eine Formel, mit der ein privater ECDSA-Schlüssel von einem öffentlichen abgeleitet werden kann, wenn die Hauptfaktoren dieses öffentlichen Schlüssels aufgedeckt werden, oder gibt es einen anderen Aspekt der Faktorisierung, der ein so großes Sicherheitsrisiko darstellt? Ich konnte keine Informationen darüber finden, mit welchen Mitteln diese Quantenangriffe die Verschlüsselung mit öffentlichen Schlüsseln trotz der großen Besorgnis darüber aufheben könnten. Jede Erklärung, insbesondere mit mathematischen Beispielen, wäre sehr dankbar.

Answer 1

Nach meinem Verständnis besteht der einzige Zweck von Shors Algorithmus darin, schnell die Primfaktoren sehr großer Zahlen zu finden.

Ihr Verständnis ist falsch. Shors Algorithmus kann sowohl zum Faktorisieren von ganzen Zahlen als auch zum Finden diskreter Logarithmen verwendet werden.

Shors Algorithmus besteht aus zwei Teilen. Erstens verwandelt es das Problem (Factoring oder diskretes Protokoll) in das Finden der Periode einer Funktion. Dieser erste Schritt ist nicht quantenmäßig. Dann findet es die Periode unter Verwendung der Quanten-Fourier-Transformation (QFT). Sobald Sie die Periode der Funktion haben, kann der erste Schritt umgekehrt werden, um die Lösung für das ursprüngliche Problem zu finden.

Shors Algorithmus kann ohne den Quantum-Teil verwendet werden und die QFT simulieren, obwohl er dann wesentlich langsamer ist als die bekanntesten klassischen Algorithmen. Diese Python-Implementierung simuliert die QFT und kann das Verständnis verbessern.