Guide

ElGamal
Ricevente

scelta di:  - p         grosso numero primo

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

               - XB        numero casuale

chiave pubblica del ricevente: (YB, p, a)                       dove    YB = aXB mod p

chiave privata del ricevente: XB

Mittente

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

costruzione della chiave            K=YBK’  mod p

crittogramma                           C = {C1, C2}               dove    C1 =  aK     mod p

                                                                                              C2 = K M  mod p     (M è il messaggio)

Ricevente

estrazione della chiave  K = C1XB  mod p = aK’ XB  mod p

recupero di M messaggio         M = C2 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 Zp* 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(2m), 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~2109.