RSA Algorithm key generation
encryption, key, rsa
Solution
The encryption exponent `e` needs to be coprime with `phi(n)`, that is, `gcd(e,phi(n)) = 1`. This condition is necessary because otherwise, you won't be able to construct (via Euclid's extended algorithm) an exponent `d` (the decryption exponent) such that `e*d = 1 mod phi(n)`.
Problem
I'm currently struggling with RSA encryption algorythm. My problem is located at the `public/private` key generation ,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) ``` Here comes the trouble : i need to find one integer e with `q < e < fi(n)`. This integer needs to have some sort of primality. My question being : does e has to be primal (cannot be divided by any number else than itself or 1) OR primal WITH `fi(n) (gcd(e, fi(n)) = 1)` OR both? I really have some issues figuring that out (my source clearly states the Euclide algorythm(gcd) is needed, but since English isn't my native language i have some trouble with mathematical English) Probably a dumb question, but i couldn't find a clear explanation of it (at least clear enough for me). Thanks for reading, even more for answering.