Crittografia/La matematica che devi conoscere: differenze tra le versioni
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 1: | Riga 1: | ||
{{crittografia}} |
|||
La matematica utilizzata nella crittanalisi è una matematica di base. |
La matematica utilizzata nella crittanalisi è una matematica di base. |
||
Tutte le operazioni utilizzate sono prevalentemente prodotti e divisioni. |
Tutte le operazioni utilizzate sono prevalentemente prodotti e divisioni. |
||
Riga 13: | Riga 14: | ||
== teoremi e definizioni dei numeri primi == |
|||
<big><big>'''TEOREMI e DEFINIZIONI dei NUMERI PRIMI:'''</big></big> |
|||
=== Definizione di numero primo === |
|||
: Un numero n (positivo) si dice primo se ha esattamente due divisori positivi distinti. |
: Un numero n (positivo) si dice primo se ha esattamente due divisori positivi distinti. |
||
: N.B.: Il numero <big>1</big> (uno) non è primo per comodità e convenzione. |
: N.B.: Il numero <big>1</big> (uno) non è primo per comodità e convenzione. |
||
Riga 22: | Riga 23: | ||
=== Teorema Fondamentale dell'Aritmetica === |
|||
: Un numero n (positivo) o è un numero primo o è un prodotto di primi. |
: Un numero n (positivo) o è un numero primo o è un prodotto di primi. |
||
Riga 29: | Riga 30: | ||
=== Teorema di Euclide === |
|||
: Esistono infiniti numeri primi. |
: Esistono infiniti numeri primi. |
||
Riga 40: | Riga 41: | ||
Per cifrari famosi, come ad esempio quello di Cesare, è molto utile, ma non necessario, conoscere il Piccolo Teorema di Fermat. |
Per cifrari famosi, come ad esempio quello di Cesare, è molto utile, ma non necessario, conoscere il Piccolo Teorema di Fermat. |
||
=== Piccolo teorema di Fermat: === |
|||
: '''Lemma 36:''' |
: '''Lemma 36:''' |
||
: --> Siano x , appartenenti a Z<sub>n</sub> con x ≠ y |
: --> Siano x , appartenenti a Z<sub>n</sub> con x ≠ y |
||
Riga 68: | Riga 69: | ||
è divisibile per n. Questo enunciato contiene il Piccolo Teorema di Fermat, in |
è divisibile per n. Questo enunciato contiene il Piccolo Teorema di Fermat, in |
||
quanto, per ogni numero primo p, si ha che φ(p)=p-1. |
quanto, per ogni numero primo p, si ha che φ(p)=p-1. |
||
[[Categoria:Crittografia|matematica che devi conoscere]] |
|||
{{Avanzamento|25%|1 maggio 2011}} |
{{Avanzamento|25%|1 maggio 2011}} |
Versione delle 18:35, 1 mag 2011
La matematica utilizzata nella crittanalisi è una matematica di base. Tutte le operazioni utilizzate sono prevalentemente prodotti e divisioni. Più complicati sono i concetti di fondo.
Ad esempio:
- Per poter costruire un algoritmo di crittografia a trasposizione è necessario introdurre il concetto di aritmetica modulare (o aritemtica dell'orologio).
Per creare algoritmi di crittanalisi più complessi come l'RSA, nella crittanalisi moderna vengono utilizzate operazioni sui numeri primi.
Importante è non utilizzare numeri primi particolari come i numeri primi di Fermat (Fn = 22n+1) e di Mersenne (Mn=2n-1).
teoremi e definizioni dei numeri primi
Definizione di numero primo
- Un numero n (positivo) si dice primo se ha esattamente due divisori positivi distinti.
- N.B.: Il numero 1 (uno) non è primo per comodità e convenzione.
Teorema Fondamentale dell'Aritmetica
- Un numero n (positivo) o è un numero primo o è un prodotto di primi.
- Per la dimostrazione di questo teorema si utilizza il principio di induzione.
Teorema di Euclide
- Esistono infiniti numeri primi.
Può essere utile conoscere i teoremi di:
- - Dirichlet
- - Wilson
- - Matijasevic
Per cifrari famosi, come ad esempio quello di Cesare, è molto utile, ma non necessario, conoscere il Piccolo Teorema di Fermat.
Piccolo teorema di Fermat:
- Lemma 36:
- --> Siano x , appartenenti a Zn con x ≠ y
- --> Dato a appartenente a Z*n coprimo con n
- --> ax e ay non sono ma tra loro congruenti modulo n
L’enunciato di questo teorema compare in una lettera indirizzata da Fermat
ad un amico. Esso afferma che, se p è un numero primo, ed a è un intero
positivo qualunque, allora il numero
ap-a
è divisibile per p. In realtà vale un risultato più forte: se p non divide a, allora
a p-1 – 1
è divisibile per p. La dimostrazione fu data nel 1736 da Eulero, che nel 1760 generalizzò il teorema. Egli introdusse la funzione φ, detta totiente: per ogni intero positivo n, indicò con φ(n) il numero di interi compresi fra 1 e n-1 che non hanno, con n, divisori comuni non banali. Egli provò che, per qualsiasi intero positivo a coprimo rispetto ad n il numero
a φ(n) - 1
è divisibile per n. Questo enunciato contiene il Piccolo Teorema di Fermat, in quanto, per ogni numero primo p, si ha che φ(p)=p-1.