Metodi crittografici e firma digitale

Esami di stato 2010/2011

Progetto realizzato da Marco Semeraro

Marco Semeraro

Classe 5B Inf

INDICE

Cenni sulla crittografia……………………………………………………….1

Crittografia simmetrica………………………………………………………1

Cifrario di cesare………………………………………………………………..2

Cifrario di vigenere……………………………………………………………..3

Cifrario di vernam……………………………………………………………...3

Crittografia asimmetrica…………………………………………………….4

Algoritmo RSA…………………………………………………………………….4

Storia dell’RSA …………………………………………………………………..5

Firma digitale……………………………………………………………………..6

Funzioni di hash…………………………………………………………………7

Algoritmo SHA……………………………………………………………………8

Algoritmo MD5…………………………………………………………………..9

Bibliografia…………………………………………………………………………10

Marco Semeraro

Classe 5B Inf

Cenni sulla Crittografia

deriva dall'unione di due parole greche: κρσπτὁς (kryptós)

La parola crittografia che significa "nascosto", e

γραφία (graphía) che significa "scrittura".

La crittografia quindi permette lo scambio di informazioni o messaggi in maniera nascosta, ossia in modo che solo gli

utenti prestabiliti riescano a interpretare l’informazione o il messaggio.

Essa è nata per garantire la sicurezza nella comunicazione attraverso la rete, questo perchè ogni giorno aumentano il

numero di persone che cercano di intercettare dei messaggi e adoperarli per scopi personali.

La crittografia essenzialmente si basa sull'aritmetic; nel caso di un testo, si tratta di trasformare le lettere che

compongono il messaggio in una successione di cifre (sotto forma di bits nel campo informaticodato che i computer si

basano sul codice binario), e poi di fare dei calcoli su queste cifre per :

 modificarle in modo da renderle incomprensibili.

 far si che solo il destinatario sappia decifrarli.

Il fatto di codificare un messaggio per renderlo segreto viene detto Codificazione. Il metodo inverso, che consiste nel

ritrovare il messaggio originale, è detta decodificazione.

Gli algoritmi di crittografia possono essere classificati sotto due principali categorie riguardanti il tipo di chiave

utilizzata: simmetrici (chiave segreta), asimmetrici (chiave pubblica).

Crittografia Simmetrica

simmetrica, o a chiave privata, consiste nel utilizzare un’unica chiave sia per cifrare

La crittografia sia per decifrare un

messaggio. Questa metodologia oggi giorno è molto utilizzata in tutte le operazioni che richiedono una certa velocità

grazie alla semplicità di cifrare e decifrare i messaggi, ma proprio per questo occorre prestare attenzione al suo utilizzo,

infatti se un malintenzionato si inserisce nel canale di comunicazione durante la trasmissione della chiave privata, la

potrà utilizzare a proprio favore decifrando i messaggi che vengono scambiati tra i reali possessori della chiave

privata(attacco Man in the Middle).

Alcuni dei più utilizzati algoritmi a cifratura simmetrica sono:

 Il cifrario di Cesare,

 Il cifrario di Vernam

 Il cifrario di Vigénère; 1 Marco Semeraro

Classe 5B Inf

Cifrario di Cesare

Il cifrario di Cesare è uno degli algoritmi crittografici più antichi di cui si son trovate tracce. E’ un cifrario a

sostituzione monosillabica perché a ogni lettera del testo in chiaro viene sostituita una lettera che si trova spostata di un

certo numero di posizioni rispetto l’alfabeto originale e in questo particolare caso il numero di scostamenti erano tre.

Nello schema sottostante vengono riportate le corrispondenze delle lettere originali dell’alfabeto spostate di tre

posizioni. Cifrario di Cesare

Alfabeto a b c d e f g h i j k l m n o p q r s t u v w x y z

originale

Alfabeto d e f g h i j k l m n o p q r s t u v w x y z a b c

cifrato

Questo cifrario veniva utilizzato da Giulio Cesare per rendere incomprensibili i suoi messaggi a chi non era autorizzato

a leggerli. Questo algoritmo al tempo era ritenuto sicuro perché molte persone erano analfabetiche e quindi non

