Algoritmi di codifica:
RSA ed altri

 

    INDICE:

 

    Algoritmi crittografici

 

ALGORITMI CRITTOGRAFICI

E' molto interessante studiare più in dettaglio i diversi algoritmi crittografici utilizzati fin dai tempi antichi che ai giorni nostri. Parleremo dunque di algoritmi a chiave privata o simmetrica, ma ancor di più di quelli a chiave pubblica o asimmetrica.

    Definizione di algoritmo

Si definisce algoritmo crittografico una trasformazione matematica reversibile di una sequenza di dati. Tale trasformazione opera sul così detto "testo in chiaro" e mediante un'opportuna funzione del testo in chiaro e di un parametro, detto "chiave", ottiene il "testo cifrato". Dato lo stesso algoritmo e lo stesso testo, ma una diversa chiave si genera un diverso testo cifrato.


Quando fu inventata la crittografia si decise di non rendere noti gli algoritmi, successivamente si optò per la pubblicazione degli algoritmi. Tale scelta venne dettata dalla necessità di testare gli algoritmi stessi: se si conosce come è fatto l'algoritmo se ne puo' ricavare una forzatura (o crack) che per ricerca esaustiva (brute force) riesca a decriptare il testo; tuttavia se il crack non vi riesce l'algoritmo è veramente dichiarato inattaccabile.

    I primi "meccanismi" crittografici

Le più antiche notizie sicure sono probabilmente quelle sulla scitala lacedemonica. Consisteva in un bastone su cui si avvolgeva ad elica un nastro di cuoio; sul nastro si scriveva per colonne parallele all'asse del bastone, e lettera per lettera, il testo segreto. Tolto il nastro dal bastone il testo vi risultava trasposto in modo regolare ma sufficiente per evitare la lettura senza un secondo bastone uguale al primo.

 

Tra il 360 e il 390 venne compilato da Enea il tattico, generale della lega arcadica, il primo trattato di cifre il cui XXI capitolo tratta appunto di messaggi segreti.  In questo viene descritto un disco sulla zona esterna del quale erano contenuti

 24 fori,ciascuno corrispondente ad una lettera dell'alfabeto. Un filo, partendo da un foro centrale, si avvolgeva passando per i fori delle successive lettere del testo: all'arrivo, riportate le lettere sul disco, si svolgeva il filo segnando le lettere da esso indicate: il testo si doveva poi leggere a rovescio. Le vocali spesso erano sostituite da gruppi di puntini.

 

In questo stesso periodo vennero ideati codici cifrati indiani ed ebraici utilizzati in particolar modo per celare nomi propri, innominabili o sacrileghi.

Numerosi testi e documenti greci antichi contengono tratti cifrati, specialmente nomi propri, ma si trovano anche interi scritti cifrati con sostituzione semplice e con alfabeti generalmente a numero.

    La scacchiera di Polibio

Lo storico greco Polibio (~200-118AC), nelle sue Storie (Libro X) descrive il più antico esempio di codice poligrafico, che attribuisce ai suoi contemporanei Cleoxeno e Democleito; l'idea è quella di cifrare una lettera con una coppia di numeri compresi tra 1 e 5, in base ad una scacchiera 5x5. In tal modo il messaggio può essere trasmesso con due gruppi di cinque torce (p.es. 1,5 = una torcia accesa a destra, cinque a sinistra). In effetti più che di un codice segreto, si tratta di un sistema di telecomunicazione, di fatto un telegrafo ottico. Telegrafi a torce esistevano da molti secoli ed erano stati descritti da Enea il tattico intorno al 350AC, ma erano basati su un limitato elenco di messaggi possibili; quello di Polibio si basa invece sulla scomposizione del messaggio nelle singole lettere ed è quindi in grado di trasmettere qualsiasi messaggio.

 

1

2

3

4

5

1

a

b

c

d

e

2

f

g

h

i

j

3

k, q

l

m

n

o

4

p

r

s

t

u

5

v

w

x

y

z

Nell'alfabeto greco ci sono 24 lettere ed avanza quindi un carattere che Polibio proponeva di usare come segnale di sincronizzazione (inizio e fine trasmissione). Nell'esempio seguente si utilizzerà, al posto di quello greco, l'alfabeto internazionale il quale ha viceversa il difetto di essere formato da 26 caratteri; così per poter costruire il quadrato necessario per la cifratura bisognerà "fondere" due lettere rare ma non foneticamente differenti nella stessa casella, in questo caso la k e la q. In questo modo si otterrà la tabella a lato.

 

