Crittografia/La matematica che devi conoscere

Indice del libro

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 primiModifica

Definizione di numero primoModifica

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'AritmeticaModifica

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 EuclideModifica

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.