Crittografia a chiave pubblica.Morandi Maria

Stelzer Sara

Seminario di Algebra

Crittografia a chiave pubblica. – p. 1/48

Sistemi di crittografia

Scambio di messaggi cifrati privatifra due utenti

possono essere decifrati solo dagli utenti in

possesso della chiave

Crittografia a chiave pubblica. – p. 2/48

Sistemi di crittografia

Scambio di messaggi cifrati privatifra due utenti

possono essere decifrati solo dagli utenti inpossesso della chiave

Crittografia a chiave pubblica. – p. 2/48

Sistemi di crittografia

Scambio di messaggi cifrati privatifra due utenti

possono essere decifrati solo dagli utenti in

possesso della chiave

Crittografia a chiave pubblica. – p. 2/48

Sistemi di crittografia

? a chiave privata:

un’ unica chiave utile siaper cifrare che per de-cifrare nota solo agli utentiinteressati

?a chiave pubblica: utilizza due chiavi, una diconoscenza pubblica percifrare, una nota al solodestinatario del messag-gio per decifrare

Crittografia a chiave pubblica. – p. 3/48

Sistemi di crittografia

? a chiave privata: un’ unica chiave utile siaper cifrare che per de-cifrare nota solo agli utentiinteressati

?a chiave pubblica: utilizza due chiavi, una diconoscenza pubblica percifrare, una nota al solodestinatario del messag-gio per decifrare

Crittografia a chiave pubblica. – p. 3/48

Sistemi di crittografia

? a chiave privata: un’ unica chiave utile siaper cifrare che per de-cifrare nota solo agli utentiinteressati

?a chiave pubblica:

utilizza due chiavi, una diconoscenza pubblica percifrare, una nota al solodestinatario del messag-gio per decifrare

Crittografia a chiave pubblica. – p. 3/48

Sistemi di crittografia

? a chiave privata: un’ unica chiave utile siaper cifrare che per de-cifrare nota solo agli utentiinteressati

?a chiave pubblica: utilizza due chiavi, una diconoscenza pubblica percifrare, una nota al solodestinatario del messag-gio per decifrare

Crittografia a chiave pubblica. – p. 3/48

Gli autori principali

Crittografia a chiave pubblica. – p. 4/48

Indice

X Sistema RSA

X Logaritmo discreto: ∗ Sistema Diffie-Hellman∗ Sistema Massey-Omura∗ Sistema ElGamal

X Problema dello zaino

Crittografia a chiave pubblica. – p. 5/48

Sistema RSA

X Moltiplicare:

p · q = nelementare! ,

. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,

. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,. . . operazione inversa. . .

X Fattorizzare:

n = ? · ? · ? · . . . · ?difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Sistema RSA

X Moltiplicare:p · q = n

elementare! ,. . . operazione inversa. . .

X Fattorizzare:n = ? · ? · ? · . . . · ?

difficile!/

Crittografia a chiave pubblica. – p. 6/48

Algoritmo RSA

Alice

KE,A = (nA, eA)

Bob

KE,B = (nB, eB)

KD,A = (nA, dA)

Crittografia a chiave pubblica. – p. 7/48

Algoritmo RSA

Alice

KE,A = (nA, eA)

Bob

KE,B = (nB, eB)

KD,A = (nA, dA)

Crittografia a chiave pubblica. – p. 7/48

Algoritmo RSA

Alice

KE,A = (nA, eA)

Bob

KE,B = (nB, eB)

KD,A = (nA, dA)

Crittografia a chiave pubblica. – p. 7/48

Algoritmo RSA

Alice

∗ Scelta di pA e qA primi grandi∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Alice∗ Scelta di pA e qA primi grandi

∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Alice∗ Scelta di pA e qA primi grandi∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Alice∗ Scelta di pA e qA primi grandi∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)

∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Alice∗ Scelta di pA e qA primi grandi∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Alice∗ Scelta di pA e qA primi grandi∗ Calcolo di nA = pA · qA

∗ Calcolo di ϕ(nA) = (pA − 1) · (qA − 1)∗ Scelta di eA primo con ϕ(nA)

∗ Calcolo di dA ≡ e−1

A (mod ϕ(nA))

