Crittografia

Page last edited 2 038 giorni 7 ore fa
Da wiki.betaingegneria.it.

Riadatto la pagoina che scrissi 10 anni fa per il corso allo Zuccante

Crittografia[modifica]

Per noi è una funzione.

tale che

essendo lo spazio delle stringhe e lo spazio delle chiavi.

In definitiva lavoreremo con i codici ascii, cioè le codifiche in binario delle stringhe, per cui in ultima analisi abbiamo a che fare con numeri:

tale che

Crittografia di Cesare[modifica]

Abbiamo già visto la volta scorsa la crittografia di Cesare:

tale che

che consisteva in uno scorrimento (shift) dei codici verso avanti o verso indietro ritornando nel segmento dei primi sedici codici (corrispondenti ai codici dell'alfabeto).

Esercizio: riesumare e far funzionare il programmino PHP della crittografia di Cesare.

C'è un modo semplice per capire quale testo chiaro si nasconda sotto la crittografia ed è quello dell'analisi delle frequenze: funziona se il testo è abbastanza lungo da poter comparare le frequenze delle lettere che compaiono nella crittografia con una tabella di frequenze della lingua italiana (se si presume che il testo chiaro è in italiano, ovviamente - qui ci sta a pennello la storia dei Sioux nella seconda Guerra Mondiale, i code-talkers o parla-codice).

Frequenze delle lettere nei Promessi Sposi

Crittografia di Vigenère[modifica]

Un metodo più difficile da scardinare è quello della crittografia di Vigènere (XVII secolo) che è una raffinazione del metodo di Cesare: per ogni carattere del testo chiaro si applica uno shift di una quantità ; il numero potrebbe essere il codice ASCII di una lettera di una chiave.

Esempio: s="ASCII", k="IO"

 k1 = 9 = cod("I") mod 26
 k2 = 15= cod("O") mod 26
 s1 = "A" + 9  = "J" 
 s2 = "S" + 15 = "M"
 s3 = "C" + 9  = "L"
 s4 = "I" + 15 = "X"
 s5 = "I" + 9  = "R"
 
 c("ASCII","IO") = "JMLXR"

Ciò che si nota subito è il fatto che lettera uguale non viene mappata in lettera uguale come nella cifratura di Cesare. Questo rende alquanto arduo tornare al testo chiaro se non si è in possesso della chiave. Se la si conosce è semplice:

 s-11 = "J" - 9  = "A" 
 s-12 = "M" - 15 = "S"
 s-13 = "L" - 9  = "C"
 s-14 = "X" - 15 = "I"
 s-15 = "R" - 9  = "I"

Esiste un modo per rompere questa crittografia ed è ancora l'analisi delle frequenze più l'esistenza di un "crib", cioè della ripetizione della chiave (to crib = scopiazzare):

 A S C I I
 I O I O I
 J M L X R

Nel caso in cui il testo sia lungo è probabile che la stessa lettera del testo chiaro venga cifrata con la stessa lettera della chiave, e anzi che dittonghi o trittonghi vengano criptati in corrispondenza delle lettere della chiave: questo consente di recuperare informazioni sulla struttura della chiave e quindi sul messaggio cifrato.

Esempio:

 NON VEDO NON SENTO NON PARL0
 IOI OIOI IOI IOIOI OIO IOIOI

Le parole NON vengono cifrate allo stesso modo permettendo di inferire sulla struttura sia della chiave (ad esempio sapere di quante lettere è composta) che su quella del testo chiaro. Non è detto che sia facile, ma su questi appigli i crittoanalisti scardinano l'impossibile.

ENIGMA e Alan Turing[modifica]

File:Turing.gif L'esistenza dei crib per un uso non corretto delle macchine Enigma ha permesso ad Alan Turing (matematico inglese del secolo appena trascorso, 1911-1954) di far vincere la guerra a Churchill e a farla perdere a Hitler. Come è fatta Enigma a grandi linee e due parole sulla storia di Enigma e di Alan Turing.

File:Enigma.gif Enigma, Arthur Scherbius, 1918 - Marian Rejewski.

Esercizio: cifrare il testo chiaro dell'esempio con la chiave "IO".

Una crittografia indecifrabile, senza crib, è la crittografia di Vigenère in cui la chiave è scelta in modo tale che la sua lunghezza sia pari a quella del testo chiaro e al suo interno sia assolutamente casuale, senza ripetizioni. Una crittografia siffatta si dice "a blocco monuso" "one-time pad".

Una stessa chiave non deve essere usata per due messaggi diversi, pena l'individuazione inevitabile dei crib che permettono di scardinarla. La chiave deve essere una sequenza generata solo per la sessione di crittografia corrente e non più riusata.

Bletcley Park, località in cui furono concentrati i maggiori matematici inglesi dell'epoca


L'algoritmo DES[modifica]

Al giorno d'oggi la crittografia che si usa in telematica è lo standard DES (Data Encryption Standard). Il DES è il sistema ufficiale di cifratura utilizzato dal governo degli Stati uniti, a partire dal 1977. Negli anni 1972-73, il governo americano indìce una gara per la scelta di un algoritmo ufficiale. La proposta della IBM arriva con l'algoritmo DEA (Data Encryption Algorithm) derivato dall'algoritmo Lucifer di fattura precedente. La NSA sceglie il DEA come standard ed è annunciato sul documento N.46 di Federal Information, col nome di DES.

Per i curiosi, i dettagli del DES sono pubblici e li trova qui.

Cosa è ECHELON

Come funziona il DES[modifica]

Non è un sistema a blocco monouso, ma vengono applicati degli stratagemmi che consentono di evitare i crib: la chiave è lunga 64 bit (di cui 8 di controllo e 56 di chiave effettiva) e vengono cifrati i caratteri in chiaro scrivendo la loro codifica binaria:

Esempio: (tabella ASCII: http://www.asciitable.com/)

 "EROS"  --> cod("E") mod 26 | cod("R") mod 26 | cod("O") mod 26 | cod("S") mod 26 
         --> 69 mod 26 | 82 mod 26 | 79 mod 26 | 83 mod 26
      	  --> 17 | 4 | 1 | 5 = 10001 | 00100 | 00001 | 00101 
      	  --> 10001001000000100101

La chiave sia "IO" (lunga, in questo esempio, 10 bit, ma nello schema reale è lunga 56 bit, il che ci garantisce la possibilità di avere 7.2 x 1016 chiavi diverse).

  		   --> cod("I") mod 26 | cod ("O") mod 26

--> 73 mod 26 | 79 mod 26 --> 21 | 1 = 10101 | 00001 --> 1010100001

Spezziamo il testo chiaro in blocchi da 10 (questa è la lunghezza della ns chiave)

       1000100100 0000100101 
       XOR 	
       1010100001 1010100001
       =
       0010000101 1010000100 -> questo è il testo cifrato

In realtà il DES non accoda i pezzi così ma li mescola secondo un algoritmo preciso per cui si riduce la possibilità di crib. Schema di permutazione del DES Schema di permutazione del DES

La versione attualmente usata è il Triple DES, che consiste nel DES applicato tre volte. Il problema di distribuzione delle chiavi.

Il problema principale per chi deve trasmettere un linguaggio in crittografia è quello di far avere, oltre al testo cifrato, anche la chiave al destinatario.

La chiave non può passare in chiaro perché così si vanifica la crittografia (uno sniffer copia chiave e messaggio e così può avere il testo chiaro). L'algoritmo di Diffie-Hellman-Merkle (1976)

Ralph Merkle, Martin Hellman e Whitfield Diffie

Nel 1976 Diffie, Hellmann e Merkle inventarono un metodo per poter condividere una chiave senza doverla distribuire. Questa tecnica (algoritmo di Diffie-Hellman-Merkle) si basa su tre ingredienti:

1) la scelta di un numero arbitrario segreto da parte di entrambi Bob e Alice

2) Il calcolo di un numero usando una funzione unidirezionale.

