Teoremi con dimostrazioni - Teoria dei numeri

M.

Se q non divide M, allora (q, M) = 1 e quindi per il piccolo teorema di fermat si ha

M^(q-1) = 1 (mod q).

Sappiamo che il cifrato C^d = M^(e*d), e nell’ipotesi precedente che q non divida M,

possiamo riscrivere la congruenza precedente come C^d = M^(1+k*(p-1)(q-1)) =

M*(M^(q-1))^(K*(p-1)) = M (mod q).

Per ipotesi p|M, questo implica che p|C, e quindi anche C^d, per cui necessariamente

si ha C^d=M (mod p).

Si conclude che C^d è divisibile sia per p sia per q, quindi per n, per cui la decifrazione

funziona sempre.

La sicurezza del cryptosistema è basata sul fatto che si ritiene che la fattorizzazione

del numero n in tempo finito, con e e q con 500 cifre ciascuno, sia proibitivo (cioè da n

passare a p e q).

Def. Firma RSA:

Ricordandosi che (e, n) è la chiave pubblica, mentre d chiave privata, dopo aver scelto

M messaggio in chiaro tale che 1 < M < n, il titolare calcola la firma F = M^d (mod p)

e manderà la coppia (F, M), mentre chi riceve M dovrà calcolare F^e = M^(e*d) = M

(mod n).

Def. Crittosistema El-Gamal:

Supponiamo come primo passo per costruire tale crittosistema che A si voglia dotare

di tale crittosistema; scegliendo un primo p grande e una radice primitiva g (mod p).

Il secondo passo è scegliere un numero 1 < a < p-1 e calcola Beta = g^a (mod p),

cioè il minimo residuo positivo della potenza modulare.

Il crittosistema è già definito, perché la terna (p,g,Beta) è la chiave pubblica, mentre a

è la chiave privata.

Per capire la cifratura, consideriamo il caso in cui B voglia inviare un messaggio M ad

A, con 1 < M < p-1.

A questo punto, B sceglie un parametro K, con 1 < K < p-1 e calcola gamma = g^K

(mod p).

Dopodiché calcola delta per cui delta = M*Beta^K (mod P), con il cifrato pari alla

coppia C = (gamma, delta).

Il procedimento di decifratura consideriamo il caso in cui A riceva la coppia C =

(gamma, delta).

Per decifrare, si usa la chiave privata “a” calcolando gamma^a=(g^K)^a = g^(k*a)

(mod p).

A questo punto calcola l’inverso moltiplicativo (g^(K*a))*(g^(K*a)^-1) = 1 (mod p)

con l’algoritmo euclideo.

Per determinare il messaggio si moltiplica per delta, cioè (g^(K^a))^-1*delta, questo

perché ragionando in modulo p esso è equivalente a (g^(K*a))^-1*M*(Beta^K) =

(g^(K*a))^-1*M*((g^a)^K) = M (mod p).

Per ricordarsi possiamo considerare il fatto che delta è la “maschera” di M*B^k,

mentre gamma è l’indizio che serve al titolare per “smascherare” il messaggio

possedendo la chiave privata.

La sicurezza del crittosistema si basa sul problema di Diffie-Hellman che si ritiene

essere equivalente a quello del logaritmo discreto, dove calcolare g^ak (mod p) per

decifrare in tempo finito è proibitivo. probabilistico,

Si sottolinea che tale sistema è l’unico cioè randomico, ovvero stesso

messaggio M può essere cifrato in maniera completamente diversa dipendentemente

dalla scelta di K.

Def. Firma di El-Gamal:

Supponiamo che A voglia mandare un messaggio in chiaro M, però firmandolo, cioè

vuole essere sicuro che il destinatario B lo riceva (questo comporta che A non possa

negare di averlo inviato); A segue i passaggi:

i) Sceglie un parametro K tale che 1 < K < p-1 e calcola gamma = g^K (mod

p), ma questa volta, diversamente dalla cifratura, K deve essere

relativamente primo con p-1, cioè (K, p-1) = 1

ii) Calcola delta = (M – a*gamma)*K^(-1) (mod p), dove K^(-1) è l’inverso

moltiplicativo di K (mod p-1) con K^(-1)=1 (mod p-1) (avere K relativamente

primo con p-1 garantisce che ci sia soluzione, ragionando con modulo p per il

calcolo di gamma e in mod p-1 per delta)

