9

I'm looking through old tests in an information security course - and there's a question about CCA and CPA security of RSA.

I can't seem to grasp how I'd either show insecurity or prove the security for this. (This is not a homework question, it is for my own personal understanding)

The question is as follows (relates to the basic scheme RSA):
For CPA secure, does an algorithm A exist so that given some ciphertext c, picks m plaintexts pt1,pt2,pt3,pt4,..., gets their ciphertexts and then returns the plaintext p for the given ciphertext c.

For CCA secure, does an algorithm B exist so that given some ciphertext c, picks m ciphertexts ct1,ct2,ct3,ct4,... , gets their appropriate plaintexts, and returns the correct p for ciphertext c.

Improve this question
3
  • @Thomas Pornin: Your assumption that "asymmetric encryption is necessarily secure agains CPA" is wrong. Any cipher that has IND-CPA security has to be nondeterministic. Otherweise the attacker could simply compare ciphertexts, because he can encrypt any message. Due to my low reputation I cannot add this statement as comment. Sorry for that.
    – null
    Commented Jul 6, 2015 at 15:10
  • The crucial part of that sentence is the part you omitted: "if it is to offer any security at all." @Thomas Pornin's claim is not that any proposed asymmetric encryption algorithm is secure against CPA; it is that any proposed asymmetric encryption algorithm that is not secure against CPA is immediately hopelessly broken, "since encryption uses only public elements."
    – Nefrubyr
    Commented Jul 6, 2015 at 16:04
  • So this subordinate clause means that asymmetric encryption schemes need to be nondeterministic to be CPA secure?
    – null
    Commented Jul 7, 2015 at 14:47

1 Answer 1

Reset to default
12

Your "basic RSA" is probably not standard RSA as specified in PKCS#1, but the so-called "textbook RSA", which is insecure because it is reduced to the core modular exponentiation and does not include the padding, which is essential.

In "textbook RSA", public key consists in n (modulus) and e (public exponent). Private key is d (private exponent). Plaintexts are integers modulo n. The encryption of m is me mod n; decryption is obtained by raising to the power d because (me)d = m mod n for all integers m in the 0 to n-1 range.

Indeed, textbook RSA is not secure against Chosen Ciphertext Attacks because of the following: for the modulus n and all messages m and m', you have:

(mm')e = (me)(m'e) mod n

In other words, the encryption of a product is the product of the encryptions. In the CCA setup:

  • There is a message m and its ciphertext c = me mod n. Attacker knows c and wants to find m.
  • Attacker is allowed to obtain the decryption of ciphertexts that he chooses, as long as none of them is equal to c.
  • Attacker generates a random m' (modulo n) and computes c' = m'e mod n.
  • Attacker asks for the decryption of cc' mod n: this is an integer modulo n, distinct from c, so the attacker gets a response.
  • The response is necessarily equals to mm' mod n. Attacker knows m' (he chose it himself) so he computed m easily.

As for Chosen Plaintext Attacks: asymmetric encryption is necessarily secure against CPA, if it is to offer any security at all. Indeed, encryption uses the public key, which is public, thus known to everybody, including the attacker. If the attacker wants to encrypt some messages of his choosing, then he... just does it. He does not need any help from the private key owner, since encryption uses only public elements.

If textbook RSA was not secure against CPA, then standard RSA, with the padding, would be weak too: using his breaking method, the attacker would recover the padded message, from which he would obtain the non-padded message.

Now this does not mean that textbook RSA is secure against attackers who cannot obtain the decryption of custom ciphertexts. Textbook RSA has (at least) the following very serious issues:

  • As noted above, it is insecure against CCA.
  • If the message is a small integer, then the RSA problem may become very easy. For instance, if m is a 200-bit integer and the public exponent is e = 3, then me is a 600-bit integer, while the modulus is normally larger (at least 1024 bits). This implies that m can be recovered with a simple, non-modular cube root (which is easy).
  • Textbook RSA is deterministic; thus, if the message itself is amenable to brute force (e.g. it is a password), then it can be recovered by trying potential message values until a match is found.

Standard padding, as specified in PKCS#1, solves these issues: the padding ensures that the padded integer is large enough; padding includes random bytes. The old-style PKCS#1 padding (dubbed "v1.5") is actually not very strong against CCA, although it still is tolerably good when employed properly, as in SSL (it requires that the SSL server does not complain when the decryption of what the client sends does not have a syntactically valid padding). The new-style PKCS#1 padding (dubbed "OAEP") is strong (and even "proven strong" for an appropriate meaning of "proven").

Improve this answer
3
  • I have previously read about the attack you described, given a "decryption oracle". I was lacking the CCA setup explanation that you had given and therefore had some trouble accepting that as a solution to this question. Thanks for your well written answer!
    – Arnon
    Commented Jan 20, 2014 at 18:53
  • 1
    Wait, isn't "textbook RSA is deterministic" and "textbook RSA is CPA-secure" a contradiction as every CPA-secure scheme must be non-deterministic? (also see Theorem 11.4 of Katz/Lindell's introduction to modern cryptography 2nd edition)
    – SEJPM
    Commented May 9, 2016 at 20:39
  • 1
    I think Thomas speaks about OW-CPA, while you @SEJPM are talking about IND-CPA. Assuming this, you are both right. Maybe you could both clarify this in your posts!
    – Marian
    Commented Feb 6, 2019 at 16:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .