ALBANESE Research Lab 🔍

Software Engineering & Systems Integration Solutions

HOME | PROJECTS | UNIX TOOLS

ECDSA 🇧🇷 🇺🇸

Elliptic Curve-based Digital Signature Algorithm

---

ECDSA Signature Scheme

Albanese, Pedro F (2024).

Adopted as a Standard in United States (NIST FIPS 186-4)

ECDSA (Elliptic Curve Digital Signature Algorithm) is a widely-used public key cryptographic algorithm based on elliptic curve cryptography (ECC) developed by NSA, providing high security with smaller key sizes compared to traditional algorithms like RSA. The algorithm is derived from the ElGamal signature scheme and uses Weierstrass curves. It relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP), a computationally difficult problem, ensuring the security of the algorithm. ECDSA is commonly used in various security protocols, including Bitcoin, TLS/SSL, and more.

Generate Key Pair

1. The private key \( d \) is randomly selected from the set \( \mathbb{Z}_n \), where \( n \) is the order of the elliptic curve group. The value of \( d \) must remain secret.

2. The public key \( Q \) is computed as \( Q = d \cdot G \), where \( G \) is the generator point of the elliptic curve.

Sign

1. Choose a random value \( k \) from \( \mathbb{Z}_n \), keep it secret, and ensure it's never reused.

2. Compute \( (x_1, y_1) = k \cdot G \) on the elliptic curve. Then, compute \( r = x_1 \mod n \). If \( r = 0 \), choose a new \( k \).

3. Hash the message \( M \) using \( H(M) \). Then, compute \( e = H(M) + d \cdot r \mod n \).

4. Compute \( s \equiv k^{-1} \cdot e \mod n \), where \( k^{-1} \) is the modular inverse of \( k \).

5. If \( s = 0 \), repeat the signing process with a new \( k \). The signature is the pair \( (r, s) \).

Verification

1. The signature consists of two values, \( r \) and \( s \). For verification, check that \( 0 < r < n \) and \( 0 < s < n \).

2. Hash the message \( M \) and compute \( e = H(M) \mod n \).

3. Compute the modular inverse of \( s \), denoted \( s^{-1} \mod n \). Then, compute \( (x_2, y_2) = s^{-1} \cdot (e \cdot G + r \cdot Q) \).

4. Check if \( x_2 \equiv r \mod n \). If true, the signature is valid. Otherwise, it’s invalid.

Go Playground
Test This Example.

Hardcoded in Golang

package main

import (
	"crypto/elliptic"
	"crypto/rand"
	"fmt"
	"math/big"
	"sync"

	"golang.org/x/crypto/sha3"
)

// Initialize the elliptic curve parameters
var initonce sync.Once
var p256 *elliptic.CurveParams

// Initialize the P-256 curve parameters
func init() {
	initP256()
}

func initP256() {
	p256 = new(elliptic.CurveParams)
	p256.P, _ = new(big.Int).SetString("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", 16)
	p256.N, _ = new(big.Int).SetString("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551", 16)
	p256.B, _ = new(big.Int).SetString("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B", 16)
	p256.Gx, _ = new(big.Int).SetString("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296", 16)
	p256.Gy, _ = new(big.Int).SetString("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5", 16)
	p256.BitSize = 256
	p256.Name = "secp256r1"
}

// Function to return the P-256 curve
func P256() elliptic.Curve {
	initonce.Do(initP256)
	return p256
}

// Structure for the public key, which will be represented only by the coordinates (x, y)
type PublicKey struct {
	X, Y *big.Int
}

// Generate the private key and the public key
func generateKeyPair(curve elliptic.Curve) (*big.Int, *PublicKey) {
	// Generate the private key (random number)
	privateKey, err := rand.Int(rand.Reader, curve.Params().N)
	if err != nil {
		panic(err)
	}

	// Calculate the public key Q = d * G (multiply the base point G by the private key d)
	Qx, Qy := curve.ScalarBaseMult(privateKey.Bytes())

	// Return the private key and the public key
	publicKey := &PublicKey{
		X: Qx,
		Y: Qy,
	}

	return privateKey, publicKey
}

