Ingegneria Energetica - Analisi e Geometria 1

Il sistema crittografico RSA

Divided by topic

UN'APPLICAZIONE INFORMATICA DELL'ARITMETICA MODULARE: IL SISTEMA CRITTOGRAFICO RSA Fin dall'antichita si e sentita l'esignza di trasmettere messaggi in modo nascosto: per questo nasce la crittograa. Fino a pochi decenni fa, i sistemi crittograci erano basati su sistemi di codica e decodica dei messaggi a chiave simmetrica: chi inviava i mes- saggi e chi li riceveva aveva a disposizione la stessa chiave. Il sistema crittograco RSA attualmente in uso si basa invece sul principio dellachiave asimmetrica. Il nome RSA deriva dalle iniziali di Ronald Rivest, Adi Shamir e Leonard Adleman che lo hanno rea- lizzato (anche se James Ellis e Cliord Cocks avevano in precedenza trovato un sistema basato sugli stessi principi, ma avevano tenuto segreto il risultato della loro scoperta). Prima di tutto le lettere vengono rappresentate da numeri in codice. Per esempio Nel- l'American Standard Code for Information Interchange le lettere vengono rappresentate dai numeri da 065 a 090. Per esempio la parola ALA viene scritta come: 065076065: Ogni utenteBdeve scegliere una coppia di numeri (n B; e B) in modo che n Bsia il prodotto di due numeri primi distinti molto grandi,n B= p B
q B, e inoltre M :C:D:(e B; p B 1) = 1; M :C:D:(e B; q B 1) = 1: La coppia (n B; e B) e pubblica, ma non e pubblica la scomposizione di n B. La segretezza di questo sistema sta proprio in questo:Bdeve costruiren Bscegliendo due numeri primi pBe q Bmolto grandi (anche di 13-14 cifre) e moltiplicandoli. Come si fa a trovare un numero primo? si prende un numero disparime si sottopone a certi test di primalita: se un test viene superato va bene, altrimenti si prova conm+ 2. La coppia (n B; e B) da aBla chiave segreta per decodicare i messaggi: si tratta del numerod B, soluzione della congruenza lineare (1)e Bx 1(mod'(n B)) e tale che 0< d B< ' (n B) :Sicuramente (3) ammette soluzione visto che '(n B) = ( p B 1)(q B 1) e quindiM :C:D:(e B; ' (n B)) = M :C:D:(e B; (p B 1)(q B 1)) = 1: Inoltre questa soluzione e unica (mod'(n B)) :QuindiBe l'unico che puo conoscere la chiaved Btale che: eBd B 1(mod'(n B)) ;0< d B< ' (n B) perche soltantoBconosce'(n B). Si supponga che l'utenteAdebba inviare il messaggioMall'utenteB. Allora consulta gli elenchi uciali e trova la coppia (n B; e B). Se il messaggio e piu lungo di n B, Apuo spezzareMin modo standard in piu messaggi. Quindi si puo supporre che M < nB; M :C:D: (M ; n B) = 1 : Il messaggio codicato cheAinvia aBeM0 tale che M0 Me B (modn B) : Il punto fondamentale e: (2)MM0 d B (modn B) ; che si dimostra usando il Teorema di Eulero. QuindiB, trovando una soluzione della congruenza linearexM0 d B (modn B), avra decodicato il messaggio. Il sistema RSA viene usato anche per l'autenticazione delle rme. L'utenteAmanda un messaggioMall'utenteBe lo fa seguire dalla propria rmaF, ma nella forma: M1 Fd A (modn A) ; 1 2 cioeAinviaM+M 1. Bnon riesce a codicare la seconda parte del messaggio, ma sa che proviene daAe ne deve controllare l'autenticita. Allora controlla che Me A 1 F(modn A) : Infatti, si prova cheMe A 1 (Fd A )e A =Fd Ae A F(modn A) : Esercizio 1.L'utenteAvuole inviare il messaggioM= 5 all'utenteB, la cui coppia identicativa e (n B= 77 ; e B= 13) : Allora soltantoBsa chen B= 11
7 e quindi'(n B) = '(11)'(7) = 10
6 = 60. Pertanto soluzioned B< 60 della congruenza lineare (3) 13x1(mod60) e la chiave per la decodica dei messaggi. Per risolvere (3), si puo usare l'algoritmo delledivisioni successive: 60 = 13
4 + 8 13 = 8
1 + 5 8 = 5
1 + 3 5 = 3
1 + 2 3 = 2
1 + 1 2 = 2
1 + 0: Quindi: 1 = 3 + 2
(1) = 3 + (5 + 3(1))
(1) = 3 + 5
(1) + 3 = 3
2 + 5
(1) = (8 + 5
(1))
2 +
(1) = 8
2 + 5
(2) + 5
(1) = 8
2 + 5
(3) = 8
2 + (13 + 8
(1))
(3) = 8
2 + 13
(3) + 8
3 = 8
5 + 13
(3) = (60 + 13
(4))
5 + 13
(3) = 60
5 + 13
(23); Allora 1 = 13
(23) + 60
5 e quindi23 e una soluzione. La piu piccola soluzione positiva e23 + 60 = 37, per cui la chiave e dB= 37 : L'utenteAdovra inviare aBil messaggio M0 Me B (modn B) : e quindi deve trovarextale che x513 (mod77): Per esempio, usando una comune calcolatrice, si vede che 56 = 15:625 e che 15:625 = 202
77 + 71; ovvero 15:62571(mod77):Quindi 513 = 56
2+1 = (56 )2
5 = (15:625)2
5712
5(mod77): Sempre eettuando il calcolo su una calcolatrice, si ha: 712
5 = 25:205 = 327
77 + 26, per cui 712
526(mod77): AlloraAinvia aBil messaggioM0 = 26. A questo puntoBdeve decodicare il messaggio ricevuto usando la sua chiaved B= 37, che solo lui conosce, e usando (2). Quindi deve cercarextale chex2637 (mod77):Si vede che 266 = 308:915:776 = 4:011:893
77 + 15, per cui 266 15(mod77):Allora: 2637 = 266
6+1 = (266 )6
26156
26(mod77): 3 D'altra parte 156 = 11:390:625 e 156
26 = 296:156:250 = 3:846:185
77 + 5 e quindi 2637 5(mod77); e quindiBha decodicato il messaggioM0 .