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 (F_n = 2²ⁿ⁺¹) e di Mersenne (M_n=2ⁿ-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, y appartenenti a Z_n 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

a^p-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.