Teoremi con dimostrazioni - Teoria dei numeri

Teorema di Fermat e cifratura RSA

Se \( q \) non divide \( M \), allora \((q, M) = 1\) e quindi, per il piccolo teorema di Fermat, si ha \( M^{(q-1)} = 1 \, (\text{mod} \, q) \). Sappiamo che il cifrato \( C^d = M^{(e \cdot d)} \), e nell'ipotesi precedente che \( q \) non divida \( M \), possiamo riscrivere la congruenza precedente come \( C^d = M^{(1+k \cdot (p-1) \cdot (q-1))} = M \cdot (M^{(q-1)})^{(K \cdot (p-1))} = M \, (\text{mod} \, q) \).

Per ipotesi \( p|M \), questo implica che \( p|C \), e quindi anche \( C^d \), per cui necessariamente si ha \( C^d=M \, (\text{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 proibitiva (cioè da \( n \) passare a \( p \) e \( q \)).

Definizione: Firma RSA

Ricordandosi che \((e, n)\) è la chiave pubblica, mentre \( d \) è la chiave privata, dopo aver scelto \( M \) messaggio in chiaro tale che \( 1 < M < n \), il titolare calcola la firma \( F = M^d \, (\text{mod} \, p) \) e manderà la coppia \((F, M)\), mentre chi riceve \( M \) dovrà calcolare \( F^e = M^{(e \cdot d)} = M \, (\text{mod} \, n)\).

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 \) \((\text{mod} \, p)\).

Il secondo passo è scegliere un numero \( 1 < a < p-1 \) e calcola \( \beta = g^a \, (\text{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.

Cifratura con El-Gamal

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 \, (\text{mod} \, p) \). Dopodiché calcola \( \delta \) per cui \( \delta = M \cdot \beta^K \, (\text{mod} \, P) \), con il cifrato pari alla coppia \( C = (\gamma, \delta) \).

Decifratura con El-Gamal

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 \cdot a)} \, (\text{mod} \, p) \). A questo punto calcola l'inverso moltiplicativo \((g^{(K \cdot a)}) \cdot (g^{(K \cdot a)})^{-1} = 1 \, (\text{mod} \, p)\) con l'algoritmo euclideo. Per determinare il messaggio si moltiplica per \( \delta \), cioè \( (g^{(K^a)})^{-1} \cdot \delta \), questo perché ragionando in modulo \( p \) esso è equivalente a \( (g^{(K \cdot a)})^{-1} \cdot M \cdot (\beta^K) = (g^{(K \cdot a)})^{-1} \cdot M \cdot ((g^a)^K) = M \, (\text{mod} \, p) \).

Per ricordarsi possiamo considerare il fatto che \( \delta \) è la "maschera" di \( M \cdot 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} \, (\text{mod} \, p) \) per decifrare in tempo finito è proibitivo.

Firma di El-Gamal

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 \).

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:

• Sceglie un parametro \( K \) tale che \( 1 < K < p-1 \) e calcola \( \gamma = g^K \, (\text{mod} \, p) \), ma questa volta, diversamente dalla cifratura, \( K \) deve essere relativamente primo con \( p-1 \), cioè \((K, p-1) = 1\)
• Calcola \( \delta = (M - a \cdot \gamma) \cdot K^{-1} \, (\text{mod} \, p) \), dove \( K^{-1} \) è l'inverso moltiplicativo di \( K \, (\text{mod} \, p-1) \) con \( K^{-1}=1 \, (\text{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, \Sigma) = (M, (\gamma, \delta))\). Per verificare la firma il destinatario dovrà calcolare \( \beta^\gamma \cdot \gamma^\delta = g^M \, (\text{mod} \, p) \). Tale congruenza è verificata, perché la firma \( \beta^\gamma \cdot \gamma^\delta \), ragionando in modulo \( p \), abbiamo è equivalente a \((g^a)^\gamma \cdot (g^K) \cdot \delta = g^{(a \cdot \gamma + K \cdot \delta)} \, (\text{mod} \, p)\). Se prendiamo la definizione di \( \delta \) e moltiplichiamo membro a membro per \( K \), abbiamo che \( K \cdot \delta = (M-a \cdot \gamma) \cdot K^{-1} \cdot K \, (\text{mod} \, p-1) \), da cui segue che \( K \cdot \delta = (M-a \cdot \gamma) \, (\text{mod} \, p-1) \) e ciò implica, portando \( a \cdot \gamma \) dall'altra parte, che \( K \cdot \delta + a \cdot \gamma = M \, (\text{mod} \, p-1) \), cioè l'esponente della congruenza di prima. Tornando quindi indietro e sostituendo abbiamo che \( g^{(a \cdot \gamma + K \cdot \delta)} = g^{(M-h \cdot (p-1))} = g^M \cdot ((g^{(p-1)})^h) = g^M \cdot 1^h = g^M \, (\text{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 \cdot (\beta^\gamma)^{-1} \, (\text{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 si volesse modificare il messaggio, \( g^M \) cambierebbe e quindi è impossibile fare tale operazione.

Crittosistema di Blum-Goldwasser

Siano \( n \) un intero di Blum, con \( n=p \cdot 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_1, \ldots, x_l) \) espresso in binario, cioè che i vari \( x_i \) appartengono all'insieme \(\{0, 1\}\), con \( 1 \leq i \leq l \).

