Archivio della categoria: Informatica

I Numeri Primi, il World Wide Web e la Crittografia

Ogni qualvolta eseguite una transazione commerciale su internet, vi affidate alla teoria matematica dei numeri primi per mantenere la transazione stessa in condizioni di sicurezza: cerchiamo di capire come.

LA STORIA

Dal momento in cui la gente cominciò ad inviarsi messaggi emerse il seguente problema: come impedire che una persona non autorizzata si impadronisca  del messaggio e venga a conoscenza del suo contenuto? La risposta sta nel codificare (Criptare) il messaggio stesso.

Oggi i sistemi di crittografia consistono essenzialmente di due componenti: una procedura di crittografia e una “chiave”. La prima è solitamente un programma per computer oppure un chip ad hoc, la seconda, la chiave, è un numero segreto. Per crittografare il messaggio, il sistema necessita non solo del messaggio stesso, ma anche della chiave.  Nei primi sistemi di crittografia con chiave, mittente e ricevente concordavano in anticipo una chiave segreta, che poi usavano per scambiarsi messaggi; ovviamente una situazione del genere non è adatta al commercio su internet, contesto nel quale spesso il messaggio deve arrivare dall’altra parte del mondo per raggiungere un destinatario che il mittente non ha mai incontrato di persona.

Queste premesse portarono alla nascita dell’attuale crittografia a chiave pubblica o asimmetrica nella quale la cifratura richiede non una ma due chiavi: una per la codifica, chiamata chiave pubblica, che è a disposizione di chiunque e ci permette di criptare il messaggio ma non di decriptarlo per inviarlo al destinatario interessato; l’altra per la decodifica del messaggio, chiamata chiave privata, che solo il legittimo destinatario del messaggio conosce. Questo è il funzionamento alla base dell’odierno standard di Crittografia. Vediamo quali concetti matematici ne sono alla base.

LA MATEMATICA CHE C’E’ DIETRO

Oggi la cifratura RSA salvaguarda gran parte delle transazioni che avvengono su Internet. La cosa straordinaria è che la matematica che rende possibile questo sistema di crittografia a chiave pubblica è decisamente semplice. Tutto si basa su quattro concetti matematici: Numero Primo, Fattorizzazione, Aritmetica Modulare e Piccolo teorema di Fermat.

1) Un numero primo è un numero naturale che sia divisibile solo per se stesso e per uno;

2) Fattorizzare un numero significa trovare un insieme di numeri tali che il loro prodotto sia il numero scelto in partenza; se ad esempio scegliamo il numero 6 (che non è primo) allora i suoi fattori sono 3 e 2 poiché 3×2=6 . Riuscite ad immaginare già da ora quanto più complesso sarebbe fattorizzare il numero 1544782 (?!?)

3) L’aritmetica modulare è un ramo della matematica che però conosciamo noi tutti molto bene, la usiamo tutte le volte che controlliamo l’ora sul nostro orologio, proprio per questo è anche chiamata aritmetica dell’orologio. Per esempio, in un orologio di 12 ore sappiamo che 9 + 5 = 2 poiché 5 ore dopo le 9 del mattino saranno le 2 del pomeriggio secondo la regola 9 + 5 = 14 allora 14/12 = 1 resto 2 e il resto è quello che dobbiamo prendere in considerazione per avere la nostra uguaglianza.

4) Piccolo teorema di Fermat, non facciamoci spaventare dal nome, afferma semplicemente che, se si prende un “orologio” (di quelli visti al punto precedente) con un numero primo di ore, e prendo un numero su questo calcolatore ad orologio e lo moltiplico per se stesso un numero primo di volte, si ottiene sempre il numero da cui si è partiti. Questo sarà successivamente necessario per la decodifica del messaggio, in particolare con la formula generalizzata del teorema (TFE): (p-1) x (q-1) +1 = D quindi D è il passo di ripetizione dell’orologio. Invece, p e q sono due numeri primi dove N è il loro prodotto (p x q=N) ed è la chiave pubblica utilizzata per la codifica sul Web.

IL METODO

La Codifica

