Return to Answer

Creating a digital signature for a message involves running the message through a hash function, creating a digest (a fixed-size representation) for the message. A mathematical operation is done on the digest using a secret value (a component of the private key) and a public value (a component of the public key). The result of this operation is the signature, and it is usually either attached to the message or otherwise delivered alongside it. Anyone can tell, just by having the signature and public key, if the message was signed by someone in possession of the private key. So, how does this work?

To use textbook RSA as an example of asymmetric cryptography, encrypting a message m into ciphertext c is done by calculating c ≡ m^e (mod N), where e is a public value (usually a Fermat prime), and N is the non-secret product of two secret prime numbers. Signing a hash m, on the other hand, involves calculating s ≡ m^d (mod N), where d is the modular inverse of e, being a secret value derived from the secret prime numbers. This is much closer to decryption than it is to encryption, though calling signing decryption is still not quite right. Note that other asymmetric algorithms may use completely different techniques. RSA is merely a common enough algorithm to use as an example.

The security of signing comes from the fact that d is difficult to obtain without knowing the secret prime numbers. In fact, the only known way to obtain d from N is to factor N into its component primes, p and q, and calculate d ≡ e^-1 mod (p - 1)(q - 1). Factoring very large integers is believed to be an intractable problem for classical computers. This makes it possible to easily verify a signature, as that involves determining if s^e ≡ m (mod N). Creating a signature, however, requires knowledge of the private key.

Creating a digital signature for a message involves running the message through a hash function, creating a digest (a fixed-size representation) for the message. A mathematical operation is done on the digest using a secret value (a component of the private key) and a public value (a component of the public key). The result of this operation is the signature, and it is usually either attached to the message or otherwise delivered alongside it. Anyone can tell, just by having the signature and public key, if the message was signed by someone in possession of the private key.

To use textbook RSA as an example of asymmetric cryptography, encrypting a message m into ciphertext c is done by calculating c ≡ m^e (mod N), where e is a public value (usually a Fermat prime for efficiency reasons), and N is the non-secret product of two secret prime numbers. Signing a hash m, on the other hand, involves calculating s ≡ m^d (mod N), where d is the modular inverse of e, being a secret value derived from the secret prime numbers. This is much closer to decryption than it is to encryption, though calling signing decryption is still not quite right. Note that other asymmetric algorithms may use completely different techniques. RSA is merely a common enough algorithm to use as an example.

The security of signing comes from the fact that d is difficult to obtain without knowing the secret prime numbers. In fact, the only known way to obtain d (or a value equivalent to d) from N is to factor N into its component primes, p and q, and calculate d = e^-1 mod (p - 1)(q - 1). Factoring very large integers is believed to be an intractable problem for classical computers. This makes it possible to easily verify a signature, as that involves determining if s^e ≡ m (mod N). Creating a signature, however, requires knowledge of the private key.

Although RSA signature generation is similar to RSA decryption on paper, there is a big difference to how it works in the real world. In the real world, a feature called padding is used, and this padding is absolutely vital to the algorithm's security. The way padding is used for encryption or decryption is different from the way it is used for a signature. The which follow are more technical...

To use textbook RSA as an example of asymmetric cryptography, encrypting a message m into ciphertext c is done by calculating c ≡ m^e (mod N), where e is a fixed value (usually a Fermat prime), and N is the non-secret product of two secret prime numbers. Signing a hash m, on the other hand, involves calculating s ≡ m^d (mod N), where d is the modular inverse of e, being a secret value derived from the secret prime numbers. This is much closer to decryption than it is to encryption, though calling signing decryption is still not quite right. Note that other asymmetric algorithms may use completely different techniques. RSA is merely a common enough algorithm to use as an example.

Although RSA signature generation is similar to RSA decryption on paper, there is a big difference to how it works in the real world. In the real world, a feature called padding is used, and this padding is absolutely vital to the algorithm's security. The way padding is used for encryption or decryption is different from the way it is used for a signature. The details which follow are more technical...

To use textbook RSA as an example of asymmetric cryptography, encrypting a message m into ciphertext c is done by calculating c ≡ m^e (mod N), where e is a public value (usually a Fermat prime), and N is the non-secret product of two secret prime numbers. Signing a hash m, on the other hand, involves calculating s ≡ m^d (mod N), where d is the modular inverse of e, being a secret value derived from the secret prime numbers. This is much closer to decryption than it is to encryption, though calling signing decryption is still not quite right. Note that other asymmetric algorithms may use completely different techniques. RSA is merely a common enough algorithm to use as an example.

I'll use RSA as an example algorithm. First, a little background on how RSA works. RSA encryption involves taking the message, represented as an integer, and raising it to the power of a known value (this value is most often 3 or 65537). This value is then divided by a public value that is unique to each public key. The remainder is the encrypted message. This is called a modulo operation. Signing with RSA is a little different. The message is first hashed, and the hash digest is raised to the power of a secret number, and finally divided by the same unique, public value in the public key. The remainder is the signature itself. This differs from encryption because, rather than raising a number to the power of a known, public value, it's raised to the power of a secret value that only the signer knows.

I'll use RSA as an example algorithm. First, a little background on how RSA works. RSA encryption involves taking the message, represented as an integer, and raising it to the power of a known value (this value is most often 3 or 65537). This value is then divided by a public value that is unique to each public key. The remainder is the encrypted message. This is called a modulo operation. Signing with RSA is a little different. The message is first hashed, and the hash digest is raised to the power of a secret number, and finally divided by the same unique, public value in the public key. The remainder is the signature. This differs from encryption because, rather than raising a number to the power of a known, public value, it's raised to the power of a secret value that only the signer knows.