English Portuguese

Digital Signature Schemes

Suppose that you're building a client-server application and you want to ensure that all requests sent to the server were generated by the expected client. How could you do that? One possible solution is to use cryptographic signatures to guarantee the authenticity, integrity of the message and also 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. Client generates a RSA Key Pair - which in practice are two different strings that we call private key and public key;
  2. Client sends its public key to the Server through a *secure channel*;
  3. Client generates a message to be sent to the Server; let's call it M;
  4. Client computes the SHA256 (or any other agreed cryptographic hash function) digest of message M; let's call it D;
  5. Client uses its Private Key to encrypt D; let's call it ED (Encrypted Digest);
  6. Client sends to the server message M and encrypted digest D;
  7. Server computes the SHA256 digest of message M; let's call it D2;
  8. Server uses client's public key to decrypt ED to get D;
  9. Server compares D and D2; if there is a match, Server assumes that message M came from Client.

But there are other schemes such as:

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

It turns out that ECDSA is a good candidate. It's being used by important 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 discussed important security concerns.

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

  1. Client generates a 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. Client sends its public key to the Server through a *secure channel*;
  3. Client generates a message to be sent to the Server; let's call it M;
  4. Client computes the SHA256 (or any other agreed cryptographic hash function) digest of message M; let's call it D;
  5. Client uses its Private Key, a Temporary Private Key (that's another private key), and the digest D to generate a signature S;
  6. Client sends to the server message M, digest D and signature S;
  7. Server computes the SHA256 digest of message M; let's call it D2;
  8. If correct, Server then verifies the signature based on message M, digest D and signature S;
  9. If the verification is successful, Server assumes that message M came from 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

Fore more details and explanations regarding this Ruby implementation, I recommend you to check out the ECDSA gem's readme.

Some encoding / decoding operations that I left out of the example above to keep it short, but that 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 as DER
signature = ECDSA::Format::SignatureDerString.decode(signature_der_string)
#<ECDSA::Signature:0x0000000208d4a8 @s=51036925271636557127129380715379960169521069162282050255362609127261656403159, @r=38842626027885064704911875892562219385404736057609313785790205992887101198775>

That's all for today, thank you.


Share the knowledge :)

Share on Twitter Share on Facebook Share on Google Plus Share on LinkedIn Share on Hacker News