Creating hash data signatures using RSA-CRT

Question

I have taken two prime numbers p=137 q=131 M=64 and i want to create a digital signature

n=pxq=17947
phi=(p-1)x(q-1)=17680
e=3                                     (I have taken public key e=3 as gcd(3,n)=1)
d=e^-1 mod phi
 =3^-1 mod 17680 = 11787
dP= d^-1 mod (p-1)
  = (11787)^-1 mod 136 = 3
dQ= d^-1 mod (q-1)
  = (11787)^-1 mod 130 = 3
qinv= q^-1 mod p 
    = (131)^-1 mod 137 = 114
mp= M ^dP mod p
  = 64^3 mod 137 = 87
mq= M ^dQ mod q
  = 64^3 mod 131 = 121
h= 114*(87-121) mod 137
 =97                              (after converting to positive remainder)
Sig= mq+ h*q
   =121+ 97*131
   =12828

Verification

 M= (Sig)^e mod N
 = (12828)^3 mod 17947
 = 8301

Not matching with the message M=64 . Where did i make a mistake?

Answer 1

The question's formula dP= d^-1 mod (p-1) is in error. Rather, $d_P=d\bmod(p-1)$, or more directly $d_P=e^{-1}\bmod(p-1)$, which makes it unnecessary to compute $d$. Same for $d_Q$. See this answer for proof of the formulas.

Use of CRT in RSA is an alternative computation modality for the transformation¹ $x\mapsto x^d\bmod n$. The conditions for the choice of $p$, $q$, $e$ remain unchanged. They depend on reference. Something common for theoretical work would be some small $e\ge3$, and $p$ and $q$ distinct large random primes such that $\gcd(e,p-1)=1=\gcd(e,q-1)$ and of about the same bit size.

---

Note: the question's computation is an illustration with small parameters of one of the steps of actual digital signature with RSA. But

• The primes used are way too small for security. Actual RSA keys use primes $p$ and $q$ with hundreds of decimal digits, so that the public modulus $n=p\,q$ is hard to factor.
• In an actual RSA digital signature, the input of the private key function is not the message. Rather, the message (an arbitrarily large piece of data) is hashed and padded to form the input of the $x\mapsto x^d\bmod n$ transformation.

---

¹ That private-key transformation is the inverse of the public-key transformation $y\mapsto y^e\bmod n$ when $n=p\,q$ and $e\,d\equiv1\pmod{\lambda(n)}$ or $e\,d\equiv1\pmod{\varphi(n)}$. These transformations are over the set $\Bbb Z_n$ or $\Bbb Z_n^*$. That depends on reference.