Piano Lauree Scientifiche
Crittografia e numeri primi
IV incontro
lunedì 29 novembre 2010
Costruzione del messaggio cifrato 1:
Testo da cifrare:
Questo messaggio non è più segreto.
Elimino gli spazi :
Questomessaggiononèpiùsegreto.
Per il nostro esempio possiamo pensare di eliminare accenti e punteggiatura,
Altrimenti dovremmo inserire altri caratteri…
Questomessaggiononepiusegreto
Costruzione del messaggio cifrato 2:
Testo da cifrare:
Questo messaggio non è più segreto.
Questomessaggiononepiusegreto
Dvido il testo in blocchi di tre lettere :
Que sto mes sag gio non epi use gre to
Aggiungo un carattere finale per fare in modo che tutti i blocchi
abbiano lo stesso numero di lettere (di solito si aggiungono tante x quanti sono
i caratteri mancanti, noi possiamo aggiungere le z)
Que sto mes sag gio non epi use gre toz
Costruzione del messaggio cifrato 3:
Testo da cifrare:
Questo messaggio non è più segreto.
Que sto mes sag gio non epi use gre toz
Traduco il messaggio utilizzando la tabella :
Que
sto
mes
sag gio
non
141804 161712 100416 160006 060812 111211
epi
use
gre
toz
041308 181604 061504 171220
Costruzione del messaggio cifrato 4:
Testo da cifrare:
Questo messaggio non è più segreto.
141804 161712 100416 160006 060812 111211
041308 181604 061504 171220
Applico la funzione (Codice Cesare):
f : Z1000000 Z1000000 | [m]  [m]+ [k]
k=909090
Costruzione del messaggio cifrato 5:
Testo da cifrare:
Questo messaggio non è più segreto.
141804 → 141804 + 909090 = 1050894 → 050894
161712 → 161712 + 909090 = 1070802 → 070802
100416
160006
060812
111211
041308
181604
061504
171220
Costruzione del messaggio cifrato 6:
Testo da cifrare:
Questo messaggio non è più segreto.
141804 161712 100416 160006 060812
111211 041308 181604 061504 171220
050894 070802 009506 069096 969902
020301 950398 090694 970594 080310
Decifratura del messaggio cifrato 7:
Testo da decifrare:
050894 070802 009506 069096 969902
020301 950398 090694 970594 080310
Determino la funzione inversa di decifratura
f-1 : Z1000000 Z1000000 | [m’]  [m’]+ [k’]
k’=1000000-k=
=1000000-909090=090910
Decifratura del messaggio cifrato 8:
Testo da decifrare:
050894 → 050894 + 090910 = 141804
070802 → 070802 + 090910 = 161712
009506
069096
969902
020301
950398
090694
970594
080310
Una volta convertito il messaggio numerico utilizzo
nuovamente la tabella dei caratteri per tradurre
Costruzione del messaggio cifrato 9:
Questo messaggio non è più segreto.
141804 161712 100416 160006 060812 111211
041308 181604 061504 171220
Se invece avessi voluto utilizzare una funzione affine:
f : Z1000000 Z1000000 | [m] [a] [m]+ [b]
Devo verificare che MCD([a],[n])=1
Devo calcolare [a]-1
Lavoriamo con numeri più semplici
(costruiamo per esempio blocchi da due caratteri):
n=1191, [a]=[46]
Utilizzando il metodo delle divisioni successive, calcola
MCD (1191, 46)
a
b
1191
46
resto
a
=
b
*
quoziente
+
1191
=
46
*
+
=
*
+
=
*
+
=
*
+
resto
a
b
resto
a
=
b
*
quoziente
+
resto
1191
46
41
1191
=
46
*
25
+
41
46
41
5
46
=
41
*
1
+
5
41
5
1
41
=
5
*
8
+
1
5
1
0
5
=
1
*
5
+
0
MCD (1191, 46) = 1
Ricostruisci ora l’identità di Bézout:
MCD
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
Ricostruisci ora l’identità di Bézout:
MCD
1
41 – 5*8
=
=
=
=
=
41*9 – 46*8
1191*9 – 46*233
=
41 – (46 – 41*1)*8
=
41 – 46*8 + 41*8
= (1191 – 46*25)*9 – 46*8
= 1191*9 – 46*225 – 46*8
=
In conclusione si può riscrivere:
1
=
MCD =
s
*
*
a
+
+
t
*
*
b
Quindi l’inverso di 46, modulo 1191, è _______
Ricostruisci ora l’identità di Bézout:
MCD
1
41 – 5*8
=
=
=
=
=
41*9 – 46*8
1191*9 – 46*233
=
41 – (46 – 41*1)*8
=
41 – 46*8 + 41*8
= (1191 – 46*25)*9 – 46*8
= 1191*9 – 46*225 – 46*8
=
In conclusione si può riscrivere:
1
=
MCD =
9
s
* 1191 + – 233 *
* a +
t
*
46
b
Quindi l’inverso di 46, modulo 1191, è [– 233 ] = [958]
Quanti sono gli elementi invertibili di Z5?
Quante sono le chiavi per cifrare con la moltiplicazione
p  [a]  [p] modulo 5?
Se n è primo, quanti sono gli elementi invertibili di Zn?
Se n è primo, quante sono le chiavi per cifrare con la
moltiplicazione
p  [a]  [p] modulo n?
Fai l’elenco dei numeri a con 0 < a < 15 e tali che MCD (a, 3) > 1:
{ _______________________ }. Quanti sono? ______________
Fai l’elenco dei numeri a con 0 < a < 15 e tali che MCD (a, 5) > 1:
{ _______________________ }. Quanti sono? ______________
Fai l’elenco degli a con 0 < a < 15 tali che MCD (a, 3) > 1 e MCD (a, 5) > 1:
{ _______________________ }. Quanti sono? ______________
Quanti sono i numeri a con 0 < a < 15 tali che MCD (a, 15) = 1
(quanti sono cioè gli invertibili in Z15)? ________________
Fai l’elenco dei numeri a con 0 < a < 21 e tali che MCD (a, 3) > 1:
{ _______________________ }. Quanti sono? ______________
Fai l’elenco dei numeri a con 0 < a < 21 e tali che MCD (a, 7) > 1:
{ _______________________ }. Quanti sono? ______________
Fai l’elenco degli a con 0 < a < 21 tali che MCD (a, 3) > 1 e MCD (a, 7) > 1:
{ _______________________ }. Quanti sono? ______________
Quanti sono i numeri a con 0 < a < 21 tali che MCD (a, 21) = 1
(quanti sono cioè gli invertibili in Z21)? ________________
Sia n il prodotto di due primi distinti: n = p  q
Quanti sono i numeri a con 0 < a < n che sono
divisibili per p? ________________
Quanti sono i numeri a con 0 < a < n che sono
divisibili per q? ________________
Quanti sono i numeri a con 0 < a < n che NON sono
coprimi con n? _____________________________
Quanti sono gli elementi invertibili in Zn?
Elevamento a potenza
f : Z n  Z n |[m]  [m ']  [m]
Potenze in Z5
Potenze in Z5
x
x^2
x^3
x^4
x^5
x^6
x^7
x^8
x^9 x^10
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
2
2
4
3
1
2
4
3
1
2
4
3
3
4
2
1
3
4
2
1
3
4
4
4
1
4
1
4
1
4
1
4
1
Osservazioni:
1. gli esponenti pari non producono una funzione biunivoca
2. ci sono colonne particolari [1]
3. le potenze si ripetono con ciclicità – alcune funzioni coincidono…
Perché [m]2 non funziona?
[1]2=[1]
[n-1]2=
(n-1)2=n2-2n+1
Potenze in Z5
[x]11=[x]4*2+3 =[x]4*2[x]3 =
=([x]4)2[x]3=
=[1]2[x]3=[x]3
Potenze in Z7
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 Modulo 10
0
1
2
3
4
5
6
7
8
9
x
x2
x3
x4
x5
x6
x7
x8
x9
x10
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
Potenze in Z11
0
1
2
3
4
5
6
7
8
9
12
x2
0
1
4
9
5
3
3
5
9
4
1
x3
0
1
8
5
9
4
7
2
6
3
10
x4
0
1
5
4
3
9
9
3
4
5
1
x5
0
1
10
1
1
1
10
10
10
1
10
x6
0
1
9
3
4
5
5
4
3
9
1
x7
0
1
7
9
5
3
8
6
2
4
10
x8
0
1
3
5
9
4
4
9
5
3
1
x9
0
1
6
4
3
9
2
8
7
5
10
x10
0
1
1
1
1
1
1
1
1
1
1
Potenze modulo 21
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x^2 x^3 x^4 x^5 x^6 x^7 x^8 x^9 x^10 x^11
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
4
8
16 11
1
2
4
8
16 11
9
6
18 12 15
3
9
6
18 12
16
1
4
16
1
4
16
1
4
16
4
20 16 17
1
5
4
20 16 17
15
6
15
6
15
6
15
6
15
6
7
7
7
7
7
7
7
7
7
7
1
8
1
8
1
8
1
8
1
8
18 15
9
18 15
9
18 15
9
18
16 13
4
19
1
10 16 13
4
19
16
8
4
2
1
11 16
8
4
2
18
6
9
3
15 12 18
6
9
3
1
13
1
13
1
13
1
13
1
13
7
14
7
14
7
14
7
14
7
14
15 15 15 15 15 15 15 15 15 15
4
1
16
4
1
16
4
1
16
4
16 20
4
5
1
17 16 20
4
5
9
15 18
9
15 18
9
15 18
9
4
13 16 10
1
19
4
13 16 10
1
20
1
20
1
20
1
20
1
20
x^12
0
1
1
15
1
1
15
7
1
15
1
1
15
1
7
15
1
1
15
1
1
x^13
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x^14
0
1
4
9
16
4
15
7
1
18
16
16
18
1
7
15
4
16
9
4
1
x^15
0
1
8
6
1
20
6
7
8
15
13
8
6
13
14
15
1
20
15
13
20
x^16
0
1
16
18
4
16
15
7
1
9
4
4
9
1
7
15
16
4
18
16
1
x^17
0
1
11
12
16
17
6
7
8
18
19
2
3
13
14
15
4
5
9
10
20
x^18
0
1
1
15
1
1
15
7
1
15
1
1
15
1
7
15
1
1
15
1
1
x^19
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x^20
0
1
4
9
16
4
15
7
1
18
16
16
18
1
7
15
4
16
9
4
1
Decifratura con Potenze in Z5
f3 : Z n  Z n |[m]  [m ']  [m]3
Quale potrebbe essere la funzione di decifratura?
x
x^2
x^3
x^4
x^5
x^6
x^7
x^8
x^9 x^10
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
2
2
4
3
1
2
4
3
1
2
4
3
3
4
2
1
3
4
2
1
3
4
4
4
1
4
1
4
1
4
1
4
1
Decifratura con Potenze in Z5
f31 : Z n  Z n |[m ']  [m]  [m ']k
3  k  1 mod 4
x
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
Decifratura con Potenze in Z5
x
x^2
x^3
x^4
x^5
x^6
x^7
x^8
x^9 x^10
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
2
2
4
3
1
2
4
3
1
2
4
3
3
4
2
1
3
4
2
1
3
4
4
4
1
4
1
4
1
4
1
4
1
Teorema di Fermat