Salsa di bit: Cifrare RSA: applicare le caratteristiche dei numeri primi

Abbiamo visto nel post di tempo fa, principi di codifica e cifratura. Oggi sviluppiamo l'argomento introducendo l'algoritmo RSA, derivato da l'applicazione di numeri primi.

Fin dai tempi di Euclide, cioè circa dal 300 a.C., gli antichi Greci sapevano che ci sono infiniti numeri primi e che essi sono distribuiti in maniera irregolare tra i numeri naturali. Da allora, molti matematici eminenti, come Fermat, Mersenne, Leibniz, Eulero, Gauss ecc., hanno compilato e analizzato lunghi elenchi di numeri primi, nel tentativo di farsi un'idea della loro distribuzione e per cercare delle formule in grado di produrre, se non tutti, almeno "molti"numeri primi.

Per esempio, un importante risultato fu ottenuto nel 1896 da due matematici francesi, Hadamard e De la Vallie Poussin. Essi dimostrarono il seguente teorema, che era stato congetturato quasi un secolo prima da Gauss: il numero dei primi minori o uguali a n può essere approssimato da n/log n (al crescere di n).

D'altra parte, molti matematici dal '600 in poi, a partire da Mersenne, si de dicarono a studiare i numeri del tipo 2p-1, con p primo. Infatti Fermat aveva dimostrato che, se non sono primi, i numeri di questo tipo hanno fattori tutti della forma 2Kp+1, con k numero naturale. Questo semplifica molto il test di primalità, cioè la verifica se sono primi o meno. In effetti, i più grandi primi trovati finora sono proprio primi di Mersenne, cioè del tipo 2p-1. In particolare lo è l'ultimo, quello trovato lo scorso novembre dal ventenne canadese Michael Cameron: si tratta di 213.466.917-1, un numero con oltre 4 milioni di cifre!

Quello che spinge a cercare nuovi numeri primi può essere l'emulazione nei confronti degli illustri matematici del passato, il desiderio di gloria, il piacere di battere un record. Nello stesso tempo, ci possono essere risultati collaterali della ricerca svolta, di interesse indipendente. Dagli anni '50 in poi, i conti necessari a verificare che grandi numeri sono primi sono stati effettuati dalle macchine calcolatrici: i programmi per trovare numeri primi sono stati usati per testare del nuovo hardware, c'è stata quindi un'utilità pratica.

A partire dagli anni '80, grandi numeri primi sono stati usati per cifrare messaggi segreti con il metodo di crittografia a chiave pubblica detto RSA (dai nomi dei suoi ideatori Rivest, Shamir e Adleman, ricercatori del Massachussetts Institute of Technology).

I metodi di crittografia a chiave pubblica prevedono che, chi deve ricevere l'informazione, renda pubblica la chiave (alcuni numeri) e il metodo per cifrare i messaggi. Egli poi, in base a dei "numerisegreti" in suo possesso è in grado di decifrare i messaggi che gli vengono inviati.

Nel metodo RSA:

i numeri segreti sono due numeri primi p, q e un numero N primo con (p-1)(q-1)
la chiave pubblica è costituita dal prodotto pq e da un numero M tale che MN-1 sia multiplo di (p-1)(q-1)
il messaggio da trasmettere è un numero intero positivo x, minore di pq;
il messaggio cifrato è il numero y, ottenuto come resto della divisione di xM per pq
per decifrare il messaggio, è sufficiente calcolare il resto della divisione di yN per pq.

Osserviamo che il messaggio deve essere un numero positivo e minore di pq. Pertanto se si tratta di un messaggio in lettere, bisogna innanzitutto trasformarlo in cifre con un metodo qualunque. Se il numero trovato è troppo grande, lo si spezza in numeri più piccoli da trasmettere separatamente.

La spiegazione del metodo si basa sul seguente teorema, che a sua volta segue da un famoso teorema, noto come piccolo teorema di Fermat.

Teorema Se 0≤x(x^M)^{^N} è congruo a x modulo pq.

Nella pratica, bisogna scegliere p e q primi molto grandi, in modo che sia impossibile fattorizzare pq in tempo ragionevole. Il metodo infatti si basa sull'assunzione che sia estremamente difficile risalire a p e q conoscendo il loro prodotto.

Se chi intercettasse un messaggio fosse in grado di fattorizzare pq, di conseguenza conoscerebbe anche (p-1)(q-1), e per trovare N gli sarebbe sufficiente risolvere l'equazione

MN = 1 mod (p-1)(q-1),

con M e (p-1)(q-1) primi tra loro, entrerebbe così facilmente in possesso di tutte le informazioni necessarie a decifrare il messaggio.

Il rapido sviluppo di nuove tecniche per la fattorizzazione dei numeri composti sta rendendo problematico l'uso del metodo RSA. Si è infatti costretti a usare numeri p,q sempre più grandi, cosa che rende molto lungo il calcolo di y e di y^N mod pq. Ci si sta orientando dunque a tornare a metodi crittografici classici, trasmettendo col metodo RSA soltanto la chiave.

Per saperne di più, consiglio i libri:

K. Devlin, Dove va la matematica?, Boringhieri
D. M. Davis, The nature and power of mathematics, Princeton University Press
S. Singh, Codici e Segreti, Rizzoli

e i siti web:

http://www.utm.edu/research/primes
http://www.mersenne.org/prime.htm