La crittografia

Brevi note per la 4TC L.S. Tron

Alice e Bob

Due studenti, A e B, che chiameremo Alice e Bob, vogliono scambiarsi un messaggio, ma vogliono anche tenerlo segreto, in modo che, se intercettato, non sia comprensibile.

Come fare ? Con la CRITTOGRAFIA

Etimologia

La parola crittografia deriva dal greco:

ó (nascosto) e γραφ (scrivo)

La crittologia nasce dall’idea di “cifrare” i messaggi in modo da renderli incomprensibili in caso di intercettazione

Glossario testo in chiaro (plaintext)

testo o file nella sua forma normalmente utilizzabile testo cifrato (ciphertext)

testo o file nella sua forma cifrata cifratura o crittazione (encryption)

operazione che permette di passare da un testo in chiaro ad un testo cifrato

decifratura o decrittazione (decryption) operazione che permette di passare dal testo cifrato al testo in chiaro

Glossario

chiave (key) parametro che rende variabile la cifratura, se la cifratura non è debole basta tenere segreta la chiave per ottenere l'effetto di tenere segreto l'intero testo

coppia di chiavi (key pair) coppia di parametri usati dalla nuova crittografia asimmetrica: quando una delle due chiavi viene usata per crittare e l'altra serve per decrittare

I primi sistemi di codifica Sebbene le prime tracce risalgano addirittura agli egizi,

il primo codice famoso è quello di Giulio Cesare, utilizzato per inviare un messaggio militare a Cicerone

Si tratta della sostituzione di ogni lettera del messaggio con una lettera successiva nell’alfabeto.

La chiave utilizzata da Cesare era 3:A diventa DB diventa E ….

Passi successivi furono compiuti, fino ad arrivare alCifrario di Leon Battista Alberti (1466)Vedi http://sicurezza.html.it/guide/lezione/2379/i-metodi-storici-di-cesare-e-alberti/

Altri passi storici interessanti:

Il codice di Vigènere

Il cifrario a trasposizione di colonne

ENIGMA

La crittografia moderna

Il DESIl DES (Data Encryption Standard) è un cifrario composto sviluppato dall'IBM, modificato dalla National Security Agency (NSA) e adottato dal governo statunitense nel 1977

e la EFF (Electronic Frontier Foundation )

IDEA (1991)

La chiave di crittografia

Il sistema DES si basa su una chiave segreta ed è usato ad es. per crittografare le password degli utenti in Unix

Si tratta di una chiave SINGOLA, che permette tanto di codificare quanto di decodificare il messaggio

Vedi http://www.boscarol.com/pages/internet/098-critto.html

La crittografia a doppia chiave

Per una maggior sicurezza Venne ideata una crittografia asimmetrica a

doppia chiave: PUBBLICA E PRIVATA http://www.nemesi.net/critt.htm http://www.megalab.it/articoli.php?id=32 http://www.trustitalia.it/decode.php?

id=cfDulE002763

La crittografia asimmetrica(a doppia chiave)

Da: S. Singh(*)

“CODICI E SEGRETI”

Ed. Rizzoli

(*) Simon Singh:

PhD in Fisica delle particelle – Cambridge, autore di “L’Ultimo Teorema di Fermat”

Dalla crittografia a chiave singola a quella a doppia chiave Il problema della cifratura con chiave

singola sta nel fatto che la chiave usata per codificare deve essere resa nota al destinatario, per dargli modo di “aprire il lucchetto”, ma ciò espone il sistema a rischi insostenibili

A metà degli anni ’70 un gruppo di crittografi indipendenti trovò la soluzione

Whitfield Diffie (MIT) Si occupò del problema della distribuzione delle

chiavi; Conobbe Martin Hellman della Stanford University

(California) Assieme cercarono una “Funzione unidirezionale”, in

cui il risultato da ottenere sia facile da ottenere, ma tornare al punto di partenza no. (Le funzioni bidirezionali posseggono una funzione inversa, le unidirezionali/hash no)

Scoprirono anche che per “Alice e Bob” era possibile stabilire una chiave senza necessità di comunicare tra di loro

La nascita della crittografia a chiave pubblica Diffie, dopo numerosi momenti di scoraggiamento

(invitò perfino la moglie a cercarsi un altro marito) ebbe un’intuizione geniale: la chiave asimmetrica (NB. Enigma e DES sono cifrature simmetriche: usano la stessa chiave).

Secondo questo metodo ALICE creerà una COPPIA di chiavi: una PRIVATA, che terrà per sé ed una PUBBLICA, che metterà a disposizione non solo di BOB, ma di chiunque (“il segreto alla luce del sole”)

Bob e Alice

Se Bob vuole spedire un messaggio ad Alice, userà la chiave pubblica di Alice per crittarlo e glielo spedirà;

Alice (e lei sola) sarà in grado, con la sua chiave privata, di “aprire” il lucchetto e di leggere il messaggio

La chiave pubblica infatti serve solo a crittare e non a decifrare

La chiave pubblica

Il fatto che la chiave pubblica non sia in grado di “aprire” il lucchetto è dovuto al fatto che utilizza una funzione unidirezionale;

La chiave privata di Alice invece possiede dei dati che rendono bidirezionale una funzione che normalmente non lo è

Insomma, il risultato della cifratura sarà irreversibile, a meno di possedere qualcosa di speciale

Alice e Bob

Il problema sorge invece se è Alice che vuole spedire un messaggio a Bob

