I am trying to solve the following problem:

Alice generates a RSA key $(n, \phi)$, she shares with Bob the value $n$, and $y = g^{2^{t}}\;\text{mod}\; n$ for $g$ a generator of the group $\left(\mathbb Z/n\mathbb Z\right)^{*}$ and $t$ a very large number for example $2^{512}$. She then asks Bob for an input $z$ ($\neq y$) and sends him a relatively small random prime (challenge) $\ell$ and $\pi$ a proof of $y$ such that $$\pi = g^{\left\lfloor\frac{2^t}{\ell}\right\rfloor}\;\text{mod}\; n$$ and so $$y = \pi^{\ell} g^r\; \text{mod} \; n$$ where $r = 2^t \; \text{mod}\; \ell$. Now Bob needs to find a proof $\psi$ for $z$ such that: $$z = \psi^{\ell} g^r\; \text{mod} \; n.$$

It is clear that if Bob has an access to $\phi$ he can find $d = \ell^{-1}\;\text{mod}\; \phi$ and solve the problem by chosing $\psi = \left(z g^r\right)^d \;\text{mod}\; n$. However in my case $n$ is large that it is almost impossible for me to compute the prime factorization of $n$ to find $\phi$. Can any one help me to find an idea of how to find $\psi$?

  • 1
    $\begingroup$ Shall we read "$2^t$ a very large number for example $2^{512}$" where there is "$t$ a very large number for example $2^{512}$"? If not: for $n$ the product of two distinct primes $p$ and $q$, in order to compute $y=g^{(2^{(2^{512})})}\bmod n$, it looks like Alice must be able to factor $p-1$ and $q-1$, which is not a standard assumption in RSA. And uh, I have not yet found how Alice would computes $\pi$. $\endgroup$
    – fgrieu
    Dec 21, 2023 at 6:15
  • $\begingroup$ Thank you for your comment. For computing $y$ Alice knows the private keys $p$ and $q$ or at least the value of $\phi$ $\endgroup$
    – Kroki
    Dec 24, 2023 at 15:50

1 Answer 1


I manage to solve it. Indeed, Bob can send $z = -y \;\text{mod} \; n$ and then $\psi$ will be simply $-\pi \; \text{mod}\; n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.