Digital Signature Schemes

Suppose that you're building a client-server application and you want to ensure that all requests sent to the server are generated by the expected client. How could you do that? One possible solution is to use cryptographic signatures to guarantee the authenticity and integrity of the message, as well as non-repudiation.

The most popular signature scheme is to apply RSA encryption on the digest of the message to be signed using an agreed cryptographic hash function, e.g., SHA256.

It works like this:

1. The client generates an RSA Key Pair - which in practice are two different strings that we call private key and public key;
2. The client sends its public key to the Server through a *secure channel*;
3. The client generates a message to be sent to the Server; let's call it M;
4. The client computes the SHA256 (or any other agreed cryptographic hash function) digest of message M; let's call it D;
5. The client uses its Private Key to encrypt D; let's call it ED (Encrypted Digest);
6. The client sends to the server message M and encrypted digest ED;
7. The server computes the SHA256 digest of message M; let's call it D2;
8. The server uses the client's public key to decrypt ED to get D;
9. The server compares D and D2; if there is a match, the server assumes that message M came from the client.

But there are other schemes such as:

• ElGamal signature scheme (predecessor of DSA);
• DSA, and its elliptic curve variant ECDSA;
• And more.

So the question is: are there better algorithms than RSA for digital signatures?

It turns out that ECDSA is a good candidate. It's being used by important protocols, e.g., Bitcoin, SSH (preferred when learning a host's keys for the first time) and TLS.

There is a very good post from CloudFlare explaining why. That post also discusses important security concerns.

In short, it offers better performance, better security (smaller key needed to provide the same security as RSA) at the same time, but a few things change when signing an arbitrary message using ECDSA.

1. The client generates an ECC Key Pair - An ECDSA private key is a random number between 1 and the order of the group (ECC Param). The public key, on the other hand, consists of the coordinates of the point that is computed by multiplying the generator point of the curve with the private key. This is equivalent to adding the generator to itself private_key times;
2. The client sends its public key to the Server through a *secure channel*;
3. The client generates a message to be sent to the Server; let's call it M;
4. The client computes the SHA256 (or any other agreed cryptographic hash function) digest of message M; let's call it D;
5. The client uses its Private Key, a Temporary Private Key (that's another private key), and the digest D to generate a signature S;
6. The client sends to the server message M and signature S;
7. The server computes the SHA256 digest of message M; let's call it D2;
8. If correct, the server then verifies the signature based on message M, digest D2, and signature S;
9. **If the verification is successful, the server assumes that message M came from the client.

Here's a demonstration of how to sign a message using ECDSA:

require 'ecdsa' # not verified lib; used for explaining ECDSA only
require 'securerandom'
require 'digest'

# ECC Curve Params
group = ECDSA::Group::Secp256k1
#<ECDSA::Group:secp256k1>

private_key = 1 + SecureRandom.random_number(group.order - 1)
# 16081229817702338787208675065841607903056865046148280384413172801433877421416

public_key = group.generator.multiply_by_scalar(private_key)
#<ECDSA::Point: secp256k1, 0x3900317347e43259e192c4e7b6b73edcaa8b2fda746ad1053fed8ad535b579f9, 0x33b3eaaed3833e6143f7c1a1d3b95580bd0190f67c5ac0a2825a57bac6d2ee76>

# Generate Message
message = "My super message"
digest = Digest::SHA256.hexdigest message
# "b6ee4bf4e98fbe4ce9e6d25542abcaf3583fcf9519ad21e89463f0574cad5f78"

# Sign Message
yet_another_private_key_but_temporary = 1 + SecureRandom.random_number(group.order - 1)
# 81090463473665506610440159056867369065382225521276149238611272506738687296653
signature = ECDSA.sign(group, private_key, digest, yet_another_private_key_but_temporary)
#<ECDSA::Signature:0x0000000212c3c8 @s=51036925271636557127129380715379960169521069162282050255362609127261656403159, @r=38842626027885064704911875892562219385404736057609313785790205992887101198775>

# Verify Signature
valid = ECDSA.valid_signature?(public_key, digest, signature)
# true

There are some encoding/decoding operations that I left out of the example above to keep it short, but they are useful:

# Encode Public Key as a Binary String
public_key_string = ECDSA::Format::PointOctetString.encode(public_key, compression: true)
# "\x029\x001sG\xE42Y\xE1\x92\xC4\xE7\xB6\xB7>\xDC\xAA\x8B/\xDAtj\xD1\x05?\xED\x8A\xD55\xB5y\xF9"

# Decode Public Key from Binary String
public_key = ECDSA::Format::PointOctetString.decode(public_key_string, group)
#<ECDSA::Point: secp256k1, 0x3900317347e43259e192c4e7b6b73edcaa8b2fda746ad1053fed8ad535b579f9, 0x33b3eaaed3833e6143f7c1a1d3b95580bd0190f67c5ac0a2825a57bac6d2ee76>

# Encode signature as DER
signature_der_string = ECDSA::Format::SignatureDerString.encode(signature)
# "0D\x02 U\xE0%\xB1\xB6\xFE\xD7\x18:g\x04\x89_\b\xE7^\xAF!p\xF6[q\xFD4\x90\xE1<\xAC\xB6$\x91\xB7\x02 p\xD5\xE0CL\x1A\xF1y\x97\f\x1Fi\xE9\xCB\xCD\xEBI\x0Fc*\xB6+\xBA.\x8B\x99\x93\xA7\\\xD1L\xD7"

# Decode signature from DER
signature = ECDSA::Format::SignatureDerString.decode(signature_der_string)
#<ECDSA::Signature:0x0000000208d4a8 @s=51036925271636557127129380715379960169521069162282050255362609127261656403159, @r=38842626027885064704911875892562219385404736057609313785790205992887101198775>

For reference, you can check the library I used as the base for these examples at https://github.com/DavidEGrayson/ruby_ecdsa.

Please note that cryptography is a complex field and any security implementation should be done carefully. It is advisable to get assistance from a cryptography expert while designing and implementing such systems to avoid any potential flaws and exploits.