Piano Lauree Scientifiche
Crittografia e numeri primi
VI incontro
lunedì 20 dicembre 2010
Cifrare con la potenza
Una ulteriore permutazione dell’alfabeto può essere ottenuta utilizzando
la potenza
f : Zn  Zn / [m] | [m’] = [mt] con t  N0
Esiste sempre un esponente corretto da usare per ottenere una cifratura?
In caso positivo, come può essere individuato?
Come decifrare?
esponente
Potenze modulo 7
1
2
3
4
5
6
7
8
9
10
11
12
13
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
base
3
4
3
4
2
2
6
1
4
4
5
2
1
1
3
4
2
2
6
1
4
4
5
2
1
1
3
4
5
5
4
6
2
3
1
5
4
6
2
3
1
5
6
6
1
6
1
6
1
6
1
6
1
6
1
6
Dunque le potenze si ripetono ciclicamente, dopo p – 1 passi.
Piccolo teorema di Fermat
Se p è un numero primo ed a non è divisibile per p,
allora a p – 1  1 mod p
a k (p – 1) + 1  a mod p
Osservazione
Se per caso k(p – 1) + 1 = e d,
allora aed = ak(p – 1) + 1 = (a(p – 1))k  a = 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
a k (p – 1) + 1  a mod p
Completa le seguenti uguaglianze in Z7
(25)5 = 2
(67).... = 6
(55).... = 5
Completa le seguenti uguaglianze in Z11
(417)3 = 4
(27)…. = 2
(83).... = 8
Completa le seguenti uguaglianze in Z17
(33)11 = 3
(65).... = 6
(129).... = 12
a k (p – 1) + 1  a mod p
Completa le seguenti uguaglianze in Z7
(25)5 = 2
(67)7 = 6
(55)11 = 5
Completa le seguenti uguaglianze in Z11
(417)3 = 4
(27)3 = 2
(83)7 = 8
Completa le seguenti uguaglianze in Z17
(33)11 = 3
(65)13 = 6
(129)9 = 12
Potenze modulo 10
0
1
2
3
4
5
6
7
8
9
x
x2
x3
x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
0
1
2
3
4
5
6
7
8
9
0
1
4
9
6
5
6
9
4
1
0
1
8
7
4
5
6
3
2
9
0
1
6
1
6
5
6
1
6
1
0
1
2
3
4
5
6
7
8
9
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
Osservazione
se per caso k(p – 1)(q – 1) + 1 = e  d,
allora
aed = a k(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
k(p – 1)(q – 1) + 1 = e  d,
allora
k(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=2q=5
n = 10
e=3
8 | 83 = 2 mod 10
(p – 1)(q – 1) = 4
e  d = 1 mod 4
3  d = 1 mod 4  d = 3
2 | 23 = 8 mod 10
Applicazione del corollario
p=3q=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
Applicazione del corollario
p = 3 q = 11
n = 33
e=7
13 | 137 = 7 mod 21
(p – 1)(q – 1) = 20
e  d = 1 mod 20
7  3 = 1 mod 20  d = 3
7 | 73 = 13 mod 33
Completa la tabella delle potenze in Z33
chiaro a b c d e f g h i l m n o p q r s t u v z ' . ?
x
y = x^7
2 3 4 5 6 7 8 9 13 14 15 16 17 18 19 20 24 25 26 27 28 29 30 31
Utilizzando l’applicazione x  x7 come applicazione di cifratura,
cifra il seguente messaggio
r
e
s
p
i
r
a
p
i
a
n
o
Ricordando che il Corollario del Teorema di Eulero afferma che:
“Se n = p  q è prodotto di due numeri primi distinti, allora a(p – 1)(q – 1) + 1
 a mod n”,
determina l’esponente t tale che l’applicazione y  yt sia l’applicazione
inversa della precedente (cioè la funzione di decifratura):
t = __________
Di quali elementi ho bisogno per cifrare un messaggio
con la funzione elevamento a potenza?
Di quali elementi ho bisogno per decifrare un messaggio
cifrato con la funzione elevamento a potenza?
Come possiamo rendere la vita difficile a chiunque volesse decifrare
un nostro messaggio?
Numeri primi minori di 10.000
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
Dichiarazione della chiave pubblica:
Preparazione del messaggio:
Preparazione del messaggio:
a
00
n
13
b
01
o
14
c
02
p
15
d
03
q
16
e
04
r
17
f
05
s
18
g
06
t
19
h
07
u
20
i
08
v
21
j
09
x
22
k
10
w
23
l
11
y
24
m
12
z
25
Preparazione del messaggio:
Cifratura del messaggio:
f : Z1003  Z1003 | mi  ci   mi 
3
Cifratura del messaggio:
f : Z1003  Z1003 | mi  ci   mi 
3
Decifratura del messaggio:
Calcolo della chiave
f
1

: Z n  Z n | ci  mi   ci    mi 
cd  1 mod( p  1)(q  1)
pq  n
d

c d
 mi
Decifratura del messaggio:
Calcolo della chiave

f 1 : Z1003  Z1003 | ci  mi   ci    mi 
d
3d  1 mod( p  1)(q  1) 
1003  17  59
pq  1003

p  17 q  59
( p  1)(q  1)  16  58  928
3

d
 mi3d  mi
Decifratura del messaggio:
Calcolo della chiave
3d  1 mod928
Calcolo dell’inverso di 3:
928  309  3  1

1  928  309  3
309  619 mod 928
d=619
Decifratura del messaggio :
f 1 : Z1003  Z1003 | ci  mi   ci 
619
301619  301512 64 328 21 
 301512301643013230183012301
3012  682 mod 928

3018   3012

301619  210

2 2
 ......


Decifratura del messaggio :
f 1 : Z1003  Z1003 | ci  mi   ci 
619
Decifrare un messaggio cifrato con RSA:
f : Z 46  Z 46 | x  y  x5
Decifrare un messaggio cifrato con RSA:
f : Z 46  Z 46 | x  y  x5
Decifrare un messaggio cifrato con RSA:
f : Z 46  Z 46 | x  y  x5
MT
l a
GPD T C L
c h i a v e
L
e
NV C L
n o v e