2
$\begingroup$

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.

P.S. I also asked this question the cryptography stack community and received an answer.

$\endgroup$
6
  • $\begingroup$ Hey mate, great question, there is a community for strictly cryptography, which may give you a better response in case you are not aware $\endgroup$
    – Adam L
    Dec 15 '20 at 6:13
  • $\begingroup$ 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. $\endgroup$
    – scribe
    Dec 15 '20 at 6:19
  • $\begingroup$ 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$ $\endgroup$ Dec 15 '20 at 6:20
  • $\begingroup$ @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 $\endgroup$
    – Adam L
    Dec 15 '20 at 6:25
  • 1
    $\begingroup$ @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". $\endgroup$
    – scribe
    Dec 15 '20 at 6:27
2
$\begingroup$

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$.

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.

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).

Important note: The forgery is worked since you are working with the textbook RSA. It is not secure as you can see you can forge messages. First of all, we don't sign messages rather their hashes known as hash-and-sign paradigm. So as long as the used hash cryptographically secure the signature multiplication will not work, which may only for negligible probability. Actually, the hash-and-sign is necessary for the security of the signature and known from the first signature scheme the Rabin Signature Scheme. In practice, the RSA is used with a Probabilistic Signature Scheme (PSS) that is designed and the security proof is reduced to RSA problem by Mihir Bellare and Phillip Rogaway. It is standardized in RFC 8017 as RSASSA-PSS.

$\endgroup$

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.