In a chosen ciphertext attack, it is hypothesized that the adversary can obtain the decryption of cryptograms chosen by the adversary other than the targeted one(s), and in addition obtain the encryption of any message chosen by the adversary (which is free for asymmetric encryption).
The most general CCA experiment goes:
- Key generation: the challenger secretly draws a key, and reveals the public key if any (that is for asymmetric encryption)
- Message choice and encryption:
- the adversary chooses messages $m_0$ and $m_1$ and submits both to the challenger
- the challenger randomly draws $b\in\{0,1\}$
- the challenger verify that both $m_0$ and $m_1$ are valid (could be encrypted), and if that holds encrypts $m_b$ yielding $c_b$, sets $c=c_b$, and reveals $c$ (unrelated to the question's $c\,$).
- Interaction: the challenger accepts and answers both encryption and decryption queries, with the exception of decryption queries which ciphertext matches $c$.
- Examination: the adversary makes a guess of $b$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for probability non-vanishingly better than $1/2$.
For asymmetric encryption, the challenger needs not answer encryption queries, for these can trivially be handled by the adversary using the public key.
No deterministic encryption can be CCA secure per this definition (argument: the adversary can get $c_0$ and $c_1$ and determine which matches $c$). For a weaker notion of CCA security applicable to deterministic encryption, another change is imperative. That can be:
- The challenger does not answer decryption queries where the ciphertext submitted matches matches one of $c_0$ or $c_1$ (the challenger needs to compute both).
- Alternatively, only the challenger is involved in the message choice, which becomes selecting $m$ such that encrypting it into $c$ succeeds. And in examination the adversary makes a guess of $m$, not $b$. And must guess correctly with non-vanishing probability.
The question is for textbook RSA, which is asymmetric and deterministic. With the second of the above options, and a single decryption query, the experiment goes:
- Key generation: the challenger
- draws a key pair
- reveals the public key $(n,e)$
- keeps secret the private exponent $d$
Note: $(n,e,d)$ is such that messages $m$ that can be encrypted are those integers with $0\le m<n$; their corresponding encryption is per $c\gets m^e\bmod n$, and decryption of $c$ with $0\le c<n$ is per $m\gets c^d\bmod n$ or equivalent.
- Message choice and encryption: the challenger
- randomly draws an integer $m\in[0,n)$
- computes $c\gets m^e\bmod n$
- reveals $c$ (unrelated to the question's $c\,$).
- Interaction: the challenger accepts a chosen ciphertext query where it
- receives $\tilde c$ (the chosen ciphertext) submitted by the adversary
- checks $0\le \tilde c<n$ and $\tilde c\ne c$
- checks and deciphers $\tilde c$, that is checks $0\le \tilde c<n$ then in the affirmative computes and reveals $\tilde m={\tilde c}^d\bmod n$ (this $\tilde m$ is the question's $c\,$).
- Examination: the adversary makes a guess of $m$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for non-vanishing probability.
A standard way to carry this attack in textbook RSA is that the adversary
- chooses some $t$ in $[2,n)$ with $\gcd(t,n)=1$, e.g. $t=2$ or $t=n-1$
- computes $s=t^e\bmod n$
- computes and submits $\tilde c=c\cdot s\bmod n$
- obtains $\tilde m$ from the challenger
Note: from $\tilde c=c\cdot s\bmod n$ it follows ${\tilde c}^d\equiv(c\cdot s)^d\pmod n$ (obtained by raising to the exponent $d$), thus ${\tilde c}^d\equiv c^d\cdot s^d\pmod n$, thus $\tilde m\equiv m\cdot(t^e)^d\pmod n$ (since decryption works for $m$ and $\tilde m$), thus $\tilde m\equiv m\cdot t\pmod n$ (since decryption works for $t$).
- solves for $m$ with $0\le m<n$ the equation $\tilde m\equiv m\cdot t\pmod n$ (which in the question is the equation $c = m \cdot t \pmod n\,$), and submits the result as the recovered $m$.
In that later step, the adversary computes a multiplicative inverse of $t$ modulo $n$, that is some integer $t'$ such that $t\cdot t'\equiv1\pmod n$. This is possible since $\gcd(t,n)=1$. One method uses the extended Euclidean algorithm. When $t=2$ (resp. $t=n-1\,$), we can use $t'=(n+1)/2$ (resp. $t'=n-1\,$).
Then $\tilde m\equiv m\cdot t\pmod n$ becomes $\tilde m\cdot t'\equiv(m\cdot t)\cdot t'\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot(t\cdot t')\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot1\pmod n$, thus $\tilde m\cdot t'\equiv m\pmod n$.
Therefore, the adversary always finds $m$ by computing the uniquely defined $m=\tilde m\cdot t'\bmod n$ (see notation at end).
Critically w.r.t. to the question, there is no hesitation between several $m$ because
- it is known that the challenger chose a valid message $m$, thus that $0\le m<n$
- a solution $m$ to $\tilde m\equiv m\cdot t\pmod n$ exists and all are congruent modulo $n$, because a solution $t'$ to $t\cdot t'\equiv1\pmod n$ exists and all are congruent modulo $n$, because the adversary has chosen $t$ with $\gcd(t,n)=1$, thus $t\bmod n$ belongs to the multiplicative group of integers modulo $n$
- when $y$ is congruent to $x$ modulo $n$, that is when $y\equiv x\pmod n$, the additional condition $0\le y<n$ makes $y$ uniquely defined by $(n,x)$.
Notation: for integer $n>0$ and integer $x$
- $y\equiv x\pmod n$ means that $n$ divides $x-y$. This is best read as: $y$ is congruent to $x$ (short pause) modulo $n$. It can be written
y = x (mod n).
- $y=x\bmod n$ means that $n$ divides $x-y$, and $0\le y<n$. This can be read as: $y$ is $x$ modulo $n$. Such integer $y$ is uniquely defined for a given $(n,x)$. That $y$ is the remainder of the Euclidean division of $x$ by $n$ when $x\ge0$.
