Guida Crittografia Criptare / Decriptare / Crackare un messaggio cifrato con RSA

0xbro

Super Moderatore
24 Febbraio 2017
4,464
179
3,755
1,825
Criptare / Decriptare / Crackare un messaggio RSA

Ciao a tutti!
Frugando tra i miei vecchi appunti di quinta superiore, ho trovato i codici di una lezione molto interessante, e ho deciso di condividerla con voi.
Si tratta delle criptazione e decriptazione di un messaggio con RSA + il procedimento per crackarne il certificato.

Condividerò con voi i sorgenti e i documenti utilizzati per la realizzazione del programma, in più aggiungerò delle note IMPORTANTISSIME a fine procedimento, per far riflettere sull'intero progetto.

La guida è a scopo didattico/informativo, con lo scopo di mostrare il funzionamento e la sicurezza di questo protocollo.

Prima di iniziare è FONDAMENTALE aver letto il documento "RSA.pdf" (consultabile dal seguente link) al fine di comprendere pienamente il procedimento intrapreso nella release. Nel sopra-citato .pdf viene spiegata e dimostrara la crittografia RSA, sia dal punto di vista pratico che matematico, anche per chi non ne conosce completamente il funzionamento.
Siccome reputo chiaro il documento allegato, non spiegherò la logica della matematica che sta dietro l'algortimo RSA. Basta guardare il documento per capire.

Bene! Ora che abbiamo letto il documento e che sappiamo come funziona il meccanismo RSA, non ci resta altro che implementarlo.

