2
$\begingroup$

I have read that the RSA numeric signature works as the following:

  1. Generation of keys : $p,q,N,e,d$
  2. Process of signing the message $m$ (which is BigInteger) : it uses the secret key $sk=(p,q,d)$ so that $s=m^d\bmod N$ where $N=p*q$.
    Why do we use the secret key to sign the message?
    How I can hash the message ?
  3. Process of verification that uses the public key $pk=(N,e)$ and a couple (message $m$, potential signature $s$), and consists in: verifying whether the signature is valid (return true) or not (return false).

Can I get more information and explanation here in the verifying process? (I have read somewhere they use encrypt method and others use decrypt method).

$\endgroup$
  • $\begingroup$ I employ RSA to sign documents without using a hashing function. See Ex. 4 of s13.zetaboards.com/Crypto/topic/7234475/1/. $\endgroup$ – Mok-Kong Shen Jul 27 '16 at 9:20
  • $\begingroup$ @Mok-KongShen - I think that is a bad idea. See, for example, Bernstein's RSA signatures and Rabin–Williams signatures:the state of the art. Bernstein provides a survey of the history of RSA-based signature schemes, and why things like hashing is required. From the paper, "Section 2, hashing (1979 Rabin): Messages are scrambled by a public hash function H. A signature of m is an eth root of H(m), not an eth root of m. This is essential for security." $\endgroup$ – jww Feb 8 at 18:05
1
$\begingroup$
  1. We do use the secret key to sign the message as otherwise anybody would be able to sign messages (in your name!)
  2. You can hash a message by passing it to cryptographically secure hash function, like SHA-2/3 and interpret the resulting digest as integer $m$.

The verification (of plain RSA, please note: RSA is never deployed like this) of RSA-signatures works as follows:

  1. Obtain the message $M$ and the signature $s$ and the public key $(N,e)$
  2. Hash the message $M$ to get the "numerical" message $m=h(M)$.
  3. Compute $m'=s^e \bmod N$.
  4. Accept the signature (= return true) if and only if $s=s'$, otherwise reject the signature (= return false)

The step 3 equals to the plain RSA-encryption, hence it is sometimes referred to as "encryption".
The signing equation you cited above corresponds to the decryption operation of RSA public key encryption, therefore to ease understandability for beginners it is often described as "encryption using the private key" or as "decryption".

$\endgroup$
  • $\begingroup$ So as I already have the encryption and decryption in RSA, can I use them to proceed the 3rd step of Verification (encryption) and the signing equation (decryption) ? Thanks for the explanation, it really clears up my mind. $\endgroup$ – JPerk May 19 '15 at 19:26
  • $\begingroup$ If you're implementation is self-made and uses "plain" RSA, then yes, you can use your encryption routine for the step 3 of verification and your decryption routine for the signing operation. If you use some library chances are it applies counter-measures against certain attacks on RSA. And please note: Don't use the above description (as sole base) for real-world RSA. $\endgroup$ – SEJPM May 19 '15 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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