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

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


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

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

  • $\begingroup$ Also can we use any set of prime numbers for the generation of public and private keys? $\endgroup$
    – Sai Teja T
    Commented Jul 25, 2020 at 13:35

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.