Il codice è scritto in Java, commentato in Italiano, e prevede l'utilizzo di 4 classi:
- Certificato (il nostro certificato che genera la chiave pubblica e privata)
- Codifica (per criptare un messaggio con una delle due chiavi)
- Decodifica (per decriptare il messaggio con l'altra chiave)
- Hack_Long (per crackare i valori di p e q e generarsi l'altra chiave )

Iniziamo con la classe Certificato, che ci permette di calcolare le rispettive chiavi pubbliche e private (n;e) e (n;d)
PS. Il significato dei calcoli effettuati per generare le chiavi è spiegato nel pdf citato a inzio release
Java:
package certificato;

import java.io.*;
import java.util.Scanner;

public class Certificato {

    public static long getMCD(long a, long b) {   // Metodo per ottenere l'MCD tra due numeri
        if (a < b) {
            long z = b;
            b = a;
            a = z;
        }

        long r = a % b;

        while (r != 0) {
            a = b;
            b = r;
            r = a % b;
        }
        return b;
    }

    public static boolean isPrimo(long n) {   // Metodo per valutare se un numero sia primo
        boolean primo = true;
        double radice = Math.sqrt(n);
        for (int i = 2; i <= radice; i++) {
            if (n % i == 0) {
                primo = false;
            }
        }
        return primo;
    }

    public static String key() {  // Creazione della chiave
        long p, q, m, n, e, d;
        Scanner tastiera = new Scanner(System.in);

        do {
            System.out.print("Inserire il valore p: ");
            p = Integer.parseInt(tastiera.next());   // input p
        } while (!isPrimo(p) || p <= 1);

        do {
            System.out.print("Inserire il valore q: ");
            q = Integer.parseInt(tastiera.next());  // input q
        } while (!isPrimo(q) || q <= 1);

        m = (p - 1) * (q - 1); // φ(n)
        n = p * q;

        do {
            System.out.print(m + "Inserire il valore e: ");
            e = Integer.parseInt(tastiera.next());     // input e coprimo con φ(n)
        } while (getMCD(e, m) != 1 || e <= 1 || e >= m);

        long phi_div_e = (long) Math.floorDiv(m, e);  // e⋅d≡1(mod φ (n))
        long phi_mod_e = -m - phi_div_e * e;         // −φ(n)/e

        int k = 1;
        while (Math.floorMod(phi_mod_e * k, e) != 1) { // Incrementando k partendo da 1, si trova il valore che soddisfa l'equazione
            k++;
        }
        d = (k * m + 1) / e;

        System.out.println("\nChiave Privata: (" + n + "," + d + ")");
        System.out.println("Chiave Pubblica: (" + n + "," + e + ")\n");

        return n + "," + d + "," + e;
    }
}

Una volta visto come si genera un certificato, possiamo passare alla creazione della classe per la criptazione del messaggio.
Java:
package certificato;

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Codifica {

    public static long code(long n, long e, long x) {   // codifica
        long base = x % n;
        long risultato = 1;
        while (e > 0) {
            if (e % 2 == 1) {
                risultato = (risultato * base) % n;
            }
            e = e / 2;
            base = (long) (Math.pow(base, 2) % n);
        }
        return risultato;
    }

    private static long[] trasformaStringaInVettore(String msg) {
        int i, length = msg.length();
        long[] vettore = new long[length];
        for (i = 0; i < length; i++) {
            vettore[i] = msg.codePointAt(i);
        }
        return vettore;
    }

    private static String trasformaVettoreInStringa(long[] msg) {
        int i, length = msg.length;
        StringBuilder string = new StringBuilder();
        string.setLength(length);
        for (i = 0; i < length; i++) {
            string.setCharAt(i, (char) msg[i]);
        }
        return string.toString();
    }

    public static void main(String[] args) throws IOException { // processo di criptazione
        InputStreamReader input;
        input = new InputStreamReader(System.in);
        BufferedReader tastiera;
        tastiera = new BufferedReader(input);
        long[] intmex = null;

        String chiave = Certificato.key();  // richiesta della chiave e creazione del certificato
        StringTokenizer st = new StringTokenizer(chiave, ",");
        long n = Long.parseLong(st.nextToken()); //valore numerico della prima parte della chiave
        long d = Long.parseLong(st.nextToken()); //valore numerico della seconda parte della chiave (n;d)
        long e = Long.parseLong(st.nextToken()); //valore numerico della seconda parte della chiave (n;e)

        System.out.println("Inserire il messaggio: ");
        String mex = tastiera.readLine();           //acquisisco il messaggio da tastiera
        intmex = trasformaStringaInVettore(mex);    //trasformo il mex da stringa a vettore di interi
        long[] messaggio = new long[intmex.length]; //inizializzo il vettore per la codifica

        for (int i = 0; i < intmex.length; i++) {
            messaggio[i] = code(n, e, intmex[i]);
        }
        System.out.println("Il messaggio criptato è: ");
        for (int i = 0; i < messaggio.length; i++) {
            if((i+1)==messaggio.length)
                System.out.print(messaggio[i]+"\n");
            else
                System.out.print(messaggio[i]+",");
         }
    }
}

e in similmodo la decriptazione
Java:
package certificato;

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Decodifica {

    public static long code(long n, long e, long x) { // decodifica
        long base = x % n;
        long risultato = 1;
        while (e > 0) {
            if (e % 2 == 1) {
                risultato = (risultato * base) % n;
            }
            e = e / 2;
            base = (int) (Math.pow(base, 2) % n);
        }
        return risultato;
    }

    public static long[] trasformaStringaInVettore(String msg) {
        int i, length = msg.length();
        long[] vettore = new long[length];
        for (i = 0; i < length; i++) {
            vettore[i] = msg.codePointAt(i);
        }
        return vettore;
    }

    public static String trasformaVettoreInStringa(long[] msg) {
        int i, length = msg.length;
        StringBuilder string = new StringBuilder();
        string.setLength(length);
        for (i = 0; i < length; i++) {
            string.setCharAt(i, (char) msg[i]);
        }
        return string.toString();
    }

    public static void main(String[] args) throws IOException { // processo di decodifica
        InputStreamReader input;
        input = new InputStreamReader(System.in);
        BufferedReader tastiera;
        tastiera = new BufferedReader(input);
        int[] intmex = null;

        String chiave = Certificato.key();  // richiesta della chiave e creazione del certificato
        StringTokenizer st = new StringTokenizer(chiave, ",");
        long n = Long.parseLong(st.nextToken()); //valore numerico della prima parte della chiave
        long d = Long.parseLong(st.nextToken()); //valore numerico della seconda parte della chiave (n;d)
        long e = Long.parseLong(st.nextToken()); //valore numerico della seconda parte della chiave (n;e)

        System.out.println("Inserire il messaggio: ");
        String mex = tastiera.readLine();
        st = new StringTokenizer(mex, ",");
        int lunghezza = st.countTokens();
        long[] messaggioint = new long[lunghezza];
        for (int i = 0; i < lunghezza; i++) {
            messaggioint[i] = code(n, d, Long.parseLong(st.nextToken()));
        }
        String messaggiofinale = trasformaVettoreInStringa(messaggioint);
        System.out.println("Il messaggio decriptato è: \n" + messaggiofinale);
    }
}

Bene! Adesso siamo in grado di generare chiave pubblica e privata e codificare con una chiave e decodificare con l'altra un messaggio a nostro piacimento.

MA ORA ARRIVA IL BELLO!

Dobbiamo fare in modo, avendo solo una chiave (la chiave pubblica), di trovarci i valori per generarci la chiave privata , per decriptare il messaggio criptato con la chiave pubblica del destinatario.
Il codice sorgente è il seguente:
PS. Non badate al nome "Long".. dopo vi spiegherò il perchè!
Java:
package certificato;

import static certificato.Certificato.isPrimo;
import static certificato.Decodifica.code;
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Hack_Long {      // Hack delle chiavi del certificato

    public static boolean isPrimo(long n) {   // Metodo per valutare se un numero sia primo
        boolean primo = true;
        double radice = Math.sqrt(n);
        for (int i = 2; i <= radice; i++) {
            if (n % i == 0) {
                primo = false;
            }
        }
        return primo;
    }

    public static long code(long n, long e, long x) {  // codifica
        long base = x % n;
        long risultato = 1;
        while (e > 0) {
            if (e % 2 == 1) {
                risultato = (risultato * base) % n;
            }
            e = e / 2;
            base = (long) (Math.pow(base, 2) % n);
        }
        return risultato;
    }

    public static int[] trasformaStringaInVettore(String msg) {
        int i, length = msg.length();
        int[] vettore = new int[length];
        for (i = 0; i < length; i++) {
            vettore[i] = msg.codePointAt(i);
        }
        return vettore;
    }

    public static String trasformaVettoreInStringa(long[] msg) {
        int i, length = msg.length;
        StringBuilder string = new StringBuilder();
        string.setLength(length);
        for (i = 0; i < length; i++) {
            string.setCharAt(i, (char) msg[i]);
        }
        return string.toString();
    }

    public static void main(String[] args) {
        Scanner tastiera = new Scanner(System.in);

        System.out.println("Inserire il valore n: "); // primo valore della chiave (n;e)
        long n = Integer.parseInt(tastiera.next());

        System.out.println("Inserire il valore e: "); // secondo valore della chiave (n;e)
        long e = Integer.parseInt(tastiera.next());

        long tStart = System.nanoTime();              // tempo a inizio processo di cracking

        long p, q = 0;
        do {        // cerco i valori di p e q coprimi tra loro
            p = 2;
            while (n % p != 0) {
                p++;
            }
            q = n / p;
        } while (!isPrimo(p) || !isPrimo(q) || n <= 1);

        long m = (p - 1) * (q - 1);           // φ(n)
        long phi_div_e = (long) Math.floor(-(double) m / (double) e); //  e⋅d≡1(mod φ (n))
        long phi_mod_e = -m - phi_div_e * e;  // −φ(n)/e

        int k = 1;
        while ((phi_mod_e * k) % e != 1) {   // Incrementando k partendo da 1, si trova il valore che soddisfa l'equazione
            k++;
        }
        long d = (k * m + 1) / e;        // Trovo l'ultimo valore per avere l'altra chiave

        long tEnd = System.nanoTime();  // Tempo a fine processo di cracking
        long tDelta = tEnd - tStart;    // Tempo impiegato
        //long elapsedSecond = tDelta;

        System.out.println("Tempo impiegato: " + tDelta);

        System.out.println("Inserire il messaggio x: ");
        int x = Integer.parseInt(tastiera.next());

        int hackerato = Codifica.code(n, d, x);

        System.out.println("<< HACK DEL MESSAGGIO RIUSCITO >>"
        + "\nCONTENUTO: " + hackerato);*/

        // Decriptazione del messaggio criptato
        System.out.println("Inserire il messaggio: ");
        String mex = tastiera.next();
        StringTokenizer st = new StringTokenizer(mex, ",");
        int lunghezza = st.countTokens();
        long[] messaggioint = new long[lunghezza];
        for (int i = 0; i < lunghezza; i++) {
            messaggioint[i] = code(n, d, Integer.parseInt(st.nextToken()));
        }
        String messaggiofinale = trasformaVettoreInStringa(messaggioint);
        System.out.println("<< HACK DEL MESSAGGIO RIUSCITO >>"
                + "\nCONTENUTO: " + messaggiofinale);
    }
}
Ecco fatto! Presa in input una chiave, siamo riusciti a generarci l'altra chiave e decriptare il messaggio!
Bello e divertente vero?

Peccato (o forse menomale) che nella vita reale non sia così semplice.

IMPORTANTE: analisi di fine progetto
Come si può notare nel sorgente di cracking ho inserito delle variabili per tenere conto della velocità con cui il programma riesce a craccare il certificato.
Questo è stato fatto per mostrare quanto sia sicuro l'algoritmo RSA.

Utilizzando i seguenti valori per generare le chiavi
p=11 ; q=13 ; e=17 otteniamo Chiave Privata: (143,113) e Chiave Pubblica: (143,17)
Per craccare i seguenti valori, il programma ci impiega 477238 nano-secondi, cioè 0,000477238 secondi

Utilizzando però valori più grandi, come
p=991 ; q=997 ; e=1009
Chiave Privata: (988027,798409)
Chiave Pubblica: (988027,1009)
il programma ci impiega già di più: 581795 nano-secondi, cioè 0,000581795 secondi

Utilizzando valori ancora più grandi, come
p=4987 ; q=4993 ; e=4999
Chiave Privata: (24900091,4102711)
Chiave Pubblica: (24900091,4999)
il programma ci impiega ancora di più: 798284 nano-secondi, cioè 0,000798284 secondi.

Queste chiavi, che sembrano molto grosse, in verità sono microscopiche per i calcolatori moderni. Infatti nell'algortimo RSA si utilizzano chiavi generate da numeri primi con 300 cifre decimali e più! (ecco il motivo per cui la classe si chiami Hack_Long: perchè servono variabili long per contenere i numeri generati, e non bastano le variabili int)
Questo per citare ciò che viene scritto nel documento linkato a inizio sorgente:
Per ottenere una discreta sicurezza è necessario utilizzare chiavi binarie di almeno 2048 bit. Quelle
a 512 bit sono ricavabili in poche ore. Le chiavi a 1024 bit, ancora oggi largamente utilizzate, non
sono più consigliabili. La fattorizzazione di interi grandi, infatti, è progredita rapidamente mediante
l'utilizzo di hardware dedicati, al punto che potrebbe essere possibile fattorizzare un intero di 1024
bit in un solo anno di tempo, al costo di un milione di dollari (un costo sostenibile per qualunque
grande organizzazione, agenzia o intelligence.

Spero che il lavoro vi sia piaciuto e sia stato utile :)
E' davvero un bel progettino che fa ragione sulla logica della criptazione a chiave asimmetrica e sulla sicurezza di quest'ultima. Da provare almeno una volta!

Autore: 0xbro
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.