COME TENERE UN SEGRETO

LA CRITTOGRAFIA DALLE ORIGINI

AL SISTEMA RSA

Cos'è la Crittografia?

Il termine Crittografia deriva dal greco "kryptòs"="nascosto" e "gráphein"="scrivere", assume quindi il significato di "Scrittura Nascosta". È la disciplina che studia i metodi necessari per rendere un messaggio comprensibile solamente ai destinatari della comunicazione.

Assieme alla crittografia nasce anche il desiderio di scoprire i messaggi apparentemente incomprensibili. La scienza che studia come decriptare le informazioni allo scopo di ricavarne il contenuto originario è la Crittoanalisi, parola che deriva dal greco "kryptòs" e "nalýein"= "risolvere".

Crittografia e Crittoanalisi appartengono ad una stessa scienza, la "Crittologia".

La crittografia ha per un'informazione lo stesso valore che ha una cassaforte per un bene materiale.

Oggi la crittografia ha la sua più ampia diffusione in campo informatico, dove vengono trasmesse molte informazioni anche delicate grazie all'efficienza dei sistemi crittografici informatici attuali.

Il primo utilizzo di sistemi crittografici risale al 1500 a.C. quando un antico vasaio si servì di un codice per tenere segreta la sua formula della ceramica invetriata.

Nel V secolo a.C. gli Spartani utilizzarono un cilindro di legno chiamato Scytala per cifrare i loro messaggi.

La crittoanalisi, invece, fu inventata dagli Arabi soltanto nel VIII - IX secolo d.C., dopo duemila anni di uso di sistemi per crittografia.

Nel 1587 Maria Stuarda, regina di Scozia era convinta che il suo codice fosse indecifrabile ma non fu così e pagò con la vita il suo errore.

Nel XVII secolo Antoine Rossignol e suo figlio inventarono il Grande Cifrario di Luigi XIV, che restò inviolato per duecento anni.

Nel XVIII secolo Vienna divenne famosa per l'abilità dei suoi crittanalisti, che lavoravano nella Camera Nera.

Nel 1812 l'invasione della Russia da parte di Napoleone fallì per il freddo dell'inverno e per l'abilità dei crittanalisti russi.

Nel 1844 fu inventato il codice Morse, utilizzato nella trasmissione dei messaggi al telegrafo.

Durante le elezioni presidenziali americane del 1876 si spedirono telegrammi in codice nel tentativo di manipolare il voto. I telegrammi vennero pubblicati su un giornale e furono decifrati soltanto due anni dopo.

Durante la Grande Guerra (1914-18) l'uso della radio per inviare messaggi li rese facili da intercettare, perciò i codici divennero sempre più importanti. Questo aiutò i crittanalisti offrendo loro un gran numero di messaggi da studiare. Ebbero un'enorme importanza nel corso del conflitto, infatti la decifrazione di un telegramma segnò l'entrata in guerra degli Stati Uniti d'America nel 1917.

Nella Seconda Guerra Mondiale un grande apporto fu dato dalla macchina appena inventata dai Tedeschi, Enigma, la cui forzatura contribuì alla vittoria degli Alleati.

Nel 1948 vennero inventati i codici a barre, oggi comunemente usati, da parte di Norman Woodland e Bernard Silver, prima ancora che esistesse la tecnologia per utilizzarli.

Oggi, infine, tutti noi usiamo continuamente codici segreti, a volte senza neanche accorgercene: ad esempio per mantenere segrete le informazioni della carta di credito quando si eseguono acquisti on line.

L'importanza della crittografia nelle due guerre mondiali

La I Guerra Mondiale fu la prima grande guerra dopo l'invenzione del telefono e della radio; questi mezzi di comunicazione, se da una parte consentirono una velocità di trasmissione dei messaggi praticamente istantanea, dall'altra furono irrimediabilmente esposti all'intercettazione da parte del nemico.

I primi a rendersi conto di questa nuova situazione furono i Francesi che, allo scoppio della guerra, disponevano già di un ben organizzato ed efficiente Ufficio cifra presso il Gran Quartier Generale dell'esercito in grado di decrittare i messaggi radio tedeschi sin dall'ottobre 1914.