riuscivano a leggere, men che meno a decifrare un messaggio, nonostante la banalità.

In seguito alla scoperta dell’analisi delle frequenze da parte di Al-Kindi, un matematico arabo del XI secolo circa, tutti i

cifrari di questo tipo diventarono molto facili da rompere e perciò da circa mille anni rendono insicure questo tipo di

comunicazioni.

Con un diagramma delle frequenze delle lettere nel testo in cifra e nella lingua originale del testo, è facile individuare il

valore della chiave osservandone la disposizione. Ad esempio, nella lingua italiana, le lettere più frequenti sono le

vocali E, A, O ed I, con lievi differenze, seguite dalle consonanti L, N, R, S e T, mentre sono rare B, F, Q e Z e

praticamente assenti le lettere straniere J, K, Y, X e W; nella lingua inglese, invece, le lettere più frequenti sono E e T,

mentre le più rare sono Q e Z. Anche i computer sono in grado di eseguire simili calcoli senza difficoltà.

2 Marco Semeraro

Classe 5B Inf

Cifrario di Vigenère

Il cifrario di Vigenere si può considerare una generalizzazione del cifrario di Cesare; invece di spostare sempre dello

stesso numero di posti la lettera da cifrare, questa viene spostata di un numero di posti variabile ma ripetuto,

determinato in base ad una parola chiave, da concordarsi tra mittente e destinatario, e da scrivere ripetutamente sotto il

messaggio, carattere per carattere; la chiave viene chiamata anche verme, per il motivo che, essendo in genere molto

più corta del messaggio, deve essere ripetuta molte volte sotto questo, come nel seguente esempio:

Testo chiaro m a r c o s e m e r a r o

Verme v e r m e v e r m e v e r

Testo cifrato h e i o s n i d q v v v f

Il testo cifrato si ottiene spostando la lettera chiara di un numero fisso di caratteri, pari al numero ordinale della lettera

corrispondente del verme. Di fatto si esegue una somma aritmetica tra l'ordinale del chiaro (A = 0, B = 1, C = 2 ...) e

quello del verme; se si supera l'ultima lettera, la Z, si ricomincia dalla A, secondo la logica delle aritmetiche finite.

Il vantaggio rispetto ai cifrari monoalfabetici (come il cifrario di Cesare o quelli per sostituzione delle lettere con

simboli/altre lettere) è il fatto che il testo viene cifrato con n alfabeti cifranti, rendendo quindi più difficile la

crittoanalisi. Cifrario di Vernam

Il cifrario di Vernam è un sistema crittografico basato sul cifrario di Vigénère, al quale aggiunge il requisito che la

chiave sia lunga quanto il testo e non riutilizzabile. Il cifrario di Vernam è l'unico sistema crittografico la cui sicurezza è

comprovata da una dimostrazione matematica.

Per avere una sicurezza assoluta non si dovrebbe mai riutilizzare la stessa chiave; se si utilizza più volte la stessa chiave

infatti questa torna ad essere più breve del messaggio, o meglio della somma di tutti i messaggi e il cifrario non è più

perfetto. Per questo motivo questo tipo di cifrario viene detto a chiave non riutilizzabile (One time pad).

modo l’algoritmo può essere svantaggioso nel caso in cui il canale di comunicazione non sia sicuro oppure se

Ad ogni

occorre distribuire continuamente chiavi molto lunghe. Nel caso la comunicazione non sia sicura, due persone

dovrebbero trovarsi periodicamente per scambiarsi la chiave che dovrà essere generata come una sequenza casuale

lunghissima, sufficiente per un gran numero di messaggi, e una volta terminata, dovranno rincontrarsi di nuovo, e

ripetere tutti i passaggi. 3 Marco Semeraro

Classe 5B Inf

Crittografia Asimmetrica

La crittografia asimmetrica, o a chiave pubblica, si differenzia da quella simmetrica perché vengono utilizzate due

chiavi differenti: una pubblica utilizzata da tutti per cifrare il messaggio e una privata usata solo da un singolo utente

che serve a decifrare il messaggio.

