Sicurezza
Mappa buffer overflow
Mappa cifratura asimmetrica
Mappa cifratura simmetrica
Mappa firewall
Mappa funzioni di hash e firma elettronica
Mappa IPsec
Mappa XSS, CSRF, SQLi
Struttura RSA

Caratteristiche di RSA
...

  • Il mittente e il ricevente non condividono chiavi
  • Per cifrare e decifrare si usano chiavi diverse
  • Cifratura e decifratura non sono efficienti (come lo sono invece per algoritmo simmetrici)
  • Decifrare senza conoscere la chiave è molto difficile, se non impossibile, poiché questo richiedere risorse computazionali molto potenti.
Perché RSA è così forte?

Perché questo cifrario è basato sulla difficoltà di calcolare la fattorizzazione di numeri ottenuti moltiplicando numeri primi molto grandi.

Altre caratteristiche
...
  • Il plaintext da cifrare e il ciphertext sono numeri minori di un determinato numero che viene detto .
  • RSA è il cifrario asimmetrico più utilizzato.

Schema generale di RSA
...

Per implementare RSA sono necessari tre ingredienti:

  • la generazione di chiavi per ogni utente
  • un algoritmo per cifrare
  • un algoritmo per decifrare

Generazione delle chiavi in RSA
...

  1. Vengono scelti due numeri primi: e .
  2. Viene calcolato , dove è detto modulo RSA.
  3. , viene scelto un valore , in modo che . Per ricapitolare è stato scelto un valore in modo che il massimo comune divisore con restituisca come risultato .
  4. Adesso viene calcolato l'inverso moltiplicativo di , tale inverso è , è l'esponente di decifrazione.

Le chiavi:

  • Chiave pubblica:
  • Chiave privata:
Come avviene la cifratura e la decifratura?

Il ciphertext è uguale a: Il plaintext è uguale a:

Dimostrazione di correttezza per RSA
...

Cifrando otteniamo , vogliamo che decifrando si ottenga lo stesso messaggio di partenza.
Se , allora
Sappiamo che il ciphertext viene generato a partire da:
E che il plaintext viene ottenuto a partire da: Ricordiamo che se , allora . Esempio: , , operazioni di modulo con lo stesso operando ripetute, si riducono ad una singola operazione di modulo.

