Crittografia

L'algortimo ElGamal

Ecco come si costruisce l'algoritmo a chiave pubblica ElGamal.L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

ElGamal

Ricevente

scelta di:  - p         grosso numero primo

               - a         generatore del gruppo moltiplicativo Z_p* degli interi modulo p

               - X_B        numero casuale

chiave pubblica del ricevente: (Y_B, p, a)                       dove    Y_B = a^X_B mod p

chiave privata del ricevente: X_B

Mittente

scelta di K’ (numero casuale tale che ) da distruggere dopo l’uso

costruzione della chiave            K=Y_B^K’  mod p

crittogramma                           C = {C₁, C₂}               dove    C₁ =  a^K     mod p

                                                                                              C₂ = K M  mod p     (M è il messaggio)

Ricevente

estrazione della chiave  K = C₁^X_B  mod p = a^{K’ X}_B  mod p

recupero di M messaggio         M = C₂ K^-1 mod p

Il modulo p è raccomandato essere almeno di 768 bit, e per sicurezza a lungo termine l’uso di 1024 bit. Il generatore a del gruppo moltiplicativo Z_p* appartiene al campo di Galois GF(p), cioè il campo degli interi modulo p, con p numero primo, ma può appartenere ad altri gruppi definiti su altri campi, come i polinomi GF(2^m), come il campo dei punti appartenenti a curve ellittiche oppure alle funzioni Lucas (polinomi speciali nel campo intero)(*)

---

(*)  Al momento i migliori algoritmi per risolvere il problema sono divisi in due classi: il metodo di calcolo dell’indice (index calculus method) ed il metodo della ricerca di collisioni (collision search method); il primo sfrutta alcune proprietà matematiche specifiche (che ad esempio sono assenti nei gruppi di curve ellittiche) ed è molto veloce, mentre il secondo è molto più generale ma più lento (tempo esponenziale). Il miglior metodo a ricerca di collisione è noto come il metodo Pollard rho, perché l’algoritmo produce una sfilza di numeri che graficamente si rappresentano la lettera greca rho, formata da una coda e un circolo; l’obiettivo è capire dove il circolo incontra la coda della lettera. Questo metodo funziona per un tempo , o più precisamente   passi, dove n è la grandezza del gruppo; pubblicamente, il gruppo più grande risolto è n~2¹⁰⁹.

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• L'indice della tesi
• L'algoritmo ElGamal
• Schema di firma con ElGamal
• Classi d'algoritmi a chiave pubblica