Sistema RSA

Il sistema RSA è un metodo di crittografia a chiave pubblica basato su principi matematici, che consente di cifrare e decifrare messaggi in modo sicuro. Si fonda sulla difficoltà computazionale di fattorizzare numeri grandi, ottenuti come prodotto di due numeri primi, per garantire la riservatezza delle comunicazioni.

 Ogni utente genera una coppia di chiavi:

• Chiave pubblica \((n, e)\): utilizzata per cifrare i messaggi.
• Chiave privata: mantenuta segreta e necessaria per decifrare i messaggi.

La decifratura è possibile solo al proprietario grazie a una chiave privata segreta.

La sicurezza di RSA si basa su una funzione matematica ("funzione trappola") difficile da invertire senza la conoscenza della chiave privata.

Questa funzione trappola consente di cifrare un messaggio in modo sicuro.

Perché si chiama RSA? Il sistema RSA prende il nome dalle iniziali dei suoi inventori: Rivest, Shamir e Adleman. RSA è un sistema di crittografia a chiave pubblica, ideato inizialmente da W. Diffie e M. E. Hellman, ma sviluppato e reso famoso dai ricercatori L. M. Adleman, R. L. Rivest e A. Shamir del MIT. È uno dei metodi più utilizzati per garantire sicurezza nelle comunicazioni.

Come funziona

Per utilizzare RSA, ogni utente deve generare due numeri primi molto grandi \(p\) e \(q\).

In genere si genera un numero casuale con molte cifre (ad esempio 100) e si verifica se il numero è primo usando test di primalità. Se non è primo, si prova qualche numero successivo.

Questi due numeri primi sono usati per calcolare il prodotto

$$ n = p \cdot q $$

Nota. Negli esempi i numeri scelti \( p \) e \( q \) sono piccoli per semplicità. Nella realtà, il sistema RSA utilizza numeri con circa 100 cifre decimali per \(p\) e \(q\), generando un \(n\) con circa 200 cifre. Questo garantisce una sicurezza elevata e rende il sistema resistente agli attacchi, perché non esiste a tutt’oggi un algoritmo efficiente per fattorizzare numeri molto grandi.

Viene poi scelto un numero \(e\) che sia relativamente primo con \((p-1)(q-1)\), ovvero:

$$ \text{MCD}(e, (p-1)(q-1)) = 1 $$

La coppia \((n, e)\) viene resa pubblica e rappresenta la chiave pubblica di cifratura.

Tuttavia, i numeri \(p\) e \(q\) rimangono segreti e rappresenano la chiave segreta che conosce solo il proprietario.

Quando un utente A vuole inviare un messaggio cifrato all'utente B, cerca la chiave pubblica di cifratura dell'utente B e la utilizza per cifrare il messaggio.

La formula di cifratura del messaggio è la seguente:

$$ C_i = P_i^{e_B} \mod n_B $$

Dove $ P_i $ sono i singoli blocchi del messaggio convertiti in valori numerici.

Una volta ottenuto il messaggio cifrato, l'utente A lo invia all'utente B.

Infine, l'utente B riceve il messaggio cifrato e lo decifra usando la sua chiave segreta.

Un esempio pratico

Considero due utenti A e B, ogni utente sceglie una propria chiave pubblica di cifratura.

$$ K_A = (65,11) $$

$$ K_B = (1003,3) $$

Un elenco pubblico contiene le chiavi di cifratura degli utenti.

Nota. Il primo elemento di ogni chiave pubblica è il prodotto di due numeri primi \( p \) e \( q \). Ad esempio, \( p =5 \) e \( q=13 \) che determina \( n = p \cdot q = 5 \cdot 13 = 65 \). Questi due numeri primi non sono pubblici. Il secondo elemento è un numero relativamente primo con \( (p-1) \cdot (q-1) = (5-1) \cdot (13 - 1) = 4 \cdot 12 = 48 \). Ad esempio, il numero $ e=11 $ è relativamente primo con $ 48 $ perché $ \text{MCD}(48,11)=1 $.

L'utente A vuole inviare un messaggio segreto ("ALGEBRA") all'utente B, utilizzando il sistema RSA.

