# 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

## 1 Answer

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.

-
Thanks for that answer! Really helped me :) And yes, I am aware of public keys being that small are very insecure, but I'm just using them as an example in my paper. –  Janman Dec 8 '12 at 14:38
@fgrieu Oh, yes, you are correct, stupid me. I will fix the answer. –  Thomas Dec 9 '12 at 0:25
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
But if e is too small, and you don't pad correctly, it will be insecure. –  Antimony Dec 10 '12 at 7:11