Crittografia/La matematica che devi conoscere

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search
Copertina

Parte I: Introduzione alla Crittografia

  1. Introduzione alla crittografia
  2. Storia della crittografia
  3. Concetti fondamentali

Parte II: Progettare cifrari

  1. Principi base nella progettazione
  2. Piccoli segreti nascondono segreti più grandi
  3. algoritmi aperti e il valore del Peer-Review
  4. Pensa come un crittoanalista
  5. La matematica che devi conoscere
  6. La sicurezza informatica non è solo la cifratura
  7. Un codice non violato non è necessariamente non violabile

Parte III: Violare cifrature

  1. I principi base nel violare cifrari
  2. Debolezze
  3. Attacchi
  4. Come furono violate le cifrature storiche

Parte IV: Usare cifrature

  1. Applicazioni della crittografia
  2. Cifrature classiche
  3. Cifrature contemporanee
  4. Protocolli

Parte V: La crittografia e la società

  1. La natura mutevole dell'uso della crittografia
  2. Crittografia, governi e leggi
  3. Aspettative dell'utente normale
  4. Snake Oil

Parte VI: Miscellanea

  1. Possibilità future
  2. Glossario dei termini
  3. Letture addizionali
  4. Appendice A: background matematico

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[modifica]

Definizione 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.