metodo usato da Cesare (con differenza 3)
CESARE
GIWEVI
debolissimo !
A=0
B=1
C=2
D=3
E=4
F=5
G=6
H=7
I=8
J=9
K=10
L=11
M=12
N=13
O=14
P=15
Q=16
R=17
S=18
T=19
U=20
V=21
W=22
X=23
Y=24
Z=25
ABCDEFGHI JKLMNOPQRST UVWXYZ
BGLQVAFKPUZEJ OT Y DINSXCHMRW
sono ammessi valori qualsiasi per a e b ?
a e 26 primi fra loro
ABCDEFGHI JKLMNOPQRST UVWXYZ
XHEBMLSYCOFKZ ADI UJNWTRQGVP
ALLECINQUEACASADIMARIO
XKKMECAUTMXEXNXBCZXJCD
debole !
XKKMECAUTMXEXNXBCZXJCD
5 volte la X
3 volte la C
A=0
B=1
C=2
D=3
E=4
F=5
G=6
H=7
I=8
J=9
K=10
L=11
M=12
N=13
O=14
P=15
Q=16
R=17
S=18
T=19
U=20
V=21
W=22
X=23
Y=24
Z=25
FTAYYEWNBIDJDTGGYSRAFFDRTAKLOWPPST
ALLECINQUEACASADIMARIO
FELCAMJDVMDLDLGJGEARRNT
perfetto
se….
la chiave è casuale
CHIAVE
406224811
TESTO
337539384
CRIPTATO
733753195
TESTI POSSIBILI
676639001
228744573
118335743
877853923
103047763
899340031
272849254
245332595
037856651
021415501
650855635
810858363
084226634
432111162
542520892
883002712
557818972
861555604
488063481
415523140
623299084
639400134
244229362
692114890
702523620
043005440
717811600
021518332
648019119
675526878
883002712
899443862
Provare l’identità
1
3
2
4
5
6
8
7
9
Certificato d’identità di A
1
3
1
2
4
5
2
6
4
8
7
3
5
6
8
9
grafo
(pubblico)
B deve verificare l’identità di A
7
insieme indipendente
(privato)
9
1
3
1
2
4
5
2
6
4
8
7
3
5
6
8
9
7
9
A costruisce una copia isomorfa del grafo
1
3
6
2
4
5
5
6
9
8
7
8
4
2
3
9
7
B sceglie a caso una delle due richieste ad A
1) mostrami l’isomorfismo tra i grafi
2) mostrami l’insieme indipendente nel grafo isomorfo
1
Se B ha scelto 1
1
3
6
2
4
5
5
6
9
8
7
4
2
3
9
A produce
8
7
16
25
38
49
54
62
77
83
91
1
e B è convinto che
i grafi sono isomorfi
Se B ha scelto 2
1
3
6
2
4
5
5
6
9
8
7
4
2
3
9
A produce
8
7
(2579)
1
e B è convinto che si tratta di un
insieme indipendente
1
3
6
2
4
5
5
6
9
8
7
8
4
2
3
9
7
1
Se un impostore sta impersonando A, ha due scelte
1) produrre un grafo non isomorfo ma con un insieme indipendente di 4 nodi
2) produrre un grafo isomorfo con un insieme indipendente di meno nodi
con probabilità 1/2
non viene smascherato
ripetendo n volte la probabilità di non essere smascherato diventa
quanto è difficile fare la radice quadrata ?
A
chiave segreta
chiave pubblica
dimostrare di possedere la chiave segreta senza svelarla
numero a caso
a B
invio di
A chiede a B: vuoi la radice quadrata di q o di q p ?
B sceglie q
A invia r
B sceglie q p
A invia (r s)
B calcola
B calcola
nessuna informazione
r non contiene informazione sulla chiave segreta
(r s)
non è fattorizzabile e quindi s non viene rilevata
un impostore, sceglie un numero casuale r e poi,
indovinando che B sceglie q, invia
e r come radice quadrata di q
indovinando che B sceglie (qp), invia
e
come radice quadrata di (qp)
ma se sbaglia di indovinare deve calcolare la radice quadrata di
in entrambi i casi
chiavi segrete
chiavi pubbliche
numero a caso
r
A invia a B
B invia a A
A calcola
B verifica che
casuali
e lo invia a B
un impostore, se indovina
invia a B
e
B verifica che
ma questo avviene con probabilità
come continuare una partita a scacchi
ogni mossa è un numero di 4 cifre
ad esempio
4312
estendere il numero ad un numero primo grande p
scegliere un altro primo (più lungo)
eseguire il prodotto
431214691
8137785211
3509132535185734801
e trasmettere questo numero
alla ripresa del gioco rivelare i fattori
numeri segreti
due primi molto grandi p e q
un numero N coprimo a (p-1)(q-1)
esempio p=11, q=17, (p-1)(q-1)=160
N=21
numeri pubblici
prodotto pq
un numero M: MN=1 mod (p-1)(q-1)
esempio pq=187
M=61
Da crittare messaggio (numero) x
calcolo di
y messaggio crittato
Per decifrare y
calcolare
1
2
Se si conoscono p e q
allora si conosce N da MN=1 mod (p-1)(q-1)