Elgamal

Corso di Sicurezza – A.A. 2006/07

Angeli Fabio 29/05/2007

Caratteristiche

• Descritto da Taher Elgamal nel 1984.• Sistema di cifratura a chiave pubblica.• Asimettrico (utilizza chiavi diverse per

codifica e decodifica).• Sicurezza basata sul problema di Diffie-

Hellman il quale a sua volta basa la propria sicurezza sulla complessità computazionale del calcolo del logaritmo discreto.

Aritmetica Finita (1)

Si definisce aritmetica finita un'aritmetica che opera su un insieme limitato di numeri. È detta anche aritmetica modulare o circolare, in quanto una volta raggiunto l'ultimo numero si ricomincia dal primo.In generale un'aritmetica finita modulo m si basa sull'insieme {0,1,2...m-1}; questi numeri possono anche vedersi come i possibili resti di una divisione per m.Esempio: in modulo 24 , 11*3 = 9 perchè 11*3 = 33 e 33 mod 24 = 9.

Aritmetica Finita (2)

• Z l'insieme dei numeri interi.• Zp l'insieme dei numeri interi tra 0 e p-1 compresi, ovvero l'insieme {0, …, p-1}. • Z*p il sottoinsieme di Zp comprendente solo i numeri primi rispetto a p. Se p è un numero primo allora Z*p={0, …, p-1}.• g si dice elemento generatore di un campo se partendo da g si possono ottenere tutti i suoi elementi.Esempio: Z7 generabile a partire da 3 oppure da 5.

31=3 32=2 33=6 34=4 35=5 36=1

Logaritmo Discreto (1)

In aritmetica finita, la potenza di un numero si definisce come:

ab = x mod n

e come per l'aritmetica ordinaria possiamo stabilire un'operazione inversa rispetto all'esponente, cioè il logaritmo discreto:

b = loga x mod n

Logaritmo Discreto (2)

Se il calcolo della potenza è semplice, il calcolo del logaritmo è computazionalmente molto complesso, può avere più soluzioni o anche nessuna. Ad esempio in un'aritmetica di ordine 7 si avrebbe:

20 = 1 21 = 2 22 = 4 23 = 124 = 2 25 = 4 26 = 1

perciò se prendiamo il log2 4 è 2 ma anche 5, non esistono però log2 3, log2 5, log2 6.Anche se non è stato ancora dimostrato, si pensa che la difficoltà computazionale del logaritmo discreto è dello stesso ordine di quella della fattorizzazione.

Diffie-Hellman (1)

Descritto da Whitfield Diffie e Martin Hellman nel 1976.

Il protocollo di Diffie-Hellman permette a due interlocutori che non hanno mai avuto nessun precedente contatto di accordarsi su una chiave segreta utilizzando un canale pubblico.

Diffie-Hellman (2)

1. Bob e Alice si accordano pubblicamente su un numero primo p e su un numero g che sia elemento generatore di Z*p.

2. Alice sceglie un numero a tale che 0 < a < p-1, calcola A = ga mod p e lo manda a Bob.

3. Bob sceglie un numero b tale che 0 < b < p-1, calcola B = gb mod p e lo manda ad Alice.

4. La chiave segreta è K = gab mod p: Alice può calcolarla come K = Ba mod p, mentre Bob può calcolarla come K = Ab mod p.

Diffie-Hellman (3)

Diffie-Hellman (4)

La sicurezza del protocollo si basa sul fatto che un estraneo non possa calcolare K partendo da ciò che viaggia in chiaro sulla rete: g, p, A, B. Essendo:

A = ga mod p e B = gb mod pRicavare a o b equivale a saper risolvere il problema del logaritmo discreto infatti:

a = logg A mod p e b = logg B mod pCosì com'è, ovvero senza alcuna forma di autenticazione come ad esempio dei certificati, è però soggetto ad un attacco di tipo man-in-the-middle.

Elgamal (1)

RiceventeSceglie:• Un grosso numero primo p.• g generatore di Z*p .• b numero casuale.Chiave pubblica del ricevente: (B, p, g) dove B = gb mod p.Chiave privata del ricevente: (b).

Elgamal (2)

Mittente

Sceglie k numero casuale tale che 0 < k < p.

Costruisce la chiave K = Bk mod p.

Crittogramma C = (C1,C2) dove:

C1 = gk mod p.

C2 = K * m mod p (m è il messaggio da cifrare).

Elgamal (3)

Ricevente

Ricava K da C1:

K = Bk mod p = gkb mod p = C1b mod p.

Recupera m da C2:

m = K-1 * C2 mod p.

Per fare tutto in un’unica espressione:

m = C1-b*C2(ricordandosi che C1-b = C1p-1-b)

Elgamal (4)

• p è raccomandato essere almeno di 768 bit, e per sicurezza a lungo termine l’uso di 1024 bit.

• Il generatore g del gruppo moltiplicativo Z*p 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).

Elgamal (4)

Esempio con numeri piccoli:Generazione delle chiavi: il ricevente sceglie il numero primo p = 2357, il generatore di Z*2357 g = 2, la chiave privata b = 1751 e calcola:

B = gb mod p = 21751 mod 2357 = 1185.Criptazione: per criptare il messaggio m = 2035, il mittente sceglie il numero casuale k = 1520 e calcola:

C1 = gk mod p = 21520 mod 2357 = 1430.C2 = m * K mod p = 2035 * 11851520 mod 2357 = 697.

Decriptazione: Il ricevente calcola:C1-b = C1p−1−b = 1430605 mod 2357 = 872.

m = C1-b * C2 = 872 * 697 mod 2357 = 2035.

Elgamal (5)

Pro:• Utilizzando un numero k casuale ogni volta anche crittografando lo stesso messaggio più volte si ottengono crittogrammi diversi.Contro:• Lento (rispetto ad RSA) 2 esponenziali per criptare ed uno per decriptare.• Crittogramma di lunghezza doppia.• Elgamal è malleabile: ad esempio dato un crittogramma (C1,C2) corrispondente al messaggio m, è possibile costruire facilmente un crittogramma (C1, 2 * C2) corrispondente al messaggio 2 * m. (Soluzione utilizzare Cramer-Shoup)

Cramer-Shoup

• Descritto da Ronald Cramer e Victor Shoup nel 1998.

• Algoritmo a chiave pubblica asimettrico.• E’ un estensione di Elgamal.• Al contrario di Elgamal non è malleabile grazie

all’utilizzo di una funzione hash resistente alle collisioni e ad altri calcoli aggiunti che portano la lungezza del crittogramma ad essere il doppio più lunga rispetto ad Elgamal.

Elgamal (6)

• Se m è troppo grande deve essere spezzato.• Utilizzo principale: scambio chiave per un algoritmo a chiave simmetrica (tecnica ibrida).• Esempi di utilizzo: GNU Privacy Guard e nelle più recenti versioni di PGP.• Elgamal ha anche descritto un algoritmo per la firma digitale, ma è inutilizzato perché gli si preferisce una sua variante sviluppata dalla National Security Agency il DSA (Digital Signature Algorithm).

Riferimenti

• T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”

• W. Diffie e M. Hellman, “New directions in cryptography”• R. Cramer e V. Shoup, “A practical public key

cryptosystem provably secure against adaptive chosen ciphertext attack”

• A. Menezes, P. van Oorschot e S. Vanstone, “Handbook of Applied Cryptography”, http://www.cacr.math.uwaterloo.ca/hac/

• Discrete logarithm calculator, http://www.alpertron.com.ar/dilog.htm

• http://www.wikipedia.org