Ogni lettera viene quindi rappresentata da due numeri, guardando la riga e la colonna in cui la lettera si trova. Per esempio, a=11 e r=42.

Quindi la frase Attenzione agli scogli dopo la cifratura risulterà:

 

1144441534552435341511223224431335223224

 

La scacchiera di Polibio ha alcune importanti caratteristiche, e cioé la riduzione nel numero di caratteri utilizzati, la conversione in numeri e la riduzione di un simbolo in due parti che sono utilizzabili separatamente. La sua importanza nella storia della crittografia sta nell'essere alla base di altri codici di cifratura come il Playfair Cipher o il cifrario campale germanico usato nella prima guerra mondiale.

    Il codice di Giulio Cesare

Svetonio, nella "Vita dei dodici Cesari", racconta che Giulio Cesare usava per le sue corrispondenze riservate un codice di sostituzione molto semplice, nel quale la lettera chiara veniva sostituita dalla lettera che la segue di tre posti nell'alfabeto: la lettera A è sostituita dalla D, la B dalla E e così via fino alle ultime lettere che sono cifrate con le prime come nella tabella che segue:

 

Chiaro       a b c d e f g h i j k l m n o p q r s t u v w x y z
Cifrato      D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Prendendo come esempio la frase Auguri di buon compleanno si otterrà il seguente messaggio cifrato:

 
Chiaro		auguridibuoncompleanno
Cifrato		dxjxulglexrqfrpsohdqqr

Più in generale si dice codice di Cesare un codice nel quale la lettera del messaggio chiaro viene spostata di un numero fisso di posti, non necessariamente tre.

Poiché l'alfabeto internazionale è composto da 26 caratteri sono possibili 26 codici di Cesare diversi dei quali uno (quello che comporta uno spostamento di zero posizioni) darà un cifrato uguale al messaggio chiaro iniziale.

    Il metodo di Vigenere

Blaise de Vigenere pubblicò nel 1586 un trattato di cifre nel quale proponeva tra gli altri un codice che ebbe grande fortuna e che è ricordato con il suo nome. Si tratta del più semplice codice di sostituzione polialfabetica, e proprio per la sua semplicità ha goduto per secoli di una fama piuttosto immeritata, essendo più debole di altri codici polialfabetici precedenti.

Dal cifrario di Vigenere deriva peraltro il cifrario di Vernam, considerato il cifrario

 teoricamente perfetto.

 

Il metodo si può considerare una generalizzazione del codice di Cesare; invece di spostare sempre dello stesso numero di posti la lettera da cifrare, questa viene spostata di un numero di posti variabile, determinato in base ad una parola chiave, da concordarsi tra mittente e destinatario, e da scriversi sotto il messaggio, carattere per carattere; la parola è detta verme, per il motivo che, essendo in genere molto più corta del messaggio, deve essere ripetuta molte volte sotto questo, come nel seguente esempio:

 

Testo chiaro  - ARRIVANOIRINFORZI
Verme           - VERMEVERMEVERMEVE
Testo cifrato - VVIUZVRFUVDRWAVUM

Il testo cifrato si ottiene spostando la lettera chiara di un numero fisso di caratteri, pari al numero ordinale della lettera corrispondente del verme. Di fatto si esegue una somma aritmetica tra l'ordinale del chiaro (A = 0, B = 1, C = 2, ...) e quello del verme; se si supera l'ultima lettera, la Z, si ricomincia dalla A, secondo la logica delle aritmetiche finite.

Il vantaggio rispetto ai codici mono-alfabetici è evidente: la stessa lettera del testo chiaro non è sempre cifrata con la stessa lettera; e questo rende più difficile l'analisi statistica del testo cifrato e la decrittazione.

Chi riceve il messaggio per decifrarlo deve semplicemente usare il metodo inverso (sottrarre invece che sommare); riferendosi all'esempio di sopra si avrà:

 

Testo cifrato - VVIUZVRFUVDRWAVUM
Verme           - VERMEVERMEVERMEVE
Testo chiaro  - ARRIVANOIRINFORZI

 

    Il principio di Kerchoff

