Swappa : Uni / El Gamal

 :: 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_^ = g^k mod p
  • y^_2_^ = (β^k * M) mod p

Invia quindi ad Alice i valori y₁ e y₂.

Alice, per decrittografare, fa le seguenti operazioni:

• z = y₁^α mod p
• M = z^-1 * y₂ mod p

Secondo voi non funziona? Beh, provate per credere!:)

Esempio

 p = 11
 g = 6
 α = 3

Quanto vale β? Beh, β = g^α = 6³ = 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)
• y₁ = g^k = 6 ² = 3 mod 11
• y₂ = M * β^k = 8 * 7² = 8 * 5 = 40 = 7 mod 11

Alice vuole decifrare:

• z = y₁^α = 3³ = 27 = 5 mod 11
• z^-1 = 9 mod 11. Infatti, 5 * 9 = 45 = 1 mod 11
• M = z^-1 * y₂ = 9 * 7 = 63 = 8 mod 11

Torna alla pagina di Crittografia