Metodo RSI

Introduzione

La crittografia consiste in tecniche che due persone stabiliscono per scriversi messaggi, in modo che non siano facilmente interpretabili da una terza persona.

La persona che riceve il messaggio criptato può decifrarlo solo se conosce la chiave utilizzata per decodificarlo.

In alcuni casi, la decifratura di un messaggio è molto più lunga della cifratura, anche se il codice crittografico è noto.

Descrizione del sistema RSA

Scelta della chiave

Scegli un intero $n$$n$ abbastanza grande, e vogliamo trasmettere $m$$m$ dove $0<m<n-1$$0<m<n-1$:

"abbastanza grande" significa che $n$$n$ deve permettere di rappresentare tutti i valori che potrebbero comparire nel messaggio.

Calcolo $\phi (n)$$\phi (n)$ e scelgo un intero $e$$e$ con $M.C.D.(e,\phi (n))=1$$M.C.D.(e,\phi (n))=1$. Supponiamo che sia vera la seguente proprietà $\ast$$\ast$:

$$t^{k\phi (n)+1}\equiv t\mod n\,\forall t\in [0,\dots ,n-1],\,\forall k\in \mathbb {Z} .$$

$$t^{k\phi (n)+1}\equiv t\mod n\,\forall t\in [0,\dots ,n-1],\,\forall k\in \mathbb {Z} .$$

Prendo una soluzione $b$$b$ della congruenza

$$xe\equiv 1\mod \phi (n)$$

$$xe\equiv 1\mod \phi (n)$$

tale soluzione esiste per come è stato scelto $e$$e$, coprimo con $\phi (n)$$\phi (n)$.

Le informazioni pubbliche sono $n$$n$ e $e$$e$. Tutto il resto ($b$$b$) rimane privato in mano all'unica persona che può decifrare il messaggio.

Cifratura

Preso $m$$m$ si calcola $m^{e}$$m^{e}$ e si prende l'unico numero $m^{\bar {e}}$$m^{\bar {e}}$ compreso tra 0 e $n-1$$n-1$ congruo a $m^{e}$$m^{e}$ modulo $n$$n$. Trasmetto $m^{\bar {e}}$$m^{\bar {e}}$.

Decifratura

Solo chi conosce $b$$b$ può decifrare il messaggio.

Calcolo $(m^{\bar {e}})^{b}$$(m^{\bar {e}})^{b}$ e prendo l'unico intero compreso tra 0 e $n-1$$n-1$ a cui è congruo. Questo numero sarà $m$$m$.

Esempio (392)

INFORMAZIONI PRELIMINARI: Prendo $n=15$$n=15$, $e=3$$e=3$, e calcolo $\phi (n)=\phi (3)*\phi (5)=8$$\phi (n)=\phi (3)*\phi (5)=8$.

Prendo la soluzione $b$$b$ di $ex\equiv 1\mod \phi (n)$$ex\equiv 1\mod \phi (n)$, cioè di

$$3x\equiv 1\mod 8,$$

$$3x\equiv 1\mod 8,$$

in questo caso $b=3$$b=3$.

CIFRATURA: Supponiamo $m=7$$m=7$. Allora cerco $m^{\bar {e}}$$m^{\bar {e}}$ tale che $m^{e}\equiv m^{\bar {e}}\mod n$$m^{e}\equiv m^{\bar {e}}\mod n$ e $0<m^{\bar {e}}<n-1$$0<m^{\bar {e}}<n-1$, cioè

$$7^{3}\equiv \dots \mod 15,$$

$$7^{3}\equiv \dots \mod 15,$$

$$7^{2}\equiv 4\mod 15,\longrightarrow \,7^{3}\equiv 28\mod 15$$

$$7^{2}\equiv 4\mod 15,\longrightarrow \,7^{3}\equiv 28\mod 15$$

$$28\equiv 13\mod 15,\,\longrightarrow \,7^{3}\equiv 13\mod 15,\,{\hbox{per transitività delle congruenze}}.$$

$$28\equiv 13\mod 15,\,\longrightarrow \,7^{3}\equiv 13\mod 15,\,{\hbox{per transitività delle congruenze}}.$$

quindi $m^{\bar {e}}=13$$m^{\bar {e}}=13$. Spedisco $13$$13$, che diventa la parola cifrata.

DECIFRATURA: Cerco il numero $m$$m$ risolvendo $(m^{\bar {e}})^{b}\equiv m\mod n$$(m^{\bar {e}})^{b}\equiv m\mod n$, con $0\leq m\leq n-1$$0\leq m\leq n-1$.

$$13^{3}\equiv \dots \mod 15$$

$$13^{3}\equiv \dots \mod 15$$

$$13^{2}\equiv 4\mod 15$$

$$13^{2}\equiv 4\mod 15$$

$$\longrightarrow \,13^{3}\equiv 13*4\mod 15$$

$$\longrightarrow \,13^{3}\equiv 13*4\mod 15$$

$$52\equiv 7\mod 15$$

$$52\equiv 7\mod 15$$

$$\longrightarrow 13^{3}\equiv 7\mod 15.$$

$$\longrightarrow 13^{3}\equiv 7\mod 15.$$

quindi $m=7$$m=7$, come deve.

 

Dimostrazione della decifratura

Devo mostrare che effettivamente $(m^{\bar {e}})^{b}\equiv m\mod n$$(m^{\bar {e}})^{b}\equiv m\mod n$, dove $m^{\bar {e}}$$m^{\bar {e}}$ è il messaggio cifrato.

Dimostrazione

Siccome $m^{\bar {e}}\equiv m^{e}\mod n$$m^{\bar {e}}\equiv m^{e}\mod n$, si ha

$$(m^{\bar {e}})^{b}\equiv m^{eb}\mod n$$

