I read some books talk about RSA cryptography but I did not understand something when choosing a public key $e$ Sometimes the condition is


Where $\phi(n) = p-1 * q-1$

also sometimes is

$e \in [{1,2,...,\phi(n)-1}]$

also sometimes is

$e$ should be prime number


Choose $p = 3\ and\ q = 11 $

Compute $n = p * q = 3 * 11 = 33 $ Compute $\phi(n) = (p - 1) * (q - 1) = 2 * 10 = 20$
Choose $e$ .here can choose e = 7 where 7 is prime number or I can choose $e=9$ where 9 is relatively prime to 20.

My question

Are both states right when choose 7 and 9. or not right .If no why???


There is no specific reason why $e$ is required to be a prime number. It must be relatively prime to $\phi(n)$ (otherwise we can't decrypt uniquely); however that is the only hard requirement. Assuming that 9 is relatively prime to $\phi(n)$, there is no reason why 9 can't be used as a public exponent.

However, selecting a prime value for $e$ does have this practical advantage; for prime $e$, then the requirement that it is relatively prime to $\phi(n)$ is equivalent to the statements that $p \ne 1 \pmod{e}$ and $q \ne 1 \pmod{e}$ (where $p$ and $q$ are the prime factors of $n$). If we use the common logic of selecting $e$ first, and then $p$ and $q$, this turns into a relatively simple additional criteria when doing prime selection.


Working with small primes for P and Q is difficult to provide good examples.

Normally primes have an advantage, as Poncho points out. However, in your case, when e=7 then d=3. When e=9 then d=9. Thereby not a good example where it would normally be fine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.