Altrettanto ben preparati gli Austriaci che già nell'agosto 1914 riuscivano a decrittare i radiomessaggi russi che per la verità erano solo in parte cifrati.

Negli altri paesi, veri e propri Uffici cifra furono organizzati solo dopo l'entrata in guerra.

Assolutamente impreparati erano soprattutto i Russi che, all'inizio della guerra, non si preoccuparono neanche di cifrare i loro messaggi radio, come avvenne durante la battaglia di Tannenberg nell'agosto 1914 quando persino gli ordini operativi vennero trasmessi in chiaro: un formidabile regalo ai Tedeschi che intercettarono tutto.

I Tedeschi comunque riuscirono a decrittare i messaggi russi anche dopo che questi ultimi iniziarono a cifrare le loro comunicazioni radio; qualche successo lo ottennero anche nei confronti dei Francesi.

In Inghilterra Sir Alfred Ewing, capo dell'Ufficio crittologico della Marina Britannica, organizzò la cosiddetta "Room 40" dove si decrittavano migliaia di radiomessaggi della marina tedesca.

Il più noto di questi messaggi fu il 'telegramma Zimmermann' con il quale i Tedeschi offrivano un'alleanza ai Messicani in chiave anti-USA. Letto al Congresso degli Stati Uniti questo messaggio fu uno dei fattori che spinsero gli USA a entrare in guerra nel 1917.

Del tutto impreparati in campo crittologico erano gli Italiani che dovettero in un primo tempo appoggiarsi all'Ufficio cifra francese; solo in un secondo tempo fu costituito un Ufficio cifra autonomo sotto la guida di Luigi Sacco, che riuscì a forzare il cifrario campale austriaco, quello diplomatico e quello navale.

Paradossalmente però ci volle la disfatta di Caporetto del 1917 perché Sacco riuscisse a convincere gli alti comandi italiani ad abbandonare i vecchi cifrari che, come poi si seppe, venivano facilmente decrittati dagli Austriaci, e ad adottare quei nuovi più sicuri sistemi che avevano fino allora rifiutato perchè troppo complicati. Unica attenuante per questa incredibile leggerezza il fatto che gli alti comandi italiani, a differenza di quelli di altri paesi, evitarono sempre di trasmettere per radio i messaggi più importanti.

La possibilità di intercettare e decrittare i messaggi austriaci ebbe un'importanza non trascurabile nel 1918 per fronteggiare l'offensiva austriaca del Piave.

In definitiva fu proprio la Grande Guerra a far scoprire a molti Stati l'importanza della Crittografia, il cui ruolo risultò fondamentale nella II Guerra Mondiale.

Lo strumento crittografico più noto utilizzato durante la guerra fu la macchina Enigma, usata dai tedeschi e considerata a torto inattaccabile; solo molti anni dopo la fine della guerra si seppe che in effetti già nel 1932, prima ancora che Hitler arrivasse al potere, l'Ufficio cifra polacco aveva trovato il modo di forzare l'Enigma. Durante la guerra gli inglesi del progetto ULTRA continuarono a forzare sistematicamente i messaggi cifrati con l'Enigma e dal 1941 anche quelli cifrati con la più sofisticata macchina Lorenz.

Molte vittorie alleate ebbero alla base questa superiorità crittografica. I casi più noti sono la Battaglia di capo Matapan (marzo 1941), dove la disfatta della flotta italiana pare abbia avuto origine dal fatto che gli Inglesi avevano decrittato alcuni messaggi cifrati della Marina tedesca che fornivano l'esatta posizione della flotta italiana; lo Sbarco in Normandia (5-6 giugno 1944): Eisenhower e Montgomery erano in grado di leggere tutti i messaggi degli alti comandi tedeschi, che usavano la macchina Lorenz; ebbero così conferma che Hitler aveva creduto alla falsa notizia di un imminente sbarco Alleato nei pressi di Calais e aveva concentrato le sue migliori truppe in quella zona. Poterono, quindi, ordinare lo sbarco in Normandia sicuri che avrebbero incontrato ben poca resistenza.

