Cifrari Storici - Plone sitebabaoglu/courses/security09-10/lucidi/...© Babaoglu 2001-2009...

ALMA MATER STUDIORUM – UNIVERSITA’ DI BOLOGNA

Cifrari Storici

Ozalp Babaoglu

© Babaoglu 2001-2009 Sicurezza 2

Prologo

! Motivazioni: ! Scopi educativi: concetti, tecniche di base,…! Divertimento: settimana enigmistica…

! Crittografia manuale! Sono note tecniche statistiche per forzarli!! Nota:

! Messaggi e crittogrammi composti di lettere! Chiave segreta: esiste oppure no (degenere)


Chiave k = shift ciclico

C(mi) = lettera in posizione (pos(m

i) + k) mod 26

D(ci) = lettera in posizione (pos(c

i) – k) mod 26

è u n a b e l l a g i oo g g i

h a q d e h o o d l n rr l l n

Cifrario di Cesare

C D

f g h i l m n o p q r s t u v za b c d e

f g h i l m n o p q r s t u v z a b cd e


Cifrario a Sostituzione

! Ammettiamo tutte le possibili permutazioni dell’alfabeto! sono (21! – 1), un numero spropositatamente grande!

! Chiave k = <BFRULMZQWEA...> = una permutazione! Questo cifrario è sicuro? No, attacco statistico

! Istogrammi di frequenza delle lettere nelle frasi in italiano! Istogrammi di frequenza delle lettere nel crittogramma! Molti crittogrammi a disposizione!

AB

CD

AB

CD


a ABCDEFGHIJKLMNO..b BCDEFGHIJKLMNO...c CDEFGHIJKLMNO...d DEFGHIJKLMNO...... ...y YZABCDEFGHIJK...z ZABCDEFGHIJ...

abcdefghijklmno...

- Monoalfabetico ogni |k| caratteri- Attacco statistico possibile, ma difficile

Cifrario Polialfabetico

! Usa più cifrari a sostituzione seconda la posizione delle lettere nel messaggio in chiaro

chiave k c a k c a ...

plaintext D Y D B B E ...

cyphertext N A D L D E ...


Cifrario Poligramma

! Invece di sostituire singole lettere nel messaggio in chiaro, sostituire blocchi di lettere

! Esempio (blocchi da 3)! AAA " SOM

! AAB " PLW

! ABA " RTQ

! ABB " SLL

! …

! Nasconde informazione sulla frequenza di singole lettere e di due lettere


Cifrario a Trasposizione

! Maintain the same set of letters in the cyphertext as in the plaintext but change their order

4312567

attackpostpone

duntilt

hreepmx

key

plaintext

Cyphertext: ttneaptetsuraodhcoipknlmpetx



! Can be repeated multiple times

4312567

ttneaptetsurao

dhcoipk

nlmpetx

output: nscmeuoptthltednariepapttokx

plaintext

key



01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

03 10 17 24 04 11 18 25 02 09 16 23 01 08 15 22 05 12 19 26 06 13 20 27 07 14 21 28

After one transposition:

After two transpositions:

17 09 05 27 24 16 12 07 10 02 22 20 03 25 15 13 04 23 19 14 11 01 26 21 18 08 06 28

Basis for “rotor machines” such as Enigma andPurple that were used during World War II



1 2 3 4 5 6 7 8 9 10 11 12 13 14

m = c i v e d i a m o t a r d i

c = c i d v a i e m o r t i d a

!

! = <1,2,4,7,3,6,5>

• In general, transposition is a permutation of the letters• With a given period (7)• May be expensive to implement (memory)• Attacks based on frequency can reveal the language• Large periods make attacks difficult


Cifrari Perfetti: One-Time Pad


One-time pad: esempio

Messaggio: 1 1 0 1 0 0 0 1

Chiave (Pad): 1 0 0 0 1 1 1 0

Crittogramma0 1 0 1 1 1 1 1"

" 1 1 0 1 0 0 0 1 Messaggio

Based on modular arithmetic:ci = mi + ki mod 2 (also called “exclusive or”)For textual messages: ci = mi + ki mod 26


Pregi e Difetti

! Se ogni bit della chiave è generato casualmente, allora conoscere un bit del crittogramma non fornisce nessuna informazione aggiuntiva sul corrispondente bit del messaggio: cifrario perfetto

! La chiave (pad):! è lunga (quanto il messaggio)! si consuma (one-time)! occorre scambiarsela


DES Data Encryption

Standard


Un po’ di storia…

! Nel 1972, l’NBS (National Bureau of Standards. Oggi NIST: National Institute of Standards and Technology) iniziò un programma per proteggere le comunicazioni non classificate

! Lo scenario era interessante:! NSA (National Security Agency) disponeva di molte conoscenze

in materia di cifrari e metodi di decrittazione! Esistevano molti prodotti pressoché oscuri, non certificati e non

compatibili

! Nel 1973, l’NBS pubblicò un “call for proposals”:! Sistema a chiave segreta (certificazione e chiarezza)! Realizzabile in hardware (compatibilità)

! Bando andò pressoché deserto© Babaoglu 2001-2009 Sicurezza 16

…. ancora un po’

! In un bando successivo IBM propose un sistema simile al suo prodotto Lucifer (operazioni logiche su gruppi di bit)

! Poco dopo NSA certificò Lucifer con il nome di DES: fece commenti e propose variazioni! Chiave ridotta da 128 bit a 64 bit! Modifiche significative alla funzione S-box

