:: El Gamal ::
Torna alla pagina di Crittografia
Che cos'č
El Gamal č un algoritmo di cifratura asimmetrica che si basa sull'intrattabilitā del logaritmo discreto.
Generazione dei parametri
p č un numero primo
g č un generatore di Zp^'*'^
α č un numero casuale, α < p - 1
β = gα mod p
Chiave privata: p, g, α.
Chiave pubblica: p, g, β.
Come funziona
Bob vuole mandare il messaggio M ad Alice, e sfrutta la chiave pubblica di Alice, ovvero p, g e β.
- sceglie un valore k casuale, k < p - 1
- genera due valori: y^_1_^ e y^_2_^
- y^_1_^ = gk mod p
- y^_2_^ = (βk * M) mod p
Invia quindi ad Alice i valori y1 e y2.
Alice, per decrittografare, fa le seguenti operazioni:
- z = y1α mod p
- M = z-1 * y2 mod p
Secondo voi non funziona? Beh, provate per credere!:)
Esempio
p = 11
g = 6
α = 3
Quanto vale β? Beh, β = gα = 63 = 7 mod 11.
Quindi:
Chiave privata: p = 11, g = 6, α = 3
Chiave pubblica: p = 11, g = 6, β = 7
Ora, Bob vuole crittografare il messaggio M = 8 per inviarlo ad Alice:
- sceglie un k casuale: k = 2 < (11 - 1)
- y1 = gk = 6 2 = 3 mod 11
- y2 = M * βk = 8 * 72 = 8 * 5 = 40 = 7 mod 11
Alice vuole decifrare:
- z = y1α = 33 = 27 = 5 mod 11
- z-1 = 9 mod 11. Infatti, 5 * 9 = 45 = 1 mod 11
- M = z-1 * y2 = 9 * 7 = 63 = 8 mod 11
Torna alla pagina di Crittografia
