8
$\begingroup$

In the spirit of Are curve secp256k1 ECDSA 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?

$\endgroup$
2
  • 2
    $\begingroup$ If you know the modulus, you might say that the message is less than the modulus size. $\endgroup$
    – kelalaka
    Dec 23, 2023 at 19:45
  • $\begingroup$ 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. $\endgroup$
    – Full Array
    Jan 3 at 3:35

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Dec 26, 2023 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.