1
$\begingroup$

For simplicity I choose two small primes for p and q.

p=3
q=11
n=33
Φ(n)=20

Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?

$\endgroup$
  • $\begingroup$ I thought of protecting this question (as mod), but I've decided to leave it open as beginners may well get a very good explanation during their courses. However, before posting please make sure that your answer is complete, self contained and not a direct copy of one of the other answers. $\endgroup$ – Maarten Bodewes Dec 22 '19 at 17:35
2
$\begingroup$

This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the GCD test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose appropriate $p$ and $q$. These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e^\text{th}$ power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.

$\endgroup$
  • 1
    $\begingroup$ Might want to be more specific about how to safely pick a prime $e$ above $\max(p,q)$ that you're going to publish… $\endgroup$ – Squeamish Ossifrage Nov 5 '19 at 4:13
  • $\begingroup$ (otherwise Coppersmith may return to haunt you) $\endgroup$ – Squeamish Ossifrage Nov 5 '19 at 7:37
2
$\begingroup$

For RSA to work, we require that its public key function $x\mapsto x^e\bmod(p\;q)$ be a reversible mapping on $[0,n)$. With $p$ and $q$ coprime, that's equivalent (by the CRT) to $x\mapsto x^e\bmod p$ being a reversible mapping on $[0,p)$ and $x\mapsto x^e\bmod q$ being a reversible mapping on $[0,q)$. With $p$ and $q$ prime, that's equivalent to $e$ being coprime with both $p-1$ and $q-1$.

We could choose for $e$ the smallest integer greater than 1 that is coprime with both $p-1$ and $q-1$ (implying $e$ odd and at least $3$ for large primes $p$ and $q$). That's not too long to find by trial and error. However, it is customary to use $e$ at least 16-bit so that $e\ge65537$. This is mandated by some standards (sometime: for encryption only), and justified if we use an ad-hoc padding (e.g. RSAES-PKCS1-v1_5) because it mitigates padding oracle attacks to some degree.

The most common practice is to choose $e=65537$, and then choose $p$ with $p\bmod e\ne1$, which ensures $e$ is coprime with both $p-1$, since $e$ is prime; same for $q$.

When using a secure padding, and no rule forbids it, we can choose $e=3$, and then choose primes of the form $3k+2$.

$\endgroup$
-4
$\begingroup$

My RSA generator in Python was a function written as follows:

def rsa_gen(p,q):

    n = p*q
    lambda_n = lcm(p-1, q-1)

    e_list = []
    e = 2

    while e < lambda_n:
        if math.gcd(e, lambda_n) == 1:
            e_list.append(e)
            e = e + 1
        else:
        e = e + 1

    e = random.choice(e_list)**
    d = inverse(e, lambda_n)

    return (n, e, d)

Obviously, I took the brute force approach for any pre-determined primes P, Q.

Basically, I initialize an array/list as empty, e as 2 since 1 and 0 are not appropriate. Then I run a co-prime check for all values 2 to lambda and populate the list/array with them. Then I pick randomly from that list to get my e.

Regards

$\endgroup$
  • $\begingroup$ Do you know why $e \in \{ 3,5,17,257,65537 \}$ in generally? $\endgroup$ – kelalaka Nov 3 '19 at 22:54
  • 5
    $\begingroup$ For p,q of barely secure size (about 1500 bits) if you turn all the matter in the universe into computer memory using only one atom per bit (which is much better than any known technology can achieve) it will be too small to store this list by a factor of over 1e370, a number larger than fits in a Stack comment. Plus you'll need many more universes to power your computation, and even if massively parallelized (and current python doesn't parallelize at all!) it will almost certainly take many times longer than the universe will exist. Therefore, I don't recomment this approach. $\endgroup$ – dave_thompson_085 Nov 4 '19 at 2:29
  • $\begingroup$ We're generally not looking for code fragments here, Aaron. When we're talking about methods, we presume mathematical constructs and their explanations. Even code fragments should be explained that way; we like to know why they follow a specific scheme rather than just how. That said, thanks for at least explaining the "how", that's often missing from answers, even on StackOverflow. $\endgroup$ – Maarten Bodewes Nov 5 '19 at 14:33

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.