Shor-Algorithmus für ECDLP — Q-Day-Preis-Einreichung

Quantenlöser für das Problem des diskreten Logarithmus auf elliptischen Kurven (ECDLP), entwickelt für den Q-Day Prize Challenge von Project Eleven. Ziel: Wiederherstellung von ECC-privaten Schlüsseln auf echter Quantenhardware unter Verwendung des Shor-Algorithmus.

• Autor: Giancarlo Lelli
• Kontakt: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Hintergrund: Technologieführer mit über 10 Jahren Erfahrung in Unternehmenssoftware, Full-Stack-Architektur und Cloud-nativer Entwicklung. Hintergrund in Informatik mit praktischer Erfahrung in den Ökosystemen .NET, Python, Rust und Cloud. Derzeit als Cloud-GTM-Spezialist tätig, mit Fokus auf Lösungsarchitektur und Vertriebstechnik.

Ansatz

Alle Herausforderungskurven verwenden y^2 = x^3 + 7 über F_p (a = 0, b = 7), entsprechend der secp256k1-Familie. Der Löser implementiert die Zwei-Register-Variante des Shor-Algorithmus für ECDLP:

1. Bereite die Zählregister |j>, |k> in gleichmäßiger Superposition vor (Hadamard)
2. Berechne |j>|k>|jG + kQ> über 2t kontrollierte Punktadditionen (t = num_counting Qubits)
3. Messe das Punktregister, kollabiere es auf ein Gruppenelement R
4. Wende die inverse QFT auf die Zählregister an
5. Messe j, k und extrahiere d aus der Beziehung j + kd = r (mod n)

Der private Schlüssel d wird durch das Sammeln mehrerer (j, k)-Stichproben wiederhergestellt, die dieselbe lineare Beziehung modulo der Gruppenordnung n erfüllen. Der Löser unterstützt sechs Oracle-Strategien für die kontrollierten Punktadditionen, die automatisch basierend auf der Kurvengröße oder manuell über --oracle ausgewählt werden.

Oracle-Strategien

Strategie 1: Dichte unitäre Matrix (Standard für n_bits <= 6)

Verwendet für Kurven mit einer Gruppenordnung bis zu etwa 6 Bits. Implementiert in projecteleven.py.

Jede kontrollierte Punktaddition "add S" wird als eine 2^(n+1) x 2^(n+1) Permutationsmatrix dargestellt, die über qc.unitary() angewendet wird. Die Matrix kodiert die vollständige Gruppenaktion: Der obere linke Block ist die Identität (Kontrolle=0), der untere rechte Block permutiert Basiszustände gemäß der Abbildung P -> P+S (Kontrolle=1).

• Kodierung: Gruppenindex (0..n-1)
• Speicher: O(2^{2n}) pro Matrix
• Qubits: 2t + n (zwei Zählregister + Punktregister)
• Einschränkung: Qiskits unitäre Zerlegung ist O(4^n), was dies jenseits von ~6 Bits undurchführbar macht

Strategie 2: Effiziente Permutationszerlegung (Standard für n_bits > 6)

Verwendet für größere Kurven. Implementiert in quantum_arithmetic.py.

Anstatt dichte Matrizen zu bauen, wird jede "add S"-Permutation zykluszerlegt in Transpositionen. Jede Transposition (Tausch zweier Basiszustände |a> <-> |b>) wird implementiert mit:

1. CNOT-Reduktion – CNOTs von einem Pivot-Bit auf alle anderen abweichenden Bits, wodurch die Mehr-Bit-Differenz auf eine Ein-Bit-Differenz reduziert wird
2. Mehrfach kontrolliertes X – Ein MCX-Gatter auf dem Pivot-Bit, konditioniert darauf, dass alle anderen Bits dem Zielmuster entsprechen
3. Rückgängigmachen der CNOTs – Schritt 1 umkehren, um die Nicht-Pivot-Bits wiederherzustellen

