Crittografia e numeri primi V incontro lunedì 13 dicembre 2010 Piano Lauree Scientifiche.
50
Crittografia e numeri primi V incontro lunedì 13 dicembre 2010 Piano Lauree Scientifiche
-
Upload
gioia-rota -
Category
Documents
-
view
221 -
download
3
Transcript of Crittografia e numeri primi V incontro lunedì 13 dicembre 2010 Piano Lauree Scientifiche.
Crittografia e numeri primi
V incontrolunedì 13 dicembre 2010
Piano Lauree Scientifiche
Un messaggio può essere cifrato utilizzando una permutazione dell’alfabeto (e di eventuali altri caratteri).
Il Codice Cesare cifra utilizzando una cifratura per traslazionedel tipo
: |[ ] [ '] [ ] [ ]n nf Z Z m m m a
Questa cifratura è molto semplice da decifrare poiché è sufficiente determinare lo spostamento di una lettera per ottenere di conseguenza tutti gli altri.
Qualsiasi valore dello spostamento 0 < [a] < n va bene.
Cifrare con l’addizione
Un’altra permutazione dell’alfabeto può essere ottenuta utilizzandola funzione moltiplicativa
: |[ ] [ '] [ ] [ ]n nf Z Z m m a m
La funzione f è però una funzione di cifratura se e solo se [a] è invertibile in Zn e…
[a] è invertibile in Zn se e solo se MCD(a, n) = 1
La funzione di decifratura è:
Cifrare con la moltiplicazione
1 1 1: |[ '] [ ] [ ] [ '] [ ] [ ] [1]n nf Z Z m m a m a a
Una ulteriore permutazione dell’alfabeto può essere ottenuta utilizzando
la potenza
Esiste sempre un esponente corretto da usare per ottenere una cifratura?
In caso positivo, come può essere individuato?
Cifrare con la potenza
f : Zn Zn / [m] | [m’] = [mt] con t N0
Come decifrare?
0 1 2 3 4 5 6
x 0 1 2 3 4 5 6
x2
x3
x4
x5
x6
x7
x8
x9
x10
Completa, in Z7, la tabella dei valori corrispondenti delle potenze di x:
L’elevamento al quadrato è una cifratura?
E se uso un esponente pari?
I valori di m per i quali la funzione fm è una funzione di
cifratura sono:
Ci sono due esponenti diversi m e k per i quali le funzioni
fm e fk coincidono? Se sì, quali?
0 1 2 3 4 5 6
x11 0 1 2 3 4 5 6
x12
x13
x14
x15
Saresti in grado di completare, in Z7, la tabella seguente senza fare conti?
Dopo quanti passi le funzioni si ripetono?
Potenze modulo 7
base1 2 3 4 5 6
esponente
2 1 4 2 2 4 13 1 1 6 1 6 64 1 2 4 4 2 15 1 4 5 2 3 66 1 1 1 1 1 17 1 2 3 4 5 68 1 4 2 2 4 19 1 1 6 1 6 6
10 1 2 4 4 2 111 1 4 5 2 3 612 1 1 1 1 1 113 1 2 3 4 5 6
x x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1
3 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6
4 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1
5 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6
6 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6
Potenze in Z7 Tav. 5.1
Potenze in Z11 Tav. 5.2
Le potenze si ripetono in modo periodico.
Utilizzando la tavola appena completata, prova a
completare, in Z11, le seguenti uguaglianze:
317= 3.... = ...… 524= 5.... = ……
899= 8.... = ……
Completa, in Z11, le seguenti uguaglianze:
(67).... = 6 (23).... = 2 (89).... = 8
Cifrare e decifrare con Fermat – Tav. 5.2
ap-1=1 mod p
a k(p-1)=1 mod p
ak(p-1)+1=a mod p
Cifratura: a → a’=ae
Decifratura: a’ → a=(ae)d
k(p-1)+1=ed → k(p-1)=ed-1 → ed=1 mod(p-1)
aed =a mod p
Tabella moltiplicazione modulo 10
* 0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 0 2 4 6 83 0 3 6 9 2 5 8 1 4 74 0 4 8 2 6 0 4 8 2 65 0 5 0 5 0 5 0 5 0 56 0 6 2 8 4 0 6 2 8 47 0 7 4 1 8 5 2 9 6 38 0 8 6 4 2 0 8 6 4 29 0 9 8 7 6 5 4 3 2 1
Tav. 5.3
Tav. 5.3
* 0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 9 102 0 2 4 6 8 10 1 3 5 7 93 0 3 6 9 1 4 7 10 2 5 84 0 4 8 1 5 9 2 6 10 3 75 0 5 10 4 9 3 8 2 7 1 66 0 6 1 7 2 8 3 9 4 10 57 0 7 3 10 6 2 9 5 1 8 48 0 8 5 2 10 7 4 1 9 6 39 0 9 7 5 3 1 10 8 6 4 2
10 0 10 9 8 7 6 5 4 3 2 1
ed=1 mod(p-1)
Tav. 5.3
Potenze in Z10
x x2 x3 x4 x5 x6 x7 x8 x9 x10
0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 1 1 12 2 4 8 6 2 4 8 6 2 43 3 9 7 1 3 9 7 1 3 94 4 6 4 6 4 6 4 6 4 65 5 5 5 5 5 5 5 5 5 56 6 6 6 6 6 6 6 6 6 67 7 9 3 1 7 9 3 1 7 98 8 4 2 6 8 4 2 6 8 49 9 1 9 1 9 1 9 1 9 1
Modulo 10
4
4
4
3 1
7 1
9 1
( 1)( 1) 1 (mod ) ( , ) 1p qa n n p q MCD a n
Teorema di Eulero – Tav. 5.4
10 2 5 2; 5
( 1)( 1) (2 1)(5 1) 1 4 4
n p q
p q
x x^2 x^3 x^4 x^5 x^6 x^7 x^8 x^9 x^10 x^11 x^12 x^13 x^14 x^15 x^16 x^17 x^18 x^19 x^200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 2 4 8 16 11 1 2 4 8 16 11 1 2 4 8 16 11 1 2 43 3 9 6 18 12 15 3 9 6 18 12 15 3 9 6 18 12 15 3 94 4 16 1 4 16 1 4 16 1 4 16 1 4 16 1 4 16 1 4 165 5 4 20 16 17 1 5 4 20 16 17 1 5 4 20 16 17 1 5 46 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 157 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 78 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 19 9 18 15 9 18 15 9 18 15 9 18 15 9 18 15 9 18 15 9 18
10 10 16 13 4 19 1 10 16 13 4 19 1 10 16 13 4 19 1 10 1611 11 16 8 4 2 1 11 16 8 4 2 1 11 16 8 4 2 1 11 1612 12 18 6 9 3 15 12 18 6 9 3 15 12 18 6 9 3 15 12 1813 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 114 14 7 14 7 14 7 14 7 14 7 14 7 14 7 14 7 14 7 14 715 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 1516 16 4 1 16 4 1 16 4 1 16 4 1 16 4 1 16 4 1 16 417 17 16 20 4 5 1 17 16 20 4 5 1 17 16 20 4 5 1 17 1618 18 9 15 18 9 15 18 9 15 18 9 15 18 9 15 18 9 15 18 919 19 4 13 16 10 1 19 4 13 16 10 1 19 4 13 16 10 1 19 420 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1
Potenze in Z21
Teorema di Eulero – Tav. 5.5
Teorema di Eulero
( 1)( 1) 1 (mod ) ( , ) 1p qa n n p q MCD a n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20X^2 0 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1X^3 0 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 20X^4 0 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 1X^5 0 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 20X^6 0 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 1X^7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20X^8 0 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1X^9 0 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 20
X^10 0 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 1X^11 0 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 20X^12 0 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 1X^13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20X^14 0 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1X^15 0 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 20X^16 0 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 1X^17 0 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 20X^18 0 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 1X^19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20X^20 0 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1
Potenze in Z21
21=3*7 (3-1)(7-1)=12
Completa, in Z10, la tabella dei valori corrispondenti delle potenze di x:
Ricapitoliamo
Potenze modulo 7
base1 2 3 4 5 6
esponente
2 1 4 2 2 4 13 1 1 6 1 6 64 1 2 4 4 2 15 1 4 5 2 3 66 1 1 1 1 1 17 1 2 3 4 5 68 1 4 2 2 4 19 1 1 6 1 6 6
10 1 2 4 4 2 111 1 4 5 2 3 612 1 1 1 1 1 113 1 2 3 4 5 6
Potenze modulo 10
p = 2
q = 5
n = 2 5 = 10
(p – 1)(q – 1) = (2 – 1)(5 – 1) = 1 4 = 4
14 1
34 1
74 1
94 1
base
1 2 3 4 5 6 7 8 9
esponente
2 1 4 9 6 5 6 9 4 1
3 1 8 7 4 5 6 3 2 9
4 1 6 1 6 5 6 1 6 1
5 1 2 3 4 5 6 7 8 9
Potenze modulo 10
Potenze modulo 21
p = 3
q = 7
n = 3 7 = 21
(p – 1)(q – 1) = (3 – 1)(7 – 1) = 2 6 = 12
112 1
212 1
412 1
512 1
812 1
1012 1
1112 1
1312 1
1612 1
1712 1
1912 1
2012 1
base1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
esponente
2 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 13 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 204 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 15 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 206 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 208 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 19 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 20
10 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 111 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 2012 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 113 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2014 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 115 1 8 6 1 20 6 7 8 15 13 8 6 13 14 15 1 20 15 13 2016 1 16 18 4 16 15 7 1 9 4 4 9 1 7 15 16 4 18 16 117 1 11 12 16 17 6 7 8 18 19 2 3 13 14 15 4 5 9 10 2018 1 1 15 1 1 15 7 1 15 1 1 15 1 7 15 1 1 15 1 119 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2020 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1
Corollario del teorema di Eulero
Se n = p q è prodotto di due numeri primi
distinti, allora a(p–1)(q–1)+1 a mod n
I casi possibili sono:
MCD (a, n) = 1
MCD (a, n) = p
MCD (a, n) = n
Se MCD (a, n) = 1
è possibile applicare il Teorema di Eulero
base
1 2 3 4 5 6 7 8 9
esponente
2 1 4 9 6 5 6 9 4 1
3 1 8 7 4 5 6 3 2 9
4 1 6 1 6 5 6 1 6 1
5 1 2 3 4 5 6 7 8 9
Potenze modulo 10
Se MCD (a, n) = p
p = 2 q = 5
n = 2 5 = 10
a = 4
MCD (4, 10) = 2
MCD (4, 5) = 1
è possibile applicare il Piccolo Teorema di Fermat
p, q numeri primi distinti
n = p q
MCD (a, q) = 1
44 1 mod 5a(q – 1) 1 mod q
Si ha infatti:
44 6e
6 1 mod 5
base
1 2 3 4 5 6 7 8 9
esponente
2 1 4 9 6 5 6 9 4 1
3 1 8 7 4 5 6 3 2 9
4 1 6 1 6 5 6 1 6 1
5 1 2 3 4 5 6 7 8 9
Si dovrà far vedere che se a(q – 1) 1 mod q,
allora a (q – 1) (p – 1) + 1 a mod q
elevando entrambi i membri alla (p – 1)
44 1 mod 5a(q – 1) 1 mod q
(aq – 1 ) (p – 1) 1 mod q
a (q – 1) (p – 1) 1 mod q
(44 )1 1 mod 5
44 1 mod 5
moltiplicando entrambi i membri per a
a (q – 1) (p – 1) + 1 a mod q 45 4 mod 5
Si dovrà far vedere che se a (q – 1) (p – 1) + 1 a mod q,
a (q – 1) (p – 1) + 1 a mod n
a ≡ b mod n (a – b) = n h per qualche h ⇔ ⋅ ∈ Z
a (q – 1) (p – 1) + 1 a mod q ⇔ a (q – 1) (p – 1) + 1 – a = q h per qualche h Z
dall’essere MCD (a, n) = p
a (q – 1) (p – 1) + 1 – a = q p k per qualche k Z
a (q – 1) (p – 1) + 1 – a = n k per qualche k Z
a (q – 1) (p – 1) + 1 a mod n
Se MCD (a, n) = n
allora a è multiplo di n
a 0 mod n
La tesi
a(p–1)(q–1)+1 a mod n
diviene allora
0 0 mod n
Osservazione
se per caso (p – 1)(q – 1) + 1 = e d,
allora aed = a (p - 1)(q – 1) + 1 = a mod n.
Ma aed = (ae)d
È dunque possibile usare l’elevamento alla potenza
con esponente e per cifrare e l’elevamento alla
potenza con esponente d per decifrare
Se
(p – 1)(q – 1) + 1 = e d,
allora
(p – 1)(q – 1) = e d – 1,
dunque
e d = 1 modulo (p – 1)(q – 1)
Le classi e, d sono inverse tra loro
modulo (p – 1)(q – 1)
Applicazione del corollario
p = 3 q = 7
n = 21
e = 5
17 | 175 = 5 mod 21
(p – 1)(q – 1) = 12
e d = 1 mod 12
5 d = 1 mod 12 d = 5
5 | 55 = 17 mod 21
Applicazione del corollario
p = 3 q = 7
n = 21
e = 11
12 | 1211 = 3 mod 21
(p – 1)(q – 1) = 12
e d = 1 mod 12
11 11 = 1 mod 12 d = 11
3 | 311 = 12 mod 21
La crittografia a chiave pubblica
Da sinistra verso destra:
Ralph Merkle
Martin Hellman
Whitfield Diffie
L'implementazione tramite algoritmo RSA
Da sinistra verso destra:
Adi Shamir
Ronald Rivest
Leonard Adleman
![locandina Fabrizio.ppt [modalità compatibilità ] · LAUREE SCIENTIFICHE — Università degli Studi di $4ena Q:lpartjmento dj Fisiça LAUREE SCIENTIFICHE 2010-2012 . Title: Microsoft](https://static.fdocumenti.com/doc/165x107/5fb123078f7c0027c50cc1e0/locandina-modalitf-compatibilitf-lauree-scientifiche-a-universit-degli.jpg)
