Why isn't it secure on its own?
It isn't secure against chosen ciphertext attacks (CCA-IND). If an scheme is CCA-IND then an attacker shouldn't be able to differentiate between the encryption of 2 messages of the same length with probability greater than negligible.
so e.g, say we have an adversary and challenger (challenger is our proposed CCA-IND scheme) we could do the following:
1) The challenger generates his key.
2) The adversary sends 2 messages to the challenger, lets call them m
0 and m
1 where |m
0| = |m
1|
3) The challenger 'flips a coin' heads he encrypts m
0. Tails he encrypts m
1
3) The challenger sends
. So in game 0 he receives the encryption of m
0 and in game 1 he receives the encryption of m
1. The adversary doesn't know what game he is in.
The adversary can do this n times.
4) Adversary then does his chosen ciphertext query. That is he can choose a ciphertext and have it decrypted. So he chooses c
i. The only rule here is that c_
i can't be any of the ciphertexts already submitted. It has to be a
new ciphertext.
5) Adversary receives the decryption of c_
i
6) Adversary has to output whether he is in game 0 or game 1.
The adversary shouldn't be able to distinguish between game 0 and game 1 with anything higher than negligible probability. Therefore an encryption scheme is CCA secure if for all efficient adversaries the probability of distinguishing between any two pairs of encrypted messages is negligible. (Efficient just means he can't have unlimited computing power)
So how is plain RSA insecure against this ? Because RSA is multiplicatively homomorphic* That is a multiplication operation on the ciphertext performs multiplication on the plaintext (modulo)
Using small numbers (the math is the same)
Let
p = 11
q = 13
N = 143 (p * q)
where phi(N) = (p-1)(q-1)
We select a value for e (our encryption exponent). e has to be relatiely prime with phi.
e = 17
Our decryption exponent is d = 113 (Read the RSA wiki if you care how e & d are calculated / chosen)
Let's choose a message to encrypt,
m
1 = 123
Encrypting m we do c
1 = m
1e mod N
So, c
1 = 123
17 mod 143 giving a ciphertext of c
1 = 106
This will be one of the message pairs the adversary chooses in the first steps of the CCA game.
Now say the attacker modifies the ciphertext by multiplying it by some value
r mod N where
r is chosen such that we can find a modular inverse of r mod N.
Let's choose r = 6
and r
-1 = 24 as 6*24 mod 143 = 1
Now,
c' = (c
1 * (r
e mod N)) mod N
c
1' = (106 * (6
17 mod 143)) mod 143
c
1' = 56
The attacker gets this decrypted by the challenger (remembered allowed in the second step of the CCA game).
The attacker receives back the decryption of 56 (let's call it m
1')
m
1' = c
1'
113 mod 143
m
1' = 23
Now because RSA is multiplicatively homomorphic, multiplying the cipher text multiplies the plain text, so:
m = (m' * (r
-1 mod N) mod N)
Subbing in our values:
m
1 = (23 * (24 mod 143) mod 143)
m
1 = 123
The adversary can easily distinguish between game 0 and game 1. He just decrypted the ciphertext he received and checks if that was m0 or m1.
So plain RSA isn't secure against Chosen Cipher text Attacks.
RSA is used with a scheme such as
OAEP
But it's worse than that, plain RSA isn't randomised. It's entirely deterministic, therefore it can't even be semantically secure. Semantic security is kind of like the same game above except you skip the phase where you submit a ciphertext to be decrypted. (Semantic security provides security against eavesdropping, chosen ciphertext security and beyond is security against active attackers)
* Homomorphic Encryption is very cool, just not feasible yet. You can read about it
here and
here. A Fully Homomorphic Scheme would allow operations to be performed on the ciphertext given encrypted results. Think being able to do cloud computing without the machine doing the operations knowing anything about the data or the result!
ETA: How on earth do you do latex on this forum other than creating a gif on the latext site and uploading it to my web server and linking to it as an image ?
