ECC_Attacks

# Attacchi Noti sulla Crittografia a Curve Ellittiche
- [Introduzione](#Introduction)
- [Introduzione alle Curve Ellittiche](#Introduction-To-Elliptic-Curves)
- [Curve Ellittiche nel Contesto della Crittografia](#Elliptic-curves-in-the-context-of-cryptography)
- [Attacchi ECC](#ECC-Attacks)

### Attacchi ECDH
- [L'ordine del generatore è troppo piccolo](#The-order-of-the-generator-is-too-small)
- [L'ordine del generatore è un numero liscio](#The-order-of-the-generator-is-a-smooth-number)
- [L'ordine del generatore è quasi un numero liscio e la chiave privata è piccola](#The-order-of-the-generator-is-almost-a-smooth-number-and-the-private-key-is-small)
- [Non verificare che un punto sia sulla curva](#Not-verifying-that-a-point-is-on-the-curve)
- [La curva è singolare](#The-curve-is-singular)
- [La curva è supersingolare](#The-curve-is-supersingular)
- [La curva è anomala](#The-curve-is-anomalous)

### Attacchi ECDSA
- [Non applicare l'hash al messaggio prima di firmarlo](#Not-hashing-the-message-before-signing-it)
- [Riutilizzare lo stesso valore di k in firme diverse](#Reusing-the-same-value-of-k-in-different-signatures)
- [Generare valori di k in modo non sicuro](#Generating-k-values-insecurely)
- [Non verificare che il generatore sia valido](#Not-verifying-the-generator-is-valid)

### Conclusione
- [Panoramica degli attacchi ECDH](#ECDH-attacks-overview)
- [Panoramica degli attacchi ECDSA](#ECDSA-attacks-overview)
- [Protezione contro questi attacchi](#Protection-against-these-attacks)
- [Riferimenti](#References)

# Introduzione
Negli ultimi anni l'approccio della crittografia a curve ellittiche è diventato popolare grazie alla sua alta efficienza e alla sua forte sicurezza. Lo scopo di questo articolo è presentare questo argomento in un modo relativamente più chiaro rispetto a quanto esiste oggi su internet.

In questo articolo presenterò cosa sono le curve ellittiche, le operazioni di base che si possono eseguire su di esse e come possono essere usate in un contesto crittografico. La maggior parte di questo articolo consiste in esempi di attacchi noti su implementazioni errate o su usi scorretti di esse. Nel corso dell'articolo cerco di separare la spiegazione in una parte intuitiva e ad alto livello e una parte matematica che entra più nei dettagli. Il lettore è invitato a concentrarsi su quale delle due parti lo interessa in quel punto e a saltare le parti meno rilevanti.

Buona lettura!

# Introduzione alle Curve Ellittiche
### Una Curva Ellittica
In generale, una curva ellittica è una sorta di linea curva. Un esempio è la parabola, la cui equazione è della forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ e appare così:

![Parabola](https://assets.kitploit.com/production/public/readmes/48932/e761eb4920ed42b6d91a3aabe8f3f88de48ff1b62e65d2867ebf244dd72f97b4.png)

Nel contesto della crittografia, è consuetudine usare curve ellittiche la cui equazione è della forma

$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$

Ad esempio, una curva ellittica corrispondente all'equazione $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ appare così:

<img src="https://assets.kitploit.com/production/public/readmes/48932/77d24f1e9aa7c309a318362c23156323e786d5d365dfaa942d163b4151f09445.png" alt="Curva ellittica semplice" width="287" height="287">

L'equazione della curva definisce la relazione tra la coordinata `𝑥` di un punto sulla curva e la sua coordinata `𝑦`. In un contesto crittografico, limitiamo `𝑥`, `𝑦`, `𝑎`, `𝑏` a essere interi e limitiamo i calcoli a essere modulo un grande numero primo. Quindi l'equazione della curva ellittica è:

$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.

Questo significa che abbiamo un numero finito di punti sulla curva. In linguaggio matematico, la curva è definita su un campo finito di ordine `𝑝`. Di conseguenza, ora non necessariamente ogni coordinata `𝑥` avrà un punto corrispondente sulla curva, perché può accadere che la coordinata `𝑦` corrispondente non sia un intero.

### Punti sulla Curva
L'insieme dei punti sulla curva è costituito da coppie di interi `(𝑥, 𝑦)` che soddisfano l'equazione della curva. Oltre a questi punti, viene definito un altro punto speciale chiamato "Infinito", denotato con `𝒪`. In linguaggio matematico, questo punto è l'elemento neutro dell'insieme dei punti sulla curva rispetto all'operazione di addizione, che definiremo nella prossima sezione. Il numero di punti sulla curva (incluso il punto `𝒪`) è chiamato "ordine della curva".

Un'altra osservazione è che le curve ellittiche sono simmetriche rispetto all'asse `X`. Ciò significa che se il punto `𝑃 = (𝑥, 𝑦)` è sulla curva, allora anche il punto `−𝑃 = (𝑥, −𝑦)` è sulla curva. In effetti, questi punti sono considerati "inversi" l'uno dell'altro (da qui la notazione `−𝑃` per il secondo punto), e il risultato dell'operazione di addizione tra loro è definito come l'elemento neutro `𝒪`.

Un teorema chiamato Teorema di Hasse fornisce una stima di `#𝐸`, l'ordine della curva, ed è dell'ordine di grandezza di `Θ(𝑝)`. Più precisamente:

$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$

### Addizione di Punti
Dati due punti sulla curva, è possibile definire un'operazione di addizione tra di essi, che produce un terzo punto anch'esso sulla curva. Per trovare geometricamente questo punto, tracciamo una linea tra i due punti dati e la prolunghiamo fino a quando interseca la curva in un terzo punto. Questo punto viene riflesso rispetto all'asse `𝑋`, e il punto risultante è definito come il risultato dell'addizione.

Ecco un diagramma che mostra come, dati i punti `𝑃` e `𝑄`, si possa trovare il punto `𝑃 + 𝑄`:

<img src="https://assets.kitploit.com/production/public/readmes/48932/73be26681f95652c8dfc62fdff6c4ea2afc6857749fb24f0886042aaec28901b.png" alt="Addizione di punti" width="300" height="300">

Una domanda che può sorgere da questa descrizione è: cosa succede se la linea tracciata tra i due punti non interseca di nuovo la curva? In questo caso si dice che la linea interseca la curva all'"infinito", e il risultato dell'addizione è il punto `𝒪`. Nota che questo caso si verifica se la linea tracciata è verticale, cioè stiamo cercando di sommare un punto `𝑃` con il suo punto inverso, `−𝑃`:

<img src="https://assets.kitploit.com/production/public/readmes/48932/abed7ccc4ea723a4088b36be5979ce13a7f8ad21d42a20e814055c9ebbf88fac.png" alt="Addizione di punti all'infinito" width="283" height="283">

Da questo derivano due identità fondamentali. Per ogni punto `𝑃` vale che:

`𝑃 + 𝒪 = 𝑃`\
`𝑃 + (−𝑃) = 𝒪`

Un'altra domanda che sorge dalla descrizione geometrica è: come si somma un punto a se stesso? Abbiamo visto che per sommare due punti diversi `𝑃` e `𝑄`, tracciamo una linea tra loro e guardiamo il punto di intersezione del suo prolungamento con la curva. Intuitivamente, lasceremo `𝑃` costante e osserveremo la linea che si crea mentre spostiamo `𝑄` "sempre più vicino" a `𝑃`, finché `𝑄` non si fonde con `𝑃`. Quello che otterremo è una linea sempre più "tangente" alla curva nel punto `𝑃`, ed è esattamente la linea che considereremo quando vogliamo sommare `𝑃` a se stesso:

<img src="https://assets.kitploit.com/production/public/readmes/48932/639aa84ded02c34e06d4629174319a77fef99abc88bbfb6aca853c958dabea71.png" alt="Moltiplicazione di punti" width="300" height="300">

Per sommare un punto `𝑃` a se stesso, tracciamo una tangente alla curva nel punto `𝑃` e la prolunghiamo finché non interseca la curva in un secondo punto. Questo punto viene riflesso rispetto all'asse `𝑋`, e il punto risultante è definito come il risultato dell'addizione. È consuetudine indicare il risultato dell'addizione come `𝑃 + 𝑃 = 2𝑃`. Di nuovo, se la tangente non interseca la curva in un secondo punto, si dice che interseca la curva all'"infinito", e il risultato dell'addizione in questo caso è il punto `𝒪`.

Queste descrizioni geometriche visive illustrano bene il funzionamento dell'addizione di punti e ci aiutano a capirla. Ma come la calcoliamo effettivamente? Con equazioni matematiche, ovviamente!

Dati i punti $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ e $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, il risultato della loro addizione è il punto $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ tale che:

$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$ \
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$

Dove `𝜆` è definito come la pendenza della linea che collega i punti, se sono diversi, e la pendenza della tangente alla curva nel punto, se il punto viene sommato a se stesso. Formalmente:

$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \   𝑠𝑒 𝑃 ≠ 𝑄$\
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \   𝑠𝑒 𝑃 = 𝑄$

I calcoli matematici dietro l'addizione di punti non sono cruciali per il resto dell'articolo. A questo proposito, possiamo considerare l'addizione di punti come una scatola nera che riceve due punti sulla curva e restituisce un terzo punto anch'esso sulla curva.

### Moltiplicare un Punto sulla Curva per una Costante
Abbiamo visto che è possibile sommare un punto `𝑃` a se stesso e abbiamo indicato il punto risultante con `2𝑃`. Se aggiungiamo di nuovo il punto `𝑃` a questo risultato, raggiungeremo un punto indicato con `3𝑃`, e così via. In questo modo è possibile definire la "moltiplicazione" di un punto per una costante, aggiungendo ripetutamente il punto a se stesso (in modo simile alla moltiplicazione tra numeri):

$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ volte)$

A quanto pare, per moltiplicare un punto per un numero `𝑛` dobbiamo eseguire `𝑛` operazioni di addizione tra punti. Questo perché, dato un punto di partenza, è difficile sapere in anticipo dove cadrà l'"ultimo" punto, senza raggiungerlo "passo dopo passo". Un calcolo del genere sarebbe molto inefficiente, perché `𝑛` potrebbe essere molto grande.

A questo scopo esiste l'algoritmo `Double And Add`, in cui si parte dal punto `𝑃`; poi, per ogni bit nella rappresentazione binaria di `𝑛`, il punto corrente viene moltiplicato per `2` (cioè sommato a se stesso) e viene aggiunto al risultato se il valore del bit è `1`. La complessità temporale di questo algoritmo è `𝑂(log 𝑛)` e consente di moltiplicare efficientemente punti per numeri molto grandi.

Una proprietà importante della moltiplicazione di punti che useremo in seguito è che per ogni punto `𝑃` e per ogni coppia di numeri `𝑎`, `𝑏` vale:

$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$

Intuitivamente, supponiamo di partire dal punto `𝑃`, fare `𝑎` passi da esso e raggiungere il punto `𝑎𝑃`. Da questo punto, facciamo `𝑏` passi di "dimensione" `𝑎` e raggiungiamo il punto `𝑏(𝑎𝑃)`. In alternativa, in un altro scenario, potremmo partire dal punto `𝑃`, fare `𝑏` passi con esso e raggiungere il punto `𝑏𝑃`. Da questo punto facciamo `𝑎` passi di "dimensione" `𝑏` e raggiungiamo il punto `𝑎(𝑏𝑃)`.

In entrambi gli scenari abbiamo fatto in totale lo stesso numero di `𝑎𝑏` passi dal punto `𝑃`, quindi in entrambi gli scenari abbiamo raggiunto lo stesso punto finale. Matematicamente, moltiplicare un punto per una costante è associativo.

### Punto Generatore
Se partiamo da un punto `𝑃` e lo sommiamo a se stesso ancora e ancora, a ogni passo raggiungeremo un nuovo punto sulla curva. Poiché il numero di punti sulla curva è finito, a un certo punto raggiungeremo di nuovo punti già raggiunti in precedenza, e ci troveremo in una sorta di ciclo, o di "cerchio". Più precisamente, a un certo punto raggiungeremo il punto `-𝑃`, al passo successivo raggiungeremo il punto `𝒪`, e al passo dopo ancora raggiungeremo di nuovo il punto `𝑃` da cui eravamo partiti.

Il punto che crea un tale "cerchio" è chiamato Generatore, perché l'intero "cerchio" può essere generato da esso, ed è consuetudine indicarlo con la lettera `𝐺`. Il numero di punti nel "cerchio" (incluso il punto `𝒪`) è chiamato "ordine del generatore `𝐺`" ed è solitamente indicato con `𝑛`. Ogni punto sulla curva forma una sorta di "cerchio". Matematicamente, l'insieme dei punti su questo "cerchio" è un gruppo ciclico.

Una proprietà interessante che ne deriva è che moltiplicare un punto `𝐺` per il suo ordine `𝑛` ci dà il punto all'infinito:\
`𝑛𝐺 = 𝒪`

### Il Problema Difficile
“Dati i punti `𝑃` e `𝑄` tali che `𝑄 = 𝑥𝑃` per un certo `𝑥`, è difficile trovare `𝑥`.”

E in parole povere, supponiamo che qualcuno sia partito da un punto di partenza, abbia fatto un certo numero di passi da esso e abbia raggiunto un punto finale. Dati il punto di partenza e il punto finale, come facciamo a sapere quanti passi ha fatto?

La risposta a questa domanda non è così intuitiva, perché è difficile prevedere in anticipo, dato un punto di partenza, quali punti verranno raggiunti facendo passi da esso. Una soluzione ingenua potrebbe essere partire noi stessi da `𝑃`, avanzare da esso un passo alla volta e contare i passi che facciamo, finché non raggiungiamo `𝑄`. La complessità di questa soluzione è `𝑂(𝑥)` ed è impraticabile se si sa che `𝑥` è un numero grande, ad esempio se `𝑥` è di `256 bit`.

Questo problema è chiamato Problema del Logaritmo Discreto su Curve Ellittiche (ECDLP), ed è un problema difficile. Ma quanto è difficile?

In un contesto crittografico, è consuetudine misurare la "difficoltà dei problemi" o la "forza di un sistema crittografico" con una metrica chiamata `Security Level`. In questa metrica, si dice che un problema abbia "`𝑛` bit di sicurezza" se il miglior attacco noto risolve il problema in $𝑂(2^𝑛)$ passi.

Attualmente, il miglior algoritmo che risolve il problema ECDLP lo fa con una complessità di $𝑂(\sqrt n)$, dove `𝑛` è l'ordine del punto `𝑃`, e lo fa usando un attacco Meet In The Middle. Quando viene scelto un punto con un ordine abbastanza grande, risolverlo è impraticabile, da qui la forza del problema.

Ad esempio, se scegliamo `𝑛` di dimensione `256 bit`, otteniamo che il problema ECDLP ha un livello di sicurezza di `128 bit` di sicurezza. Per confronto, per ottenere lo stesso livello di sicurezza di `128 bit` nella crittografia RSA, che si basa sul problema della fattorizzazione di interi, è richiesta una chiave pubblica di dimensione `3072 bit`. Questo rende l'uso delle curve ellittiche relativamente più efficiente dal punto di vista computazionale.

# Curve Ellittiche nel Contesto della Crittografia
Dopo tutta questa introduzione al mondo delle curve ellittiche, passiamo a vedere cosa si può fare con esse in un contesto crittografico. Come sappiamo, i sistemi crittografici sono solitamente basati su un "problema difficile" da risolvere. Ad esempio RSA con il problema della fattorizzazione di un numero che abbiamo menzionato, o il protocollo Diffie-Hellman con il problema del logaritmo discreto. Un sistema crittografico basato sul problema ECDLP su una curva ellittica appartiene alla famiglia della Crittografia a Curve Ellittiche, o in breve ECC.

### Primo Uso delle Curve Ellittiche - Accordo su un Segreto Condiviso
Iniziamo con una storia. Immagina di essere a una festa: una stanza piena di persone, dove tutti possono parlare con tutti e tutti ascoltano tutti. In questa stanza ci sono anche Alice e Bob, che non si sono mai incontrati prima. Alice trova simpatico Bob e vuole invitarlo a uscire. Alice è un po' timida, quindi vuole dire a Bob questo messaggio segreto senza che tutti gli altri ospiti della festa la sentano. Alice e Bob non hanno concordato nulla in anticipo, e tutto ciò che Alice dice a Bob sarà udito da tutti gli altri ospiti alla festa. Come può Alice comunicare il messaggio a Bob senza che nessun altro lo senta?

Se hai risposto "curve ellittiche", allora hai ragione!

Alice sceglierà una curva ellittica e un generatore al suo interno, e li comunicherà a Bob. Nello specifico, Alice passerà a Bob (e a tutti gli altri nella stanza) i due parametri della curva `𝑎`, `𝑏`, il modulo `𝑝` e il generatore `𝐺`. Inoltre, Alice sceglierà un valore $𝑑_𝐴$ nell'intervallo $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ dove `𝑛` è l'ordine di `𝐺`. Il valore $𝑑_𝐴$ è chiamato chiave privata di Alice. Alice calcolerà il punto $𝐴 = 𝑑_𝐴𝐺$, chiamato chiave pubblica di Alice, e lo comunicherà a Bob. Analogamente, Bob sceglierà una chiave privata $𝑑_𝐵$, calcolerà il punto $𝐵 = 𝑑_𝐵𝐺$, chiamato chiave pubblica di Bob, e lo comunicherà ad Alice.

Alice prenderà la chiave pubblica di Bob, moltiplicherà quel punto per la sua chiave privata e raggiungerà un terzo punto $𝑃_𝐴 = 𝑑_𝐴𝐵$. Analogamente, Bob prenderà la chiave pubblica di Alice, la moltiplicherà per la sua chiave privata e raggiungerà un suo terzo punto $𝑃_𝐵 = 𝑑_𝐵𝐴$. Se esaminiamo i punti che Alice e Bob hanno raggiunto separatamente, scopriamo che hanno raggiunto lo stesso punto! Questo fatto deriva dalla proprietà di associatività della moltiplicazione di un punto per una costante che abbiamo visto prima:

$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$

Alla fine dell'intero processo, Alice e Bob sono riusciti a raggiungere un accordo su un punto sulla curva, e in nessuna fase nessuno dei due ha trasmesso quel punto all'altra persona. Le informazioni che tutti hanno sentito sono: `𝑎`, `𝑏`, `𝑝`, `𝐺`, `𝐴`, `𝐵`. Una persona nella stanza che ascolta queste informazioni non può trovare il punto su cui Alice e Bob si sono accordati.

Questo perché se un'altra persona nella stanza volesse trovare quel punto, dovrebbe conoscere la chiave privata di Alice o quella di Bob per moltiplicare `𝐵` o `𝐴` per esse. Per trovare, ad esempio, la chiave privata di Alice, guarderebbe $𝐴 = 𝑑_𝐴𝐺$, perché questa è l'unica informazione che è stata inviata e che "contiene" la chiave privata di Alice. Dati `𝐺` e $𝑑_𝐴𝐺$, trovare $𝑑_𝐴$ equivale a risolvere il problema del logaritmo discreto sulle curve ellittiche, che, come già detto, è un problema difficile.

Questo bellissimo protocollo si chiama: Elliptic Curve Diffie-Hellman (ECDH).

### Uso del Segreto Condiviso per Comunicazioni Successive
La nostra storia non è ancora finita. Sebbene Alice e Bob abbiano concordato un punto segreto condiviso, Alice non ha ancora chiesto a Bob di uscire, come desiderava tanto.

Dopo che le parti hanno concordato un punto segreto condiviso, possono usarlo come chiave di cifratura di qualsiasi metodo di cifratura, ad esempio AES, e da quel momento comunicare in modo sicuro tramite cifratura.

È comune prendere una delle coordinate `𝑥` o `𝑦` del punto e usarla. Per mantenere la sicurezza, si raccomanda di applicare un hash al valore scelto e di usare solo il risultato dell'hash come chiave di cifratura. In pratica, a volte il valore è troppo grande per essere usato come chiave di cifratura. Ad esempio, se la funzione di hash usata è SHA-1, la sua lunghezza di output è `160 bit`, mentre la cifratura AES richiede solo `128 bit`. In tal caso, è consuetudine usare solo `128 bit` dei `160` e scartare il resto.

In ogni caso, a questo punto Alice e Bob concordano una chiave di cifratura e sono gli unici a conoscerla. Da questo momento in poi comunicano tramite cifratura, e chiunque ascolti nella stanza non può capire cosa si stanno dicendo.

Ecco un diagramma del protocollo:
<img src="https://assets.kitploit.com/production/public/readmes/48932/f3fe023cf8a13bf51638694db2a464ffeba35e2afb90035eeb6f4b190610c209.png" alt="ECDH">

Usando la chiave concordata, Alice cifra il messaggio "Hey Bob, ti andrebbe di uscire per un caffè domani sera?", e passa il messaggio cifrato a Bob. Bob decifra il messaggio con la chiave che conosce anche lui. Alice spera che Bob dica di sì, ma questa non è una parte del protocollo.

### Le Somiglianze tra Elliptic Curve Diffie-Hellman e Diffie-Hellman
Nel noto protocollo Diffie-Hellman (DH), le parti trasmettono apertamente un numero primo `𝑝` e un generatore `𝑔` che appartiene al gruppo corrispondente al valore `𝑝`. Alice genera casualmente una chiave privata `𝑎` e trasmette apertamente la sua chiave pubblica $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. Analogamente, Bob genera casualmente una chiave privata `𝑏` e trasmette apertamente la sua chiave pubblica $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Alice poi prende la chiave pubblica di Bob e la eleva alla sua chiave privata, calcolando così il valore $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Allo stesso modo Bob calcola il valore $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Alla fine del processo, Alice e Bob sono riusciti a concordare un valore comune `𝐾`, senza trasmetterlo tra loro.

Un attaccante che li ascolta non può trovare `𝐾` dati i valori trasmessi `𝑝`, `𝑔`, `𝐴`, `𝐵`. Per fare questo, dovrebbe trovare la chiave privata di Alice o quella di Bob. Per calcolare, ad esempio, la chiave privata di Alice, dovrebbe trovare `𝑎` dati `𝑔` e $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$, il che è un problema difficile. Questo problema è chiamato Problema del Logaritmo Discreto (DLP).

C'è una somiglianza molto chiara tra DH, che si basa su DLP, ed ECDH, che si basa su ECDLP (sono fondamentalmente lo stesso, solo con un prefisso EC). In entrambi i protocolli, due parti che comunicano tra loro possono concordare un valore segreto condiviso, senza che abbiano concordato nulla in anticipo. Chiunque ascolti i messaggi tra le parti sarà esposto alle informazioni pubbliche che si scambiano, ma non potrà raggiungere il valore segreto condiviso tra loro.### Secondo uso delle curve ellittiche - firmare un messaggio
Continuando la nostra storia, diciamo che Alice e Bob sono usciti insieme e hanno trascorso una piacevole serata. Il giorno dopo Alice riceve un messaggio che dice: «Ciao Alice, sono Bob, mi sono divertito molto con te ieri e mi piacerebbe rivederti questo fine settimana». Alice sospetta che non sia Bob a inviare il messaggio, perché sa che Bob si è divertito così tanto con lei ieri che non aspetterà fino al fine settimana per incontrarla, ma vorrà vederla domani! Come può Alice verificare che sia stato Bob a scrivere il messaggio?

Se hai risposto «curve ellittiche», hai di nuovo ragione!

La difficoltà del problema ECDLP può essere usata anche per firmare messaggi. Durante il loro appuntamento, Alice e Bob hanno concordato una curva ellittica e un generatore `𝐺` su di essa. Bob ha generato un valore $𝑑_𝐵$, chiamato chiave privata di Bob, e ha calcolato il punto $𝑃_𝐵 = 𝑑_𝐵𝐺$, chiamato chiave pubblica di Bob. Bob ha dato la sua chiave pubblica ad Alice così che potesse usarla in seguito per verificare se un messaggio ricevuto fosse stato davvero firmato da lui.

Diciamo che Bob vuole firmare un certo messaggio `𝑚`. Calcolerà il valore $z = hash(m)$ usando una qualche funzione hash sicura, e conserverà dal risultato un numero di bit pari alla lunghezza in bit di `n`, l'ordine del generatore `𝐺`. Bob genererà un valore casuale `𝑘` nell'intervallo $1 ≤ 𝑘 ≤ 𝑛 − 1$. Poi calcolerà il punto $𝑘𝐺 = (𝑥_1, 𝑦_1)$, ne prenderà la coordinata `𝑥` e calcolerà $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Infine, Bob calcolerà il valore $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.

La firma del messaggio `𝑚` è definita come la coppia di valori calcolati `𝑟` e `𝑠`.

Supponiamo che Alice abbia ricevuto un certo messaggio `𝑚` e che la sua firma sia composta da una coppia di valori `𝑟` e `𝑠`. Alice vuole assicurarsi che sia davvero Bob ad aver firmato il messaggio. Alice calcolerà il valore $z = hash(m)$ nello stesso modo di Bob. Poi calcolerà i valori $𝑢_1 = 𝑧𝑠^{−1}$ e $𝑢_2 = 𝑟𝑠^{−1}$. Infine, Alice userà la chiave pubblica di Bob $𝑃_𝐵$ e calcolerà il punto $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. La firma sarà considerata valida se vale che $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. Il motivo per cui questo è corretto è che vale:

$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$

Se la firma è valida, la coordinata `𝑥` di questo punto dovrebbe effettivamente essere `𝑟`, come definito nella firma del messaggio. Va notato che l'ordine del generatore `𝐺`, indicato con la lettera `𝑛`, dovrebbe essere un numero primo; questo è necessario affinché sia effettivamente possibile calcolare i numeri inversi negli algoritmi di firma e verifica.

Si può vedere che solo chi possiede la chiave privata $𝑑_𝐵$ può creare una firma valida per la chiave pubblica $𝑃_𝐵$. Un attaccante che non ha il valore $𝑑_𝐵$ non può calcolare il valore `𝑠` corrispondente a $𝑃_𝐵$ nella firma. Se l'attaccante vuole creare una firma che corrisponda a un certo messaggio, dovrà risolvere il problema ECDLP, cioè trovare la chiave privata $𝑑_𝐵$ dati $𝐺$ e $𝑃_𝐵 = 𝑑_𝐵𝐺$, che è un problema difficile.

Questo protocollo di firma è chiamato Elliptic Curve Digital Signature Algorithm, o in breve ECDSA. Il protocollo garantisce che i messaggi firmati non siano stati alterati o contraffatti e, in aggiunta, garantisce che la persona che ha firmato il messaggio non possa negare di averlo creato.

A differenza del protocollo ECDH, in cui le parti non devono concordare nulla in anticipo, nel protocollo ECDSA le parti devono accordarsi in anticipo su una chiave pubblica. Solo dopo che ciascuna parte è certa che la chiave pubblica che possiede appartenga davvero alla persona con cui vuole comunicare, il protocollo può essere usato. Altrimenti, non ha senso verificare la firma con la chiave pubblica posseduta da ciascuna parte.

Torniamo alla nostra storia. Alice sa per certo che la chiave pubblica $𝑃_𝐵$ in suo possesso appartiene davvero a Bob, perché Bob gliel'ha data esplicitamente durante l'appuntamento. Alice prova a verificare il messaggio con essa e scopre che non c'è corrispondenza. Ovviamente! Qualcun altro ha creato il messaggio e lo ha firmato, proprio come Alice sospettava.

Ecco un diagramma del protocollo:
<img src="https://assets.kitploit.com/production/public/readmes/48932/84854e1ed16d1dfdcdeb6c5d4917ab6d454163373a3b924c3040c1c96e465678.png" alt="ECDSA">

### Le somiglianze tra ECDSA ed ElGamal
Nel protocollo ElGamal per la firma di messaggi, le parti concordano un grande numero primo `𝑝` e un numero generatore `𝑔`. La parte firmataria genera un valore `𝑑` nell'intervallo $1 ≤ 𝑑 < 𝑝 − 1$, chiamato chiave privata, calcola il valore $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, chiamato chiave pubblica, e lo pubblica.

Per firmare un certo messaggio, calcolano il valore $z = hash(m)$ e generano un valore casuale `𝑘` nell'intervallo $1 ≤ 𝑘 < 𝑝 − 1$ che sia coprimo con $(p-1)$. Calcolano $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ e $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. La firma del messaggio `m` è definita come la coppia di valori calcolati `𝑟` e `𝑠`.

La parte che ha ricevuto un certo messaggio `𝑚`, la cui firma è composta da una coppia di valori `𝑟` e `𝑠`, usa la chiave pubblica `𝑦` per verificare la firma calcolando i valori $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ e $𝑢_2 = 𝑔^𝑧$. La firma sarà considerata valida se $𝑢_1 = 𝑢_2$. Questo perché, secondo la definizione di `𝑠`, si ha:\
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, quindi $𝑘𝑠 = 𝑧 − 𝑑𝑟$, da cui $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Pertanto:

$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$

Un attaccante non può creare una firma valida per la chiave pubblica `𝑦` senza conoscere la chiave privata `𝑑`. Per ottenere la chiave privata data la chiave pubblica, l'attaccante dovrebbe risolvere il problema DLP, che è un problema difficile.

Anche qui c'è una chiara somiglianza tra ECDSA, che si basa su ECDLP, ed ElGamal, che si basa su DLP. In entrambi i casi, le parti devono concordare in anticipo una chiave pubblica, ed è necessario generare un valore casuale `𝑘` ogni volta che si vuole firmare un nuovo messaggio. Inoltre, in entrambi i casi un attaccante che ascolta i messaggi tra le parti non può ricavare informazioni utili che gli permettano di contraffare firme.

# Attacchi a ECC
Abbiamo visto come le curve ellittiche possano essere usate nei sistemi crittografici per concordare un valore segreto e per firmare messaggi. Come per tutto nella vita, quando si tratta di mettere in pratica qualcosa, le cose non vanno sempre come previsto. Nel resto dell'articolo presenterò diversi modi per attaccare sistemi crittografici basati su ECC che sono stati usati in modo improprio dall'utente o implementati in modo non sicuro.

Naturalmente, divido questa parte in attacchi a ECDH e attacchi a ECDSA. In entrambi i casi diremo che abbiamo «avuto successo» nell'attacco se troviamo la chiave privata di una delle parti, e ci fermeremo lì. Nel caso di ECDH, è sufficiente perché dalla chiave privata è possibile risalire al valore segreto condiviso e a tutte le informazioni successivamente cifrate con esso. Nel caso di ECDSA, è sufficiente perché la chiave privata può essere usata per firmare messaggi a piacere.

### SageMath
SageMath è un software matematico gratuito e open source. Può essere scritto con una sintassi quasi identica a Python e può anche essere usato come libreria Python. Questa libreria implementa funzioni utili relative alle curve ellittiche ed è quindi molto utile per i calcoli che dobbiamo fare nel contesto di ECC. In questo articolo fornisco frammenti di codice scritti con questa libreria. Ho scoperto che è più semplice installarla sul sistema operativo Ubuntu, in particolare sulla versione 22.04. Per installarla, basta eseguire il comando: `sudo apt install sagemath`.
Per eseguire un file che contiene codice, salvare il file con estensione .sage ed eseguire il comando: `sage file.sage`.

Inoltre, si può usare un interprete, simile all'interprete di Python, eseguendo il comando: `sage`. È anche possibile creare file .py in cui viene importata la libreria sage.all ed eseguirli con il comando `python3 file.py`. Nota che quando si esegue un file con il comando `sage`, la notazione `^` viene interpretata come potenza, mentre quando si esegue con `python3`, questa notazione viene interpretata come xor.

In questo articolo uso principalmente le seguenti funzioni di SageMath:
- `E.gens()` - trova i generatori nella curva `E`
- `G.order()` - calcola l'ordine del generatore `G`
- `n*G` - moltiplicazione del generatore `G` per il numero `n`
- `n.factor()` - fattorizza il numero `n` nei suoi fattori - la funzione restituisce una lista di coppie `(𝑝, 𝑒)` tali che `𝑝` è un fattore primo ed `𝑒` è il suo esponente, cioè il numero di volte che `𝑝` appare nella scomposizione di `n`
- `crt` - risolve un sistema di equazioni del teorema cinese del resto

# Attacchi a ECDH
## L'ordine del generatore è troppo piccolo
Probabilmente l'uso scorretto di ECDH più facile da attaccare è scegliere un generatore con un ordine `n` troppo piccolo.

Come accennato, è possibile risolvere il problema ECDLP con una complessità di $O(\sqrt{n})$. Quando `𝑛` è troppo piccolo, ad esempio 32 bit, diventa fattibile risolvere questo problema. Esistono diversi algoritmi che risolvono il problema, tra cui Baby-Step Giant-Step, Pollard's Rho e Pollard's Lambda. Questi algoritmi possono essere eseguiti come una scatola nera con l'aiuto di SageMath, usando la funzione `discrete_log`:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
```
In questo frammento di codice scegliamo i parametri della curva casualmente, con il vincolo che `𝑝` sia lungo 32 bit. Questo vincolo ci garantisce che il numero di punti sulla curva sia $O(2^{32})$ e quindi anche l'ordine di ogni punto su di essa sia al massimo $O(2^{32})$. Dopodiché creiamo la curva, scegliamo un generatore al suo interno, generiamo una chiave privata casuale e calcoliamo la chiave pubblica. Infine, dal generatore e dalla chiave pubblica, calcoliamo il logaritmo discreto per trovare la chiave privata e verifichiamo che la chiave trovata sia effettivamente corretta. Questo codice impiega al massimo pochi secondi per trovare la chiave privata.



## L'Ordine Del Generatore È Un Numero Smooth
Come accennato, l'ordine di un generatore è definito come il numero di punti nel "cerchio" formato quando sommiamo il punto generatore a sé stesso ripetutamente, ed è indicato con `𝑛`. Se `𝑛` è un numero composto che può essere scomposto in fattori primi più piccoli, allora è possibile risolvere ECDLP in modo efficiente. Un tale numero è chiamato Numero Smooth e, ai fini di questo articolo, è un numero che può essere scomposto in un numero sufficiente di fattori primi, ciascuno dei quali è abbastanza piccolo perché il nostro attacco funzioni. La definizione formale di Numero Smooth è leggermente diversa e non rilevante per noi.

Intuitivamente, questo viene fatto "attaccando" ciascuno dei fattori primi separatamente. Dato un punto generatore `𝐺` che forma un "cerchio" molto grande, e un punto `𝑃` nel "cerchio" tale che `𝑃 = 𝑘𝐺`. Il grande "cerchio" può essere smontato in diversi piccoli "cerchi", ciascuno delle dimensioni di un fattore primo di `𝑛`. In ogni piccolo "cerchio" possiamo mappare `G` e `P` in altri punti corrispondenti `G'` e `P'` che si trovano nel piccolo "cerchio" e soddisfano `𝑃′ = 𝑘′𝐺′`. Poiché il "cerchio" è piccolo, è relativamente facile risolvere il problema e trovare `𝑘′`. Infine, possiamo combinare tutti i piccoli `𝑘′` trovati nel `𝑘` desiderato nel "cerchio" originale.

L'algoritmo che esegue ciò che ho descritto è chiamato Algoritmo di Pohlig-Hellman. La sua complessità temporale è $O(\sqrt{p_{max}})$ dove $p_{max}$ è il più grande fattore primo nella scomposizione di `𝑛`. Ha anche senso, perché la parte più "pesante" nell'algoritmo è risolvere il problema ECDLP nel più grande "cerchio" tra i "cerchi" più piccoli. Ad esempio, `n` potrebbe essere un numero a 128 bit e si scompone in fattori primi tali che il più grande sia un numero a 30 bit. L'algoritmo riduce la complessità di risolvere il problema da $2^{64}$ a $2^{15}$, trasformandolo così da irrealizzabile a fattibile.

Fortunatamente, la funzione `discrete_log` di SageMath esegue questo algoritmo nella sua implementazione. Per eseguire l'attacco puoi semplicemente chiamare la funzione:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
```
In questo frammento di codice definiamo una curva ellittica e un suo generatore, e stampiamo i fattori primi del suo ordine. L'output è:```
number of bits in n: 128
n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 *
2234328781
number of bits in n's greatest factor: 32
Calculating discrete_log...
success!
```
Si può notare che, sebbene l'ordine del generatore sia lungo 128 bit, esso si scompone in fattori primi tali che il più grande fattore primo è di 32 bit.

Dopodiché, proprio come nell'attacco precedente - scegliamo una chiave privata casuale, ne calcoliamo la chiave pubblica, quindi, dati il generatore e la chiave pubblica, calcoliamo la chiave privata e verifichiamo che sia corretta.

Anche se abbiamo finito, non abbiamo ancora visto come sono definiti i "piccoli" cerchi, come mappare i punti `𝐺` e `𝑃` nei corrispondenti punti `𝐺′` e `𝑃′`, e come combinare tutte le piccole soluzioni in un'unica grande soluzione. Proverò a spiegarlo qui in modo intuitivo, perché anche il prossimo attacco si basa su questa parte.

Supponiamo di avere un "cerchio" di ordine `3𝑥5𝑥7 = 105`, e che il suo generatore sia `𝐺`. Definiamo un punto `𝐺′ = (5𝑥7)𝐺 = 35𝐺`, e osserviamo il "cerchio" generato da esso. Se da `𝐺′` facciamo un "passo", cioè aggiungiamo `𝐺′` a sé stesso, sarà come avanzare di 35 passi dal punto `35𝐺` nel "cerchio" originale, e raggiungeremo il punto `2𝐺′ = 70𝐺`. Se facciamo un altro "passo", raggiungeremo il punto `3𝐺′ = 105𝐺 = 𝒪`, e se da lì facciamo un altro "passo", raggiungeremo il punto `4𝐺′ = 35𝐺 = 𝐺′`, cioè di nuovo al punto di partenza. Il "cerchio" formato da `G′` è di ordine `3`, e non è un caso, perché su un "cerchio" di ordine `105` è possibile fare esattamente `3` "passi" di dimensione `35`. Allo stesso modo, potremmo creare un "cerchio" di ordine `5` definendo il punto `𝐺′ = (3𝑥7)𝐺 = 21𝐺`, e un cerchio di ordine `5` definendo `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.

Quando lo guardiamo dall'altro lato diventa più interessante. Supponiamo che nel "cerchio" originale abbiamo fatto `𝑛` passi dal punto `G` e siamo arrivati al punto `𝑛𝐺`. Se anche nel piccolo "cerchio" facessimo `𝑛` passi dal punto `𝐺′`, raggiungeremmo il punto `𝑛′𝐺′` tale che `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. E perché è interessante? Perché l'ordine di `𝐺′` è molto più piccolo dell'ordine di `𝐺` e quindi, dati `𝐺′` e `𝑛′𝐺′`, possiamo trovare `𝑛′` con relativa facilità. Se lo facciamo, e lo facciamo anche per gli altri due fattori primi dell'ordine del "cerchio", che sono `5` e `7`, avremmo i seguenti valori:

𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)

Da questi tre valori, `𝑛` può essere facilmente trovato usando il Teorema Cinese del Resto, risolvendo così il problema originale.

## L'ordine del generatore è quasi un numero liscio e la chiave privata è piccola

Supponiamo che, analogamente all'attacco precedente, otteniamo una curva in cui l'ordine del generatore si scompone in fattori primi, ma questa volta il fattore primo più grande è troppo grande perché sia pratico risolverne l'ECDLP. Ad esempio, se l'ordine del generatore è `256 bit`, ma il fattore primo più grande è `128 bit`.

L'algoritmo di Pohlig-Hellman richiederà circa $O(2^{64})$ operazioni per trovare la chiave privata, il che è impraticabile.

Se sappiamo che la chiave privata utilizzata è relativamente piccola, può comunque essere trovata in modo efficiente.

Supponiamo che la chiave privata sia `64 bit` (invece di `256 bit`). Quando viene creata la chiave pubblica, il generatore viene moltiplicato per la chiave privata e si ottiene un punto nel "cerchio" che il generatore crea. Sebbene il "cerchio" abbia una dimensione di circa $2^{256}$ punti, questo punto "cadrà" da qualche parte tra i "primi" $2^{64}$ punti. Non c'è alcuna "interazione" tra la chiave privata e i punti nel "cerchio" che corrispondono a valori più grandi.

È possibile eseguire l'algoritmo di Pohlig-Hellman, ma "scartare" i "cerchi" troppo grandi, purché il prodotto degli ordini dei "cerchi" rimanenti sia almeno pari alla lunghezza della chiave privata. Se vengono trovati abbastanza fattori primi piccoli, il cui prodotto sia di almeno `64 bit`, allora i "cerchi" corrispondenti saranno sufficienti per eseguire lo stesso attacco visto in precedenza.

Se prima avevamo vita facile in termini di scrittura del codice, questa volta dovremo implementare le cose da soli, perché la funzione `discrete_log` di SageMath non sa che vogliamo "scartare" alcuni dei fattori primi. Il seguente frammento di codice fa questo:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
      68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()

print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)

PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G

print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
    new_order *= p^e
    count_factors_needed += 1
    if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
        print("Found enough factors! The rest are not needed")
        break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)

print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
    quotient_n = (n // p ^ e)
    G0 = quotient_n * G # G0's order is p^e
    P0 = quotient_n * P
    k = G0.discrete_log(P0)
    subsolutions.append(k)
    subgroup.append(p ^ e) # k the order of G0

print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
```
In questo frammento di codice definiamo una curva ellittica e un generatore al suo interno, e stampiamo i fattori primi del suo ordine. L'output è:```
Number of bits in n: 256
n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 *
84878782522781478604307230464271
```
L'ordine del generatore è `256 bit` e si scompone in diversi fattori primi, tali che i due più grandi siano `77 bit` e `107 bit`. Sono abbastanza grandi da rendere impraticabile risolvere l'ECDLP. Quindi, viene generata casualmente una chiave privata di `64 bit` e viene calcolata una chiave pubblica. Nel passaggio successivo "raccogliamo" abbastanza fattori primi finché non otteniamo un ordine con una lunghezza di almeno `64 bit`. L'output è:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
```
Si può vedere che i due fattori più grandi sono ridondanti, e il fattore più grande che rimane è `40 bit`. Nel passaggio successivo, per ciascuno dei fattori rimasti, calcoliamo i punti `𝐺′` e `𝑃′` come ho spiegato in precedenza, e per ciascuno di essi risolviamo l'ECDLP. I risultati e i fattori primi vengono conservati rispettivamente nelle liste `subsolutions` e `subgroups`. Infine, tutti i risultati vengono combinati usando il teorema cinese del resto per ottenere la chiave privata, e verifichiamo che sia effettivamente corretta.

## Non verificare che un punto sia sulla curva

Esaminando la definizione dell'addizione di punti nelle curve ellittiche, notiamo una proprietà interessante: nell'addizione di punti non viene usato il valore `𝑏`, ma solo i valori `𝑎` e `𝑝`. Questo significa che aggiungere punti che giacciono su una curva può essere significativo anche per un'altra curva, che differisce da essa solo per quel valore di `𝑏`. Questo vale ovviamente anche per la moltiplicazione di un punto per un numero. Se l'utente non verifica che il punto ricevuto dall'altra parte come chiave pubblica si trovi effettivamente sulla propria curva, allora si espone a un attacco tramite curva non valida.

Supponiamo che due parti abbiano concordato una certa curva ellittica $E_1$. Un attaccante può creare una curva malevola $𝐸_2$, che ha gli stessi valori `𝑎` e `𝑝` di $𝐸_1$ ma un valore `𝑏` diverso. Sulla curva $𝐸_2$ l'attaccante sceglierà un punto `𝑃` il cui ordine è piccolo, ad esempio `3`. Naturalmente, il punto `𝑃` non si troverà su $𝐸_1$, poiché soddisfa un'equazione con un valore `𝑏` diverso da quello di $𝐸_1$. L'attaccante invierà il punto `𝑃` come propria chiave pubblica all'utente. Supponiamo che l'utente non si preoccupi di verificare che il punto ricevuto sia effettivamente sulla curva $𝐸_1$ concordata dalle parti. L'utente prenderà la chiave pubblica ricevuta dall'attaccante, la moltiplicherà per la propria chiave privata e raggiungerà un punto che dovrebbe essere il punto segreto condiviso, come abbiamo visto nella definizione del protocollo ECDH. Dal punto di vista dell'utente, calcolerà l'operazione di moltiplicazione sulla curva $𝐸_1$. Ma poiché il punto `𝑃` non si trova affatto su di essa, bensì su $𝐸_2$, l'utente calcolerà in realtà l'operazione di moltiplicazione sulla curva $𝐸_2$. In seguito, l'utente userà il punto segreto condiviso per continuare la comunicazione con l'attaccante. Supponiamo che le parti utilizzino la coordinata `𝑥` del punto come chiave di cifratura AES. In questo caso, l'utente cifrerà un messaggio e lo invierà all'attaccante.

Poiché l'ordine di `𝑃` è `3`, ci sono solo `3` possibili punti condivisi che l'utente può calcolare. L'attaccante esaminerà questi possibili punti e troverà quale di essi corrisponde alla chiave che decifra con successo il messaggio cifrato inviato dall'utente. Dato questo punto e il punto iniziale `𝑃`, l'attaccante può dedurre il resto della divisione della chiave privata dell'utente per il numero `3`. L'attaccante può inviare all'utente ulteriori punti `𝑃` malevoli, con ordini crescenti, ad esempio `5`, `7`, e così via. In questo modo l'attaccante può raccogliere abbastanza valori che rappresentano i resti delle divisioni della chiave privata dell'utente per piccoli numeri. Infine l'attaccante può usare il teorema cinese del resto per calcolare la chiave privata dell'utente, nello stesso modo visto nell'attacco precedente.

Ecco una spiegazione più intuitiva: un attaccante può fornire all'utente un punto su un "cerchio" molto piccolo, ad esempio di lunghezza `2`. L'utente avanzerà in questo "cerchio" di un numero qualsiasi di passi e raggiungerà il punto di destinazione. L'attaccante conosce il punto di destinazione dell'utente, che può essere una delle `2` possibilità. Quindi l'attaccante può capire se l'utente ha compiuto un numero pari o dispari di passi sul cerchio. L'attaccante può fornire all'utente ulteriori punti su "cerchi" di lunghezze `3`, `5`, `7`, e così via. Finché l'attaccante non ha abbastanza di questi fattori, ciascuno dei quali contiene poche informazioni sul numero di passi compiuti dall'utente. Infine l'attaccante può combinare tutti questi valori nel numero esatto di passi compiuti dall'utente, che è la sua chiave privata.

Il codice seguente dimostra l'attacco:```python
from ecdsa.ecdsa import generator_128r1, curve_128r1
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import random


# Select a curve and generator
curve = curve_128r1
G = generator_128r1
n = G.order()
p = curve.p()
a = curve.a()

# This is the private key of the other side, we don't know it and don't use it!
private_key = random.randrange(n)


# Both sides encrypt and decrypt data the same way
# key is the shared point's x coordinate, IV is point's y coordinate
def encrypt_data(shared_point, message):
    if shared_point.is_zero():
        x, y = 0, 0
    else:
        x, y = shared_point.xy()
    key = long_to_bytes(int(x)).rjust(16, b"\x00")
    iv = long_to_bytes(int(y)).rjust(16, b"\x00")
    cipher = AES.new(key, AES.MODE_CBC, iv)

    message = pad(message.encode(), 16)
    return cipher.encrypt(message)


def decrypt_data(shared_point, enc_message):
    if shared_point.is_zero():
        x, y = 0, 0
    else:
        x, y = shared_point.xy()
    key = long_to_bytes(int(x)).rjust(16, b"\x00")
    iv = long_to_bytes(int(y)).rjust(16, b"\x00")
    cipher = AES.new(key, AES.MODE_CBC, iv)

    decrypted = cipher.decrypt(enc_message)
    return unpad(decrypted, 16)


def ECDH(A):
    # Send our public key to the other side
    # Have them reach the shared point and
    # Send us an encrypted message using the shared point as key

    # This part takes place remotely and is unknown to the attacker
    shared_point = private_key * A
    message = "Inconceivable!"
    return encrypt_data(shared_point, message)


def brute_force_encrypted_message(A, encrypted_message, max_order):
    # Returns n such that n*A matches the key used to encrypt the message
    for i in range(1, max_order):
        shared_point = i * A
        try:
            # If both padding is correct and all characters are ascii
            # Then it is probably the correct encryption key
            decrypted = decrypt_data(shared_point, encrypted_message)
            decrypted = decrypted.decode()
            return i
        except:
            continue
    raise Exception("Did not find a value for one of the encrypted messages")


def find_curves_with_small_subgroup(p, a, max_order):
    # Yield tuples of (order, point) such that the point is
    # on a curve with the same a & p values, but different b
    # and the point's order is <= max_order
    orders_found = set()
    b = 0
    while True:
        b += 1
        if b == p:
            # Ran out of b values
            break
        if (4*a^3 + 27*b^2) % p == 0:
            # Curve is singular
            continue

        E = EllipticCurve(GF(p), [a, b])
        for _ in range(100):
            R = E.random_point()
            n = R.order()
            for f, e in n.factor():
                if f in orders_found:
                    continue
                if f > max_order:
                    break

                # Create a point with order f
                orders_found.add(f)
                P = (n // f) * R
                assert P.order() == f
                yield (f, P)


subsolutions = []
subgroup = []
max_order = 10000
upto = 1
for order, A in find_curves_with_small_subgroup(p, a, max_order):
    upto *= order
    print("Found point with order", order, "so now can find keys of size up to", upto)

    # Send this point as our public key and get an encrypted message from other side
    encrypted_message = ECDH(A)

    # Find the value n such that: private_key = n (mod order)
    key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)

    # Save result to be used in CRT later
    subsolutions.append(key_mod_order)
    subgroup.append(order)

    # Found enough values to calculate private key
    if upto >= n:
        break

print("Found enough values! Running CRT...")
found_key = crt(subsolutions, subgroup)
print("Found private key", found_key)
assert private_key == found_key
print("success!")
```
In questo frammento di codice vengono selezionati una curva e un generatore; l'utente genera casualmente una chiave privata e la usa per tutti gli utilizzi del protocollo ECDH. La funzione `find_curves_with_small_subgroup` trova coppie di punti e ordini, tali che l'ordine di ogni punto sia relativamente piccolo e che il punto si trovi su una curva diversa da quella originale solo per il valore di `𝑏`. Il codice genera tali coppie finché non ne trova abbastanza. Per ogni coppia, la chiave pubblica viene inviata all'utente e da esso viene ricevuto un messaggio cifrato.

Sul messaggio cifrato viene eseguita una ricerca a forza bruta per trovare il valore della chiave privata dell'utente, modulo l'ordine corrente. Tutti questi risultati vengono salvati e, infine, usiamo il Teorema Cinese del Resto per calcolare la chiave privata dell'utente e verificarne la correttezza. In questo caso, le parti hanno concordato che la comunicazione avverrà in AES, con chiave di cifratura pari alla coordinata `x` del punto del segreto condiviso e IV pari alla sua coordinata `𝑦`.

La complessità dell'attacco è $𝑂(𝑛_{𝑚𝑎𝑥})$ dove $𝑛_{𝑚𝑎𝑥}$ è l'ordine più grande tra gli ordini dei punti maliziosi. Questo perché la parte più "pesante" dell'attacco è la forza bruta sul "cerchio" più grande tra i piccoli "cerchi" e, fortunatamente per l'attaccante, può controllare quasi completamente questo valore. Pertanto questo attacco è relativamente efficiente in termini di complessità. Come già menzionato, la radice del problema in questo caso è che l'utente non verifica nemmeno che il punto ricevuto si trovi sulla curva con cui sta lavorando. Inoltre, l'utente usa la stessa chiave privata in ogni nuovo utilizzo di ECDH, il che non è molto sicuro.

## La curva è singolare

Una delle proprietà importanti che una curva ellittica deve avere per essere crittograficamente sicura è di essere non singolare. Una curva non singolare è una curva in cui un certo valore, chiamato "discriminante" della curva, è diverso da zero. Vale quando i suoi parametri `𝑎` e `𝑏` soddisfano la disuguaglianza:

$4a^3 + 27b^2 ≠ 0$

Una curva che non soddisfa questa disuguaglianza ha un punto "problematico" chiamato `singular point`. Esistono due tipi di tali punti: nodo e cuspide. Un punto di nodo si trova su una curva che ha una sorta di cappio che si interseca nel punto singolare, e attraverso questo punto si possono tracciare due tangenti diverse alla curva.
Un punto di cuspide è un punto in cui la curva è "appuntita", come se due linee ne uscissero, ma esiste una sola tangente alla curva in quel punto.

<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Curve Ellittiche Singolari"  width="500">

In un punto di tipo nodo è presente una radice doppia, quindi l'equazione della curva può essere scritta come:

$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$

La curva può essere "spostata" a sinistra sostituendo la variabile $x$ con la variabile $(𝑥 + 𝑥_0)$, ottenendo così la forma:

$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$

Ora il punto singolare si trova nell'origine degli assi. Il valore numerico di $t = (x_0-x_1)$ può essere usato per creare una mappatura dai punti della curva agli interi, tale che l'operazione di addizione tra punti sulla curva sia equivalente all'operazione di moltiplicazione tra numeri. Per ogni punto `(𝑥, 𝑦)` assoceremo il numero
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. In particolare, a una coppia di punti `𝐺` e `𝑄` tale che `𝑄 = 𝑛𝐺` possiamo associare numeri `𝑔` e `𝑞` tali che $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, e questo è un problema DLP "normale". Per illustrare questo processo, ho aggiunto un collegamento a un esempio con numeri piccoli nei riferimenti alla fine dell'articolo. Nella mappatura che abbiamo effettuato, abbiamo usato le equazioni delle rette $y+\sqrt{t}x$ e $y-\sqrt{t}x$, e queste sono le rette che corrispondono alle due tangenti che possono essere tracciate nel punto singolare (dopo aver "spostato" la curva), che è essenzialmente il motivo per cui questo attacco può essere usato.

Un tale problema DLP può essere risolto in modo efficiente con l'aiuto dell'algoritmo di Pohlig-Hellman, che abbiamo già visto in precedenza, perché può essere usato anche su interi invece che su punti della curva. Nel contesto dei punti, abbiamo visto che l'algoritmo è utile quando l'ordine del generatore è un numero liscio. A differenza di un "cerchio" di punti su una curva, che può avere un ordine qualsiasi, nel campo degli interi modulo un numero primo `𝑝` l'ordine è `𝑝 − 1`. Se `𝑝 − 1` è un numero liscio, allora l'algoritmo risolverà il problema DLP in modo efficiente, trovando così la chiave privata `n`.

Il seguente frammento di codice fa proprio questo:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0

Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066

x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()

assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
    double_root = roots[0][0]
    single_root = roots[1][0]
else:
    double_root = roots[1][0]
    single_root = roots[0][0]

print("double root:", double_root)
print("single root:", single_root)

# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)

# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()

def transform(x, y, t_sqrt):
    return (y + t_sqrt * x) / (y - t_sqrt * x)

g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)

# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)

from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
```
In questo frammento di codice definiamo i parametri di una curva ellittica e verifichiamo che sia effettivamente singolare. Troviamo le radici del polinomio corrispondente alla curva e identifichiamo quale di esse sia la radice doppia. Usiamo la radice doppia per "spostare" la curva e raggiungere i punti "spostati" `𝐺` e `𝑄`. Quindi calcoliamo $\sqrt{t}$ dalle radici che abbiamo trovato e lo usiamo per mappare i punti `𝐺` e `𝑄` ai numeri `𝑔` e `𝑞`. Stampiamo la decomposizione di `𝑝 − 1` nei suoi fattori primi (per verificare che il DLP possa effettivamente essere risolto in modo efficiente). Infine calcoliamo il DLP e interpretiamo il risultato come una stringa.

L'output è: ```
double root: 1
single root:
102360775616927576983385464260307534406913988994641083488371841417601237589485
g: 79308184675041981395063385790064051127319168083579208141274962436724168376607
q: 72551144069373709737718398534799929820619379063890479978458954196900267190559
Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
* 3792634171577 * 3997021218613
Calculating discrete log for g and q...
Found private key:
30943506368388267314266516224984737426569114488424608324579076903023329506337
The secret is: Digital Whisper is pretty great!
 ```
Questa volta ho nascosto un messaggio nella chiave privata stessa. Va notato che, essendo una curva singolare, non è possibile in SageMath crearla in modo normale, definire punti su di essa ed eseguire operazioni con essi come abbiamo fatto prima. In questo codice ho definito le coordinate dei punti come variabili costanti. Per calcolare il punto `𝑄` ho moltiplicato la chiave privata per il generatore usando la mia implementazione dell'algoritmo Double And Add.


## La curva è supersingolare
Data una curva ellittica modulo `𝑝` e un generatore il cui ordine è `𝑛`, il grado di embedding della curva rispetto al generatore è definito come il più piccolo numero `k` che soddisfa l'equazione $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. Con certe trasformazioni, il problema ECDLP può essere ridotto a un problema DLP in un campo di ordine $𝑝^𝑘$. Il valore `𝑘` è di solito un numero molto grande (circa della stessa dimensione di `𝑝` stesso), ma quando è relativamente piccolo (ad esempio, minore di `6`), la curva è chiamata `supersingolare` e diventa fattibile risolvere efficientemente questo problema DLP. Questo attacco è chiamato attacco MOV, dal nome dei suoi tre inventori (Menezes-Okamoto-Vanstone).

Le trasformazioni che ho menzionato sono funzioni che ricevono due punti e restituiscono un numero nel campo dei numeri complessi. Le trasformazioni utilizzabili sono il Weil Pairing o il Tate Pairing, e le useremo come una scatola nera. Tale trasformazione `𝑇` soddisfa la seguente proprietà per ogni coppia di punti `𝑃`, `𝑄`:

$T(mP, nQ)=T(P,Q)^{mn}$


Pertanto, dati due punti `𝐺` e `𝑄 = 𝑚𝐺`, possiamo selezionare casualmente un terzo punto `𝑅` e calcolare i due valori: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
Da qui possiamo risolvere il problema DLP per `𝑔` e `𝑞` in un campo di ordine $p^k$, trovando così la chiave privata `𝑚`. Ho incluso un link a una spiegazione più dettagliata della matematica alla base di questo attacco, nei riferimenti alla fine dell'articolo.

Il seguente frammento di codice esegue questo attacco:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052, 
      524474557735717484100814381066)

# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
    k += 1
print("Found k:", k)

# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G

# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()

# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY

# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)

# Make sure the pairing did not break anything
assert g ^ private_key == q

print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")

from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
```
In questo frammento di codice definiamo una curva e il suo generatore, e calcoliamo il suo valore di Embedding Degree, che in questo caso è `2`, quindi è pratico eseguire l'attacco. Definiamo una curva identica alla curva originale, tranne per il fatto che i calcoli vengono eseguiti modulo $𝑝^𝑘$ invece che modulo $𝑝$. I due punti `𝐺` e `𝑄` sono anch'essi sulla nuova curva. Poi troviamo un terzo punto il cui ordine divide `𝑛`.

Usando il terzo punto, mappiamo i punti `𝐺` e `𝑄` ai numeri `𝑔` e `𝑞` e calcoliamo per essi il logaritmo discreto. Infine, verifichiamo  il risultato ottenuto sia effettivamente corretto.

L'output è:```
Found k: 2
Calculating private key...
success!
The private key is: Festivus
```
Da un punto di vista computazionale, oggi esistono algoritmi Index Calculus che possono risolvere il problema DLP in modo relativamente efficiente, e lo fanno con complessità $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Questa espressione può sembrare spaventosa, ma rispetto agli algoritmi ECDLP la cui complessità è $O(\sqrt{p})=e^{O(log\ p)}$, si può vedere che è più facile risolvere il problema DLP, supponendo che il grado di embedding (indicato con `𝑘`) sia effettivamente piccolo.



## La curva è anomala
Se una certa curva ha la proprietà che l'ordine della curva (il numero di punti su di essa) è esattamente uguale al modulo `𝑝`, allora viene chiamata `curva anomala` ed è vulnerabile a un attacco chiamato attacco di Smart. Questo attacco usa i `numeri 𝑝-adici`. Un tale numero può essere rappresentato come una somma di potenze di `p` (positive e negative) con coefficienti. Formalmente, tale numero `s` è una serie della forma:

$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$

Quando i coefficienti sono interi nell'intervallo $0 ≤ 𝑎_𝑖 < 𝑝$, e la somma può essere infinita nella direzione delle potenze positive di `𝑝`. In tali numeri, "guardiamo" le cifre da destra a sinistra invece che da sinistra a destra, e quindi tale serie può convergere a qualche valore. Tali numeri appartengono a un sistema numerico diverso da quello con cui abbiamo familiarità, e si comportano in modo molto diverso dalle regole matematiche "normali". Un intero articolo separato potrebbe essere scritto solo su questo argomento, e per chi fosse interessato, ho incluso nei riferimenti alla fine dell'articolo un link a un video che lo presenta in modo relativamente chiaro.

In ogni caso, in questo attacco viene creata una nuova curva a partire dalla curva data, che è definita sui numeri p-adici. Dati due punti `𝐺` e `𝑄 = 𝑚𝐺` sulla curva originale, li mappiamo a punti corrispondenti sulla nuova curva. Dalle coordinate dei punti ottenuti è facile calcolare `𝑚`.

Il seguente codice esegue l'attacco:```python
def lift(P, E, p):
    # lift point P from old curve to a new curve
    Px, Py = map(ZZ, P.xy())
    for point in E.lift_x(Px, all=True):
         # take the matching one of the 2 points corresponding to this x on the p-adic curve
        _, y = map(ZZ, point.xy())
        if y % p == Py:
            return point


p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
      28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p

private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G

# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37]) 
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)

# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")

from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
```
In questo frammento di codice, viene definita una funzione `lift`, che riceve un punto sulla curva originale e gli fa corrispondere un punto sulla nuova curva. Poi definiamo una curva ellittica e un generatore in essa, e verifichiamo che l'ordine della curva sia effettivamente `p`. Scegliamo una chiave privata e calcoliamo la corrispondente chiave pubblica, quindi eseguiamo l'attacco. Definiamo una nuova curva sui numeri 𝑝-adici e mappiamo i punti originali `𝐺` e `𝑃` ai punti corrispondenti nella nuova curva usando la funzione `lift` e moltiplicandoli per `𝑝`.

Per ogni nuovo punto, calcoliamo il rapporto tra la coordinata `𝑥` e la coordinata `𝑦`. Il quoziente di questi due valori è la soluzione ECDLP dei punti originali.

L'output è:```
success!
The private key is: >>>>> Extraordinarily Nice <<<<<
```
Il motivo per cui questo calcolo funziona è legato al fatto che il numero di punti sulla curva è esattamente `𝑝`. Questa proprietà ci consente di eseguire diverse mappature, l'ultima delle quali mappa punti su una curva sui numeri 𝑝-adici, a numeri modulo $p^2$. Questa mappatura ha la proprietà che il rapporto tra la coppia di numeri corrispondenti ai due punti originali è esattamente il risultato del logaritmo dei due punti. Lasceremo tutte queste mappature come una scatola nera, ma alla fine dell'articolo ho aggiunto dei riferimenti alle spiegazioni matematiche pertinenti.


# Attacchi ECDSA
## Non Fare l'Hashing del Messaggio Prima di Firmarlo
Abbiamo visto che nel processo di firma di un messaggio, prima viene calcolato l'hash del messaggio, e i bit alti dell'hash vengono usati nel calcolo della firma. Supponiamo che in qualche implementazione della firma e della verifica della firma, questo passaggio di hashing venga saltato, e invece di prendere i bit alti dell'hash, i bit vengano presi dal messaggio così com'è. In una tale implementazione, l'unica parte del messaggio che influisce sulla sua firma è l'inizio del messaggio. In altre parole, se abbiamo un messaggio e la sua firma, possiamo mantenere l'inizio del messaggio e modificare il resto, e la firma rimarrà valida. È un attacco davvero semplice.


Supponiamo, ad esempio, che tu scriva il seguente messaggio alla tua banca e lo firmi senza applicare l'hash:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
```
La banca verificherà con successo questo messaggio ed eseguirà l'azione. Qualche ... attaccante ... potrebbe creare il seguente messaggio:```
"Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
```
E usa la firma che hai appena creato. La firma sarà valida anche per questo messaggio, e la banca eseguirà l'azione. Non va bene (beh, dipende da chi).

Il seguente codice dimostra l'attacco:```python
from ecdsa import SigningKey, NIST256p

signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key

class MyHash:
    def __init__(self, data):
        self.data = data

    def digest(self):
        return self.data

# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)

# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
```
In questo frammento di codice viene utilizzata la libreria `ecdsa`, insieme a una curva nota. Definiamo una classe che dovrebbe implementare una funzione hash ma non lo fa, lasciando invece il messaggio così com'è. Pertanto, quando si firma un messaggio, vengono usati solo i primi bit del messaggio originale, invece di quelli del suo hash. Il messaggio viene poi firmato e verificato con successo. Viene quindi creato un messaggio dannoso e il codice verifica che la firma del messaggio originale corrisponda anche al messaggio dannoso.

In uno scenario del genere potremmo non aver ottenuto la chiave privata per generare nuove firme nostre, ma data una firma, possiamo firmare quanti messaggi vogliamo, purché inizino con lo stesso prefisso.


## Riutilizzo dello stesso valore di `k` in firme diverse

Come parte del processo di firma del messaggio, all'utente viene richiesto di generare casualmente un valore `𝑘` e usarlo per firmare il messaggio. È molto importante usare valori `𝑘` diversi in firme diverse. Altrimenti — date due firme di messaggi in cui l'utente ha usato lo stesso valore `𝑘` invece di rigenerarlo — un attaccante potrebbe calcolare la chiave privata dell'utente.

Come accennato, durante la firma del messaggio l'utente invia pubblicamente $r=x_1\ \ \ \ (mod\ p)$ e e $s=k^{-1}(z+rd_A)$. Supponendo che l'utente abbia firmato due messaggi diversi corrispondenti a $𝑧_1$ e $𝑧_2$, e abbia inviato pubblicamente due coppie di valori $𝑟, 𝑠_1$ e $𝑟, 𝑠_2$, ovvero abbia usato lo stesso valore `𝑘` in queste due firme. Notiamo che:

$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$

Da questo, l'attaccante può trovare il valore di `𝑘` calcolando:

$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$

Dopo che l'attaccante ha trovato `𝑘`, può calcolare la chiave privata dell'utente da una delle firme. Notiamo che:

$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$

Dati i valori di `𝑟`, `𝑠` e `𝑧` di un messaggio e della sua firma, e il valore di `𝑘` trovato dall'attaccante, quest'ultimo può calcolare $d_A=r^{-1}(ks-z)$. Da questo punto, l'attaccante può firmare qualsiasi messaggio voglia, per conto dell'utente di cui ha ottenuto la chiave privata.

Il seguente frammento di codice esegue questo attacco:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long,  long_to_bytes
from hashlib import sha256
import random

# Select a curve and generator
curve = curve_256
generator = generator_256
n = generator.order()

# Create private key and public keys
secret_key = 6743529130774090927928101169617481154782309
public_key = Public_key(generator, generator * secret_key)
private_key = Private_key(public_key, secret_key)

# Sign 2 messages using the same k
k = random.randrange(curve.p())
message1 = "Life is like a box of chocolates."
message2 = "You never know what you're gonna get."
z1 = bytes_to_long(sha256(message1.encode()).digest())
z2 = bytes_to_long(sha256(message2.encode()).digest())

signature1 = private_key.sign(z1, k)
signature2 = private_key.sign(z2, k)

# Given the two messages and their signatures, find k
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n
assert k == found_k

# Given k and one of the messages, find the private key
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n
assert found_key == secret_key
print("success!")
print("The secret is:", long_to_bytes(found_key).decode())
```
In questo frammento di codice viene utilizzata la libreria `ecdsa`, insieme a una curva nota. Definiamo una chiave privata e la usiamo per firmare due messaggi. Il valore di `𝑘` viene generato casualmente, ma rimane lo stesso per le due firme. Date le due firme e i due messaggi, il codice esegue il calcolo visto in precedenza per trovare `𝑘`. Infine, usiamo il valore di `𝑘` trovato per calcolare la chiave privata come visto. L'output è:```
Success!
The secret is: Mistakes were made
```
È interessante notare che questo attacco è stato effettivamente utilizzato nel 2010, quando Sony ha implementato in modo insicuro il proprio meccanismo di firma sul software della console PlayStation. Sony utilizzava un valore statico di `𝑘` per le sue firme, il che ha permesso agli attaccanti di ottenere la chiave privata di Sony utilizzando il calcolo sopra descritto. Ciò ha portato alla possibilità di firmare qualsiasi codice e far sì che PlayStation accettasse di eseguirlo. Successivamente questa capacità è stata utilizzata per installare giochi piratati e non ufficiali sulla console.


## Generare valori `k` in modo insicuro
Se l'utente sceglie `𝑘` in modo non sufficientemente casuale, la chiave privata può essere trovata. Ad esempio, se l'attaccante sa che `𝑘` si trova in un intervallo di valori molto piccolo, o alcuni dei byte di `𝑘` sono noti all'attaccante, allora è possibile, con una semplice forza bruta, trovare la chiave privata dell'utente a partire da un singolo messaggio firmato. L'attaccante eseguirà il calcolo visto nell'attacco precedente per i diversi valori di `𝑘`, finché non raggiunge il valore corretto e ne ricava la chiave privata.

Per superare questo problema, a volte gli utenti generano casualmente un valore, ne calcolano l'hash con una funzione hash e usano il risultato come `𝑘`. Questo metodo potrebbe causare problemi. Supponiamo, ad esempio, che l'ordine del generatore `𝑛` sia `256 bit` e che la funzione hash scelta sia SHA-1. L'output di questa funzione è un numero di `160 bit`. Nei calcoli modulo `𝑛`, è noto che il valore di `𝑘` contiene 96 zeri all'inizio, il che significa che `𝑘` è un numero relativamente piccolo. In una situazione del genere, si dice che i valori di `𝑘` sono `distorti` e, dati diversi messaggi firmati con la stessa chiave privata, la chiave privata può essere trovata.

L'attacco si basa su una struttura algebrica chiamata reticolo. Informalmente, un reticolo può essere pensato come un insieme di vettori in uno spazio `𝑚`-dimensionale, che può essere espresso come combinazione lineare di vettori "base" con coefficienti interi. Matematicamente, se $`\{b_1,\dots,b_d\}`$ sono i vettori base su $ℝ^𝑚$, allora il reticolo corrispondente è $L=$ $`\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}`$. In questa struttura esiste il noto problema: data la base di un reticolo, trovare il vettore più corto che esista nel reticolo. In questo contesto, informalmente, un "vettore corto" è un vettore i cui elementi sono il più vicino possibile a zero. Questo problema è chiamato Shortest Vector Problem (SVP), ed è considerato NP-hard. Esistono algoritmi che risolvono un problema simile ma più semplice: trovare un qualche vettore corto, cioè un vettore relativamente "vicino" al vettore più corto del reticolo. Questo problema è chiamato Closest Vector Problem (CVP), e uno degli algoritmi che lo risolve è chiamato algoritmo di Lenstra-Lenstra-Lovász (LLL). In questo attacco useremo questo algoritmo come una scatola nera.

Dati `𝑑` messaggi firmati, è possibile costruire un reticolo che contiene il vettore $(𝑘_1, \dots , 𝑘_𝑑)$, dove ogni elemento del vettore è un valore `𝑘` che corrisponde a una firma. L'algoritmo LLL troverà un'approssimazione del vettore più corto in questo reticolo. Poiché è noto che i valori di `𝑘` sono piccoli, c'è un'alta probabilità che il vettore corto trovato dall'algoritmo contenga almeno un elemento `k` corretto. Una volta trovato un `𝑘` corretto, la chiave privata può essere calcolata come visto nell'attacco precedente.

Per costruire questo reticolo, occorre definire i suoi vettori base. Ho incluso nei riferimenti alla fine dell'articolo un link a un articolo che spiega come vengono definiti questi vettori base. Tecnicamente, i vettori base del reticolo possono essere rappresentati come una matrice, in cui ogni riga è composta dagli elementi di un vettore base. Per migliorare l'accuratezza dell'algoritmo LLL, si consiglia di aggiungere a questa matrice due colonne che contengono informazioni sulla dimensione attesa dei valori `𝑘` e sul rapporto tra `𝑘` e `𝑛`. Questo miglioramento è spiegato anche nel riferimento che ho allegato. Il seguente frammento di codice dimostra questo attacco:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random


def build_matrix(signatures, bias, q):
    # M matrix should be:
    """
    [
            B 0   m'1 m'2 m'2 ... m'n
            0 B/q r'1 r'2 r'3 ... r'n
            0 0
            0 0        q * I
            0 0
    ]
    where:
        m' = s^-1 * m
        r' = s^-1 * r
    """

    # Construct the first 2 rows of M:
    row1 = [bias, 0]
    row2 = [0, bias / q]
    for m, r, s in signatures:
        row1.append((inverse_mod(s, q) * m) % q)
        row2.append((inverse_mod(s, q) * r) % q)
    top_rows = Matrix(QQ, [row1, row2])

    # Construct the q*I block along with 2 columns of zeros
    zero_cols = zero_matrix(QQ, len(signatures), 2)
    qI = q * identity_matrix(QQ, len(signatures))
    bottom_rows = block_matrix([[zero_cols, qI]])

    # Combine all rows into one matrix
    M = top_rows.stack(bottom_rows)
    return M


def find_private_key(L, signatures, public_key):
    # Check if any valid k was found in L
    generator = public_key.generator
    q = generator.order()
    for row in L.rows():
        for i in range(len(signatures)):
            m,r,s = signatures[i]
            # Skip the first two vector components we used to improve LLL
            possible_k = row[i+2]
            # LLL might have swapped the sign of the found short vectors
            for k in [possible_k, -possible_k]:
                d = inverse_mod(r,q)*(k*s-m) % q
                if d*generator == public_key.point:
                    return d


# Select a curve and generator
curve = curve_256
generator = generator_256
q = int(generator_256.order())

# Create private key and public key
secret_key = 1793056234309773077862125006843383726029262764680727851636
public_key = Public_key(generator, generator * secret_key)
private_key = Private_key(public_key, secret_key)

# Sign some messages
messages_to_sign = [
    "And then I go and spoil it all",
    "By saying somethin' stupid like",
    "I love you"
]

signatures = []
for message in messages_to_sign:
    message_hash = bytes_to_long(sha1(message.encode()).digest())
    k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest())
    signature = private_key.sign(message_hash, k)
    signatures.append((message_hash, signature.r, signature.s))

# Given the messages and their signatures, retrieve the private key

# Build the matrix out of the signatures
# We know that k < 2^160 because it is the result of sha1
bias = 2^160
M = build_matrix(signatures, bias, q)

# Calculate the closest short vector
L = M.LLL()

# Find the private key!
found_key = find_private_key(L, signatures, public_key)
assert found_key == secret_key
print("success!")
print("The secret is:", long_to_bytes(found_key).decode())
```
In questo frammento di codice viene utilizzata una curva standard, viene selezionata una chiave privata e da essa viene calcolata la corrispondente chiave pubblica. Vengono creati 3 messaggi e firmati con 3 valori casuali `k` che sono il risultato della funzione hash SHA-1. Quindi creiamo la matrice corrispondente alla base del reticolo come spiegato nell'articolo ed eseguiamo su di essa l'algoritmo LLL. Successivamente, esaminiamo le righe della matrice risultante e verifichiamo se in una di esse viene trovato un valore corretto di un qualche `𝑘`.

Il controllo viene eseguito calcolando la chiave privata dal potenziale `𝑘`, come visto nell'attacco precedente, e verificando se la chiave ottenuta è effettivamente corretta. Infine, ci assicuriamo che la chiave privata trovata sia effettivamente corretta. L'output è:```
success!
The secret is: I am Jack's broken heart
```
La complessità di questo attacco è pari alla complessità dell'algoritmo LLL, che è $O(d^6\ \log^3B)$, dove `𝐵` indica la lunghezza del bias di `𝑘` ($2^{160}$
nel nostro caso), e `𝑑` indica il numero di messaggi firmati (3 nel nostro caso). Sorge la domanda su quale sia il numero minimo di messaggi firmati che siamo tenuti a utilizzare per poter eseguire l'attacco. La risposta è 
$\displaystyle d=O(\frac {\log n}{\log n-\log B})$ dove `𝑛` è l'ordine del generatore e `𝐵` è il bias. Una spiegazione di ciò appare nel secondo collegamento nei riferimenti che ho allegato a questo argomento alla fine dell'articolo.

In pratica, una variante di questo attacco può essere eseguita anche nei casi in cui sono noti i bit più significativi di `𝑘`, o semplicemente qualsiasi bit di `𝑘`. L'attacco può essere eseguito anche se è noto il valore di un solo bit, o anche se il valore di un solo bit è noto con una probabilità superiore al 50%! Ma ovviamente, in questi casi, sono necessari molti più messaggi firmati per eseguire l'attacco.

## Non verificare che il generatore sia valido

Abbiamo visto che nel processo di verifica della firma, la parte firmataria invia la coppia di valori `​𝑟` e `𝑠` alla parte verificante. Nei browser che implementano il protocollo HTTPS, ad esempio, è consuetudine inviare questa coppia di valori ​​in un certificato, che può contenere anche dati sulla curva utilizzata dalla parte firmataria. La parte verificante deve assicurarsi che i dati sulla curva trovati nel certificato corrispondano effettivamente alla curva concordata in precedenza. Se non corrispondono, può essere problematico.

Supponiamo che in una certa curva Alice abbia una chiave privata $d_A$ e una chiave pubblica $𝑃_𝐴$ ad essa corrispondente, il che significa che $𝑃_𝐴 = 𝑑_𝐴𝐺$ per il generatore `𝐺` in questa curva. Con la chiave privata $𝑑_𝐴$, Alice può firmare i propri messaggi come abbiamo visto nella definizione del protocollo ECDSA. Supponiamo che la parte verificante riceva anche il generatore `𝐺` dall'utente e non verifichi che il generatore ricevuto dall'utente sia effettivamente il generatore concordato. Un attaccante può inviare come generatore il punto che è la chiave pubblica di Alice, $𝐺^′ = 𝑃_𝐴$. L'attaccante sceglierà come chiave privata "fittizia" il valore $𝑑_𝐴^′ = 1$, e quindi è chiaro che $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. Ciò significa che l'attaccante può "dimostrare" di possedere la chiave privata che corrisponde alla chiave pubblica di Alice. Così un attaccante può creare qualsiasi messaggio desideri e calcolare per esso una coppia di valori `​𝑟` e `𝑠` nel modo usuale con $𝑑_𝐴^′$, e la firma risultante sarà verificata con successo.

Intuitivamente, nel processo di verifica della firma, la parte firmataria dimostra di essere effettivamente il "proprietario" della chiave pubblica, che in realtà è un punto di "destinazione" sulla curva. Questo perché solo il firmatario sa quanti passi compiere dal punto di partenza per raggiungere il punto di destinazione. Se la parte verificante non verifica che il punto di partenza ricevuto dall'utente sia davvero il vero punto di partenza, allora un attaccante può decidere che il punto di partenza è il punto di destinazione e che il numero di passi da compiere da esso è zero. Tutte le altre parti della verifica della firma rimangono le stesse e la firma sarà verificata con successo. Questo attacco si chiama Curveball.

Questo attacco può essere generalizzato con valori aggiuntivi. L'attaccante sceglierà un certo valore `𝑥` e calcolerà $𝐺^′ = 𝑥𝑃_𝐴$. La chiave privata fittizia sarà $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. Allora è chiaro che vale $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.

Il seguente codice dimostra l'attacco:```python
from ecdsa.ecdsa import generator_256
from Crypto.Util.number import bytes_to_long
from hashlib import sha256
import random


def hash_message(message):
    return bytes_to_long(sha256(message.encode()).digest())

def verify(public_key, G, message, r, s):
        n = G.order()
        if r < 1 or r > n - 1 or s < 1 or s > n-1:
            return False
        hash = hash_message(message)
        u1 = (hash * inverse_mod(s, n)) % n
        u2 = (r * inverse_mod(s, n)) % n
        P = u1 * G + u2 * public_key
        return P.x() % n == r

def sign(private_key, G, message):
    n = G.order()
    k = random.randrange(n)
    hash = hash_message(message)

    r = (k * G).x() % n
    s = inverse_mod(k, n) * (hash + r * private_key) % n
    return r, s


# Create private and public keys
G = generator_256
n = G.order()
private_key = random.randrange(n)
public_key = private_key * G

# Sign a message and verify it
message = "Let me be the one that shines with you"
r, s = sign(private_key, G, message)
assert verify(public_key, G, message, r, s)

# Create a fake private key and generator that match the original public key
x = random.randrange(n)
fake_G = x * public_key
fake_private_key = inverse_mod(x, n)
assert fake_private_key != private_key
assert fake_G != G

# Sign an evil message and verify it using the same public key
evil_message = "Where did I go wrong?"
r, s = sign(fake_private_key, fake_G, evil_message)
assert verify(public_key, fake_G, evil_message, r, s)
```
In questo frammento di codice scegliamo un generatore noto, una chiave privata e una chiave pubblica. Firmiamo un messaggio e ci assicuriamo che venga verificato con successo. Poi creiamo una chiave privata falsa e un generatore falso in modo che entrambi corrispondano alla chiave pubblica originale. Un messaggio malevolo viene firmato con la chiave falsa e, infine, la firma falsa viene verificata con successo con la chiave pubblica originale. Il problema di questo codice è che l'algoritmo di verifica non verifica che il generatore `𝐺` corrisponda alla chiave pubblica. Sebbene in questo attacco non abbiamo trovato la chiave privata dell'utente, un attaccante può sfruttare l'implementazione errata della verifica delle firme e creare una firma che viene verificata con successo. Tuttavia, l'attaccante non può creare firme "reali" che vengano effettivamente verificate con successo in un'implementazione corretta della verifica delle firme.

È interessante notare che questa è una vulnerabilità reale che esisteva nell'architettura Windows CryptoAPI. Nella funzione responsabile della verifica della firma di un certificato, la verifica dei parametri della curva era insufficiente, nei casi in cui questi erano inclusi nel certificato stesso. In particolare, non veniva controllato che il generatore fosse effettivamente il generatore corrispondente alla chiave pubblica. Un attaccante poteva creare certificati falsi considerati attendibili perché sembravano firmati da un'Autorità di Certificazione fidata. Questo veniva fatto aggiungendo al certificato campi malevoli relativi alla curva e scegliendo il generatore nel modo che ho descritto. La vulnerabilità è stata scoperta dall'NSA, corretta nel 2020 e ha ricevuto il numero CVE-2020-0601.

# Conclusione
## Panoramica degli attacchi ECDH
| Tipo di problema  | Il problema | L'attacco | Come funziona l'attacco | Complessità dell'attacco |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Selezione di una curva con un generatore non sicuro | L'ordine del generatore `n` è troppo piccolo | Baby-Step Giant-Step | Meet In The Middle | $𝑂(\sqrt n)$ |
| Selezione di una curva con un generatore non sicuro | L'ordine del generatore `n` è un numero liscio | Pohlig-Hellman | Scomporre `𝑛` in fattori primi, attaccare ciascuno di essi separatamente e combinare i risultati usando il Teorema Cinese del Resto | $O(\sqrt{p_{max}})$ dove $p_{max}$ è il più grande fattore primo nella scomposizione di `𝑛` |
| Selezione di una curva con un generatore non sicuro + selezione di una chiave privata non sicura | L'ordine del generatore `n` è quasi un numero liscio e la chiave privata è piccola | Pohlig-Hellman migliorato | Scomporre `𝑛` in fattori primi, scartare i fattori troppo grandi, attaccare ciascuno di essi separatamente e combinare i risultati usando il Teorema Cinese del Resto | $O(\sqrt{p_{max}})$ dove $p_{max}$ è il più grande fattore primo nella scomposizione di `𝑛` |
| Implementazione errata di ECDH | Non verificare che un punto sia sulla curva | Invalid Curve Attack | Inviare punti con ordini piccoli su curve malevole come chiave pubblica, attaccare ciascuno di essi separatamente e combinare i risultati usando il Teorema Cinese del Resto | $𝑂(𝑛_{𝑚𝑎𝑥})$ dove $𝑛_{𝑚𝑎𝑥}$ è l'ordine più grande tra gli ordini dei punti malevoli |
| Selezione non sicura dei parametri della curva | La curva è singolare | Riduzione di ECDLP a DLP | Mappare i punti in numeri in un modo che converte l'addizione dei punti in moltiplicazione di interi | $O(\sqrt{p_{max}})$ dove $p_{max}$ è il più grande fattore primo nella scomposizione di $(p-1)$ |
| Selezione non sicura dei parametri della curva | La curva è supersingolare | Riduzione di ECDLP a DLP | Mappare i punti in numeri in un modo che converte l'addizione dei punti in moltiplicazione di interi | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ dove `k` è il grado di immersione rispetto al generatore |
| Selezione non sicura dei parametri della curva | La curva è anomala | Attacco di Smart | Una serie di mappature tra punti su una curva e punti su una curva sui numeri `p-adici`, e di nuovo agli interi | $O(1)$ |


## Panoramica degli attacchi ECDSA
| Tipo di problema  | Il problema | L'attacco | Come funziona l'attacco | Complessità dell'attacco |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Implementazione errata della firma e della verifica | Non applicare l'hash al messaggio prima di firmarlo | Data una firma di un messaggio, contraffare messaggi aggiuntivi che corrispondono alla stessa firma | Mantenere il prefisso del messaggio invariato e modificare il resto | $O(1)$ |
| Uso errato dell'algoritmo di firma | Riutilizzare lo stesso valore di `k` in firme diverse | Trovare la chiave privata dell'utente | Trovare il valore di `k` e calcolare da esso la chiave privata dell'utente | $O(1)$ |
| Uso errato dell'algoritmo di firma | Generare valori di `k` in modo non sicuro | Date diverse firme di messaggi, trovare la chiave privata dell'utente | Ridurre il problema alla ricerca di un vettore corto in un reticolo, trovare il valore di `k` e calcolare da esso la chiave privata dell'utente |  $O(d^6\ \log^3B)$ dove `B` è il bias di `k` e `d` è il numero di messaggi firmati |
| Implementazione errata della verifica | Non verificare che il generatore sia valido | Contraffare firme che vengono verificate con successo (Curveball) | Selezionare un generatore e una chiave privata falsi che corrispondono alla chiave pubblica di un altro utente | $O(1)$ |


## Protezione contro questi attacchi
Va notato che in ECDH, entrambe le parti devono concordare la curva all'inizio del protocollo. Se un utente sta comunicando con un attaccante e l'attaccante è colui che fornisce i parametri della curva, allora l'attaccante può fornire parametri non sicuri. Di conseguenza, l'attaccante può ottenere la chiave privata dell'utente. Se l'utente usa sempre la stessa chiave privata, allora l'attaccante può decifrare tutte le conversazioni tra quell'utente e qualsiasi altro utente. Ecco perché è molto importante non permettere a utenti sconosciuti di fornire i parametri della curva se non sono considerati affidabili. Oltre a questo, bisogna assicurarsi che ogni punto ricevuto da un utente esterno sia effettivamente sulla curva concordata. E, naturalmente, bisogna assicurarsi che la curva selezionata stessa non sia vulnerabile a uno degli attacchi noti che abbiamo visto. Inoltre, è meglio usare una nuova chiave privata ogni volta che si utilizza il protocollo ECDH.

Analogamente, in ECDSA, bisogna prestare attenzione a implementare correttamente gli algoritmi di firma e verifica. Non saltare l'hash del messaggio, la generazione casuale e sicura del valore `𝑘` ogni volta che il protocollo viene utilizzato e, naturalmente, nella verifica della firma, se il generatore viene ricevuto dall'utente - assicurarsi che sia effettivamente quello concordato in precedenza.

## Riferimenti
- In questo articolo ho usato grafici dal libro Understanding Cryptography di Christof
paar:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf


- Un sito che illustra l'aspetto delle curve ellittiche crittografiche:\
https://graui.de/code/elliptic2/

- Spiegazione dettagliata delle operazioni di addizione e moltiplicazione nelle curve ellittiche:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

- Lezione introduttiva sulle curve ellittiche e sull'addizione dei punti - di Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ

- Lezione su generatori, ECDLP, difficoltà dei problemi, ECDH, Double And Add - di Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY

- Spiegazione del livello di sicurezza di diversi algoritmi di crittografia:\
https://en.wikipedia.org/wiki/Security_level

- Spiegazione di ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman

- Spiegazione di ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

- Spiegazione delle firme con ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme

- Spiegazione del Teorema Cinese del Resto:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem

- Spiegazione della relazione tra il discriminante di una curva singolare e il fatto che abbia una radice doppia:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity

- Un esempio con numeri piccoli della mappatura tra punti e numeri nelle curve singolari:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434

- Spiegazioni dei numeri 𝑝-adici:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA

- Spiegazione della matematica alla base dell'attacco MOV:\
https://risencrypto.github.io/WeilMOV/

- Spiegazioni della matematica alla base dell'attacco di Smart (è piuttosto complicato, siete stati avvertiti):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf

- Spiegazione dell'attacco basato sui reticoli e dell'algoritmo LLL:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
L'attacco si basa sulla parte 4 di un articolo di Joachim Breitner e Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf

- Spiegazione del problema CVP:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)

- Spiegazione dell'algoritmo LLL:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm