Pillole di crittografia teorica 1: Introduzione e tecniche classiche di crittografia

Tempo di lettura: 9 minuti
Data pubblicazione: November 29, 2016

Con questo articolo inzierò una serie di scritti sulla crittografia teorica, iniziando con le basi e le tecniche classiche, passando per DES, AES, Web of Trust, fino ad arrivare ad RSA. L’idea è dare delle basi di crittografia, le quali, sebbene dal punto di vista pratico non siano prettamente rilevanti, sono utilissime dal punto di vista teorico. Ovviamente non riuscirò a spiegare in modo approfondito i vari algoritmi, visto che servono nozioni avanzate di matematica discreta, ma darò la possibilità a chiunque voglia approfondire di poterlo fare in modo autonomo.

Introduzione

La crittografia è la branca della crittologia che si occupa di scrivere i metodi per rendere un messaggio ofuscato, quindi gli algoritmi e protoccoli per nascondere un messaggio in modo da non essere comprensibile a persone non autorizzate. Le branche affini ad essa sono:

  • Crittoanalisi: ossia la scienza che si occupa di cercare vulnerabilità in sistemi crittografici;
  • Crittologia: incorpora sia aspetti della critografia che gli aspetti della crittonalisi.

Prima di iniziare, utilizzerò una serie di termini di cui darò solamente ora la definizione, che sono:

  1. Plain text: riferito al testo in chiaro;
  2. Cypher text: riferito al testo cifrato;
  3. Cifratura/Crittografia: è la conversione da plain text a cypher text;
  4. Decifratura/Decrittografia: è la conversione da cyphert text a plain text.

Tipo di attacco

La forza di un algoritmo deve essere indipendente dal numero di messaggi e deve essere computazionalmente intrattabile. Per esserlo deve soddisfare due criteri principali:

  • il costo della violazione del testo cifrato supera il valore delle informazioni crittografate;
  • il tempo richiesto per violare il testo cifrato è superiore alla vita utile delle informazioni. Questo significa che se un attacco di forza bruta necessita migliai anni per essere portato a termine, esso andrà bene.

Esistono diversi attacchi ad un cifrario, i principali sono:

  1. Cypher-text only(CO) : si ha a ha disposizione solamente il testo cifrato;
  2. Known plain-text(KP) : si conoscono solo alcuni messaggi (una coppia cypher-plain);
  3. Choosen plain-text(CP) : sostituisco il messaggio dell’utente con il mio messaggio
  4. Choosen cypher-text(CC) : posso scegliere sia il messaggio in chiaro sia in cypher

I due tipi di attacco a un algoritmo di crittografia sono l’analisi crittografica, che si basa sulle caratteristiche dell’algoritmo di cifratura, e l'attacco a forza bruta, che consiste nel tentare tutte le possibili chiavi.

Principio di Kerckhoffs

L’attaccante di noi sa tutto. L’algoritmo e il codice sono pubblici, l’unica cosa che non si sa è la mia password (chiave). Questo principio afferma quindi che la sicurezza di un crittosistema non deve dipendere dal tenere celato il crittoalgoritmo ma solo dal tenere celata la chiave.

Tipi di crittografia

Crittografia simmetrica

fa uso della stessa chiave per cifrare e decifrare i messaggi (ex. DES,AES) ed è chiamata anche Crittografia convenzionale. La crittografia simmetrica trasforma il testo in chiaro in testo cifrato utilizzando un algoritmo di crittografia con una chiave segreta e presuppone che le due parti siano già in possesso delle chiavi. Per riavere il testo in chiaro basta applicare la medesima chiave al testo cifrato.

Il modello a cifratura simmetrica prevede quindi:

  • Testo in chiaro;
  • Algoritmo di crittografia;
  • Chiave segreta;
  • Testo cifrato: il messaggio codificato che viene prodotto come output;
  • Algoritmo di decrittografia: sostanzialmente l’algoritmo di crittografia eseguito al contrario.

Crittografia asimmetrica

ad ogni persona coinvolta nella comunicazione è associata una coppia di chiavi:

  • La chiave pubblica, che deve essere distribuita per decrittografare;
  • La chiave privata;

Il meccanismo si basa sul fatto che, se con una delle due chiavi si cifra (o codifica) un messaggio, allora quest’ultimo sarà decifrato solo con l’altra.