Das MCX verwendet eine V-Ketten-Zerlegung mit (n-2) dedizierten Ancilla-Qubits, was O(n) Toffoli-Gatter pro MCX ergibt, statt O(n^2) ohne Ancillas. Jede kontrollierte Addition wird als isolierter Unter-Schaltkreis gebaut und als ein einzelnes undurchsichtiges Gatter angehängt, wodurch quadratisches DAG-Wachstum in Qiskit vermieden wird.

• Kodierung: Gruppenindex (0..n-1)
• Speicher: O(N) pro Addition (N = Gruppenordnung)
• Qubits: 2t + n + (n-2) Ancillas
• Gatter pro Addition: O(N * n)

Strategie 3: Koordinatenbasiertes Quanten-Oracle (--oracle coordinate)

Verfügbar für Kurven bis ~6 Bits. Implementiert in quantum_oracle.py.

Anstatt Punkte als Gruppenindizes zu kodieren, enthält das Quantenregister tatsächliche (x, y)-Feldelementkoordinaten in Binärform plus ein Identitäts-Flag. Das Punktregister-Layout ist:

• x_reg: f_bits Qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits Qubits
• id_flag: 1 Qubit (1 = Punkt im Unendlichen)

Jede kontrollierte "add S" wird aus der EC-Additionsformel über alle gültigen Koordinatenkodierungen berechnet, was eine Permutation auf dem Koordinatenregister erzeugt. Diese Permutation wird mit derselben CNOT-Reduktions- + MCX-Infrastruktur wie Strategie 2 in Transpositionen zykluszerlegt.

• Kodierung: (x, y, id_flag)-Koordinaten
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) Ancillas
• Gatter pro Addition: O(N * f_bits)

Strategie 4: Arithmetisches Oracle (--oracle arithmetic)

Framework für polynomial skalierende Punktaddition. Implementiert in quantum_oracle.py und quantum_arithmetic.py.

Verwendet Koordinatenkodierung (wie Strategie 3) mit QFT-basierten modularen arithmetischen Primitiven als Bausteine auf dem Weg zur vollständig arithmetischen Punktaddition. Die Codebasis enthält getestete Implementierungen von:

• Beauregard modularem Addierer – QFT-basiert (target + constant) mod p mit korrekter Ancilla-Entberechnung
• Quanten-Quanten modularer Multiplikation – |a>|b>|0> -> |a>|b>|a*b mod p> via Shift-and-Add mit expliziter modularer Verdopplung, O(n^3) Gatter
• Modularer Inversen-Permutation – |x> -> |x^{-1} mod p> via Lookup-Tabellen-Transpositionen
• Kontrollierter Quanten-Quanten modularer Addition – Kontrolliert |a> -> |a + b mod p> mit Beauregard-Reduktion

Die arithmetischen Primitive erreichen eine Skalierung von O(n^3) pro Punktaddition gegenüber O(N*n) für den Permutationsansatz. Allerdings haben die QFT-basierten Operationen einen etwa 150x größeren konstanten Faktor, was den arithmetischen Ansatz erst für Kurven oberhalb einer Gruppenordnung von ~20 Bits effizienter macht. Für die aktuellen Herausforderungsgrößen (bis zu 12 Bits) bleibt der permutationsbasierte Addierer schneller und wird standardmäßig verwendet.

Strategie 5: Google Semiclassical Phase Estimation (--oracle google)

Implementiert in google_semiclassical.py. Inspiriert von der Qubit-recycelten Phasenschätzungstechnik von Griffiths & Niu (1996), angewendet im Maßstab in Babbush et al. (2026) für secp256k1-ECDLP-Ressourcenschätzungen. Das Papier von Babbush et al. wurde am 30. März 2026 veröffentlicht.

Ersetzt die zwei Multi-Qubit-Zählregister (j, k) und die bulk inverse QFT durch zwei einzelne recycelte Qubits und klassisch konditionierte Phasenkorrekturen. Jedes Bit des Zählregisters wird sequentiell verarbeitet: Vorbereitung in |+>, Anwendung der kontrollierten Punktaddition, Phasenkorrektur basierend auf allen zuvor gemessenen Bits, dann Messung. Die dynamischen Schaltkreis-Primitive reset + if_test in Qiskit ermöglichen dies auf IBM-Quantenhardware.

