martedì 17 maggio 2016

RSA: sicurezza in una calcolatrice!

Avete mai sentito parlare di RSA? Non ancora? Allora siete capitati nel posto giusto!
Oggi vi spiegheremo cosa è e come funziona!

Prima però, dobbiamo parlare di crittografia: l' RSA è infatti un metodo crittografico che permette a me e a voi e a chiunque ne faccia uso di trasmettere i propri dati in maniera sicura su internet, sul telefonino,  e ovunque vogliate! Per applicarla bastano solamente un foglio di carta e una penna! Aiutati con una semplice calcolatrice oggi vi sveleremo i segreti di questo metodo crittografico, ancora così tanto usato nei sistemi bancari e nei servizi web.

Se vi siete incuriositi dell'argomento, continuate a leggerci!


Che cosa è la crittografia? Per rispondere a questa domanda, vi rimandiamo a questo nostro capitolo che approfondisce in maniera speriamo esaustiva ogni vostro dubbio riguardo l'argomento!

Dunque iniziamo!

La dicitura "RSA" è un acronimo dei nomi degli inventori di tale metodo crittografico, "Ronald Rivest, Adi Shamir e Leonard Adleman" che furono i matematici dietro "l'idea" nel 1977: il metodo si basa sull'algebra modulare e su uno scambio di chiavi, per questo viene anche chiamato "metodo crittografico a chiavi pubbliche". Le chiavi sono formate da due coppie di due numeri ciascuna, una coppia serve per codificare il messaggio l'altra per decodificarlo. La scelta dei numeri deve essere effettuata però molto accuratamente, e non deve essere casuale! Occorre seguire determinate regole matematiche in maniera assolutamente precisa.

Prima ci occorrono alcune nozioni di algebra modulare necessarie alla spiegazione del metodo, in particolare ci occorre conoscere una funzione, chiamata "funzione di Eulero"  o "$\phi$ di Eulero" che non fa altro che calcolare quanti numeri naturali ci sono sotto un certa soglia coprimi con il valore scelto: per esempio, se volessimo calcolare la funzione di Eulero di 11, il risultato che otterremmo sarebbe uguale a 10, poichè ci sono esattamente 10 numeri coprimi con 11 (1,2,3,4,5,6,7,8,9,10 .. tutti questi hanno $MCD(n,11)=1$), mentre se scegliessimo per esempio 10 come soglia, otterremmo il valore di 4 (1,3,7,9 sono infatti i soli numeri coprimi con 10). La $\phi(x)$ ha un'importante proprietà: se x è primo, allora $\phi(x)=(x-1)$, altrimenti se x non è primo, per esempio $x=ab,\text{con a e b due numeri primi}$, allora $\phi(x)=\phi(ab)=(a-1)(b-1)$. Questa funzione ci tornerà estremamente utile nel seguito.

Il primo numero che compone una chiave deve essere, per forza, un prodotto di due primi ( per alcune info sui numeri primi, click!), chiamiamolo $cod_{1}$.

Si sceglie adesso un numero arbitrario che sia
  • coprimo con $\phi(cod_{1})$ 
  • e più piccolo di $\phi(cod_{1})$,
questo lo chiameremo $cod_{2}$.
Tale numero infatti costituirà una delle due coppie delle chiavi a noi necessarie per crittografare (o decrittare a seconda di come ci piace di più) il nostro messaggio che vogliamo trasmettere. Per ultimare il nostro "mazzo di chiavi" ci occorre ancora l'ultimo pezzetto: per decidere $cod_{3}$, bisogna calcolarlo in maniera tale che $cod_{2}*cod_{3}\equiv1(\textrm{mod}\ \phi(cod_{1}))$ e per farlo qui ci occorre una bella calcolatrice e un po' di pazienza ;) anche se in realtà per trovare l'inverso di un numero in algebra modulata ci potrebbero venir utili alcuni strumenti... ma non è qui il luogo adatto per parlarne, magari in un prossimo post!

