Given a private key $k$ and a modulus $n=pq$, where $p \neq q$ are two very large prime numbers, we find the value of Euler's Totient Function $\varphi(n)=(p-1)(q-1)$. The public key $K$ is given by the multiplicative inverse of the private key, modulo $\varphi(n)$, i.e. $kK \equiv 1 \bmod \varphi(n)$.This is often written as $K = k^{-1} \pmod{\varphi(n)}$.

The extended Euclidean algorithm can by used to find $K$. Assuming that $k$ and $\varphi(n)$ are coprime, i.e. $\gcd(k,\varphi(n))=1$, we can find integers $s$ and $t$ for which $ks + \varphi(n)t=1$. The multiplicative inverse of $k$, i.e. the public key $K$, will be given by $s$.

Assuming that $n=pq$ is a very large number, say 1024 bit or larger, it follows that $\varphi(n)=(p-1)(q-1)$ will also be a very large number.

How "expensive" is it, or how long would it take, to compute the multiplicative inverse of $k \pmod{\varphi(n)}$ using the extended Euclidean algorithm? How does this "expense"/time compare to factorise $n$?

  • 1
    $\begingroup$ If you know $k$ and $\varphi(n)$, computing the multiplicative inverse of $k$ $\pmod{\varphi(n)}$ is only a few times more costly than division of $\varphi(n)$ by $k$; that is, in practice, inexpensive. It you only know $k$ and $n$, computing the multiplicative inverse of $k$ $\pmod{\varphi(n)}$ is about as hard as factoring $n$. $\endgroup$ – fgrieu Jan 5 '17 at 20:59
  • $\begingroup$ The fact that the EEA is cheap (or equivalently, that computing GCDs and modular inverses is easy) is absolutely fundamental, and you should look into it seriously with a good computational number theory textbook. $\endgroup$ – fkraiem Jan 5 '17 at 21:16
  • $\begingroup$ By the way, if you only know the modulus $n$, then the EEA is irrelevant since you do not know $\varphi(n)$ (so you cannot run the EEA on it). $\endgroup$ – fkraiem Jan 5 '17 at 21:54
  • $\begingroup$ @fkraiem But I'm the private key holder, so I know $p$ and $q$ where $n=pq$. $\endgroup$ – Fly by Night Jan 6 '17 at 15:37
  • $\begingroup$ Right, then the previous comment applies. $\endgroup$ – fkraiem Jan 6 '17 at 19:44

If you have two positive integers $a>b>0$ with $n_1,n_2$ bits respectively, you need $O(n_1n_2)$ running time to compute integers $d,s,t$ such that $d=\gcd(a,b)$ and $d=as+bt$ (this is theorem 4.4 of Victor Shoup book). In your case (since you know $\phi(N))$ set $a=K, b=\phi(N)$ to compute $k$ (as you desrcibed) in time $O( len(\phi((N))\cdot len(k) ).$

|improve this answer|||||
  • $\begingroup$ Thank you very much for your answer. What is $\operatorname{len}(k)$? $\endgroup$ – Fly by Night Jan 6 '17 at 17:59
  • $\begingroup$ the binary length. $\endgroup$ – 111 Jan 6 '17 at 18:05
  • $\begingroup$ Thanks for that. What would the running time for the factorisation of $n$ be in terms of $\operatorname{len}(p)$ and $\operatorname{len}(q)$, where $n=pq$, be? $\endgroup$ – Fly by Night Jan 6 '17 at 18:21
  • $\begingroup$ If you have as input the private and public key and you want to factor N, there is a probabilistic polynomial algorithm which will give you the factors with probability ≈1/2. Is that you want? $\endgroup$ – 111 Jan 6 '17 at 18:41
  • $\begingroup$ Let's say I'm a public key holder (so I know the modulus $n$ and public key $K$). How hard is it to factorise $n$? The motivation for my question is (quite naively): using RSA is "easy" and uses the EEA which depends on division of very large numbers, but the "hard" problem of factorising is also a division problem. What is the relative difficulty of using the EEA to find the public key $K = k^{-1} \pmod{\varphi(n)}$ compared to factoring $n$ given $K$? $\endgroup$ – Fly by Night Jan 6 '17 at 21:15

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.