Crittografia

OII 2018-11-15 – 18

Alice e Bob si stanno scambiano messaggi cifrati e Hack ha intercettato un messaggio: “GONSIUZMS ITTO VZGO”
Hack ha scoperto che Alice e Bob usano il cifrario di Cesare (traslano l’alfabeto italiano di una costante k, per es. se k=1 A diventa B, B diventa C, e così via fino a Z che diventa A).
Alfabeto: A, B, C, D, E, F, G, H, I, L, M, N, O, P, Q, R, S, T, U, V, Z.
Trova la costante k, per rispondere alla seguente domanda: quale è il messaggio MESS scambiato da Alice e Bob?

Soluzione

Per tentativi…

Con k=8 appare il messaggio originale.

Crittografia asimmetrica

Chiave pubblica e chiave privata

  1. X genera una chiave pubblica PK e una chiave privata SK
  2. X rende nota la chiave pubblica a chiunque voglia comunicare con lui
  3. Y scrive il messaggio m, lo cifra tramite la chiave pubblica di X e lo spedisce a X
  4. X riceve il messaggio cifrato c, lo decifra tramite la chiave privata e ottiene m

Osserva

  • Se Z conosce la chiave pubblica PK e intercetta c non può ottenere m perché non conosce la chiave privata SK.
  • Se Z vuole scoprire la chiave privata SK deve risolvere un problema numerico noto ma difficilissimo

RSA

  • Rivest Shamir Adleman
  • il nome è l’acronimo dei cognomi di tre ricercatori del MIT
    • Ronald Rivest
    • Adi Shamir
    • Leonard Adleman
  • presentato nel 1978
  • brevettato nel 1983
  • scaduto nel 2000
  • per forzarlo è necessario fattorizzare un numero enorme come prodotto di due numeri primi
  • oggi viene considerato sicuro (non fattorizzabile) un numero che in base 10 ha almeno 300 cifre, quindi una chiave di 1024 bit e oltre

Generazione delle chiavi

Scelgo due numeri primi a caso (grandi a piacere…)

  • p = 3
  • q = 11

Calcolo

  • (p-1)(q-1)
     2*10 = 20
  • n = p*q
    3*11 = 33

Scelgo

  • e = 7 tale che
    • e < n
    • coprimo con (p-1)(q-1)
  • d = 3 tale che
    • e*d mod (p-1)(q-1) = 1
      3*7 mod 20 = 21 mod 20 = 1

Ottengo

  • PK = (n,e) = (33, 7), chiave pubblica
  • SK = (n,d) = (33, 3), chiave privata
Cifratura Decifratura
Sia m = 15 il messaggio in chiaro.

Calcolo: c = me (mod n)

  • 157 (mod 33) = 27

e lo spedisco

 Ricevo il messaggio cifrato c = 27.

Calcolo: m = cd (mod n)

  • 273 (mod 33) = 15

e ottengo il messaggio in chiaro!

DSA

  • Digital Signature Algorithm
  • Un’alternativa alla difficoltà dell’operazione di fattorizzazione
  • Utilizza il logaritmo discreto

RISORSE ONLINE

Crittografia simmetrica

Cronologia

  • 1972
    1974: Richieste pubbliche di uno standard di cifratura
  • 1975: DES, pubblicazione
  • 1977: FIPS PUB 46, standard
  • 1988: FIPS 46-1
  • 1993: FIPS 46-2
  • 1999: FIPS 46-3, si raccomanda il Triple DES (TDES, 2TDES)
  • 2001: FIPS 197: AES (Advanced Encryption Standard), selezionato con competizione internazionale
  • 2005: Ritiro del FIPS 46-3

DES

  • Data Encryption Standard
  • il nome originale dell’algoritmo ideato da IBM era DEA (Data Encryption Algorithm) e derivava dal progetto Lucifer
  • il blocco in chiaro è di 64 bit
  • il testo cifrato è della stessa lunghezza
  • la chiave ha 56 bit (IBM intendeva utilizzare una chiave a 128 bit ma l’NSA ha spinto per 64 bit per poi giungere a 56 bit)
  • 8 parole di 8 bit, ogni parola è di 7 bit e un bit di parità
  • 16 fasi identiche di
    • espansione
    • miscelazione con la chiave
    • sostituzione
    • permutazione
  • Altri sistemi simili: RC5, Blowfish, IDEA, NewDES, SAFER, CAST5 e FEAL
  • Evoluzioni: DES-X, GDES

AES

  • Advanced Encryption Standard
  • il blocco in chiaro è di 128 bit
  • la chiave può essere di 128, 192 o 256
  • l’implentazione software è più veloce del DES
  • proposto da due crittografi belgi col nome Rijndael, deriva da Square e SHARK
  • primo classificato su Serpent, Twofish, RS6, MARS, …

RISORSE ONLINE

Cifrario di Cesare

Il Cifrario di Cesare:

  • il cifrario per sostituzione monoalfabetico più antico e famoso
  • ogni carattere del messaggio in chiaro viene cifrato tramite il carattere corrispondente a 3 posizioni in avanti nell’alfabeto
  • Vedi: Wikipedia: Cifrario_di_Cesare

Per ogni carattere del messaggio

  1. considera il suo codice ASCII: A –> 65
  2. incremento il codice di 3: 65 –> 68
  3. converti il codice in carattere: 68 –> D
  4. analogamente (-3) per decifrare ogni carattere del messaggio cifrato.
In chiaro A B C D E F …
Cifrato (+3) D E F G H I …
Decifrato (-3) A B C D E F …

Prova…

In chiaro

Codici
Codici+3
Cifrato

Per rendere la cifratura più simile a quella tradizionale

  1. filtra il messaggio in modo che sia costituito soltanto da lettere dalla A alla Z
  2. considera circolare la trasformazione +3.
In chiaro A B C ... X Y Z
Cifrato (+3) D E F ... A B C
Decifrato (-3) A B C ... X Y Z

Prova...

In chiaro

Filtrato
Cifrato

ROT13

Un caso particolare e curioso di cifrario

  • la trasformazione utilizzata è +13
  • le operazioni di cifratura e decifratura possono essere svolte con la stessa funzione!
In chiaro A B C ... X Y Z
Cifrato (+13) N O P ... K L M
Decifrato (+13) A B C ... X Y Z

Prova...

In chiaro

Filtrato
Cifrato

Crittografia

Marvin Minski ha codificato una sua frase famosa cambiando ogni lettera con quella che la precede o la segue in ordine alfabetico (A segue Z e Z precede A).

ONM RJ DBOHRBF TM DPMDFSUP RD ONM KP TJ JNQZSB JO NPKSH LNCH

Sapete codificarla?

Osserva le possibili codifiche per ogni lettera della frase

e scegli di conseguenza

Risposta

NON SI CAPISCE UN CONCETTO SE NON LO SI IMPARA IN MOLTI MODI