Das Oracle für kontrollierte Punktadditionen wird an die vorhandene Infrastruktur delegiert (dichte unitäre für <= 6 Bits, effiziente Permutation für > 6 Bits), sodass die Qubit-Einsparungen ausschließlich aus der Eliminierung der Zählregister stammen.

• Kodierung: Wie zugrundeliegende Strategie (Gruppenindex)
• Qubits: 2 + n_bits + Ancillas (vs. 2t + n_bits + Ancillas)
• Kompromiss: Erfordert dynamische Schaltkreise (Mid-Circuit-Messung, Reset, klassisch konditionierte Gatter). Funktioniert auf IBM Heron r2 bis zu 7 Bits; bei 8 Bits+ überschreitet der klassische Feedback-Synchronisations-Overhead das QPU-Zeitbudget

Strategie 6: Ripple-Carry modulare Addition (--oracle ripple)

Implementiert in ripple_carry_shor.py. Verwendet CDKM-Ripple-Carry-Addierer (Cuccaro et al. 2004) für die kontrollierten Punktadditionen, wodurch sowohl dichte unitäre Matrizen als auch zykluszerlegte Transpositionsschaltungen ersetzt werden.

In der Gruppenindex-Kodierung wird Punkt P = kG durch seinen Index k in der zyklischen Gruppe dargestellt. Das Addieren von S = sG wird zur modularen Addition des klassischen konstanten s (mod n). Die entscheidende Einsicht: Jede kontrollierte Punktaddition reduziert sich auf eine einzige kontrollierte modulare Addition einer bekannten Konstanten, implementiert über Qiskits CDKMRippleCarryAdder und IntegerComparator.

Das Oracle besteht aus 2m kontrollierten modularen Additionen (m pro Zählregister), wobei jede kontrollierte Mod-Add wie folgt ausgeführt wird:

1. Konstante laden in Ancilla-Register über CX vom Kontroll-Qubit
2. CDKM-Halbaddierer zur Addition der Ancilla in den Akkumulator (nur Nächstnachbar-Gatter)
3. Integer-Komparator zur Erkennung eines Überlaufs (acc >= n)
4. Bedingte Subtraktion von n über flag-gesteuerte Addition von 2^m1 - n
5. Flag-Entberechnung über carry-basierte Sondierung

Kein Wissen über den privaten Schlüssel d wird beim Schaltungsaufbau verwendet. Gruppenindizes für G-Potenzen werden als 2^i mod n (öffentlich) berechnet. Gruppenindizes für Q-Potenzen werden aus der öffentlichen Aufzählung der von G erzeugten zyklischen Gruppe abgeleitet – der Punkt Q wird in dieser Aufzählung nachgeschlagen.

• Kodierung: Gruppenindex (0..n-1)
• Qubits: 4m + 5, wobei m = ceil(log2(n))
• Gatter pro Addition: O(m) CDKM-Operationen, jede O(m) CX-Gatter
• Gesamt-CX-Skalierung: O(m^3)
• Hardware-Mapping: CDKM verwendet nur Nächstnachbar-Gatter, was etwa 1x Routing-Overhead auf IBM-Heavy-Hex-Topologie ergibt (vs. 26-33x für QFT-basierte Addierer)

Vergleich

QFT-Arithmetik-Primitive

Die Codebasis enthält QFT-basierte modulare arithmetische Bausteine (Beauregard/Draper-Addierer, Quanten-Quanten modulare Multiplikation, modulare Inverse/Negation) als Grundlage für eine vollständig arithmetische Koordinatenkodierung bei 256 Bit. Diese Primitive wurden mittels Statevector-Simulation für Primzahlen bis p=13 auf Korrektheit verifiziert.

Ergebnisse

Erfolgreiche Wiederherstellung privater Schlüssel auf IBM-Quantenhardware für Herausforderungskurven bis zu 17 Bit:

Alle Läufe wurden auf dem IBM-Quantum-Open-Instance-Plan ausgeführt, der 10 Minuten kostenlose Quantenberechnung pro Monat gewährt. Vollständige Ausführungsprotokolle befinden sich im Ordner executions/.

Die Ripple-Carry-Strategie (Strategie 6) ermöglichte einen großen Sprung: von 10 Bit (40 Qubits, 2M Gatter) auf 17 Bit (69 Qubits, 112K Gatter) – eine 7-Bit-Schlüsselerhöhung mit einer 18-fachen Reduktion der Zwei-Qubit-Gatteranzahl. Die Nächstnachbar-Gatterstruktur des CDKM-Addierers lässt sich effizient auf IBMs Heavy-Hex-Topologie abbilden, wodurch der Routing-Overhead nahe 1x bleibt.

Semiclassical PE: Dynamische Schaltungen auf IBM-Hardware

Die semiklassische Strategie (--oracle google) hat erfolgreich Schlüssel bei 4 Bit, 6 Bit und 7 Bit unter Verwendung dynamischer Schaltungen (Mid-Circuit reset, klassisch konditionierte p-Gatter via if_test) auf IBM-Heron-r2-Prozessoren wiederhergestellt. Bei 7 Bit verwendet die Schaltung nur 14 Qubits (vs. 26 beim Standard-Permutationsansatz), während nach der Transpilation vergleichbare 2Q-Gatterzahlen erzielt werden.

Ab 8 Bit wird der semiklassische Ansatz auf aktueller IBM-Hardware unpraktikabel. Obwohl if_else und reset auf Heron r2 unterstützt werden (bestätigt durch Inspektion des Backend-Targets), erfordert jeder klassische Feedback-Punkt eine vollständige QPU-Synchronisation – alle 156 physikalischen Qubits müssen im Leerlauf sein, während der klassische Controller die Konditional für die ~16 aktiven Qubits verarbeitet. Bei ~295K CZ-Gattern, verteilt auf 16+ Feedback-Punkte, überschreitet der Ausführungs-Overhead pro Shot das QPU-Zeitbudget. Der Standard-Permutationsansatz, der die gleiche Gatteranzahl als einen einzigen kontinuierlichen Batch ohne dynamische Schaltungen ausführt, wird in diesem Maßstab erfolgreich abgeschlossen.

Eine approximative QFT-Trunkierung (max_corrections-Parameter) reduziert die Anzahl der if_else-Blöcke von O(n^2) auf O(n), indem nur die nächsten k Phasenkorrekturen pro Messschritt beibehalten werden (Winkel jenseits k tragen < pi/2^{k+1} bei, unterhalb des Hardware-Rauschbodens). Mit max_corrections=1 hat die 8-Bit-Schaltung 16 if_else-Blöcke – immer noch ausreichend, um bei dieser Gatteranzahl auf IBM-Hardware einen Timeout zu verursachen.

Rauschen und Fidelity-Analyse

Geschätzte Schaltungsfidelity

Unter Annahme einer typischen IBM-Quantum-Zwei-Qubit (CX)-Gatterfidelity von ~99,5% fällt die geschätzte Schaltungsfidelity exponentiell mit der Gatteranzahl:

Die Schaltungsfidelity wird berechnet als F ≈ (0.995)^{CX_count}. Für alles jenseits von 4 Bit ist die geschätzte Fidelity astronomisch klein – die Ausgabeverteilung ist überwältigend durch Rauschen bestimmt.

Warum es trotzdem funktioniert

Ab 8 Bit erzeugt jeder Shot fast einen eindeutigen Bitstring (8.128 einzigartige Ergebnisse von 8.192 Shots bei 8 Bit; alle 20.000 einzigartig bei 16 Bit und 17 Bit). Die Ausgabe ist auf Bitstring-Ebene nicht von einer gleichmäßigen Zufallsstichprobe zu unterscheiden. Dennoch gewinnt der Algorithmus den korrekten privaten Schlüssel zurück.

Die entscheidende Einsicht ist, dass die Shor-Nachverarbeitung auf eine Weise robust gegenüber Rauschen ist, wie es die reine Bitstring-Analyse nicht ist. Jeder Shot erzeugt ein (j, k, r)-Messungstripel. Die Extraktion berechnet d_cand = (r - j) · k^{-1} mod n und verifiziert über d_cand · G == Q. Nur der wahre d besteht die EC-Verifikation, sodass selbst ein einziger korrekter Kandidat unter Tausenden von Rauschshots ausreicht.

