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 abbastanza grande, e vogliamo trasmettere dove :

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


Calcolo e scelgo un intero con . Supponiamo che sia vera la seguente proprietà :

Prendo una soluzione della congruenza

tale soluzione esiste per come è stato scelto , coprimo con .


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

Cifratura
Preso si calcola e si prende l'unico numero compreso tra 0 e congruo a modulo . Trasmetto .
Decifratura
Solo chi conosce può decifrare il messaggio.

Calcolo e prendo l'unico intero compreso tra 0 e a cui è congruo. Questo numero sarà .


Esempio

INFORMAZIONI PRELIMINARI: Prendo , , e calcolo .


Prendo la soluzione di , cioè di

in questo caso .


CIFRATURA: Supponiamo . Allora cerco tale che e , cioè

quindi . Spedisco , che diventa la parola cifrata.


DECIFRATURA: Cerco il numero risolvendo , con .

quindi , come deve.

 

Dimostrazione della decifratura

Devo mostrare che effettivamente , dove è il messaggio cifrato.

Dimostrazione

Siccome , si ha

è stata costruita come soluzione della congruenza , allora con intero. Segue quindi che
e per la proprietà , cioè, per transitività, .

 



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


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

Validità della proprietà ast

Proposizione

Sia un numero intero senza quadrati, cioè che non sia divisibile per il quadrato di un numero primo. Allora per ogni e per ogni . (le ipotesi implicano anche un'ulteriore restrizione sulla scelta di , che deve essere scelto senza quadrati)

 
Dimostrazione

Divido la dimostrazione in due casi:

  • Caso 1:

Per il teorema di Eulero-Fermat, sappiamo che , allora elevando alla :

moltiplicando per :

  • Caso 2: dove i sono primi distinti.

Mostro prima che .


Se è coprimo con , siccome è multiplo di , applicando ancora Eulero-Fermat si ottiene:

Quando invece , , perché è multiplo di , quindi l'equazione da dimostrare diventa che è vera.


Per ora abbiamo dimostrato che , per . equivalentemente

allora anche il prodotto dei primi divide il secondo membro, cioè
cioè , cioè vale la proprietà . (solo in quest'ultimo passaggio si sfrutta il fatto che è senza quadrati)

 
 PrecedenteSuccessivo