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.