Sul fronte del Pacifico gli Americani, sin dal 1940, avevano realizzato Magic, una macchina in grado di decrittare i messaggi giapponesi cifrati con la macchina Purple.

Un importante episodio fu la Battaglia delle Midway. L'ammiraglio Yamamoto, comandante della flotta giapponese, nel maggio 1942 preparò un piano per attaccare a sorpresa le isole Midway a est delle Haway. Gli Americani intercettarono i piani di Yamamoto e l'Ammiraglio Nimitz, comandante della flotta USA, fu in grado di preparare la battaglia conoscendo già fin nei dettagli i piani del nemico; fece, inoltre, trasmettere falsi piani americani usando un cifrario che sapeva essere stato forzato dai Giapponesi. L'effetto sorpresa si trasformò in un boomerang e la vittoria USA alle Midway fu quindi in buona parte dovuta alla superiorità crittologica.

Diversi storici, inoltre, tra cui il noto scrittore americano Gore Vidal, sostengono che gli Americani sapessero in anticipo, grazie a Magic, anche dell'attacco di Pearl Harbour e decisero di non impedirlo. Avevano infatti bisogno di un motivo forte per convincere la riluttante opinione pubblica americana della necessità di entrare in guerra e quell'attacco a tradimento dei Giapponesi fu ideale per questo scopo. Un'altra teoria più prudente sostiene che gli Americani sapessero che il Giappone stava per attaccare, ma non sapessero dove. Certo è che, al momento dell'attacco nella baia di Pearl Harbour, non ci fosse nemmeno una portaerei e in definitiva furono affondate solo alcune navi vecchie e di importanza non fondamentale per la guerra.

La crittografia classica

I primi metodi utilizzati per assicurare la segretezza dei messaggi sono decisamente insoliti.

Un esempio è il metodo scelto da Istico il quale, per incoraggiare Aristagora di Mileto a ribellarsi al re persiano, decide di far radere i capelli ad un suo servo, tatuargli il messaggio sulla testa e inviarlo una volta che gli siano cresciuti i capelli. Al suo arrivo basta soltanto raderlo di nuovo.

Le prime notizie sull'invio sicuro di messaggi risalgono ad Erodoto che racconta di metodi che vengono di solito indicati con l'espressione di steganografia, cioè scrittura nascosta. Demeratus scrive un messaggio su una tavola di legno e la invia ricoperta di cera. In questo modo può superare le sentinelle e basta sciogliere la cera per leggere il messaggio.

Altri esempi di steganografia si trovano nell'uso dell'inchiostro simpatico (succo di limone) oppure nei "micro punti", tecnica che consiste nel fotografare un documento segreto e ridurlo alle dimensioni di un punto stampato.

Tuttavia la sola steganografia non è in grado di garantire la reale segretezza di un messaggio.

Esistono due tipi di scrittura segreta:

• i codici, che sostituiscono intere parole con altre parole o gruppi di lettere
• i cifrari, che sostituiscono ciascuna lettera o ciascun suono con altre lettere o simboli, oppure cambiano l'ordine delle lettere.

Un famoso cifrario è il cifrario di Cesare che trasla tutte le lettere del messaggio di un certo numero prestabilito. Per esempio la A diventa D, la B si trasforma in E, C in F e così via. È una sostituzione monoalfabetica.

Il più semplice cifrario a sostituzione polialfabetica è il cifrario di Vigenere pubblicato nel 1586. Può essere considerato una generalizzazione del codice di Cesare. Scelta una parola chiave trasla tutte le varie lettere nell'alfabeto con la lettera di partenza della lettera della parola chiave corrispondente al posto occupato dalla lettera del messaggio.

Ad esempio:

La crittografia moderna

La storia della crittografia moderna inizia con la stesura del De Cifris di Leon Battista Alberti, che per primo insegnò a cifrare per mezzo di un disco cifrante con un alfabeto segreto da spostare a piacere ogni due o tre parole. È una trasformazione del quadrato di Vigenere in disco.

Lo sviluppo della crittografia moderna procede di pari passo con lo sviluppo informatico.

