# RSA Blind Signature Attack

In Information Security Class I learned a non-adaptive chosen ciphertext attack using "blinding" but I just can't follow the proof and therefore can't reconstruct it. From what I've found out, it seems to be based on this Wikipedia entry (although not entirely I think): http://en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing

The idea is that an attacker intercepts a ciphertext, replaces it with a blinded ciphertext, and sends it to the recipient. Upon decrypting, the recipient complains because the message is corrupt and returns the decrypted, corrupt "plaintext". So far, so good. Now, if the attacker intercepts the corrupt plaintext, he is supposed to be able to decrypt it to obtain the original message.

Assuming that the corrupt message $m'$, the encryption keys $c$ and $n$ (where $n$ = $p$ * $q$) are public, and $d$ is the recipients' private decryption key, the proof is supposed to be:

$$1) \ m' = (m^c * z^c )^d\ mod\ n = m^{c*d} * z^{c*d} \ mod\ n$$ $$2)\ c*d\ mod\ n = 1$$ $$3)\ m' = m^1 * z^1 mod\ n\ \ \ \ \ (edit:\ because\ of\ 2)$$ $$4)\ m = z^{-1} * m'$$

I understand that the attacker can intercept the corrupt message $m'$ in step 1). What I don't understand is step 2). Shouldn't it be $c*d\ mod\ \phi(n) = 1$, where $\phi$ is Euler's totient function? After all $d$, which is the multiplicative inverse of $c$, is calculated $mod\ \phi(n)$, which only the recipient can calculate because he has $p$ and $q$.

• Yes, it should be $\varphi(n)$ in step 2. Aug 9 '14 at 17:32

You are correct; whoever put together the above proof typo'ed that point; we have $c \times d \equiv 1 \pmod {\phi(n)}$, or more accurately, $c \times d \equiv 1 \pmod {lcm(p-1, q-1)}$.
On the other hand, the attacker isn't expected to be able to compute step 2 (he can't, he doesn't know the value of $lcm(p-1,q-1)$, and hence cannot compute $d$). Instead, it is there to establish the relationship between $c$ and $d$ (and why they cancel out in step 3)
• I'm sorry, I formulated the proof imprecisely. I guessed that the attacker is not able to compute $d$ by this attack but only the message. Step 2 was, like you said, just supposed to demonstrate, why $c$ and $d$ cancel each other out in step 3. And this leads to my actual question: Why do they cancel each other out, if they are inverse in $mod\ \phi(n)$ and not in $mod\ n$? Is there are connection between the two I am unaware of? Aug 9 '14 at 18:57