Infatti lei potrà cifrarlo con la sua chiave privata, ma purtroppo chiunque potrà aprirlo (tramite la chiave pubblica)

Solo un’ idea ???

Nel 1975 Diffie pubblicò un riassunto della sua idea, invitando gli studiosi a ricercare una funzione unidirezionale che potesse funzionare nel modo indicato

Fu solo nel 1977 che un altro trio di studiosi, al MIT, a 5000 Km, sulla costa orientale, riuscì nell’intento

RSA

Rivest, Shamir e Adleman Dopo una festa, Rivest (specialista in

computer), incapace di prender sonno, aprì un libro di matematica e a poco a poco arrivò alla soluzione

Il cuore della cifratura sta nel numero N, utilizzato nella funzione di cifratura, che la rende flessibile e permette ad ognuno di personalizzare le chiavi

N

Alice sceglie due numeri primi (un numero è primo se è divisibile solo per se stesso e per 1): p e q

Moltiplica p e q e ottiene N

es sceglie p=17.159 e q=10.247 N (=p*q) diviene 175.828.273 e viene

utilizzato come chiave pubblica

Bob Se Bob vuole inviare un messaggio cifrato ad

Alice, deve procurarsi la sua chiave pubblica (175.828.273) e inserirlo nella formula generale della funzione unidirezionale, anch’essa di dominio pubblico

Alice sarà l’unica in grado di decifrarlo, infatti solo lei conosce i numeri primi p e q (il “qualcosa” che rende possibile la decifrazione)

La domanda è: non è possibile risalire a p e q conoscendo N ?

P e q Se, a partire da p e q genero N in pochi secondi con

una calcolatrice, il procedimento inverso (scomposizione in fattori primi) richiede diverse ore.

Il tempo aumenta se aumento il numero di cifre di N, cioè se scelgo due numeri primi p e q molto più grandi

Per le banche si usano valori di N dell’ordine di 10^308

Naturalmente se in futuro si trovasse un metodo di scomposizione in fattori primi velocissimo, la RSA diventerebbe inutilizzabile

Resta il problema di Alice e Bob

Come già detto, che succede se è Alice che vuole spedire un messaggio a Bob ?

Infatti lei potrà sì cifrarlo con la sua chiave privata, ma purtroppo chiunque potrà aprirlo (tramite la chiave pubblica)

Zimmerman e il PGP

Phil Zimmermann (studiò fisica e informatica alla Florida Atlantic University) voleva garantire la Privacy (Pretty Good Privacy) anche ai privati cittadini;

Il PGP permette anche la FIRMA dei documenti

La “doppia coppia” di chiavi Se Alice vuola inviare una cyberlettera riservata

solo a Bob può: Cifrare la lettera con la sua chiave privata (guscio

interno fragile, in quanto renderebbe la lettera apribile a tutti, ma che garantisce che la lettera proviene proprio da Alice);

Cifrare il crittogramma così ottenuto con la chiave pubblica di Bob (guscio esterno robusto, che permetterà solo a Bob di aprire la lettera)

Spedire la lettera;

Bob

Bob (e solo lui) potrà aprire la lettera ricevuta con la sua chiave privata (apertura del guscio esterno)

Userà poi la chiave pubblica di Alice per leggere finalmente la lettera (apertura del guscio interno, di firma del messaggio)

Il guscio interno non serve a proteggere il messaggio, ma solo a garantire l’autenticità del mittente.

Il PGP

Il PGP è scaricabile liberamente, solo per uso personale non a scopo di lucro, ad es. dal sito http://www.pgpi.com

Il futuro

Per ora questo sistema “regge”, ma D.Deutch, un fisico britannico, pensò, a partire dal 1984, di riformulare l’informatica alla luce della fisica quantistica.

In un computer quantistico le varianti potrebbero essere risolte tutte contemporaneamente, in una “sovrapposizione” di stati (o universi) paralleli.

Il computer quantistico Proviamo ad immaginare che ad ogni bit corrisponda una particella

subatomica, dotata di spin (o momento angolare). Come un pallone da basket che ruoti sulla punta di un dito, la

particella potrebbe ruotare verso est oppure verso ovest. Potremmo allora far corrispondere le due diverse rotazione a 0 e 1.

Ad es, con 7 particelle:

Est Est Ovest Ovest Est Ovest Ovest

1 1 0 0 1 0 0

Gli stati sovrapposti A livello subatomico, essendo molto piccole, le

particelle obbediscono alle leggi della meccanica quantistica ed entrano perciò in una sovrapposizione di stati.

Possiamo così immaginare che ogni particella entri in universi alternativi, in uno dei quali ruota verso ovest e nell’altro verso est

Immettendo un debole impulso elettromagnetico possiamo ottenere che le 7 particelle dell’esempio precedente si trovino simultaneamente in 2^7 cioè 128 stati diversi

I Qbit I bit diventano Qbit ed è possibile eseguire

(nell’esempio precedente delle 7 particelle) 128 calcoli nel tempo necessario ad uno solo

Si può pensare a quanto avviene (a seconda dell’interpretazione quantistica che si preferisce),– o come ad un’entità singola che esegue

simultaneamente i calcoli con 128 numeri diversi;– o a 128 entità distinte che eseguono, in universi

paralleli, un solo calcolo, diverso da tutti gli altri Con computer di tale genere la crittografia

verrebbe ancora una volta stravolta