1
$\begingroup$

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing the factorization of $N$?

$\endgroup$
2
$\begingroup$

Yes, the problem of finding unknown random $x\in\mathbb Z_N$ given $N\in\mathbb N$, $u\in\mathbb N$ with $1<u\le\lceil\log_2N\rceil$, and $x^u$ computed in $\mathbb Z_N$, is believed hard unless the factorization of $N$ can be determined, which itself is believed hard for appropriately constructed RSA moduli $N$. Moreover, depending on $u$ and $N$, there might be several solutions with no way to tell the right one (if $u$ is odd and $N$ squarefree with no divisor up to $\lceil\log_2N\rceil$ then there is a single solution). Notice that I have excluded $u=1$ (which the question allows), for it makes finding $x$ trivial.

When $u$ is odd this is the RSA problem with small exponent, which is believed hard when the factorization of $N$ can't be determined (with the caveat that a usual definition of that problem asks that $N$ is squarefree and without small divisors).

When $u$ is $2$, this is the square root modulo unknown composite problem, which is believed hard when the factorization of $N$ can't be determined.

Ability to consistently solve both that square root problem and the RSA problem implies ability to find a solution to the question's problem, by writing $u$ as $e\cdot2^s$ with odd $e$, solving the RSA problem for exponent $e$, and solving the square root problem $s$ times.


Addition: this answer is for version 5 of the question. As correctly noted in another answer for an earlier version of the question, knowing that $N$ is a square does not make the problem easier if the factorization of $N$ remains unknown.


Further addition following comments:

  • It is easy to find the inverse of any given element of $\mathbb Z_N$ when its exists, using the Extended Euclidian algorithm.
  • It is hard to exhibit $a\in\mathbb Z_N$ that has no inverse modulo $N$, other than $0$ or a multiple of an easily found factor of $N$ (argument: if such an $a$ was found, then $\gcd(a,N)$ would be a non-trivial divisor of $N$ contributing towards finding the full factorization of $N$).
  • If $\gcd(u,N)=1$ (which we'll assume hereafter), it is thus easy to find non-negative integers $v$ and $k$ with $u\cdot v=k\cdot N+1$, otherwise said with $v\equiv u^{-1}\pmod N$.
  • It does follow that $\forall x\in\mathbb Z_N$, $(x^u)^v=x^{k\cdot N+1}=(x^N)^k\cdot x$.
  • That does not seem to help finding $x$, because we have nothing telling us that $x^N=1$; on the contrary, $x^N=1$ seldom holds when $x\ne 1$; in particular $x^N=1$ holds only for $x=1$ when $N$ is prime, since in this case: $\forall x\in\mathbb Z_N$, $x^N=x$ by Fermat's little theorem.
$\endgroup$
  • $\begingroup$ Does this imply that finding inverses mod $N=pq$ is also hard as long you don't know the factorization of $N$ $\endgroup$ – curious Apr 1 '15 at 8:05
  • 1
    $\begingroup$ @curious Not at all. Multiplicative inverses can easily be found using the extended Euclidean algorithm. $\endgroup$ – Aleph Apr 1 '15 at 8:09
  • $\begingroup$ @Aleph Then why finding $x \mod N$ from $x^u \mod N$ is difficult? You compute $v=u^{-1}$ and then $x= (x^{u})^v=x^{uu^{-1}} \mod N$ $\endgroup$ – curious Apr 1 '15 at 8:54
  • 1
    $\begingroup$ @curious Because $v \equiv u^{-1} \pmod {\varphi(N)}$, if $v, u$ and $\varphi(N)$ are coprime. Given $N$, it is assumed that $\varphi(N)$ cannot be found easily (this would be equivalent to factoring $N$). $\endgroup$ – Aleph Apr 1 '15 at 10:35
  • 1
    $\begingroup$ @curious The inverse you want (need) is modulo $\varphi(N)$, the one modulo $N$ has no relation with the one you want. They are completely different things. $\endgroup$ – Thomas Apr 1 '15 at 11:26
2
$\begingroup$

I'm not sure if this is what you meant, but computing arbitrary roots modulo a composite number IS the RSA-problem, which is considered hard.
I'm pretty sure that squaring the modulus won't make a difference in the hardness, as you still don't know the prime-factors, but don't think that it's "more" secure than with normal N, and it will certainly be slower due to the larger modulus.

$\endgroup$
  • $\begingroup$ RSA problem states that it is difficult to compute multiplicative inverses moduli $\phi(N)$ $\endgroup$ – curious Mar 31 '15 at 12:40
  • 1
    $\begingroup$ @curious, cited from Handbook of Applied Cryptography, page 98 chapter 3.3: "Definition the RSA problem (RSAP) is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e,(p-1)(q-1))=1, and an integer c, find an integer m such that m^e=c (mod n). In other words, the RSA problem is that of finding e-th roots modulo a composite integer n." $\endgroup$ – SEJPM Mar 31 '15 at 13:06
  • $\begingroup$ The solution to the RSA problem as you said is the inverse of $e$ moduli $\phi(N)=(p-1)(q-1)$. And it is believed that if the factorization $(p,q)$ is not known you cannot find the inverse. $\endgroup$ – curious Mar 31 '15 at 14:00
  • $\begingroup$ @curious Knowing the inverse is equivalent to knowing the factorization, since if you know $u$ and $u^{-1}$ modulo $\varphi(n)$ (or $\varphi(n^2)$) then the latter divides $u u^{-1} - 1$ and you are done. $\endgroup$ – Thomas Mar 31 '15 at 14:13
  • $\begingroup$ Yes but my concern is that i want the inverse not moduli $\phi(N^2)$ but $(N^2)$ $\endgroup$ – curious Mar 31 '15 at 14:16

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.