4
$\begingroup$

I'm learning RSA in one of my classes and we were given a problem:

$p = 5$, $q = 11$

I have done the following steps:

$n = 5 \cdot 11 = 55$
$\phi = (5-1)\cdot(11-1) = 40$

I know that to find $e$ we have to find an integer co-prime with $\phi$, where $\phi$ is $40$ and $\gcd(e,40) = 1$.

Is there an algorithm I can use by hand that can give me $e$? I know there can be numerous values. The method the professor has shown is to just enumerate each prime and find the first divisible into the totient $\phi$. I assume he will give us small numbers in the exam but still, doing it by trial and error can be time consuming.

I understand one can use extended Euclids algorithm to find the inverse of $e$, which I can do provided I know what $e$ is.

I just struggle with finding $e$.

$\endgroup$
  • $\begingroup$ You can factor phi and choose a prime that isn't such a factor. Slow for properly sized numbers, trivial for something like 40. But even with trial division using 3, 5, 7 etc. you will find a divisor within a minute as long as n is small. Inverting e will certainly take longer than finding e. $\endgroup$ – CodesInChaos Nov 18 '14 at 20:40
  • $\begingroup$ @CodesInChaos Can you show me via example? I seem to learn better like that. Totally get what you mean as I found a couple of co-primes for example 3 in this instance within seconds, but looking for alternative ways if numbers are bigger. :) $\endgroup$ – orange Nov 18 '14 at 20:45
  • $\begingroup$ If the modulus is so large that you don't find an e via trival division in less than a minute, it's so big that you won't be able to do the rest of RSA. For example no four-digit number is co-prime to 3, 5, 7, 11 and 13. $\endgroup$ – CodesInChaos Nov 18 '14 at 20:49
9
$\begingroup$

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA.

What's an acceptable public exponent $e$?

The public exponent in RSA should be an integer $e>1$ with $\gcd(e,p-1)=\gcd(e,q-1)=1$, so that $e$ will have an inverse both $\pmod{p-1}$ and $\pmod{q-1}$; or, equivalently, such that $e$ will have an inverse $\pmod{\phi(p\cdot q)}$. This insures that $e$ is odd, for we have assumed that $p$ and $q$ are.

Also, $e$ must not reveal so much information (about $p$ or $q$, or $\phi(p\cdot q)$) that it significantly simplifies factorization of $N$. This rules out some non-iterative constructive methods like $e=\max(p,q)$, or $e=(p-1)(q-1)+1$, or $e=(p-1)(q-1)-1$ (which do insure that $\gcd(e,p-1)=\gcd(e,q-1)=1$, assuming $\min(p,q)>3$ for the last formula).

Some RSA definitions, most notably PKCS#1, require $e<N$. There is no stated rationale for that requirement.

An old, straightforward (but non standard) method to chose $e$

If we ignore the requirement that $e<N$, one straightforward method is to set $e=N$, which satisfies all other requirements provided that $\min(p,q)$ does not divide $\max(p,q)-1$ (which does not hold in the example in the question, but is extremely likely for large random primes $p$ and $q$; and is certain if $2\min(p,q)>\max(p,q)$, or if $p$ and $q$ have exactly the same bit size, or if $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for some integer $k$; all of which are common requirements for $p$ and $q$, listed by increasing selectivity).

This choice of $N$ as the public exponent historically is the first method that was considered, before RSA got named (C. Cocks, A Note on "non-secret encryption", classified GCHQ note dated 20 November 1973, re-typeset here). It is demonstrably as safe as can be with respect to attacks factoring $N$ (or equivalent to that), since we do not reveal anything beyond $N$, which we make public anyway; however, as noted by Chris Peikert, the RSA problem (of finding $x$ knowing $x^e\bmod N$) might be easier for this choice of $e$ (we have no indication of that).

A PKCS#1-conformant (if not standard) method to chose $e$ from $N$

An idea is to select $e$ as a prime with $N/3\le e<N$; such $e$ is acceptable, since it is a prime at least $\max(p,q)$, thus co-prime to $p-1$ and $q-1$. We can pick the smallest prime at least $N/3$, or the highest prime less than $N$. For small $N$ we can restrict to $e$ in a table of pre-computed primes: $7$, $17$, $41$, $97$, $257$, $769$, $1153$, $2113$, $4129$, $12289$, $18433$, $40961$, $65537$, $163841$, $270337$, $786433$.. (I have picked values with at most 3 bits set in their binary representation, which slightly simplifies raising to the $e$th power). Since these choices of $e$ do not depend on the factorization of $N$, they can't help factorize $N$ (but we have no idea if that's a bad or good choice w.r.t. the RSA problem).

The above methods are uncommon, for reasons explained below. To my knowledge, standard and safe methods to chose $e$ somewhat use trial an error in the choice of $e$ from $p$ and $q$, or the choice of $p$ and $q$ from $e$; and most such methods have additional objectives.