Crittografia a chiave pubblica. – p. 8/48

Algoritmo RSA

Cifratura:

Plaintext_ Ciphertext

C = P eA(mod nA)

Decifratura:

Ciphertext_ Plaintext

P = C dA(mod nA)

Crittografia a chiave pubblica. – p. 9/48

Algoritmo RSA

Cifratura:

Plaintext_ Ciphertext

C = P eA(mod nA)

Decifratura:

Ciphertext_ Plaintext

P = C dA(mod nA)

Crittografia a chiave pubblica. – p. 9/48

Algoritmo RSA

Cifratura:

Plaintext_ Ciphertext

C = P eA(mod nA)

Decifratura:

Ciphertext_ Plaintext

P = C dA(mod nA)

Crittografia a chiave pubblica. – p. 9/48

Algoritmo RSA

Cifratura:

Plaintext_ Ciphertext

C = P eA(mod nA)

Decifratura:

Ciphertext_ Plaintext

P = C dA(mod nA)

Crittografia a chiave pubblica. – p. 9/48

Algoritmo RSA

NOTA !· Alfabeto di N-lettere

· unità plaintext: blocchi di k -lettere

· unità ciphertext: blocchi di l-lettere

Crittografia a chiave pubblica. – p. 10/48

Esempio RSA

N = 128 k = 3 l = 4

Bob Alice

P= ’SISTER’ KE,A = (5 250 907, 12 809)

KD,A = (5 250 907, 276 793)

Crittografia a chiave pubblica. – p. 11/48

Esempio RSA

N = 128 k = 3 l = 4

Bob Alice

P= ’SISTER’ KE,A = (5 250 907, 12 809)

KD,A = (5 250 907, 276 793)

Crittografia a chiave pubblica. – p. 11/48

Esempio RSA

N = 128 k = 3 l = 4

Bob Alice

P= ’SISTER’

KE,A = (5 250 907, 12 809)

KD,A = (5 250 907, 276 793)

Crittografia a chiave pubblica. – p. 11/48

Esempio RSA

N = 128 k = 3 l = 4

Bob Alice

P= ’SISTER’ KE,A = (5 250 907, 12 809)

KD,A = (5 250 907, 276 793)

Crittografia a chiave pubblica. – p. 11/48

Esempio RSA

Bob

k = 3 ⇒ P1 = SISP2 = TER

SIS 7−→ 83 · 1282+73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282+73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→

83 · 1282+73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ S

83 · 1282+73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 +

73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + I

73 · 1281+83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + 73 · 1281 +

83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 +73 · 1281 + S

83 · 1280= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + 73 · 1281 + 83 · 1280

= 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + 73 · 1281 + 83 · 1280 = 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + 73 · 1281 + 83 · 1280 = 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bobk = 3 ⇒ P1 = SIS

P2 = TER

SIS 7−→ 83 · 1282 + 73 · 1281 + 83 · 1280 = 1369299

C = P eA(mod nA)

1369299 12809(mod 5250907) = 440725

Crittografia a chiave pubblica. – p. 12/48

Esempio RSA

Bob

C1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

BobC1 = 440725 = 0 · 1283 + 26 · 1282 + 115 · 1281 + 21

<NUL>

<SUB>

s

<NAK>

C1 = <NUL><SUB>s<NAK>

Crittografia a chiave pubblica. – p. 13/48

Esempio RSA

Bob

P2 = TER 7−→ <NUL>x<’><FF> = C2

C =<NUL><SUB>s<NAK><NUL>x<’><FF>↘

Alice

Crittografia a chiave pubblica. – p. 14/48

Esempio RSA

BobP2 = TER 7−→ <NUL>x<’><FF> = C2

C =<NUL><SUB>s<NAK><NUL>x<’><FF>↘

Alice

Crittografia a chiave pubblica. – p. 14/48

Esempio RSA

BobP2 = TER 7−→ <NUL>x<’><FF> = C2

C =<NUL><SUB>s<NAK><NUL>x<’><FF>

↘Alice

Crittografia a chiave pubblica. – p. 14/48

Esempio RSA

BobP2 = TER 7−→ <NUL>x<’><FF> = C2

