Generazione chiave dell'algoritmo RSA

Question

Attualmente sono alle prese con RSA encryption algorythm.

Il mio problema si trova al public/private generazione chiave, qui sono i miei passi:

1. -Generate 2 prime numbers p, q with p > q and nbBits(p) == nbBits(q) 
      using the miller-rabin algorythm this was done succesfully 
2. -compute n = p*q 
3. -compute fi(n) = (p-1)*(q-1) 

Qui viene il problema: ho bisogno di trovare un intero e con q < e < fi(n). Questo numero intero deve avere una sorta di primalità.

La mia domanda è: deve essere primale (non può essere diviso per un numero diverso da se stesso o 1) OR primale CON fi(n) (gcd(e, fi(n)) = 1) O entrambi?

ho davvero alcune questioni immaginando che la (mia fonte afferma chiaramente è necessario l'Euclide algoritmo (MCD), ma dal momento che l'inglese non è la mia lingua madre ho qualche difficoltà con l'inglese matematica)

Probabilmente uno stupido domanda, ma non ho trovato una spiegazione chiara (almeno abbastanza chiara per me).

Grazie per la lettura, ancora di più per la risposta.

Answer 1

L'esponente di crittografia e deve essere coprimi con phi(n), ovvero gcd(e,phi(n)) = 1. Questa condizione è necessaria perché altrimenti, non sarà possibile costruire (tramite l'algoritmo esteso di Euclid) un esponente d (l'esponente di decrittografia) tale che e*d = 1 mod phi(n).