! Diverse agenzie replicarono in modo allarmato !!! Dopo alcune indagini il DES fu certificato e reso pubblico nel 1977! Primo esempio di cifrario robusto (con certificazione NSA) che i

ricercatori potevano studiare! È stato certificato pressoché ogni 5 anni, dal 1998 non è più

considerato sicuro. Ad esso si preferisce il Triplo-DES! AES: il cifrario simmetrico del prossimo millennio!


Caratteristiche Principali di DES

! Codifica Simmetrica! Codifica a blocchi! Blocco = 64 bit! Chiave = 64 Bit (solo 56 usati, altri 8 per parità)


Operazioni di Base

! Permutazione! Sostituzione! Espansione! Contrazione! Shift Circolare (destro e sinistro)


1

2

3

4

5

6

5

1

6

3

2

4

P=(5,1,6,3,2,4)

Un bit in ingresso determina un bit in uscita

Permutazione


Ogni ingresso può determinare ogni uscita

000 010001 011010 100011 111100 110 101 000110 001111 101

Sostituzione


3

3

3

3

Numero delle uscite maggiore del numero degli ingressi

Esempio:

Espansione


Numero delle uscite minore del numero degli ingressi

Esempio (scelta):

1

2

3

4

5

6

1

6

3

2

Alcuni ingressi non influenzano le uscite, vengono scartati

Contrazione


1

2

3

4

5

6

1

2

4

6

6

4

2

1

Scelta (contrazione)

Permutazione

Scelta Permutata


Round 1

Round 2

Round 16

Scambio a 32 bit

Scelta Permutata 2

Scelta Permutata 2

Scelta Permutata 2

Shift circolare a Sinistra



64 bit testo in chiaro 64 bit chiave

k1

k2

k16

64 bit testo cifrato

Permutazione Iniziale : PI

Permutazione Finale: PF

Scelta Permutata: T

DES Overview


Mancano bit: 8,16,24,32,40,48,56,64Servono come controllo di parità

DES: PI, PF, e T


L i-1

L i R i

R i-1 C i-1 D i-1

C i D i

Shift a sinistra Shift a sinistra

Contrazione/PermutazioneXOR

E-Box

S-Box

P-Box

32 32

48

48

32

32

3232

48 Ki

28 28

2828

DES: Detail of a Round

XOR


E-Box: Espansione/Permutazione

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 2 3 4 5 6 7 8 9 10 1112 1314 15 16 1718 1920 21 22 2324

32

48

(Schneier fig. 12.3)

E

32

48


s1 s2 s3 s4 s5 s6 s7 s8

P

32 bit

"48 bit K (48 bit)

E

Sostituzione/Scelta


DES: S-Box

Bits 1 and 6 select a row, bits 2-5 select a columnto read a 4-bit value from one of eight possible maps

© Babaoglu 2001-2009 Sicurezza

DES: P-Box

30

! Straight permutation of 32 bits

16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 1002 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25


RSA:Rivest, Shamir,

Adelman


E’ necessaria la chiave segreta?

! A manda ad B il suo lucchetto aperto! B chiude lo scrigno con il lucchetto ricevuto da A e glielo

spedisce! A riceve lo scrigno e lo apre !!!


! Un lucchetto è una funzione one-way con trapdoor !

! Infatti tutti possono chiudere un lucchetto pur senza possedere la chiave

! Nessuno può aprire un lucchetto senza avere la chiave! La cassetta delle lettere è

un’altra funzione one-way con trapdoor

Funzioni One-way con Trapdoor


Chiave Pubblica

! Per ottenere un protocollo a chiave pubblica occorre trovare una funzione matematica one-way con trapdoor!

! Cioè una funzione facile da calcolare e difficile da invertire a meno di possedere qualche informazione aggiuntiva (chiave)

! La Teoria dei numeri ci viene in aiuto…


Notation


Facts

Se p e q sono due numeri primi, allora:


RSA

! Generazione delle chiavi

! Codifica. Encryption: C(m)

! Decodifica. Decryption: D(c)


Scelgo due numeri primi grandi p, q

Calcolo n = p"qScelgo e tale per cui GCD(e, !(n)) = 1Calcolo d tale per cui d"e mod !(n) = 1

Chiave Pubblica = (e,n)

Chiave Privata = (d,n)

RSA: Generazione delle chiavi


C(m) = me mod n

RSA: Encryption


D(c) = cd mod n

RSA: Decryption


• Scegliamo p=61, q=53

• Dunque n=61"53=3233, !(n) = (61 # 1)(53 # 1) = 3120• Scegliamo e=17 (verificare che GCD(e, !(n))=1)

• Calcoliamo d=2753 e verificare che d"e mod !(n) = 1

d"e = 27533 " 17 = 46801 d"e mod !(n) = 46801 mod 3120 = 1 visto che 15 " 3120 + 1 = 46801

• Quindi il nostro sistema ha le seguenti chiavi: K[priv] = (2753,3233) K[pub] = (17,3233)

RSA: esempio


• Sia m=123

Codifica: 12317 mod 3233 = c = 855

Decodifica: 8552753 mod 3233 = 123 = m

RSA: esempio


Domande

! Come codificare il messaggio iniziale M come un intero 0 < m < n ?

! Chi ci assicura che D(C(m)) = m?! Chi dice che RSA sia sicuro?! RSA è efficiente?! Come eseguo le varie operazioni?

Date post:	19-Jan-2021
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Cifrari Storici - Plone sitebabaoglu/courses/security09-10/lucidi/...© Babaoglu 2001-2009...

Documents