Diffie-Hellman [1976] Diffie-Hellman [1976] Generatori Z Accordo su una chiave Diffie-Hellman [1976]

Diffie-Hellman 0

Accordo su una chiave

iagio

… …

…

K K K K K

K

?? ??

nnarella

Diffie-Hellman 1

Diffie-Hellman [1976]

primo p, generatore g di Z_p^*

?? ??

nnarella

Diffie-Hellman 2

Generatori

2¹⁰= 1024 = 1 mod 11

2¹ = 2 mod 11

2⁸= 256 = 3 mod 11

2² = 4 mod 11

2⁴= 16 = 5 mod 11 2⁹= 512 = 6 mod 11 2⁷= 128 = 7 mod 11

2³ = 8 mod 11

2⁶= 64 = 9 mod 11 2⁵= 32 = 10 mod 11 g è generatore di Z_p^*se {gⁱ|1≤i≤ p-1} = Z_p^* g è generatore di Z_p^*se {gⁱ|1≤i≤ p-1} = Z_p^*

g = 2 è un generatore diZ₁₁^* g = 2 è un generatore diZ₁₁^* Esempio:

Diffie-Hellman 3

Potenze in Z

1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18

1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17

1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16

1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15

1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14

1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13

1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12

1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11

1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10

1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9

1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8

1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7

1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6

1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5

1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4

1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3

1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

a¹⁸ a¹⁷ a¹⁶ a¹⁵ a¹⁴ a¹³ a¹² a¹¹ a¹⁰ a⁹ a⁸ a⁷ a⁶ a⁵ a⁴ a³ a² a

Diffie-Hellman [1976]

?? ??

scelgo y scelgo y scelgo y scelgo x

scelgo x scelgo x

iagio nnarella

primo p, generatore g

Diffie-Hellman [1976]

?? ??

g g^xxmod pmod p

scelgo y scelgo y scelgo y scelgo x

scelgo x scelgo x

iagio nnarella

primo p, generatore g

Diffie-Hellman 6

Diffie-Hellman [1976]

?? ??

gg^xxmod mod pp g g^yymod mod pp

scelgo y scelgo y scelgo y scelgo x

scelgo x scelgo x

iagio nnarella

primo p, generatore g

Diffie-Hellman 7

Diffie-Hellman [1976]

K = g^xymod p

= (g^y)^xmod p K = gK = g^xyxymodmodpp

= (

= (gg^yy))^xxmodmodpp

?? ??

gg^xxmod pmod p g g^yymod pmod p

scelgo y scelgo y scelgo y scelgo x

scelgo x scelgo x

iagio nnarella

primo p, generatore g

K = g^xymod p

= (g^x)^ymod p K = K = gg^xyxymodmodpp

= (

= (gg^xx))^yymodmodpp

Diffie-Hellman 8

Diffie-Hellman:

esempio

primo 11, generatore 2

K=4=2^3·4mod 11

= 5³mod 11 K=4=2

K=4=2^3·43·4modmod1111

= 5

= 5³³modmod1111

?? ??

8 = 2

8 = 2³³mod 11mod 11 5 = 2

5 = 2⁴⁴mod mod 1111

scelgo y=4 scelgo y=4 scelgo y=4 scelgo x=3

scelgo x=3 scelgo x=3

iagio nnarella

K=4=2^3·4mod 11

= 8⁴mod 11 K=4=2

K=4=2^3·43·4modmod1111

= 8

= 8⁴⁴modmod1111

Diffie-Hellman 9

Esercizio

Svolgere “piccolo” esempio Diffie-Hellman –Utilizzare p = 19

–Calcolo di g –Calcolo di x ed y

–Calcolo messaggi scambiati (gg^xxmodmod19, g19, g^yymodmod19)19) –Calcolo della chiave K

Diffie-Hellman 10

Dati a,n,b calcolare x tale che a^x= b mod n Dati a,n,b calcolare x tale che a^x= b mod n

Logaritmo discreto

‰ Esempio: 3^x= 7 mod 13 soluzione x = 6

‰ Se n è primo, i migliori algoritmi hanno complessità

L_n[a,c] = O(e(c+o(1))(ln n)^a(lnln n)^1-a)

con c > 0 ed 0 < a < 1

‰ Miglior algoritmo: Number field sieve tempo medio euristico Ln[1/3, 1.923]

Diffie-Hellman 11

Logaritmo discreto

La sicurezza di molte tecniche

