Cryptology Academy · Lezione

Moltiplicazione scalare ed ECDLP

Comprenda la somma ripetuta di punti e perché invertirla è difficile.

Lezione 2 di 413 passaggi

Moltiplicazione scalare ed ECDLP è una lezione Cryptology Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Cryptology Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Cryptology Academy include 4 lezioni in totale.

Introduzione

La moltiplicazione scalare è l'operazione EC fondamentale: calcolare k×P applicando ripetutamente la legge di gruppo. L'ECDLP, cioè trovare k dato k×P, è il problema difficile alla base della sicurezza della crittografia su curve ellittiche.

Definizione della moltiplicazione scalare

k×P = P + P + ... + P (k volte). Per k=4: 4P = P+P = 2P; 2P+2P = 4P. Per k=2^256, l'iterazione diretta è impraticabile. È necessario un algoritmo efficiente.

Algoritmo double-and-add

È analogo a square-and-multiply: Per ogni bit di k, dal MSB all'LSB: R = 2R (raddoppiamento) se il bit è 1: R = R + P (somma) O(log k) operazioni di gruppo ≈ O(256) per P-256.

Esempio: 13×P

13 = 1101 in binario Inizio: R = P 1: R = 2P+P = 3P (per il bit 1) 0: R = 6P 1: R = 12P+P = 13P ✓ 4 raddoppiamenti + 2 somme per k=13.

Problema del logaritmo discreto su curve ellittiche (ECDLP)

Dati i punti G e Q = k×G su una curva, trovare k. In avanti: semplice (O(log k) operazioni) In senso inverso: non è noto alcun algoritmo polinomiale per le curve crittografiche Miglior algoritmo generico: rho di Pollard in O(√n) ≈ 2^128 per P-256.

Perché l'ECDLP è più difficile del DLP

DLP classico (g^k mod p): gli algoritmi di calcolo dell'indice funzionano in tempo subesponenziale. ECDLP: per le curve ellittiche generiche non è noto alcun equivalente del calcolo dell'indice. A parità di lunghezza della chiave, il problema è molto più difficile.

Attacco di Pohlig-Hellman

Se l'ordine del gruppo ha piccoli fattori primi, l'ECDLP può essere risolto efficientemente in ciascun sottogruppo. Difese: usare curve con ordine del gruppo primo o quasi primo; evitare curve con sottogruppi piccoli.

Attacco MOV

L'attacco MOV trasferisce l'ECDLP al DLP in un campo finito tramite l'accoppiamento di Weil. Funziona solo per curve supersingolari (grado di immersione k=1,2). Tutte le curve NIST sono resistenti a MOV.

Moltiplicazione scalare a tempo costante

Il double-and-add ingenuo rivela k tramite i tempi di esecuzione (il passaggio di somma condizionale). Utilizzi il Montgomery ladder o algoritmi comb che eseguono le stesse operazioni indipendentemente dai bit della chiave. È essenziale per implementazioni sicure.

Livelli di sicurezza dell'ECDLP

P-192: sicurezza a 96 bit (deprecato da NIST) P-224: sicurezza a 112 bit P-256: sicurezza a 128 bit (standard attuale) P-384: sicurezza a 192 bit P-521: sicurezza a 260 bit Curve25519: sicurezza a 128 bit

Dall'ECDLP alla sicurezza di ECDH

La sicurezza di ECDH si riduce a quella dell'ECDLP: se è possibile risolvere l'ECDLP (trovare a dato A=a×G), è possibile calcolare il segreto condiviso. L'assunzione computazionale di Diffie-Hellman (CDH) presuppone che questo problema sia difficile.

Verifica rapida

Qual è la complessità temporale del miglior algoritmo generico (rho di Pollard) per l'ECDLP con ordine del gruppo n?

Rispondi nella lezione interattiva

Riepilogo

La moltiplicazione scalare e l'ECDLP sono ora chiari. Nel prossimo argomento confronteremo le curve standard: P-256, Curve25519 e secp256k1.

Gratis per iniziare

Impara Cryptology Academy con un tutor IA — gratis

Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.

Corsi: 67
Lezioni: 261

Inizia a imparare gratis Visualizza il corso completo

Domande Frequenti

La lezione «Moltiplicazione scalare ed ECDLP» è gratuita?

Sì — il testo completo di «Moltiplicazione scalare ed ECDLP» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Cryptology Academy, passa a CoddyKit PRO. Il corso Cryptology Academy include 4 lezioni in totale.

Cosa imparerò in «Moltiplicazione scalare ed ECDLP»?

Comprenda la somma ripetuta di punti e perché invertirla è difficile. Eserciti Cryptology Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Cryptology Academy?

Non è richiesta alcuna esperienza precedente. Cryptology Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Moltiplicazione scalare ed ECDLP»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Cryptology Academy?

Sì. Ogni lezione Cryptology Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

Legge di gruppo delle curve ellittiche
Moltiplicazione scalare ed ECDLP
Curve standard: P-256, Curve25519, secp256k1
ECC e RSA: compromessi tra sicurezza e prestazioni

← Torna a Cryptology Academy