In un sistema di crittografia a chiave pubblica (ad esempio: RSA), chiunque può crittografare un messaggio utilizzando la chiave pubblica del destinatario, ma tale messaggio può essere decifrato solo con la chiave privata del destinatario. La forza di un sistema di crittografia a chiave pubblica si basa sul grado di difficoltà per una chiave privata correttamente generata da determinare la sua chiave pubblica corrispondente.

La sicurezza dipende quindi solo mantenere la chiave privata segreta, e la chiave pubblica può essere pubblicata senza compromettere la sicurezza.

Crittografia asimmetrica
Crittografia asimmetrica

Steganografia

è una tecnica utilizzata per celare un messaggio segreto all’interno di un altro messaggio in modo tale che nessuno possa individuare la presenza e/o i contenuti del messaggio nascosto.

Tecniche di sostituzione

Cifratura di Cesare

La cifratura di Cesare prevede la sostituzione di ciascuna lettera con la lettera che si trova a tre posizioni di distanza nell’alfabeto.

L’algoritmo può essere espresso nel seguente modo: C=E(3,p)=(p+3) mod 26

Per decrittografare: p=D(k,C)=(C-k) mod 26

In questa cifratura si può usare la forza bruta perchè le chiavi sono solamente 25, gli algoritmi di crittografia e decrittografia sono noti e il linguaggio del testo cifrato è facilmente riconoscibile.

Cifrario di Cesare
Cifrario di Cesare

Cifratura monoalfabetica

La cifratura a sostituzione monoalfabetica utilizza un alfabeto per il testo in chiaro e una permutazione dello stesso per il testo cifrato. La chiave del sistema è rappresentata dalla permutazione. Se l’attaccante conosce la natura del testo in chiaro potrebbe sfruttare regolarità persenti in esso per attaccare (ex. Frequenza relativa delle lettere nel testo).

Queste cifrature sono infatti facili da violare poiché conservano le informazioni di frequenza dell’alfabeto originario.

Cifratura Playfair

È una cifratura multi-lettera, si basa sull’uso di una matrice 5x5 costruita utilizzando una parola chiave. La tecnica cifra coppie di lettere invece che una singola lettera, come nei precedenti. Le regole da applicare per cifrare sono:

  1. se entrambe le lettere sono le stesse bisogna aggiungere un “x” dopo la prima lettera;
  2. Se le lettere appaiono nella stessa riga della tabella, vengono codificate con le lettere alla propria destra;
  3. Se le lettere appaiono nella stessa colonna della tabella, vengono sostituite con le lettere sottostanti;
  4. negli altri casi, ciascuna lettera di testo in chiaro di una coppia verrà sostituita dalla lettera che si trova nella stessa riga e colonna occupata dall’altra lettera di testo in chiaro.

Cifratura Hill

L’algoritmo di crittografia prende un sequenza di _m _lettere in chiaro e le sostituisce con m lettere di testo cifrato. La sostituzione è determinata da m equazioni lineari in cui a ciascun carattere viene assegnato un valore numerico.

La formula di cifratura è:C=E(K,P)=KP mod26

La formula di decifratura è: P=D(K;C)=K(^-1)C mod26

La potenza di questo algoritmo deriva del fatto che essa nasconde completamente le frequenze mono-lettera.

Cifratura polialfabetica

La tecnica più nota è la cifratura di Vigenerè. In questa tecnica, l’insieme di regole di sostituzione monoalfabetica è costituito da 26 cifrature di Cesare con scorrimenti da 0 a 25. Ogni cifratura è denotata da una lettere chiave che è la lettera che sostituisce la lettera in chiaro “a”.

One-Time Pad

In questo schema viene utilizzata una chiave lunga quanto il messaggio in chiaro; inoltre, essa dev’essere utilizzata per crittografare e decrittografare un solo messaggio, poi scartata. Le difficoltà principali, sebbene esso sia inviolabile, sono:

  • bisogna creare grandi quantità di chiavi casuali;
  • bisogna distribuire e proteggere le chiavi.

Altre cifrature possono essere:

Conclusioni

Come si può notare, la crittografia classica ha moltissime tecniche che porteranno poi le basi agli ideatori dei moderni algoritmi crittografici. Chiunque si sia interessato alla storia e alle tecniche passate consiglio vivamente _“Simon Singh - Codici & Segreti”. _