Generating RSA signature, by manipulating shorter message signatures?

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
• Welcome to Cryptography. Is this a homework? – kelalaka Jan 8 at 20:14
• yes, i have added more details to the question – Tamar Geldiashvili Jan 8 at 20:20
• The 0x000 strings have a zero too many of course. – Maarten Bodewes Jan 8 at 20:34
• @kelalaka it would be sign of 2*M ? – Tamar Geldiashvili Jan 8 at 20:49
• 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$. – 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.