Si nota che chi riceve il messaggio, non può modificarlo, perché non saprebbe come

firmarlo (vantaggio).

A questo punto ho la firma sigma Σ costituito dalla coppia (gamma, delta).

Il destinatario riceverà la terna (M, Σ) = (M, (gamma, delta)).

Per verificare la firma il destinatario dovrà calcolare beta^gamma*gamma^delta =

g^M (mod p).

Tale congruenza è verificata, perché la firma beta^gamma*gamma^delta, ragionando

in modulo p, abbiamo è equivalente a (g^a)^gamma*(g^K)*delta =

g^(a*gamma+K*delta) (mod p).

Se prendiamo la definizione di delta e moltiplichiamo membro a membro per K,

abbiamo che K*delta = (M-a*gamma)*K^(-1)*K (mod p-1), da cui segue che K*delta =

(M-a*gamma) (mod p-1) e ciò implica, portando a*gamma dell’altra parte, che

K*delta+a*gamma=M (mod p-1), cioè l’esponente della congruenza di prima.

Tornando quindi indietro e sostituendo abbiamo che g^(a*gamma+K*delta) = g^(M-

h*(p-1)) = g^M*((g^(p-1))^h) = g^M*1^h = g^M (mod p).

Supponiamo che un utente voglia falsificare la firma su un certo messaggio creato da

lui.

Se sceglie per primo il valore di gamma (scelta arbitraria) per far tornare g^M.

Dal momento che beta è pubblico, allora conosce anche beta^gamma.

Tuttavia, deve trovare gamma^delta = g^M * (beta^gamma)^-1 (mod p), cioè deve

trovare il corrispondente delta e quindi risolvere il problema del logaritmo discreto

(strada impraticabile).

Se sceglie delta è anche peggio, deve risolvere la congruenza in gamma, e quindi

anche questa è una strada impraticabile, per cui si conclude che la firma di El-Gamal è

sicura.

Se un volesse modificare il messaggio, g^M cambierebbe e quindi è impossibile fare

tale operazione.

Def. Crittosistema di Blum-Goldwasser :

Siano n un intero di Blum, con n=p*q (p,q = 3 (mod 4)), n chiave pubblica e p,q chiave

privata.

Supponiamo che il messaggio X che B vuole cifrare per A titolare del crittosistema sia

X = (x , …, x ) espresso in binario, cioè che i vari x appartengono all’insieme {0, 1},

1 l i

con 1 <= i <= l.

Chi vuole mandare il messaggio, cioè B, sceglie un b con 1 <= b <= n, con (b, n) = 1,

2

e calcola s = b (mod n).

0 02 12 l-12

A questo punto, B considera i numeri S = S (mod n), S = S (mod n), …, S = S

1 2 l

02*i

(mod n), cioè in generale si ha S = S (mod n) con tutti gli i tali che 1 <= i <= l.

i

Successivamente B considera la sequenza z z …z , dove tutti gli z appartengono a {0,

1 2 l

1} e z = S (mod 2).

i i

Per cifrare il messaggio X con tutti gli x , che possono essere 0 o 1, somma il vettore z

i

ad x, cioè calcola Y = x + z (mod 2) e il cifrato Y è dato da y y …y , aggiungendo alla

i i i 1 2 l

l2

fine s dove s = s (mod n).

l+1 l+1

Senza il numero s alla fine il ricevente non avrebbe nessuna base da cui partire per

l+1

decifrare.

Per decifrare, una volta ricevuto y y …y ,s , A usa la procedura seguente:

1 2 l l+1

i) Calcola a = (p+1/4)^(l+1) (mod p-1) e a = (q+1/4)^(l+1) (mod q-1)

1 2

ii) Calcola b = s ^(a ) (mod p) e b = s ^(a ) (mod q)

1 l+1 1 2 l+1 2

iii) Recupera il seme S con il teorema cinese del resto, perché S è {S =

0 0 0

b (mod p), S = b (mod q)}

1 0 2

iv) Usa il seme S per calcolare z z …z ed infine decifra calcolando x = y + z

0 1 2 l i i i

(mod 2), ottenendo quindi la sequenza x x …x , cioè il messaggio originale

1 2 l

