2
$\begingroup$

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

  • 0
    @NItin, what do you want to know?2011-05-07
  • 1
    @quanta i have edited the question to make it more clear.2011-05-07
  • 2
    Is there some part of RSA you don't understand or what?2011-05-07
  • 0
    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.2011-05-07
  • 0
    @NItin, Something is calculated incorrectly? What should it have been and what is it?2011-05-07
  • 1
    M^d mod q is not calculated correctly. It is something other then M^d mod q.2011-05-07

1 Answers 1

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

  • 0
    I just figured out the exact same solution an hour ago. What a coincidence. Thanks for confirming :)2011-05-07
  • 0
    gcd(M' - M,n) would be equal to q.2011-05-07
  • 0
    @NItin, This is just a hint. One still has to actually come up with a theorem and prove it.2011-05-07
  • 0
    yeah. I have worked it out.:)2011-05-08