1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Technically $e$ is the public exponent, and $e$ together with $n$ make up the full public key. $\endgroup$ – Nayuki Apr 1 '18 at 23:39
4
$\begingroup$

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.

$\endgroup$

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.