![Page 1: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/1.jpg)
La matematica dell’orologioUn’aritmetica inusuale:
I numeri del nostro ambiente sono: 0, 1, 2, . . . , 11 ecorrispondono alle ore di un nostro orologio
Le operazioni sono intese in questo modo:1 somma: a+ b e l’ora che si ottiene spostando la lancetta dalla
posizione a in avanti di b ore;2 prodotto: a · b e l’ora che si ottiene sommando a a se stessa b
volte.
I risultati nella matematica dell’orologio vengono distinti dagli altrimediante l’espressione (mod 12)
![Page 2: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/2.jpg)
La matematica dell’orologioUn’aritmetica inusuale:
I numeri del nostro ambiente sono: 0, 1, 2, . . . , 11 ecorrispondono alle ore di un nostro orologio
Le operazioni sono intese in questo modo:1 somma: a+ b e l’ora che si ottiene spostando la lancetta dalla
posizione a in avanti di b ore;2 prodotto: a · b e l’ora che si ottiene sommando a a se stessa b
volte.
I risultati nella matematica dell’orologio vengono distinti dagli altrimediante l’espressione (mod 12)
Esercizio 1
Calcolare 7 · 3 (mod 12), 8 · 4 (mod 12), 10 · 5 (mod 12)
![Page 3: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/3.jpg)
La matematica dell’orologioUn’aritmetica inusuale:
I numeri del nostro ambiente sono: 0, 1, 2, . . . , 11 ecorrispondono alle ore di un nostro orologio
Le operazioni sono intese in questo modo:1 somma: a+ b e l’ora che si ottiene spostando la lancetta dalla
posizione a in avanti di b ore;2 prodotto: a · b e l’ora che si ottiene sommando a a se stessa b
volte.
I risultati nella matematica dell’orologio vengono distinti dagli altrimediante l’espressione (mod 12)
Esercizio 1
Calcolare 7 · 3 (mod 12), 8 · 4 (mod 12), 10 · 5 (mod 12)
Esercizio 2
Riflettere sul rapporto che c’e fra i risultati usuali e i risultati(mod 12).
![Page 4: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/4.jpg)
Problema 1
Provare a dare una definizione matematica di a+ b (mod 12) e dia · b (mod 12) che non faccia uso dell’orologio.
![Page 5: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/5.jpg)
Problema 1
Provare a dare una definizione matematica di a+ b (mod 12) e dia · b (mod 12) che non faccia uso dell’orologio.
Quindi:
1 a + b (mod 12) e il resto della divisione di a + b per 12;
2 a · b (mod 12) e il resto della divisione di a · b per 12.
![Page 6: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/6.jpg)
Problema 1
Provare a dare una definizione matematica di a+ b (mod 12) e dia · b (mod 12) che non faccia uso dell’orologio.
Quindi:
1 a + b (mod 12) e il resto della divisione di a + b per 12;
2 a · b (mod 12) e il resto della divisione di a · b per 12.
Gara 1
Calcolare 715 (mod 12) nel minor tempo possibile senzacalcolatrice
![Page 7: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/7.jpg)
Problema 1
Provare a dare una definizione matematica di a+ b (mod 12) e dia · b (mod 12) che non faccia uso dell’orologio.
Quindi:
1 a + b (mod 12) e il resto della divisione di a + b per 12;
2 a · b (mod 12) e il resto della divisione di a · b per 12.
Gara 1
Calcolare 715 (mod 12) nel minor tempo possibile senzacalcolatrice
Idea chiave: elevare a potenza nella matematica dell’orologio puoessere un’operazione molto piu veloce di quello che si potrebbeimmaginare
![Page 8: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/8.jpg)
Generalizziamo: Aritmetica modulareNon c’e niente di speciale nel numero 12. Sostituiamolo con unnumero intero n qualsiasi, purche maggiore di 1.
I numeri del nostro ambiente sono: 0, 1, 2, . . . , n − 1
Le operazioni sono intese in questo modo:1 a+ b (mod n) e il resto della divisione di a + b per n;2 a · b (mod n) e il resto della divisione di a · b per n.
![Page 9: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/9.jpg)
Generalizziamo: Aritmetica modulareNon c’e niente di speciale nel numero 12. Sostituiamolo con unnumero intero n qualsiasi, purche maggiore di 1.
I numeri del nostro ambiente sono: 0, 1, 2, . . . , n − 1
Le operazioni sono intese in questo modo:1 a+ b (mod n) e il resto della divisione di a + b per n;2 a · b (mod n) e il resto della divisione di a · b per n.
Questo insieme numerico viene indicato con il simbolo
Zn = {0, 1, . . . , n − 2, n − 1}
![Page 10: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/10.jpg)
Generalizziamo: Aritmetica modulareNon c’e niente di speciale nel numero 12. Sostituiamolo con unnumero intero n qualsiasi, purche maggiore di 1.
I numeri del nostro ambiente sono: 0, 1, 2, . . . , n − 1
Le operazioni sono intese in questo modo:1 a+ b (mod n) e il resto della divisione di a + b per n;2 a · b (mod n) e il resto della divisione di a · b per n.
Questo insieme numerico viene indicato con il simbolo
Zn = {0, 1, . . . , n − 2, n − 1}
Quando e chiaro che ci stiamo riferendo ad operazioni in Zn
possiamo omettere l’espressione (mod n).
![Page 11: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/11.jpg)
Generalizziamo: Aritmetica modulareNon c’e niente di speciale nel numero 12. Sostituiamolo con unnumero intero n qualsiasi, purche maggiore di 1.
I numeri del nostro ambiente sono: 0, 1, 2, . . . , n − 1
Le operazioni sono intese in questo modo:1 a+ b (mod n) e il resto della divisione di a + b per n;2 a · b (mod n) e il resto della divisione di a · b per n.
Questo insieme numerico viene indicato con il simbolo
Zn = {0, 1, . . . , n − 2, n − 1}
Quando e chiaro che ci stiamo riferendo ad operazioni in Zn
possiamo omettere l’espressione (mod n).
Esercizio 3
Calcolare: 21 + 23 (mod 14), 21 · 23 (mod 19), 2210 (mod 20),senza usare la calcolatrice
![Page 12: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/12.jpg)
Esempio crittografico: n = 21
Gli elementi di Z21 sono identificati con le lettere dell’alfabeto
A 0B 1C 2D 3E 4F 5G 6H 7I 8L 9M 10N 11O 12P 13Q 14R 15S 16T 17U 18V 19Z 20
![Page 13: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/13.jpg)
Il cifrario di Cesare:
Testi in chiaro: Z21
Testi cifrati: Z21
Chiavi: Z21
Codifica: ek(x) = x + k (mod 21)
![Page 14: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/14.jpg)
Il cifrario di Cesare:
Testi in chiaro: Z21
Testi cifrati: Z21
Chiavi: Z21
Codifica: ek(x) = x + k (mod 21)
Una possibile generalizzazione:
Testi in chiaro: Z21
Testi cifrati: Z21
Chiavi: Z21 × Z21
Codifica: ea,b(x) = a · x + b (mod 21)
![Page 15: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/15.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
![Page 16: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/16.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?
![Page 17: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/17.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?Quale e secondo voi la motivazione di natura matematica?
![Page 18: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/18.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?Quale e secondo voi la motivazione di natura matematica?a · x1 = a · x2 per qualche x1 6= x2
![Page 19: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/19.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?Quale e secondo voi la motivazione di natura matematica?a · x1 = a · x2 per qualche x1 6= x2
Quale congettura di carattere generale vi sentireste diformulare al riguardo? Come si distinguono le chiavi valide daquelle non valide (se necessario, provate anche altre chiavi!)
![Page 20: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/20.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?Quale e secondo voi la motivazione di natura matematica?a · x1 = a · x2 per qualche x1 6= x2
Quale congettura di carattere generale vi sentireste diformulare al riguardo? Come si distinguono le chiavi valide daquelle non valide (se necessario, provate anche altre chiavi!)
Come provereste a dimostrare tale congettura?
![Page 21: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/21.jpg)
Esperimento 1
A gruppi di 4, calcolate le funzioni di codifica relative alle seguentichiavi: (3, 0), (3, 1), (2, 0), (2, 1). Discutere i risultati ottenuti.
Perche le chiavi con a = 3 non sono adeguate mentre quellecon a = 2 sı?Quale e secondo voi la motivazione di natura matematica?a · x1 = a · x2 per qualche x1 6= x2
Quale congettura di carattere generale vi sentireste diformulare al riguardo? Come si distinguono le chiavi valide daquelle non valide (se necessario, provate anche altre chiavi!)
Come provereste a dimostrare tale congettura?deve esistere x con ax = 1 (mod 21) ⇒ ax = c · 21 + 1. Cio e implica MCD(a, 21) = 1. Viceversa, se
MCD(a, 21) = 1 allora ax1 = ax2 non puo mai verificarsi dato che 21 divide a(x1 − x2)
![Page 22: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/22.jpg)
Cifrario affine
Testi in chiaro: Z21
Testi cifrati: Z21
Chiavi: A× Z21 doveA = {a ∈ Z21 | MCD(a, 21) = 1} ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}Codifica: ea,b(x) = a · x + b (mod 21)
![Page 23: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/23.jpg)
Cifrario affine
Testi in chiaro: Z21
Testi cifrati: Z21
Chiavi: A× Z21 doveA = {a ∈ Z21 | MCD(a, 21) = 1} ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}Codifica: ea,b(x) = a · x + b (mod 21)
Gara 2
Decodificare il seguente messaggio, sapendo che e stato cifrato conun cifrario affine:lo qtpobzh avb pmt eohvdo ctznvt od rmtcgh ponbvgoztdgh ntv sbnvhccozb stuohdtlink verifica: www.dmi.unipg.it/giuliet/MIP.txt
![Page 24: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/24.jpg)
La divisione in Zn
.Abbiamo visto che in Z21 vale la seguente proprieta:MCD(a, 21) = 1 ⇔ esiste b in Z21 con ab = 1 (mod 21)
![Page 25: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/25.jpg)
La divisione in Zn
.Abbiamo visto che in Z21 vale la seguente proprieta:MCD(a, 21) = 1 ⇔ esiste b in Z21 con ab = 1 (mod 21)
E facile dimostrare che la stessa proprieta vale in Zn:MCD(a, n) = 1 ⇔ esiste b in Zn con ab = 1 (mod n)
![Page 26: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/26.jpg)
La divisione in Zn
.Abbiamo visto che in Z21 vale la seguente proprieta:MCD(a, 21) = 1 ⇔ esiste b in Z21 con ab = 1 (mod 21)
E facile dimostrare che la stessa proprieta vale in Zn:MCD(a, n) = 1 ⇔ esiste b in Zn con ab = 1 (mod n)
Nell’ambiente numerico Zn la divisione non e sempre possibile:1aesiste se e solo se MCD(a, n) = 1
![Page 27: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/27.jpg)
La divisione in Zn
.Abbiamo visto che in Z21 vale la seguente proprieta:MCD(a, 21) = 1 ⇔ esiste b in Z21 con ab = 1 (mod 21)
E facile dimostrare che la stessa proprieta vale in Zn:MCD(a, n) = 1 ⇔ esiste b in Zn con ab = 1 (mod n)
Nell’ambiente numerico Zn la divisione non e sempre possibile:1aesiste se e solo se MCD(a, n) = 1
Problema: come calcolare 1/a?
![Page 28: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/28.jpg)
La divisione in Zn
.Abbiamo visto che in Z21 vale la seguente proprieta:MCD(a, 21) = 1 ⇔ esiste b in Z21 con ab = 1 (mod 21)
E facile dimostrare che la stessa proprieta vale in Zn:MCD(a, n) = 1 ⇔ esiste b in Zn con ab = 1 (mod n)
Nell’ambiente numerico Zn la divisione non e sempre possibile:1aesiste se e solo se MCD(a, n) = 1
Problema: come calcolare 1/a?
Esperimento 2
Calcolare (se possibile):12 in Z23
14 in Z9
12 in Z22
13 in Z22
![Page 29: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/29.jpg)
Un metodo piu veloce: l’algoritmo euclideo
n dividendo; a divisoredivisione euclidea: n = qa + r con 0 ≤ r ≤ a− 1poniamo q := q0 e r := r1
![Page 30: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/30.jpg)
Un metodo piu veloce: l’algoritmo euclideo
n dividendo; a divisoredivisione euclidea: n = qa + r con 0 ≤ r ≤ a− 1poniamo q := q0 e r := r1
Passi successivi:a = q1r1 + r2r1 = q2r2 + r3r2 = q3r3 + r4. . .ri−1 = qi ri + ri+1
. . .
![Page 31: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/31.jpg)
Un metodo piu veloce: l’algoritmo euclideo
n dividendo; a divisoredivisione euclidea: n = qa + r con 0 ≤ r ≤ a− 1poniamo q := q0 e r := r1
Passi successivi:a = q1r1 + r2r1 = q2r2 + r3r2 = q3r3 + r4. . .ri−1 = qi ri + ri+1
. . .
Ad un certo punto il resto diventa uguale a 0. L’ultimo restonon nullo e il Massimo Comun Divisore di n e a.
![Page 32: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/32.jpg)
Un metodo piu veloce: l’algoritmo euclideo
n dividendo; a divisoredivisione euclidea: n = qa + r con 0 ≤ r ≤ a− 1poniamo q := q0 e r := r1
Passi successivi:a = q1r1 + r2r1 = q2r2 + r3r2 = q3r3 + r4. . .ri−1 = qi ri + ri+1
. . .
Ad un certo punto il resto diventa uguale a 0. L’ultimo restonon nullo e il Massimo Comun Divisore di n e a.
Nel caso in cui MCD(n, a) = 1 e facile trovare x , y tali che1 = nx + ay .
![Page 33: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/33.jpg)
Un metodo piu veloce: l’algoritmo euclideo
n dividendo; a divisoredivisione euclidea: n = qa + r con 0 ≤ r ≤ a− 1poniamo q := q0 e r := r1
Passi successivi:a = q1r1 + r2r1 = q2r2 + r3r2 = q3r3 + r4. . .ri−1 = qi ri + ri+1
. . .
Ad un certo punto il resto diventa uguale a 0. L’ultimo restonon nullo e il Massimo Comun Divisore di n e a.
Nel caso in cui MCD(n, a) = 1 e facile trovare x , y tali che1 = nx + ay .
Conseguenza: y mod n e proprio 1/a in Zn
![Page 34: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/34.jpg)
EsempioCome trovare l’inverso di 12 in Z53?
![Page 35: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/35.jpg)
EsempioCome trovare l’inverso di 12 in Z53?Algoritmo euclideo53 = 4 · 12 + 512 = 2 · 5 + 25 = 2 · 2 + 12 = 2 · 1 + 0
![Page 36: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/36.jpg)
EsempioCome trovare l’inverso di 12 in Z53?Algoritmo euclideo53 = 4 · 12 + 5 ⇒ 5 = 53− 4 · 1212 = 2 · 5 + 2 ⇒ 2 = 12 − 2 · 55 = 2 · 2 + 1 ⇒ 1 = 5− 2 · 22 = 2 · 1 + 0Risalendo le uguaglianze dal basso si scopre che...1 = 5− 2 · 21 = 5− 2(12 − 2 · 5)1 = (53− 4 · 12) − 2(12 − 2 · (53− 4 · 12))1 = 5 · 53− 22 · 12
![Page 37: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/37.jpg)
EsempioCome trovare l’inverso di 12 in Z53?Algoritmo euclideo53 = 4 · 12 + 5 ⇒ 5 = 53− 4 · 1212 = 2 · 5 + 2 ⇒ 2 = 12 − 2 · 55 = 2 · 2 + 1 ⇒ 1 = 5− 2 · 22 = 2 · 1 + 0Risalendo le uguaglianze dal basso si scopre che...1 = 5− 2 · 21 = 5− 2(12 − 2 · 5)1 = (53− 4 · 12) − 2(12 − 2 · (53− 4 · 12))1 = 5 · 53− 22 · 12Pertanto
−22 · 12 = 1 (mod 53) ⇒ 1
12= −22 = 31 (mod 53)
![Page 38: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/38.jpg)
EsempioCome trovare l’inverso di 12 in Z53?Algoritmo euclideo53 = 4 · 12 + 5 ⇒ 5 = 53− 4 · 1212 = 2 · 5 + 2 ⇒ 2 = 12 − 2 · 55 = 2 · 2 + 1 ⇒ 1 = 5− 2 · 22 = 2 · 1 + 0Risalendo le uguaglianze dal basso si scopre che...1 = 5− 2 · 21 = 5− 2(12 − 2 · 5)1 = (53− 4 · 12) − 2(12 − 2 · (53− 4 · 12))1 = 5 · 53− 22 · 12Pertanto
−22 · 12 = 1 (mod 53) ⇒ 1
12= −22 = 31 (mod 53)
Gara 3
Determinare 1/11 in Z63
![Page 39: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/39.jpg)
L’algoritmo euclideo nel linguaggio MAGMA
Istruzioni
r:=(a mod b);while (r ne 0) do
a:=b;b:=r;r:=(a mod b);
end while;MCD:=b;MCD;
![Page 40: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/40.jpg)
L’algoritmo euclideo nel linguaggio MAGMA
Istruzioni con contapassi
r:=(a mod b);cont:=1;while (r ne 0) do
a:=b;b:=r;r:=(a mod b);cont:=cont+1;
end while;MCD:=b;MCD;cont;
![Page 41: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/41.jpg)
Esperimento 3
Calcolare con MAGMA i MCD di coppie di numeri sempre piugrandi e il numero di divisioni effettuate.
Quanti passi vi aspettavate in teoria? (ordine di grandezzarispetto a b)
![Page 42: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/42.jpg)
Esperimento 3
Calcolare con MAGMA i MCD di coppie di numeri sempre piugrandi e il numero di divisioni effettuate.
Quanti passi vi aspettavate in teoria? (ordine di grandezzarispetto a b)
Quanti passi sono stati necessari in realta?
![Page 43: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/43.jpg)
Esperimento 3
Calcolare con MAGMA i MCD di coppie di numeri sempre piugrandi e il numero di divisioni effettuate.
Quanti passi vi aspettavate in teoria? (ordine di grandezzarispetto a b)
Quanti passi sono stati necessari in realta?
Quale congettura potreste formulare relativamente a talenumero di passi? (Suggerimento: provare divisori che sianopotenze di 2)
![Page 44: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/44.jpg)
Esperimento 3
Calcolare con MAGMA i MCD di coppie di numeri sempre piugrandi e il numero di divisioni effettuate.
Quanti passi vi aspettavate in teoria? (ordine di grandezzarispetto a b)
Quanti passi sono stati necessari in realta?
Quale congettura potreste formulare relativamente a talenumero di passi? (Suggerimento: provare divisori che sianopotenze di 2)
Come potreste provare tale congettura?
![Page 45: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/45.jpg)
Esperimento 3
Calcolare con MAGMA i MCD di coppie di numeri sempre piugrandi e il numero di divisioni effettuate.
Quanti passi vi aspettavate in teoria? (ordine di grandezzarispetto a b)
Quanti passi sono stati necessari in realta?
Quale congettura potreste formulare relativamente a talenumero di passi? (Suggerimento: provare divisori che sianopotenze di 2)
Come potreste provare tale congettura?ri−1 ≥ ri + ri+1 ≥ 2ri+1
![Page 46: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/46.jpg)
Confronto con il metodo della scuola media...
Esperimento 4
Provate ad usare MAGMA per calcolare il massimo comundivisore di numeri sempre piu grandi. Potete usaredirettamante il comando GCD(a,b)
Sempre con MAGMA, fattorizzate quegli stessi numeri con ilcomandoFactorization(n);
Confrontate i tempi di esecuzione.
![Page 47: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/47.jpg)
Confronto con il metodo della scuola media...
Esperimento 4
Provate ad usare MAGMA per calcolare il massimo comundivisore di numeri sempre piu grandi. Potete usaredirettamante il comando GCD(a,b)
Sempre con MAGMA, fattorizzate quegli stessi numeri con ilcomandoFactorization(n);
Confrontate i tempi di esecuzione.
Esempio:a = 10000000000000000000000000000603000000000000000000000000001881b = 1000000000000000000000000000000000000000000000001231231231234Confrontare GCD(a,b) con Factorization(a)
![Page 48: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/48.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto:
![Page 49: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/49.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
![Page 50: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/50.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione:
![Page 51: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/51.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
![Page 52: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/52.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Fattorizzazione:
![Page 53: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/53.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Fattorizzazione: lenta
![Page 54: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/54.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Fattorizzazione: lenta
Elevamento a potenza: ?
![Page 55: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/55.jpg)
Primo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Fattorizzazione: lenta
Elevamento a potenza: ?
Logaritmo: ?
![Page 56: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/56.jpg)
Il vero cifrario di Diffie-Hellman
Chiave pubblica: (1) un numero primo p; (2) un elemento diZp, diciamo A; (3) una potenza di A, diciamo AB (mod p).
Chiave privata: l’esponente B (compreso fra 1 e p − 2).
Codifica di un messaggio M ∈ Zp: il mittente sceglie unintero casuale compreso fra 1 e p − 2, diciamo C e invia, ivalori (M · (AB)C ,AC ).
Decodifica di un messaggio (α, β): M = α/βB .
![Page 57: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/57.jpg)
Il vero cifrario di Diffie-Hellman
Chiave pubblica: (1) un numero primo p; (2) un elemento diZp, diciamo A; (3) una potenza di A, diciamo AB (mod p).
Chiave privata: l’esponente B (compreso fra 1 e p − 2).
Codifica di un messaggio M ∈ Zp: il mittente sceglie unintero casuale compreso fra 1 e p − 2, diciamo C e invia, ivalori (M · (AB)C ,AC ).
Decodifica di un messaggio (α, β): M = α/βB .
Gara 4
Divisi in tre squadre, impersonate i ruoli di mittente, opponente edestinatario. Supponiamo che parte della chiave pubblica deldestinatario sia p = 29, A = 2. La squadra destinatario sceglie B ecomunica a tutta la classe AB (mod p). Misuriamo i tempi in cui:
la squadra mittente codifica un messaggio scelto a caso
la squadra destinatario decodifica tale messaggio
la squadra opponente decodifica tale messaggio
![Page 58: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/58.jpg)
Elevamento a potenza in Zn
Sia n un numero di 1024 cifre binarie (circa 308 cifre decimali).Problema: Fissato A in Zn, e B esponente compreso fra 1 en − 1, quante moltiplicazioni in Zn sono necessarie per calcolareAB (mod n)?
![Page 59: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/59.jpg)
Elevamento a potenza in Zn
Sia n un numero di 1024 cifre binarie (circa 308 cifre decimali).Problema: Fissato A in Zn, e B esponente compreso fra 1 en − 1, quante moltiplicazioni in Zn sono necessarie per calcolareAB (mod n)?
Esperimento 5
Scegliere un numero n con 300 cifre (esempio:10300 + 1378543)
Scegliere due numeri A e B minori di n
Provare a calcolare con MAGMA il prodotto A · A · A · · ·(mod n) per B volte
![Page 60: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/60.jpg)
Elevamento a potenza in Zn
Sia n un numero di 1024 cifre binarie (circa 308 cifre decimali).Problema: Fissato A in Zn, e B esponente compreso fra 1 en − 1, quante moltiplicazioni in Zn sono necessarie per calcolareAB (mod n)?
Esperimento 5
Scegliere un numero n con 300 cifre (esempio:10300 + 1378543)
Scegliere due numeri A e B minori di n
Provare a calcolare con MAGMA il prodotto A · A · A · · ·(mod n) per B volte
Deve esistere un metodo molto piu veloce, altrimenti nonpotremmo usare Diffie-Hellman!
![Page 61: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/61.jpg)
Elevamento a potenza in Zn
Sia n un numero di 1024 cifre binarie (circa 308 cifre decimali).Problema: Fissato A in Zn, e B esponente compreso fra 1 en − 1, quante moltiplicazioni in Zn sono necessarie per calcolareAB (mod n)?
Esperimento 5
Scegliere un numero n con 300 cifre (esempio:10300 + 1378543)
Scegliere due numeri A e B minori di n
Provare a calcolare con MAGMA il prodotto A · A · A · · ·(mod n) per B volte
Deve esistere un metodo molto piu veloce, altrimenti nonpotremmo usare Diffie-Hellman!Tentiamo con il comando Modexp(A,B,n)
![Page 62: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/62.jpg)
Elevamento a potenza in Zn
Sia n un numero di 1024 cifre binarie (circa 308 cifre decimali).Problema: Fissato A in Zn, e B esponente compreso fra 1 en − 1, quante moltiplicazioni in Zn sono necessarie per calcolareAB (mod n)?
Esperimento 5
Scegliere un numero n con 300 cifre (esempio:10300 + 1378543)
Scegliere due numeri A e B minori di n
Provare a calcolare con MAGMA il prodotto A · A · A · · ·(mod n) per B volte
Deve esistere un metodo molto piu veloce, altrimenti nonpotremmo usare Diffie-Hellman!Tentiamo con il comando Modexp(A,B,n)Quale potrebbe essere l’idea alla base di Modexp?
![Page 63: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/63.jpg)
Square and Multiply
Supponiamo di voler calcolare 35637 (mod 832)
![Page 64: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/64.jpg)
Square and Multiply
Supponiamo di voler calcolare 35637 (mod 832)
Sfruttiamo la scrittura di 637 in base 2:
637 = 1001111101 = 512 + 64 + 32 + 16 + 8 + 4 + 1
e quindi
35637 (mod 832) = 35512·3564·3532·3516·358·354·351 (mod 832);
apparentemente il problema non sembra semplificato.
![Page 65: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/65.jpg)
Square and Multiply
Supponiamo di voler calcolare 35637 (mod 832)
Sfruttiamo la scrittura di 637 in base 2:
637 = 1001111101 = 512 + 64 + 32 + 16 + 8 + 4 + 1
e quindi
35637 (mod 832) = 35512·3564·3532·3516·358·354·351 (mod 832);
apparentemente il problema non sembra semplificato.
Ma 352 = 79 (mod 832) e possiamo proseguire con lepotenze di 2 e calcolare 354 (mod 832): basta osservare che354 = 352 · 352 (mod 832) e quindi 354 = 792 = 129(mod 832)
![Page 66: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/66.jpg)
Procedendo con lo stesso sistema si ottengono:352 = 79 (mod 832)354 = 792 = 129 (mod 832)358 = 1292 = 215 (mod 832)3516 = 2152 = 3 (mod 832)3532 = 32 = 9 (mod 832)3564 = 92 = 81 (mod 832)35128 = 812 = 67 (mod 832)35256 = 672 = 287 (mod 832)35512 = 2872 = 239 (mod 832)
![Page 67: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/67.jpg)
Procedendo con lo stesso sistema si ottengono:352 = 79 (mod 832)354 = 792 = 129 (mod 832)358 = 1292 = 215 (mod 832)3516 = 2152 = 3 (mod 832)3532 = 32 = 9 (mod 832)3564 = 92 = 81 (mod 832)35128 = 812 = 67 (mod 832)35256 = 672 = 287 (mod 832)35512 = 2872 = 239 (mod 832)Quindi 35637 (mod 832) = 239 · 81 · 9 · 3 · 215 · 129 · 35 (mod 832).Il risultato finale 35367 = 121 (mod 832)
![Page 68: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/68.jpg)
Procedendo con lo stesso sistema si ottengono:352 = 79 (mod 832)354 = 792 = 129 (mod 832)358 = 1292 = 215 (mod 832)3516 = 2152 = 3 (mod 832)3532 = 32 = 9 (mod 832)3564 = 92 = 81 (mod 832)35128 = 812 = 67 (mod 832)35256 = 672 = 287 (mod 832)35512 = 2872 = 239 (mod 832)Quindi 35637 (mod 832) = 239 · 81 · 9 · 3 · 215 · 129 · 35 (mod 832).Il risultato finale 35367 = 121 (mod 832)
Esercizio 4
Calcolare col metodo square and multiply le seguenti potenzemodulo n = 92:
1 7237
2 2453
![Page 69: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/69.jpg)
Secondo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Elevamento a potenza: veloce - square and multiply
Fattorizzazione: lenta
![Page 70: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/70.jpg)
Secondo Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Elevamento a potenza: veloce - square and multiply
Fattorizzazione: lenta
Logaritmo: ?
![Page 71: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/71.jpg)
Logaritmo in Zn
Esperimento 6
Scrivere tutte le potenze di 2 in R con esponente compresofra 1 e 200
Ripetere lo stesso conteggio modulo p, con p = 557
Discutere i risultati ottenuti
![Page 72: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/72.jpg)
Logaritmo in Zn
Esperimento 6
Scrivere tutte le potenze di 2 in R con esponente compresofra 1 e 200
Ripetere lo stesso conteggio modulo p, con p = 557
Discutere i risultati ottenuti
Conseguenza: Non esistono algoritmi veloci per il calcolo dilogaritmi in aritmetica modulare
![Page 73: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/73.jpg)
Riepilogo
Nell’aritmetica modulare:
Somma e prodotto: veloci
Divisione: veloce - algoritmo euclideo
Elevamento a potenza: veloce - square and multiply
Logaritmo: lento
Fattorizzazione: lenta
![Page 74: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/74.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
![Page 75: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/75.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
![Page 76: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/76.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
Se n e un numero primo, quanto vale φ(n)?
![Page 77: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/77.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
Se n e un numero primo, quanto vale φ(n)? n-1
Il caso piu interessante per noi e quello in cui n = pq, dove p e qsono numeri primi.
![Page 78: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/78.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
Se n e un numero primo, quanto vale φ(n)? n-1
Il caso piu interessante per noi e quello in cui n = pq, dove p e qsono numeri primi.
Esperimento 7
Determinare φ(n) per n = 6, 10, 15, 21, . . ..
![Page 79: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/79.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
Se n e un numero primo, quanto vale φ(n)? n-1
Il caso piu interessante per noi e quello in cui n = pq, dove p e qsono numeri primi.
Esperimento 7
Determinare φ(n) per n = 6, 10, 15, 21, . . ..
Congetturare una regola generale per φ(n) nel caso n = pqcon p, q primi.
![Page 80: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/80.jpg)
La funzione toziente di Eulero
Problema: Quanti sono gli elementi invertibili in Zn?
Il numero di questi elementi si indica con φ(n). La funzione φ sichiama funzione toziente di Eulero
Se n e un numero primo, quanto vale φ(n)? n-1
Il caso piu interessante per noi e quello in cui n = pq, dove p e qsono numeri primi.
Esperimento 7
Determinare φ(n) per n = 6, 10, 15, 21, . . ..
Congetturare una regola generale per φ(n) nel caso n = pqcon p, q primi.
Provare a dimostrare tale congettura.
![Page 81: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/81.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
![Page 82: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/82.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
![Page 83: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/83.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
Scrivere le potenze di tutti gli elementi non nulli di Z11;
![Page 84: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/84.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
Scrivere le potenze di tutti gli elementi non nulli di Z11;
Osservare i risultati
![Page 85: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/85.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
Scrivere le potenze di tutti gli elementi non nulli di Z11;
Osservare i risultati
Formulare una congettura generale sul valore di ap (mod p)
![Page 86: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/86.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
Scrivere le potenze di tutti gli elementi non nulli di Z11;
Osservare i risultati
Formulare una congettura generale sul valore di ap (mod p)
Provare a dimostrare tale congettura
![Page 87: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/87.jpg)
Il piccolo Teorema di Fermat
Esperimento 8
Scrivere le potenze di tutti gli elementi non nulli di Z5;
Scrivere le potenze di tutti gli elementi non nulli di Z7;
Scrivere le potenze di tutti gli elementi non nulli di Z11;
Osservare i risultati
Formulare una congettura generale sul valore di ap (mod p)
Provare a dimostrare tale congettura
Teorema 1 (Piccolo teorema di Fermat)
Sia p un numero primo e sia a un intero qualsiasi. Allora
ap = a (mod p)
![Page 88: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/88.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
![Page 89: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/89.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
![Page 90: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/90.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
![Page 91: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/91.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
Questo vuol dire che aj−i = 1 (mod p) (perche?)
![Page 92: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/92.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
Questo vuol dire che aj−i = 1 (mod p) (perche?)
Sia s ≤ p − 1 il minimo intero positivo tale che as = 1(mod p)
![Page 93: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/93.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
Questo vuol dire che aj−i = 1 (mod p) (perche?)
Sia s ≤ p − 1 il minimo intero positivo tale che as = 1(mod p)
Le potenze distinte di a sono 1, a, a2, . . . , as−1. Dopodiche,dato che as = 1, si ripetono.
Per ogni b ∈ Zp, gli elementi b, ba, ba2, . . . , bas−1 sono innumero di s
![Page 94: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/94.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
Questo vuol dire che aj−i = 1 (mod p) (perche?)
Sia s ≤ p − 1 il minimo intero positivo tale che as = 1(mod p)
Le potenze distinte di a sono 1, a, a2, . . . , as−1. Dopodiche,dato che as = 1, si ripetono.
Per ogni b ∈ Zp, gli elementi b, ba, ba2, . . . , bas−1 sono innumero di s
L’insieme degli elementi non nulli di Zp e ripartito in taligruppi di s elementi
![Page 95: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/95.jpg)
Se a = 0 (mod p), allora ap = a = 0 (mod p)
Se a 6= 0 (mod p), allora possiamo consideriamo le potenze dia = a0, a1, a2, . . ., tutte calcolate (mod p)
Per qualche 0 ≤ i ≤ j ≤ p − 1 si avranno due potenze uguali:ai = aj (mod p) (perche?)
Questo vuol dire che aj−i = 1 (mod p) (perche?)
Sia s ≤ p − 1 il minimo intero positivo tale che as = 1(mod p)
Le potenze distinte di a sono 1, a, a2, . . . , as−1. Dopodiche,dato che as = 1, si ripetono.
Per ogni b ∈ Zp, gli elementi b, ba, ba2, . . . , bas−1 sono innumero di s
L’insieme degli elementi non nulli di Zp e ripartito in taligruppi di s elementi
s divide p − 1
![Page 96: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/96.jpg)
Il Teorema di Eulero - forma deboleL’argomento vale per ogni n sostituendo l’espressione elementi nonnulli di Zp con elementi invertibili in Zn.
![Page 97: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/97.jpg)
Il Teorema di Eulero - forma deboleL’argomento vale per ogni n sostituendo l’espressione elementi nonnulli di Zp con elementi invertibili in Zn.
Teorema 2 (Teorema di Eulero - forma debole)
Sia n un intero positivo e sia a un elemento di Zn tale cheMCD(a, n) = 1. Allora
akφ(n)+1 = a (mod n)
![Page 98: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/98.jpg)
Il Teorema di Eulero - forma deboleL’argomento vale per ogni n sostituendo l’espressione elementi nonnulli di Zp con elementi invertibili in Zn.
Teorema 2 (Teorema di Eulero - forma debole)
Sia n un intero positivo e sia a un elemento di Zn tale cheMCD(a, n) = 1. Allora
akφ(n)+1 = a (mod n)
Esercizio 5
Verificare il Teorema di Eulero in forma debole per le seguenticoppie di interi: n = 10, a = 3; n = 20, a = 3; n = 15, a = 7.
![Page 99: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/99.jpg)
Il Teorema di Eulero - forma deboleL’argomento vale per ogni n sostituendo l’espressione elementi nonnulli di Zp con elementi invertibili in Zn.
Teorema 2 (Teorema di Eulero - forma debole)
Sia n un intero positivo e sia a un elemento di Zn tale cheMCD(a, n) = 1. Allora
akφ(n)+1 = a (mod n)
Esercizio 5
Verificare il Teorema di Eulero in forma debole per le seguenticoppie di interi: n = 10, a = 3; n = 20, a = 3; n = 15, a = 7.
Esperimento 9
L’ipotesi MCD(a, n) = 1 e veramente necessaria. Il comandoMAGMA per la funzione di Eulero e EulerPhi(n).
![Page 100: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/100.jpg)
Il Teorema di Eulero - forma deboleL’argomento vale per ogni n sostituendo l’espressione elementi nonnulli di Zp con elementi invertibili in Zn.
Teorema 2 (Teorema di Eulero - forma debole)
Sia n un intero positivo e sia a un elemento di Zn tale cheMCD(a, n) = 1. Allora
akφ(n)+1 = a (mod n)
Esercizio 5
Verificare il Teorema di Eulero in forma debole per le seguenticoppie di interi: n = 10, a = 3; n = 20, a = 3; n = 15, a = 7.
Esperimento 9
L’ipotesi MCD(a, n) = 1 e veramente necessaria. Il comandoMAGMA per la funzione di Eulero e EulerPhi(n).
controesempi per n = 8, 12, 16, 20, 24, 28, 32 e a = 2
![Page 101: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/101.jpg)
Il Teorema di Eulero - forma RSA
Teorema 3 (Teorema di Eulero - forma debole)
Sia n un intero positivo della forma n = pq con p e q primi, e sia aun elemento qualsiasi di Zn. Allora
akφ(n)+1 = a (mod n)
![Page 102: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/102.jpg)
Il Teorema di Eulero - forma RSA
Teorema 3 (Teorema di Eulero - forma debole)
Sia n un intero positivo della forma n = pq con p e q primi, e sia aun elemento qualsiasi di Zn. Allora
akφ(n)+1 = a (mod n)
Esperimento 10
Verificare il Teorema per un certo numero di casi con l’aiuto diMagma.
![Page 103: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/103.jpg)
Il crittosistema RSA: esempioChiave pubblica di Ryanair:Modulo (1024 bit):AE 64 DD 3D 64 45 D9 56 AB 5B 18 D1 03 3F 68 6B F4 F7 735B A1 C7 B3 1D CE A8 3E 57 FC B0 51 86 81 E0 81 AC C1 72F5 4F E0 F5 8E 47 5B 93 D6 33 D6 21 F9 9F 81 10 18 C5 47 C133 94 1B D1 3A 88 5B 3B 32 92 49 75 0A 92 8E 17 0A 74 F7 EAC0 E5 A9 BD E2 02 84 FC 86 C2 F3 98 64 74 FE AA D4 8D 8D8F CD 95 65 83 25 B9 DE D3 47 C1 A6 33 C9 F2 A8 A8 DC 023F C3 4F 4A A7 F3 D2 A4 69 A8 15 E5
Esponente pubblico:01 00 01
Convertitore: http://www.darkfader.net/toolbox/convert/
![Page 104: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/104.jpg)
Modulo:n=122463632067233237685492934786911990404770932108216049460931235788797236176105263908162964225569626674489521384482266087210944781649755406053639321717623493398190382750848442616120715097041738231236128611955073508554768311206520492762180030935394395072324941947924722132784355728552674799561849761300834948581
Esponente pubblico:e=65537
![Page 105: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/105.jpg)
RSA
Chiave pubblica: n, e
![Page 106: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/106.jpg)
RSA
Chiave pubblica: n, e
Chiave privata:1 p, q numeri primi tali che n = p · q2 d ∈ Zφ(n) tale che d = 1/e (mod φ(n))
![Page 107: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/107.jpg)
RSA
Chiave pubblica: n, e
Chiave privata:1 p, q numeri primi tali che n = p · q2 d ∈ Zφ(n) tale che d = 1/e (mod φ(n))
Codifica di un messaggio M ∈ Zn:
Me (mod n)
![Page 108: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/108.jpg)
RSA
Chiave pubblica: n, e
Chiave privata:1 p, q numeri primi tali che n = p · q2 d ∈ Zφ(n) tale che d = 1/e (mod φ(n))
Codifica di un messaggio M ∈ Zn:
Me (mod n)
Decodifica di un messaggio
M = (Me)d
![Page 109: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/109.jpg)
RSA
Chiave pubblica: n, e
Chiave privata:1 p, q numeri primi tali che n = p · q2 d ∈ Zφ(n) tale che d = 1/e (mod φ(n))
Codifica di un messaggio M ∈ Zn:
Me (mod n)
Decodifica di un messaggio
M = (Me)d
Perche e corretta la decodifica?
![Page 110: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/110.jpg)
RSA
Chiave pubblica: n, e
Chiave privata:1 p, q numeri primi tali che n = p · q2 d ∈ Zφ(n) tale che d = 1/e (mod φ(n))
Codifica di un messaggio M ∈ Zn:
Me (mod n)
Decodifica di un messaggio
M = (Me)d
Perche e corretta la decodifica?Grazie al Teorema di Euleroed = 1 (mod φ(n)) ⇒ ed = k · φ(n) + 1 ⇒(Me)d = Med = Mkφ(n)+1 = M
![Page 111: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/111.jpg)
Fattibilita
calcolo di n a partire da p e q: moltiplicazione
calcolo di d : divisione in Zφ(n)
codifica: elevamento a potenza
decodifica: elevamento a potenza
![Page 112: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/112.jpg)
Fattibilita
calcolo di n a partire da p e q: moltiplicazione
calcolo di d : divisione in Zφ(n)
codifica: elevamento a potenza
decodifica: elevamento a potenza
calcolo di p e q: PROBLEMA
![Page 113: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/113.jpg)
Fattibilita
calcolo di n a partire da p e q: moltiplicazione
calcolo di d : divisione in Zφ(n)
codifica: elevamento a potenza
decodifica: elevamento a potenza
calcolo di p e q: PROBLEMA
Nota: 65537 e il piu grande numero primo conosciuto della forma22
n+ 1 (in questo caso n = 4). Per questa caratteristica viene
comunemente usato come esponente pubblico. Al tempo stesso e(a) abbastanza grande (b) primo (c) in forma tale da velocizzaresquare and multiply
![Page 114: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/114.jpg)
Sicurezza
Risalire da Me a M conoscendo e e n? Serve d
Risalire a d conoscendo e e n? Serve φ(n)
Risalire a φ(n) conoscendo n? Servono p e q
![Page 115: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/115.jpg)
Sicurezza
Risalire da Me a M conoscendo e e n? Serve d
Risalire a d conoscendo e e n? Serve φ(n)
Risalire a φ(n) conoscendo n? Servono p e q
Se si e sicuri che nessuno riesca a fattorizzare n, allora il sistemapuo considerarsi sicuro.
![Page 116: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/116.jpg)
Sicurezza
Risalire da Me a M conoscendo e e n? Serve d
Risalire a d conoscendo e e n? Serve φ(n)
Risalire a φ(n) conoscendo n? Servono p e q
Se si e sicuri che nessuno riesca a fattorizzare n, allora il sistemapuo considerarsi sicuro.
Il PROBLEMA: Se non si conosce un metodo per fattorizzare unnumero di 150 cifre, come faccio a costruire due numeri primi di150 cifre?
![Page 117: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/117.jpg)
Sicurezza
Risalire da Me a M conoscendo e e n? Serve d
Risalire a d conoscendo e e n? Serve φ(n)
Risalire a φ(n) conoscendo n? Servono p e q
Se si e sicuri che nessuno riesca a fattorizzare n, allora il sistemapuo considerarsi sicuro.
Il PROBLEMA: Se non si conosce un metodo per fattorizzare unnumero di 150 cifre, come faccio a costruire due numeri primi di150 cifre?
SOLUZIONE Usare numeri che sono primi con probabilitaarbitrariamente alta (per capirci, 99.9999999999999 per cento)
![Page 118: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/118.jpg)
Esperimento 11
Considerare due numeri primi molto grandi:
p :=NextPrime(10150 + 321412043120372103472104721047120412304712034712304712412)q := NextPrime(p + 100000)
![Page 119: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/119.jpg)
Esperimento 11
Considerare due numeri primi molto grandi:
p :=NextPrime(10150 + 321412043120372103472104721047120412304712034712304712412)q := NextPrime(p + 100000)
Calcolarne il prodotto n
![Page 120: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/120.jpg)
Esperimento 11
Considerare due numeri primi molto grandi:
p :=NextPrime(10150 + 321412043120372103472104721047120412304712034712304712412)q := NextPrime(p + 100000)
Calcolarne il prodotto n
Provare a fattorizzare n con il comando Factorization
![Page 121: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/121.jpg)
Esperimento 11
Considerare due numeri primi molto grandi:
p :=NextPrime(10150 + 321412043120372103472104721047120412304712034712304712412)q := NextPrime(p + 100000)
Calcolarne il prodotto n
Provare a fattorizzare n con il comando Factorization
Usereste questa chiave a tutela della vostra riservatezza e delvostro denaro?
![Page 122: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/122.jpg)
Esperimento 11
Considerare due numeri primi molto grandi:
p :=NextPrime(10150 + 321412043120372103472104721047120412304712034712304712412)q := NextPrime(p + 100000)
Calcolarne il prodotto n
Provare a fattorizzare n con il comando Factorization
Usereste questa chiave a tutela della vostra riservatezza e delvostro denaro?
Provare con questo algoritmo:trovato:=false; i:=1;while not trovato do
m:=n + i2;if IsSquare(m) then
trovato:=true; bool,t:=IsSquare(m); t;P:=t-i; P; Q:=t+i; Q;
end if;i:=i+1;
end while;
![Page 123: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/123.jpg)
Cosa e successo?
Idea dell’algoritmo: per tentativi provare a controllare se percaso
n+ i2 e un quadrato perfetto (test veloce)
![Page 124: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/124.jpg)
Cosa e successo?
Idea dell’algoritmo: per tentativi provare a controllare se percaso
n+ i2 e un quadrato perfetto (test veloce)
In tal caso da n + i2 = t2 segue
n = t2 − i2 = (t − i) · (t + i)
![Page 125: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/125.jpg)
Cosa e successo?
Idea dell’algoritmo: per tentativi provare a controllare se percaso
n+ i2 e un quadrato perfetto (test veloce)
In tal caso da n + i2 = t2 segue
n = t2 − i2 = (t − i) · (t + i)
Secondo voi, quali sono le chiavi deboli per questo algoritmo?
![Page 126: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/126.jpg)
Chiavi deboli
L’algoritmo appena visto si chiama Algoritmo di Fermat, eabbiamo visto che ha successo nel caso in cui p e q sianorelativamente vicini
![Page 127: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/127.jpg)
Chiavi deboli
L’algoritmo appena visto si chiama Algoritmo di Fermat, eabbiamo visto che ha successo nel caso in cui p e q sianorelativamente vicini
Ne esistono altri di algoritmi di fattorizzazione cherisultano veloci se p e q hanno determinate proprieta
![Page 128: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/128.jpg)
Chiavi deboli
L’algoritmo appena visto si chiama Algoritmo di Fermat, eabbiamo visto che ha successo nel caso in cui p e q sianorelativamente vicini
Ne esistono altri di algoritmi di fattorizzazione cherisultano veloci se p e q hanno determinate proprieta
Un altro esempio di chiave debole e quella in cui p− 1 o q− 1si fattorizzano in tanti fattori primi piccoli
![Page 129: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/129.jpg)
Chiavi deboli
L’algoritmo appena visto si chiama Algoritmo di Fermat, eabbiamo visto che ha successo nel caso in cui p e q sianorelativamente vicini
Ne esistono altri di algoritmi di fattorizzazione cherisultano veloci se p e q hanno determinate proprieta
Un altro esempio di chiave debole e quella in cui p− 1 o q− 1si fattorizzano in tanti fattori primi piccoli
Per questo si tende a scegliere p = 2p1 + 1 e q = 2q1 + 1 conp1 e q1 primi
![Page 130: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/130.jpg)
Chiavi deboli
L’algoritmo appena visto si chiama Algoritmo di Fermat, eabbiamo visto che ha successo nel caso in cui p e q sianorelativamente vicini
Ne esistono altri di algoritmi di fattorizzazione cherisultano veloci se p e q hanno determinate proprieta
Un altro esempio di chiave debole e quella in cui p− 1 o q− 1si fattorizzano in tanti fattori primi piccoli
Per questo si tende a scegliere p = 2p1 + 1 e q = 2q1 + 1 conp1 e q1 primi
Pare che una percentuale rilevante (compresa fra 1 e 10 percento) delle chiavi RSA sia debole
![Page 131: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/131.jpg)
Funzioni hash
L’hash (o digest) di un file ha gli stessi scopi dell’impronta digitaledi un individuo.
Sintetizza un individuo/file in un formato unico (160 bit per ifile)
Si ottiene con relativa facilita
Praticamente impossibile data un’impronta digitale, risalire alfile/individuo
Praticamente impossibile dato un file/individuo, trovarne unaltro con la stessa impronta
Praticamente impossibile trovare due file/individui con lastessa impronta
![Page 132: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/132.jpg)
Perche c’e bisogno di una funzione hash?
Integrita dei dati. Trasferimenti file di grosse dimensioni(E-mule, torrent, etc).
![Page 133: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/133.jpg)
Perche c’e bisogno di una funzione hash?
Integrita dei dati. Trasferimenti file di grosse dimensioni(E-mule, torrent, etc).
Autenticazione di un documento. Si calcola l’impronta delfile ottenuto combinando documento e chiave simmetrica.
![Page 134: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/134.jpg)
Perche c’e bisogno di una funzione hash?
Integrita dei dati. Trasferimenti file di grosse dimensioni(E-mule, torrent, etc).
Autenticazione di un documento. Si calcola l’impronta delfile ottenuto combinando documento e chiave simmetrica.
Firma digitale. Non si firma l’intero documento, ma la suaimpronta.
![Page 135: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/135.jpg)
Perche c’e bisogno di una funzione hash?
Integrita dei dati. Trasferimenti file di grosse dimensioni(E-mule, torrent, etc).
Autenticazione di un documento. Si calcola l’impronta delfile ottenuto combinando documento e chiave simmetrica.
Firma digitale. Non si firma l’intero documento, ma la suaimpronta.
Per questi scopi e fondamentale che sia praticamente impossibiletrovare due file con la stessa hashUna funzione hash deve essere resistente alle collisioni
![Page 136: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/136.jpg)
Un modello ideale
La funzione hash e calcolata da un oracolo in modo totalmenteoscuro, che nessuno conosce. Casuale ma riproducibile.
![Page 137: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/137.jpg)
Un modello ideale
La funzione hash e calcolata da un oracolo in modo totalmenteoscuro, che nessuno conosce. Casuale ma riproducibile.
Si cerca di riprodurre per quanto possibile il modello oracolocasuale.
![Page 138: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/138.jpg)
Un modello ideale
La funzione hash e calcolata da un oracolo in modo totalmenteoscuro, che nessuno conosce. Casuale ma riproducibile.
Si cerca di riprodurre per quanto possibile il modello oracolocasuale.
In tutti i nostri computer esistono algoritmi che simulano talemodello. Il piu utilizzato al momento e SHA1. SHA=Secure HashAlgorithmFCIV - md5, sha1 nomefile.con.path in Windows, sha1sum nomefile in Linux
![Page 139: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/139.jpg)
Un modello ideale
La funzione hash e calcolata da un oracolo in modo totalmenteoscuro, che nessuno conosce. Casuale ma riproducibile.
Si cerca di riprodurre per quanto possibile il modello oracolocasuale.
In tutti i nostri computer esistono algoritmi che simulano talemodello. Il piu utilizzato al momento e SHA1. SHA=Secure HashAlgorithmFCIV - md5, sha1 nomefile.con.path in Windows, sha1sum nomefile in Linux
SHA1 calcola un’impronta di 160 bit
Perche proprio 160 bit sono necessari per un impronta?
![Page 140: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/140.jpg)
Il paradosso del compleanno
In una classe di 23 alunni la probabilita che ve ne siano 2 conla stessa data di nascita supera il 50 per cento
![Page 141: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/141.jpg)
Il paradosso del compleanno
In una classe di 23 alunni la probabilita che ve ne siano 2 conla stessa data di nascita supera il 50 per cento
In una classe di 40 alunni supera l’85 per cento
![Page 142: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/142.jpg)
Il paradosso del compleanno
In una classe di 23 alunni la probabilita che ve ne siano 2 conla stessa data di nascita supera il 50 per cento
In una classe di 40 alunni supera l’85 per cento
Teorema 4
Sia h una funzione casuale, associata ad un file/individuo, che puoassumere M valori. Sia dato un insieme di
√2M ln 2 file/individui.
Allora la probabilita di trovare due file/individui a cui e associato lostesso valore supera il 50 per cento
![Page 143: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/143.jpg)
Il paradosso del compleanno
In una classe di 23 alunni la probabilita che ve ne siano 2 conla stessa data di nascita supera il 50 per cento
In una classe di 40 alunni supera l’85 per cento
Teorema 4
Sia h una funzione casuale, associata ad un file/individuo, che puoassumere M valori. Sia dato un insieme di
√2M ln 2 file/individui.
Allora la probabilita di trovare due file/individui a cui e associato lostesso valore supera il 50 per cento
Se l’hash ha k bit, i possibili esiti di un hash sono 2k .Pertanto in un insieme di circa
√2k = 2k/2 file sarebbe
abbastanza probabile trovare una collisione. Per questomotivo, ad esempio, un hash di 80 bit non sarebbe sicuro.
![Page 144: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/144.jpg)
Dimostrazione del paradosso del compleanno
Si consideri un insieme di n individui. La probabilita ditrovarne due con lo stesso compleanno e
P = 1− 365 − 1
365· 365− 2
365· · · 365 − (n − 1)
365.
![Page 145: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/145.jpg)
Dimostrazione del paradosso del compleanno
Si consideri un insieme di n individui. La probabilita ditrovarne due con lo stesso compleanno e
P = 1− 365 − 1
365· 365− 2
365· · · 365 − (n − 1)
365.
O anche
P = 1− (1− 1
365) · (1− 2
365) · · · (1− (n − 1)
365).
![Page 146: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/146.jpg)
Dimostrazione del paradosso del compleanno
Si consideri un insieme di n individui. La probabilita ditrovarne due con lo stesso compleanno e
P = 1− 365 − 1
365· 365− 2
365· · · 365 − (n − 1)
365.
O anche
P = 1− (1− 1
365) · (1− 2
365) · · · (1− (n − 1)
365).
Per capirci qualcosa occorre considerare che per numeri xvicini allo zero si ha
1− x ∼ e−x
![Page 147: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/147.jpg)
Dimostrazione del paradosso del compleanno
Si consideri un insieme di n individui. La probabilita ditrovarne due con lo stesso compleanno e
P = 1− 365 − 1
365· 365− 2
365· · · 365 − (n − 1)
365.
O anche
P = 1− (1− 1
365) · (1− 2
365) · · · (1− (n − 1)
365).
Per capirci qualcosa occorre considerare che per numeri xvicini allo zero si ha
1− x ∼ e−x
Pertanto approssimiamo P come segue
P ∼ e−1/365 · e−2/365 · e−3/365 · · · e−(n−1)/365
![Page 148: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/148.jpg)
P ∼ e−1+2+...+(n−1)
365 = e−12 ·(n−1)·(n−2)
365
![Page 149: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/149.jpg)
P ∼ e−1+2+...+(n−1)
365 = e−12 ·(n−1)·(n−2)
365
Eseguendo il logaritmo di ambo i membri
lnP ∼ −n2 − 3n + 2
2 · 365
![Page 150: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/150.jpg)
P ∼ e−1+2+...+(n−1)
365 = e−12 ·(n−1)·(n−2)
365
Eseguendo il logaritmo di ambo i membri
lnP ∼ −n2 − 3n + 2
2 · 365
Ulteriore approssimazione: n2 − 3n + 2 ∼ n2. Pertanto
lnP ∼ − n2
2 · 365
![Page 151: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/151.jpg)
P ∼ e−1+2+...+(n−1)
365 = e−12 ·(n−1)·(n−2)
365
Eseguendo il logaritmo di ambo i membri
lnP ∼ −n2 − 3n + 2
2 · 365
Ulteriore approssimazione: n2 − 3n + 2 ∼ n2. Pertanto
lnP ∼ − n2
2 · 365Da qui segue l’asserto: per P = 1/2 basta n = 23.
![Page 152: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/152.jpg)
P ∼ e−1+2+...+(n−1)
365 = e−12 ·(n−1)·(n−2)
365
Eseguendo il logaritmo di ambo i membri
lnP ∼ −n2 − 3n + 2
2 · 365
Ulteriore approssimazione: n2 − 3n + 2 ∼ n2. Pertanto
lnP ∼ − n2
2 · 365Da qui segue l’asserto: per P = 1/2 basta n = 23.
In generale, se abbiamo M esiti (es. 2160 per SHA1) allora peravere P = 1/2 occorre
ln 1/2 · 2 ·M ∼ −n2 ⇒ n ∼√2 · ln 2 ·M
![Page 153: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/153.jpg)
Quale proprieta delle derivate abbiamo usato?
Si veda fooplot.com
![Page 154: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/154.jpg)
Il Teorema del Quinto A
![Page 155: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/155.jpg)
Il Teorema del Quinto A
Esperimento: scrivere tutti gli elementi invertibili di Zn:
![Page 156: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/156.jpg)
Il Teorema del Quinto A
Esperimento: scrivere tutti gli elementi invertibili di Zn:
n = 10 1, 3, 7, 9n = 15 1, 2, 4, 7, 8, 11, 13, 14n = 22 1, 3, 5, 7, 9, 13, 15, 17, 19, 21
![Page 157: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/157.jpg)
Il Teorema del Quinto A
Esperimento: scrivere tutti gli elementi invertibili di Zn:
n = 10 1, 3, 7, 9n = 15 1, 2, 4, 7, 8, 11, 13, 14n = 22 1, 3, 5, 7, 9, 13, 15, 17, 19, 21
Osservazione: la somma degli elementi invertibili di Zn edivisibile per n
![Page 158: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/158.jpg)
Il Teorema del Quinto A
Esperimento: scrivere tutti gli elementi invertibili di Zn:
n = 10 1, 3, 7, 9n = 15 1, 2, 4, 7, 8, 11, 13, 14n = 22 1, 3, 5, 7, 9, 13, 15, 17, 19, 21
Osservazione: la somma degli elementi invertibili di Zn edivisibile per n
Congettura: per ogni intero positivo n > 1,
∑
a∈Zn,MCD(a,n)=1
a = 0 (mod n)
![Page 159: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/159.jpg)
Dimostrazione:1 Se MCD(a, n) = 1 allora anche MCD(n − a, n) = 1. Infatti
ogni divisore d di n − a e n sarebbe un divisore di −a e quindidi a
2 Siano a1, . . . , as sono gli elementi di Zn primi con n e minori din/2. Allora tutti gli elementi di Zn primi con n sono
a1, . . . , as , n − a1, . . . , n− as
3 Pertanto la somma totale e uguale a
a1+ . . .+ as +n− a1+ . . .+n− as = n+ . . .+n = 0 (mod n)
![Page 160: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/160.jpg)
Dimostrazione:1 Se MCD(a, n) = 1 allora anche MCD(n − a, n) = 1. Infatti
ogni divisore d di n − a e n sarebbe un divisore di −a e quindidi a
2 Siano a1, . . . , as sono gli elementi di Zn primi con n e minori din/2. Allora tutti gli elementi di Zn primi con n sono
a1, . . . , as , n − a1, . . . , n− as
3 Pertanto la somma totale e uguale a
a1+ . . .+ as +n− a1+ . . .+n− as = n+ . . .+n = 0 (mod n)
Teorema 5
Per ogni intero positivo n > 1,
∑
a∈Zn,MCD(a,n)=1
a = 0 (mod n)
![Page 161: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/161.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
![Page 162: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/162.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
![Page 163: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/163.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
![Page 164: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/164.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
Firma del documento: F = Dd (mod n) ∈ Zn
![Page 165: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/165.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
Firma del documento: F = Dd (mod n) ∈ Zn
Documento firmato: (D,F ) con F = Dd (mod n)
![Page 166: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/166.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
Firma del documento: F = Dd (mod n) ∈ Zn
Documento firmato: (D,F ) con F = Dd (mod n)Verifica della firma:
F e = D (mod n) ???
![Page 167: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/167.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
Firma del documento: F = Dd (mod n) ∈ Zn
Documento firmato: (D,F ) con F = Dd (mod n)Verifica della firma:
F e = D (mod n) ???
Il punto chiave e che se F e = D (mod n), allora (F e)d = Dd
(mod n) e quindi per il Teorema di Eulero F = Dd (mod n).
![Page 168: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/168.jpg)
La firma digitale
Idea: la firma di un documento consiste nel mascherare ildocumento con la propria chiave privata
Firma digitale RSA: chiave pubblica di Alice (n, e), chiaveprivata (p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare: D ∈ Zn
Firma del documento: F = Dd (mod n) ∈ Zn
Documento firmato: (D,F ) con F = Dd (mod n)Verifica della firma:
F e = D (mod n) ???
Il punto chiave e che se F e = D (mod n), allora (F e)d = Dd
(mod n) e quindi per il Teorema di Eulero F = Dd (mod n).Ma solo Alice conosce d
![Page 169: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/169.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
![Page 170: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/170.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
![Page 171: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/171.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
Se ho due documenti firmati da Alice, diciamo (D1,F1) e(D2,F2), e faccio finta di essere Alice e spedisco(D1 · D2,F1 · F2), allora la verifica della firma e accettata:
(F1 · F2)e = F e1 · F e
2 = D1 · D2 (mod n)
![Page 172: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/172.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
Se ho due documenti firmati da Alice, diciamo (D1,F1) e(D2,F2), e faccio finta di essere Alice e spedisco(D1 · D2,F1 · F2), allora la verifica della firma e accettata:
(F1 · F2)e = F e1 · F e
2 = D1 · D2 (mod n)
D1 · D2 probabilmente e un documento senza senso.
![Page 173: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/173.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
Se ho due documenti firmati da Alice, diciamo (D1,F1) e(D2,F2), e faccio finta di essere Alice e spedisco(D1 · D2,F1 · F2), allora la verifica della firma e accettata:
(F1 · F2)e = F e1 · F e
2 = D1 · D2 (mod n)
D1 · D2 probabilmente e un documento senza senso.
La facilita di ottenere firme false e un problema
![Page 174: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/174.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
Se ho due documenti firmati da Alice, diciamo (D1,F1) e(D2,F2), e faccio finta di essere Alice e spedisco(D1 · D2,F1 · F2), allora la verifica della firma e accettata:
(F1 · F2)e = F e1 · F e
2 = D1 · D2 (mod n)
D1 · D2 probabilmente e un documento senza senso.
La facilita di ottenere firme false e un problemaUn altro problema e che un documento/file non sempre puo nonessere rappresentato da un elemento di Zn (es.: DVD PS3)
![Page 175: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/175.jpg)
Falsificazioni firma digitale RSA
Se faccio finta di essere Alice e spedisco (F e ,F ), allora laverifica della firma e accettata:
F e = F e (mod n)
F e probabilmente e un documento senza senso.
Se ho due documenti firmati da Alice, diciamo (D1,F1) e(D2,F2), e faccio finta di essere Alice e spedisco(D1 · D2,F1 · F2), allora la verifica della firma e accettata:
(F1 · F2)e = F e1 · F e
2 = D1 · D2 (mod n)
D1 · D2 probabilmente e un documento senza senso.
La facilita di ottenere firme false e un problemaUn altro problema e che un documento/file non sempre puo nonessere rappresentato da un elemento di Zn (es.: DVD PS3)Soluzione: utilizzo funzioni hash
![Page 176: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/176.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
![Page 177: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/177.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
![Page 178: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/178.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
Si calcola l’hash di D con l’algoritmo SHA1, diciamo H(D), elo si interpreta come elemento di Zn
![Page 179: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/179.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
Si calcola l’hash di D con l’algoritmo SHA1, diciamo H(D), elo si interpreta come elemento di Zn
Firma del documento: F = H(D)d (mod n) ∈ Zn
![Page 180: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/180.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
Si calcola l’hash di D con l’algoritmo SHA1, diciamo H(D), elo si interpreta come elemento di Zn
Firma del documento: F = H(D)d (mod n) ∈ Zn
Documento firmato: (D,F ) con F = H(D)d (mod n)
![Page 181: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/181.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
Si calcola l’hash di D con l’algoritmo SHA1, diciamo H(D), elo si interpreta come elemento di Zn
Firma del documento: F = H(D)d (mod n) ∈ Zn
Documento firmato: (D,F ) con F = H(D)d (mod n)
Verifica della firma:
F e = H(D) (mod n) ???
![Page 182: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/182.jpg)
Firma digitale SHA1-RSA
Firma digitale SHA1-RSA: chiave pubblica (n, e), chiave privata(p, q, d) con n = p · q e e · d = 1 (mod φ(n))
Documento da firmare da Alice: D, file di dimensionepraticamente arbitraria
Si calcola l’hash di D con l’algoritmo SHA1, diciamo H(D), elo si interpreta come elemento di Zn
Firma del documento: F = H(D)d (mod n) ∈ Zn
Documento firmato: (D,F ) con F = H(D)d (mod n)
Verifica della firma:
F e = H(D) (mod n) ???
Il punto chiave e che se F e = H(D) (mod n), allora(F e)d = H(D)d (mod n) e quindi per il Teorema di EuleroF = H(D)d (mod n). Ma solo Alice conosce d .
![Page 183: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/183.jpg)
Falsificazioni di SHA1-RSA?
(F e ,F ) non e accettato perche F non e l’hash di F .Dovrei trovare un file che abbia come impronta F , ma comesappiamo e praticamente impossibile.
![Page 184: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/184.jpg)
Falsificazioni di SHA1-RSA?
(F e ,F ) non e accettato perche F non e l’hash di F .Dovrei trovare un file che abbia come impronta F , ma comesappiamo e praticamente impossibile.
Allo stesso modo, non e piu accettata (D1D2,F1F2) perche
H(D1D2)d 6= H(D1)
dH(D2)d = F1F2
![Page 185: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/185.jpg)
Firma digitale in pratica
www.digitpa.gov.it“Per dotarsi di firma digitale necessario rivolgersi aicertificatori accreditati autorizzati da DigitPA chegarantiscono lidentita dei soggetti che utilizzano la firmadigitale.”
![Page 186: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/186.jpg)
Firma digitale in pratica
www.digitpa.gov.it“Per dotarsi di firma digitale necessario rivolgersi aicertificatori accreditati autorizzati da DigitPA chegarantiscono lidentita dei soggetti che utilizzano la firmadigitale.”
http://www.digitpa.gov.it/firma-digitale/certificatori-accreditati/certificatori-attiviEsempio forse piu conosciuto in TV: Aruba.(http://www.pec.it/FirmaDigitale.aspx)
![Page 187: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/187.jpg)
Firma digitale in pratica
www.digitpa.gov.it“Per dotarsi di firma digitale necessario rivolgersi aicertificatori accreditati autorizzati da DigitPA chegarantiscono lidentita dei soggetti che utilizzano la firmadigitale.”
http://www.digitpa.gov.it/firma-digitale/certificatori-accreditati/certificatori-attiviEsempio forse piu conosciuto in TV: Aruba.(http://www.pec.it/FirmaDigitale.aspx)
http://www.digitpa.gov.it/firma-elettronica/liste-certificatiOgni Autorita di Certificazione e a sua volta Certificata dalGoverno/Unione Europea.
![Page 188: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/188.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
![Page 189: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/189.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
![Page 190: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/190.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
![Page 191: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/191.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di Alice
![Page 192: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/192.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di AliceIl certificato di Alice. Il certificato C di Alice contiene la chiavepubblica n, e di Alice, ed e firmato dalla Certification Authority
![Page 193: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/193.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di AliceIl certificato di Alice. Il certificato C di Alice contiene la chiavepubblica n, e di Alice, ed e firmato dalla Certification Authority
Quando Alice vuole firmare un file inserisce la chiavetta eavvia il programma di firma inserendo il PIN. Il risultato e unfile .p7m che contiene:
![Page 194: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/194.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di AliceIl certificato di Alice. Il certificato C di Alice contiene la chiavepubblica n, e di Alice, ed e firmato dalla Certification Authority
Quando Alice vuole firmare un file inserisce la chiavetta eavvia il programma di firma inserendo il PIN. Il risultato e unfile .p7m che contiene:
Il documento D (esempio file .doc o file .pdf)
![Page 195: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/195.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di AliceIl certificato di Alice. Il certificato C di Alice contiene la chiavepubblica n, e di Alice, ed e firmato dalla Certification Authority
Quando Alice vuole firmare un file inserisce la chiavetta eavvia il programma di firma inserendo il PIN. Il risultato e unfile .p7m che contiene:
Il documento D (esempio file .doc o file .pdf)La firma F = SHA1(D)d (mod n)
![Page 196: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/196.jpg)
Firma digitale in pratica
Alice si reca fisicamente dalla Certification Authority.
La Certification Authority riconosce l’identita di Alice e lerilascia una chiavetta usb e un PIN.
La chiavetta USB contiene:
La chiave privata p, q, d di AliceIl certificato di Alice. Il certificato C di Alice contiene la chiavepubblica n, e di Alice, ed e firmato dalla Certification Authority
Quando Alice vuole firmare un file inserisce la chiavetta eavvia il programma di firma inserendo il PIN. Il risultato e unfile .p7m che contiene:
Il documento D (esempio file .doc o file .pdf)La firma F = SHA1(D)d (mod n)Il certificato C di Alice (quindi la chiave pubblica di Alice e lafirma della Certification Authority)
![Page 197: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/197.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
![Page 198: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/198.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
Controlla la firma del certificato: deve essere sicuro che ilcertificato C sia stato firmato da una Certification Authority.Il browser si collega al sito governativo dove e sicuro di trovarela VERA chiave pubblica della Certification Authority. Talechiave pubblica e cio che serve per controllare l’autenticita delcertificato.
![Page 199: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/199.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
Controlla la firma del certificato: deve essere sicuro che ilcertificato C sia stato firmato da una Certification Authority.Il browser si collega al sito governativo dove e sicuro di trovarela VERA chiave pubblica della Certification Authority. Talechiave pubblica e cio che serve per controllare l’autenticita delcertificato.
Dopo aver controllato il certificato, Bob e sicuro che la chiavepubblica di Alice e quella riportata nel certificato stesso.Quindi
![Page 200: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/200.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
Controlla la firma del certificato: deve essere sicuro che ilcertificato C sia stato firmato da una Certification Authority.Il browser si collega al sito governativo dove e sicuro di trovarela VERA chiave pubblica della Certification Authority. Talechiave pubblica e cio che serve per controllare l’autenticita delcertificato.
Dopo aver controllato il certificato, Bob e sicuro che la chiavepubblica di Alice e quella riportata nel certificato stesso.Quindi
Calcola l’impronta di D =contratto.pdf: SHA1(D)
![Page 201: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/201.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
Controlla la firma del certificato: deve essere sicuro che ilcertificato C sia stato firmato da una Certification Authority.Il browser si collega al sito governativo dove e sicuro di trovarela VERA chiave pubblica della Certification Authority. Talechiave pubblica e cio che serve per controllare l’autenticita delcertificato.
Dopo aver controllato il certificato, Bob e sicuro che la chiavepubblica di Alice e quella riportata nel certificato stesso.Quindi
Calcola l’impronta di D =contratto.pdf: SHA1(D)Calcola SHA1(D)e
![Page 202: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/202.jpg)
Firma digitale in pratica
Bob riceve il file contratto.pdf.p7m, che consiste diD =contratto.pdf, F , CQuali passi compie per verificare la firma di Alice?
Controlla la firma del certificato: deve essere sicuro che ilcertificato C sia stato firmato da una Certification Authority.Il browser si collega al sito governativo dove e sicuro di trovarela VERA chiave pubblica della Certification Authority. Talechiave pubblica e cio che serve per controllare l’autenticita delcertificato.
Dopo aver controllato il certificato, Bob e sicuro che la chiavepubblica di Alice e quella riportata nel certificato stesso.Quindi
Calcola l’impronta di D =contratto.pdf: SHA1(D)Calcola SHA1(D)e
Controlla che SHA1(D)e = F
![Page 203: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/203.jpg)
Codici autocorrettori
Da Wikipedia Error Detection and Correction:Many communication channels are subject to channel noise, and thus errors may be introduced during transmissionfrom the source to a receiver. Error detection techniques allow detecting such errors, while error correction enablesreconstruction of the original data.Development of error-correction codes was tightly coupled with the history of deep-space missions due to theextreme dilution of signal power over interplanetary distances, and the limited power availability aboard spaceprobes. Whereas early missions sent their data uncoded, starting from 1968 digital error correction wasimplemented.The Reed-Muller code was well suited to the noise the spacecraft was subject to (approximately matching a bellcurve), and was implemented at the Mariner spacecraft for missions between 1969 and 1977.The Voyager 1 and Voyager 2 missions, which started in 1977, were designed to deliver color imaging amongstscientific information of Jupiter and Saturn. This resulted in increased coding requirements, and thus thespacecraft were supported by (optimally Viterbi-decoded) convolutional codes that could be concatenated with anouter Golay (24,12,8) code.The Voyager 2 probe additionally supported an implementation of a Reed-Solomon code: the concatenatedReed-Solomon-Viterbi (RSV) code allowed for very powerful error correction, and enabled the spacecraft’s extendedjourney to Uranus and Neptune.
The CCSDS currently recommends usage of error correction codes with performance similar to the Voyager 2 RSV
code as a minimum. Concatenated codes are increasingly falling out of favor with space missions, and are replaced
by more powerful codes such as Turbo codes or LDPC codes.
![Page 204: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/204.jpg)
Un esempio elementare
N 0 0E 0 1O 1 0S 1 1
![Page 205: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/205.jpg)
Un esempio elementare
N 0 0 0E 0 1 1O 1 0 1S 1 1 0
![Page 206: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/206.jpg)
Un esempio elementare
N 0 0 0 0 0E 0 1 1 1 0O 1 0 1 0 1S 1 1 0 1 1
![Page 207: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/207.jpg)
Un esempio elementare
N 0 0 0 0 0E 0 1 1 1 0O 1 0 1 0 1S 1 1 0 1 1
Un qualunque errore puo essere corretto automaticamente!
![Page 208: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/208.jpg)
Un esempio elementare
N 0 0 0 0 0E 0 1 1 1 0O 1 0 1 0 1S 1 1 0 1 1
Un qualunque errore puo essere corretto automaticamente!
Idea: Codificare le parole del nostro linguaggio in modo tale chesiano tutte abbastanza diverse fra loro
![Page 209: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/209.jpg)
Alfabeto: Zp, p primo
![Page 210: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/210.jpg)
Alfabeto: Zp, p primo
Parole del codice: alcune sequenze di n lettere dell’alfabeto
![Page 211: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/211.jpg)
Alfabeto: Zp, p primo
Parole del codice: alcune sequenze di n lettere dell’alfabeto
Distanza di due parole:
d((a1, a2, . . . , an), (b1, b2, . . . , bn)) = #{i = 1, . . . , n | ai 6= bi}
![Page 212: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/212.jpg)
Alfabeto: Zp, p primo
Parole del codice: alcune sequenze di n lettere dell’alfabeto
Distanza di due parole:
d((a1, a2, . . . , an), (b1, b2, . . . , bn)) = #{i = 1, . . . , n | ai 6= bi}
Esempi:
d((1, 2, 3), (0, 2, 3)) = 1, d((0, 2, 3, 0), (1, 2, 1, 0)) = 2
![Page 213: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/213.jpg)
Alfabeto: Zp, p primo
Parole del codice: alcune sequenze di n lettere dell’alfabeto
Distanza di due parole:
d((a1, a2, . . . , an), (b1, b2, . . . , bn)) = #{i = 1, . . . , n | ai 6= bi}
Esempi:
d((1, 2, 3), (0, 2, 3)) = 1, d((0, 2, 3, 0), (1, 2, 1, 0)) = 2
Teorema 6
Se la distanza minima di due parole del codice e D, allora il codicecorregge fino a (D − 1)/2-errori
![Page 214: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/214.jpg)
Codici di Reed-Solomon (versione soft)
Si fissano k < m < p, con p primo
![Page 215: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/215.jpg)
Codici di Reed-Solomon (versione soft)
Si fissano k < m < p, con p primo
Alfabeto: Zp, lunghezza delle parole: m
![Page 216: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/216.jpg)
Codici di Reed-Solomon (versione soft)
Si fissano k < m < p, con p primo
Alfabeto: Zp, lunghezza delle parole: m
Ogni parola e associata a un polinomio
f (X ) = a0 + a1X + a2X2 + . . .+ akX
k
a coefficienti in Zp e grado minore o uguale di k :
C = {(f (1), f (2), . . . f (m)) | f polinomio con deg(f ) ≤ k}
![Page 217: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/217.jpg)
Codici di Reed-Solomon (versione soft)
Si fissano k < m < p, con p primo
Alfabeto: Zp, lunghezza delle parole: m
Ogni parola e associata a un polinomio
f (X ) = a0 + a1X + a2X2 + . . .+ akX
k
a coefficienti in Zp e grado minore o uguale di k :
C = {(f (1), f (2), . . . f (m)) | f polinomio con deg(f ) ≤ k}
Teorema 7 (Ruffini)
Un polinomio di grado k non nullo ha al massimo k radici.
![Page 218: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/218.jpg)
Esempio:
p = 7,m = 4, k = 2
![Page 219: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/219.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
![Page 220: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/220.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
Quanti errori si possono correggere con un codice diReed-Solomon?
![Page 221: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/221.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
Quanti errori si possono correggere con un codice diReed-Solomon?
d((f (1), f (2), . . . , f (m)), (g(1), g(2), . . . , g(m)))
e uguale a m meno il numero di valori i = 1, . . . ,m per cui(f − g)(i) = 0
![Page 222: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/222.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
Quanti errori si possono correggere con un codice diReed-Solomon?
d((f (1), f (2), . . . , f (m)), (g(1), g(2), . . . , g(m)))
e uguale a m meno il numero di valori i = 1, . . . ,m per cui(f − g)(i) = 0
Quante radici al massimo puo avere f − g?
![Page 223: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/223.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
Quanti errori si possono correggere con un codice diReed-Solomon?
d((f (1), f (2), . . . , f (m)), (g(1), g(2), . . . , g(m)))
e uguale a m meno il numero di valori i = 1, . . . ,m per cui(f − g)(i) = 0
Quante radici al massimo puo avere f − g? k
![Page 224: La matematica dell’orologiogiuliet/MIPLezione1.pdfLa matematica dell’orologio Un’aritmetica inusuale: I numeri del nostro ambiente sono: 0,1,2,...,11 e corrispondono alle ore](https://reader033.vdocumenti.com/reader033/viewer/2022042308/5ed4ca0bfd1f950b814dfd3b/html5/thumbnails/224.jpg)
Esempio:
p = 7,m = 4, k = 2
Esempi di parole:
f (X ) = 1 + X 2 → (1 + 12, 1 + 22, 1 + 32, 1 + 42) = (2, 5, 3, 3)
f (X ) = 1 + X + X 2 → (3, 0, 6, 0)
. . . . . .
Quanti errori si possono correggere con un codice diReed-Solomon?
d((f (1), f (2), . . . , f (m)), (g(1), g(2), . . . , g(m)))
e uguale a m meno il numero di valori i = 1, . . . ,m per cui(f − g)(i) = 0
Quante radici al massimo puo avere f − g? k
Pertanto D ≥ m − k e quindi il codice di Reed-Solomon correggefino a (m − k)/2 errori!