textbook RSA signature scheme security

Question

Are textbook RSA signatures secure if an Adversary does not have access to ask signing oracle queries?

Answer 1

No, plain RSA signatures are existentially forgeable under a key only attack. This is because of the following attack strategy:

Given a verification key $(e,N)$, set the message to $m=s^e \bmod{N}$ for an arbitrary $s$ in the message space and set the corresponding signature to $s$. Output the message signature pair $(m,s)$ as a forgery.

It is easy to verify that this pair passes the verification equation.

Answer 2

There is no encryption or decryption here, since this scheme doesn't aim provide any confidentiality. This scheme aims to provide authenticity. The operations are signature (with the private key) and verification (with the public key).

The reason this scheme isn't used as is, but only with some form of padding or formatting inside (typically one of the two signature modes specified by PKCS#1), is that it has holes. Whether these holes are exploitable depends on the exact data format: after all, if the signer only ever signs valid PKCS#1 padding, and the verifier always verifies that proper PKCS#1 padding is present, the scheme will be secure.

The problem with this scheme is that it allows various forms of forgeries. Let $n$ be the modulus, $e$ the public exponent and $d$ the private exponent. The signature of the message $M$ is $M^d \bmod n$. The purported signature $S$ is a valid signature of $M$ if $S^e \bmod n = M$. Here are a few simple ways to forge a signature, i.e. to produce a valid signature that the holder of the private key has not produced. (Those are well-known classics; I don't know offhand who first wrote about them.)

If $e$ is small, it's possible to forge signatures of some messages. $e$ is usually small because that makes the calculations faster; in particular $e=3$ (the smallest possible value) is a somewhat popular choice. Let $x$ be an integer such that $x^e \lt n$. Then $x$ is a valid signature of $x^e$. PKCS#1 signature formatting schemes avoid this attack by ensuring that no messages are small: v1.5 forces $m \gt n/2^16$, and PSS had at most 8 top bits set to 0 followed by at least 64 pseudorandom bits (usually a lot more) so there's less than a $1/2^{64}$ chance to have $m \lt n/2^{72}$.

If the attacker already knows some valid signatures, it's possible to construct more valid signatures. This is due to a very simple mathematical property: if $S_1^e = M_1$ and $S_2^e = M_2$ then $(S_1 \cdot S_2)^e \bmod n = (M_1 \cdot M_2) \bmod n$. Depending on the encoding of messages, $(M_1 \cdot M_2) \bmod n$ may or may not be interesting. Suppose for example the messages are commands with an “admin” bit, and most admin commands cause undesirable results but the signer is normally very careful not to sign undesirable admin commands. Multiplying two random non-admin commands has roughly one chance in two of producing a message that has the admin bit set. More generally, given a pool of valid signatures, the attacker can brute-force a message with $k$ bits set to desirable values in about $2^k$ attempts. PKCS schemes avoid this kind of attack (at least the simple variant I presented here) by hashing the message, so the attacker can neither craft $M$ and invert the hash function to find a preimage, nor set a hash as target and get all the bits right (that would take e.g. about $2^{128}$ attempts to produce a signature of a given message when using a 128-bit hash function).

Answer 3

It's used an RSA private key to sign¹ message² $m\in[0,n)$ per textbook RSA signature $m\mapsto s:=m^d\bmod n$, and from the signature $s$ the signed message $m$ is recovered³ using the public key as $s\mapsto m:=s^e\bmod n$ in the user software.

Given that the plaintext is known and no padding is used, are there any practical attacks which would allow the private key to be recovered ?

No. A working⁴ private key $(n,d)$ won't leak from example $(m,s)$ pairs and the public key $(n,e)$, even if $m$ was chosen by adversaries. That's for properly generated, kept and used key pair.

or for chosen plaintext to be "encrypted" signed?

For arbitrary random message $m$ in $[0,n)$, no, BUT it might however be possible to obtain the signature of a message that matches certain chosen criteria, and that can be damaging.

Are there any practical weaknesses in RSA where the private key is used to encrypt sign a message, without padding?

Yes, many. Without knowing how the result of $m:=s^e\bmod n$ is used, and what latitude attackers may have in obtaining signed messages, it's impossible to tell if the system can be attacked. The responsible thing from a security perspective is to assume that it can be. That's why we have proper RSA signature (e.g. RSASSA-PSS, ISO/IEC 9796-2), rather than the notoriously insecure textbook RSA signature. Example of attacks against the later:

• Trial and error allows to find $s$ such that $m$ starts with a certain short bytestring, e.g. such that $m$ parses as LICNB: followed by decimal digits and a terminating zero.
• If $e$ is small and it's known $s$ yielding a message $m$ with $n/m>2^{k\,e}$ then it's trivial to compute $s'=2^k\,s$ that yields $m'$ with $m'=2^{k\,e}\,m$. For $k=8$, $m'$ may be meaningful.
• If it's possible to obtain $s_i$ the signature of a chosen $m_i$ (e.g. for a price), it might be possible to devise $m_0$, $m_1$, $m_2$, $m_3$ that match some criteria (e.g. start with some constant) and such that $m_0\,m_1=m_2\,m_3$, legitimately obtain the signatures $s_0$, $s_1$, $s_2$ of $m_0$, $m_1$, $m_2$, and from that compute the signature $s_3$ of $m_3$ as $s_3=s_0\,s_1\,s_2^{-1}\bmod n$.

This offers no confidentiality.

Indeed. That's why it's not encryption.

However it does prevent the data being tampered with, as users have no access to the private key.

That's assuming adversaries can't change the software, or it's public key. In many applications, that's unwarranted. Proper signature does not solve that issue.

---

¹ "encrypt" is inappropriate, since encryption implies the desire to make the data unintelligible by adversaries, and that's not the case.

² "data" is preferable to "plaintext" since there's no encryption.

³ "decrypt" is inappropriate, since there was no encryption in the first place.

⁴ even less so the private key, for there are several functionally equivalent private keys $(n,d)$ matching a given $(n,e)$.