# If we have multiple unique RSA signed messages produced from the same private key, can we always find new valid signatures?

Say Alice publishes $$t$$ unique signed messages with her private key $$d$$,

$$m_1^d, m_2^d, m_3^d, ... , m_t^d \mod n$$

For $$t = 2$$, we have $$m_1^d, m_2^d \mod n$$ and if we let $$x \equiv m_1m_2 \mod n$$ then we can produce a valid signature,

$$x^d \equiv (m_1m_2)^d \equiv m_1^d\times m_2^d \mod n$$

For $$t$$ signatures, I think we can have at most $$\sum_{i=2}^{t}\binom{t}{i}$$ new signatures. Is this correct?

This was inspired by a quiz question in which Alice published $$t$$ RSA signatures and we were asked to find a valid signature for $$M \equiv m_1^{-1} \times m_2^{-1} \times m_3^{-1} \times ... \times m_t^{-1} \mod n$$ and the solution was,

$$M^d \equiv (m_1^{-1} \times m_2^{-1} \times m_3^{-1} \times ... \times m_t^{-1})^{d} \equiv (m_1^{d} \times m_2^{d} \times m_3^{d} \times ... \times m_t^{d})^{-1} \mod n$$

We assumed that all inverses existed. So, I was wondering why did this question involve inverses? Are they necessary to produce new signatures? Because as I showed above, I don't see why we could not do that otherwise.

• Hey mate, great question, there is a community for strictly cryptography, which may give you a better response in case you are not aware Dec 15 '20 at 6:13
• I knew that it existed but I was sceptical as from my past experience the RSA answers there tend to be more concerned with implementation details and high level descriptions than more of a mathematical approach which is what I am looking for with this question. Dec 15 '20 at 6:19
• Note however that $m_1m_2$ etc. are certainly "useless" messages. If we wanted to produce pairs of messages $m$ with valid signatures $m^d$, we could simply use the public exponent $e$ and take message $x^e$ with signature $x$ Dec 15 '20 at 6:20
• @scribe well I have all the praise for your ambition, I am just to lazy to even think about attempting to factorize RSA numbers, but keep in mind there must be at least some element that relies on the means of implementation, the internet would be a horrifying place if loons like me could bit bash their way through anything Dec 15 '20 at 6:25
• @AdamL certainly implementation is important! Although, I am expecting more questions like this on a final and therefore my main concerns here are mostly of the type, "what if" and "but is that even possible". Dec 15 '20 at 6:27

For $$t$$ signatures, I think we can have at most $$\sum_{i=2}^{t}\binom{t}{i}$$ new signatures. Is this correct?
There is no restriction for repetitions like $$m_1 \cdot m_1$$ has a signature as $$(m_1\cdot m_1)^d$$. Also, once we forged a signature, the signature space in your hand is probably increased. We can forge maybe all of the messages on the input space of the RSA modulus and maybe not depending on the messages given and the modulus ( see important note). Remember RSA works in modulus so $$m_1\cdot m_1 = x \bmod n$$.
No, the inverse is not necessary for forging signatures as you noticed. It seems that they asked it only for educative purposes for you to notice that the only messages that don't have the inverses are $$0,p,$$ and $$q$$. Remember, for an $$x \in \mathbb{Z}_n^*$$ to have an multiplicative inverse we need the $$\gcd(m,x)=1$$ ( defining $$\gcd(0,m)=0$$ is problematic).