Nel ventesimo secolo vengono create macchine cifranti e decifranti, tra cui la più celebre è Enigma.

Enigma è una macchina simmetrica inventata nel 1918 dal tedesco Arthur Scherbius. Al suo interno ha tre rotori, o più nelle macchine successive; quando un operatore preme un tasto un segnale elettrico passa da rotore a rotore fino al rotore finale, il riflettore e quindi torna indietro fino a mostrare una lettera illuminata che è il carattere cifrato. La chiave dell'Enigma è la disposizione iniziale dei rotori; questa chiave veniva cambiata ogni 24 ore secondo una regola prefissata, la vera chiave segreta. Inoltre i tre (o più) rotori possono essere scambiati tra di loro, e quindi vi sono n! (3! = 6 nell'Enigma originale) disposizioni possibili, cosa che aumenta il numero di posizioni iniziali possibili.

I tedeschi erano convinti che l'Enigma fosse inattaccabile, ma questa fiducia era assai mal riposta. Già nei primi anni '30 un gruppo di matematici polacchi guidato da Marian Rejeski era riuscito a ricostruire la struttura dei rotori e a decrittarne i messaggi e fu continuamente forzata dal servizio crittografico inglese al quale partecipava anche il famoso matematico Alan Turing.

Nella crittografia moderna bisogna chiarire i concetti di:

Testo in chiaro (o "plaintext") indica il messaggio originale che ancora non è stato cifrato.

Testo Cifrato (o "ciphertext") è il termine tecnico relativo al risultato di un operazione di cifratura. Si riferisce quindi al messaggio crittografato.

Un Algoritmo di Cifratura è una serie di istruzioni che permettono di crittografare un testo in chiaro trasformandolo quindi in un testo cifrato.

Un Algoritmo di Decifratura è una serie di istruzioni che permettono di tornare al testo in chiaro partendo dal testo cifrato.

I metodi di crittografia moderna si dividono in crittografia simmetrica e asimmetrica.

La Crittografia Simmetrica

La Crittografia Simmetrica basa la propria sicurezza sull'utilizzo di una chiave.

Nella crittografia simmetrica con la parola "Chiave" si indica l'informazione che, se conosciuta, permette di cifrare e decifrare un messaggio.

Quando si vuole cifrare un testo mediante tecniche di crittografia simmetrica è quindi necessario scegliere un algoritmo di cifratura, determinare il testo da cifrare e stabilire una chiave che sarà necessario possedere al momento di decifrare il messaggio.

La struttura di un sistema crittografico simmetrico può quindi essere pensato in questo modo:

A(M,K) = C

A-1(C,K) = M

Dove A è l'algoritmo di cifratura, A-1 e l'algoritmo di decifratura, M è il testo in chiaro, C è il testo cifrato e K la chiave.

Da ciò si capisce che per avere una comunicazione sicura è necessario che solamente i legittimi destinatari del messaggio siano a conoscenza della chiave.

E' importante far notare che molto spesso in ambito informatico la lunghezza delle chiavi viene indicata in base al numero di bit che occupano per essere memorizzate in binario, raramente ci si riferisce alla dimensione in caratteri.

I più conosciuti metodi di crittografia simmetrica sono DES e IDEA.

DES Data Encryption Standard)  è un algoritmo di cifratura a blocchi sviluppato dalla IBM che è stato definito standard ufficiale dal governo degli Stati Uniti nel 1977.

La dimensione dei blocchi DES è di 64 bit e la chiave ha una dimensione di soli 56 bit.

È stato ormai soppiantato da sistemi più avanzati perchè con le sue caratteristiche può essere decodificato in meno di 24 ore.

IDEA International Data Encryption Algorithm) è anch'esso un algoritmo di cifratura a blocchi inventato nel 1991, ma utilizza una chiave di 128 bit per aumentare la sicurezza rispetto al DES.

Allo stato attuale è uno degli algoritmi a chiave simmetrica più utilizzati, ma è brevettato e la sua licenza, per le applicazioni commerciali, deve essere richiesta alla società che lo commercializza.

La Crittografia Asimmetrica

