I numeri primi e la crittografia

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 2^p-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 2^p-1. In particolare lo è l'ultimo, quello trovato lo scorso novembre dal ventenne canadese Michael Cameron: si tratta di 2^13.466.917-1, un numero con oltre 4 milioni di cifre!

Tornando alla domanda iniziale, 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 (e qui vengo alla seconda domanda), 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 x^M perpq
- per decifrare il messaggio, è sufficiente calcolare il resto della divisione di y^N perpq.

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 numerip,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

Emilia MezzettiDipartimento di Matematica e Informatica, Università di Trieste

Fonte: http://ulisse.sissa.it/chiediAUlisse/domanda/2001/Ucau011225d001/

IL PICCOLO TEOREMA DI FERMAT E IL SISTEMA RSA

In una lettera scritta nel 1640 ad un amico, Fermat dichiarò di aver trovato la dimostrazione di un teorema, denominato in seguito piccolo teorema di Fermat, che afferma:

PICCOLO TEOREMA DI FERMAT Sia p un numero primo. Allora per ogni intero a, vale  a^p≡a(mod p)

• Osservazione : ciò implica che in un orologio di Gauss con p ore, moltiplicando a per se stesso p-volte ,si ottiene sempre il numero a!!!!!!!
  
• Esempio: 2⁵≡2(mod 5) 2¹³≡2(mod 13)

Dimostrazione:

La dimostrazione del teorema è di Eulero (1736)

per induzione su a≥0; 

Per a =0, si ha che 0p=0≡0(mod p)  

Per ipotesi sia : ap≡a(mod p)  cioè ap-a=pd’   

Considero la relazione per (a+1) e tramite la formula del binomio di Newton scrivo                              (a+1)p   =  

Ricordiamo che i coefficienti binomiali sono numeri interi e precisamente: 

                                      

Quando 0

 Allora posso scrivere (a+1)p= ap+1+ pd

Quindi:   (a+1)p-(a+1)=ap+1+pd-a-1= (ap –a) +pd = pd’+pd =p(d’+d)         quindi           (a+1)p≡(a+1)(mod p) (si osservi che dopo = si è usata l’ipotesi induttiva)

quindi (a+1)^p≡(a+1)(mod p). 

• Eulero non si limitò a dimostrare il teorema ma lo estese anche al caso in cui p non sia primo.
  
  
• Se infatti si considera un numero N =p·q, con p e q primi, si ha che
  a ^(p-1)(q-1)+1≡a(mod N)
• Questo vuol dire che in un orologio di Gauss con N ore, l’andamento si ripete dopo
  (p-1)(q-1)+1 passaggi.
  
  
• Esempio: 2^(3-1)(5-1)+1≡2(mod 15)

IL CRIPTOSISTEMA RSA

Il criptosistema a chiave pubblica più conosciuto e usato è quello chiamato RSA dalle iniziali dei suoi inventori Rivest, Shamir, Adleman.

La criptografia a chiave pubblica fu proposta pubblicamente per al prima volta nel 1976 in un articolo scientifico scitto da due matematici californiani: Whit Diffie e Martin Hellmann.

Il sistema si basava sull’esistenza di due chiavi : una chiave pubblica e una chiave privata.

Utilizzando la chiave pubblica è possibile inviare un messaggio

Solo chi conosce la chiave privata è in grado di leggere il messaggio

• I matematici Rivest, Shamir, Adleman accettarono la sfida e compresero che nella teoria dei numeri, ed in particolare in quella riguardante i numeri primi , c’era la soluzione.
  
  

Utilizzarono il teorema di Fermat e il teorema di Eulero che considerava orologi di Gauss con un numero di ore pari a N dove N è uguale al prodotto di due numeri primi p e q.

Ogni utente A (ad esempio una banca) fissa due numeri primi p e q (con p≠q) molto grandi e ne calcola il prodotto N=p·q

A comunica a B (ad esempio un titolare di carta di credito che vuole comprare via internet) sia N che un numero E (opportunamente scelto)

B prende il numero della sua carta di credito, cioè C, e lo eleva alla E modulo N : C^E(mod N). Quindi restituisce questo numero ad A.

A possiede un numero di decodifica cioè un numero D tale che con l’operazione (C^E)^D=C(modN).

• Perché il sistema è sicuro?

Cosa accade se un hacker viene a conoscenza di N,E e del numero comunicato da B cioè
C^E(mod N)?

Può risalire facilmente a D e con l’operazione (C^E)^D=C(mod N) può risalire a C?

