La firma digitale è un metodo matematico volto a dimostrare l’autenticità di un messaggio, oppure di un documento digitale, scambiato tra un mittente ed un destinatario attraverso un sistema di comunicazione non sicuro. La firma digitale viene spesso utilizzata per certificare l’autenticità del mittente del messaggio e per garantire la non manomissione di quest’ultimo. Presentiamo di seguito due algoritmi che permettono di eseguire la firma digitale di un documento: RSA e ElGamal

Firmare con RSA

Supponiamo che Bob possegga un contratto e che sia interessato a farlo sottoscrivere ad Alice. Da una parte Bob vuole essere sicuro che Alice firmi il contratto, dall’altro Alice vuole essere tutelata dalle future modifiche che potrebbero essere apportate al contratto sottoscritto. Utilizzando la firma digitale con ElGamal entrambi possono raggiungere il loro obiettivo.

Alice scegliere due numeri interi primi p e q e ottiene in numero n :
n = p \cdot q

Successivamente sceglie il numero e co-primo con \phi(n) :
\text{MCD}(e, \phi(n)) = 1

Ricordiamo che per il teorema di Eulero:
\phi(n) = (p-1) \cdot (q-1)

Infine, calcola il valore d , inverso moltiplicativo di e :
d \cdot e = 1 \pmod{\phi(n)}

Per firmare il documento Alice dovrà calcolare:
y = m^d \pmod{n}

Alice consegna a Bob la chiave (m, y) e (e, n) come prova della sua firma. Se Bob volesse controllare la firma dovrebbe ricalcolare il messaggio m e successivamente confrontarlo con quello in suo possesso:
m_1 = y^e
m_1 = m

Supponiamo che EVA voglia modificare il contratto e falsificare la firma di Alice, essa non potrebbe calcolare il valore y in quanto non sarebbe in possesso del valore d . Per trovare il valore d EVA dovrebbe fattorizzare n , tuttavia questo problema è computazionalmente intrattabile.