Ein rein zufälliges (j, k, r)-Tripel erzeugt mit Wahrscheinlichkeit ~1/n den korrekten d_cand. Bei S Shots beträgt die erwartete Anzahl verifizierter Treffer allein aus Rauschen ~S/n. Bei 17 Bit (n=65.173, S=20.000) ergibt dies etwa 0,3 erwartete Rauschterffer – jede erfolgreiche Wiederherstellung in diesem Maßstab liefert einen Hinweis auf ein Quantensignal oberhalb des klassischen Rauschbodens.

Für die kleineren Kurven, bei denen shots >> n (z. B. 10 Bit mit n=547 und 1.024 Shots), liegt der Rauschboden bei ~1.024/547 ≈ 1,9 Stimmen pro Kandidat. Selbst eine Handvoll signaltragender Shots hebt das korrekte d über den Rauschboden. Dies erklärt, wie der Algorithmus trotz Schaltungsfidelities erfolgreich ist, die die Berechnung unmöglich erscheinen lassen würden.

Quantensignal vs. klassisches Rauschen

Im Spielzeugmaßstab fungiert der Verifikationsschritt der Extraktion (d_cand * G == Q) als Filter, der nur den wahren d akzeptiert. Dies bedeutet, dass selbst rein zufällige (j, k, r)-Tripel gültige Kandidaten mit einer Rate von etwa shots / n pro Lauf erzeugen. Wenn shots >> n, kann allein zufälliges Rauschen d mit hoher Wahrscheinlichkeit wiederherstellen.

Um zu testen, ob der Quantenschaltkreis über diesen klassischen Rauschboden hinaus beiträgt, haben wir die 6-Bit-Herausforderung (n=31) mit nur 8 Shots (deutlich unter der Gruppenordnung) 10 Mal auf ibm_kingston ausgeführt:

Ergebnis: 4/10 Erfolge (40 %) gegenüber einer klassischen Rauschbasislinie von ~20 % (berechnet mittels Monte-Carlo-Simulation: 8 zufällige Bitstrings mit (r-j)*k_inv mod 31 gefiltert durch Verifikation). Einseitiger Binomialtest: P(X >= 4 | n=10, p=0,20) = 0,121, was auf eine 2-fache Verbesserung gegenüber dem Rauschboden hindeutet. Obwohl dies bei p < 0,05 (was 5+ Erfolge erfordern würde) nicht einzeln statistisch signifikant ist, ist die beobachtete Rate konsistent mit einem Quantensignal, das etwa 1-2 zusätzliche gültige (j, k)-Paare pro Lauf über das hinaus liefert, was der Zufall bietet.

Dieses Ergebnis liegt zwischen dem klassischen Rauschboden und dem theoretischen Quantenvorteilsbereich. Bei größeren Kurvengrößen, bei denen n >> shots, sinkt die Rauschbasislinie unter 1 %, und jede erfolgreiche Schlüsselwiederherstellung wird zu einem starken Hinweis auf Quantenberechnung.

Schnellstart```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### So führen Sie es aus

Sie benötigen ein [IBM Quantum](https://quantum.ibm.com/)-Konto. Geben Sie Ihren API token beim ersten Durchlauf ein, und er wird lokal gespeichert:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

CLI-Optionen

Projektstruktur```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## Referenzen

- P. Shor, ["Algorithmen für Quantenberechnung: Diskrete Logarithmen und Faktorisierung"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Schaltung für Shors Algorithmus mit 2n+3 Qubits"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["Eine neue Quanten-Ripple-Carry-Additionsschaltung"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Quantenressourcenabschätzungen zur Berechnung diskreter elliptischer Kurven-Logarithmen"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Semiclassische Fouriertransformation für die Quantenberechnung"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Sicherung von Elliptische-Kurven-Kryptowährungen gegen Quantenbedrohungen: Ressourcenabschätzungen und Abhilfemaßnahmen"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Lizenz

Dieses Projekt ist ein Beitrag zur Q-Day Prize Challenge und wird unter der [MIT LICENSE](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE) veröffentlicht.