2

Consider a RSA group $Z_N$ for $N=pq$, where $p,q$ are large prime numbers. Under strong RSA assumption, can an adversary efficiently compute the inverse of a random element $z$ from $Z_N$ without access to $p,q, \phi(N)$? Mathematically does there exists efficient algorithm $\mathcal{A}$ s.t

$$ \mathbb{P}\left( z.u=1,\quad z \leftarrow Z_N,\; u=\mathcal{A}(x,N) \right) \geq \text{neglible}? $$

PS: I am learning cryptography so my notations are quite shaky.

Ella Rose
  • 19,386
  • 6
  • 52
  • 99
Vivek Bagaria
  • 125
  • 4
  • 1
    Welcome to crypto.stackexchange - How does the reference-request tag fit into your question? Are you hoping to find some kind of paper with the solution or ? If so then you may want to state that explicitly in your answer. – Ella Rose Feb 10 '19 at 20:43
  • @EllaRose: I was hoping to find a reference to lecture notes. – Vivek Bagaria Feb 10 '19 at 21:57

1 Answers1

4

Mathematically does there exists efficient algorithm $\mathcal{A}$

Yes; the Extended Euclidean algorithm can be used to efficiently compute multiplicative inverses modulo $N$, without knowledge of the factorization of $N$.

poncho
  • 138,335
  • 11
  • 217
  • 344
  • Addition: this works by using the Extended Euclidean algorithm to find the $(u,v)$ in [Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity) $u\,z+v\,N=1$. We do not need $v$, and that allows to reduce the cost by a small factor, see [this](https://crypto.stackexchange.com/a/54477/555). There's also a binary variant, see [this](https://crypto.stackexchange.com/a/54623/555). – fgrieu Feb 12 '19 at 10:51