Per farlo, cerca nell'elenco pubblico la chiave pubblica dell'utente B che è costituita dai valori \(n_B = 1003\) e \(e_B = 3\).

A questo punto, l'utente A deve trasformare il messaggio "algebra" in una forma numerica, cifrare il messaggio usando la chiave pubblica dell'utente B e inviare il messaggio cifrato all'utente B.

1] La cifratura del messaggio

Per prima cosa, converte ogni lettera del messaggio in un numero utilizzando una tabella che assegna a ogni lettera un valore numerico a due cifre (ad esempio, "A = 00", "B = 01", ..., "Z = 25").

Il messaggio "ALGEBRA" diventa:

$$ \text{A = 00, L = 11, G = 06, E = 04, B = 01, R = 17, A = 00} $$

La sequenza numerica del messaggio è quindi:

$$ 00 \ 11 \ 06 \ 04 \ 01 \ 17 \ 00 $$

Poi suddivide il messaggio in blocchi di due lettere (digrafi), ciascuno rappresentato da un numero.

Ogni blocco deve soddisfare due condizioni:

1. Il numero associato al blocco deve essere minore di \(n_B = 1003\).
2. Il numero deve essere relativamente primo con \(n_B\) (cioè, \(\text{MCD}(P_i, n_B) = 1\)).

I blocchi diventano:

$$ \text{AL = 0011, GE = 0604, BR = 0117, AX = 0023} $$

Poiché le lettere del messaggio sono dispari, l'utente A ha aggiunto la lettera "x" alla fine del messaggio per completare l'ultimo blocco.

A questo punto procede alla verifica delle condizioni.

I numeri corrispondenti ai blocchi sono:

$$ P_1 = 11, \quad P_2 = 604, \quad P_3 = 117, \quad P_4 = 23 $$

Tutti questi numeri sono minori di 1003 e relativamente primi a 1003 (si verifica calcolando il \(\text{MCD}\)).

$$ \text{MCD}(11, 1003) = 1 $$

$$ \text{MCD}(604, 1003) = 1 $$

$$ \text{MCD}(117, 1003) = 1 $$

$$ \text{MCD}(23, 1003) = 1 $$

Quindi, si può procedere alla cifratura del messaggio.

Nota. Se uno o più blocchi non sono minori di $ n_B=1003 $ occorre suddividere i blocchi in $ k_B - 1 $ dove $ k_B=4 $ è il numero di cifre presenti in $ n_B $. Poiché $ n_B $ è conosciuto sia dal mittente che dal destinatario, entrambi possono usarlo sia per codificare che per decodificare il messaggio.  Ad esempio, in questo caso in blocchi da tre cifre ( $ k_B-1=4-1=3 $ ). Quindi la stringa "0011 0604 0117 00" del messaggio  diventerebbe "001 106 040 117 002 323" aggiungendo due caratteri riempitivi "x" alla fine. In questo esempio non è necessario farlo perché tutti i numeri sono già inferiori a $ n_B=1003 $. Se invece un blocco numerico $ P_i $ non è relativamente primo a $ n_B $ è necessario modificare il messaggio inserendo dei caratteri non significativi per alterare i valori dei blocchi $ P_i $ finché non siano tutti relativamente primi con $ n_B $.

Per cifrare ogni blocco \(P_i\), l'utente A utilizza la chiave pubblica del destinatario, ossia dell'utente B \((n_B, e_B)\).

La formula di cifratura del messaggio è la seguente:

$$ C_i = P_i^{e_B} \mod n_B $$

Svolge i seguenti calcoli per ogni blocco.

$$ C_1 = 11^3 \mod 1003 = 328 $$

$$ C_2 = 604^3 \mod 1003 = 797 $$

$$ C_3 = 117^3 \mod 1003 = 825 $$

$$ C_4 = 23^3 \mod 1003 = 131 $$

Il messaggio cifrato diventa:

$$ C_1 = 328, \quad C_2 = 797, \quad C_3 = 825, \quad C_4 = 131 $$

Infine, l'utente A invia il messaggio cifrato all'utente B.

$$[ 328, 797, 825, 131 ] $$

L'utente B riceve il messaggio cifrato e utilizza la sua chiave privata per decifrarlo.

Solo l'utente B può decifrarlo perché possiede la chiave segreta che consente di invertire il processo di cifratura.