3) Un secondo calcolo basato sui risultati intermedi che da' la chiave.

La commutatività delle funzioni scelte garantisce che il risultato finale del calcolo (la chiave) sarà lo stesso per entrambi che così la potranno usare per un qualsiasi schema simmetrico di crittografia.

La funzione unidirezionale scelta è una esponenziazione modulare:

L'inversione di questa funzione rispetto all'esponente è estremamente difficile, e la difficoltà di inversione aumenta esponenzialmente all'aumentare dei numeri in gioco. Si parla di "logaritmo discreto".

Funzioni di questo tipo si dicono anche "a tombino" (trapdoor functions) perché ricordano quanto sia facile perdere la chiave della macchina dentro ad un tombino ma sia invece difficilissimo recuperarla.

ESEMPIO: calcoliamo la funzione per questi valori dei parametri:

x=4, M=2, N=7;

il calcolo diretto è semplice:

y = Mx = 24 = 16 y mod N = 16 mod 7 = 2

Il primo problema inverso, consiste nel trovare M dati C, x, N; non è il caso che ci interessa per cui passiamo subito al

Secondo problema inverso, trovare l'esponente (logaritmo discreto):

Noti, C, M e u trovare x:

4 = 2x mod 7

equivale a trovare, tra gli interi, (y,K) tali che y = 7K + 2 e 2x = y