Per giustificare la decifrazione, poniamo l’attenzione innanzitutto sull’ultimo elemento

del cifrato s .

l+1 l2 l2

Si osserva che s ^(p+1/4) = s ^(p+1/4) (mod n) per costruzione, perché s = s

l+1 l+1

(mod n), quindi elevandoli allo stesso fattore p+1/4 la congruenza rimane valida.

Segue che s ^(p+1/4) = s ^(p+1/2) = s ^(p-1/2)*s = 1*s = s (mod n) e posso

l+1 l l l l l

affermare questo perché s per Blum-Blum-Shub è anch’esso un quadrato, in

l l-12

particolare è il quadrato di s , quindi s ^(p-1/2) = s ^(p-1/2) = s ^(p-1) = 1 (mod p)

l-1 l l-1

per il teorema di eulero fermat (cioè elevando s a (p+1/4) ottengo il precedente s ).

l+1 l

2

Se itero, cioè faccio (s ^(p+1/4)) = (s ^(p+1/4))^(p+1/4), ma l’interno è congruo a

l l+1

s , per cui ho s ^(p+1/4).

l l l-12

Segue che s ^(p+1/4) = s ^(p+1/4) = s ^(p+1/2) = s ^(p-1/2)*s = 1*s = s

l l-1 l-1 l-1 l-1 l-1

(mod n). 2

In altri termini, elevando s a (p+1/4) scendo di due indici, cioè ottengo s .

l+1 l-1

l+1

Iterando si ha s ^(p+1/4) = S (mod p)e lo stesso vale ragionando per q, cioè

l+1 0

l+1

s ^(p+1/4) = S (mod q).

l+1 0

Si osserva che gli esponenti precedenti sono di fatto a e a , per cui ho dimostrato il

1 2

secondo passo.

Una volta recuperato S tramite il teorema cinese, lo utilizzo per determinare s s …s .

0 1 2 l

Infine, prendo i bit di parità ottengo il vettore di mascheratura z z …z e sottraendolo

1 2 l

ottengo l’originale.

Def. Crittosistema di Rabin (1979) :

Alice si vuole dotare di un crittosistema di Rabin, si procede scegliendo due primi

grandi p,q con p,q = 3 (mod 4) (privilegiati) e calcola n = p*q.

“A” rende noto il numero n, cioè la chiave pubblica, mentre tiene segreta (p,q), cioè

chiave privata.

Se B vuole cifrare il messaggio M con 1 < M < n, calcola il cifrato C = M^2 (mod n).

Dopo aver ricevuto C, “A” lo decifra estraendo le quattro radici quadrate di C (mod n)

nel seguente modo:

i) Precalcola a e b tali che a*p+b*q = 1, con a, b in Z (lo può fare perché A

conosce p e q, per cui tramite l’algoritmo euclideo va a ritroso e tramite

l’identità di Bezount lo individua)

ii) Calcola C^((p+1)/4) = r (mod p) e C^((q+1)/4) = s (mod q)

Da queste potenze modulai segue il sistema {x = a*p*s + b*q*r (mod n), y = a*p*s –

b*q*r (mod n)}.

Allora +-x e +-y sono le quattro radici quadrate di C (mod n), cioè una radice tra le

quattro è il messaggio M.

La dimostrazione è immediata:

Preso x = aps + bqr = bqr (mod p), ma bq = 1 (mod p) per l’identità di bezount ap +

bq = 1 (mod p), per cui x = r (mod p), ma r = C^((p+1)/4) (mod p) per il passaggio ii.

Segue C^((p+1)/4) = M (mod p), perché è congruo 3 (mod 4), quindi x = M (mod p).

Allo stesso modo ragiono mod q, cioè x = aps (mod q) = s (mod q) = C^((q+1)/4) = M

(mod q).

Siccome x = M è congruo sia mod p, sia mod q, allora lo è anche (mod n).

Allo stesso modo ragiono per y per ottenere le altre due radici.

Il crittosistema è “probability sicure”, ammesso che la fattorizzazione dei numeri interi

sia complicata.

Sostanzialmente, è equivalente alla fattorizzazione, perché se conosce p e q decifra,

ma se uno suppone che qualcuno abbia un metodo ipotetico polynomial time che

estragga le radici quadratiche senza p e q, allora si dimostra facilmen