An implementation of Shor's algorithm for elliptic curve cryptography
Benjamin Luxbacher
Elliptische-Kurven-Kryptografie, so wie es vom Signal Protokoll (Whatsapp), Bitcoin und Ethereum verwendet wird, basiert auf der angenommenen Schwierigkeit des Diskreten Logarithmus-Problems (DLP). Um das DLP mittels bekannter Algorithmen auf klassischen Computern zu lösen, wird zwar exponentielle Zeit benötigt, mit Quantencomputer kann es allerdings in polynomieller Zeit gelöst werden. Dies ist möglich mit Shors Algorithmus, welcher im Wesentlichen aus der Quantum Phase Estimation und Quantum Fourier Transformationen besteht. Zusammen mit Quantengattern für gewöhnliche Arithmetik, Montgomery modularer Arithmetik und Punktaddition kann der Algorithmus verwendet werden, um aus öffentlichen Schlüsseln den dazugehörigen privaten Schlüssel in polynomieller Zeit zu errechnen. Der Algorithmus wurde im Zuge der Arbeit in Python implementiert und bereits für kleine Schlüssel simuliert. Derzeit besitzen Quantencomputer nicht die benötigten Ressourcen, um Shors Algorithmus für bedeutsame Schlüsselgrößen auszuführen. In der Zukunft wird es aber Quantencomputer mit genügend vielen Qubits und der benötigten Dekohärenzzeit geben, um Elliptische-Kurven-Kryptografie unsicher zu machen. Die genaue Implementierung des Algorithmus und die Zusammensetzung der verschiedenen Gatter sind immer noch Teil von aktueller Forschung. Dadurch ist es denkbar, dass noch effizientere Quantenschaltkreise für die Quantengatter gefunden werden. Dies hat zur Folge, dass Elliptische-Kurven-Kryptografie noch früher keine ausreichende Sicherheit mehr bieten kann.
•May 1, 2026•0 citations