Shor
Algoritmo di Shor (o Algoritmo di fattorizzazione di Shor)

L’algoritmo di Shor è un algoritmo quantistico sviluppato dal matematico americano Peter Shor nel 1994. È considerato uno degli algoritmi quantistici più importanti e pericolosi per la crittografia moderna.

Cosa fa?

L’algoritmo di Shor è in grado di fattorizzare numeri interi molto grandi in modo estremamente efficiente su un computer quantistico, e di risolvere il problema del logaritmo discreto.

Queste due capacità permettono di:

• Rompere RSA (la crittografia a chiave pubblica più usata al mondo)
• Rompere ECC (Elliptic Curve Cryptography), inclusa la curva secp256k1 utilizzata da Bitcoin per generare chiavi private e firme digitali (ECDSA)

Perché è rilevante per Bitcoin?

Bitcoin basa gran parte della sua sicurezza sulla difficoltà di derivare una chiave privata da una chiave pubblica usando algoritmi classici.
L’algoritmo di Shor, eseguito su un CRQC (computer quantistico crittograficamente rilevante), potrebbe:

• Calcolare la chiave privata partendo dalla chiave pubblica in tempi ragionevoli
• Firmare transazioni fraudulentamente
• Rubare bitcoin da indirizzi in cui la public key è stata esposta (ad esempio indirizzi legacy o transazioni già spese)

Caratteristiche tecniche principali:

• È un algoritmo quantistico (non funziona su computer classici)
• Ha una complessità polinomiale (molto più veloce della migliore soluzione classica, che è esponenziale)
• Richiede un computer quantistico con migliaia di qubit logici stabili e corretti dagli errori per essere eseguito su chiavi di dimensione reale (es. 256 bit o 2048 bit)

Contesto nel glossario Bitcoin:

L’algoritmo di Shor è la principale minaccia quantistica contro Bitcoin.
Il giorno in cui un computer quantistico sarà in grado di eseguire efficacemente l’algoritmo di Shor su chiavi crittografiche reali viene chiamato Q-Day.