Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For simplicity I choose two small primes for p and q.

p=3
q=11
n=33
Φ(n)=20

Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the gcd test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose $q$ and $p$ appropriate. These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e$-th power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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