I metodi di crittografia asimmetrica risolvono il principale problema della crittografia simmetrica: la necessità di un canale sicuro per la trasmissione delle chiavi.

La crittografia asimmetrica ha due chiavi e quindi si basa su due diversi algoritmi di cifratura e decifratura. Una chiave è pubblica, disponibile a tutti e l'altra è privata, segreta, che deve essere conosciuta solo dal destinatario.

Il mittente, per criptare il messaggio, utilizza l'algoritmo basato sulla chiave pubblica del destinatario. Per questo motivo, viene chiamata anche crittografia a chiave pubblica.

Per decifrarlo, invece, è indispensabile conoscere la chiave privata, che non può essere ricavata da quella pubblica.

La crittografia asimmetrica funziona secondo il seguente schema:

Dal punto di vista matematico, lo schema della funzione è:

Vantaggi

La chiave pubblica può essere trasmessa tramite un canale insicuro, in quanto la sua conoscenza da parte di terzi non è sufficiente a mettere in pericolo la sicurezza dei dati crittografati con essa. Ciascuna chiave segreta resta sotto la responsabilità del solo utente proprietario

Deve esistere una coppia di chiavi per ogni possibile utente, ovvero per n utenti occorrono 2*n chiavi. Nei sistemi a chiave simmetrica, invece, deve esistere una chiave per ogni possibile coppia di utenti, perciò per n utenti occorrono (n* (n-1))/2

Svantaggi

Generalmente gli algoritmi asimmetrici sono molto più lenti da eseguire, rispetto a quelli simmetrici, quindi risulta poco agevole il loro uso per crittografare lunghi messaggi.

Caratteristiche

I crittosistemi a chiave pubblica consentono di garantire le seguenti caratteristiche:

• Confidenzialità (riservatezza)

Il messaggio non potrà essere letto da nessuno al di fuori dei legittimi destinatari

L'utente A vuole inviare un messaggio all'utente B e lo cifra utilizzando la chiave pubblica di quest'ultimo. Solo il legittimo destinatario, l'utente B, utilizzando la propria chiave privata sarà in grado di decifrare il messaggio.

• Autenticità

Viene verificata l'identità del mittente del messaggio

L'utente A cifra il suo messaggio con la propria chiave privata. Chiunque, avendo accesso alla chiave pubblica di A, può decifrare quel messaggio perché la funzione è bidirezionale. Se la procedura riesce, si è allora sicuri che esso è stato scritto dall'utente A, l'unico a possedere la corrispondente chiave segreta. L'utente A ha quindi posto la sua firma elettronica sul messaggio.

• Integrità

Viene verificato che il messaggio, nel suo tragitto, non sia stato modificato da terzi.

E' possibile autenticare oltre al mittente anche il contenuto del messaggio, generando un 'hashing' (stretta di mano) dello stesso. Se il messaggio viene alterato, l'hash, aggiunto in fondo al messaggio, non corrisponde più.

Il mittente può firmare con la propria chiave privata tutto l'insieme, oppure lasciare il messaggio vero e proprio in chiaro e firmare solo l'hash. Chiunque può decifrare l'insieme ricevuto o il solo hash con la chiave pubblica del mittente e così è sicuro dell'origine del messaggio.

Metodo del doppio lucchetto

Il fatto di eliminare lo scambio delle chiavi può rendere intuitivamente impossibile la crittografia.

Ma in realtà esistono metodi che evitano lo scambio delle chiavi. La spiegazione di ciò può essere esemplificata dal metodo del doppio lucchetto.

Alice vuole spedire un messaggio segreto a Bob.

