# How reasonable is deriving the key a corpus of RSA-PSS signed messages?

Given access to a 2048 bit public key, a large corpus of 2048 bit plain text messages and their signatures (RSA-PSS with SHA256 as the hash and MGF) are any of the following statements correct:

1. Increasing the number of of messages available significantly increases the likelihood an attacker can reverse the private key
2. Decreasing the plain text message size significantly increases the likelihood an attacker can reverse the private key

Note: by significantly I mean "before the heat death of the universe" becomes a few hundred years. If instead it becomes half the heat death of the universe, I'm less interested.

• Mar 27, 2019 at 23:04
• Note that the hash over the message is integral part of PSS, so increasing or decreasing the message size does nothing (special) to the input of the PSS padding algorithm (MGF1) and of course neither to the subsequent OS2IP algorithm or final RSA exponentiation. So part 2 is only of interest if you skip the data hashing part all together. You could probably argue that the resulting scheme would not be PSS. Mar 28, 2019 at 0:16
• Personally, if you're talking about reversing PSS, I would expect you mean that you can retrieve the messages or hash during verification. That's something entirely different from retrieving the private key and breaking the cipher. Maybe it is a good idea to adjust the title accordingly. And welcome to crypto.SE, of course :) Mar 28, 2019 at 0:23
• I updated the title Mar 28, 2019 at 17:31
• @MaartenBodewes Verification requires knowledge of the message and/or its hash. The security definition of signatures usually addresses unforgability, maybe the question should point in that direction. But the answer is fairly simple: No, with data and computational power in realistic dimensions, this should not work unless you can break the computational assumptions of RSA or the hash function.
– tylo
Mar 28, 2019 at 17:33

The best way we know to forge messages is to factor $$n$$. The best algorithm we know to factor $$n = pq$$ when $$2^{1023} < p < q < 2^{1024}$$ are (near) uniform random primes, the general number field sieve, costs more than $$e^{(\log n)^{1/3} (\log \log n)^{2/3}}$$, and uses only the modulus $$n$$, without reference to any signed messages.
The standard PSS security theorem is that if you had an algorithm to forge signatures, then someone could use your signature forger as a subroutine in a program to invert $$x \mapsto x^e \bmod n$$ with essentially the same probability of success as the forger, and as many additional modular exponentiations as the forger makes hash or signing queries. Consequently, PSS forgery can't be much cheaper than computing $$e^{\mathit{th}}$$ roots, but we don't know any way to actually do it besides factoring $$n$$ in order to compute $$e^{\mathit{th}}$$ roots in the first place.