# RSA Key generation Public exponent too big

I'm currently writing a paper about RSA (a self-chosen subject). I'm writing about the key-generation in RSA, and I have problem finding the public exponent e.

I have chosen p = 61 and q = 53.

Then I determined my modulus n = p ⋅ q = 3233

and my phi(n) = (p-1)(q-1) = 3120.

What bothers me is that when I try to generate the public exponent e using CrypTool (given the same parameters), it gives me e = 2^16+1 = 65537 BUT I thought e had to be less that phi(n) = (p-1)(q-1) (according to this source). Why is it OK to break this rule? Or is the CrypTool faulty?

• Use $e = 3$, it should work. But this small primes offer no security at all, so only use these as an example, and please make clear that in real-live systems the primes must be much larger. – Paŭlo Ebermann Dec 8 '12 at 14:21
• @PaŭloEbermann $e = 3$ won't work here, $\varphi{(n)}$ is a multiple of 3. – Thomas Dec 9 '12 at 0:32
• For an introduction, $e=17$ will do: it is actually used, and the audience will grab that $x^{17}\bmod n$ can be computed as $((((x^2)^2)^2)^2)⋅x\bmod n$; will be able to do that for small $x$; then find that for bigger $x$ they want to $((((x^2\bmod n)^2\bmod n)^2\bmod n)^2\bmod n)⋅x\bmod n$. Also, the audience may be less intimidated by $1=e⋅d\bmod\operatorname{lcm}(p−1,q−1)$ than by $d=e^{-1}\bmod{φ(n)}$, with the extra benefit for the former that it is the industry standard. – fgrieu Dec 9 '12 at 12:30

The $2^{16} + 1$ exponent is really meant for use in real life systems, in which public keys are expected to be considerably larger than that. I guess CrypTool assumes this is the case, as you would expect, really.
That said, if $\gcd{(e, \varphi{(n)})} = 1$, then $gcd{(e ~ \mathrm{mod} ~ \varphi{(n)}, \varphi{(n)})} = 1$ by definition, so such an $e$ will still work regardless, as noted by fgrieu in the comments.
• RSA "works" as long as $n=p⋅q$ with $p$, $q$ distinct odd primes, $e$ coprime with $p−1$ and $q−1$ (thus $e$ odd), and $e⋅d≡1\pmod{\operatorname{lcm}(p−1,q−1)}$; then, $x↦x^e\bmod n$ and $x↦x^d\bmod n$ are reverse permutations of $[0,n−1]$. It is immaterial that $e<φ(n)$, though usual $e$ are smalller, and PKCS#1v2.1 wants $e<n$. Any $e'≡e\pmod{\operatorname{lcm}(p−1,q−1)}$ is equivalent to $e$, and odd. The first RSA-like cryptosystem used $e=n$. [Take five] – fgrieu Dec 9 '12 at 12:36