I've found this explanation regarding signature verification but I still confused

In the example in the picture, the sender sign the hash using his secret key. The output of signing produces a signature.

The receiver takes as input the signature and with the public key (sent with the message) verify it using verification algorithm and produce the hash as output. According to what I understand, the receiver performs the revere action, which is equivalent to encryption /decryption, using private/public key instead of the same private key.

Any clarification, please?

enter image description here


This diagram is not accurate. Hashing is not a separate step outside signing for the convenience of handling long messages; hashing is an integral part of signing that is necessary for security. And the verification algorithm does not always return a hash that you can compute separately: it only returns a boolean that indicates a valid signature or not. In particular, signature is not ‘encryption with the private key’, which is a contradiction in terms, and very few signature schemes even resemble that idea. Here is an accurate diagram:

Diagram of a signature scheme: signature algorithm run by signer takes private key and data and returns signature; verification algorithm run by verifier takes public key, signature, and data, and returns boolean for valid or invalid.

Note that hashing doesn't figure into this diagram, because it sits inside the signature algorithm and the verification algorithm; the user, who calls the signature algorithm or calls the verification algorithm, is not concerned with the hash function.

How does it work inside? Let's examine an example of an RSA-based randomized signature scheme, RSA-PSS, which is related to (but better than) the standard RSASSA-PSS algorithm of IEEE P1363-2000 and PKCS#1 v2.1:

RSA-PSS embedded in signature and verification diagram: s^3 \equiv 2^t r + H(r \mathbin\| m) \pmod n

There is a hashing step inside, but it is randomized with randomization that is embedded in the signature, so it's not just that we compute $\operatorname{MD5}(m)$—which would make us vulnerable to collisions in MD5! If we skipped the hashing step, using $s^3 \equiv m \pmod n$ as the verification equation, the signature scheme would be totally insecure, e.g. I could forge 3 as a signature on the message 9—this is why hashing is not a separate step for the convenience of long messages, but actually crucial for something to be a secure signature algorithm at all.

In other signature schemes like Ed25519, there is no hash concealed within the signature that the verifier compares against a recomputed hash: a valid signature under a public key $A$ is a pair $(R, s)$ of a point $R$ and a scalar $s$ such that $[s]B = R + [H(R, A, m)]A$; here we are working in an elliptic curve, namely edwards25519, with standard base point $B$. The hash $H(R, A, m)$ uses inputs that are embedded in the signature, so like RSA-PSS the hash can't be computed separately without the signature; and then the hash figures into some fancy math that returns a boolean answer $[s]B \stackrel?= R + [H(R, A, m)]A$ directly.

Ed25519 embedded in signature and verification diagram: [s]B = R + [H(R, A, m)]A

| improve this answer | |
  • $\begingroup$ Thanks for the detailed info. I did not quite get how the random r value appeared on the verifier side in the first graph. Does it also get passed via the signature itself? $\endgroup$ – stdout May 5 at 21:32

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.