"La conoscenza pubblica dell'algoritmo non deve risultare in un possibile indebolimento della sua robustezza crittografica"
In realtà nessun algoritmo è così robusto da garantire che mai nessuno potrà, senza conoscere la chiave, riconvertirlo, tuttavia occorrerebbe così tanto tempo che è praticamente impossibile. In altre parole, il numero di mappature nel quale il testo originale può essere trasformato è così vasto che è praticamente impossibile ricostruire il messaggio originale senza conoscerne la chiave. Un secondo requisito che deve avere un algoritmo di codifica e decodifica è quello di essere computazionalmente agevole.

Esistono 3 tipi diversi di algoritmi di cifratura:

L'ultimo è quello più sfruttato nella firma elettronica e pertanto i primi 2 saranno trattati più brevemente.

    L'algoritmo di ElGamal e il problema del logaritmo discreto

Il problema del logaritmo discreto usa entità matematiche chiamate gruppi. Un gruppo è una collezione di elementi, su cui sono definite delle operazioni che ubbidiscono a certe regole quali ad esempio la composizione e la moltiplicazione.

Se il gruppo ha un numero finito di elementi, ciascun elemento nel gruppo ha, quello che è chiamato un ordine, che è il minimo numero di volte che deve essere moltiplicato per sé stesso per ottenere l’identità, che di solito è 1.

 

Il problema del logaritmo discreto è quindi il seguente: dato un elemento g in un gruppo G di ordine t e un altro elemento y di G, il problema è trovare x, per 0 < x < (t - 1) tale che y è il risultato della composizione di g per sé stessa, x volte.

 

Così come il problema della fattorizzazione, il problema del logaritmo discreto è ritenuto difficile. Per questa ragione è diventato la base per diversi cifrari a chiave pubblica quali ad esempio il sistema di ElGamal.

 

I parametri per tale cifrario sono un numero primo p ed un intero g, le cui potenze modulo p generano un gran numero di elementi.

Rifacendosi ad un esempio possiamo dire che Mr. Y ha una una chiave privata a e una pubblica y dove y = ga mod p.

Supponiamo che Mr. X desideri mandare un messaggio a Mr. Y.

Mr. X prima genera un numero casuale k minore di p,

poi calcola y1=gkmod p e y2 = m XOR y · k, dove XOR indica l’OR esclusivo bit a bit.

Mr. X manda (y1, y2) a Mr. Y, che subito dopo aver ricevuto il testo cifrato calcola 

m = (y1 · a  mod p) XOR y2

 

L’algoritmo di firma elettronica di ElGamal è simile agli altri sistemi che sfruttano i metodi di cifratura a chiavi asimmetriche.

    DES: Data Encryption Standard

Lo standard di crittografia di dati (DES) ha approvato la procedura crittografica secondo le esigenze delle FIP 140-1.

Il DES definisce una procedura matematica per codificare e decodificare informazioni binarie. I dati di cifratura vengono convertiti in una forma inintelligibile chiamata cipher. La decriptazione della cipher converte i dati di nuovo alla relativa forma originale chiamata plaintext. Il dato può essere recuperato soltanto usando la stessa chiave usata per cifrarlo.

 

Il DES è un codice cifrato a blocchi che può essere usato nei i modelli ECB, CBC, CFB e OFB. La chiave usata per crittografare è un blocco di 64 bits suddivisa in 8 sottoblocchi di 8 bits ciascuno; l'ultimo bit di ogni sottoblocco è di controllo, di conseguenza i bit liberi sono 56. Il testo da cifrare viene suddiviso in blocchi di 64 bits ciascuno e vengono cifrati uno dopo l'altro in successione con uguale procedimento se viene usato il modello ECB altrimenti vengono incatenati fra loro secondo i metodi CBC, CFB e OFB.

 

Nel modo ECB si suddivide il messaggio in chiaro in blocchi di 64 bits, ed ogni blocco viene cifrato indipendentemente dagli altri utilizzando la stessa chiave. Ci sono diversi sistemi utilizzati per completare un messaggio se esso non raggiunge la lunghezza
desiderata di 64 bit ad esempio un metodo (detto "pad") aggiunge zeri fino alla lunghezza stabilita, mentre un altro, se i dati sono binari, integra il blocco con bits che sono l'opposto degli ultimi bit del messaggio. Nel caso di dati ASCII si usano invece byte random specificando nell'ultimo byte il carattere ASCII corrispondente al numero di byte aggiunti.
Infine un'ultima tecnica, in parte equivalente alla precedente, usa sempre bits random, ma fornisce, negli ultimi tre bits, il numero di byte non-padding cioè originali. In tal caso se il blocco è già di 64 bits si dovrà aggiungere un'altra stringa di 64 bits con 61 bits random e gli ultimi 3 nulli dato che indicano il numero di byte validi.

