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.

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?

share|improve this question
    
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
3  
@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 1

up vote 6 down vote accepted

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.

share|improve this answer
1  
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

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.