crittografiche si basa sulla intrattabilità del logaritmo discreto:

‰Accordo su chiavi di Diffie-Hellman

‰Crittosistema di El-Gamal

‰Firme digitali di El-Gamal e DSS

‰…

Diffie-Hellman 12

Problema di Diffie-Hellman

Il miglior algoritmo conosciuto calcola prima il logaritmo discreto x ← log_g,p(g^xmod p)

Input: primo p, generatore g, g^xmod p, g^ymod p Calcolare: g^xymod p

Input: primo p, generatore g, g^xmod p, g^ymod p Calcolare: g^xymod p

… ma non si sa se sono equivalenti!

Diffie-Hellman 13

Generatori di Z

‰ Zn*ha un generatore ⇔ n = 2,4,p^k,2p^k, con p primo e k≥1 – In particolare, se p è primo, allora Zp* ha un generatore

‰ Se α è un generatore di Z_n*, allora – Zn* = {αⁱmod n | 0 ≤ i ≤ φ(n)-1}

– b = αⁱmod n è un generatore di Zn* ⇔gcd(i,φ(n))=1 – il numero di generatori in Zn* è φ(φ(n)).

Teorema di Eulero x∈Zn* ⇒x^φ(n)=1 mod n

‰ Ordine di α∈Z_n^*= il più piccolo intero positivo r tale che α^r = 1 mod n

‰ α è generatore di Z_n^*se ha ordine φ(n)

Diffie-Hellman 14

Potenze in Z

1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18

1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17

1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16

1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15

1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14

1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13

1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12

1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11

1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10

1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9

1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8

1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7

1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6

1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5

1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4

1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3

1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

a¹⁸ a¹⁷ a¹⁶ a¹⁵ a¹⁴ a¹³ a¹² a¹¹ a¹⁰ a⁹ a⁸ a⁷ a⁶ a⁵ a⁴ a³ a² a

Diffie-Hellman 15

Scelta di un generatore

‰ p primo, p -1 = p₁^e1 p₂^e1… p_k^ek

α^(p-1)/p1≠1 mod p

‰ αè un generatore di Zp*⇔ ^...

α^(p-1)/pk≠1 mod p

‰ 11 primo, p-1 = 10 = 2·5 Esempio

‰ 2 è un generatore di Z₁₁^*perché 2^(11-1)/2= 2⁵ = 10 ≠ 1 mod 11 2^(11-1)/5= 2²= 4 ≠ 1 mod 11

‰ 11 primo, p-1 = 10 = 2·5 EsempioEsempio

‰ 2 è un generatore di Z₁₁^*perché 2^(11-1)/2= 2⁵ = 10 ≠ 1 mod 11 2^(11-1)/5= 2²= 4 ≠ 1 mod 11

Scelta di un generatore

‰ p primo, p -1 = p₁^e1 p₂^e1… p_k^ek

α^(p-1)/p1≠1 mod p

‰ αè un generatore di Z_p^*⇔ ^...

α^(p-1)/pk≠1 mod p

‰ 11 primo, p-1 = 10 = 2·5 Esempio

‰ 3 non è un generatore di Z₁₁^*perché 3^(11-1)/2= 3⁵ = 243 = 1 mod 11 3^(11-1)/5= 3²= 9 ≠ 1 mod 11

‰ 11 primo, p-1 = 10 = 2·5 EsempioEsempio

‰ 3 non è un generatore di Z₁₁^*perché 3^(11-1)/2= 3⁵ = 243 = 1 mod 11 3^(11-1)/5= 3²= 9 ≠ 1 mod 11

Scelta di un generatore

‰ p primo, p -1 = p₁^e1 p₂^e1… p_k^ek

α^(p-1)/p1≠1 mod p

‰ αè un generatore di Z_p^*⇔ ^...

α^(p-1)/pk≠1 mod p

Diffie-Hellman 18

Scelta di un generatore

‰ p primo, p -1 = p₁^e1 p₂^e1… p_k^ek

α^(p-1)/p1≠1 mod p

‰ αè un generatore di Z_p^*⇔ ^...

α^(p-1)/pk≠1 mod p

Scegli_generatore( p, (p₁,e₁,p₂,e₂,…,p_k,e_k) ) 1. α ← elemento scelto a caso in Z_p^*

2. if (α^(p-1)/p1 ≠1 mod p and … andα^(p-1)/pk≠1 mod p) then esci

else go to 1.