$$(m^{\bar {e}})^{b}\equiv m^{eb}\mod n$$

$b$$b$ è stata costruita come soluzione della congruenza $be\equiv 1\mod \phi (n)$$be\equiv 1\mod \phi (n)$, allora $be=1+\phi (n)k$$be=1+\phi (n)k$ con $k$$k$ intero. Segue quindi che

$$m^{eb}\equiv m^{1+\phi (n)k}\mod n$$

$$m^{eb}\equiv m^{1+\phi (n)k}\mod n$$

e per la proprietà $\ast$$\ast$$m^{1+\phi (n)k}\equiv m\mod n$$m^{1+\phi (n)k}\equiv m\mod n$, cioè, per transitività, $(m^{\bar {e}})^{b}\equiv m\mod n$$(m^{\bar {e}})^{b}\equiv m\mod n$.

 

Questo metodo crittografico funziona per il seguente motivo. Non conoscendo $b$$b$, per trovarlo bisogna risolvere la congruenza $ex\equiv 1\mod \phi (n)$$ex\equiv 1\mod \phi (n)$ e quindi bisogna conoscere $\phi (n)$$\phi (n)$, quindi chi ha $\phi (n)$$\phi (n)$ riesce a trovare $b$$b$. Per trovare $\phi (n)$$\phi (n)$ bisogna fattorizzare $n$$n$ in numeri primi, e la difficoltà sta proprio in questo, infatti non si conosce nessun algoritmo polinomiale che permetta di fattorizzare $n$$n$ in numeri primi. Quindi una persona che non conosce $b$$b$, pur conoscendo $e,n$$e,n$, non riesce a ricavare $\phi (n)$$\phi (n)$ con facilità e quindi ha difficoltà nel decifrare il messaggio.

Per fare in modo che $\phi (n)$$\phi (n)$ sia difficile da ottenere, $n$$n$ non può essere scelto primo. In genere $n$$n$ viene preso come prodotto di due numeri primi di 300 cifre.

Validità della proprietà ast

Proposizione (393 proprietà $\ast$)

Sia $n$$n$ un numero intero senza quadrati, cioè che non sia divisibile per il quadrato di un numero primo. Allora $t^{k\phi (n)+1}\equiv t\mod n$$t^{k\phi (n)+1}\equiv t\mod n$ per ogni $t$$t$ e per ogni $k$$k$. (le ipotesi implicano anche un'ulteriore restrizione sulla scelta di $n$$n$, che deve essere scelto senza quadrati)

 

Dimostrazione

Divido la dimostrazione in due casi:

• Caso 1: $M.C.D.(t,n)=1$$M.C.D.(t,n)=1$

Per il teorema di Eulero-Fermat, sappiamo che $t^{\phi (n)}\equiv 1\mod n$$t^{\phi (n)}\equiv 1\mod n$, allora elevando alla $k$$k$:

$$t^{k\phi (n)}\equiv 1\mod n$$

$$t^{k\phi (n)}\equiv 1\mod n$$

moltiplicando per $t$$t$:

$$t^{k\phi (n)+1}\equiv t\mod n.$$

$$t^{k\phi (n)+1}\equiv t\mod n.$$

• Caso 2: $n=p_{1}*p_{2}*\dots *p_{l}$$n=p_{1}*p_{2}*\dots *p_{l}$ dove i $p_{i}$$p_{i}$ sono primi distinti.

$$\phi (n)=(p_{1}-1)*(p_{2}-1)*\dots *(p_{l}-1)$$

$$\phi (n)=(p_{1}-1)*(p_{2}-1)*\dots *(p_{l}-1)$$

Mostro prima che $t^{k\phi (n)+1}\equiv t\mod p_{1}$$t^{k\phi (n)+1}\equiv t\mod p_{1}$.

Se $t$$t$ è coprimo con $p_{1}$$p_{1}$, siccome $k\phi (n)$$k\phi (n)$ è multiplo di $p_{1}-1$$p_{1}-1$, applicando ancora Eulero-Fermat si ottiene:

$$t^{k\phi (n)}\equiv 1\mod p_{1}$$

$$t^{k\phi (n)}\equiv 1\mod p_{1}$$

$$\longrightarrow \,t^{k\phi (n)+1}\equiv t\mod p_{1}$$

$$\longrightarrow \,t^{k\phi (n)+1}\equiv t\mod p_{1}$$

Quando invece $p_{1}\mid t$$p_{1}\mid t$, $t\equiv 0\mod p_{1}$$t\equiv 0\mod p_{1}$, perché è multiplo di $p_{1}$$p_{1}$, quindi l'equazione da dimostrare diventa $0\equiv 0\mod p_{1}$$0\equiv 0\mod p_{1}$ che è vera.

Per ora abbiamo dimostrato che $t^{k\phi (n)+1}\equiv t\mod p_{i}$$t^{k\phi (n)+1}\equiv t\mod p_{i}$, per $i=1,\dots ,l$$i=1,\dots ,l$. equivalentemente

$$p_{i}\mid t^{k\phi (n)+1}-t,\,\forall i$$

$$p_{i}\mid t^{k\phi (n)+1}-t,\,\forall i$$

allora anche il prodotto dei primi divide il secondo membro, cioè

$$p_{1}*p_{2}*\dots *p_{l}\mid t^{k\phi (n)+1}-t$$

$$p_{1}*p_{2}*\dots *p_{l}\mid t^{k\phi (n)+1}-t$$

cioè $n\mid t^{k\phi (n)+1}-t$$n\mid t^{k\phi (n)+1}-t$, cioè vale la proprietà $\ast$$\ast$. (solo in quest'ultimo passaggio si sfrutta il fatto che $n$$n$ è senza quadrati)