# When is an asymmetric scheme considered broken?

Does the following quote imply that valid encrypted data can be created and decrypted by someone other than the owner of a private key:

An asymmetric encryption scheme is considered to be broken if an attacker can decrypt a given ciphertext, even if he can convince you to decrypt arbitrary other ciphertexts

What conditions must exist for this to occur? (Specifics would be appreciated)

-

I think you are referring to Colin Percival's Everything you need to know about Cryptography, in one hour in which he observes:

An asymmetric authentication scheme is considered to be broken if an attacker with access to the verification key can generate any valid ciphertext, even if he can convince you to sign arbitrary other plaintexts.

This is called a chosen ciphertext attack, abbreviated CCA in literature.

I'm going to look at the RSA case. In the case of RSA, decryption given a ciphertext $c$ is $r = c^d \mod n$ and signing is $s = p^d \mod n$. As you have no doubt gathered, these both use $d$ the private key. So for the purposes of RSA, the two operations are related (this is a trapdoor permutation). However, assuming they weren't, being able to convince an attacker to sign arbitrary plaintexts may compromise the signing key and allow the attacker to pass themselves off as you.

Next up, actually exploiting a cryptosystem such as RSA. This paper discusses encrypting RSA properly (the use of padding) but also contains the observation that:

$$\epsilon_{n,e}(m_1)\epsilon_{n}{e}(m_2) = \epsilon_{n,e}(m_1m_2)\mod(n)$$

Re-writing this using slightly more familiar notation:

$$(m_1^e \mod n)(m_2^e \mod n) = m_1^e m_2^e \mod n = (m_1m_2)^e \mod n$$

Now, the paper notes that chosing $C\prime = C\cdot 2^e$ then $C\prime = m^e2^e$ which is equivalent to $(2m)^e$. Decrypted this is $(2m)^ed = 2m \mod n$ and so the attacker, having access to $2m \mod n$ knows $m$.

From a practical point of view, the attacker still needs to acquire the decrypted output. The attack doesn't make any assumptions as to how they achieve that, but it does demonstrate an exploit of RSA. To counter this, continue reading that paper; specifically, one should use an appropriate padding scheme.

Any crypto-system which has a similar homomorphic property will be vulnerable. For example, these slides explain similar behaviour in ElGamal.

-
Actually, the quote given in the question is also in the same document (page 20). – Paŭlo Ebermann Oct 10 '11 at 10:40
@PaŭloEbermann ah, so it is! – user46 Oct 10 '11 at 10:44