Quando un cliente piazza un ordine sul sito di un’azieda, l’azienda gli comunica quante ore usare nel suo calcolatore ad orologio. Per scegliere questo numero di ore, l’azienda prende due grandi numeri primi, p e q, ciascuno composto da 60 cifre circa (ma posso essere anche di più). Quindi li moltiplica per ottenere un terzo numero, N=p x q. Il numero di cifre dell’orologio risulterà perciò enorme, fino ad un massimo di 120 cifre. Nonostante il numero N sia reso pubblico, i due numeri primi p e q che lo compongono sono segreti.

Dopodiché ogni cliente riceve un secondo numero E chiamato numero di codifica ed è pubblico proprio come lo è N, il numero di ore sul “quadrante” del calcolatore ad orologio. Per cifrare il proprio numero di carta di credito C, il cliente lo eleva alla potenza E, cioè moltiplica il numero della carta di credito per se stesso E volte sul calcolatore a orologio reso pubblico dal sito web. Immaginate che E sia il numero di scozzate che un prestigiatore esegue per nascondere, nel mazzo composto di N carte, la carta da voi scelta, cioè il numero della vostra carta di credito.

La Decodifica

Che cosa rende questa procedura tanto sicura? Dopo tutto qualsiasi hacker può vedere il numero cifrato della carta di credito mentre viaggia nel cyberspazio, e può cercare la chiave pubblica dell’azienda (N per intenderci) ed anche l’istruzione di elevamento alla E (C alla E modulo N). Tutto quello che l’hacker deve fare per decifrare il codice è trovare un numero che, moltiplicato E volte per se stesso nell’oroglogio di N ore, fornisce il numero di carta di credito. Ma questo è molto, molto difficile. La crescita, mentre si moltiplica per se stesso il numero di carta di credito nella codifica, non è lineare nel calcolatore ad orologio e si perde subito il punto di partenza a causa dell’utilizzo di numeri primi. Passare in rassegna tutte le possibili soluzioni con un computer significherebbe impiegare molte centinaia di anni.

L’azienda, dal canto suo, riesce a recuperare il numero della carta di credito grazie al piccolo teorema di Fermat, infatti, moltiplicando il numero cifrato della carta di credito per se stesso altre D volte, grazie all’andamento periodico scoperto dal matematico (Fermat appunto), si riesce a ritornare al punto di partenza cioè il numero NON cifrato della carta di credito. Ma D è un numero ricavabile solo se si conoscono i due numeri primi p e q  secondo la formula vista in precedenza quando si parlava del piccolo teorema di Fermat (Punto 4).

CONCLUSIONI: L’IMPORTANZA DELL’IPOTESI DI RIEMANN

Come abbiamo visto, il solo modo per sapere quanto bisognerà aspettare per vedere la sequenza ricominciare su un orologio con N= p x q ore sul quadrante è conoscere i valori di entrambi i numeri primi p e q attraverso i quali ricavare la chiave di decodifica D. Tuttavia, sebbene i due numeri p e q siano stati tenuti segreti, il loro prodotto N è stato reso pubblico. La sicurezza della cifratura RSA si basa perciò sulla difficoltà di fattorizzare N. Difficoltà alla quale, si pensa, saprà rispondere la dimostrazione all’Ipotesi di Riemann.

APPROFONDIMENTI:

Per approfondire l’argomento, grazie alla cortesia di Cristiano Teodoro, a disposizione per il download trovate listato di codice e relativa spiegazione riguardante la generazione di chiavi private nell’algoritmo di criptatura RSA a chiave pubblica.

In effetti mi rendo perfettamente conto che è un’ardua impresa spiegare e divulgare in termini semplici una materia così ostica come è quella della crittografia. Confido in un vostro dialogo costruttivo in merito. Se volete, i commenti sono a disposizione!

Eliminare la protezione Anti-DVD e potenziare gli Screenshot su Mac OsX

