ALBANESE Research Lab 🔍

Software Engineering & Systems Integration Solutions

HOME | PROJECTS | UNIX TOOLS

EC-SDSA 🇧🇷 🇩🇪

Elliptic Curve-based Schnorr Digital Signature Algorithm

---

EC-SDSA Signature Scheme

Albanese, Pedro F (2024).

Adopted as an International Standard (ISO/IEC 14888-3:2018)

EC-SDSA is a public-key cryptographic algorithm based on elliptic curve cryptography (ECC) and the Schnorr signature scheme, a highly efficient and secure signature algorithm. It is an alternative to the ECDSA (Elliptic Curve Digital Signature Algorithm) and offers several advantages in terms of simplicity, performance, and security.

Generate Key Pair

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

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

Sign

1. Hash the message \( m \) using \( H(m) \), which gives the hash value \( H(m) \).

2. Generate a random value \( k \) from \( ]0, q[ \), keep it secret, and ensure it is never reused.

3. Compute the point \( W = k \cdot G = (W_x, W_y) \) on the elliptic curve.

4. Compute \( r = H(W_x || W_y || m) \), where \( H \) is a hash function and \( r \) is the result reduced modulo \( q \). If \( r = 0 \), repeat from step 2.

5. Compute \( e = \text{OS2I}(r) \mod q \), where \( \text{OS2I}(r) \) is the integer representation of \( r \). If \( e = 0 \), repeat from step 2.

6. Compute \( s = (k + e \cdot d) \mod q \), where \( d \) is the private key. If \( s = 0 \), repeat from step 2.

7. The signature is the pair \( (r, s) \), which will be used for verification.

Verification

1. The signature consists of two values, \( r \) and \( s \). Verify that \( 0 < r < q \) and \( 0 < s < q \). If not, the signature is invalid.

2. Hash the message \( m \) to obtain \( H(m) \mod q \).

3. Compute \( w = s^{-1} \mod q \), the modular inverse of \( s \).

4. Compute the coefficients: \( u_1 = H(m) \cdot w \mod q \) and \( u_2 = r \cdot w \mod q \).

5. Compute the point \( W' = u_1 \cdot G + u_2 \cdot Y \) on the elliptic curve.

6. Compute \( r' = H(W'_x || W'_y || m) \), where \( W'_x \) and \( W'_y \) are the coordinates of the computed point \( W' \) and \( r' \) is the hash result reduced modulo \( q \).

7. The signature is valid if and only if \( r = r' \). If \( r \neq r' \), the signature is invalid.

Go Playground
Test This Example.

Hardcoded in Golang

package main

import (
	"bytes"
	"crypto/elliptic"
	"crypto/rand"
	"crypto/sha256"
	"fmt"
	"io"
	"math/big"

	"golang.org/x/crypto/cryptobyte"
	"golang.org/x/crypto/cryptobyte/asn1"
)

// PrivateKey is a structure of a private key with an embedded public key.
type PrivateKey struct {
	PublicKey
	D *big.Int
}

// PublicKey contains the public key.
type PublicKey struct {
	Curve elliptic.Curve
	X, Y  *big.Int
}

// GenerateKey generates a private key for an elliptic curve.
func GenerateKey(random io.Reader, c elliptic.Curve) (*PrivateKey, error) {
	d, err := randFieldElement(random, c)
	if err != nil {
		return nil, err
	}

	priv := new(PrivateKey)
	priv.PublicKey.Curve = c
	priv.D = d
	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(d.Bytes())

	return priv, nil
}

// randFieldElement returns a random number from the field order of an elliptic curve.
func randFieldElement(rand io.Reader, c elliptic.Curve) (k *big.Int, err error) {
	for {
		N := c.Params().N
		b := make([]byte, (N.BitLen()+7)/8)
		if _, err = io.ReadFull(rand, b); err != nil {
			return
		}

		if excess := len(b)*8 - N.BitLen(); excess > 0 {
			b[0] >>= excess
		}

		k = new(big.Int).SetBytes(b)
		if k.Sign() != 0 && k.Cmp(N) < 0 {
			return
		}
	}
}

// Sign generates a signature for the data.
func Sign(rand io.Reader, priv *PrivateKey, data []byte) ([]byte, error) {
	h := sha256.New()
	h.Write(data)
	digest := h.Sum(nil)

	r, s, err := SignToRS(rand, priv, digest)
	if err != nil {
		return nil, err
	}

	return encodeSignature(r, s)
}

// SignToRS signs the message using the private key and returns the r and s values of the signature.
func SignToRS(rand io.Reader, priv *PrivateKey, digest []byte) (r, s *big.Int, err error) {
	h := sha256.New()

	curve := priv.Curve
	curveParams := curve.Params()
	n := curveParams.N

Retry:
	// 1. Get a random value k in ]0, q[
	k, err := randFieldElement(rand, priv.Curve)
	if err != nil {
		return
	}

	// 2. Compute W = kG = (Wx, Wy).
	x1, _ := curve.ScalarBaseMult(k.Bytes())

	// 3. Compute r = H(Wx || m)
	Wx := make([]byte, (curve.Params().P.BitLen()+7)/8)
	x1.FillBytes(Wx)
	h.Write(Wx)
	h.Write(digest)
	eBuf := h.Sum(nil)

	r = new(big.Int)
	r.SetBytes(eBuf)

	// 4. Compute e = OS2I(r) mod q
	e := new(big.Int).Set(r)
	e.Mod(e, n)

	if e.Cmp(big.NewInt(0)) == 0 {
		goto Retry
	}

	// 6. Compute s = (k + ex) mod q.
	ex := new(big.Int)
	ex.Mod(ex.Mul(e, priv.D), n)

	s = new(big.Int)
	s.Mod(s.Add(k, ex), n)

	// 7. if s == 0, restart at step 1.
	if s.Cmp(big.NewInt(0)) == 0 {
		goto Retry
	}

	return r, s, nil
}

// encodeSignature encodes the signature (r, s) in ASN.1 format.
func encodeSignature(r, s *big.Int) ([]byte, error) {
	var b cryptobyte.Builder
	b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
		b.AddASN1BigInt(r)
		b.AddASN1BigInt(s)
	})

	return b.Bytes()
}