Durante la cifratura, un blocco di testo normale viene trasposto (o permutato), ovvero ogni bits cambia di posizione con un altro mediante un modulo di trasposizione. Poi il blocco di 64 bits viene diviso in una metà destra e una metà sinistra di 32 bits. In seguito vengono applicate 16 volte funzioni che operano sia trasposizioni che sostituzioni ad ogni metà mediante delle sottochiavi.

Durante ogni passaggio l'output della metà sinistra diventa l'input della destra e viceversa. Dopo il completamento di tutti i round i due sottoblocchi vengono riuniti e il risultato viene permutato per invertire la trasposizione iniziale.

 

Precisamente: indichiamo con T(i) il risultato della i-esima iterazione, con S(i) il semiblocco sinistro, con D(i) il semiblocco destro e con K(i) la sottochiave. In base all’algoritmo avremo che:

T(i) = S(i) · D(i)  (blocco di testo chiaro, plaintext)
S(i) = D(i-1) · D(i) = S(i-1) XOR f[ D(i-1), K(i) ]

 

Vediamo come opera la funzione f:
il blocco D(i-1) viene espanso da 32 bits a 48 con un modulo di espansione E. Indichiamo il blocco espanso con E[D(i-1)]; si calcola E[D(i-1)] XOR K(i);
il risultato precedente viene spezzato in 8 blocchi di 6 bits ciascuno: B(1),B(2), ..., B(8) contenenti rispettivamente i bits 1 ÷ 6,  7 ÷ 12, ecc...
Ciascun blocchetto B viene usato come ingresso ad una funzione Z che restituisce stringhe di 4 bits indicate Z[B(i)]

 

La funzione Z opera in questo modo: preleva da ogni matrice fissata S-box i 4 bits del nuovo blocchetto S(i)=Z[B(i)] posizionati in base alle righe e colonne specificate dai 6 bits del corrispondente B(i); una volta concatenati gli 8 blocchetti S(1), S(2), ..., S(8) verranno permutati ottendo finalmente P[S(1), ..., S(8)] = f [D(i-1), K(i)].

    DES: creazione di sottochiavi e decifratura

La chiave è una stringa di 64 bits con 8 bits di controllo che vengono ignorati durante la cifratura/decifratura. Essa viene spezzata in due blocchi di 28 bits, supponiamo di chiamarli L(0) e R(0), dopo di che per 16 volte i semiblocchi vengono shiftati a sinistra ottenendo L(1), R(1), L(2), R(2), ..., L(16), R(16) .
Quindi al primo round l'algoritmo utilizzerà la sottochiave K(1) = P[L(1) · R(1)] dove P al solito indica una permutazione, al secondo K(2) = P[L(2) · R(2)] e al 16° round K(16) = P[L(16) · L(16)] (si noti che tutte le operazioni effettuate producono sottochiavi K(i) di 48 bits).

Per la decifratura il procedimento è lo stesso salvo che al 1° passo verrà utilizzata K(16) = P[L(16) · L(16)], al secondo K(15)=P[L(15) · L(15)],  ecc.

In termini di equazione avremo:
T(i) = S(i)D(i) (blocco di testo cifrato, ciphertext)
D(i-1) = S(i) · S(i-1) = D(i) XOR f[S(i),K(i)]

 

Questo metodo di tipo simmetrico è poco sicuro perchè se il messaggio viene intercettato durante l'invio al destinatario la chiave permette immediatamente la decodifica.

    Il protocollo di Diffie-Hellman

Il protocollo per lo scambio di chiave Diffie-Hellman (anche chiamato scambio di chiave
esponenziale) è stato sviluppato da Diffie ed Hellman nel 1976 e pubblicato nella rivista “New Directions in Cryptography.” Il protocollo permette a due utenti di cambiare la chiave segreta su un canale insicuro senza dover usare nessun’altra chiave segreta.

 

Il protocollo ha due parametri di sistema p e g, sono entrambi pubblici e possono essere usati da tutti gli utenti del sistema.
Il parametro p è un numero primo e il parametro g (generalmente chiamato generatore) è un intero minore di p, con la seguente proprietà:
 

