cerca
El Gamal
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

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_^ = 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