// Verify verifies the signature for the data using the public key.
func Verify(pub *PublicKey, data, sig []byte) bool {
	h := sha256.New()
	h.Write(data)
	digest := h.Sum(nil)

	r, s, err := parseSignature(sig)
	if err != nil {
		return false
	}

	return VerifyWithRS(pub, digest, r, s)
}

// VerifyWithRS verifies the signature using the r and s values.
func VerifyWithRS(pub *PublicKey, digest []byte, r, s *big.Int) bool {
	curve := pub.Curve
	curveParams := pub.Curve.Params()
	n := curveParams.N

	// Check if s is in the range ]0, q[
	if s.Cmp(n) >= 0 {
		return false
	}

	// 2. Compute e = -r mod q
	rmodq := new(big.Int)
	rmodq.Mod(r, n)

	e := new(big.Int)
	e.Mod(e.Neg(rmodq), n)

	// 3. If e == 0, reject the signature.
	if e.Cmp(big.NewInt(0)) == 0 {
		return false
	}

	// 4. Compute W' = sG + eY
	x21, y21 := curve.ScalarMult(pub.X, pub.Y, e.Bytes())
	x22, y22 := curve.ScalarBaseMult(s.Bytes())
	x2, _ := curve.Add(x21, y21, x22, y22)

	// 5. Compute r' = H(W'x || m)
	Wx := make([]byte, (curve.Params().P.BitLen()+7)/8)
	x2.FillBytes(Wx)

	h := sha256.New()
	h.Write(Wx)
	h.Write(digest)
	rPrime := h.Sum(nil)

	rBytes := make([]byte, len(rPrime))
	r.FillBytes(rBytes)

	return bytes.Equal(rBytes, rPrime)
}

// parseSignature parses the signature (r, s).
func parseSignature(sig []byte) (r, s *big.Int, err error) {
	var inner cryptobyte.String
	input := cryptobyte.String(sig)

	r = new(big.Int)
	s = new(big.Int)

	if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
		!input.Empty() ||
		!inner.ReadASN1Integer(r) ||
		!inner.ReadASN1Integer(s) ||
		!inner.Empty() {
		return nil, nil, fmt.Errorf("invalid ASN.1 signature")
	}

	return r, s, nil
}

// PrintPrivateKey prints the details of the private key.
func PrintPrivateKey(privKey *PrivateKey) {
	fmt.Println("Private key:")
	fmt.Println("D:", privKey.D)

	// Accessing the public key components.
	fmt.Println("Public key:")
	fmt.Println("X:", privKey.PublicKey.X)
	fmt.Println("Y:", privKey.PublicKey.Y)
}

func main() {
	// Generating the private key for the P-384 curve
	privKey, err := GenerateKey(rand.Reader, elliptic.P384())
	if err != nil {
		fmt.Println("Error generating the key:", err)
		return
	}

	// Printing the private and public keys
	PrintPrivateKey(privKey)

	// Data to be signed
	data := []byte("Message to be signed")

	// Generating the signature
	signature, err := Sign(rand.Reader, privKey, data)
	if err != nil {
		fmt.Println("Error signing the message:", err)
		return
	}

	fmt.Println("Generated signature:", signature)

	// Verifying the signature
	valid := Verify(&privKey.PublicKey, data, signature)
	if valid {
		fmt.Println("Signature is valid!")
	} else {
		fmt.Println("Signature is invalid!")
	}
}

Reference

Digital Signature Mechanisms with Appendix, ISO/IEC 14888-3:2018.
ECC Technical Guideline BSI TR-03111, subsection 4.2.3.

Check also:
- Belarus Digital Signature Standard, BignV1 (STB 34.101.45-2013).

---

Examples

Generate Key Pair:

./edgetk -pkey keygen -algorithm ecsdsa [-bits 384] -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 ecsdsa -md sha256 -key "Private.pem" FILE > sign.txt

Transmit the Signature:

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

Verify Signature:

./edgetk -pkey verify -algorithm ecsdsa -md sha256 -key "Public.pem" -signature $sign FILE
echo $?

This example uses the standard US FIPS 180-2 Secure Hash Standard (SHS) SHA2 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
• EC-SDSA Signature Scheme
• BN256 Cryptosystem
• ECC Encryption
• SE (Sistema Eleitoral) 🇧🇷
• SUITE 🇧🇷
• SURF 🇧🇷
• Support Chat



Page views: 74817