per tutti i numeri n compresi tra 1 e p-1 (inclusi), c’è una potenza k di g tale che gk = n mod p.

 

Supponiamo che Mr. Y e Mr. X si vogliano accordare su una chiave segreta condivisa usando il protocollo di Diffie-Hellman.

Procederanno come segue:
Per prima cosa Mr. Y genera un valore casuale a che solo lui conosce e Mr. X fa altrettanto generando b. Entrambi faranno parte dell’insieme di interi [1,…..,p-2].

Quindi ricaveranno i loro numeri pubblici usando i parametri p e g e i loro numeri privati. Il valore pubblico di Mr. Y è ga mod p, mentre quello di Mr. X sarà gb mod p.

A questo punto si scambiano i loro valori pubblici.

Finalmente Mr. Y si calcola gba = (ga)b mod p.
Giacchè g ba = g ab = k, Mr. Y e Mr. X adesso hanno una chiave segreta condivisa k.

 

Il protocollo dipende per la sua sicurezza dal problema del logaritmo discreto, si assume che sia computazionalmente irrealizzabile calcolare la chiave segreta k=g ba mod p dati i due valori pubblici ga mod p e gb mod p quando il primo p è sufficientemente grande. 

 

Maurer ha mostrato che la sprotezione del protocollo di Diffie-Hellman è equivalente al calcolo del logaritmo discreto sotto certe assunzioni.
Lo scambio di chiave di Diffie-Hellman è vulnerabile all’attacco dell’uomo in mezzo.

In questo tipo di attacco un avversario Mr. Z intercetta il numero pubblico di Mr. Y e manda il suo numero pubblico a Mr. X. Quando Mr. X trasmette il suo numero pubblico, Mr. Z lo sostituisce con il suo e lo manda a Mr. Y.

Mr. Z e Mr. Y si scambiano una chiave, mentre Mr. Z e Mr. X un’altra.

Dopo questi scambi, Mr. Z semplicemente decifra qualunque messaggio mandato tra Mr. Y e Mr. X, lo legge e volendo lo modifica prima di recifrarlo con la chiave appropriata per trasmetterlo all’altro.


Questa vulnerabilità è presente perchè lo scambio di chiave Diffie-Hellman non prevede l’autenticazione tra i partecipanti alla comunicazione. Una possibile soluzione consiste
nell’includere una forma di firma elettronica.

A grandi linee, l’idea di base è la seguente: prima dell’esecuzione del protocollo, le due parti Mr. Y e Mr. X ottengono ciascuno una coppia di chiavi pubbliche/private ed un certificato per la loro chiave pubblica.

Durante il protocollo, Mr. Y si calcola una firma su un certo messaggio che contiene il
valore pubblico ga mod p e
Mr. X procede in modo analogo.

Mr. Z può comunque intercettare i messaggi tra Mr. Y e Mr. X ma non può generare la firma senza la chiave private di Mr. Y e di Mr. X.

Il protocollo così rafforzato è in grado di sconfiggere l’attacco dell’uomo in mezzo.

    La matematica dell'RSA: numeri primi e Fermat-Eulero

I Numeri primi
Un numero si dice primo se divisibile soltanto per se stesso e per uno.

I numeri primi sono infiniti, ma non ne conosciamo nè una formula di generazione, nè una che ce ne dia infiniti.

Esistono però coppie di numeri ( p, p+2) dove i termini sono entrambi primi, detti primi gemelli, del tipo 3 e 5, 5 e 7, 11 e 13, 17 e 19 e così via.

L' insieme di appartenenza non sappiamo se sia finito o infinito.


Un sistema per determinare un numero primo consiste nell'utilizzare la formula di Fermat: Fh = 2 (2h)+1 per h minore di 4, gli altri sono risultati essere composti.
I grandi numeri primi noti sono tutti della forma di Mersenne: Mp = 2p - 1 (p primo necessariamente), ma non tutti i numeri di Mersenne sono primi.

Sappiamo che è facile venire a conoscenza in tempi brevi se n è primo o composto, ma i tempi per trovare i fattori crescono fortemente al crescere del numero di cifre che compongono il numero.
Questa caratteristica è preziosa per la crittografia ed è alla base del cifrario RSA.

 

