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

Question

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.

Answer 1

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

That's the number of new (message, signature) pairs with message of the form $\prod m_i^{k_i}\bmod n$ with $k_i\in\{0,1\}$ and $1<\sum k_i$; that is, we combine at least two existing messages. BTW, that simplifies to $2^t-t-1$.

But we can just as well compute the signature for message $\prod m_i^{k_i}\bmod n$ for any integers $k_i$. As noted in the question, $k_i=-1$ or more generally negative works too. And even more generally, we can compute as many (message, signature) pairs as we see fit if we know $(n,e)$, for we can find the message matching any desired signature, by raising the signature to the power $e$ modulo $n$. Problem from an attacker's perspective is that the messages thus obtained are largely random-like.

Conclusion: textbook RSA signature can be secure only if the parties that verify are selective in the messages they accept, and the signers selective in the messages they sign. That's where message padding for RSA signature comes to play.

---

Are inverses necessary to produce new signatures?

No. That's one of the tricks that can be pulled to form new (message, signature) pairs with specific properties of the message in attacks against some RSA signature practices.