Il modulo: strumento per test di primalità e crittografia

I test di primalità sono spesso una combinazione di due tecniche:
- evidenziano rapidamente se un numero è composto
- se non è composto devono avere un algoritmo rapido di primalità: deterministico (AKS, Lehmer, etc) o
  probabilistico (Miller-Rabin, Fermat, etc) 

Oggi la "grande sfida numerica" per gli sviluppatori, i matematici e chi si interessa di hardware per tali tipi di problemi (primalità), è realizzare hw e/o algoritmi più efficienti di quelli disponibili, anche attraverso lo sviluppo di nuovi Teoremi di Teoria dei numeri. 

E' noto che per verificare la primalità di un numero primo o anche per generare le chiavi pubbliche e private
(vedi RSA) nella crittografia, si fa uso dell'operatore aritmetico modulo, che restituisce il resto della divisione intera.

Ad esempio nel Piccolo Teorema di Fermat è noto che "se a^p-1 mod p = 1 mod p allora p è primo. Per evitare i numeri di Carmichel si testa per diverse basi per cui si individua un numero che molto probabilmente è primo.

Il problema che nasce è che se p-1 è un numero molto elevato a^p-1 mod p richiede un tempo notevole di calcolo.

Per tale motivo si usano "tecniche di riduzione" per velocizzare il calcolo, effetto che si nota soprattutto se il numero è di "grandissime dimensioni".

Se ad esempio a=2345 b=2345678 c=341   allora a^b mod c si può sostituire con a^c mod b. Se questo è conveniente perchè adesso l'esponente è minore, col Piccolo Teorema di Fermat non è conveniente; difatti da a^p-1 mod p si passa a  a^p mod p-1 come l'algoritmo che segue (ma  abbiamo peggiorato le cose sostituendo p-1 con p):

/*
** Simple Method
*/
pMod(base,exponent,modulus)= local(ret=1); {    
ret = lift(Mod(base, modulus)^exponent);
return(ret);
}


Un'altra possibilità, se l'esponente è troppo grande, in Mod(a,N)^n è di usare una riduazione del tipo Mod(n, phi(N)), dove phi(N) è la funzione totiente di Eulero.

Una modalità più efficiente è di lavorare con gli esponenti in binario ( tra l'altro sono possibili creazioni
di processori che lavorano in questo modo): tale tecnica è nota come "exponentiation squaring", proposta
da Bruce Schneier nel suo Applied Cryptography, 2e, ISBN 0471117099. Questo metodo richiede un tempo costante indipendente dall'input, si dice che è a complessità lineare.

/*
**  Fast Mod Exp: exponentiation by squaring
**
**  Concrete implementation by R. Turco
*/
ModExp(base,exponent, modulus) = local(ret=1,i=1); {  
 b = binary(exponent);  
 i = length(b);
 while(exponent>0 & i>0,        
        if(b[i]==1,            
           ret = lift(Mod((ret * base), modulus));        
        );
        exponent = exponent >> 1; 
        base = lift(Mod((base * base), modulus));       
        i--;   
 );   
 return(ret);
}

La tecnica mette insieme anche l'altra tecnica dello "Square e Multiply" che vediamo di seguito, anche questa con esponenziazione binaria:

/*
** Square & Multiply
** 
*/
SqMod(base,exponent,modulus)= local(residue=1); {   
 b = binary(exponent);  
 len = length(b); 
 for(i=1,len,
      residue=(lift(Mod(residue,modulus)^2)*(base^b[i])) % modulus;
 );
 return(residue);

}

Lo square & multiply, usato nel RSA o altri come AES per le chiavi, potrebbe essere soggetto ad attacchi furbi per il crack delle chiavi stesse.

Esistono anche altri algoritmi basati sulla tecnica "Montgomery reduction" e varianti come la "Barrett’s reduction" che usano un pre-processing e che sono interessanti per la produzione di HW ad hoc (sia basati sul binario ma preferibilmente sulle word). La "Montgomery reduction" è possibile anche sulle curve ellittiche GF(2^k).

Riferimenti
http://en.wikipedia.org/wiki/Montgomery_reduction
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/RSA
http://www.it.uu.se/edu/course/homepage/security/vt09/labs/lab2

Propri lavori su tecniche di primalità
http://www.gruppoeratostene.com/articoli/PrimTech.pdf
http://www.gruppoeratostene.com/articoli/Rtc2009.pdf
http://www.gruppoeratostene.com/articoli/PDC.pdf
http://www.gruppoeratostene.com/articoli/Mersenne.pdf
http://www.gruppoeratostene.com/articoli/Rtac.pdf

Implementazioni Software
http://www.gruppoeratostene.com/programmi/programmi.htm