K=0 => y=2 => 2x = 2 => x = 1

K=1 => y=9 => 2x = 9 => soluzione non intera

K=2 => y=16 => 2x = 16 => x = 4

esistono altre soluzioni:

K=18 => x = 7

K=1170 => x = 13

K=9362 => x = 16

Esercizio: Scrivere un programmino PHP che da' le soluzioni mostrate (così vedete anche la nutritissima libreria di funzioni matematiche implementata in PHP).

Dunque il problema di invertire una tale funzione è difficile, genera più soluzioni (ma una sola è quella che ci interessa), diventa computazionalmente pesante per numeri grandi.

Il protocollo di Diffie - Helmann - Merkle è il seguente:

  0. Alice e Bob si accordano pubblicamente per due numeri, siano (u primo ed e<u);
  1. Bob pensa un numero segreto N e calcola P = eN mod u
     Alice pensa un numero segreto M e calcola Q = eM mod u
  2. Alice e Bob si scambiano pubblicamente i risultati e effettuano il calcolo:
         * Bob: K1 = QN mod u
         * Alice: K2 = PM mod u 

Teorema: K1=K2

Così A e B possiedono la medesima chiave e possono crittografare il messaggio ad esempio usando la cifratura di Vigenère.

Cosa può fare un terzo incomodo, che chiamiamo Eve (da "eavesdropping" = spione)? Ella conosce molte informazioni: (e,u) e addirittura (P,Q) ma non conosce N e M. Trovare N o M per risalire alla chiave, da parte di Eve, equivale a trovare il logaritmo discreto in base e dei numeri scambiati: è un compito non impossibile ma molto difficile dal punto di vista computazionale, anche perché la soluzione non è univoca.

Esempio: clicca

Ulteriori informazioni su Diffie-Hellman Key Agreement Protocol.

Una intervista a Whitfield Diffie. Crittografia a chiave "asimmetrica"

Adi Shamir, Ronald Rivest e Leonard Adleman

Nel 1977 Rivest, Shamir e Adleman inventarono la crittografia a chiave asimmetrica. In cosa consiste? Vediamolo per gradi.

Un modo per poter fare a meno di distribuitre la chiave è quello di usarne due: siano Alice (A) e Bob (B) i nostri protagonisti:

