# Is there a way to systematically calculate the public exponent $e$ in RSA?

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$.

• 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. – CodesInChaos Nov 18 '14 at 20:40
• @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. :) – orange Nov 18 '14 at 20:45
• 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. – CodesInChaos Nov 18 '14 at 20:49

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$.

• 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). – Chris Peikert Nov 20 '14 at 0:19
• @Chris Peikert: Indeed. I'll edit the answer accordingly. – fgrieu Nov 20 '14 at 3:21

@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 !

• 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. – fgrieu Nov 19 '14 at 19:43
• 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). – fgrieu Nov 19 '14 at 20:51
• Ok, agreed: those two methods are a bit longer to explain but they do speed up calculation. – Cédric Van Rompay Nov 20 '14 at 9:34