2] La decifratura del messaggio

Per decifrare il messaggio l'utente B deve usare la sua chiave segreta $ d_B $ che solo lui conosce.

La chiave pubblica dell'utente B è $ n_B = 1003 $ e $ e_B=3 $

$$ K_B = (1003,3) $$

L'utente B conosce anche i numeri primi $ p $ e $ q $ che ha usato per generare il numero $ n_B = 1003 $. Ad esempio, $ p_B= 17 $ e $ q_B = 59 $

$$ n_B = p_B \cdot q_B = 17 \cdot 59 = 1003 $$

Utilizza la funzione di Eulero \(\varphi(n_B) = 928 \) che conta quanti numeri interi positivi minori di $ n_B = 1003  $ sono relativamente primi con $ n_B $.

$$ \varphi(n_B) = (p_B - 1)(q_B - 1) $$

$$ \varphi(1003) = (17 - 1)(59 - 1) = 16 \cdot 58 = 928 $$

Per trovare la chiave privata \(d_B\) deve risolvere la seguente congruenza:

$$ e_B \cdot d_B \equiv 1 \pmod{\varphi(n_B)} $$

In questo caso:

$$ 3 \cdot d_B \equiv 1 \pmod{928} $$

Questa è una congruenza lineare che può essere risolta usando l’algoritmo esteso di Euclide.

Si divide \(928\) per \(3\) per trovare il massimo comune divisore (MCD):

$$   928 \div 3 = 309 \ con \ r=1  $$

Il resto è \(1\), quindi \(\text{MCD}(3, 928) = 1\), e una soluzione.

Si riscrive la divisione in forma lineare per esprimere \(1\) come combinazione lineare di \(3\) e \(928\):

$$ 1 = 928 - 3 \cdot 309 $$

Il coefficiente di \( 3 \) è la chiave privata  \(d_B\) dell'utente B

$$ d_B = -309 $$

Tuttavia, in questo caso si tratta di un valore negativo e a noi serve un valore positivo in modulo 928 come chiave privata, quindi aggiungiamo 928 moltiplicato per una costante k.

$$ d_B = -309 + 928k $$

Scegliendo \(k = 1\) otteniamo un valore positivo:

$$ d_B = -309 + 928 = 619 $$

Quindi, la chiave privata dell'utente B è

$$ d_B = 619 $$

Per decifrare ogni blocco $ C_i $ del messaggio cifrato, l'utente B utilizza la relazione inversa:

$$ P_i = C_i^{d_B} \mod n_B $$

Dove $ d_B = 619 $ è la chiave privata è $n_B=1003 $

Si procede con il calcolo per ogni singolo blocco del messaggio cifrato $[ 328, 797, 825, 131 ] $