Il Teorema di Fermat-Eulero
Questo teorema fu enunciato per la prima volta in forma semplificata da Pierre de 

Fermat nel 1679, mentre la prima dimostrazione è dovuta ad Eulero nel 1736, che ne diede anche una formulazione più generale (quella che segue). Di qui il doppio nome con cui è conosciuto il teorema, che è tornato di attualità negli ultimi anni quando è diventato uno degli ingredienti del cifrario RSA.

Il teorema afferma che dati due numeri interi qualsiasi m e n primi tra di loro, allora è:

 

mf(n) MOD n = 1; oppure (che è lo stesso): (mf(n) - 1) MOD n = 0

 

dove f(n) è la funzione di Eulero.

 

Il teorema si può anche enunciare nell'ambito delle aritmetiche finite affermando che in un'aritmetica di ordine n è mf(n) = 1 .
Un caso particolare si ha quando n è senz'altro primo; allora f(n) = n - 1 e quindi il teorema si riduce a: m (n - 1) MOD n = 1
È questa la formulazione originale di Fermat.

 

Ad esempio si prendano i numeri 2 e 9 che sono primi tra di loro.

La funzione di Eulero f(9) = 9(1-1/3) = 6 e 2 6 -1 = 63 che è appunto un multiplo di 9

 