Una volta trovato anche l'ultimo pezzetto, abbiamo le chiavi pronte!
Chiave A={$cod_{1},cod_{2}$}
Chiave B={$cod_{1},cod_{3}$}

Una chiave la dovremmo rendere pubblica a chi ci vuole scrivere, l'altra invece la terremo al sicuro da occhi indiscreti poiché sarà quella che ci permetterà di decodificare i messaggi! Per questo motivo, la RSA è anche detta "crittografia asimmetrica". Per usarle, basterà elevare il messaggio alla potenza di $cod_{2}$ modulato $cod_{1}$: in questa maniera si attua la codifica; per decodificarlo occorre fare la stessa operazione ma alla potenza di $cod_{3}$.

Facciamo un esempio pratico! A noi piace molto la praticità!!


Ad esempio, imbastiamo un gioco crittografico tra due persone, Alice e Bob. Entrambi hanno le loro personali Chiave A e Chiave B, e solo una di esse deve essere resa pubblica e nota all'altro, così che la loro missiva può avere inizio.
Alice ha:
Chiave pubblica A1={21, 5}
Chiave privata B1={21, 17}

Provate a verificare che $5*17\equiv 1 (\textrm{mod}\ \phi(21))$.

Bob ha:
Chiave pubblica  A2={33, 7}
Chiave privata B2={33, 3}

Verificate di nuovo che $7*3\equiv 1 (\textrm{mod}\ \phi(33))$.

Ora Alice e Bob si scambiano le due chiavi pubbliche: Alice conoscerà A2 e Bob conoscerà A1. Prima di avventurarci in parole e testi, facciamo prima una rapida verifica con un solo numero: Alice vuole dire a Bob l'ora in cui vedersi, le 19. Non le resta altro da fare che: $$19^{3} (\textrm{mod}\ 33)=6859(\textrm{mod}\ 33)=28 (\textrm{mod}\ 33)$$.

Avendo Bob ricevuto il numero 28, dovrà adesso decodificarlo per leggere il numero in chiaro facendo la stessa operazione di Alice, ma usando la sua chiave nascosta, in questo caso la Chiave B2:
$$28^7(\textrm{mod}\ 33)=28*28^2*28^{2^{2}}(\textrm{mod}\ 33)$$ $$=28*25*25^2(\textrm{mod}\ 33)=28*25*31(\textrm{mod}\ 33)=21700(\textrm{mod}\ 33)=19(\textrm{mod}\ 33)$$

Ed ecco riottenuto il messaggio in chiaro! Ora Bob sa a che ora incontrarsi con Alice!

Dato che sarebbe più interessante scambiarsi anche qualche parola oltre che a soli numeri, qui può intervenire la fantasia! Basta far corrispondere a ciascuna lettera dell'alfabeto un numero prefissato, ed ecco che otteniamo un set alpha-numerico che ci aiuta a tradurre il testo in numeri e la RSA ci aiuta a inviare questi numeri in maniera sicura, poichè qualunque sia il corpo del messaggio $$ciao^{cod_{2}^{cod_{3}}}(\textrm{mod}\  cod_{1})=ciao(\textrm{mod}\  cod_{1})$$ ovviamente se il testo rappresentato dal "ciao" si riesce a decifrare correttamente in numeri nonostante il modulo cod_{1}.

 L'unica debolezza del sistema RSA è il fatto che si possono trovare le chiavi private semplicemente scomponendo in fattori il primo numero della chiave pubblica, ma per dati importanti si usano numeri molto grandi, in modo che anche i più potenti computer impieghino anni per scomporli! Attenzione però: se si inventassero algoritmi estremamente più veloci di quelli di oggi per  la fattorizzazione, l'intero sistema crittografico basato sulla RSA cadrebbe in un battibaleno! Per il momento usiamo RSA come svago e divertiamoci a crittografare messaggi in modo semplice e astuto!
Questa è la nostra chiave pubblica:
${713, 19}$
Se vi va di usarla... fatecelo sapere ;)

Cosa ne pensate dell'articolo? Fatevi sentire nei commenti!


Nessun commento:

Posta un commento