C =<NUL><SUB>s<NAK><NUL>x<’><FF>↘

Alice

Crittografia a chiave pubblica. – p. 14/48

Esempio RSA

BobP2 = TER 7−→ <NUL>x<’><FF> = C2

C =<NUL><SUB>s<NAK><NUL>x<’><FF>↘

Alice

Crittografia a chiave pubblica. – p. 14/48

Esempio RSA

Alice

l = 4 ⇒ C1=<NUL><SUB>s<NAK>C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→0 · 1283+26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→0 · 1283+26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>

7−→0 · 1283+26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→

0 · 1283+26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→< NUL >

0 · 1283+26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 ·1283 +

26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 · 1283+ < SUB >

26 · 1282+115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 ·1283 +26 ·1282 +

115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0·1283+26·1282+s

115 · 1281+21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 ·1283 +26 ·1282 +115 ·1281 +

21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 · 1283 + 26 · 1282 + 115 · 1281+ < NAK >

21= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 ·1283 +26 ·1282 +115 ·1281 +21

= 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alicel = 4 ⇒ C1=<NUL><SUB>s<NAK>

C2=<NUL>x<’><FF>

C1 = <NUL><SUB>s<NAK>7−→ 0 ·1283+26 ·1282+115 ·1281+21 = 440725

Crittografia a chiave pubblica. – p. 15/48

Esempio RSA

Alice

P = CdA(mod nA)

440725 276793(mod 5250907) = 1369299

P1 = 1369299 = 83 · 1282 + 73 · 1281 + 83 · 1280

7→ SIS

Crittografia a chiave pubblica. – p. 16/48

Esempio RSA

Alice

P = CdA(mod nA)

440725 276793(mod 5250907) = 1369299

P1 = 1369299 = 83 · 1282 + 73 · 1281 + 83 · 1280

7→ SIS

Crittografia a chiave pubblica. – p. 16/48

Esempio RSA

Alice

P = CdA(mod nA)

440725 276793(mod 5250907) = 1369299

P1 = 1369299 = 83 · 1282 + 73 · 1281 + 83 · 1280

7→ SIS

Crittografia a chiave pubblica. – p. 16/48

Esempio RSA

Alice

P = CdA(mod nA)

440725 276793(mod 5250907) = 1369299

P1 = 1369299 = 83 · 1282 + 73 · 1281 + 83 · 1280

7→ SIS

Crittografia a chiave pubblica. – p. 16/48

Esempio RSA

Alice

P = CdA(mod nA)

440725 276793(mod 5250907) = 1369299

P1 = 1369299 = 83 · 1282 + 73 · 1281 + 83 · 1280

7→ SIS

Crittografia a chiave pubblica. – p. 16/48

Esempio RSA

Alice

C2 = <NUL>x<’><FF> 7−→ TER = P2

P = SISTER

Crittografia a chiave pubblica. – p. 17/48

Esempio RSA

AliceC2 = <NUL>x<’><FF> 7−→ TER = P2

P = SISTER

Crittografia a chiave pubblica. – p. 17/48

Esempio RSA

AliceC2 = <NUL>x<’><FF> 7−→ TER = P2

P = SISTER

Crittografia a chiave pubblica. – p. 17/48

Esempio RSA

AliceC2 = <NUL>x<’><FF> 7−→ TER = P2

P = SISTER

Crittografia a chiave pubblica. – p. 17/48

Indice

X Sistema RSA

X Logaritmo discreto: ∗ Sistema Diffie-Hellman∗ Sistema Massey-Omura∗ Sistema ElGamal

X Problema dello zaino

Crittografia a chiave pubblica. – p. 18/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:

b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,

. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:

logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

. . . su gruppo finito . . .

X Elevare:b x = y

semplice! ,. . . operazione inversa. . .

X Logaritmo:logb y =? x ?

difficile! /

Crittografia a chiave pubblica. – p. 19/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto

di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Logaritmo discreto

∗ G gruppo finito

∗ b elemento di G

∗ y elemento di G, potenza di b

⇒ il logaritmo discreto di y per la base b è unintero x tale che

b x = y

Crittografia a chiave pubblica. – p. 20/48

