Aritmetica modulare, numeri primi e crittografia
Alberto Canonaco
Universita di Pavia
14 Giugno 2016
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Numeri primi
DefinizioneUn intero n > 1 e un numero primo se non esistono due interia, b > 1 tali che n = ab.
Sono dunque numeri primi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, . . .
Teorema fondamentale dell’aritmeticaOgni intero n > 1 si puo scrivere, in modo unico a menodell’ordine, come prodotto di numeri primi.
Esempio
140 = 2 · 7 · 5 · 2 = 5 · 2 · 2 · 7 = · · ·Di solito si scrive 140 = 22 · 5 · 7.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Alcune proprieta dei numeri primi
TeoremaI numeri primi sono infiniti.
Si sa molto di piu sulla distribuzione dei numeri primi.In particolare, il cosiddetto teorema dei numeri primi afferma che inumeri primi fino a n sono (in un senso che si puo renderematematicamente rigoroso) “circa” n
log(n) .
Esempio
I numeri primi fino a un miliardo sono 50847534, mentre
1000000000
log(1000000000)= 48254942, 43
D’altra parte non si conoscono risultati generali che permettano dideterminare facilmente se un dato numero e primo.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Il problema della fattorizzazione
Dato un intero n > 1 come posso stabilire se n e primo? Nel casoche non lo sia, come posso trovare la sua fattorizzazione?E facile fornire un algoritmo che risolve entrambi i problemi:
1. d = 2
2. se d >√n, allora n e primo (fine!)
3. se d - n (d non divide n), sostituisco d + 1 a d e torno alpunto 2
4. se d | n (d divide n), allora n non e primo, d e un suo fattoreprimo e riapplico l’algoritmo con n
d (< n) al posto di n
OsservazioneNel caso peggiore (cioe quando n e primo), l’algoritmo richiedecirca
√n passi. Il suo tempo e quindi esponenziale come funzione
del numero di cifre di n (che e circa log(n)).
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Efficienza degli algoritmi
Esistono algoritmi molto piu veloci (e complicati...).
I In particolare si puo sempre fattorizzare n in temposubesponenziale, ma non polinomiale (almeno allo statoattuale delle conoscenze).
I E invece possibile stabilire in tempo polinomiale se n e primoo no: anche se questo e stato dimostrato rigorosamente solonel 2002 da Agrawal, Kayal e Saxena, erano gia noti deglialgoritmi che in pratica funzionano in tempo polinomiale.
I Inoltre esistono dei test di primalita probabilistici moltosemplici e ancora piu veloci, che sono sicuri se indicano che nnon e primo e altrimenti permettono di concludere solo che ne molto probabilmente primo.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Conseguenze
In pratica un computer puo trovare velocemente (in pochi minuti)dei numeri primi anche di parecchie centinaia di cifre, mentre ingenerale impiegherebbe un tempo enormemente maggiore perfattorizzare un numero della stessa grandezza.
Il caso che richiede piu tempo e quello in cui n = pq con p e qnumeri primi circa della stessa grandezza (ma non troppo vicini escelti con alcune altre accortezze).
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
RSA-768
Un normale pc impiegherebbe almeno mille anni per fattorizzare
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
=33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
RSA-768
Un normale pc impiegherebbe almeno mille anni per fattorizzare
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
=33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Crittografia
Scopo della crittografia e di trasformare un messaggio rendendoloincomprensibile a chiunque, tranne a chi e autorizzato a leggerlo.
Ci sono essenzialmente due tipi di crittografia:
I la crittografia simmetrica, in cui un’unica chiave (nota solo amittente e destinatario) permette di crittare e decrittare ilmessaggio;
I la crittografia asimmetrica, in cui si usa una chiave pubblica(nota a tutti) per crittare il messaggio e una chiave privata(nota solo al destinatario) per decrittarlo.
Uno dei primi sistemi di crittografia asimmetrica fu inventato nel1977 da Rivest, Shamir e Adleman, basandosi proprio sulla facilitadi trovare due numeri primi grandi e sulla difficolta di fattorizzarneil prodotto.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Crittografia
Scopo della crittografia e di trasformare un messaggio rendendoloincomprensibile a chiunque, tranne a chi e autorizzato a leggerlo.Ci sono essenzialmente due tipi di crittografia:
I la crittografia simmetrica, in cui un’unica chiave (nota solo amittente e destinatario) permette di crittare e decrittare ilmessaggio;
I la crittografia asimmetrica, in cui si usa una chiave pubblica(nota a tutti) per crittare il messaggio e una chiave privata(nota solo al destinatario) per decrittarlo.
Uno dei primi sistemi di crittografia asimmetrica fu inventato nel1977 da Rivest, Shamir e Adleman, basandosi proprio sulla facilitadi trovare due numeri primi grandi e sulla difficolta di fattorizzarneil prodotto.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Crittografia
Scopo della crittografia e di trasformare un messaggio rendendoloincomprensibile a chiunque, tranne a chi e autorizzato a leggerlo.Ci sono essenzialmente due tipi di crittografia:
I la crittografia simmetrica, in cui un’unica chiave (nota solo amittente e destinatario) permette di crittare e decrittare ilmessaggio;
I la crittografia asimmetrica, in cui si usa una chiave pubblica(nota a tutti) per crittare il messaggio e una chiave privata(nota solo al destinatario) per decrittarlo.
Uno dei primi sistemi di crittografia asimmetrica fu inventato nel1977 da Rivest, Shamir e Adleman, basandosi proprio sulla facilitadi trovare due numeri primi grandi e sulla difficolta di fattorizzarneil prodotto.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Crittografia
Scopo della crittografia e di trasformare un messaggio rendendoloincomprensibile a chiunque, tranne a chi e autorizzato a leggerlo.Ci sono essenzialmente due tipi di crittografia:
I la crittografia simmetrica, in cui un’unica chiave (nota solo amittente e destinatario) permette di crittare e decrittare ilmessaggio;
I la crittografia asimmetrica, in cui si usa una chiave pubblica(nota a tutti) per crittare il messaggio e una chiave privata(nota solo al destinatario) per decrittarlo.
Uno dei primi sistemi di crittografia asimmetrica fu inventato nel1977 da Rivest, Shamir e Adleman, basandosi proprio sulla facilitadi trovare due numeri primi grandi e sulla difficolta di fattorizzarneil prodotto.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Divisione con resto
TeoremaDati due interi a e n con n > 0, esistono unici due altri interi q e r(detti quoziente e resto della divisione di a per n) tali che
I a = qn + r
I 0 ≤ r < n
Il resto della divisione di a per n si chiama a modulo n e si indica
a mod n
Chiaramente a mod n = 0 se e solo se n | a.
Esempio
Se n = 10 e a ≥ 0, q si ottiene da a cancellando l’ultima cifra,mentre r e proprio l’ultima cifra di a (scritto come al solito in base10). Quindi, per esempio, 216 = 21× 10 + 6 e 216 mod 10 = 6.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo RSA
Preliminarmente il destinatario
I sceglie (opportunamente) due numeri primi p e q
I calcola n := pq
I calcola m := mcm(p − 1, q − 1)
I sceglie un intero 1 < c < m tale che mcd(c,m) = 1
I trova un intero 0 ≤ d < m tale che (cd) mod m = 1
I divulga n e c (la chiave pubblica), mentre tiene segretip, q, m e d (la chiave privata)
Per mandare un intero 0 ≤ a < n (ogni messaggio si puotrasformare in questa forma, eventualmente spezzandolo)il mittente
I calcola b := ac mod n e manda b
Infine il destinatario
I calcola bd mod n (= a)
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Sicurezza dell’algoritmo RSA
La sicurezza dell’algoritmo dipende da alcune assunzioni su cui nonci sono certezze, ma che sembrano molto plausibili grazie ainumerosi esperti che hanno studiato (e continuano a studiare) laquestione. In particolare non deve essere possibile risolverevelocemente nessuno dei seguenti problemi:
I fattorizzare n
I trovare d conoscendo solo n e c
I trovare a conoscendo solo n, c e b
D’altra parte e noto che vanno prese alcune precauzioni tecnichetra cui evitare che a assuma valori particolari per i quali l’ultimoproblema si risolve facilmente.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Aritmetica modulare
Dati degli interi a, a′ e n con n > 0, si vede subito che
a mod n = a′ mod n ⇐⇒ n | (a′ − a)
Proposizione
Se a mod n = a′ mod n e b mod n = b′ mod n, allora
(a + b) mod n = (a′ + b′) mod n
(ab) mod n = (a′b′) mod n
Dimostrazione.Se a′ − a = cn e b′ − b = dn, si trova
(a′ + b′)− (a + b) = (c + d)n
a′b′ − ab = (cdn + bc + ad)n
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Aritmetica modulare
Dati degli interi a, a′ e n con n > 0, si vede subito che
a mod n = a′ mod n ⇐⇒ n | (a′ − a)
Proposizione
Se a mod n = a′ mod n e b mod n = b′ mod n, allora
(a + b) mod n = (a′ + b′) mod n
(ab) mod n = (a′b′) mod n
Dimostrazione.Se a′ − a = cn e b′ − b = dn, si trova
(a′ + b′)− (a + b) = (c + d)n
a′b′ − ab = (cdn + bc + ad)n
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Esponenziale modulare
Per calcolare ak mod n (con k > 0) non e necessario calcolare ak .Se k > 1, posso scrivere k = k1 + k2 on 0 < k1, k2 < k. Essendo
ak = ak1+k2 = ak1ak2 ,
se so calcolare ai := aki mod n, allora
ak mod n = (a1a2) mod n.
Scegliendo k1 = k − 1 e k2 = 1 se k e dispari e k1 = k2 = k2 se k e
pari, se ne deduce induttivamente che posso calcolare ak mod ncon circa log(k) moltiplicazioni modulari, dunque in tempopolinomiale se k < n.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Massimo comun divisore e minimo comune multiplo
DefinizioneDati due interi a, b > 0 si definiscono
mcd(a, b) := max{k : k | a, k | b}mcm(a, b) := min{k > 0 : a | k , b | k}
Osservazione
I Se sono note le fattorizzazioni di a e di b, si calcolanofacilmente mcd(a, b) e mcm(a, b). Inoltre
mcm(a, b) =ab
mcd(a, b)
I Si definisce allo stesso modo mcd(a, 0) e risulta mcd(a, 0) = a(perche k | 0 per ogni k).
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo di Euclide
Se a ≥ b > 0, per calcolare mcd(a, b) pongo
r1 := a, r2 := b.
Poi definiscor3 := r1 mod r2
e induttivamente, se ri > 0,
ri+1 := ri−1 mod ri
Dato che ri+1 < ri , esiste j tale che
rj 6= 0 e rj+1 = 0
Alloramcd(a, b) = rj .
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo di Euclide
Se a ≥ b > 0, per calcolare mcd(a, b) pongo
r1 := a, r2 := b.
Poi definiscor3 := r1 mod r2
e induttivamente, se ri > 0,
ri+1 := ri−1 mod ri
Dato che ri+1 < ri , esiste j tale che
rj 6= 0 e rj+1 = 0
Alloramcd(a, b) = rj .
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo di Euclide
Se a ≥ b > 0, per calcolare mcd(a, b) pongo
r1 := a, r2 := b.
Poi definiscor3 := r1 mod r2
e induttivamente, se ri > 0,
ri+1 := ri−1 mod ri
Dato che ri+1 < ri , esiste j tale che
rj 6= 0 e rj+1 = 0
Alloramcd(a, b) = rj .
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo di Euclide
Se a ≥ b > 0, per calcolare mcd(a, b) pongo
r1 := a, r2 := b.
Poi definiscor3 := r1 mod r2
e induttivamente, se ri > 0,
ri+1 := ri−1 mod ri
Dato che ri+1 < ri , esiste j tale che
rj 6= 0 e rj+1 = 0
Alloramcd(a, b) = rj .
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Algoritmo di Euclide
Se a ≥ b > 0, per calcolare mcd(a, b) pongo
r1 := a, r2 := b.
Poi definiscor3 := r1 mod r2
e induttivamente, se ri > 0,
ri+1 := ri−1 mod ri
Dato che ri+1 < ri , esiste j tale che
rj 6= 0 e rj+1 = 0
Alloramcd(a, b) = rj .
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Dimostrazione
Dato 2 ≤ i ≤ j , per definizione esiste un intero qi tale cheri−1 = qi ri + ri+1. Allora
mcd(ri−1, ri ) = mcd(qi ri + ri+1, ri ) = mcd(ri+1, ri )
(perche k | ri+1 e k | ri se e solo se k | (qi ri + ri+1) e k | ri ).Dunque
mcd(a, b) = mcd(r1, r2) = mcd(r2, r3) = · · ·= mcd(rj , rj+1) = mcd(rj , 0) = rj
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Ulteriori proprieta
I Poiche ri+1 < ri < ri−1, deve essere qi > 0, e quindi
ri−1 = qi ri + ri+1 ≥ ri + ri+1 > 2ri+1
Ne segue che l’algoritmo di Euclide richiede circa log(a) passi,e dunque un tempo polinomiale se a < n.
I Inoltre, partendo da rj e sostituendo ricorsivamente ri+1 conri−1 − qi ri , si possono trovare (sempre in tempo polinomiale)due interi x e y tali che
ax + by = mcd(a, b).
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Esempio
a = r1 = 91, b = r2 = 35
91 = 2 · 35 + 21 (q2 = 2, r3 = 21)
35 = 21 + 14 (q3 = 1, r4 = 14)
21 = 14 + 7 (q4 = 1, r5 = 7)
14 = 2 · 7 + 0 (q5 = 2, r6 = 0)
Dunque j = 5 e mcd(91, 35) = r5 = 7. Inoltre
7 = 21− 14
= 21− (35− 21) = 2 · 21− 35
= 2 · (91− 2 · 35)− 35 = 2 · 91− 5 · 35
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Efficienza dell’algoritmo RSA
Osserviamo che tutti i calcoli richiesti dall’algoritmo possono esseresvolti velocemente (in particolare, in tempo polinomiale):
I Gia detto che si possono trovare i primi p e q (e ovviamentecalcolare n := pq).
I Con l’algoritmo di Euclide si calcola
m := mcm(p − 1, q − 1) =(p − 1)(q − 1)
mcd(p − 1, q − 1)
e si trova 1 < c < m tale che mcd(c ,m) = 1.
I Inoltre si trovano due interi x e y tali che cx + my = 1.Dunque (cx) mod m = 1 e allora d := x mod m verifica0 ≤ d < m e (cd) mod m = 1.
I Con l’esponenziale modulare si calcolano b := ac mod n ebd mod n.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Efficienza dell’algoritmo RSA
Osserviamo che tutti i calcoli richiesti dall’algoritmo possono esseresvolti velocemente (in particolare, in tempo polinomiale):
I Gia detto che si possono trovare i primi p e q (e ovviamentecalcolare n := pq).
I Con l’algoritmo di Euclide si calcola
m := mcm(p − 1, q − 1) =(p − 1)(q − 1)
mcd(p − 1, q − 1)
e si trova 1 < c < m tale che mcd(c ,m) = 1.
I Inoltre si trovano due interi x e y tali che cx + my = 1.Dunque (cx) mod m = 1 e allora d := x mod m verifica0 ≤ d < m e (cd) mod m = 1.
I Con l’esponenziale modulare si calcolano b := ac mod n ebd mod n.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Efficienza dell’algoritmo RSA
Osserviamo che tutti i calcoli richiesti dall’algoritmo possono esseresvolti velocemente (in particolare, in tempo polinomiale):
I Gia detto che si possono trovare i primi p e q (e ovviamentecalcolare n := pq).
I Con l’algoritmo di Euclide si calcola
m := mcm(p − 1, q − 1) =(p − 1)(q − 1)
mcd(p − 1, q − 1)
e si trova 1 < c < m tale che mcd(c ,m) = 1.
I Inoltre si trovano due interi x e y tali che cx + my = 1.Dunque (cx) mod m = 1 e allora d := x mod m verifica0 ≤ d < m e (cd) mod m = 1.
I Con l’esponenziale modulare si calcolano b := ac mod n ebd mod n.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Efficienza dell’algoritmo RSA
Osserviamo che tutti i calcoli richiesti dall’algoritmo possono esseresvolti velocemente (in particolare, in tempo polinomiale):
I Gia detto che si possono trovare i primi p e q (e ovviamentecalcolare n := pq).
I Con l’algoritmo di Euclide si calcola
m := mcm(p − 1, q − 1) =(p − 1)(q − 1)
mcd(p − 1, q − 1)
e si trova 1 < c < m tale che mcd(c ,m) = 1.
I Inoltre si trovano due interi x e y tali che cx + my = 1.Dunque (cx) mod m = 1 e allora d := x mod m verifica0 ≤ d < m e (cd) mod m = 1.
I Con l’esponenziale modulare si calcolano b := ac mod n ebd mod n.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Caratterizzazione dei numeri primi
Proposizione
Sia p un numero primo e siano a e b due interi tali che p | (ab).Allora p | a o p | b.
Dimostrazione.Se p | b, OK. Altrimenti mcd(b, p) = 1, e dunque esistono x e ytali che bx + py = 1. Essendo ab = pk per qualche k, si trova
a = a(bx + py) = abx + apy = pkx + pay = p(kx + ay),
il che dimostra che p | a.
OsservazioneCon questo si dimostra il teorema fondamentale dell’aritmetica.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Teorema cinese del resto
Siano n1 e n2 due interi positivi tali che mcd(n1, n2) = 1. Dati0 ≤ a1 < n1 e 0 ≤ a2 < n2, esiste unico 0 ≤ a < n1n2 tale che{
a mod n1 = a1
a mod n2 = a2
Dimostrazione.Dato che sia a che (a1, a2) possono assumere n1n2 valori, bastadimostrare l’unicita della soluzione.Se a e a′ sono due soluzioni del sistema, allora n1 | (a′ − a) en2 | (a′ − a). Questo implica che
mcm(n1, n2) =n1n2
mcd(n1, n2)= n1n2 | (a′ − a),
e quindi a′ = a perche 0 ≤ a, a′ < n1n2.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Teorema cinese del resto
Siano n1 e n2 due interi positivi tali che mcd(n1, n2) = 1. Dati0 ≤ a1 < n1 e 0 ≤ a2 < n2, esiste unico 0 ≤ a < n1n2 tale che{
a mod n1 = a1
a mod n2 = a2
Dimostrazione.Dato che sia a che (a1, a2) possono assumere n1n2 valori, bastadimostrare l’unicita della soluzione.Se a e a′ sono due soluzioni del sistema, allora n1 | (a′ − a) en2 | (a′ − a). Questo implica che
mcm(n1, n2) =n1n2
mcd(n1, n2)= n1n2 | (a′ − a),
e quindi a′ = a perche 0 ≤ a, a′ < n1n2.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Piccolo teorema di Fermat
Sia p un numero primo e a un intero tale che a mod p 6= 0. Allora
ap−1 mod p = 1
OsservazioneQuesto teorema fornisce un criterio molto veloce per vedere se unintero n > 1 non e primo: scelto 0 < a < n, se an−1 mod n 6= 1,sicuramente n non e primo.Se invece an−1 mod n = 1, non si puo concludere che n e primo,ma una semplice variante di questo criterio (ripetuto per unnumero abbastanza grande di valori di a) permette di sapere che ne molto probabilmente primo.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Piccolo teorema di Fermat
Sia p un numero primo e a un intero tale che a mod p 6= 0. Allora
ap−1 mod p = 1
OsservazioneQuesto teorema fornisce un criterio molto veloce per vedere se unintero n > 1 non e primo: scelto 0 < a < n, se an−1 mod n 6= 1,sicuramente n non e primo.Se invece an−1 mod n = 1, non si puo concludere che n e primo,ma una semplice variante di questo criterio (ripetuto per unnumero abbastanza grande di valori di a) permette di sapere che ne molto probabilmente primo.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Dimostrazione
Per i = 0, 1, . . . , p − 1 sia ai := (ai) mod p. Se ai = aj , allora
p | (ai − aj) = a(i − j)
Per ipotesi p - a, dunque p | (i − j). Dato che 0 ≤ i , j < p, questoimplica i = j . Visto che a0 = 0, ne segue che
{a1, . . . , ap−1} = {1, . . . , p − 1}
Posto r := 1 · · · (p− 1), si ha ap−1r = a(2a) · · · ((p− 1)a), e quindi
(ap−1r) mod p = (a1 · · · ap−1) mod p = r mod p
Pertanto p | (ap−1r − r) = r(ap−1 − 1), e, tenendo conto che p - r(perche p - i per 0 < i < p), si ottiene p | (ap−1 − 1), da cui sideduce subito ap−1 mod p = 1.
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Correttezza dell’algoritmo RSA
p e q primi distinti, n := pq, m := mcm(p− 1, q− 1), c, d > 0 taliche (cd) mod m = 1. Devo dimostrare che dato 0 ≤ a < n e postob := ac mod n, vale bd mod n = a.
Essendo bd mod n = (ac)d mod n = acd mod n, devo quindidimostrare acd mod n = a, che per il teorema cinese equivale a{
acd mod p = a mod p
acd mod q = a mod q
Per simmetria basta dimostrare la prima uguaglianza.Se a mod p = 0, anche acd mod p = 0.Se a mod p 6= 0, osservo che cd = 1 + (p − 1)k per qualche k(perche (cd) mod m = 1 e (p − 1) | m), e quindi acd = a(ap−1)k .Usando il piccolo teorema di Fermat concludo che
acd mod p = (a(ap−1)k) mod p = (a · 1k) mod p = a mod p
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Correttezza dell’algoritmo RSA
p e q primi distinti, n := pq, m := mcm(p− 1, q− 1), c, d > 0 taliche (cd) mod m = 1. Devo dimostrare che dato 0 ≤ a < n e postob := ac mod n, vale bd mod n = a.Essendo bd mod n = (ac)d mod n = acd mod n, devo quindidimostrare acd mod n = a, che per il teorema cinese equivale a{
acd mod p = a mod p
acd mod q = a mod q
Per simmetria basta dimostrare la prima uguaglianza.Se a mod p = 0, anche acd mod p = 0.Se a mod p 6= 0, osservo che cd = 1 + (p − 1)k per qualche k(perche (cd) mod m = 1 e (p − 1) | m), e quindi acd = a(ap−1)k .Usando il piccolo teorema di Fermat concludo che
acd mod p = (a(ap−1)k) mod p = (a · 1k) mod p = a mod p
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Correttezza dell’algoritmo RSA
p e q primi distinti, n := pq, m := mcm(p− 1, q− 1), c, d > 0 taliche (cd) mod m = 1. Devo dimostrare che dato 0 ≤ a < n e postob := ac mod n, vale bd mod n = a.Essendo bd mod n = (ac)d mod n = acd mod n, devo quindidimostrare acd mod n = a, che per il teorema cinese equivale a{
acd mod p = a mod p
acd mod q = a mod q
Per simmetria basta dimostrare la prima uguaglianza.
Se a mod p = 0, anche acd mod p = 0.Se a mod p 6= 0, osservo che cd = 1 + (p − 1)k per qualche k(perche (cd) mod m = 1 e (p − 1) | m), e quindi acd = a(ap−1)k .Usando il piccolo teorema di Fermat concludo che
acd mod p = (a(ap−1)k) mod p = (a · 1k) mod p = a mod p
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Correttezza dell’algoritmo RSA
p e q primi distinti, n := pq, m := mcm(p− 1, q− 1), c, d > 0 taliche (cd) mod m = 1. Devo dimostrare che dato 0 ≤ a < n e postob := ac mod n, vale bd mod n = a.Essendo bd mod n = (ac)d mod n = acd mod n, devo quindidimostrare acd mod n = a, che per il teorema cinese equivale a{
acd mod p = a mod p
acd mod q = a mod q
Per simmetria basta dimostrare la prima uguaglianza.Se a mod p = 0, anche acd mod p = 0.
Se a mod p 6= 0, osservo che cd = 1 + (p − 1)k per qualche k(perche (cd) mod m = 1 e (p − 1) | m), e quindi acd = a(ap−1)k .Usando il piccolo teorema di Fermat concludo che
acd mod p = (a(ap−1)k) mod p = (a · 1k) mod p = a mod p
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia
Correttezza dell’algoritmo RSA
p e q primi distinti, n := pq, m := mcm(p− 1, q− 1), c, d > 0 taliche (cd) mod m = 1. Devo dimostrare che dato 0 ≤ a < n e postob := ac mod n, vale bd mod n = a.Essendo bd mod n = (ac)d mod n = acd mod n, devo quindidimostrare acd mod n = a, che per il teorema cinese equivale a{
acd mod p = a mod p
acd mod q = a mod q
Per simmetria basta dimostrare la prima uguaglianza.Se a mod p = 0, anche acd mod p = 0.Se a mod p 6= 0, osservo che cd = 1 + (p − 1)k per qualche k(perche (cd) mod m = 1 e (p − 1) | m), e quindi acd = a(ap−1)k .Usando il piccolo teorema di Fermat concludo che
acd mod p = (a(ap−1)k) mod p = (a · 1k) mod p = a mod p
Alberto Canonaco Aritmetica modulare, numeri primi e crittografia