crittografia

kryptós gráphein

nascosto scrivere

la crittografia tratta delle "scritture nascoste", deimetodi per rendere un messaggio "offuscato"

404 a. C

Lisandro riceve un corrierea Sparta recante la notiziadi un attacco persiano

crittografia per trasposizione di lettere, la scitale greca

crittografia per sostituzione nel libro di Geremia

Atbash

a b c d e f g h i l m n o p q r s t u v zZ V U T S R Q P O N M L I H G F E D C B A

a b c d e f g h i l m n o p q r s t u v zZ V U T S R Q P O N M L I H G F E D C B A

u n s e g r e t o t i m a n d oC L E S Q F S D I D O M Z L T I

cifrario di Cesare

a b c d e f g h i l m n o p q r s t u v zD E F G H I L M N O P Q R S T U V Z A B C

con “chiave” = 3

“La sicurezza di un crittosistema non deve dipenderedal tener celato il crittoalgoritmo.

La sicurezza dipenderà solo dal tener celata la chiave”

La Cryptographie Militaire, Kerckhoffs, 1883

l'analisi delle frequenze

i segni che identificano le lettere cambianoma le caratteristiche rimangono le stesse:

frequenza d'uso

regole grammaticali

...

1467

Leon Battista Alberti pubblicail “De Cifris” e introduce lacifratura polialfabetica

disco cifrante

cambiando diversi alfabeti cifranti in un unico messaggio lastessa lettera viene cifrata differentemente di volta in volta

la successione delle sostituzioni di alfabetocostituisce la chiave del messaggio

chiave ABCDAB CD ABCDA BCD ABCDABCDABCDtesto CRYPTO IS SHORT FOR CRYPTOGRAPHYtesto cifrato CSASTP KV SIQUT GQU CSASTPIUAQJB

si hanno ancora ripetizioni, per lettere che sono distanti traloro quanto la lunghezza della chiave o multipli

casuale

lunga quanto il testo da cifrare

mai riutilizzata

one time pad

non ci sono appigli per un'analisi statistica

la chiave è a sua volta un segreto tra mittente e destinatario

possiamo scambiarci un segreto senza riverarlo?

1976

Diffie, Hellman e Merkeaffrontano il problemadello scambio delle chiavi

Protocollo Diffie-Hellman-Merkeper lo scambio delle chiavi

la difficoltà è ora trovare funzioni “unidirezionali”, equivalentialla mescola dei colori:

invertibili

facili da calcolare in un verso ma difficili nell'altro

risultato finale indipendente dall'ordine delle operazioni

2 + 5 = 7 (mod 12)

7 + 8 = 3 (mod 12)

9 + 5 = 2 (mod 12)

funzioni banali diventano interessantinell'aritmetica dei moduli

y=2x

y=2xmod12

il problema della distribuzione delle chiavi è risoltoma la procedura è macchinosa

occorre l'intervento di alice e bob ad ogni passaggio

non molto pratico per comunicazioni in tempo reale:

transazioni economiche e finanziarie,telefonate, email, istant messaging...

ma se disponessimo di due chiavi diverse per lucchetto:

una che può solo cifrare

una che può solo decifrare

1977

Rivest, Shamir, Adleman creanoil protocollo a chiave pubblica RSA

alice sceglie due numeri primi molto grandi: p, qe un ulteriore numero e minore e primo con

alice inoltre calcola

e d tale che

e,N chiave pubblica

d,N chiave privata

p−1q−1

N=p⋅q

e⋅d=1mod[p−1q−1]

la chiave pubblica e,N può essere divulgata liberamente

la chiave privata d,N viene tenuta nascosta

C=MemodN

bob vuole inviare un messaggio ad alice:

conoscendo e,N trasforma il messaggio in chiaro Mnel messaggio criptato C con la formula

M=Cd modN

alice ricevuto il messaggio C lo ritrasformanel testo in chiaro M con la formula

M=Cd modN

per alice è facile perché conosce d

non conoscendolo per violare il messaggio cifrato Csi deve ricalcolare d a partire da p e q fattori di N

ma non ci sono algoritmi efficienti per la fattorizzazione

scegliere p e q molto grandi ci garantisce che calcolarli da

non sia fattibile in un tempo ragionevole per quantapotenza di calcolo si abbia a disposizione

N=p⋅q

quanto tempo ci vuole per fattorizzare N?

RSA Number Decimal digits Binary digits Cash prize offered Factored on RSA-129 129 426 $100 USD April 1994RSA-576 174 576 $10,000 USD December 3, 2003RSA-640 193 640 $20,000 USD November 2, 2005RSA-704 212 704 $30,000 USD openRSA-768 232 768 $50,000 USD openRSA-896 270 896 $75,000 USD openRSA-1024 309 1024 $100,000 USD openRSA-1536 463 1536 $150,000 USD openRSA-2048 617 2048 $200,000 USD open

RSA factoring challenge

CRIPTAZIONE

FIRMA

impostori e certificati digitali

la chiave di “alice” è stata emessa veramente da aliceo da un impostore?

una “certification authority” può firmare a sua volta undocumento contenente la chiave pubblica di alice, dopoche quest'ultima si e' identificata

se abbiamo fiducia in chi certifica la nostra fiducia si puòestendere a tutti i certificati che emette

“nel 1790, quando la Dichiarazione dei diritti dell'Uomo fu promulgata, due persone potevano tenere una conversazione riservata con una tranquillità che oggi neanche ci sogniamo, semplicemente facendo due passi e badando che nessuno fosse nascosto tra i cespugli.

Non c'erano registratori, microfoni parabolici e laser che ti rimbalzano sugli occhiali.

E bisogna pur riconoscere che la civiltà esisteva lo stesso”.

Whitfield Diffie

“CODICI E SEGRETI” Simon Singhed. BUR isbn 88-17-12539-3

http://en.wikipedia.org/wiki/Portal:Cryptography

http://it.wikipedia.org/wiki/Numbers_station

claudio@tanci.it