Crittografia/La matematica che devi conoscere
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 aritmetica 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
modificaDefinizione di numero primo
modifica- 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
modifica- 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
modifica- 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:
modifica- Lemma 36:
- --> Siano x, y 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.