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?

  • $\begingroup$ 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. $\endgroup$ Dec 8 '12 at 14:21
  • 3
    $\begingroup$ @PaŭloEbermann $e = 3$ won't work here, $\varphi{(n)}$ is a multiple of 3. $\endgroup$
    – Thomas
    Dec 9 '12 at 0:32
  • $\begingroup$ 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. $\endgroup$
    – 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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Janman
    Dec 8 '12 at 14:38
  • $\begingroup$ @fgrieu Oh, yes, you are correct, stupid me. I will fix the answer. $\endgroup$
    – Thomas
    Dec 9 '12 at 0:25
  • 1
    $\begingroup$ 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] $\endgroup$
    – fgrieu
    Dec 9 '12 at 12:36
  • $\begingroup$ But if e is too small, and you don't pad correctly, it will be insecure. $\endgroup$
    – Antimony
    Dec 10 '12 at 7:11

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.