Guide

ElGamal
Ricevente

scelta di:&#nbsp; - p&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; grosso numero primo

&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; &#nbsp;&#nbsp; - a&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;generatore del gruppo moltiplicativo Zp* degli interi modulo p

&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; &#nbsp;&#nbsp; - XB&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; numero casuale

chiave pubblica del ricevente: (YB, p, a)&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; dove&#nbsp;&#nbsp;&#nbsp; 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 &#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; K=YBK’ &#nbsp;mod p

crittogramma &#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; C = {C1, C2}&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; dove&#nbsp;&#nbsp;&#nbsp; C1 =&#nbsp; aK&#nbsp;&#nbsp;&#nbsp;&#nbsp; mod p

&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; C2 = K M&#nbsp; mod p&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;(M è il messaggio)

Ricevente

estrazione della chiave&#nbsp; K = C1XB &#nbsp;mod p = aK’ XB&#nbsp; mod p

recupero di M messaggio&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp;&#nbsp; 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)(*)

(*)&#nbsp; 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 &#nbsp;&#nbsp;passi, dove n è la grandezza del gruppo; pubblicamente, il gruppo più grande risolto è n~2109.