Sistema Diffie-Hellman

X campo con q elementi

Fq

; q conosciuto da tutti

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 21/48

Sistema Diffie-Hellman

X campo con q elementi Fq

; q conosciuto da tutti

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 21/48

Sistema Diffie-Hellman

X campo con q elementi Fq

; q conosciuto da tutti

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 21/48

Sistema Diffie-Hellman

X campo con q elementi Fq

; q conosciuto da tutti

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 21/48

Sistema Diffie-Hellman

X campo con q elementi Fq

; q conosciuto da tutti

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 21/48

Sistema Diffie-Hellman

Alice Bob

? Sceglie 1 ≤ a ≤ q − 1

; a privato? Sceglie 1 ≤ b ≤ q − 1

; b privato

? Calcola ga∈ Fq

; ga pubblico? Calcola gb ∈

Fq

; gb pubblico

Crittografia a chiave pubblica. – p. 22/48

Sistema Diffie-Hellman

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato

? Sceglie 1 ≤ b ≤ q − 1

; b privato

? Calcola ga∈ Fq

; ga pubblico? Calcola gb ∈

Fq

; gb pubblico

Crittografia a chiave pubblica. – p. 22/48

Sistema Diffie-Hellman

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato? Sceglie 1 ≤ b ≤ q − 1

; b privato

? Calcola ga∈ Fq

; ga pubblico? Calcola gb ∈

Fq

; gb pubblico

Crittografia a chiave pubblica. – p. 22/48

Sistema Diffie-Hellman

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato? Sceglie 1 ≤ b ≤ q − 1

; b privato

? Calcola ga∈ Fq

; ga pubblico

? Calcola gb ∈Fq

; gb pubblico

Crittografia a chiave pubblica. – p. 22/48

Sistema Diffie-Hellman

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato? Sceglie 1 ≤ b ≤ q − 1

; b privato

? Calcola ga∈ Fq

; ga pubblico? Calcola gb ∈

Fq

; gb pubblico

Crittografia a chiave pubblica. – p. 22/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice BobConosce: a, gb Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice Bob

Conosce: a, gb Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice BobConosce: a, gb

Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice BobConosce: a, gb Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice BobConosce: a, gb Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

Alice BobConosce: a, gb Conosce: b, ga

⇓gab = (gb)a

⇓gab = (ga)b

Crittografia a chiave pubblica. – p. 23/48

Sistema Diffie-Hellman

Chiave privata: gab

CharlieConosce: ga, gb

Non sa calcolare gab

NON conosce a, b

Crittografia a chiave pubblica. – p. 24/48

Sistema Diffie-Hellman

Chiave privata: gab

Charlie

Conosce: ga, gb

Non sa calcolare gab

NON conosce a, b

Crittografia a chiave pubblica. – p. 24/48

Sistema Diffie-Hellman

Chiave privata: gab

CharlieConosce: ga, gb

Non sa calcolare gab

NON conosce a, b

Crittografia a chiave pubblica. – p. 24/48

Sistema Diffie-Hellman

Chiave privata: gab

CharlieConosce: ga, gb

Non sa calcolare gab

NON conosce a, b

Crittografia a chiave pubblica. – p. 24/48

Sistema Diffie-Hellman

Chiave privata: gab

CharlieConosce: ga, gb

Non sa calcolare gab

NON conosce a, b

Crittografia a chiave pubblica. – p. 24/48

Esempio Diffie-Hellman

∗ Alfabeto 26-lettere

∗ Campo finito F53

∗ g = 2

C ≡ P + K (mod 26)

; K = chiave privata

Crittografia a chiave pubblica. – p. 25/48

Esempio Diffie-Hellman

∗ Alfabeto 26-lettere

∗ Campo finito F53

∗ g = 2

C ≡ P + K (mod 26)

; K = chiave privata

Crittografia a chiave pubblica. – p. 25/48

Esempio Diffie-Hellman

∗ Alfabeto 26-lettere

∗ Campo finito F53

∗ g = 2

C ≡ P + K (mod 26)

; K = chiave privata

Crittografia a chiave pubblica. – p. 25/48

Esempio Diffie-Hellman

∗ Alfabeto 26-lettere

