Crittografia RSA

Per rendere ancora più sicure le comunicazioni segrete tra gli smartphone durante l’esame di maturità, gli studenti stanno ponderando l’eventualità di cifrare tutti i messaggi che si scambieranno. Nel corso dell’ultimo anno scolastico hanno infatti studiato l’algoritmo di cifratura asimmetrica RSA. L’idea è semplice: realizzare un’app che cifri i messaggi e un’altra che li decifri; in questo modo anche qualora i commissari dovessero intercettarli non riuscirebbero a leggerne il contenuto!

Soluzione corretta al 100%:

                
#include <stdlib.h> 

long long mod_pow(long long base, long long esponente, long long modulo) {
    long long risultato = 1;
    base = base % modulo;
    while (esponente > 0) {
        if (esponente % 2 == 1) {
            risultato = (risultato * base) % modulo;
        }
        base = (base * base) % modulo;
        esponente /= 2;
    }
    return risultato;
}

void decifra(int N, int d, int L, int messaggio[], char plaintext[]) {
    for (int i = 0; i < L; i++) {
        // Decifra c^d mod N utilizzando l'esponenziazione modulare rapida
        long long carattere_decifrato = mod_pow(messaggio[i], d, N);

        // Converte il carattere decifrato in char e lo aggiunge a plaintext
        plaintext[i] = (char)carattere_decifrato;
    }

    // Aggiunge il carattere di fine stringa '\0' alla fine di plaintext
    plaintext[L] = '\0';
}

Spiegazione del programma:

In questa implementazione, per ottimizzare il calcolo di c^d mod N, puoi utilizzare l'esponenziazione modulare rapida, che ridurrà notevolmente il tempo di esecuzione, specialmente per grandi valori di d. L'esponenziazione modulare rapida sfrutta le proprietà dell'aritmetica modulare per calcolare l'esponente in modo più efficiente.
Utilizzando la funzione mod_pow sopra, riduci notevolmente il tempo di esecuzione, soprattutto per grandi esponenti d. Questa funzione calcola base^esponente mod modulo in modo efficiente, evitando calcoli ridondanti e migliorando le prestazioni del tuo algoritmo.