1) A chiude il suo messaggio in una cassetta e la chiude con un lucchetto, di cui lui solo ha la chiave, e lo invia a B

2) B chiude un ulteriore lucchetto (di cui egli solo ha la chiave) sulla cassetta (senza aprirla) e lo rispedisce ad A.

3) A toglie il suo lucchetto: rimane ancora il lucchetto di B ad impedire l'apertura infingarda della cassetta

4) B finalmente toglie il suo lucchetto e può aprire la cassetta.

Notiamo una cosa: l'ordine di apertura dei lucchetti è lo stesso di quello di chiusura.

In crittografia questo non è possibile perché le chiavi vanno applicate in senso FIFO (First In First OUT): in pratica per i crittogrammi è come se chiudessimo la prima cassetta dentro un'altra cassetta: A non può aprirla prima che non l'abbia aperta B.

Infatti possiamo immaginare la crittografia come una funzione: la doppia chiave ci porta ad avere una funzione composta:

   S x K ---> S
   (s,k1) |--> s1

S x K ---> S (s1,k2) |--> s2=s

L'idea è quella di trovare il modo per cui se Alice vuole cifrare un messaggio perché solo Bob lo possa leggere, lo faccia utilizzando una chiave "pubblica" k1 mentre per decifrare Bob debba usare una chiave "inversa" ("privata") k2; così sarà possibile per chiunque mandare messaggi cifrati a Bob, mentre solo lui potrà leggerli. Come è possibile inventare un marchingegno simile?

Sia M il messaggio, usiamo una esponenziazione modulare per cifrarlo:

C = Me mod N

(e,N) costituiscono la chiave pubblica di Bob, che Alice può trovare in una sorta di "elenco telefonico".

Bob decifra il messaggio utilizzando la formula seguente:

M = Cd mod N

Per capire le relazioni tra le grandezze in gioco è più facile capire come si ricava la chiave pubblica a partire dalla chiave privata. Premettiamo una definizione: Funzione di Eulero:

Si dice funzione di Eulero di un numero intero p il numero di interi compresi tra 0 e p-1 che sono primi con p (tali che il mcd tra m e p è 1):

φ(p) = #{0 <= m < p | mcd(m,p)=1} p φ(p) 1 1 2 1 3 2 4 2 5 4 6 2 7 6 8 4 9 6 10 4 11 10 Tabella dei primi valori di φ(p)

La funzione di Eulero ha le seguenti proprietà:

  1. φ(p) = p-1 se p è primo >1.
  2. (moltiplicatività) φ(xy) = φ(x) * φ(y) se x,y primi 

Chiave privata di Bob

Bob sceglie due numeri interi primi tra loro, possibilmente "grandi": siano U e V.

Poi:

- calcola N = U * V,

- sceglie un qualsiasi intero e < N che sia coprimo con N.

- calcola φ(N)=(U-1)*(V-1)

- calcola d | e * d = 1 mod φ(N),

(y = φ(N) * e * d + 1)

si dice che e e d sono "inversi modulo φ(N)" e si scrive anche:

d = e-1 mod (φ(N))

Per capire, ad esempio, come funzioni la moltiplicazione modulo 7 si guardi questa tabella.

Esercizio: generare la tabella dell'esempio con un programmino PHP.

La chiave privata di Bob è costituita dalla terna di interi (U,V,d) dove d è l'inverso dell'esponente pubblico e modulo la funzione di Eulero di N.

Invece, la chiave pubblica di Bob è la coppia di interi (e,N): egli la invia in un canale pubblico ad Alice (oppure la pubblica in un elenco telefonico). Alice cifra il messaggio usando la chiave pubblica di Bob

Dato il messaggio M che lei vuole inviare, calcola il crittogramma come:

C = Me mod N

e invia a Bob il risultato C. Bob decifra il risultato C ottenendo il testo in chiaro

- calcola

M = Cd mod N