La funzione di Eulero associa a un numero intero n il numero dei numeri interi primi con n e minori di n (compreso l'uno); è una funzione basilare della teoria dei numeri ed interviene in molti teoremi come quello di Fermat-Eulero, oltre ad essere uno degli ingredienti fondamentali del cifrario RSA.


Per esempio per n = 6 la funzione di Eulero vale 2 perché gli interi primi con 6 e minori di 6 sono solo 1 e 5; per n = 7 la funzione vale 6 perché essendo 7 primo tutti i numeri che lo precedono sono primi con 7.


La funzione di Eulero di un numero n si indica di solito con f(n).

Si dimostra che:

f(n) = n(1 - 1/n1)(1 - 1/n2)...(1 - 1/nm)

dove n1, n2 ... nm sono i fattori primi distinti di n.

Se n è primo allora ovviamente f(n) = n - 1

Se n è il prodotto di due numeri primi p e q, è facile verificare che 

f(n) = (p - 1) · (q - 1)

 

Infatti f(n) = p · q ·(1 - 1/p) · (1 - 1/q) e svolgendo i prodotti p(1 - 1/p) e q(1 - 1/q) si ottiene la formula data.

 

Ad esempio se prendiamo n = 18 = 32·2, i fattori primi sono 2 e 3 e la funzione di Eulero vale:
f(18) = 18(1 - 1/2)(1 - 1/3) = 18(1/2)(2/3) = 6
ed effettivamente sono 6 i numeri primi con 18: 1, 5, 7, 11, 13, 17.
Questo esempio ci permette anche di giustificare la formula, come una sorta di setaccio: all'inizio i numeri in gioco sono tutti e 18 (da 1 a 18); poi essendo 18 multiplo del due si escludono tutti i numeri pari, che sono la metà del totale e ne restano 9, come dalla prima parte della formula [18(1 - 1/2) = {1,3,5,7,9,11,13,15,17} ]

A questo punto essendo anche 3 un fattore primo di 18, si escludono tutti i multipli del tre che sono un terzo del totale; ne restano i due terzi, appunto (1 - 1/3), dei nove rimasti ovvero i sei già visti: 1,5,7,11,13,17.


È evidente che il procedimento resta valido per qualsiasi numero e per qualsiasi numero di fattori e questo giustifica la formula di sopra.

    RSA

A partire dagli anni ’70 si sono affermati cifrari a chiave pubblica, primo tra tutti il ben noto RSA: la chiave per cifrare non è la stessa di quella per decifrare; la prima può allora essere resa pubblica, mentre solo la seconda resta segreta. Per questo motivo sono detti anche cifrari asimmetrici.
RSA è un cifrario a chiave pubblica che permette di cifrare un messaggio attraverso un procedimento che sfrutta il problema della fattorizzazione di un numero grande, ovvero della ricerca di tutti i suoi fattori primi.

 

Per generare la chiave pubblica di cifratura ogni utente del sistema RSA sceglie a caso due numeri primi piuttosto grandi p e q. Il prodotto n e un altro numero casuale E vengono inseriti nell'elenco pubblico e costituiscono la chiave di cifratura dell'utente. Per applicare la chiave, il mittente deve convertire il messaggio in una successione di numeri, e quindi frazionarla in blocchi P1, P2, ... Ogni numero del testo in chiaro Pi deve essere compreso tra 0 e n-1. Trovata nell'elenco la chiave pubblica (E, n) dell'utente, il mittente calcola per ogni numero Pi il numero Ci = PiE mod n del testo cifrato.

 

Ad esempio:

con p = 5, q = 11, E = 3, la chiave risulta (3,55);

la cifra P = 2 che sarebbe C = 23 = 8 mod 55.

 

Per decifrare un testo cifrato C1, C2, ... l'utente usa n e una chiave di decifrazione D, ricavata dai fattori primi p e q di n. Per chiarire come venga ricavata D è necessario considerare il numero (p-1) · (q-1) chiamato funzione di Eulero f(n).

Le probabilità di f(n) garantiscono che esiste sempre un inverso moltiplicativo D di E, modulo f(n), ovvero (E · D) mod (p-1) · (q-1) = 1.

 

Riprendendo l'esempio:

con p = 5, q = 11, E = 3, (p-1) · (q-1) = 40;

D = 27 dato che 3 · 27 supera di uno 2 · 40

 

Per decifrare un testo il destinatario calcola CiD mod n per ogni numero del testo cifrato Ci, che è uguale a piE mod n. In altri termini, elevando il testo cifrato alla D-esima potenza e riducendolo modulo n si riottiene il testo in chiaro.

La difficoltà di calcolare D a partire dall'informazione pubblica (E, n) deriva dalla difficoltà di fattorizzare n, cioè di ricavare p e q.

 

In sintesi: per cifrare un messaggio il trasmettitore deve prendere le diverse cifre pubbliche del ricevente e costruire un messaggio cifrato, quest’ultimo a sua volta utilizza la parte segreta del suo codice per decifrarlo.

 

Il codice RSA viene considerato sicuro perchè, essendo la formula di decifrazione basata su f(n) calcolabile solo se si è a conoscenza di p e q, non esiste un algoritmo efficiente per scomporre n nei suoi fattori primi p e q, perlomeno in tempi accettabili.

Potrebbe sorgere il dubbio che esista un modo di calcolare f(n) senza passare per p e q: questa ipotesi in effetti è verificabile, ma ha lo stesso grado di complessità di fattorizzare n.

    CST

Allo scopo di studiare e capire meglio le problematiche che insorgono nel creare un sistema crittografico, ho creato un personale algoritmo che si basa su chiave privata, a tale algoritmo ho dato il nome di CST.

Il codice CST si basa sulla corrispondenza biunivoca tra carattere e codice.

 

Esso è così strutturato:

Per una maggiore comprensione occorre fare un esempio, si può dunque lanciare il programma oppure spiegarlo più semplicemente:

Immaginiamo di avere 10  caratteri disponibili anzichè 95: (a, e, i, o, u, b, c, d, f, g);

ponendo 2 cifre casuali per ogni carattere avremo una chiave di 20 cifre scelte casualmente: (05987413265486310977); inoltre se il punto di inizio della creazione della tabella carattere/cifre è uguale a 11, quest' ultima risulterà:

Carattere

Cifra

a

54

e

86

i

31

o

09

u

77

b

05

c

98

d

74

f

13

g

26

Volendo così scrivere la frase Oggi gioco a bocce essa cifrata risulterà: 092626312631099809540509989886.

 

Per poter riuscire a decodificare il messaggio verrà infine inserito il numero della chiave, in questo caso 01, ed il punto di inizio di lettura corrispondente nell'esempio ad 11. Il messaggio cifrato risulterà dunque: 0926263126310998095405099898860111.

 

Il destinatario riceverà a questo punto 2 pacchetti dati: il primo corrispondente alla chiave (05987413265486310977) ed il secondo corrispondente al messaggio (0926263126310998095405099898860111).

 

Recuperando i parametri indispensabili, e conoscendo a priori la sequenza dei caratteri disposti nella tabella, con procedimento inverso il destinatario riesce semplicemente a decodificare il messaggio inviatogli.

 

Risulta evidente come aumentando il numero di caratteri disponibili e il numero della chiavi su cui lavorare, la probabilità di decodifica di un messaggio risulti essere un lavoro piuttosto arduo anche se non impossibile.