Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$.

share|improve this question
1  
Yes, it should be $\varphi(n)$ in step 2. –  DrLecter Aug 9 at 17:32

1 Answer 1

up vote 2 down vote accepted

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)

share|improve this answer
1  
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? –  Juergen Aug 9 at 18:57
1  
2  
Thanks @DrLecter, now I get it. My mistake was disregarding that c*d is in the exponent and that apparently changes everything. –  Juergen Aug 9 at 19:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.