Non dimostriamo che effettivamente le cose stanno così, ma diciamo che questa inversione è possibile grazie alle proprietà della funzione di Eulero, che gioca in questo protocollo un ruolo fondamentale. Difficoltà per Eve

Dato N non è facile trovare U e V primi tale che U*V = N: è il problema della fattorizzazione di interi in fattori primi, problema formidabile soprattutto per fattori grandi, per il quale non esiste a oggi un algoritmo polinomiale.

La principale difficoltà per Eve è dunque reperire U e V dato N: lei potrebbe calcolarsi anche φ(N) ma, non sapendo la fattorizzazione, dovrebbe generare tutti i valori di φ "a mano" fino al numero N, impresa ardua quanto la fattorizzazione di N. Dunque la difficoltà di violare questo protocollo di crittografia sta nel trovare la fattorizzazione in primi di un intero grande.

E' evidente che qualore un matematico trovasse un algoritmo di complessità polinomiale per la fattorizzazione di numeri primi, questo metodo diverrebbe immediatamente privo di valore e si dovrebbe cercarne un altro. Questo al dice lunga sull'importanza della ricerca nel campo delle scienze e, in questo caso, nell'ambito della matematica.

Altri metodi sicuri per lo scambio delle chiavi si stanno mettendo a punto utilizzando la meccanica quantistica (quantum cryptography),

Esempio: clicca Diversi usi della crittografia a chiave asimmetrica.

Alice può usare la chiave pubblica di Bob per spedirgli un messaggio in crittografia: le è sufficiente reperire la chiave pubblica di Bob presso un'agenzia (tipo la VeriSign).

Allo stesso modo, anche Charlotte può spedire il suo messaggio in crittografia a Bob, senza che Alice possa leggerlo: solo Bob può infatti invertire la crittografia e volgere il testo in chiaro. Charlotte può però fingersi Alice senza che Bob se ne accorga. Problema: come si può essere sicuri dell'autenticità del mittente?

La chiave asimmetrica ci viene incontro anche per risolvere questo problema.

Se prima di inviare il messaggio Alice lo cifra con la sua CHIAVE PRIVATA, a Bob sarà possibile leggerlo utilizzando la chiave pubblica di Alice (non dimostriamo che le chiavi pubblica e privata possono commutare). In questo modo, qualsisasi persona che venga in possesso del crittogramma può leggerne il contenuto: infatti la chiave pubblica di Alice, è per definizione, PUBBLICA.

In questo modo però abbiamo la certezza che un documento provenga solamente da Alice e da nessun altro mittente. In questo caso la chiave privata di Alice funge da firma digitale di Alice.

Se Alice vuole essere sicura che il suo messaggio lo possa leggere soltanto Bob e che Bob sia sicuro che è stata lei a scrivere, deve impiegare entrambe le chiavi, secondo questo protocollo:

  1. Alice cifra il suo messaggio chiaro con la SUA CHIAVE PRIVATA (fino a qui qualsiasi persona poterebbe comunque leggere il testo chiaro usando la sua chiave pubblica).
  2. Alice cifra nuovamente il messaggio risultante con la chiave PUBBLICA DI BOB.
  3. Alice recapita il messaggio a Bob
  4. Bob decifra il messaggio, in ordine, con la sua chiave privata, e poi con la chiave pubblica di Alice.
  5. Bob può leggere il testo chiaro con la sicurezza che gli è stato mandato da Alice. 

Siti:

Bletchley Park: http://www.bletchleypark.org.uk/

RSA: http://home.ecn.ab.ca/~jsavard/crypto/pk0502.htm

Funzione di Eulero: http://www.cut-the-knot.com/blue/Euler.html

Crittografia in generale http://www.valtellinux.it/knights/crittografia2-1.html

algoritmo RSA: http://www.provincia.venezia.it/mfosc/studenti/crittografia/critto/rsa.htm

Liceo Classico Foscarini di Venezia: http://www.provincia.venezia.it/mfosc/studenti/crittografia/