Should $e$ have other characteristics?

There is incentive not to chose $e$ too large, for a large $e$ slows down the public-key operation (about proportionally to the bit size of $e$) with no tangible benefit provided proper padding is used. That's one good reason not to use any of the above methods. FIPS 186-4, appendix B.3.1 puts the limit at $e<2^{256}$. In fact, $e\ge2^{32}$ has become uncommon, for it has caused interoperability hurdles with some RSA implementations (formerly including that bundled in Windows); and unduly long waits for users of Smart Cards.

Some standards/security authorities set a lower bound on $e$, typically $e>2^{16}$. That's of debated rationality when using a proper padding scheme.

It is common to choose $e$ prime, because this decreases the amount of trial and error, for odds that a prime $e$ and much larger prime $p$ meet $\gcd(e,p-1)=1$ are $(e-2)/(e-1)$ (thus quickly converging to $1$ when $e$ grows) if either $e$ or $p$ is random; while odds are lower if we remove the condition that $e$ is prime (the odds become mostly independent of the magnitude of $e$; as a hint to that, odds that two large integers each uniformly chosen below some limit $m$ are coprime converges to $6/\pi^2\approx60.8\%$ when $m$ grows). As an aside, if $e$ is composite, revealing it as part of the public key arguably reveals even so slightly more information about $p$ and $q$ (or about $\phi(N)$ or $\lambda(N)$) than if $e$ was a large prime, for there are less possible $p$ and $q$ knowing $e$.

There is also incentive to choose $e$ of the form $2^i+1$, because that's allowing the fastest computation of $x^e\bmod N$ for a given size of $e$ (only $i$ modular squaring and one modular multiplication are required). If we combine with $e$ prime, that leaves the Fermat primes $F_j=2^{(2^j)}+1$ with $0\le j\le4$ as the only candidates (it is conjectured that there exists no other Fermat prime, and known that there are none of manipulable size).

Choice of $p$ and $q$ before search of $e$ by trial and error

RSA key generation as in a textbook typically choose $p$ and $q$ first. An unobjectionable method to then chose $e$ is to try values of $e$ that are moderate random primes in some suitably large interval, until one $e$ is found such that $e$ does not divide $p-1$ or $q-1$. Such $e$ is acceptable w.r.t. both $p$ and $q$ (assumed much larger, random and independent primes) with odds $(e-2)^2/(e-1)^2$, thus high for all but very small $e$. If we specify a large enough interval for $e$ (e.g. $2^{16}<e<2^{17}$) and the choice of $p$ and $q$ is without relations to the primes in that interval, it is not even necessary to insure that the $e$ tested are distinct to find a suitable $e$ quickly, with overwhelming odds.

Some (including the teacher in the question) select $e$ as the lowest prime at least some fixed minimum (chosen no less than $3$) dividing neither $p-1$ nor $q-1$ (or not dividing $\phi(N)$). Notice that doing so often reveals some information about $\phi(N)$: if in a large collection of public keys known to have been generated by the same device we see keys where $1/4$ of the $e$ are $3$ (thus $25\%$ of $e$), $9/16$ of the other $e$ are $5$ (thus about $42.2\%$ of $e$), $25/36$ of the other $e$ are $7$ (thus about $22.8\%$ of $e$), and generally $(r-2)^2/(r-1)^2$ of the other $e$ are $r$ for $r$ the successive primes starting from $11$, we have reverse-engineered the choice of $e$, and know that for the few public keys of the form $(N,23)$, $\phi(N)$ and $\lambda(N)$ are a multiple of $3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19$, which can be used to speed-up a straight brute-force search of these quantities (it is likely that there is at least one such public key if we gathered $27600$ of these). It might give a feeling of discomfort, although we do not know that such knowledge can significantly improve one's ability to find $\phi(N)$ or $\lambda(N)$ knowing the public key, or otherwise derive a working private key, or factor $N$ (rationale: these goals are equivalent, factorization of $N$ is by far the most efficient avenue known to reach any of these goals, and we do not know how to use a known moderate divisor of $\phi(N)$ or $\lambda(N)$ to speed up that factorization).

We can also choose $e$ as an (odd) random integer (not necessarily prime) in some similar interval until $\gcd(e,p-1)=\gcd(e,q-1)=1$. It will require significantly more trials, but success is also virtually insured; and by the same reasoning as above, whatever little extra information we leak is not a worrying security issue.

Hand computation of small $e$ for moderate $p$ and $q$ expressed in decimal

We can easily test divisibility by the primes $5$, $3$, $11$, $37$, $101$. We'll pick the first $e$ in this list that is suitable. Odds that none is suitable are only $0.0068\%$.

