Il sistema crittografico RSA

Pagina 1

UN’APPLICAZIONE INFORMATICA DELL’ARITMETICA MODULARE: IL SISTEMA CRITTOGRAFICO RSA Fin dall’antichit` a si ` e sentita l’esignza di trasmettere messaggi in modo nascosto: per questo nasce la crittografia. Fino a pochi decenni fa, i sistemi crittografici erano basati su sistemi di codifica e decodifica dei messaggi a chiave simmetrica: chi inviava i mes- saggi e chi li riceveva aveva a disposizione la stessa chiave. Il sistema crittografico RSA attualmente in uso si basa invece sul principio della chiave 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 Clifford 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 utente B deve scegliere una coppia di numeri ( nB, eB) in modo che nB sia il prodotto di due numeri primi distinti molto grandi, nB = pB · qB, e inoltre M.C.D.(eB, pB − 1) = 1, M.C.D. (eB, qB − 1) = 1. La coppia (nB, eB) ` e pubblica, ma non ` e pubblica la scomposizione dinB. La segretezza di questo sistema sta proprio in questo: B deve costruire nB scegliendo due numeri primi pB e qB molto grandi (anche di 13-14 cifre) e moltiplicandoli. Come si fa a trovare un numero primo? si prende un numero dispari m e si sottopone a certi test di primalit` a: se un test viene superato va bene, altrimenti si prova con m + 2. La coppia ( nB, eB) d` a aB la chiave segreta per decodificare i messaggi: si tratta del numero dB, soluzione della…