Timing Attack ad RSA

Moltiplicazione di Montgomery.

L’algoritmo di Montgomery permette di fare il calcolo veloce della moltiplicazione fra numeri rappresentati con un numero elevato di bit. In particolare va a sfruttare alcune proprietà dell’algebra modulare per velocizzare al massimo questa operazione. Il problema in questione si riconduce al calcolo della seguente quantità:

ab mod n (8.1)

Questa operazione, essendo a,b,n numeri molto grandi (dell’ordine di 1024 bit) è piuttosto dispendiosa e, dato che viene eseguita più volte negli algoritmi di crittografia a chiave pubblica, si cerca di ricondurla in una forma più snella.

Ovvero l’algoritmo di Montgomery permette il calcolo della seguente quantità:

MonPro(a,b) = a b r^-1 mod n (8.2)

E’ necessario scegliere un numero r maggiore di n in modo tale che i due numeri siano primi fra loro. Di conseguenza, il massimo comune divisore deve essere uguale ad 1 (gcd(n,r)=1). La scelta di questo parametro può essere fatta in modo tale che si semplifichino le operazioni che si dovranno compiere. Di conseguenza, si sceglie come r il numero potenza di 2 (r = 2^k) tale che valga la seguente disuguaglianza .

In questo modo, le divisioni per r diventano semplici shift, mentre i moduli diventano delle semplici maschere. Infatti, per quanto riguarda il modulo si ha:

f mod r = f ^ (r-1)    (8.3)

(Es. 27 mod 8 = 3 espresso in binario 27=11011 8=1000 per cui si vede che 27&7=11011&00111=3    27 mod 8 = 27 & 7 = 3).