Chi di voi si è trovato a lavorare o anche semplicemente divertirsi con un Mac saprà che in alcuni casi la cattura di una schermata su video (Screenshot) può risultare abbastanza antipatica. Si pesi, ad esempio, all’imposibilità di effettuare screenshots durante la riproduzione di DVD; una grave limitazione, in quanto la funzionalità è bloccata, in questo determinato caso, alla radice: se volessimo effettuare uno screenshot di una pagina web del nostro browser durante la riproduzione di un determinato film messo su dvd saremmo costretti a chiudere il player e poi procedere con lo “scatto”, a maggior ragione, la cosa diventa limitante se volessimo scattare un’istantanea di una determinata scena del nostro DVD durante la sua riproduzione.

A tal proposito, possiamo raggirare il problema andando ad utilizzare direttamente il prompt dei comandi e facendo uso delle opzioni che Darwin, la versione Unix sfruttata per il core di Mac OsX, ci mette a disposizione:

1) Inserite il DVD nel vostro lettore ed aprite il DVD Player se non parte in automatico (Applicazioni -> DVD Player). Selezionate la massima dimensione per il vostro video o ciò che preferite e l’inizio della scena alla quale siete interessati.

2) Aprite il Terminale (Applicazioni -> Utility -> Terminale). Digitate nel terminale:

screencapture -i ~/Desktop/dvd.png

Il puntatore del mouse dovrebbe commutare in uno strumento di selezione, premendo la barra spaziatrice dovrebbe commutare in una “Macchinetta Fotografica” la quale evidenzia ogni singola finestra, cliccate sulla finestra del vostro Player DVD. Una volta cliccato, verrà creato un file denominato “dvd.png” e sarà visibile sulla vostra scrivania.

Qui trovate la lista completa delle opzioni per il comando screencapture.

Qui trovate la lista dei comandi Unix per Darwin.

La vita vista da un informatico: L’ultima lezione di Randy Pausch

All’incirca un mese fa, durante la mia ultima full-immersion di studio, ho avuto modo di leggere questo libro di cui avevo già accennato di volerne parlare.

Randy Pausch è stato uno tra i fondatori e più grandi esperti al mondo di realtà virtuale e grafica computerizzata nonchè professore di informatica alla Carnegie Mellon University. Nell’agosto del 2007 scopre che il suo cancro al pancreas sta avendo la meglio su di lui e gli restano pochi mesi di vita. Prima di lasciare l’università per dedicarsi completamente alla sua famiglia, decide di tenere la sua ultima lezione, con l’obiettivo finale di concedere, a modo suo, un’eredità concreta, una sorta di lascito per i suoi figli di 1, 2 e 5 anni. Un libro bellissimo, in cui Pausch non si sofferma sulla tragedia dell’esistenza in lui di un male che lo porterà alla morte ma, al contrario, trattasi di un commosso ed entusiasmante inno alla vita.

Mi sono appassionato nella lettura dei suoi modi assolutamente unici di insegnamento, delle sue tecniche di “approccio alla vita” del tutto singolari e della sua sempre ottimizzata gestione del tempo(sapendo di averne poco a disposizione): si pensi che per stare in compagnia dei suoi figli il più a lungo possibile durante la giornata, scrisse questo suo libro in bicicletta, o meglio, dettò ogni singolo paragrafo via cellulare durante la sua ora quotidiana di moto che gli era stata imposta per aiutarlo nella cura contro il suo cancro, al suo amico giornalista Jeffrey Zaslow che successivamente si occupò della stesura dello stesso!

Il libro è molto divertente, al contrario di quanto si possa credere, la sua ultima lezione nel Settembre 2007 fu anche registrata e se avete un po’ di dimestichezza con l’inglese potete dare uno sguardo ai primi minuti per comprendere che clima divertente e magico si era creato all’interno dell’aula gremita di gente.

Randy Pausch è scomparso lo scorso 25 Luglio, in quel giorno ero in macchina e ascoltavo il radiogiornale, ero di ritorno da Ancona. Nella gioia di quel momento ebbi modo di ascoltare la brutta notizia, buttata lì, quasi senza importanza, ed avvertii un brivido: nel giorno del mio ultimo esame una parte di storia dell’informatica era venuta a mancare definitivamente.

Non so come si fa a non divertirsi. Sto per morire e mi diverto. E ho intenzione di continuare a divertirmi per ogni singolo giorno che mi resta. Perchè non c’è altro modo di vivere.

[Randy Pausch]