Scegli_generatore( p, (p₁,e₁,p₂,e₂,…,p_k,e_k) ) 1. α ← elemento scelto a caso in Z_p^*

2. if (α^(p-1)/p1 ≠1 mod p and … andα^(p-1)/pk≠1 mod p) then esci

else go to 1. trovato!trovato!

Diffie-Hellman 19

Probabilità successo singola iterazione

 Numero di generatori modulo un primo p è φ(φ(p)) = φ(p -1)

> (p -1) /(6 ·lnln(p-1))

per ogni intero n≥5, φ(n) > n/(6lnln n) per ogni intero n≥5, φ(n) > n/(6lnln n)

Diffie-Hellman 20

Probabilità successo singola iterazione

Numero di generatori modulo un primo p è φ(φ(p)) = φ(p -1)

> (p -1) /(6 ·lnln(p-1))

Probabilità che un elemento a caso in Z_p^*sia generatore φ(φ(p)) p -1 1

= > =φ(p) φ(p) 6 ·lnln(p -1) 6 ·lnln(p -1) per ogni intero n≥5,

φ(n) > n/(6lnln n) per ogni intero n≥5, φ(n) > n/(6lnln n)

Diffie-Hellman 21

Analisi di

Numero medio di iterazioni < 6 ·lnln(p -1)

512 bit 6 ·lnln(2⁵¹²) ≈ 35,23 1024 bit 6 ·lnln(2¹⁰²⁴) ≈ 39,38 2048 bit 6 ·lnln(2²⁰⁴⁸) ≈ 43,54 512 bit 6 ·lnln(2⁵¹²) ≈ 35,23 1024 bit 6 ·lnln(2¹⁰²⁴) ≈ 39,38 2048 bit 6 ·lnln(2²⁰⁴⁸) ≈ 43,54

Diffie-Hellman 22

Generazione chiavi Diffie-Hellman

1. Scegli a caso 2 numeri primi p1 p2

2. p ← 1 + 2p₁p₂

3. Se p non è primo, go to 1.

4. g ← Scegli_generatore(p,(2,1,p1,1,p2 ,1)) 1. Scegli a caso 2 numeri primi p1 p2

2. p ← 1 + 2p₁p₂

3. Se p non è primo, go to 1.

4. g ← Scegli_generatore(p,(2,1,p₁,1,p₂ ,1))

Diffie-Hellman 23

Esercizio

Svolgere “piccolo” esempio Diffie-Hellman –Calcolo di p e g

–Calcolo di x ed y

–Calcolo messaggi scambiati (gg^xxmodmodp, gp, g^yymodmodp)p) –Calcolo della chiave K

Diffie-Hellman 24

Puzzle di Merkle

Puzzle la cui soluzione richiede t operazioni Esempio:

Puzzle(x,ID) Scegli una chiave k

Computa y ← CBC-DES_k(x,ID) return (y, primi 20 bit di k) Puzzle(x,ID)

Scegli una chiave k

Computa y ← CBC-DES_k(x,ID) return (y, primi 20 bit di k)

Richiede 2³⁵operazioni in media Soluzione del puzzle: x

Diffie-Hellman 25

Puzzle di Merkle

x

x x

x

x

x

?? ??

Puzzle

Puzzle11, …, , …, PuzzlePuzzlenn

ID ID_jj

Scegli x₁, …, x_n, ID₁, …, ID_n Puzzle_i←Puzzle(x_i,ID_i) Scegli x

Scegli x₁₁, …, x, …, x_nn, ID, ID₁₁, …, , …, IDID_nn Puzzle

Puzzle_ii←Puzzle←Puzzle((xx_ii,ID,ID_ii)) Scegli j Risolvi Puzzle_j

Scegli j Scegli j Risolvi Risolvi PuzzlePuzzlej_j

iagio nnarella

Diffie-Hellman 26

Puzzle di Merkle

‰Computazioni di :

–Costruzione di n puzzle tempo θ(n)

‰Computazioni di :

–Risoluzione di un puzzle tempo θ(t)

‰Computazioni di :

–Risoluzione di n/2 puzzle in media tempo θ(t·n)

Diffie-Hellman 27

Puzzle di Merkle

‰ Computazioni di :

– Costruzione di n puzzle tempo θ(n)

‰Computazioni di :

– Risoluzione di un puzzle tempo θ(n)

‰Computazioni di :

– Risoluzione di n/2 puzzle in media tempo θ(n²)

Se n = θ(t) Se n = θ(t)