Geek asks and answers

RSA Algorithm Key Generation

I am currently struggling with the RSA encryption algorithm .

My problem is in the generation public/private, here are my steps:

 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)

This raises the problem: I need to find a single integer e s q < e < fi(n). This integer must have some primitiveness.

My question is: should e really be the main one (cannot be divided by any number except itself or 1) OR primarily WITH fi(n) (gcd(e, fi(n)) = 1)OR OR both?

I really have some problems figuring this out (my source explicitly states that the Euclidean algorithm (gcd) is necessary, but since English is not my native language, I have some problems with mathematical English)

Probably a dumb question, but I could not find a clear explanation for this (at least clear enough for me).

Thanks for reading, even more for the answer.

+5
source share
1 answer

The encryption metric eshould be mutually simple with phi(n), that is gcd(e,phi(n)) = 1. This condition is necessary, because otherwise you will not be able to build (through the extended Euclidean algorithm) an exponent d(decryption), such as e*d = 1 mod phi(n).

+3
source

More articles:


All Articles