Breaking RSA in a special case

Question

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

Answer 1

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