Crittografia asimmetrica (RSA) Dato un numero intero positivo N C = (N^e)%r Decifratura => N = (C^d)%r La chiave di cifratura e' data dalla coppia di numeri interi positivi (e, r). La chiave di decifratura e' data dalla coppia di numeri interi positivi (d, r). Si puo' rappresentare sinteticamente una chiave (di cifratura/decifratura) con la terna (e, d, r). L'algoritmo di costruzione delle chiavi e' il seguente: 1 generare due numeri primi molto grandi p e q 2 calcolare r = p*q 3 calcolare f(r)=(p-1)*(q-1) 4 prendere un numero e tale numero è la chiave di cifratura 5 trovare un numero d tale che (d*e)%f(r) = 1 -> tale numero è la chiave di decifratura Esempi di costruzione di chiavi p q r f(r) e d 3 5 15 8 3 11 3 5 15 8 5 13 2 5 10 4 3 7 17 13 221 192 11 35 19 17 323 288 5 173 Alcune chiavi valide sono le seguenti: (3, 11, 15) per cifrare/decifrare numeri interi positivi minori di 15 (5, 13, 15) per cifrare/decifrare numeri interi positivi minori di 15 (3, 7, 10) per cifrare/decifrare numeri interi positivi minori di 10 (11, 35, 221) per cifrare/decifrare numeri interi positivi minori di 221 (5, 173, 323) per cifrare/decifrare numeri interi positivi minori di 323 -------------------------------------------- Nei programmi seguenti non ci si occupa della generazione delle chiavi, ma si da per scontato che sia già noto quali terne costituiscono delle chiavi valide! In particolare si possono usare le terne elencate sopra. Realizzare la cifratura del numero N e la decifratura del numero C mediante un algoritmo ricorsivo. ------------------------------------------------------------------------- RSA intero Traccia: Scrivere un programma che fornisca il seguente menu ed implementi le funzioni in esso elencate Chiave attualmente in uso: (5, 173, 323) 1 Inserimento nuova chiave RSA 2 Cifratura di un numero 3 Decifratura di un numero 4 Uscita Il programma parte con la chiave predefinita (5, 173, 323). Se scegliamo di modificarla, il programma ci chiede di inserire una nuova terna di numeri. Il programma non controlla se la nuova terna e' corretta o meno, sta a noi assicurarci di fornire tre numeri corretti. Se la chiave RSA e' corretta, il programma permette di cifrare/decifrare un numero. Realizzare la cifratura/decifratura all'interno di funzioni dedicate (quante ne occorrono?). Memorizzare la terna in tre variabili globali. Gestire le situazioni di errore, tranne, ovviamente, il controllo della correttezza delle chiavi inserite. (finito il programma, provare ad invertire l'uso della chiave di cifratura con quella di decifratura ...) Un possibile output e' il seguente: Chiave attualmente in uso: (5, 173, 323) 1 Inserimento nuova chiave RSA 2 Cifratura di un numero 3 Decifratura di un numero 4 Uscita Scelta 2 Inserisci il numero da cifrare 123 Il numero cifrato e' 225 Chiave attualmente in uso: (5, 173, 323) 1 Inserimento nuova chiave RSA 2 Cifratura di un numero 3 Decifratura di un numero 4 Uscita Scelta 3 Inserisci il numero da decifrare 225 Il numero cifrato e' 123 ---- Attenzione: l'elevamento a potenza e' una operazione che puo' portare ad overflow, perche' a^n puo' essere un numero enorme. Dobbiamo, pertanto evitare un approccio del tipo: . calcolo a^n . dato il valore di a^n, calcolo il resto della divisione intera per r Per evitare il problema, possiamo sfruttare la seguente proprieta': (a^n)%r = ( a * ( (a^(n-1))%r ) )%r Sfruttando questa proprieta' si puo' realizzare sia una versione ricorsiva che una versione iterativa del calcolo di (a^n)%r. Bisogna cercare di mantenere limitato il valore calcolato in ciascuna invocazione ricorsiva o iterazione. Suggerimenti per la versione ricorsiva Ad ogni passo ricorsivo, possiamo utilizzare il seguente schema: 1 dato il valore di a^(n-1), ne calcoliamo il resto della divisione intera per r (ottenendo un numero minore o uguale ad r) 2 moltiplichiamo il risultato per a 3 calcoliamo il resto della divisione intera per r (ottenendo, di nuovo, un numero minore di r) Importante: se abbiamo fatto le cose per bene, potremmo accorgerci che il calcolo del resto al passo 1 non e' necessario ... ---------------------------------------------------- RSA array di interi Traccia: Scrivere un programma che fornisca il seguente menu e implementi le funzioni in esso elencate Chiave attualmente in uso: (5, 173, 323) Contenuto attuale del vettore: 1 2 3 4 5 1 Inserimento nuova chiave RSA 2 Cifratura vettore 3 Decifratura vettore 4 Uscita Il programma contiene al suo interno un vettore di 5 interi (nell'esempio il vettore contiene i numeri da 1 a 5). Se si sceglie l'opzione 2, il contenuto del vettore viene cifrato (si perde pertanto il contenuto precedente). Se si sceglie l'opzione 3, il contenuto del vettore viene decifrato (se tutto e' andato bene, si e' recuperato il contenuto precedente). Il programma parte con la chiave predefinita (5, 173, 323). Se scegliamo di modificarla, il programma ci chiede di inserire una nuova terna di numeri. Il programma non controlla se la nuova terna e' corretta o meno, ma siamo noi che dobbiamo assicurarci di fornire tre numeri corretti. Se la chiave RSA e' corretta, il programma permette di cifrare/decifrare un numero. Gestire le situazioni di errore, tranne, ovviamente, il controllo della correttezza delle chiavi inserite. ----------------------------------------------------------------------------- RSA messaggio Traccia: Scrivere un programma che fornisca il seguente menu e implementi le funzioni in esso elencate Chiave attualmente in uso: (5, 173, 323) Messaggio attuale: Ciao mondo! 1 Inserimento nuova chiave RSA 2 Cifratura messaggio 3 Decifratura messaggio 4 Uscita Il programma contiene al suo interno un messaggio in codice ASCII. Se si sceglie l'opzione 2, il messaggio viene cifrato (si perde pertanto il contenuto precedente). Se si sceglie l'opzione 3, il messaggio viene decifrato (se tutto e' andato bene, si e' recuperato il contenuto precedente). Il programma parte con la chiave predefinita (5, 173, 323). Se scegliamo di modificarla, il programma ci chiede di inserire una nuova terna di numeri. Il programma non controlla se la nuova terna e' corretta o meno, ma siamo noi che dobbiamo assicurarci di fornire tre numeri corretti. Se la chiave RSA e' corretta, il programma permette di cifrare/decifrare un numero. Gestire le situazioni di errore, tranne, ovviamente, il controllo della correttezza delle chiavi inserite. ------------------------------------------------- Il seguente messaggio e' stato criptato con la chiave (5, 173,323) e, una volta decriptato, va letto molto velocemente: int messaggio_criptato[556] = { 193, 87, 131, 271, 42, 104, 230, 42, 223, 53, 230, 241, 223, 190, 22, 131, 190, 271, 131, 241, 223, 115, 42, 169, 165, 109, 241, 223, 22, 230, 223, 53, 230, 241, 223, 53, 169, 22, 230, 22, 115, 271, 190, 165, 241, 286, 223, 22, 241, 165, 22, 109, 241, 230, 241, 176, 223, 230, 42, 230, 223, 168, 241, 223, 22, 6, 181, 42, 165, 190, 107, 241, 230, 241, 193, 22, 230, 223, 265, 241, 109, 53, 271, 223, 42, 104, 190, 230, 22, 271, 223, 109, 271, 223, 109, 165, 271, 165, 190, 271, 271, 223, 115, 230, 42, 42, 223, 104, 115, 22, 42, 6, 165, 115, 271, 223, 22, 230, 223, 53, 230, 241, 223, 6, 190, 42, 241, 109, 241, 223, 109, 286, 53, 131, 22, 230, 241, 223, 131, 115, 42, 241, 223, 193, 22, 6, 181, 42, 165, 190, 241, 165, 230, 271, 223, 271, 286, 223, 131, 168, 271, 223, 109, 241, 223, 6, 181, 22, 190, 241, 223, 271, 223, 109, 286, 53, 165, 109, 181, 22, 241, 223, 109, 165, 271, 190, 271, 165, 241, 223, 115, 241, 230, 22, 42, 223, 241, 109, 223, 6, 115, 42, 165, 42, 223, 69, 53, 115, 165, 22, 42, 88, 223, 193, 99, 109, 223, 190, 115, 271, 165, 42, 223, 6, 53, 42, 286, 223, 271, 115, 190, 271, 115, 271, 223, 53, 230, 241, 223, 165, 241, 109, 42, 165, 271, 223, 131, 230, 68, 42, 115, 42, 53, 230, 22, 271, 223, 271, 104, 223, 271, 115, 190, 271, 115, 271, 223, 241, 131, 230, 190, 42, 241, 223, 131, 181, 6, 42, 109, 165, 271, 241, 230, 271, 181, 165, 271, 193, 131, 181, 6, 190, 42, 115, 230, 271, 22, 109, 22, 319, 271, 88, 193, 47, 271, 53, 165, 115, 42, 223, 6, 190, 271, 168, 131, 271, 286, 223, 230, 42, 230, 223, 109, 69, 271, 69, 241, 181, 22, 42, 223, 42, 230, 69, 22, 223, 115, 230, 22, 42, 109, 69, 241, 223, 109, 165, 271, 190, 165, 271, 241, 223, 181, 241, 223, 109, 241, 223, 6, 190, 241, 109, 42, 241, 223, 230, 109, 271, 109, 241, 223, 115, 53, 241, 193, 22, 165, 230, 271, 107, 190, 271, 107, 241, 88, 193, 206, 169, 190, 241, 22, 176, 223, 115, 271, 165, 22, 271, 223, 190, 115, 22, 53, 22, 131, 165, 22, 223, 241, 223, 104, 131, 271, 68, 190, 22, 241, 190, 271, 223, 22, 109, 223, 181, 271, 115, 69, 241, 115, 69, 22, 42, 88, 223, 87, 131, 115, 53, 241, 165, 271, 176, 223, 181, 241, 223, 230, 42, 230, 223, 168, 42, 223, 190, 115, 271, 22, 165, 115, 165, 22, 42, 193, 241, 109, 109, 241, 223, 165, 230, 271, 165, 241, 22, 107, 42, 230, 271, 223, 104, 22, 223, 68, 190, 241, 169, 22, 223, 6, 190, 271, 104, 230, 190, 271, 271, 223, 53, 230, 223, 6, 22, 131, 42, 131, 109, 42, 223, 115, 6, 169, 241, 271, 165, 230, 42, 176, 223, 115, 6, 115, 42, 165, 241, 104, 230, 42, 223, 109, 271, 223, 109, 165, 271, 165, 190, 271, 271, 193, 230, 109, 271, 109, 271, 223, 6, 190, 241, 42, 109, 271, 96, 163, 300, 193, 0 } ;