Chi vuole mandare il messaggio, cioè \( B \), sceglie un \( b \) con \( 1 \leq b \leq n \), con \((b, n) = 1\), e calcola \( s_0 = b^2 \, (\text{mod} \, n) \). A questo punto, \( B \) considera i numeri \( S_1 = S_0^2 \, (\text{mod} \, n) \), \( S_2 = S_1^2 \, (\text{mod} \, n) \), \(\ldots\), \( S_l = S_{l-1}^2 \, (\text{mod} \, n) \), cioè in generale si ha \( S_i = S_{i-1}^2 \, (\text{mod} \, n) \) con tutti gli \( i \) tali che \( 1 \leq i \leq l \). Successivamente \( B \) considera la sequenza \( z_1, z_2, \ldots, z_l \), dove tutti gli \( z_i \) appartengono a \(\{0, 1\}\) e \( z_i = S_i \, (\text{mod} \, 2) \).

Per cifrare il messaggio \( X \) con tutti gli \( x_i \), che possono essere 0 o 1, somma il vettore \( z_i \) ad \( x_i \), cioè calcola \( Y_i = x_i + z_i \, (\text{mod} \, 2) \) e il cifrato \( Y \) è dato da \( y_1, y_2, \ldots, y_l \), aggiungendo alla fine \( s_{l+1} \) dove \( s_{l+1} = S_l^2 \, (\text{mod} \, n) \). Senza il numero \( s_{l+1} \) alla fine il ricevente non avrebbe nessuna base da cui partire per decifrare.

Decifratura con Blum-Goldwasser

Per decifrare, una volta ricevuto \( y_1, y_2, \ldots, y_l, s_{l+1} \), \( A \) usa la procedura seguente:

• Calcola \( a_1 = ((p+1)/4)^{(l+1)} \, (\text{mod} \, p-1) \) e \( a_2 = ((q+1)/4)^{(l+1)} \, (\text{mod} \, q-1) \)
• Calcola \( b_1 = s_{l+1}^{a_1} \, (\text{mod} \, p) \) e \( b_2 = s_{l+1}^{a_2} \, (\text{mod} \, q) \)
• Recupera il seme \( S_0 \) con il teorema cinese del resto, perché \( S_0 \) è \(\{S_0 = b_1 \, (\text{mod} \, p), S_0 = b_2 \, (\text{mod} \, q)\}\)
• Usa il seme \( S_0 \) per calcolare \( z_1, z_2, \ldots, z_l \) ed infine decifra calcolando \( x_i = y_i + z_i \, (\text{mod} \, 2) \), ottenendo quindi la sequenza \( x_1, x_2, \ldots, x_l \), cioè il messaggio originale

Giustificazione della decifrazione

Per giustificare la decifrazione, poniamo l'attenzione innanzitutto sull'ultimo elemento del cifrato \( s_{l+1} \). Si osserva che \( s_{l+1}^{(p+1)/4} = S_0 \, (\text{mod} \, n) \) per costruzione, perché \( s_l^2 = s_{l+1} \, (\text{mod} \, n) \), quindi elevandoli allo stesso fattore \((p+1)/4\) la congruenza rimane valida.

Siccome \( x = M \) è congruo sia mod \( p \), sia mod \( q \), allora lo è anche \((\text{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 facilmente.

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 \, (\text{mod} \, 4) \) (privilegiati) e calcola \( n = p \cdot 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 \, (\text{mod} \, n) \).

Decifratura con Rabin

Dopo aver ricevuto \( C \), "A" lo decifra estraendo le quattro radici quadrate di \( C \, (\text{mod} \, n)\) nel seguente modo:

• Precalcola a e b tali che \( a \cdot p + b \cdot q = 1 \), con \( a, b \in \mathbb{Z} \) (lo può fare perché A conosce \( p \) e \( q \), per cui tramite l'algoritmo euclideo va a ritroso e tramite l'identità di Bezout lo individua)
• Calcola \( C^{((p+1)/4)} = r \, (\text{mod} \, p) \) e \( C^{((q+1)/4)} = s \, (\text{mod} \, q) \)

Da queste potenze modulai segue il sistema \(\{x = a \cdot p \cdot s + b \cdot q \cdot r \, (\text{mod} \, n), y = a \cdot p \cdot s - b \cdot q \cdot r \, (\text{mod} \, n)\}\). Allora \(\pm x\) e \(\pm y\) sono le quattro radici quadrate di \( C \, (\text{mod} \, n)\), cioè una radice tra le quattro è il messaggio \( M \).

Dimostrazione

La dimostrazione è immediata: Preso \( x = aps + bqr = bqr \, (\text{mod} \, p) \), ma \( bq = 1 \, (\text{mod} \, p) \) per l'identità di Bezout \( ap + bq = 1 \, (\text{mod} \, p) \), per cui \( x = r \, (\text{mod} \, p) \), ma \( r = C^{((p+1)/4)} \, (\text{mod} \, p) \) per il passaggio ii. Segue \( C^{((p+1)/4)} = M \, (\text{mod} \, p) \), perché è congruo 3 \((\text{mod} \, 4)\), quindi \( x = M \, (\text{mod} \, p) \). Allo stesso modo ragiono mod \( q \), cioè \( x = aps \, (\text{mod} \, q) = s \, (\text{mod} \, q) = C^{((q+1)/4)} = M \, (\text{mod} \, q) \). Siccome \( x = M \) è congruo sia mod \( p \), sia mod \( q \), allora lo è anche \((\text{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 facilmente.