4
$\begingroup$

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?

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

1 Answer 1

Reset to default
7
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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