Dai calcoli sopra, dobbiamo dimostrare che: Sapendo che (come abbiamo detto nel paragrafo sulla generazione delle chiavi, punti 3 e 4: e poi so anche che e sono inversi moltiplicativi in modulo : questo vuol dire che:

Per prima cosa dimostriamo che
...

Sappiamo che e sono due numeri primi.
Diciamo che il prodotto tra e mi restituisce .
Quindi .

è la funzione di Eulero, conta il numero di numeri minori di , che sono relativamente primi con . Per esempio poiché i numeri primi minori di sono: e sono .

Ora, dentro ci sono numeri che vanno da a che non sono multipli né di , né .
Questo insieme è formato da tutti i numeri che vanno da a , quindi tutti gli numeri prima di , a cui vanno sottratti i numeri che sono multipli di .

In questo insieme quindi vi sono, tutti gli numeri prima di , a cui sottraiamo i multipli di e di , quindi:

Notiamo che, i multipli di che possono essere contenuti nell'insieme arrivano fino a , poiché , e stesso ragionamento vale per i multipli di che arrivano fino a .

Possiamo riscrivere l'equazione sopra come: Quanti sono i multipli di che sono stati rimossi? , quindi sono stati rimossi multipli di .

Quanti sono i multipli di che sono stati rimossi? , quindi sono stati rimossi multipli di .

Quindi: Sappiamo che , quindi:
Sono stati raccolti il primo termine e il terzo termine con fattore comune , mentre il secondo e il quarto con fattore comune .

Risultato utile per RSA
...

Teorema di Eulero
Se e sono relativamente primi, allora:Questo è vero anche per qualsiasi tale che: Se e , oltre a essere coprimi, risulta anche che , allora:
Sappiamo che , allora:

Correttezza RSA
...

Avendo dimostrato che la funzione di Eulero di un numero è , avendo ricordato il teorema e avendo fatto presenti dei risultati utili, possiamo conclude la dimostrazione di correttezza per RSA.

Sappiamo che se , allora esiste una costante tale che: Esempio: se e , abbiamo che: , quindi esiste che moltiplicato a , sommatogli , restituisce , infatti

Per il teorema di Eulero abbiamo detto che:ricordiamo che il risultato sopra, per le proprietà delle potenze, può essere scritto come: Ricordiamo che , quindi esisterà un tale che:
Per , abbiamo che:

Abbiamo dimostrato che se e e sono coprimi, allora cifrando e decifrando si riottiene il messaggio originale .

Cosa succede se non è relativamente primo con ?

Nel caso in cui si verifica che : e non sono relativamente primi, per cui oltre ad esiste un altro divisore comune.
per ipotesi, ricordiamo anche che è un numero prodotto di due numeri primi
se possiamo avere due casi:

  • , essendo il prodotto di due primi, può avere come fattore , ma non ;
  • , stesse considerazioni del punto sopra.

Notiamo anche che non può essere , altrimenti questo significa che non è minore di .

Consideriamo uno solo dei due casi: .
Se e hanno fattori in comune, vuol dire che esiste un valore tale che .
Se abbiamo questo vuol dire che e sono coprimi. Infatti se significa che ha come fattore comune con il fattore e non il fattore .
Quindi .
Da quest'ultima considerazione possiamo dire che, per il teorema di Eulero: Le regole della matematica ci consentono di elevare a potenza entrambi i membri di un'equazione allo stesso termine: Il che vuol dire che possiamo elevare per qualsiasi termine entrambi i membri per un numero generico . Abbiamo poi trasformato l'equivalenza in una congruenza. Inoltre se il risultato del termine a sinistra fa vuol dire che esiste un che moltiplicato a e aggiuntogli il resto di si ottiene il membro sinistro della congruenza.
Sempre grazie alle regole della matematica, possiamo moltiplicare entrambi i membri per uno stesso termine: Ricordiamo che , sostituiamolo al termine più a destra nel secondo membro.
Ricordiamo che , sostituiamolo nell'equazione
Ricordiamo che , sostituiamo nell'equazione
A questo punto il membro a sinistra è uguale a: Sappiamo anche che tale che se , otteniamo:

Sicurezza di RSA
...

Punti forti RSA
  • Si ritiene computazionalmente difficile il problema di decifrare un messaggio cifrato con RSA senza conoscere la corrispondente chiave .
  • Si ritiene computazionalmente difficile calcolare a partire da e senza conoscere e .
  • Si ritiene computazionalmente difficile calcolare a partire da , avendo un grande.
Punti deboli

Gli algoritmi per cifrare e decifrare con RSA, hanno complessità , che non può competere con algoritmi simmetrici come AES che hanno complessità .
Anche gli algoritmi per la generazione delle chiavi sono considerati inefficienti.

Per realizzare RSA, occorrono
...

Esempio
...

Supponiamo che Alice e Bob vogliono comunicare utilizzando questo sistema di crittografia.
Supponiamo che Alice generi le su chiavi e fornisce la sua chiave pubblica a Bob, quindi escludiamo il fatto che Bob generi le sue chiavi per fornire la sua chiave pubblica.

Alice
...

Passo 1: scelta di due numeri primi
...

Diciamo che Alice scelga come numeri primi:
Per raggiungere questo scopo Alice utilizza un algoritmo che fa uso dei test di primalità (come quello di Miller-Rabin).

Passo 2: calcolo di
...

Passo 3: calcolo di
...

Passo 4: scelta di in modo che
...

La chiave pubblica di Alice è stata generata ed è:

Passo 5: calcolo di
...

A questo punto attraverso l'algoritmo esteso di Euclide va calcolato l'inverso moltiplicativo di . Ovvero va trovato: Il cui risultato è La chiave privata di Alice è

Bob
...

Bob riceve la chiave pubblica di Alice:
Allora, Bob prepara un certo messaggio che viene elevato a .
A questo punto Bob prende il messaggio e per cifrarlo fa Per dare un'idea di come funziona, sceglieremo un messaggio m = .-., il motivo per cui abbiamo scelto due punti e un trattino è che tali simboli convertiti in decimale non superano la dimensione del modulo che abbiamo scelto . I simboli da cifrare devono avere un valore inferiore rispetto al modulo.
Il punto in decimale risulta essere 46, mentre il trattino 45.
Allora abbiamo m = 46 45 46.
c = 12 30 12.
Bob allora prende il messaggio cifrato e lo invia ad alice.

Alice (parte due)
...

Alice riceve il messaggio e per decifrarlo esegue: Alice allora converte il messaggio da intero decimale a codice ASCII per ottenere: m = .-.

Si noti che tutte queste operazioni sono in realtà effettuate con i numeri binari.

Mettiamoci nei panni di un attaccante
...

Supponiamo di avere la chiave pubblica di Alice:
Avendo questi due valori dovremmo sapere in che modo è fattorizzato 77. In questo caso è molto semplice, poiché è un numero primo piccolo, ma quando il modulo RSA comincia ad avere un certo numero di bit, come , anche per un computer diventa difficile risolvere tale problema.

Prossimo argomento: Funzioni di hash.

Interactive Graph
Table Of Contents

Struttura RSA

Caratteristiche di RSA

Altre caratteristiche

Schema generale di RSA

Generazione delle chiavi in RSA

Dimostrazione di correttezza per RSA

Per prima cosa dimostriamo che

Risultato utile per RSA

Correttezza RSA

Sicurezza di RSA

Per realizzare RSA, occorrono

Esempio

Alice

Passo 1: scelta di due numeri primi

Passo 2: calcolo di

Passo 3: calcolo di

Passo 4: scelta di in modo che

Passo 5: calcolo di

Bob

Alice (parte due)

Mettiamoci nei panni di un attaccante