Cryptocache: Part 4 Mystery Cache

[ENGLISH HERE]

Quarta e ultima cache dedicata alla crittografia (forse... potrebbe essercene una riassuntiva!).

Nella precedente parte avevamo visto un metodo efficace per cifrare le informazioni personali (file), su propri dispositivi digitali.
Quando invece le informazioni devono essere condivise o trasmesse, magari a molti chilometri di distanza grazie ad internet, diventa impossibile utilizzare una sola password per cifrare e decifrare il contenuto del file, poiché questa dovrebbe essere condivisa (quindi trasmessa in maniera sicura) a tutti coloro che devono poter cifrare e decifrare le informazioni condivise.
Nel 1976 circa, Diffie ed Hellman teorizzano e descrivono una algoritmo di cifratura a chiave asimmetrica, ossia in cui le chiavi di cifratura e quella di decifratura sono diverse. Nel 1977 Rivest, Shamir e Adleman (fondatori della RSA Datagroup) creano il primo software di cifratura basato su questo paradigma, molto efficiente e tutt'ora utilizzato in software come PGP o nella firma digitale.
Il paradigma della cifratura a chiave asimmetrica prevede che con una chiave pubblica si cifrino le informazioni mentre, con la chiave privata ad essa correlata, si possa effettuare la decifratura. Ogni utente possiede quindi due chiavi, una pubblica che può essere liberamente distribuita (via e-mail, tramite certificati digitali o con server di distribuzione delle chiavi) poiché servirà solo per cifrare, mentre una privata che deve essere conservata gelosamente (poiché l'unica in grado di effettuare la decifratura).
Il funzionamento di tutto ciò, si basa su alcuni concetti matematici:
- teoria dei numeri primi: esistono infiniti numeri primi, distribuiti in maniera "casuale". Un numero si dice primo quando può essere diviso perfettamente (cioè senza generare resto) solo per se stesso e per 1.
- fattorizzazione: ciascun numero è il risultato del prodotto di uno o più numeri primi detti "fattori". Ad esempio, 6 è il risultato della moltiplicazione di due numeri primi, 2 e 3, mentre 7 ha solo se stesso come fattore, poiché primo. Questo implica che un qualsiasi numero può essere perfettamente divisibile (cioè senza generazione di "resto") solo per 1, per se stesso, per uno dei suoi fattori o per il prodotto di essi. Ad esempio, 12 (avente come fattorizzazione 2x2x3) può essere diviso per 1,2,3,4 (2x2),6 (2x3) o per 12 (2x2x3). 11 che è numero primo, può essere diviso solo per 1 e per se stesso.
La fattorizzazione di un numero è univoca e, in caso di numeri aventi come fattori propri dei numeri primi molto grossi, richiede molto tempo poiché devono essere provati tutti i numeri primi precedenti, uno ad uno; il problema è definito matematicamente "arduo".
- aritmetica modulare: secondo il teorema fondamentale dell'aritmetica, ogni numero può essere scritto come il risultato di una moltiplicazione e di una somma, ossia: N = aX + R. Ad esempio, 7 = 2x3 + 1, ove R è il resto. In parole povere, se dividiamo 7 per 3, otteniamo come resto 1. L'aritmetica modulare si ha utilizzando l'operatore modulare, "mod", per un determinato n. In pratica è quella operazione che restituisce il resto che si ha dividendo un numero x per un divisore n. Ad esempio, 9 mod 6 = 3, anche 3 mod 6 = 3. In quest'ultimo esempio si dice che 3 e 9 sono "congrui modulo 6". Si evince che in ogni operazione modulare, il risultato può andare da 0 a n-1 (per trovare la cache comunque non è necessario saper utilizzare tale operatore poiché presente, ad esempio, nella calcolatrice di Windows, o in altre, di tipo scientifico).

Premesso tutto ciò, sia "l" la lunghezza del blocco da cifrare, l'algoritmo di cifratura a chiave asimmetrica RSA, funziona nel seguente modo:
1) Si scelgono 2 numeri primi p e q lunghi "l/2" (cioè ciascuno la metà della lunghezza massima del blocco da cifrare); ad esempio p=7 e q=13. Quindi si determina n come p x q, ossia nel nostro esempio: n = 7x13 = 91.
2) Ora si sceglie a caso un valore e, tale che e e (p-1)(q-1) siano "primi relativi"; in pratica e ed il risultato di (p-1)x(q-1) non devono avere fattori in comune, MCD(e,(p-1)(q-1))=1. Nel nostro esempio, se prendiamo e=3, si ha che MCD(3,72)=3 e non va bene. Se invece prendiamo e=5, allora MCD(5,72)=1.
3) Si calcola d come d=e^-1 mod (p-1)(q-1), che equivale a dire che exd=1 mod (p-1)(q-1) (per convenzione, qui sopra il simbolo ^ rappresenta l'elevamento a potenza, quindi e^-1 mod (p-1)(q-1), significa elevare alla -1 il valore e quindi applicare l'operatore modulare con divisore pari a (p-1)(q-1) ). Nel nostro esempio, d sarà uguale a 29 (poiché 29x5=145 e 145mod72=1).
4) La chiave pubblica è formata da n e da e, cioè pubkey=(91,5) nel nostro caso.
5) La chiave privata è formata da n e da d, cioè privkey=(91,29) nel nostro caso
6) Per ottenere un blocco di codice cifrato C a partire da un blocco M di codice in chiaro si effettua il seguente calcolo C=M^e mod n . Nel nostro caso, se dobbiamo cifrare il valore 23 (i valori da cifrare devono essere compresi tra 0 e n-1, quindi tra 0 e 90), il valore cifrato sarà dato da C = 23^5 mod 91 = 4 .
7) Per ottenere il codice in chiaro M a partire da un blocco C di codice cifrato si effettua il seguente calcolo M=C^d mod n . Nel nostro caso, se abbiamo il numero cifrato 4, M = 4^29 mod 91 = 23.
Provare per credere!
Alcune considerazioni veloci:
- i calcoli appena esposti sono semplici da effettuare e veloci per una macchina, ma anche a mano visto i valori bassi scelti nell'esempio. Il sistema è sicuro poiché data la chiave pubblica (n,e) per decifrare un messaggio con essa cifrato, serve conoscere anche d; ma per ottenere d, si deve innanzi tutto fattorizzare n per poter risalire a (p-1) e (q-1), quindi calcolare d come descritto sopra. Poiché n è il prodotto di due numeri primi (p e q) molto grandi, si impiega troppo tempo per determinarli.
- l'operazione di cifratura è invertibile perché praticamente il messaggio iniziale viene cifrato elevandolo alla "e" e poi decifrato elevandolo alla "d" (entrambi le operazioni modulo n, naturalmente); il messaggio originale quindi subisce una elevazione alla "e"x"d" (che per definizione è uguale a 1 modulo (p-1)(q-1)), quindi applicandovi l'operatore modulare con divisore uguale n, restituisce se stesso (cioè il messaggio in chiaro).
----------------------------------------------
Le coordinate della cache sono state suddivise nei seguenti blocchi di cifratura:
N A°B,C
E D°E,F
quindi cifrate con la chiave pubblica (n=3337,e=79), ed i risultati sono stati:
N 1921°2877,1111'
E 2120°827,2865'
Occorre dunque determinare "d" per poter decifrare le coordinate corrette.
Nella cache è presente il solo logbook. Portarsi dietro un lapis o una penna.
Rimettere la cache come trovata e state attenti ai babbani.

[ITALIANO QUI]