Ultima modifica:
Introduzione
RSA è uno dei primi algoritmi di crittografia asimmetrica, prende il nome da Rivest, Shamir e Adleman, le tre persone che l'hanno definito. La crittografia asimmetrica si basa sul concetto che i messaggi criptati con una chiave dovranno essere decriptati con una chiave diversa, decriptare un messaggio usando la stessa chiave utilizzata nella fase di encryption non ci riporta al messaggio originale. In un crittosistema a chiave pubblica si hanno dunque due tipi di chiave: pubblica (conosciuta da tutti) e privata (segreta). Chi vuole inviare un messaggio dovrà utilizzare la chiave pubblica associata alla persona che vuole contattare, mentre il destinatario, che è l'unico in possesso della propria chiave privata, può decriptare il crittotesto utilizzando la chiave privata.Sebbene sia stato attribuito da Rivest, Shamir e Adleman, che l'hanno pubblicato nel 1977, è risaputo che un algoritmo molto simile fosse già in uso da alcune agenzie governative che, ovviamente, non l'hanno reso pubblico.
Tra i principali vantaggi di questo sistema è lampante il fatto che non è necessaria una chiave condivisa per poter comunicare, di conseguenza non si pone il problema di come scambiarsi questa chiave: le chiavi pubbliche possono essere visibili a chiunque senza influire sulla sicurezza dell'algoritmo. Tra i principali svantaggi vi è il fatto che sono molto lenti, approssimativamente tra un crittosistema simmetrico e uno asimmetrico c'è un fattore di $$\(10^3$$\), per fare un esempio: il tempo che impiegate a cifrare qualche megabyte utilizzando RSA è paragonabile al tempo in cui impieghereste a cifrare qualche gibabyte utilizzando AES (l'attuale standard per la crittografia simmetrica). Ne consegue che la crittografia asimmetrica è principalmente utilizzata per cifrare informazioni molto piccole, come ad esempio la chiave condivisa che andremo ad utilizzare in un algoritmo di crittografia simmetrica.
Problema della fattorizzazione
RSA basa la sua sicurezza sul problema matematico della fattorizzazione: dal teorema fondamentale dell'algebra sappiamo che ogni intero $$\(n$$\) può essere scritto in modo essenzialmente unico come prodotto di numeri primi. Il problema della fattorizzazione lo possiamo esporre nel modo seguente: data una coppia di numeri primi $$\(p, q \in \text{Prime}$$\), grandi a piacere, è facile moltiplicarli per calcolare $$\(n=pq$$\) ma, dato un intero composto $$\(n=pq$$\), trovare uno dei fattori $$\(p,q \in \text{Prime}$$\) che formano $$\(n$$\) è difficile. Se vogliamo dirla in modo un po' più formale, con "facile" definiamo i problemi risolubile in tempo al più polinomiale e con "difficile" definiamo i problemi risolubili in almeno un tempo esponenziale, dev'essere un problema intrattabile anche nel caso medio e dev'essere difficilmente approssimabile, ma "facile" e "difficile" rende bene l'idea. Dall'ultima frase è chiaro che il problema della fattorizzazione è in $$\(\mathcal{F}_{\text{NP}}$$\), che dal nostro punto di vista comporta: è facile costruire un istanza del problema della fattorizzazione di cui conosciamo la risposta, ma è difficile per gli altri trovare quale sia questa risposta.
L'algoritmo
Per descrivere l'algoritmo, supponiamo che Bob voglia trasmettere un messaggio $$\(m$$\), rappresentato come numero, ad Alice.
Generazione della coppia di chiavi:
Encryption e Decryption:
Dimostrazione
Com'è possibile che $$\(m \equiv c^d \bmod n$$\)? Facciamo prima un paio di premesse.
Funzione $$\(\phi$$\) di Eulero
La funzione $$\(\phi(n)$$\) conta i numeri $$\(1 \le k \le n$$\) tali che $$\(\gcd(k, n) = 1$$\). Per ogni intero $$\(n > 0$$\) vale
$$\[\phi(n) = n \prod_\limits{p|n} \left(1 - \frac{1}{p}\right)$$\]quindi, se abbiamo $$\(n = pq$$\) con $$\(p,q \in \text{Prime}$$\) possiamo dire $$\(\phi(n) = (p-1)(q-1)$$\). Questo concetto lo utilizziamo al punto 3 della generazione della coppia di chiavi.
Teorema di Eulero
Se $$\(\gcd(a, n) = 1$$\) allora $$\(a^{\phi(n)} \equiv 1 \bmod n$$\).
Piccolo teorema di Fermat
Per ogni intero $$\(a$$\) e ogni $$\(p \in \text{Prime}$$\) abbiamo $$\(a^{p-1} \equiv 1 \bmod p$$\).
Adesso abbiamo abbastanza informazioni per dimostrare che $$\(m \equiv c^d \bmod n$$\). Prima di tutto ci ricordiamo che $$\(c \equiv m^e \bmod n$$\) per via del punto 3 nella fase di encryption e decryption, quindi possiamo riscrivere la stessa equazione come $$\(m \equiv \left(m^e\right)^d \bmod n$$\). Poi ci ricordiamo che la potenza di una potenza è uguale al prodotto degli esponenti, quindi abbiamo $$\(m \equiv m^{de} \bmod n$$\).
Nel punto 3 della fase di generazione delle chiavi avevamo detto $$\(de \equiv 1 \bmod{(p-1)(q-1)}$$\) e, sapendo come funziona l'aritmetica modulare, possiamo dire $$\(de = 1 + k(p-1)(q-1)$$\) per qualche $$\(k \in \mathbb{N}$$\). Sostituiamo a $$\(de$$\) quanto abbiamo trovato e, ricordandoci che $$\((p-1)(q-1) = \phi(n)$$\), otteniamo $$\(m \equiv m^{1+k\phi(n)} \bmod n$$\).
A questo punto ci ricordiamo un'altra proprietà delle potenze: nel prodotto di potenze con la stessa base si sommano gli esponenti. Così riscriviamo ciò che avevamo ottenuto come $$\(m \equiv m \cdot m^{k \phi(n)} \bmod n$$\).
In fine, applichiamo il teorema di Eulero e otteniamo $$\(m \equiv m \cdot 1^k \bmod n$$\) che è esattamente dove volevamo arrivare: partendo da $$\(m \equiv c^e \bmod n$$\) siamo arrivati a $$\(m \equiv m \bmod n$$\).
$$\[m \equiv c^e \equiv m^{de} \equiv m^{1+k(q-1)(p-1)} \equiv m \cdot m^{k\phi(n)} \equiv m \cdot 1^k \equiv m \bmod n$$\]
Come troviamo i numeri primi?
Al punto 1 nella fase di generazione delle chiavi abbiamo parlato di scegliere due numeri $$\(p, q \in Prime$$\) grandi a piacere. Ovviamente più sono grandi e più è difficile fattorizzare, ma è facile trovare dei numeri primi?
Teorema dei numeri primi
Sia $$\(\pi(n)$$\) la quantità di numeri primi inferiori a $$\(n$$\), il teorema dei numeri primi ci dice che $$\(\pi(n) \sim \frac{n}{\ln n}$$\).
Quel simbolo lì si chiamo asintotico, ha un significato ben preciso, ma in questo momento ce ne sbattiamo le palle e approssimiamo il significato di quel simbolo con "circa uguale". Supponiamo che vogliamo cercare due numeri primi rappresentati da 300 cifre e, per farlo, li scegliamo a caso e verifichiamo se sono primi. Abbiamo una buona probabilità di successo? I numeri primi di 300 cifre sono tanti o sono pochi? Utilizzando questo teorema possiamo dire:
$$\[\pi(10^{301}) - \pi(10^{299}) \approx \frac{10^{301}}{\ln(10^{301})} - \frac{10^{300}}{\ln(10^{300})} \approx \frac{10^{301}}{301 \ln(10)} - \frac{10^{300}}{300 \ln(10)} \approx 1.29 \cdot 10^{298}$$\]Ovvero se prendiamo la quantità di primi formati da numeri più piccoli di 301 cifre decimali e gli sottraiamo la quantità di numeri primi formati da numeri più piccoli di 300 cifre decimali, otteniamo un numero astronomico. Conclusione: abbiamo tantissimi numeri primi grandi.
A differenza del problema della fattorizzazione, il problema di decidere se un numero è primo o composto appartiene a $$\(\text{P}$$\) (algoritmo AKS), quindi è facile. Per questioni di praticità, l'estrazione dei numeri primi random non la facciamo utilizzando AKS (che è più rilevante dal punto di vista teorico che pratico), ma utilizzando Miller-Rabin: un algoritmo probabilistico che si basa sul piccolo teorema di Fermat, con un ulteriore accorgimento che permette di beccare anche i composti che ingannano questo test a prescindere dalla base $$\(a$$\) (numeri di Carmichael). Grazie al teorema dei numeri primi, generando numeri random grandi non impieghiamo molto tempo per trovarne uno che sia anche primo. Inoltre, è molto improbabile che due persone utilizzino la stessa coppia di numeri primi.
Come calcolo l'esponente di decryption?
Al punto 3 della fase di generazione delle chiavi abbiamo parlato di calcolare il $$\(d$$\) tale che
$$\[de \equiv 1 \bmod{(p-1)(q-1)}$$\]ovvero, l'inversa moltiplicativa di $$\(e \bmod \phi(n)$$\). L'esistenza di questa inversa è data da $$\(\gcd(e, (p-1)(q-1))$$\), che è una condizione che avevamo imposto nel passo precedente. Per calcolarla possiamo utilizzare l'algoritmo di Euclide esteso. Questo argomento è già stato trattato su questo forum, quindi mi limito a riproporvi questi due post: 1 e 2.
Attacchi ad RSA
Possiamo procedere in due modi: cercare di fattorizzare $$\(n$$\), che ci porterebbe ad avere le stesse informazioni che ha Alice, oppure assumere di non essere in grado di fattorizzare e procedere per vie traverse. Calcolare $$\(\phi(n)$$\) è tanto difficile quanto fattorizzare (spiegazione).
Di seguito vi propongo alcuni degli attacchi a questo crittosistema:
Dalla teoria alla pratica
Adesso, utilizzando openssl, cerchiamo un riscontro di quanto abbiamo detto fino ad ora.
Nel mio caso la chiave pubblica è:
Il modulo è quello che precedentemente avevamo chiamato $$\(n$$\), espresso in formato esadecimale per aumentare la leggibilità, mentre l'esponente è la nostra $$\(e$$\). Poco sorprendentemente $$\(e = 65537 = 2^{16}+1$$\), avevamo detto che questo era un valore tipico.
Sempre nel mio caso, la chiave privata è:
Avevamo detto che la chiave privata era data dalla tripla $$\((p,q,d)$$\), ma qui abbiamo molte più informazioni:
Per completezza, ecco come cifrare e decifrare utilizzando le nostre due chiavi:
Firma digitale con RSA
Una firma digitale di un messaggio $$\(m$$\) è una stringa di bit che associa un messaggio con l'entità che l'ha originato. Tale firma dev'essere verificabile, ovvero chiunque dev'essere in grado di verificare l'autenticità di una firma senza l'intervento del firmatario. Lo scopo di una firma digitale è garantire:
Esistono due tipologie di firma: con appendice e con recupero di messaggio. Le firme con appendice sono in allegato al messaggio stesso, quelle con recupero di messaggio invece ti permettono di ottenere il messaggio nel momento in cui effettui la verifica.
Per firmare si fa uso degli algoritmi crittografici a chiave pubblica, l'idea è quella di cifrare con la propria chiave privata e di decifrare con la chiave pubblica (l'opposto di quello che si fa normalmente). Vediamo come utilizzare RSA per effettuare una firma con recupero di messaggio:
La dimostrazione è analoga a quella precedente. Firmare un messaggio in questo modo è poco conveniente, abbiamo detto che la crittografia asimmetrica è generalmente più lenta di un fattore di $$\(10^3$$\) rispetto alla crittografia simmetrica, firmare un messaggio molto grande (eg. un filmato) richiederebbe troppe risorse sia per la fase di firma che per quella di verifica. Per ovviare a questo inconveniente si fa uso delle funzioni di hash: un hash è una stringa di pochi bit che rappresenta un messaggio, lo possiamo generare molto velocemente e non richiede alcuna chiave. Ha delle proprietà tali per cui è difficile falsificare un hash. Procediamo nel modo seguente
Con RSA è anche possibile effettuare una blinded signature, ovvero possiamo firmare qualcosa che non ci appartiene e di cui non conosciamo il contenuto. Visto che la firma digitale voleva solo essere un argomento marginale di questa discussione, per il momento non mi dilungo in ulteriori spiegazioni. Se qualcuno fosse interessato al suo funzionamento, me lo faccia sapere e modificherò questo post spiegandone il funzionamento.
PGP / GPG
Se vogliamo comunicare, normalmente non faremo uso di Openssl, ma PGP (Pretty Good Privacy). PGP è uno dei più famosi programmi per cifrare, decifrare, firmare ed effettuare altre operazioni legate al mondo della privacy, GPG (Gnu Privacy Guard) è l'implementazione free (as in freedom) di PGP. Vediamo come utilizzare GPG, da linea di comando, per generare la nostra coppia di chiavi.
E adesso vediamo come firmare un messaggio utilizzando le nostre chiavi. È un procedimento che possiamo fare anche con openssl, lo facciamo con gpg semplicemente per vedere il funzionamento di questo software che è più adatto agli usi pratici.
Il file plaintext.txt.asc conterrà:
E quando controlleremo a chi appartiene questa firma, nel punto 3, otterremo:
Il warning che otteniamo serve solamente ad avvisarci che è una firma con appendice: non siamo sicuri che il contenuto di plaintext.txt sia esatto, ma abbiamo verificato a chi appartiene il messaggio "Ciao inforge" che appare nel file plaintext.txt.asc. Provando a falsificare il messaggio contenuto in plaintext.txt.asc, per esempio scrivendo "Ciamo inforge!" otterremmo:
Attacchi ad RSA: l'implementazione
Ecco alcuni attacchi implementati in C, ho utilizzato la libreria GMP per svolgere le operazioni matematiche sui big numbers. Se volete compilarli dovrete linkare questa libreria. Su GCC è sufficiente aggiungere come parametro -lgmp.
Trial division:
Fermat:
Downloads:
Se trovate qualche errore o se volete delle informazioni aggiuntive, avvisatemi pure!
RSA è uno dei primi algoritmi di crittografia asimmetrica, prende il nome da Rivest, Shamir e Adleman, le tre persone che l'hanno definito. La crittografia asimmetrica si basa sul concetto che i messaggi criptati con una chiave dovranno essere decriptati con una chiave diversa, decriptare un messaggio usando la stessa chiave utilizzata nella fase di encryption non ci riporta al messaggio originale. In un crittosistema a chiave pubblica si hanno dunque due tipi di chiave: pubblica (conosciuta da tutti) e privata (segreta). Chi vuole inviare un messaggio dovrà utilizzare la chiave pubblica associata alla persona che vuole contattare, mentre il destinatario, che è l'unico in possesso della propria chiave privata, può decriptare il crittotesto utilizzando la chiave privata.Sebbene sia stato attribuito da Rivest, Shamir e Adleman, che l'hanno pubblicato nel 1977, è risaputo che un algoritmo molto simile fosse già in uso da alcune agenzie governative che, ovviamente, non l'hanno reso pubblico.
Tra i principali vantaggi di questo sistema è lampante il fatto che non è necessaria una chiave condivisa per poter comunicare, di conseguenza non si pone il problema di come scambiarsi questa chiave: le chiavi pubbliche possono essere visibili a chiunque senza influire sulla sicurezza dell'algoritmo. Tra i principali svantaggi vi è il fatto che sono molto lenti, approssimativamente tra un crittosistema simmetrico e uno asimmetrico c'è un fattore di $$\(10^3$$\), per fare un esempio: il tempo che impiegate a cifrare qualche megabyte utilizzando RSA è paragonabile al tempo in cui impieghereste a cifrare qualche gibabyte utilizzando AES (l'attuale standard per la crittografia simmetrica). Ne consegue che la crittografia asimmetrica è principalmente utilizzata per cifrare informazioni molto piccole, come ad esempio la chiave condivisa che andremo ad utilizzare in un algoritmo di crittografia simmetrica.
Problema della fattorizzazione
RSA basa la sua sicurezza sul problema matematico della fattorizzazione: dal teorema fondamentale dell'algebra sappiamo che ogni intero $$\(n$$\) può essere scritto in modo essenzialmente unico come prodotto di numeri primi. Il problema della fattorizzazione lo possiamo esporre nel modo seguente: data una coppia di numeri primi $$\(p, q \in \text{Prime}$$\), grandi a piacere, è facile moltiplicarli per calcolare $$\(n=pq$$\) ma, dato un intero composto $$\(n=pq$$\), trovare uno dei fattori $$\(p,q \in \text{Prime}$$\) che formano $$\(n$$\) è difficile. Se vogliamo dirla in modo un po' più formale, con "facile" definiamo i problemi risolubile in tempo al più polinomiale e con "difficile" definiamo i problemi risolubili in almeno un tempo esponenziale, dev'essere un problema intrattabile anche nel caso medio e dev'essere difficilmente approssimabile, ma "facile" e "difficile" rende bene l'idea. Dall'ultima frase è chiaro che il problema della fattorizzazione è in $$\(\mathcal{F}_{\text{NP}}$$\), che dal nostro punto di vista comporta: è facile costruire un istanza del problema della fattorizzazione di cui conosciamo la risposta, ma è difficile per gli altri trovare quale sia questa risposta.
L'algoritmo
Per descrivere l'algoritmo, supponiamo che Bob voglia trasmettere un messaggio $$\(m$$\), rappresentato come numero, ad Alice.
Generazione della coppia di chiavi:
- Alice sceglie due numeri $$\(p, q \in \text{Prime}$$\) e calcola $$\(n = pq$$\);
- Alice sceglie un esponente di encryption $$\(e$$\) tale che $$\(\gcd((q-1)(p-1), e)=1$$\), un valore tipico per questo esponente è $$\(2^{16}+1$$\) perché non è troppo piccolo e permette ad un computer di velocizzare i conti;
- Alice calcola l'esponente di decryption, ovvero un valore $$\(d$$\) tale che $$\(de \equiv 1 \bmod{(p-1)(q-1)}$$\);
- Alice ha finalmente la sua coppia di chiavi, quella pubblica la posta online, quella privata la tiene al sicuro: $$\(\text{A}_\text{pub} = (n, e)$$\) e $$\(\text{A}_\text{prv} = (p, q, d)$$\).
Encryption e Decryption:
- Bob va su internet a scaricare la chiave pubblica di Alice $$\(\text{A}_\text{pub} = (n, e)$$\);
- Bob vuole cifrare un messaggio $$\(m$$\) che, senza perdita di generalizzazione, assumiamo essere un numero $$\(0 \le m < n$$\);
- per cifrare il messaggio $$\(m$$\), Bob calcola $$\(c \equiv m^n \bmod n$$\) e invia ad Alice $$\(c$$\);
- per decifrare il messaggio $$\(c$$\), Alice calcola $$\(m \equiv c^d \bmod n$$\).
Dimostrazione
Com'è possibile che $$\(m \equiv c^d \bmod n$$\)? Facciamo prima un paio di premesse.
Funzione $$\(\phi$$\) di Eulero
La funzione $$\(\phi(n)$$\) conta i numeri $$\(1 \le k \le n$$\) tali che $$\(\gcd(k, n) = 1$$\). Per ogni intero $$\(n > 0$$\) vale
$$\[\phi(n) = n \prod_\limits{p|n} \left(1 - \frac{1}{p}\right)$$\]quindi, se abbiamo $$\(n = pq$$\) con $$\(p,q \in \text{Prime}$$\) possiamo dire $$\(\phi(n) = (p-1)(q-1)$$\). Questo concetto lo utilizziamo al punto 3 della generazione della coppia di chiavi.
Teorema di Eulero
Se $$\(\gcd(a, n) = 1$$\) allora $$\(a^{\phi(n)} \equiv 1 \bmod n$$\).
Piccolo teorema di Fermat
Per ogni intero $$\(a$$\) e ogni $$\(p \in \text{Prime}$$\) abbiamo $$\(a^{p-1} \equiv 1 \bmod p$$\).
Adesso abbiamo abbastanza informazioni per dimostrare che $$\(m \equiv c^d \bmod n$$\). Prima di tutto ci ricordiamo che $$\(c \equiv m^e \bmod n$$\) per via del punto 3 nella fase di encryption e decryption, quindi possiamo riscrivere la stessa equazione come $$\(m \equiv \left(m^e\right)^d \bmod n$$\). Poi ci ricordiamo che la potenza di una potenza è uguale al prodotto degli esponenti, quindi abbiamo $$\(m \equiv m^{de} \bmod n$$\).
Nel punto 3 della fase di generazione delle chiavi avevamo detto $$\(de \equiv 1 \bmod{(p-1)(q-1)}$$\) e, sapendo come funziona l'aritmetica modulare, possiamo dire $$\(de = 1 + k(p-1)(q-1)$$\) per qualche $$\(k \in \mathbb{N}$$\). Sostituiamo a $$\(de$$\) quanto abbiamo trovato e, ricordandoci che $$\((p-1)(q-1) = \phi(n)$$\), otteniamo $$\(m \equiv m^{1+k\phi(n)} \bmod n$$\).
A questo punto ci ricordiamo un'altra proprietà delle potenze: nel prodotto di potenze con la stessa base si sommano gli esponenti. Così riscriviamo ciò che avevamo ottenuto come $$\(m \equiv m \cdot m^{k \phi(n)} \bmod n$$\).
In fine, applichiamo il teorema di Eulero e otteniamo $$\(m \equiv m \cdot 1^k \bmod n$$\) che è esattamente dove volevamo arrivare: partendo da $$\(m \equiv c^e \bmod n$$\) siamo arrivati a $$\(m \equiv m \bmod n$$\).
$$\[m \equiv c^e \equiv m^{de} \equiv m^{1+k(q-1)(p-1)} \equiv m \cdot m^{k\phi(n)} \equiv m \cdot 1^k \equiv m \bmod n$$\]
Come troviamo i numeri primi?
Al punto 1 nella fase di generazione delle chiavi abbiamo parlato di scegliere due numeri $$\(p, q \in Prime$$\) grandi a piacere. Ovviamente più sono grandi e più è difficile fattorizzare, ma è facile trovare dei numeri primi?
Teorema dei numeri primi
Sia $$\(\pi(n)$$\) la quantità di numeri primi inferiori a $$\(n$$\), il teorema dei numeri primi ci dice che $$\(\pi(n) \sim \frac{n}{\ln n}$$\).
Quel simbolo lì si chiamo asintotico, ha un significato ben preciso, ma in questo momento ce ne sbattiamo le palle e approssimiamo il significato di quel simbolo con "circa uguale". Supponiamo che vogliamo cercare due numeri primi rappresentati da 300 cifre e, per farlo, li scegliamo a caso e verifichiamo se sono primi. Abbiamo una buona probabilità di successo? I numeri primi di 300 cifre sono tanti o sono pochi? Utilizzando questo teorema possiamo dire:
$$\[\pi(10^{301}) - \pi(10^{299}) \approx \frac{10^{301}}{\ln(10^{301})} - \frac{10^{300}}{\ln(10^{300})} \approx \frac{10^{301}}{301 \ln(10)} - \frac{10^{300}}{300 \ln(10)} \approx 1.29 \cdot 10^{298}$$\]Ovvero se prendiamo la quantità di primi formati da numeri più piccoli di 301 cifre decimali e gli sottraiamo la quantità di numeri primi formati da numeri più piccoli di 300 cifre decimali, otteniamo un numero astronomico. Conclusione: abbiamo tantissimi numeri primi grandi.
A differenza del problema della fattorizzazione, il problema di decidere se un numero è primo o composto appartiene a $$\(\text{P}$$\) (algoritmo AKS), quindi è facile. Per questioni di praticità, l'estrazione dei numeri primi random non la facciamo utilizzando AKS (che è più rilevante dal punto di vista teorico che pratico), ma utilizzando Miller-Rabin: un algoritmo probabilistico che si basa sul piccolo teorema di Fermat, con un ulteriore accorgimento che permette di beccare anche i composti che ingannano questo test a prescindere dalla base $$\(a$$\) (numeri di Carmichael). Grazie al teorema dei numeri primi, generando numeri random grandi non impieghiamo molto tempo per trovarne uno che sia anche primo. Inoltre, è molto improbabile che due persone utilizzino la stessa coppia di numeri primi.
Come calcolo l'esponente di decryption?
Al punto 3 della fase di generazione delle chiavi abbiamo parlato di calcolare il $$\(d$$\) tale che
$$\[de \equiv 1 \bmod{(p-1)(q-1)}$$\]ovvero, l'inversa moltiplicativa di $$\(e \bmod \phi(n)$$\). L'esistenza di questa inversa è data da $$\(\gcd(e, (p-1)(q-1))$$\), che è una condizione che avevamo imposto nel passo precedente. Per calcolarla possiamo utilizzare l'algoritmo di Euclide esteso. Questo argomento è già stato trattato su questo forum, quindi mi limito a riproporvi questi due post: 1 e 2.
Attacchi ad RSA
Possiamo procedere in due modi: cercare di fattorizzare $$\(n$$\), che ci porterebbe ad avere le stesse informazioni che ha Alice, oppure assumere di non essere in grado di fattorizzare e procedere per vie traverse. Calcolare $$\(\phi(n)$$\) è tanto difficile quanto fattorizzare (spiegazione).
Di seguito vi propongo alcuni degli attacchi a questo crittosistema:
- Trial division: Se $$\(p$$\) e $$\(q$$\) sono vicini, quindi sono in un intorno (relativamente) piccolo di $$\(\sqrt{n}$$\), possiamo partire dall'intero dispari più vicino a $$\(\sqrt{n}$$\) e provare tutti i numeri da li in avanti fino a trovare un fattore di $$\(n$$\), ovvero un numero $$\(p$$\) tale per cui il resto della divisione $$\(\frac{n}{p}$$\) sia 0. Per evitare quest'attacco, $$\(p$$\) e $$\(q$$\) li scegliamo distanti tra loro (eg. uno con un bit in meno dell'altro).
- Timing attack: Nella fase di decryption, oltre a ricordarci l'esponente $$\(d$$\), precomputiamo alcuni valori che ci permettono di sfruttare il Teorema cinese del resto per velocizzare i calcoli. Avendo accesso alla macchina che decripta e potendo decriptare diversi crittotesti da noi scelti (attacco chosen-ciphertext), cronometrando il tempo di decryption di ciascun messaggio, è possibile effettuare delle statistiche che ci permettono di ottenere delle informazioni su $$\(p$$\) e $$\(q$$\). Per evitare questo tipo di attacco, si aggiunge un calcolo random che sballa i tempi misurati.
- Short plaintext: Se il messaggio da cifrare è troppo piccolo, è possibile scoprire cosa Bob sta dicendo ad Alice senza fattorizzare $$\(n$$\). Per evitare questo tipo di attacco, i messaggi cifrati contengono un padding, generalmente calcolato utilizzando lo schema OAEP.
- Low exponent attack: Esiste un attacco teorico effettuabile se si usa un esponente di encryption $$\(e$$\) troppo piccolo (eg. 3), si consiglia di utilizzare $$\(2^{16}+1$$\) come esponente di encryption perché è un numero primo (quindi garantisce $$\(\gcd(e, \phi(n)) = 1$$\) indipendentemente dal valore di $$\(n$$\)) abbastanza grande e veloce da utilizzare (va incontro all'aritmetica binaria utilizzata dai computer). Si è sotto attacco anche in caso in cui l'esponente di decryption $$\(d$$\) è troppo piccolo, in questo caso bisogna cambiare $$\(e$$\).
- Common modulus attack: Cifrare lo stesso messaggio $$\(m$$\) con tanti esponenti di encryption diversi, permette di costruire un sistema di equazioni che, con un po' di fortuna, ci permette di risalire ad $$\(m$$\).
- Algoritmo rho di Pollard: Una descrizione del funzionamento la potete trovare in questo post.
- Algoritmo p-1: Se $$\(p-1$$\), dove $$\(p$$\) è uno dei nostri primi, è un numero smooth (un composto formato da fattori piccoli) allora possiamo fattorizzare $$\(n$$\) utilizzando questo algoritmo. Per evitare questo algoritmo dobbiamo provare a fattorizzare $$\(p-1$$\) e verificare che non sia smooth. Una descrizione dell'algoritmo la potete trovare in questo post.
- Algoritmo di Lanstra: Fa uso delle curve ellittiche $$\(\bmod n$$\), ovvero su un campo, ed è simile all'algoritmo p-1. Prendendo una curva ellittica random e un punto $$\(\text{P}$$\) su questa curva, se nel calcolo di $$\(kP$$\) (dove $$\(k$$\) è un numero smooth) raggiungiamo il punto all'infinito, abbiamo fattorizzato $$\(n$$\). Se $$\(n$$\) è molto grande, la probabilità di riuscire fattorizzare con questo algoritmo è bassa.
- Setaccio quadratico: Si basa sulla fattorizzazione di Fermat ovvero se troviamo due interi $$\(x, y$$\) tali che $$\(x^2 \equiv y^2 \bmod n$$\) allora $$\(\gcd(x-y, n)$$\) è un fattore non banale di $$\(n$$\). È uno degli algoritmi più veloci per fattorizzare numeri inferiori a $$\(10^{100}$$\).
- Crivello dei campi di numeri generale: Attualmente è l'algoritmo più efficiente per fattorizzare interi molto grandi senza proprietà particolari (eg. p-1 funziona molto bene, ma l'intero da fattorizzare deve avere delle caratteristiche ben precise). La complessità in tempo è data da $$\(O\left(e^{(c+o(1))(\log n)^{1/3}(\log \log n)^{2/3}}\right)$$\).
- Algoritmo di Shor: Fattorizzare è facile... ma dobbiamo costruire un quantum computer. Ovviamente non è va considerato tanto come un attacco al crittosistema, quanto ad un traguardo teorico non indifferente. Di fatto non siamo nemmeno lontanamente vicini a costruire un quantum computer (non siamo nemmeno sicuri che possa essere costruito) e siamo ancora meno vicini a costruire un quantum computer capace di far girare questo algoritmo su dei numeri con una così considerevole dimensione.
Dalla teoria alla pratica
Adesso, utilizzando openssl, cerchiamo un riscontro di quanto abbiamo detto fino ad ora.
- Con openssl genrsa -out private_key.pem 2048 generiamo un file chiamato private_key.pem contenente una chiave di RSA da 2048 bit, ovviamente possiamo scegliere una dimensione a nostro piacimento.
- Con openssl rsa -pubout -in private_key.pem -out public_key.pem generiamo un file public_key.pem a partire dalla chiave privata precedentemente generata.
- Con openssl rsa -pubin -in public_key.pem -text -noout mostriamo a schermo la chiave pubblica, ovvero la coppia $$\((n, e)$$\)
Nel mio caso la chiave pubblica è:
Codice:
Public-Key: (2048 bit)
Modulus:
00:c1:c1:74:85:6b:62:6f:fc:62:fe:91:6e:0c:71:
6b:a3:53:df:9c:22:c4:16:bd:df:86:92:ef:81:1f:
0a:b9:57:29:4e:e3:05:97:5f:28:47:13:91:96:84:
23:f9:7a:ae:37:89:7b:02:40:0c:c7:5c:84:b4:c1:
e2:9b:17:e0:68:68:78:3d:60:ef:3a:73:4d:1b:29:
af:84:83:5f:0c:78:0f:cb:43:bc:13:06:24:59:7f:
37:48:bf:ed:df:45:40:69:cb:99:ec:f7:49:f9:ee:
59:d4:3e:9d:89:7c:ea:db:b0:2d:c0:08:69:e2:f4:
70:bd:2b:17:73:28:c5:91:4b:7b:56:36:c7:c4:e7:
11:9f:43:8e:11:2a:78:16:2b:79:27:b4:80:5b:a3:
23:5d:c2:29:27:34:10:27:40:5a:66:32:28:0e:96:
90:14:85:2a:0e:fd:1c:6b:9e:54:81:5a:a1:a2:06:
a3:2b:9b:c6:e5:bc:c3:83:f9:92:f7:02:2b:d8:ef:
8a:76:08:17:9e:0d:2f:87:a4:b6:e9:90:a2:33:ba:
e6:18:9b:08:c6:63:b8:d9:3c:af:06:06:44:75:db:
c1:87:29:d3:9f:cf:e2:dd:e0:2f:7a:de:e7:d8:ad:
bb:84:e2:46:0a:5a:e0:2d:28:98:d2:07:4b:e4:dd:
69:c1
Exponent: 65537 (0x10001)Sempre nel mio caso, la chiave privata è:
Codice:
Private-Key: (2048 bit)
modulus:
00:c1:c1:74:85:6b:62:6f:fc:62:fe:91:6e:0c:71:
6b:a3:53:df:9c:22:c4:16:bd:df:86:92:ef:81:1f:
0a:b9:57:29:4e:e3:05:97:5f:28:47:13:91:96:84:
23:f9:7a:ae:37:89:7b:02:40:0c:c7:5c:84:b4:c1:
e2:9b:17:e0:68:68:78:3d:60:ef:3a:73:4d:1b:29:
af:84:83:5f:0c:78:0f:cb:43:bc:13:06:24:59:7f:
37:48:bf:ed:df:45:40:69:cb:99:ec:f7:49:f9:ee:
59:d4:3e:9d:89:7c:ea:db:b0:2d:c0:08:69:e2:f4:
70:bd:2b:17:73:28:c5:91:4b:7b:56:36:c7:c4:e7:
11:9f:43:8e:11:2a:78:16:2b:79:27:b4:80:5b:a3:
23:5d:c2:29:27:34:10:27:40:5a:66:32:28:0e:96:
90:14:85:2a:0e:fd:1c:6b:9e:54:81:5a:a1:a2:06:
a3:2b:9b:c6:e5:bc:c3:83:f9:92:f7:02:2b:d8:ef:
8a:76:08:17:9e:0d:2f:87:a4:b6:e9:90:a2:33:ba:
e6:18:9b:08:c6:63:b8:d9:3c:af:06:06:44:75:db:
c1:87:29:d3:9f:cf:e2:dd:e0:2f:7a:de:e7:d8:ad:
bb:84:e2:46:0a:5a:e0:2d:28:98:d2:07:4b:e4:dd:
69:c1
publicExponent: 65537 (0x10001)
privateExponent:
00:8b:45:87:80:2f:c4:3e:42:e8:d5:9b:ab:c2:fd:
f4:25:1e:b0:e9:06:84:74:e4:5e:bb:d8:fa:97:91:
bc:9f:a4:eb:68:6c:ff:23:e3:9e:8c:18:a0:d9:d4:
7a:17:65:fb:bc:a7:f1:e7:98:2a:97:53:05:80:f8:
ac:ee:56:a7:53:e5:64:28:9a:78:db:46:ed:f1:cc:
71:01:8b:7c:d2:f5:aa:44:ad:97:8f:05:27:33:bd:
a1:fb:85:1a:73:16:d0:4a:3b:b3:95:05:dc:02:ef:
35:5a:be:f7:76:50:78:71:19:9e:89:1e:83:1e:44:
1e:95:9b:57:eb:cb:2e:d8:54:6b:83:51:08:94:5b:
0e:5c:64:49:f5:a6:58:6b:3c:0c:5f:18:1d:12:20:
02:b8:06:64:fb:b8:67:37:bd:ef:17:7c:86:9b:70:
9a:5c:a1:78:34:95:4a:4a:47:f0:45:37:68:ee:38:
ef:f8:fd:90:cd:2c:48:e0:3e:1c:7f:9a:fe:5e:a3:
bc:63:10:a8:13:1a:4d:32:ec:a6:d0:e1:5d:51:4c:
d8:fc:d5:0b:6c:0d:2a:96:10:7e:4c:f0:f6:ec:d2:
a8:1e:d2:94:fb:da:df:42:9e:26:b5:36:91:ba:70:
2e:28:52:ea:34:fe:11:24:5e:aa:c0:5d:1e:c2:7a:
cc:01
prime1:
00:f7:a9:cd:72:b9:5f:93:18:de:a7:4b:5f:31:93:
aa:e0:15:df:71:25:62:7f:f5:bb:f0:85:51:c9:a1:
0a:99:fc:05:8e:b0:3d:ba:51:b0:83:2c:29:ae:8e:
bd:6e:f0:33:e4:51:d8:04:30:05:9e:aa:18:d9:51:
3f:41:2a:d3:a0:5d:ad:8a:d5:94:07:9c:a8:3b:93:
88:6c:21:54:49:92:7f:a5:e7:dd:8e:7d:b6:c5:4b:
d4:ce:0c:e8:6c:86:4d:bc:b6:4b:04:a7:9a:63:9c:
99:a6:0a:c3:f5:4b:bc:00:f9:3f:70:82:92:43:12:
ee:fe:31:41:6e:cf:94:49:d1
prime2:
00:c8:47:1c:dc:6a:d3:d7:b1:be:e1:8b:8e:e6:55:
df:86:db:c4:dd:3f:5a:c3:0e:3e:46:b4:e5:7f:95:
76:99:ab:d2:a9:1b:45:21:98:82:54:08:ba:43:74:
a8:68:cf:79:4e:ca:bf:9e:57:86:e3:4a:06:43:d1:
6f:ee:35:b2:85:dd:48:11:8b:78:a1:cc:79:0e:ec:
40:d8:43:07:56:b9:64:3c:1d:cb:c1:f7:ad:e4:bb:
51:e6:82:21:73:de:8c:30:10:a7:93:38:e6:60:d0:
8f:5f:0d:bc:b3:4a:22:9c:d3:ed:ae:fd:9e:b6:de:
9f:56:db:3f:34:b5:54:2c:f1
exponent1:
00:cc:81:dd:d1:bf:3b:29:b7:5e:9c:5c:83:d5:e7:
6f:31:ad:3e:1e:2b:55:c3:fe:41:dc:21:ea:e0:89:
67:bc:b1:bc:51:10:3d:58:ae:7e:08:43:1e:84:33:
00:40:2c:7f:5d:29:2c:2c:81:0f:12:ee:b8:a8:33:
0b:fd:9f:04:b3:a6:c7:58:1e:77:27:35:f8:41:81:
d9:24:18:fd:85:e7:40:1a:da:75:3c:65:98:d8:20:
7f:30:4a:be:5e:67:24:a8:11:0b:af:63:4a:fc:b8:
62:b4:16:ad:ab:cf:87:06:72:cb:2c:f7:d5:19:27:
f8:4b:d4:96:88:8f:46:8f:11
exponent2:
00:aa:c1:de:fc:9b:64:95:61:ea:12:99:8f:b4:19:
81:64:95:1a:4b:5d:4a:00:46:b3:98:4b:81:e4:fe:
c5:49:0e:73:a5:55:27:e3:16:0a:00:a6:14:51:91:
34:49:70:a3:c8:27:1b:ab:60:8b:14:5d:37:ec:38:
b4:8b:50:63:2e:b9:55:4a:08:35:49:16:72:1c:e4:
18:01:8b:5c:c5:77:79:db:bb:b7:cf:60:62:76:43:
b3:f7:a9:f9:e5:b5:d8:a6:de:7c:52:0c:d0:77:b9:
3a:94:5b:bd:08:cc:6b:a8:75:15:10:ff:12:84:6e:
59:42:8f:da:5b:11:43:7c:b1
coefficient:
04:57:4a:37:8a:d1:96:86:01:04:9f:a3:c0:aa:ec:
17:bf:6e:5e:e0:63:8b:18:b9:ab:5c:22:45:6e:83:
5f:cd:80:a5:de:08:b9:35:b9:b3:29:34:36:f0:11:
91:c9:99:9e:6d:b4:ee:27:65:9a:92:15:a9:fc:84:
0e:e9:8c:01:83:a8:14:51:93:23:45:be:66:33:ba:
89:8b:7d:7a:d5:1f:91:cf:60:e4:ec:10:75:32:65:
34:c0:70:82:a9:62:7e:36:a3:3e:cc:c6:d3:80:14:
e8:fe:bd:c9:d8:4a:43:d0:6c:45:5a:41:ed:1b:38:
a0:02:11:29:32:11:46:7eAvevamo detto che la chiave privata era data dalla tripla $$\((p,q,d)$$\), ma qui abbiamo molte più informazioni:
- modulus è la nostra $$\(n$$\)
- publicExponent è la nostra $$\(e$$\)
- privateExponent è la nostra $$\(d$$\)
- prime1 e prime2 sono rispettivamente $$\(p$$\) e $$\(q$$\)
- exponent1, exponent2 e coefficientsono dei dati che vengono utilizzati dal teorema cinese del resto per velocizzare la fase di decryption
- $$\(\text{exponent1} = d \bmod{p-1}$$\);
- $$\(\text{exponent2} = d \bmod{q-1}$$\);
- $$\(\text{coefficient} = q^{-1} \bmod p$$\).
Per completezza, ecco come cifrare e decifrare utilizzando le nostre due chiavi:
- Supponiamo che vogliamo cifrare "Ciao inforge", anzitutto creiamo un file con: echo "Ciao inforge" > plaintext.txt
- Come ormai ben sappiamo, per cifrare si utilizza la chiave pubblica, quindi facciamo: openssl rsautl -encrypt -pubin -inkey public_key.pem -oaep -in plaintext.txt -out ciphertext.enc
- Con il comando precedente abbiamo detto di cifrare usando RSA, utilizzando la chiave pubblica contenuta in public_key.pem, utilizzando il padding OAEP (Optimal Asymmetric Encryption Padding), il contenuto del file chiamato plaintext.txt e di salvare il crittotesto nel file ciphertext.enc.
- Se vogliamo decifrare, utilizzando la chiave privata, facciamo: openssl rsautl -decrypt -inkey private_key.pem -oaep -in ciphertext.enc e otteniamo in output Ciao inforge.
Firma digitale con RSA
Una firma digitale di un messaggio $$\(m$$\) è una stringa di bit che associa un messaggio con l'entità che l'ha originato. Tale firma dev'essere verificabile, ovvero chiunque dev'essere in grado di verificare l'autenticità di una firma senza l'intervento del firmatario. Lo scopo di una firma digitale è garantire:
- Autenticità: Il destinatario può verificare l'identità del mittente.
- Integrità: Nessuno dev'essere in grado di modificare un documento firmato senza compromettere la validità della firma.
- Non ripudio: Il mittente non può disconoscere un documento da lui firmato.
Esistono due tipologie di firma: con appendice e con recupero di messaggio. Le firme con appendice sono in allegato al messaggio stesso, quelle con recupero di messaggio invece ti permettono di ottenere il messaggio nel momento in cui effettui la verifica.
Per firmare si fa uso degli algoritmi crittografici a chiave pubblica, l'idea è quella di cifrare con la propria chiave privata e di decifrare con la chiave pubblica (l'opposto di quello che si fa normalmente). Vediamo come utilizzare RSA per effettuare una firma con recupero di messaggio:
- Alice genera la sua coppia di chiave $$\(\text{A}_\text{pub} = (n,e)$$\) e $$\(\text{A}_\text{prv} = (p,q,d)$$\) nel modo descritto precedentemente.
- Alice firma un messaggio $$\(m$$\) calcolando $$\(f \equiv m^d \bmod n$$\) e lo pubblica.
- Bob recupera il messaggio calcolando $$\(m \equiv f^e \bmod n$$\), è consapevole che si tratta di un messaggio di Alice perché ha utilizzato la coppia $$\((n,e)$$\) presenti nella chiave pubblica di Alice.
La dimostrazione è analoga a quella precedente. Firmare un messaggio in questo modo è poco conveniente, abbiamo detto che la crittografia asimmetrica è generalmente più lenta di un fattore di $$\(10^3$$\) rispetto alla crittografia simmetrica, firmare un messaggio molto grande (eg. un filmato) richiederebbe troppe risorse sia per la fase di firma che per quella di verifica. Per ovviare a questo inconveniente si fa uso delle funzioni di hash: un hash è una stringa di pochi bit che rappresenta un messaggio, lo possiamo generare molto velocemente e non richiede alcuna chiave. Ha delle proprietà tali per cui è difficile falsificare un hash. Procediamo nel modo seguente
- Alice genera $$\(h(m)$$\) (lo hash del messaggio $$\(m$$\)).
- Alice firma $$\(h(m)$$\) come descritto in precedenza ed pubblica il messaggio originale allegando la firma dell'hash.
- Bob genera $$\(h(m)$$\) (non è richiesta alcuna chiave) e verifica che tale hash corrisponde alla firma decriptata utilizzando la chiave pubblica di Alice.
Con RSA è anche possibile effettuare una blinded signature, ovvero possiamo firmare qualcosa che non ci appartiene e di cui non conosciamo il contenuto. Visto che la firma digitale voleva solo essere un argomento marginale di questa discussione, per il momento non mi dilungo in ulteriori spiegazioni. Se qualcuno fosse interessato al suo funzionamento, me lo faccia sapere e modificherò questo post spiegandone il funzionamento.
PGP / GPG
Se vogliamo comunicare, normalmente non faremo uso di Openssl, ma PGP (Pretty Good Privacy). PGP è uno dei più famosi programmi per cifrare, decifrare, firmare ed effettuare altre operazioni legate al mondo della privacy, GPG (Gnu Privacy Guard) è l'implementazione free (as in freedom) di PGP. Vediamo come utilizzare GPG, da linea di comando, per generare la nostra coppia di chiavi.
- Con gpg2 --full-gen-key avvia una sessione interattiva per generare la chiave.
- GPG supporta molti algoritmi, la prima cosa che ci viene chiesto è il tipo di chiave che vogliamo: con 1 sceglimo RSA and RSA (master key per la firma e chiave subordinata per la cifratura).
- Dopodiché ci viene chiesta la dimensione della chiave, possiamo scegliere un valore tra 1024 e 4096 (in futuro potremo creare chiavi anche più grandi), se non ci sono motivi particolari possiamo andare sul sicuro utilizzando la chiave più grande possibile: 4096.
- Adesso ci viene chiesta la validità della chiave: questo parametro è solo una formalità, dal punto di vista algoritmico non c'è niente che possa scadere. Se qualcuno prova a mandarci qualcosa utilizzando una chiave pubblica scaduta, gli verrà notificato che l'utente di quella chiave pubblica potrebbe non essere più attivo. Visto che noi non siamo interessati a questa cosa mettiamo 0 almeno la chiave non scade mai. In ogni caso, potremmo modificare questo valore successivamente.
- Dovremo inserire i nostri dati: nome, email e (opzionalmente) un commento, questi dati saranno associati alla nostra chiave pubblica. Io ho inserito: "Fake St3ve (this is a comment) <[email protected]>".
- Ci viene chiesta una passphrase, ovvero la password mnemonica che ci permette di non doverci ricordare la tripla $$\(p, q, d$$\) per poter utilizzare la chiave.
- Viene generata la chiave, ovvero tutto ciò che abbiamo descritto in "Generazione della coppia di chiavi" dell'algoritmo. Per avere una buona randomizzazione ci viene chiesto di fare altro nel frattempo, come ad esempio muovere il mouse, pigiare qualche tasto e cose di questo tipo. Visto che abbiamo chiesto una chiave di 4096 bit, potrebbe volerci qualche minuto per generare una chiave sicura, nel frattempo continuiamo ad utilizzare il computer per fare altro: più utilizziamo il computer e meno tempo ci vorrà, dobbiamo aumentare l'entropia. Finito questo processo, abbiamo la nostra coppia di chiavi.
- Con gpg --list-keys possiamo controllare la presenza delle nostre chiavi.
E adesso vediamo come firmare un messaggio utilizzando le nostre chiavi. È un procedimento che possiamo fare anche con openssl, lo facciamo con gpg semplicemente per vedere il funzionamento di questo software che è più adatto agli usi pratici.
- Vogliamo creare una firma con appendice, il messaggio può essere grande a piacere (eg. possiamo firmare un video di diversi gigabyte), GPG si occuperà di generare l'hash e di firmarlo. Per riportarvi gli output, utilizzerò il file "plaintext.txt" ottenuto con il comando: echo "Ciao inforge" > plaintext.txt.
- Firmiamo facendo gpg --clearsign plaintext.txt, che genera il file plaintext.txt.asc.
- Verifichiamo la firma utilizzando gpg --verify plaintext.txt.asc.
Il file plaintext.txt.asc conterrà:
Codice:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
Ciao inforge
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
iQIcBAEBCgAGBQJXjk6ZAAoJEM48TTliuSd34zEP/3N1b1qDLAV5fJURkcqzwYYy
PjMRf/jkCm2EU38L96iSZpcOAx3tRvKoWSbuojIAKg8UDERDf6PZsuvLTU2kEVOs
wWkBUqYetOoM5c/h8jMw3+S+IBjc0iRpd49kIQ9NPoKxQvNWCpIYkl3+6NfyqxAe
e/brXkFrqpabHYZ/h1SSGbvJ/3GKUEInhgfm0Rp+1EDg7IzMFJoRtG2ioBaeMsqS
GyUMM7mBlfiDupzG6jfjcZlRnOJduFv4LRmbq3RK7hUD5ZDuStTKNV98Z/dutit9
UMgSavSMkay0zEsXAk6g4uVgKre25TKiFphq/WosCsACUlmtAlUiXYy6p/fIXzb6
hq0CutM2O6L8OOjr1+USy8WTS08+8MBJTpcBtXX2tuph+Qwgpr/C2ssRQRgZMK3K
UoJIfRGErgm3EUoW4TWluYLhjdW82NaMYkeDClCad5KPRbuSw0KrzCr0Do9wovEh
kZ2OPrC9F17JUyv0rOWEb5/QGMIawUbYc9q43IakMBYuXatSCcUTbXgRHnckx4U7
A7P77a3ze8FsE40AYE21b50pOHYCMhec3BF6UCmjKK3OwyyoizL2ADxlOchlYHWZ
JvayZSicv60t32xNW/7aIBew7xvdt9MlEghk7adHsqJd7vnb1h1bJCrh7afNwnkT
WzoxqMFQwjwdXXrYFHFV
=y8w6
-----END PGP SIGNATURE-----E quando controlleremo a chi appartiene questa firma, nel punto 3, otterremo:
Codice:
gpg: Signature made Tue 19 Jul 2016 06:00:25 PM CEST using RSA key ID CE3C4D3962B92777
gpg: Good signature from "Fake St3ve (this is a comment) <[email protected]>" [ultimate]
gpg: WARNING: not a detached signature; file 'plaintext.txt' was NOT verified!Il warning che otteniamo serve solamente ad avvisarci che è una firma con appendice: non siamo sicuri che il contenuto di plaintext.txt sia esatto, ma abbiamo verificato a chi appartiene il messaggio "Ciao inforge" che appare nel file plaintext.txt.asc. Provando a falsificare il messaggio contenuto in plaintext.txt.asc, per esempio scrivendo "Ciamo inforge!" otterremmo:
Codice:
gpg: Signature made Tue 19 Jul 2016 06:00:25 PM CEST using RSA key ID CE3C4D3962B92777
gpg: BAD signature from "Fake St3ve (this is a comment) <[email protected]>" [ultimate]Attacchi ad RSA: l'implementazione
Ecco alcuni attacchi implementati in C, ho utilizzato la libreria GMP per svolgere le operazioni matematiche sui big numbers. Se volete compilarli dovrete linkare questa libreria. Su GCC è sufficiente aggiungere come parametro -lgmp.
Trial division:
C:
#include <stdio.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
mpz_t n, p, q, rest;
mpz_inits(n, p, q, rest, NULL);
if (argc != 2) {
fprintf(stderr, "Wrong parameters: ./trial_division <decimal number>\n");
return 1 ;
}
mpz_set_str(n, argv[1], 10);
mpz_sqrt(p, n);
if (mpz_even_p(p))
mpz_add_ui(p, p, 1);
do {
mpz_tdiv_qr(q, rest, n, p);
mpz_sub_ui(p, p, 2);
} while (mpz_cmp_ui(rest, 0) != 0);
mpz_add_ui(p, p, 2);
mpz_mul(n, p, q);
gmp_printf("p = %Zd\nq = %Zd\np*q = %Zd\n", p, q, n);
return 0;
}Fermat:
C:
#include <stdio.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
mpz_t n, a, b, p, q;
mpz_inits(n, a, b, p, q, NULL);
if (argc != 2) {
fprintf(stderr, "Wrong parameters: ./fermat <decimal number>\n");
return 1 ;
}
mpz_set_str(n, argv[1], 10);
mpz_sqrt(a, n);
do {
mpz_add_ui(a, a, 1);
mpz_mul(b, a, a);
mpz_sub(b, b, n);
} while (!mpz_perfect_square_p(b));
mpz_sqrt(b, b);
mpz_sub(p, a, b);
mpz_add(q, a, b);
mpz_mul(n, p, q);
gmp_printf("p = %Zd\nq = %Zd\np*q = %Zd\n", p, q, n);
return 0;
}Downloads:
Se trovate qualche errore o se volete delle informazioni aggiuntive, avvisatemi pure!
