Practical Cryptography — Part XI
What are Digital Signatures?
These are authentication mechanisms which are used to sign messages and verify message signatures. They provide:
- Authentication, a proof that a key owner created and signed the message
- Integrity, a proof that the message wasn’t tampered after signing
- Non-repudiation, proof that the signature cannot deny the signing of the document once the signature is created
Digital signatures cannot identify the person who created the signature, which is a problem that is solved using digital certificates along with signatures.
Digital certificates binds the public key owner with the identity of a person or an organization.
How does Message Signing Work?
Digital Signature mechanisms use public-key cryptosystems like RSA. A message is signed by a private key and verified using the corresponding public key.
Input message is hashed and then the signature is calculated using an algorithm, which often perform operations on the hash and the signing key.
Signing(message, privateKey) → Signature
Verification(message, signature, pubKey) →0/1
Steps:
- Input message is hashed, standalone or with the public key
- Digital Signature is calculated using complex math, ecc or discrete logs
- Signed message now consists of original message and calculated signature
- At the other end, message is hashed, digital signature is verified using public key
- Comparisons of outputs verifies the digital signature
Digital Signatures vs MACs
- MACs are created and verified by the same secret key using symmetric algorithms
- Digital signatures are created by a signing key and verified using a different key, using asymmetric algorithms
- Both methodologies provide message authentication, message integrity and user non-repudiation
RSA Signatures
- Provides cryptographic secure signing and verification scheme
- Based on modular exponentiation, discrete logarithms and the difficulty of the Integer factorization problem
RSA Signing Process
- RSA signing algorithm hashes a message, encrypts the hash with the private key to obtain a signature, which is an integer number
- RSA verification algorithm computes the message hash, decrypts the message signature with the public key and compares the hashes of the decrypted hash and the hash in the signed message
Code in Python
ECDSA
Elliptic Curve Digital Signature Algorithm relies on the math of cyclic groups of elliptic curves over finite fields and on the difficulty of the Elliptic-Curve Discrete Logarithm problem.
ECDSA Signing Process
- The ECDSA signing algorithm calculates a message hash, generates a random integer k, and calculates the signature {r,s} where r is computed from k and s is computed from message hash + private key +random number k
- ECDSA becomes non-deterministic due to the added randomness of the random number k. Contrary to common sense, this non-deterministic trait, makes the private key vulnerable to recovery by attackers
- Note: Instead of using a random number k, replace it with HMAC for security, and use a deterministic ECDSA, which is more secure
- ECDSA signature verification algorithm involves computations based on message hash, public key and the signature {r,s}
Note: Public Key Recovery from ECDSA Signature
ECDSA signature technique allows a public key to be recovered from the signed messages together with the signature.
It is useful in bandwidth constrained or storage constrained environments, like blockchains. Extended signatures, {r,s} → {r,s,v}, use an additional bit v to remove the ambiguity in 0, 1 or 2 EC points being considered public keys, to make them deterministic.
This technique is feasible for signatures based on ElGamal Signature scheme like ECDSA.
