Are RSA signatures distinguishable from random data?

Are RSA signatures distinguishable from random data?

What if you don't know the message?

What if you have many common datasets you can do analysis across?

• If you know the modulus, you might say that the message is less than the modulus size. Dec 23, 2023 at 19:45
• Creating true random numbers is difficult. The same is true for random data. For example, the creation of random numbers always depend on some base, for examples the pattern you follow to hit your keys on your keyboard as you type. Therefore, the chance for RSA signatures and random data to be distinguishable is plausible. Jan 3 at 3:35

Yes.

Known public key

Is it possible to distinguish, with non-negligible advantage, an RSA signature made with a key with the modulus $$n$$, from a random number in the range $$[1,n-1]$$?

Yes for standard signature formats (PKCS#1v1.5, PSS). Given a public key $$(n,e)$$ and a putative signature $$s$$, calculate $$s^e$$ and convert it to an octet string following the procedure in PKCS#1. For a valid PKCS#1v1.5 signature, the string begins with a fixed prefix of length at least 11 octets, out of which all but part of the first octet are random if $$s$$ is random, giving a less than $$2^{-80}$$ probability that a random input looks like a signature. For a valid PSS signature, the string ends with a fixed octet value, and the string obtained after unmasking also has at least one fixed octet value, giving a less than $$2^{-16}$$ probability that a random input looks like a signature.

Unknown public key

Is it possible to distinguish, with non-negligible advantage, an RSA signature made with an unknown key with an $$N$$-bit modulus from a random number in the range $$[1,2^N-1]$$?

Yes, with a small advantage: a valid signature is smaller than the modulus, so a putative signature $$s$$ can only have been produced with a modulus $$n$$ such that $$n \gt s$$.

This is mostly relevant for a slightly different question, namely: is it possible to tell, with non-negligible advantage, whether two sets of signatures are made with the same key? The answer is yes, because you can recover the modulus with non-negligible probability from a set of signatures. This means that RSA signatures do not provide privacy of the signer, which has led to practical attacks on privacy.

• In the unknown public key setup, for deterministic signature only (like RSASSA-PKCS1-v1_5 but not RSASSA-PSS), given a few signatures, the corresponding messages, and the public exponent (or just a guess of that if it's small, as is usual), we can find the public key and then are back to known public key.
– fgrieu
Dec 26, 2023 at 13:30