Per fare questo è necessario conoscere come si decompone N cioè è necessario conoscere p e q.

Ciò è molto difficile se si utilizzano numeri N con molte cifre.

Oggi il sistema RSA raccomanda di utilizzare un numero N che abbia almeno 230 cifre

Ma le agenzie governative che necessitano di un livello di sicurezza in grado di garantire una protezione a lungo termine raccomandano l’utilizzo di numeri N con più di 600 cifre.

• Quant’è difficile scomporre un numero nei primi che lo costituiscono?

Rivest, Shamir, Adleman dopo aver inventato il metodo RSA lanciarono una sfida chiamata “RSA129”: fattorizzare un numero di 129 cifre che loro stessi avevano ottenuto moltiplicando due numero primi

Dichiararono che ci sarebbero voluti migliaia di anni!!!!

La sfida fu accettata da molti matematici e il problema fu risolto in soli 17 anni (Aprile 1994)

• Per generazioni si è cercato comprendere i misteri legati ai numeri primi

Sappiamo già che i numeri primi sono infiniti.

Per anni si sono cercate formule in grado di produrre un elenco di numeri primi.

Alla luce delle nuove esigenze , la parte della matematica che studia i numeri primi è diventata di grande attualità

Numeri di Fermat (1601-1665)

Consideriamo le potenze di 2 : 1, 2, 4, 8, 16, ….,2^m,….

e i loro successori 2, 3, 5, 9, 17, ..., 2^m+1, ...

Trascuriamo 2, dunque supponiamo m>0.

Osserviamo: se m ha un fattore dispari d >1 ,

m= d d′ cioè se m non è potenza di 2, 2^m +1 è composto.

2^m+1=(2^d’)^d+1^d=(2^d’+1) · ….. (Infatti se d è dispari, (a^d+b^d)=(a+b)·…….)

Esempi: 2³+1= 9 è composto, 2⁵+ 1 =33 è composto, e così via.

Invece

sono tutti primi

Notazione: chiamiamo F(n)= n-simo numero di Fermat

Congettura ( Fermat ): F (n) è primo per ogni n.

Eulero ha dimostrato che F(5) = 641· 6700417 è composto.

• i primi di Fermat conosciuti sono ancora F(n) per n ≤4 ,
• 5 ≤ n ≤30 ⇒ F(n) è composto,
• 5 ≤ n ≤ 11 ⇒ è nota la decomposizione in fattori primi.
• per n = 14, 20, 22, 24 : non si conosce alcun fattore primo di F(n) ,
• per gli altri valori di n ≤30 : noto qualche fattore primo, non la decomposizione.

Numeri di Mersenne (1588-1648)

Stavolta consideriamo i predecessori delle potenze di 2:

0, 1, 3, 8, 15, ….,2^m -1,….

Trascuriamo 0 e 1, dunque supponiamo m>1.

Osserviamo: se m è composto, cioè m= d·d′, anche 2^m -1 è composto.

2^m-1 = (2^d’)^d-1^d = (2^d’-1)·…..

Esempi: 2⁴-1= 15 è composto.

Invece se m è primo, non è detto che 2^m -1 sia primo.

Notazione: chiamiamo M(m)= 2^m -1 m-simo numero di Mersenne

Si trovano primi di Mersenne:

• M(13) Eulero 1722
• M(127) Lucas 1876
• M(216091) Slowiski 1987
• M(20996011 ) Shafer 2003
• M(24036583) Findley 2004
• M (25964951) Nowack 2005
• ………………..si ipotizza che i primi di Mersenne siano infiniti!

• Nel 1903 Frank Nelson Cole, professore di matematica alla Columbia University Di New York, tenne una conferenza assai curiosa. Senza pronunciare una parola, Cole scrisse uno dei numeri di Mersenne alla lavagna.  Vicino a questo scrisse due numeri più piccoli e li moltiplicò. In mezzo mise un segno di uguaglianza e si sedette.
  
  2⁶⁷-1 = 193707721 · 761838257287
  
  Il pubblico si alzò in piedi ad applaudirlo.
  Già dal 1876 si sapeva che 2⁶⁷-1, un numero di Mersenne di 28 cifre, non era un numero primo ma nessuno era riuscito a scomporlo.

• Oggi esiste un programma GIMPS che coordina l’attività di chi vuole scoprire i primi di Mersenne e mette a disposizione un software
  
  
• Al momento l’ultimo primo di Mersenne identificato è:
  M (30402457) Curtis Cooper e Steven Boone 03-01-2006 (ha 9 milioni di cifre decimali)