// ECDSA signature function manually (without using a library)
func signMessage(message []byte, privateKey *big.Int, curve elliptic.Curve) (*big.Int, *big.Int) {
	// Hash the message using SHA3 (Keccak256)
	hash := sha3.Sum256(message)
	hashInt := new(big.Int).SetBytes(hash[:])

	// Choose a random value k
	k, err := rand.Int(rand.Reader, curve.Params().N)
	if err != nil {
		panic(err)
	}

	// Calculate the point (x1, y1) = k * G
	x1, _ := curve.ScalarBaseMult(k.Bytes())

	// Calculate r = x1 % n
	r := new(big.Int).Mod(x1, curve.Params().N)
	if r.Sign() == 0 {
		// If r == 0, choose a new k
		return signMessage(message, privateKey, curve)
	}

	// Calculate e = H(M) + d * r % n
	e := new(big.Int).Add(hashInt, new(big.Int).Mul(privateKey, r))
	e.Mod(e, curve.Params().N)

	// Calculate s = k^-1 * e % n
	kInv := new(big.Int).ModInverse(k, curve.Params().N)
	s := new(big.Int).Mul(kInv, e)
	s.Mod(s, curve.Params().N)

	if s.Sign() == 0 {
		// If s == 0, choose a new k
		return signMessage(message, privateKey, curve)
	}

	return r, s
}

// Manual ECDSA signature verification function
func verifySignature(message []byte, r, s *big.Int, publicKey *PublicKey, curve elliptic.Curve) bool {
	// Verify if r or s are out of bounds, if so, the signature is invalid
	if r.Sign() <= 0 || r.Cmp(curve.Params().N) >= 0 || s.Sign() <= 0 || s.Cmp(curve.Params().N) >= 0 {
		return false
	}

	// Hash the message using SHA3 (Keccak256)
	hash := sha3.Sum256(message)
	hashInt := new(big.Int).SetBytes(hash[:])

	// Calculate v = s^-1 % n
	sInv := new(big.Int).ModInverse(s, curve.Params().N)

	// Calculate the point (x2, y2) = s^-1 * (e * G + r * Q)
	e := new(big.Int).Mul(sInv, hashInt)
	e.Mod(e, curve.Params().N)

	// Calculate rTerm = s^-1 * r % n
	rTerm := new(big.Int).Mul(sInv, r)
	rTerm.Mod(rTerm, curve.Params().N)

	// Calculate the point (x2, y2) = rTerm * Q (point of the public key)
	x2, y2 := curve.ScalarMult(publicKey.X, publicKey.Y, rTerm.Bytes())

	// Now add the points (x3, y3) = (e * G) + (rTerm * Q)
	x3, y3 := curve.ScalarMult(curve.Params().Gx, curve.Params().Gy, e.Bytes()) // e * G

	// Add the points (x3, y3) = (e * G) + (rTerm * Q)
	x3, y3 = curve.Add(x3, y3, x2, y2)

	// Verify if x3 is congruent to r (mod n)
	return x3.Cmp(r) == 0
}

func main() {
	// Use the P-256 curve (common in ECDSA)
	curve := P256()

	// Generate the private key and public key
	privateKey, publicKey := generateKeyPair(curve)

	// Message to be signed
	message := []byte("This is a secret message!")

	// Sign the message
	r, s := signMessage(message, privateKey, curve)
	fmt.Printf("Signature: r = %s, s = %s\n", r.String(), s.String())

	// Verify the signature
	valid := verifySignature(message, r, s, publicKey, curve)
	if valid {
		fmt.Println("The signature is valid!")
	} else {
		fmt.Println("The signature is invalid!")
	}
}

Reference

Digital Signature Standard (DSS) NIST FIPS 186-4, 2013.

Check also:
- Korean Certificate-based Digital Signature Algorithm, EC-KCDSA (TTAK.KO-12.0015/R3).
- Belarus Digital Signature Standard, BignV1 (STB 34.101.45-2013).

---

Examples

Generate Key Pair:

./edgetk -pkey keygen -algorithm ecdsa [-bits 521] -prv "Private.pem" [-pass "passphrase"] -pub "Public.pem"

Parse Keys:

./edgetk -pkey text -key "Private.pem" [-pass "passphrase"]
./edgetk -pkey text -key "Public.pem"

Generate Signature:

./edgetk -pkey sign -algorithm ecdsa -md sha3-256 -key "Private.pem" FILE > sign.txt

Transmit the Signature:

sign=$(cat sign.txt|awk '{print $2}')

Verify Signature:

./edgetk -pkey verify -algorithm ecdsa -md sha3-256 -key "Public.pem" -signature $sign FILE
echo $?

This example uses the standard US FIPS 202 SHA-3 Permutation-Based Hash (instance of the Keccak) for pre-hashing.

---

LICENSE

Copyright (c) 2024 Pedro F. Albanese <pedroalbanese@hotmail.com>

Permission to use, copy, modify, and distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

---

• Home
• My Projects
• Unix Tools for Windows
• EDGE Toolkit
• ElGamal Cryptosystem
• ECDSA Signature Scheme
• BN256 Cryptosystem
• ECC Encryption
• SUITE 🇧🇷
• SURF 🇧🇷
• Support Chat



Page views: 67352