If neither of $p$ and $q$ has a $1$ or $6$ as its rightmost decimal digit, then neither $p-1$ nor $q-1$ is divisible by $5$, and we select $e=5$. That won't do for the example in the question (because $q=11$ ends in $1$), but is enough for $p=14627$, $q=15959$ (because neither $7$ nor $9$ are $1$ or $6$).

Otherwise, we sum the digits in $p$; subtract $1$; recursively sum the digits in the result, until the result is single-digit; if that digit is not divisible by $3$, $p-1$ is not, and we do the same test for $q$; if we find that $q-1$ is not divisible by $3$, we select $e=3$. That's the case for $p=5$, $q=11$ in the question (because neither $4$, nor $1$, are divisible by $3$).

Otherwise, we use similar techniques for $e=11$, $37$, and $101$; the divisibility rules are explained here.

Choice of $e$ before search for $p$ and $q$ by trial and error

Real-world RSA implementations tend to choose $e$ first, typically because

  • very commonly, $e=2^{16}+1=65537$ is required, because that's the minimum value recognized as acceptable by all security authorities, thus unobjectionable and well-supported;
  • sometime $e=3$ is required, because that gives the best speed of the public-key RSA operation, with no known drawback if proper padding methods are used;
  • having a fixed $e$ simplifies the transmission of the public key; in that case, one of the Fermat primes $F_j=2^{(2^j)}+1$ is typical.

With $e$ prime, we can pick a prime $p$ such that $p-1$ is not a multiple of $e$, and it insures $\gcd(e,p-1)=1$. The contrary has odds only $1/(e-1)$ for random prime $p$, and that's rare enough to be mildly hard to test for the very popular $e=2^{16}+1$.

An unobjectionable method reducing guesswork (especially for the smaller $e$ like $3$) is to chose $e$ prime, then when it comes to the choice of $p$ chose a secret $f$ uniformly random with $0<f<e-1$, then only explore candidate primes of the form $p=(2k+(f\bmod 2))\cdot e+f+1$, which insure $p$ is odd and $\gcd(e,p-1)=1$. $f$ should be randomly drawn again when it comes to the choice of $q$.

$\endgroup$
  • 1
    $\begingroup$ This is a great answer, however I don't think the following claim is justified: "$e=N$ is demonstrably as safe as can be, since we do not reveal anything beyond $N$, which we make public anyway." This is true for the problem of factoring $N$ (because revealing $e=N$ gives no further information), but not necessarily for the RSA problem of finding $e$th roots mod $N$ (which is what really matters). The RSA problem could be easier for $e=N$ than for other choices of $e$ (say, random under some distribution). $\endgroup$ – Chris Peikert Nov 20 '14 at 0:19
  • $\begingroup$ @Chris Peikert: Indeed. I'll edit the answer accordingly. $\endgroup$ – fgrieu Nov 20 '14 at 3:21
1
$\begingroup$

@CodesInChaos is right, here is an example of his method on your data :

$40 = 2^3 5$ so I pick, say $e=3$, which is for sure coprime with $40$.

Actually $e=3$ is a common value in some implementations of RSA (see @fgrieu giant response about that)

By chance (or did you teacher foresaw it ?) Extended Euclidian Algo is pretty fast here :

$40 = 13 \times 3 + 1$ : END

We got Bézout's Identity : $40 + (-13) \times 3 = 1 = gcd(40,3)$

thus your decryption key is $27 = -13 \bmod 40$

To see if this works, lets encrypt/decrypt a number (here 15):

>>> 15**3 % 55
20
>>> 20**27 % 55
15

It works !

$\endgroup$
  • $\begingroup$ You means $40 = 2^3\cdot5$. This method involves factoring $p-1$ and $q-1$ (and choosing a small odd factor not appearing in this factorization). By hand, this is utterly impractical for even moderate $p$ and $q$. Try it with $p=14627, q=15959$. Then compare to the method I'll add in my giant answer. $\endgroup$ – fgrieu Nov 19 '14 at 19:43
  • $\begingroup$ Also: if we do hand calculation, and after checking $p\ne q$, we should use $d=e^{-1}\bmod (p-1)(q-1)/2$, or $d=e^{-1}\bmod((p-1)(q-1)/\gcd(p-1,q-1))$, or $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, which are more practical formulas to compute a working $d$. Notice how $d=3^{-1}\bmod 20=7$ is easier to compute than $d=3^{-1}\bmod 40=27$ is, and $20^7\bmod55$ is much easier to compute than $20^{27}\bmod55$ is (but equal). $\endgroup$ – fgrieu Nov 19 '14 at 20:51
  • 1
    $\begingroup$ Ok, agreed: those two methods are a bit longer to explain but they do speed up calculation. $\endgroup$ – Cédric Van Rompay Nov 20 '14 at 9:34

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.