# Creating hash data signatures using RSA-CRT

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?

• Also can we use any set of prime numbers for the generation of public and private keys? – Tileti SaiTeja Reddy Jul 25 at 13:35

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