If someone has an encrypted message and it's original plaintext, could he guess the private key if it's the one used to encrypt the message?

Question

In digital signatures, the private key is used to encrypt a (hashed) message and the public key is used to decrypt it. This made me wonder since the receiver has the cipher text (digital signature) and can easily reach the original plain text— by decrypting the digital signature using the sender's public key— if there is a way for him to guess the private key given the cipher text and its plain text.

Answer 1

There is a big confusion here;

In digital signatures, the private key is used to encrypt a (hashed) message and the public key is used to decrypt it.

In a digital signature, we have a signature algorithm ($\mathsf{Sign}$) and a signature verification algorithm ($\mathsf{Vrfy}$). For the digital signature algorithm, the private key is used, and for the signature verification algorithm, the related public key is used.

There is no encrypt and decrypt in Digital signatures The common confusion comes from the RSA where it is one of the rare and simple systems that can be used for encryption/decryption and signature/verification.

This is true in the textbook RSA which is in no way secure. The encryption needs proper paddings like PKCS#1 v1.5 (RSAES-PKCS1-v1_5) or OAEP (RSAES-OAEP) padding. For signature, one needs the PSS ( RSASSA-PSS). Follow the links from rfc8017 or read the from Cornell University's web page for this;

• RSA Signing is Not RSA Decryption

Hashing before a signature is also part of the secure signature scheme since the first true digital signature scheme, Rabin Signature. We don't prefer the term hash-then-sign paradigm since it is part of the security.

This made me wonder since the receiver has the ciphertext (digital signature) and can easily reach the original plain text— by decrypting the digital signature using the sender's public key— if there is a way for him to guess the private key given the ciphertext and its plain text.

The security of the signature scheme is not about accessing the message it is about forging a signature. i.e given $(\sigma_i,m_i)$ pairs, the adversary must find another pair $(\sigma',m')$ such that $\mathsf{Vrfy}(\sigma',m')$ must return valid signature where $m_i \neq m'$.

As we can see this is not talking about the encrypted message. This doesn't mean that we cannot sign encrypted messages, this is about the formal security game of the signature schemes and see some variants on Wikipedia

As we talked about earlier, the message is hashed for the signature therefore even you somehow access the hash of the message due to the very weak signature scheme you need to break the pre-image resistance of the applied hash function. All cryptographic hash functions including the MD5 and SHA-1 , where they have been broken in their collision resistance, are still pre-image resistant for any power in the near future and you will not have luck there for 256-bit output hash function even a Cryptographic Quantum Computer is built, the best they can have the Brassard's optimization over Grovers with around $2^{85}$-time and $2^{85}$-space. Using a hash function with 512-bit output is clearly quantum-safe ( this is applicable to$\left(\mathsf{Enc}(m)\mathbin\| \mathsf{sign}(m)\right)$ that we don't prefer.)

What you saying is the total break of the signature scheme where the attacker also gains the private key. There are example signature scheme that has a total break given many $(\sigma_i,m_i)$ pairs;

• Total Break of the `-IC Signature Scheme by by Pierre-alain Fouque , Gilles Macario-rat , Ludovic Perret , Jacques Stern, 2007

Still, this doesn't give access to the message since we usually encrypt-then-sign. What you will get the signature key and even in the RSA case one needs two sets of keys; one for encryption and one for signature. We don't reuse the keys that are used for different aims.

What you need to access the message is the break of the encryption scheme that usually AES-256 and ChaCha20-256 in nowadays and both are secure against Grover's algorithm, too.

AES with a proper mode of operation like CTR and CBC is Ind-CPA secure. ChaCha has a built-in CTR mode. More than IND-CPA we need integrity and currently, all cipher suites of TLS 1.3 use Authenticated Encryption Modes with Associated Data (AEAD) like AES-GCM and ChaCha20-Poly1305 (and AEAD > Ind-CCAx).

As long as the cipher suites are correctly used, the task is almost impossible.

---

In RSA case, RSASSA-PPS is probably secure.

---

We don't have Ind-CPA or Ind-CCAx security for the signature schemes, those are for encryption. We have SUF-KMA or EUF-KMA like security games for the signature schemes.

If someone has an encrypted message and it's original plaintext, could he guess the private key if it's the one used to encrypt the message?

In public-key scheme, the encryption oracle is free, that is once you know the target public key, then you can get as many as (plaintext, ciphertext) pairs as you want ( well polynomially bounded) then work on breaking the system. This simply implies that we need at least Ind-CPA secure public-key cryptosystem for encryption.

RSA can achieve Ind-CPA with the proper paddings. Many tried to break this ( yes we have come a long way [1][2][3]) but there is no failure if the proper padding scheme is used and implemented correctly. Any public key cryptosystem that fails to satisfy Ind-CPA is a direct way to the graveyard of broken schemes.

While using RSA for information encryption, your biggest concern is the GCD attack. Have a good random number generator to mitigate this.

And, keep in mind that we mostly use RSA for signatures. In general, we use hybrid-cryptosystems where the key exchange is performed with a public-key cryptosystem, and data encryption is performed with asymmetric system. One can use

• RSA-KEM with AES-GCM/ChaCha20-Poly1305
• DHKE with AES-GCM/ChaCha20-Poly1305
• Integreted Encryption Scheme (IES): Discrete Logarithm Integrated Encryption Scheme (DLIES) and Elliptic Curve Integrated Encryption Scheme (ECIES)

There are broken schemes or still safe schemes so future safe schemes against quantum attacks ( RSA and ECC is gone with that, welcome back Supersingular curves) that we did not list here.

---

Abbreviations

• IND-CPA: INDistinguishability under Chosen Plaintext Attack
• IND-CCA1: INDistinguishability under Chosen Ciphertext Attack
• IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack
• IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

Answer 2

This is known as chosen plaintext attack, or at least known plaintext attack if he can't choose the plaintext.

Any real-world algorithm will of course have to protect against this kind of attack.