# Breaking RSA in a special case

This is a part of homework assignment, and I am stuck. The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here.

Public and private keys are $(N,e)$ and $(N,p,q,d)$ respectively. $N = pq$. $p, q$ being prime. $e\cdot q = 1 \bmod \Phi(N)$

1. $S_p = M^d \mod p = M^{d \mod (p−1)} \bmod p$
2. $S_q = M^d \mod q = M^{d \mod (q−1)} \bmod q$
3. $\rm{Sign}_{(d,p,q)} (M ) = (S_{p} \cdot \beta \cdot q + S_{q} \cdot \alpha \cdot p) \bmod N$

$M$ is the message.

The problem states that if the value of $S_p$ is calculated correctly but value of $S_q$ is not. Then the receiver finds out the secret key.. We have to give the description of this receiver that figures out the secret key.

Any help will be appreciated. thanks in advance

-
@NItin, what do you want to know? – quanta May 7 '11 at 12:12
@quanta i have edited the question to make it more clear. – Nitin Garg May 7 '11 at 12:22
Is there some part of RSA you don't understand or what? – quanta May 7 '11 at 12:28
I don't understand how incorrect computation of Sp couldnt reveal some information. It is very counter intuitive for me. I am not able to think ahead. – Nitin Garg May 7 '11 at 12:35
M^d mod q is not calculated correctly. It is something other then M^d mod q. – Nitin Garg May 7 '11 at 13:15

Here is an example of RSA (using Chinese remainder optimization) done "right":

1. Alice chooses prime numbers $p=3001$, $q=4093$ and computes $n = 12283093$ and $\varphi(n) = 12276000$, then picks a random $e = 57413$ coprime to $\varphi(n)$ and inverts it modulo $\varphi(n)$ to get $d = 2498477$.
2. For optimization and signing purposes Alice also computes $d_p = 2477 \equiv d \pmod {\varphi(p)}$, $d_q = 2357 \equiv d \pmod {\varphi(q)}$, $p' = 1533 \equiv p^{-1} \pmod q$ and $q' = 1877 \equiv q^{-1} \pmod p$.
3. Alice sends everyone the public key $(12283093,57413)$ and writes down the private key $(12283093,2498477)$ and optimization data $(2477,2357,1877)$.
4. Bob has also released his public keys.
5. Alice wants to send a signed version of the message $M = 1177711 < n$ to Bob so she computes $S_p = 1475 \equiv M^d \pmod p$, $S_q = 3501 \equiv M^d \pmod q$ and $\text{Sign} = \text{Mod}(S_p q q' + S_q p p',n) = 2191230$ (by CRT) satisfying $\text{Sign} \equiv S_p \pmod q$, $\text{Sign} \equiv S_q \pmod p$.
6. Now Alice sends this signature in a message to Bob who decodes it and checks it is all okay.

So now suppose Alice made a mistake in step 4, computing a signature which satisfied instead:

• $\text{Sign} \equiv S_p \pmod q$.
• $\text{Sign} \equiv 3502 \not \equiv S_q \pmod p$.

so that

• $\text{Sign} = 2414279$.

Bob has Alice's public key $(n,e)=(12283093,57413)$, (wrong) signature $2414279$ and the message $M = 1177711$ but he noticed that the signature did not check out.

Now perhaps consider $$\text{gcd}(M' - M,n)$$ where $M' \equiv {M'}^e \pmod n$ (note that $M' = M$ when no mistake was made..).

-
I just figured out the exact same solution an hour ago. What a coincidence. Thanks for confirming :) – Nitin Garg May 7 '11 at 15:38
gcd(M' - M,n) would be equal to q. – Nitin Garg May 7 '11 at 15:38
@NItin, This is just a hint. One still has to actually come up with a theorem and prove it. – quanta May 7 '11 at 15:40
yeah. I have worked it out.:) – Nitin Garg May 8 '11 at 13:53