1. Per \(C_1 = 328\) la congruenza da risolvere è \[ P_1 = 328^{619} \mod 1003 \] Questo viene calcolato usando la scomposizione binaria di \(619 = 512 + 64 + 32 + 8 + 2 + 1\) e calcolando le potenze modulari il risultato è: \[ P_1 = 11 \]
   Nota. Per calcolare \( P_1 = 328^{619} \mod 1003 \), scomponiamo l'esponente in somma di potenze di due e procediamo al calcolo iterativo delle potenze modulari. $$ 619 = (1001101011)_2 = 512 + 64 + 32 + 8 + 2 + 1 $$ Calcoliamo le potenze successive di \(328 \mod 1003\), iniziamo con \(328\) e iteriamo per trovare le potenze modulari necessarie. $$ 328^1 \rightarrow 328^1 \mod 1003 = 328 $$ $$ 328^2 \rightarrow 328^2 = 107584 \quad \Rightarrow \quad 107584 \mod 1003 = 263 $$ $$ 328^4 \rightarrow  263^2 = 69169 \quad \Rightarrow \quad 69169 \mod 1003 = 95 $$ $$ 328^8 \rightarrow  95^2 = 9025 \quad \Rightarrow \quad 9025 \mod 1003 = 992 $$ $$ 328^{16} \rightarrow  992^2 = 984064 \quad \Rightarrow \quad 984064 \mod 1003 = 16 $$ $$ 328^{32} \rightarrow   16^2 = 256 \quad \Rightarrow \quad 256 \mod 1003 = 256 $$ $$ 328^{64} \rightarrow  256^2 = 65536 \quad \Rightarrow \quad 65536 \mod 1003 = 454 $$ $$ 328^{128} \rightarrow  454^2 = 206116 \quad \Rightarrow \quad 206116 \mod 1003 = 647 $$ $$ 328^{256} \rightarrow  647^2 = 418609 \quad \Rightarrow \quad 418609 \mod 1003 = 902 $$ $$ 328^{512} \rightarrow  902^2 = 814564 \quad \Rightarrow \quad 814564 \mod 1003 = 783 $$ Quindi abbiamo trovato che in modulo 1003 i valori sono $ 328^1 \equiv 328 $, $ 328^2 \equiv 263 $, $ 328^8 \equiv 992 $, $ 328^{32} \equiv 256 $, $ 328^{64} \equiv 454 $, $ 328^{512} \equiv 783 $. Usiamo la rappresentazione binaria di \(619 = 512 + 64 + 32 + 8 + 2 + 1\) per combinare le potenze calcolate. Scriviamo: $$ 328^{619} = 328^{512} \cdot 328^{64} \cdot 328^{32} \cdot 328^{8} \cdot 328^{2} \cdot 328^{1} $$ Sostituiamo i risultati calcolati: $$ 328^{619} \equiv 783 \cdot 454 \cdot 256 \cdot 992 \cdot 263 \cdot 328 \mod 1003 $$ Eseguiamo le moltiplicazioni modulo \(1003\) $$ 783 \cdot 454 \mod 1003 = 354762 \mod 1003 = 154 $$ $$ 154 \cdot 256 \mod 1003 = 39424 \mod 1003 = 171 $$ $$ 171 \cdot 992 \mod 1003 = 169632 \mod 1003 = 441 $$ $$ 441 \cdot 263 \mod 1003 = 115983 \mod 1003 = 328 $$ $$ 328 \cdot 328 \mod 1003 = 107584 \mod 1003 = 11 $$ Il risultato finale è $$ 328^{619} \mod 1003 = 11 $$
2. Per \(C_2 = 797\) la congruenza da risolvere è \[ P_2 = 797^{619} \mod 1003 \] Il risultato è: \[ P_2 = 604 \]
3. Per \(C_3 = 825\) la congruenza da risolvere è \[ P_3 = 825^{619} \mod 1003 \] Il risultato è: \[ P_3 = 117 \]
4. Per \(C_4 = 131\) la congruenza da risolvere è \[ P_4 = 131^{619} \mod 1003 \] Il risultato è: \[ P_4 = 23 \]

I numeri \(P_i\) decifrati sono:

$$ P_1 = 11, \quad P_2 = 604, \quad P_3 = 117, \quad P_4 = 23 $$

Aggiungiamo degli zeri non significativi per trasformarli in blocchi da 4 cifre ciascuno

$$ P_1 = 0011, \quad P_2 =0604, \quad P_3 = 0117, \quad P_4 = 0023 $$

Quindi, poiché ogni blocco contiene due lettere e ogni lettera è un codice composto da due cifre, la sequenza numerica del messaggio decifrato è

$$ 00 \ 11 \ 06 \ 04 \ 01 \ 17 \ 00 \ 23 $$

Questi numeri corrispondono ai blocchi del messaggio originale, che erano stati convertiti in lettere.

Usando la tabella di corrispondenza numeri-lettere, l'utente B ottiene:

$$ 00=A $$

$$ 11=L $$

$$ 06=G $$

$$ 04=E $$

$$ 01=B $$

$$ 17=R $$

$$ 00=A $$

$$ 23 = X $$

Il messaggio ricostruito è $ \text{"ALGEBRAX"} $ dove l'ultimo carattere è stato usato solo come riempitvo e può essere eliminato.

In questo modo, l'utente B ha decifrato il messaggio cifrato usando la sua chiave privata \(d_B = 619\)

Il messaggio originale inviato dall'utente A è stato correttamente ricostruito come "ALGEBRA".

Questo processo dimostra la sicurezza del sistema RSA, in cui solo chi conosce la chiave privata può decifrare il messaggio.

E così via.