How to find the public key in RSA?

Question

Finding the public key given the private key $d$ and the prime numbers $p$ and $q$.

$$p = 3092551601$$

$$q = 3490383433$$

$$d = 10719928016004921607$$

Since this is RSA, here is my thinking.

In order to find the public key $e$ it must satisfy this equation

$$d\cdot e=1 \mod \varphi(n)$$ Since I am looking for $e$, $$(e \cdot 10719928016004921607) \mod 10794190867245091200=1$$ However, after this step is where I am lost.

I tried using basic mathematics but it gives me the inverse of $d$. Plus, I don't think that using brute force is the right way to learn or understand this question.

Answer 1

You indeed need the inverse of $d$, but it's the so-called modular (multiplicative) inverse.

This can be done with the Extended Euclidean algorithm. You basically compute the greatest common divisor of $d$ and $\varphi(n)$ (you know already that it's going to be 1) and use the intermediate results to get the value of $e$.

The following simple Java program implements this algorithm, prints the result ($e = 8601051999309708343$) and proves it's indeed the multiplicative inverse (modulo $\varphi(n)$ of $d$.

List<BigInteger> q = new ArrayList<>(), r = new ArrayList<>(), s = new ArrayList<>(), t = new ArrayList<>();
q.add(BigInteger.ZERO);
r.add(new BigInteger("10719928016004921607"));
r.add(new BigInteger("10794190867245091200"));
s.add(BigInteger.ONE);
s.add(BigInteger.ZERO);
t.add(BigInteger.ZERO);
t.add(BigInteger.ONE);
int i = 0;
do {
    i++;
    BigInteger[] results = r.get(i - 1).divideAndRemainder(r.get(i));
    q.add(results[0]);
    r.add(results[1]);
    if (results[1].compareTo(BigInteger.ZERO) == 0) {
        break;
    }
    s.add(s.get(i - 1).subtract(q.get(i).multiply(s.get(i))));
    t.add(t.get(i - 1).subtract(q.get(i).multiply(t.get(i))));
} while (true);

BigInteger lastS = s.get(s.size() - 1);
System.out.println(lastS.mod(r.get(1)) + ", " + lastS.multiply(r.get(0)).mod(r.get(1)));

It takes 15 steps to get to this result, it's rather hard to do that by hand.