Alice mette il messaggio in una scatola che chiude con il suo lucchetto LA (di cui è l'unica a possedere la chiave) e poi spedisce a Bob.

Bob riceve la scatola chiusa ed aggiunge il suo lucchetto LB  (di cui è l'unico a possedere la chiave) e poi rinvia il tutto ad Alice.

Alice, ricevuta la scatola con il doppio lucchetto, toglie il lucchetto LA e rispedisce la scatola a Bob.

A questo punto Bob può usare la sua chiave per aprire la scatola e leggere il messaggio.

Questo metodo, supponendo che i lucchetti non possano essere forzati, è ritenuto estremamente sicuro. Il suo principale problema è la lentezza, infatti la scatola viaggia più volte del necessario.

Algoritmo RSA

Un importante metodo di crittografia asimmetrica è l'algoritmo RSA. È stato il primo algoritmo nel suo genere è tuttora il più utilizzato in assoluto.

Il nome dell'algoritmo deriva dalla prima lettera dei cognomi di coloro che lo inventarono nell'aprile del 1977: Ronald Rivest, Adi Shamir e Leonard Adleman.

L'algoritmo si basa sull'aritmetica modulare e dei numeri primi.

L'infallibilità della procedura si basa sulla difficoltà di fattorizzare numeri composti di grande dimensione.

I campi di impiego dell'algoritmo sono diversi e variano passando dall'uso all'interno di programmi fino ad arrivare a costituire l'elemento portante di vere e proprie tecnologie di rete.

Generazione delle chiavi:

1. vengono scelti casualmente due numeri primi molto grandi, p e q.
2. viene calcolato il numero n, ottenuto come prodotto tra i due primi p e q. n è il numero che poi verrà utilizzato nelle operazioni come modulo. Viene calcolata la funzione di Eulero delta(n) =(p-1)(q-1), che chiamiamo z, dopo di che i primi p e q vengono eliminati.
3. viene scelto un altro numero naturale casuale d, che deve risultare primo e minore rispetto a z, ovvero al prodotto (p-1)(q-1).
4. si calcola e tale che il prodotto de sia 1 modulo z. In altri termini la divisione de/z deve dare resto 1, ovvero kz + 1 = de, dove k è il quoziente della divisione ed è un numero naturale.

La chiave pubblica è costituita dalla coppia di  numeri e ed n.

La chiave privata è formata dalla coppia d ed n.

Trasmissione del messaggio

1. l'informazione da trasmettere viene indicata come M.
2. si cifra il messaggio ottenendo C con il seguente calcolo: C = (M^e)% n. L'operazione di modulo riduce il numero enorme ricavato dall'elevazione a potenza e in numero di grandezza simile all'originale M.
3. l'informazione decifrata D viene ottenuta con un calcolo simile a quello di cifratura, utilizzando la chiave privata (segreta): D = (C^d)%n.

Dimostrazione dell'algoritmo RSA:

Lo scopo della dimostrazione è dimostrare che decifrando il messaggio cifrato si ottiene il messaggio originale. Ovvero la tesi è D = M.

Per eseguire la dimostrazione si parte dall'operazione di cifratura C = (M^e)% n che può anche essere riscritta come C = M^e - sn dove s è il quoziente intero della divisione tra M^e e C.

Sostituendo l'espressione appena trovata per C nella formula di decifratura si ottiene:
D = (C^d)% n = ((M^e - sn)^d)% n .

Si nota che sn è multiplo di n, quindi nell'operazione di modulo può essere trascurato, quindi si ottiene  D = ((M^e )^d)% n = (M^(ed))% n .

Ricordando che de = kz + 1 dove z = (p-1)(q-1), si può scrivere M^(ed) = M^(1 + kz) =

= M^ (1 + k(p-1)(q-1)) = M*M^(k(p-1)(q-1)) = M(((M^(p-1))^(q-1))^k)

Dato che p è primo, per il Piccolo Teorema di Fermat, si può scrivere:

M^(p-1) = 1 mod p

Se M non è multiplo di p, allora:

M^(ed) = M(((M^(p-1))^(q-1))^k) = M((1^ (q-1))^k) mod p = M mod p

Se, invece M è multiplo di p si ottiene banalmente che M^(ed) = M mod p

Operando in maniera analoga sul termine (q-1) si ottiene che

M^(ed) = M((1^ (p-1))^k) mod q= M mod q

A questo punto si può scrivere che M^(ed) - M = rp e M^(ed) - M = sq, dove r e s sono due numeri interi (r è il quoziente intero della divisione tra M^(ed) e p; s è il quoziente intero della divisione tra M^(ed) e q).

Comparando le due espressioni rp = sq , si nota che r = s * q/p. Dato che p e q sono entrambi primi e quindi primi tra loro e che r e s sono interi, allora s deve essere multiplo di p, quindi si può scrivere s = fp dove f è un intero opportuno.

Così M^(ed) - M = sq, diventa M^(ed) - M = fpq, che equivale a scrivere M^(ed) = M mod (pq) oppure (M^(ed)) %(pq) = M %(pq).

Ricordando che pq = n e M < n per definizione, si conclude la dimostrazione:

D = (C^d)%n = (M^(ed)) % n = M

Piccolo Teorema di Fermat

Scelto un numero primo p e un numero intero qualsiasi z vale la relazione z^p = z mod p.

Se z non è multiplo di  p vale anche la proprietà (z^(p-1))%p =1

Esempio di invio di un messaggio

Alice manda un messaggio M a Bob utilizzando KEB, la chiave pubblica di Bob.

Bob riceve C = M^eB mod nB e ne calcola la funzione di decifratura segreta KDB ottenendo così il messaggio in chiaro.

Consideriamo il messaggio M ="MIAO"

Trasliamo ogni lettera del messaggio in numero secondo il semplice cifrario che fa corrispondere 1 ad A, 2 a B, 3 a C.

M: M1 =13; M2 =09; M3 = 01; M4 =15

Nei reali utilizzi le lettere vengono trascritte in codice ASCII e trasformate in numeri binari.  

Si esegue l'algoritmo per ogni lettera e poi si ricompone il messaggio.

Quindi è come se fossero inviati tanti messaggi M quanti il numero delle lettere totali.

Importante è che n sia sempre maggiore del singolo M.

Procediamo:

1. scegliamo casualmente due numeri primi, p e q, che dovrebbero essere molto grandi ma a scopo esemplificativo prendiamo 11 e 3.
2. calcoliamo il numero n, ottenuto come prodotto tra i due primi p e q. n= 11*3 = 33
3. ora calcoliamo z =(p-1)(q-1) = (11-1) * (3-1) = 10 * 2= 20. p e q non ci servono più.
4. scegliamo un altro numero naturale casuale d, che deve risultare primo e minore rispetto a z, ovvero al prodotto (p-1)(q-1). d = 7
5. si procede al calcolo di e: 7*e =1 mod 20 => e = (20 + k)/ 7  dove k deve essere il più piccolo numero che dia e intero. Vediamo che con k =1, e =3

La chiave pubblica è costituita dalla coppia di  numeri e ed n. (3, 33)

La chiave privata è formata dalla coppia d ed n. (7,33)

Ricordando che gli algoritmi sono

C = M^e mod n

D = C^d mod n

Dove di C è il messaggio crittografato e D quello decriptato.

Abbiamo ora:

C = M^3  mod 33

D = C^7  mod 33

Ovvero, Alice spedisce a Bob il seguente messaggio: 19-3-1-9

Bob procede così:

Riottene, quindi, i numeri di partenza e traslando in lettere può leggere " MIAO".

Utilizzando numeri così piccoli il sistema può essere forzato per tentativi, ma la difficoltà cresce esponenzialmente all'aumentare di n, perché la facilità di violazione del sistema è legata alla difficoltà computazionale di fattorizzare n, ovvero di trovare p e q.

Ci sono voluti 17 anni per violare il sistema con n di 129 cifre.

Oggi nelle operazioni bancarie viene utilizzato n dell'ordine di grandezza di 10^302.

BIBLIOGRAFIA

• Diana Kimpton "CERVELLOTICI CODICI"
• Andrew S. Tanenbaum "RETI DI COMPUTER"
• Simon Singh CODICI & SEGRETI"

A. Languasco - A. Zaccagnini "CRITTOGRAFIA"
Progetto Nazionale Lauree Scientifiche- Sottoprogetto Matematica per il veneto

G. Franzo - M. Cabrini "SICUREZZA DEL TUO PC"

P. Ferragina; F. Luccio "CRITTOGRAFIA"     Principi Algoritmi Applicazioni

Wikipedia, l`enciclopedia libera

Sito "la crittografia da Atbash a RSA" del Liceo Foscarini, Venezia