# 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. Nov 18, 2014 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. :) Nov 18, 2014 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. Nov 18, 2014 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. 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, 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} and $$2^{k-1/2} 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; 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}) 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, 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). Nov 20, 2014 at 0:19
• @Chris Peikert: Indeed. Answer edited accordingly.
– fgrieu
Nov 20, 2014 at 3:21
• So, in practice, e = 65537 is commonly used ? Also: You said e is usually between (2^16, 2^32) and e is usually within range (N/3, N), but N is usually >= 4096 bits. N/3 > 1365 bits, which is much larger than 2^32 I think. So, which part did I get wrong ?
– Eric
Jan 4 at 9:56
• @Eric: Yes, $e = 65537$ is commonly used, but does require to select $p$ and $q$ as a function of $e$. I did not suggest that $e$ is usually within range $(N/3,N)$. That's in fact unusual, and that's stated ("The above methods are uncommon"). This is included because the question asks "a way to systematically calculate the public exponent", and choosing $e$ as a prime in $(N/3,N)$ is a method that works regardless of how $p$ and $q$ have been chosen.
– fgrieu
Jan 4 at 10:35
• I've asked a question about choosing e, could u take a look crypto.stackexchange.com/q/103576/56409
– Eric
Jan 4 at 10:38

@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, 2014 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, 2014 at 20:51
• Ok, agreed: those two methods are a bit longer to explain but they do speed up calculation. Nov 20, 2014 at 9:34