Utilizzando due chiavi differenti quindi, si può distribuire a chiunque la chiave pubblica che ogni utente utilizzerà per

quest’ultima chiave

cifrare il messaggio e spedirlo al possessore della chiave privata, ma solamente chi possiede può

decifrare il messaggio, ovviando così al rischio che altri utenti si intromettano e riescano a interpretare il messaggio

cifrato, problema che si può incorrere utilizzando la crittografia simmetrica.

Naturalmente, per poter usufruire di due chiavi bisogna trovare una relazione tra di esse e fare in modo che generando la

chiave pubblica, non si possa risalire alla chiave privata.

La crittografia asimmetrica viene utilizzata molto per poter scambiare segretamente la chiave pubblica che verrà

utilizzata per la crittografia simmetrica, questo perché la crittografia asimmetrica richiede maggior tempo rispetto a

quella simmetrica. Algoritmo RSA

L’algoritmo RSA fu inventato nel 1977 da Rivest, Shamir e Adleman, degli studenti del MIT, i quali realizzarono uno

degli algoritmi a chiave pubblica piu’ utilizzato al giorno d’oggi e che prese il nome di RSA. Questo algoritmo è reso

sicuro grazie alla difficoltà di fattorizzazione del prodotto di due numeri primi molto grandi e al contrario della facilità

di calcolarne il prodotto.

Vediamo ora il funzionamento di questo algoritmo:

Generazione delle chiavi

1. Si generano due grandi numeri primi p, q tali che il loro prodotto n = pq ha la lunghezza in bit che

desideriamo.

2. Si calcola n = pq.

φ

3. Si calcola = (p-1)(q-1). φ φ.

4. Si sceglie un numero intero positvo tale che e < e e sia coprimo con

φ ≡ 1

5. Si calcola un intero positivo d < tale che e*d [modulo phi]

6. La coppia (n, e) forma la chiave pubblica, la coppia (n, d) forma la chiave privata.

Criptaggio

Per criptare un messaggio occorre avere la chiave pubblica e solo dopo aver codificato la stringa di testo in un numero

intero, si può criptare il messaggio utilizzando la formula:

e

c = m mod n

m e’ il messaggio.

Dove

Decriptaggio

Avendo il testo criptato, attraverso la formula

d

m = c mod n

possiamo risalire al messaggio di partenza.

nella formula, per risalire al messaggio originale occorre sapere l’esponente d che ovviamente conosce solo

Come noto

il possessore della chiave privata.

Per poter risalire a tale dato non conoscendolo occorrerebbe sapere i numeri primi p e q che formano n ma come

detto all’inizio, indovinare i due primi grandi avendo n è molto difficile e porterebbe via troppo tempo.

abbiamo 4 Marco Semeraro

Classe 5B Inf

Storia dell’ RSA

È nel 1978 che questo sistema trova la sua applicazione reale. Infatti sono 3 ricercatori del MIT (Ronald Rivest, Adi

Shamir e Leonard Adleman) che hanno saputo implementare tale logica utilizzando particolari proprietà formali dei

numeri primi con alcune centinaia di cifre. L'algoritmo da loro inventato, denominato RSA per via delle iniziali dei loro

cognomi, non è sicuro da un punto di vista matematico teorico, in quanto esiste la possibilità che tramite la conoscenza

della chiave pubblica si possa decrittare un messaggio, ma l'enorme mole di calcoli e l'enorme dispendio in termini di

tempo necessario per trovare la soluzione, fa di questo algoritmo un sistema di affidabilità pressoché assoluta.

Ronald Rivest, Adi Shamir e Leonard Adleman nel 1983 hanno brevettato l'algoritmo negli Stati Uniti dal MIT

(brevetto 4.405.829, scaduto il 21 settembre 2000); inoltre hanno dato vita alla società RSA Data Security, tutelando

così i propri interessi commerciali. In seguito la Security Dynamics acquisì la società e vendette l'utilizzo degli

algoritmi a società come Netscape, Microsoft ed altri. Una variante del sistema RSA è utilizzato nel pacchetto di

crittografia Pretty Good Privacy (PGP). L'algoritmo RSA costituisce la base dei sistemi crittografici su cui si fondano i