∗ Campo finito F53

∗ g = 2

C ≡ P + K (mod 26)

; K = chiave privata

Crittografia a chiave pubblica. – p. 25/48

Esempio Diffie-Hellman

∗ Alfabeto 26-lettere

∗ Campo finito F53

∗ g = 2

C ≡ P + K (mod 26)

; K = chiave privata

Crittografia a chiave pubblica. – p. 25/48

Esempio Diffie-Hellman

Alice Bob

a = 29 b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Alice Boba = 29

b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Alice Boba = 29 b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Alice Boba = 29 b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Alice Boba = 29 b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Alice Boba = 29 b = 19

ga = 45 ∈ F53

gb = 12 ∈ F53

}

Pubbliche

K = gab = 21

Crittografia a chiave pubblica. – p. 26/48

Esempio Diffie-Hellman

Bob

P = SISTER C ≡ P + K (mod 26)

C1 =18+21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER

C ≡ P + K (mod 26)

C1 =18+21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 =18+21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 =

18+21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = S

18+21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 +

21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + K

21 (mod 26)= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + 21 (mod 26)

= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + 21 (mod 26) = 13

= N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + 21 (mod 26) = N

C = NDNOZM 7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + 21 (mod 26) = N

C = NDNOZM

7−→

Alice

Crittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

BobP = SISTER C ≡ P + K (mod 26)

C1 = 18 + 21 (mod 26) = N

C = NDNOZM 7−→

AliceCrittografia a chiave pubblica. – p. 27/48

Esempio Diffie-Hellman

Alice

C = NDNOZM P ≡ C − K (mod 26)

P1 =13−21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM

P ≡ C − K (mod 26)

P1 =13−21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 =13−21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 =

13−21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = N

13−21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 −

21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − K

21 (mod 26)= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − 21 (mod 26)

= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − 21 (mod 26) = 18

= S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − 21 (mod 26) = S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − 21 (mod 26) = S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Esempio Diffie-Hellman

AliceC = NDNOZM P ≡ C − K (mod 26)

P1 = 13 − 21 (mod 26) = S

P = SISTER

Crittografia a chiave pubblica. – p. 28/48

Sistema Massey-Omura

X campo con q elementi

Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob

? Sceglie0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1

MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

X campo con q elementi Fq

; q conosciuto da tutti

Alice Bob? Sceglie

0 ≤ eA ≤ (q − 1)

? Sceglie0 ≤ eB ≤ (q − 1)

MCD(eA, q − 1) = 1 MCD(eB, q − 1) = 1

Crittografia a chiave pubblica. – p. 29/48

Sistema Massey-Omura

Alice Bob

? CalcoladA = e−1

A (mod (q − 1))

? CalcoladB = e−1

B (mod (q − 1))

; eA, dA private ; eB, dB private

Crittografia a chiave pubblica. – p. 30/48

Sistema Massey-Omura

Alice Bob? CalcoladA = e−1

A (mod (q − 1))

? CalcoladB = e−1

B (mod (q − 1))

; eA, dA private ; eB, dB private

Crittografia a chiave pubblica. – p. 30/48

Sistema Massey-Omura

Alice Bob? CalcoladA = e−1

A (mod (q − 1))

? CalcoladB = e−1

B (mod (q − 1))

; eA, dA private ; eB, dB private

Crittografia a chiave pubblica. – p. 30/48

Sistema Massey-Omura

Alice Bob? CalcoladA = e−1

A (mod (q − 1))

? CalcoladB = e−1

B (mod (q − 1))

; eA, dA private

; eB, dB private

Crittografia a chiave pubblica. – p. 30/48

Sistema Massey-Omura

Alice Bob? CalcoladA = e−1

A (mod (q − 1))

? CalcoladB = e−1

B (mod (q − 1))

; eA, dA private ; eB, dB private

Crittografia a chiave pubblica. – p. 30/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

Alice

PeB 7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB

7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→

(PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ PeB

(PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙(PeB)eA

((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙((PeB)eA)dB = P eA

7−→(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙((PeB)eA)dB = P eA 7−→

(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙((PeB)eA)dB = P eA 7−→ PeA

(PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙((PeB)eA)dB = P eA 7−→ (PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema Massey-Omura

Bob

P7−→

AlicePeB 7−→ (PeB)eA

↙((PeB)eA)dB = P eA 7−→ (PeA)dA = P

Crittografia a chiave pubblica. – p. 31/48

Sistema ElGamal

X campo con q elementi

Fq

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 32/48

Sistema ElGamal

X campo con q elementi Fq

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 32/48

Sistema ElGamal

X campo con q elementi Fq

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 32/48

Sistema ElGamal

X campo con q elementi Fq

X g generatore di F∗q

; g conosciuto da tutti

Crittografia a chiave pubblica. – p. 32/48

Sistema ElGamal

Alice Bob

? Sceglie 1 ≤ a ≤ q − 1

; a privato? Calcola ga∈ Fq

; ga pubblico

Crittografia a chiave pubblica. – p. 33/48

Sistema ElGamal

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato

? Calcola ga∈ Fq

; ga pubblico

Crittografia a chiave pubblica. – p. 33/48

Sistema ElGamal

Alice Bob? Sceglie 1 ≤ a ≤ q − 1

; a privato? Calcola ga∈ Fq

; ga pubblico

Crittografia a chiave pubblica. – p. 33/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak)

↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗

? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Sistema ElGamal

Bob

P7−→

Alice

? Sceglie k intero

(gk, P · gak) ↗? Calcola (gk)a = gak

? Calcola P·gak

gak = P

Crittografia a chiave pubblica. – p. 34/48

Indice

X Sistema RSA

X Logaritmo discreto: ∗ Sistema Diffie-Hellman∗ Sistema Massey-Omura∗ Sistema ElGamal

X Problema dello zaino

Crittografia a chiave pubblica. – p. 35/48

Problema dello zaino

Dato uno zaino di volume V

e dato un insieme{vi} di k interi positivi trovare la k − upla di interin = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Problema dello zaino

Dato uno zaino di volume V e dato un insieme{vi} di k

interi positivi trovare la k − upla di interin = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Problema dello zaino

Dato uno zaino di volume V e dato un insieme{vi} di k oggetti

interi positivi trovare la k − upla

di interi n = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Problema dello zaino

Dato uno zaino di volume V e dato un insieme{vi} di k interi positivi

trovare la k − upla di interin = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Problema dello zaino

Dato uno zaino di volume V e dato un insieme{vi} di k interi positivi trovare la k − upla diinteri n = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Problema dello zaino

Dato uno zaino di volume V e dato un insieme{vi} di k interi positivi trovare la k − upla diinteri n = (εk−1εk−2 . . . ε1ε0)2 tale che

V =n∑

i=0

εivi

se n esiste.

Crittografia a chiave pubblica. – p. 36/48

Zaino superincreasing

L’insieme {vi} è particolare:

? vi−1 < vi < vi+1 ⇒ ordine crescente

? vi >i−1∑

j=0

vj ⇒ ogni vi maggiore della somma dei

precedenti

Crittografia a chiave pubblica. – p. 37/48

Zaino superincreasing

L’insieme {vi} è particolare:

? vi−1 < vi < vi+1

⇒ ordine crescente

? vi >i−1∑

j=0

vj ⇒ ogni vi maggiore della somma dei

precedenti

Crittografia a chiave pubblica. – p. 37/48

Zaino superincreasing

L’insieme {vi} è particolare:

? vi−1 < vi < vi+1 ⇒ ordine crescente

? vi >i−1∑

j=0

vj ⇒ ogni vi maggiore della somma dei

precedenti

Crittografia a chiave pubblica. – p. 37/48

Zaino superincreasing

L’insieme {vi} è particolare:

? vi−1 < vi < vi+1 ⇒ ordine crescente

? vi >i−1∑

j=0

vj

⇒ ogni vi maggiore della somma dei

precedenti

Crittografia a chiave pubblica. – p. 37/48

Zaino superincreasing

L’insieme {vi} è particolare:

? vi−1 < vi < vi+1 ⇒ ordine crescente

? vi >i−1∑

j=0

vj ⇒ ogni vi maggiore della somma dei

precedenti

Crittografia a chiave pubblica. – p. 37/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}

1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 35- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k

2- Partendo con εj−1 decrementare j eporre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 35- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 35- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i0

4- Se W > 0 eseguire nuovamente punto 2e 3

5- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 3

5- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 35- Se W = 0 ⇒ Ok! Soluzione UNICA

6- Se W > 0 e tutti i vi > W ⇒ Non esistesoluzione

Crittografia a chiave pubblica. – p. 38/48

Algoritmo per superincreasing

Dati: V intero e la k − upla di {vi}1- Scegliere W = V e porre j = k2- Partendo con εj−1 decrementare j e

porre tutti gli εj = 0 finchè vi ≤ W talei sarà chiamato i0 e εi0 = 1

3- Sostituire W = W − vi0 e porre j = i04- Se W > 0 eseguire nuovamente punto 2

e 35- Se W = 0 ⇒ Ok! Soluzione UNICA6- Se W > 0 e tutti i vi > W ⇒ Non esiste

soluzione

Crittografia a chiave pubblica. – p. 38/48

Crittografia con lo zaino

X Unità P equivalenti a k − uple di interi

X Ogni utente fissa:· una k − upla {v0 . . . vk−1} con proprietàdi superincreasing

· un intero m tale che m >k−1∑

i=0

vi

· un intero a primo con m tale che0 < a < m

Crittografia a chiave pubblica. – p. 39/48

Crittografia con lo zaino

X Unità P equivalenti a k − uple di interi

X Ogni utente fissa:

· una k − upla {v0 . . . vk−1} con proprietàdi superincreasing

· un intero m tale che m >k−1∑

i=0

vi

· un intero a primo con m tale che0 < a < m

Crittografia a chiave pubblica. – p. 39/48

Crittografia con lo zaino

X Unità P equivalenti a k − uple di interi

X Ogni utente fissa:· una k − upla {v0 . . . vk−1} con proprietàdi superincreasing

· un intero m tale che m >k−1∑

i=0

vi

· un intero a primo con m tale che0 < a < m

Crittografia a chiave pubblica. – p. 39/48

Crittografia con lo zaino

X Unità P equivalenti a k − uple di interi

X Ogni utente fissa:· una k − upla {v0 . . . vk−1} con proprietàdi superincreasing

· un intero m tale che m >k−1∑

i=0

vi

· un intero a primo con m tale che0 < a < m

Crittografia a chiave pubblica. – p. 39/48

Crittografia con lo zaino

X Unità P equivalenti a k − uple di interi

X Ogni utente fissa:· una k − upla {v0 . . . vk−1} con proprietàdi superincreasing

· un intero m tale che m >k−1∑

i=0

vi

· un intero a primo con m tale che0 < a < m

Crittografia a chiave pubblica. – p. 39/48

Crittografia con lo zaino

X Calcola b = a−1 (mod m)

X Calcola la k − upla {wi} definita dawi = avi (mod m)

KE = {w0, . . . , wk−1}

KD = (b,m)

Crittografia a chiave pubblica. – p. 40/48

Crittografia con lo zaino

X Calcola b = a−1 (mod m)

X Calcola la k − upla {wi} definita dawi = avi (mod m)

KE = {w0, . . . , wk−1}

KD = (b,m)

Crittografia a chiave pubblica. – p. 40/48

Crittografia con lo zaino

X Calcola b = a−1 (mod m)

X Calcola la k − upla {wi} definita dawi = avi (mod m)

KE = {w0, . . . , wk−1}

KD = (b,m)

Crittografia a chiave pubblica. – p. 40/48

Crittografia con lo zaino

X Calcola b = a−1 (mod m)

X Calcola la k − upla {wi} definita dawi = avi (mod m)

KE = {w0, . . . , wk−1}

KD = (b,m)

Crittografia a chiave pubblica. – p. 40/48

Cifrare

Messaggio P = (εk−1 . . . ε1ε0)2

C =k−1∑

i=0

εiwi

Crittografia a chiave pubblica. – p. 41/48

Cifrare

Messaggio P = (εk−1 . . . ε1ε0)2

C =k−1∑

i=0

εiwi

Crittografia a chiave pubblica. – p. 41/48

Decifrare

V ≡ bC (mod m)

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Decifrare

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Decifrare

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Decifrare

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Decifrare

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Decifrare

V ≡ bC (mod m) ≡k−1∑

i=0

εibwi ≡ εivi (mod m)

V =k−1∑

i=0

εivi

Algoritmo perproblema dello zaino

superincreasing

}

Si ricava P

Crittografia a chiave pubblica. – p. 42/48

Esempio

X Alfabeto 26-lettere

X Unità P = singole lettere = 5 − uple da(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

X Alfabeto 26-lettereX Unità P = singole lettere

= 5 − uple da(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

X Alfabeto 26-lettereX Unità P = singole lettere = 5 − uple da

(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

X Alfabeto 26-lettereX Unità P = singole lettere = 5 − uple da

(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

X Alfabeto 26-lettereX Unità P = singole lettere = 5 − uple da

(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

X Alfabeto 26-lettereX Unità P = singole lettere = 5 − uple da

(00000)2 a (11001)2

Bob

“SISTER”7−→

Alice

Crittografia a chiave pubblica. – p. 43/48

Esempio

Alice

? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)

? Fissa m = 61 e a = 17? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17

? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17? Calcola b = 18

? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → Pubblica

KD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Alice? Fissa {vi} = (2, 3, 7, 15, 31)? Fissa m = 61 e a = 17? Calcola b = 18? Calcola {wi} = (34, 51, 58, 11, 39)

KE,A = (34, 51, 58, 11, 39) → PubblicaKD,A = (18, 61) → Privata

Crittografia a chiave pubblica. – p. 44/48

Esempio

Bob

P1 = S= (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39= 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S

= (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39= 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = 18

= (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39= 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39= 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39

= 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39 = 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39 = 90

C = (90, 11, 90, 124, 58, 73)

7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

BobP1 = S = (10010)2

= 0 · 34 + 1 · 51 + 0 · 58 + 0 · 11 + 1 · 39 = 90

C = (90, 11, 90, 124, 58, 73) 7−→

Alice

Crittografia a chiave pubblica. – p. 45/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90⇒ V1 ≡ 90 · 18 (mod 61)= 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90⇒ V1 ≡ 90 · 18 (mod 61)= 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90

⇒ V1 ≡ 90 · 18 (mod 61)= 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90 ⇒ V1 ≡ 90 · 18 (mod 61)

= 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90 ⇒ V1 ≡ 90 · 18 (mod 61) = 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

C = (90, 11, 90, 124, 58, 73)

C1 = 90 ⇒ V1 ≡ 90 · 18 (mod 61) = 34

. . . ora applica l’algoritmo dello zainosuperincreasing . . .

Crittografia a chiave pubblica. – p. 46/48

Esempio

Alice

V1 = 34 > 31 → ε4 = 134 − 31 = 3 < 15 → ε3 = 0

3 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34

> 31 → ε4 = 134 − 31 = 3 < 15 → ε3 = 0

3 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31

→ ε4 = 134 − 31 = 3 < 15 → ε3 = 0

3 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3

< 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15

→ ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 0

3 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03

< 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7

→ ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 0

3 = 3 → ε1 = 13 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03

= 3 → ε1 = 13 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3

→ ε1 = 13 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0

< 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2

→ ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

AliceV1 = 34 > 31 → ε4 = 1

34 − 31 = 3 < 15 → ε3 = 03 < 7 → ε2 = 03 = 3 → ε1 = 1

3 − 3 = 0 < 2 → ε0 = 0

Crittografia a chiave pubblica. – p. 47/48

Esempio

Alice

V1 ⇒ (10010)2 = 18 = S

P = SISTER

Crittografia a chiave pubblica. – p. 48/48

Esempio

AliceV1 ⇒ (10010)2 = 18 = S

P = SISTER

Crittografia a chiave pubblica. – p. 48/48

Esempio

AliceV1 ⇒ (10010)2 = 18 = S

P = SISTER

Crittografia a chiave pubblica. – p. 48/48

Esempio

AliceV1 ⇒ (10010)2 = 18 = S

P = SISTER

Crittografia a chiave pubblica. – p. 48/48