Given a server that can return me RSA sign for any plaintext shorter or equal length of the given plaintext (excluding the given plaintext), how can I fraud/get the sign of the given?

$$sign = M^{d} \pmod{N}$$

  • $m$ is 63 bytes, if not it is left-padded with zeroes
  • $M = \mathtt{0x00}\mathbin\|m\mathbin\|\mathtt{0x00}\mathbin\|m$, which is always 128 bytes
  • $(e,N)$ is public key
  • $(d,N)$ is private key
  • $N$ is 128 bytes long
  • $\begingroup$ Welcome to Cryptography. Is this a homework? $\endgroup$ – kelalaka Jan 8 at 20:14
  • $\begingroup$ yes, i have added more details to the question $\endgroup$ – Tamar Geldiashvili Jan 8 at 20:20
  • $\begingroup$ The 0x000 strings have a zero too many of course. $\endgroup$ – Maarten Bodewes Jan 8 at 20:34
  • $\begingroup$ @kelalaka it would be sign of 2*M ? $\endgroup$ – Tamar Geldiashvili Jan 8 at 20:49
  • $\begingroup$ Hint: Assume that a non-trivial factor $m_0$ of $m$ can be found, which is possible for all but prime $m$, and easy for all but a small fraction of possible $m$. Obtain the signature of $m_0$, $m/m_0$, and $1$. Toss. I do not immediately see a solution for prime $m$. $\endgroup$ – fgrieu Jan 8 at 21:06

We notice that $M=k\cdot m$ with constant $k=2^{512}+1$. Hence the signature $\mathcal S(m)$ of $m$ is $\mathcal S(m)=k^d\cdot m^d\bmod N$.

It follows that for any valid messages $m_0$ and $m_1$ with $m=m_0\cdot m_1$ a valid message, we have $\mathcal S(m)\cdot\mathcal S(1)\equiv\mathcal S(m_0)\cdot\mathcal S(m_1)\pmod N$.

Hence, when we can write $m$ as $m_0\cdot m_1$ with $m_0>1$ and $m_1>1$, we can obtain the signature of $m$ by asking to the server the signature of $m_0$, $m_1$, and $1$. We can then compute $\mathcal S(m)$ as $\mathcal S(m_0)\cdot\mathcal S(m_1)\cdot\mathcal S(1)^{-1}\bmod N$. The last term of the product is obtained by modular inversion modulo $N$, using e.g. the half-extended Euclidean algorithm.
Note: that solution was found by the OP, based on a (strong) hint.

Given the server's limitation, we can get $\mathcal S(m)$ for any composite $m\in[4,2^{504}($, using three oracle queries (or just two when $m$ is a square). We can most often pull a factor $m_0$ using trial division, Pollard's Rho, ECM (all in GMP-ECM). We need GNFS in some difficult cases (e.g. CADO-NFS or Msieve, perhaps as packaged as FaaS).

With the "lengh" of a message counted in bits, I see no solution for prime $m$, or for $m=1$.

If the "lengh" of a message was counted in bytes excluding leading zero bytes, and for those $m$ such that $2m$ has the same length as $m$, then we can use $\mathcal S(m)\,=\,\mathcal S(2m)\cdot\mathcal S(1)\cdot\mathcal S(2)^{-1}\bmod N$ for $m>1$, and $\mathcal S(1)\,=\,\mathcal S(2)^2\cdot\mathcal S(4)^{-1}\bmod N$ for $m=1$. That still leaves quite a few problematic $m$, such as $131$ and $2^{504}-503$.
Note: We have $S(0)=0$ with no query for $m=0$.
Note: $k=F_9$ where $F_m=2^{(2^m)}+1$. The factorization of Fermat integers is well-studied, and it has been known since 1903 that $2424833$ divides $F_9$. But I do not see that it helps.


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.