RSA
Si scelgono a caso due numeri primi p e q
p. es.
- p = 13
- q = 7
Si calcola il loro prodotto n = pq, chiamato modulo, e il prodotto φ(n) = (p – 1)(q – 1) (φ(x) è il numero degli interi coprimi a x)
p. es
- n = 91
- φ(n) = 72
Si sceglie un numero coprimo a φ(n) e più piccolo di esso
p. es
- e = 7
Si calcola il numero d in modo che de % φ(n) = 1
p. es
- d = 31
La chiave pubblica è (n, e) e la chiave privata è (n, d)
p. es.
- pub = (91, 7)
- priv = (91, 31)
La forza dell'algoritmo sta nel fatto che per calcolare d da e (o viceversa) non basta la conoscenza di n ma serve il numero φ ( n ) = ( p − 1 ) ( q − 1 ) , e che il suo calcolo richiede tempi molto elevati; infatti fattorizzare in numeri primi (cioè scomporre un numero nei suoi divisori primi) è un'operazione computazionalmente costosa.