ALBANESE Research Lab 🔍
Software Engineering & Systems Integration Solutions
BignV1 🇧🇷 🇧🇾
Deterministic and Stochastic Schnorr Signature Scheme
BignV1 Signature Scheme
Albanese, Pedro F (2024).Adopted as the standard in Belarus (STB 34.101.45-2013)
The Bign algorithm is a Schnorr-type signature scheme used in the Belarusian cryptographic standard. Below are the detailed equations and descriptions for the signing and verification phases of BignV1. It is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), a well-known and computationally difficult problem that underpins the security of elliptic curve-based cryptography. The algorithm utilizes Weierstrass curves, a specific type of elliptic curve, to enhance its security and efficiency. BignV1 provides a secure and efficient solution for digital signatures, offering both stochastic and deterministic implementations of the ephemeral key generation.
Parameters
\( l \) ∈ {128, 192, 256} — Security level.
\( q \) — A \( 2^l \)-bit prime number.
\( G \) — A generator of an Abelian group \( \langle G \rangle \) of order \( q \).
\( H \) — An external hash function: \( H: \{0, 1\}^* \to \{0, 1\}^{2l} \).
\( OID(H) \) — An identifier uniquely identifying the hash function \( H \) (an ASN.1 object identifier).
\( h \) — An internal hash function: \( h: \{0, 1\}^* \to \{0, 1\}^l \).
Private Key
\( d \) — A secret random/pseudorandom element from \( \{1, 2, \dots, q-1\} \).
Public Key
\( Q = d \cdot G \) — The public key associated with the private key \( d \).
Message to be Signed
\( X \) ∈ \( \{0, 1\}^* \).
Signing
The signature \( s \) of a message \( X \) is generated as follows:
1. Choose \( k \): Select a random (or pseudorandom) value \( k \) from \( \{1, 2, \dots, q-1\} \).
2. Calculate \( R \): \( R = k \cdot G \).
3. Calculate \( s_0 \): \( s_0 = h(OID(H) \parallel R \parallel H(X)) \).
4. Calculate \( s_1 \): \( s_1 = (k - H(X) - (s_0 + 2^l) d) \mod q \).
5. Final signature: \( s = s_0 \parallel s_1 \) — The final signature \( s \) is the concatenation of \( s_0 \) and \( s_1 \).
6. Return the signature: The signature \( s \) is returned.
Verification
To verify the signature \( s = s_0 \parallel s_1 \) of a message \( X \) with public key \( Q \):
1. Verify the length of \( s \): If \( |s| \neq 3l \), return 0 (invalid signature).
2. Extract \( s_0 \) and \( s_1 \): Split \( s = s_0 \parallel s_1 \), where \( |s_0| = l \) and \( |s_1| = 2l \).
3. Verify \( s_1 \): If \( s_1 \geq q \), return 0 (invalid signature).
4. Calculate \( R \): Compute \( R = (s_1 + H(X))G + (s_0 + 2^l)Q \).
5. Verify \( R \): If \( R = O \) (the identity element of the group), return 0 (invalid signature).
6. Verify the hash: If \( h(OID(H) \parallel R \parallel H(X)) \neq s_0 \), return 0 (invalid signature).
7. Valid signature: If all checks pass, return 1 (valid signature).
Design Rationale
• Short signatures: The algorithm uses Schnorr's compression and reduces the length of \( s_0 \) from \( 2l \) to \( l \) bits, resulting in shorter signatures and faster verification (1.5 exponentiations instead of 2).
• Pre-hashing: Instead of directly using \( h(R \parallel X) \), the algorithm uses pre-hashing: \( s_0 = h(OID(H) \parallel R \parallel H(X)) \). This protects against multiple-target preimage attacks and facilitates integration with existing APIs and data formats.
• "Whitening" the signature: The second part of the signature (\( s_1 \)) is "whitened" by using \( Y = H(X) \). This makes finding collisions more difficult, providing security with strength \( 2^l \).
• Use of \( Q \) during verification: While hashing \( Q \) during signature generation could help protect against certain attacks, this approach is rejected, as key distribution should already provide protection, and hashing \( Q \) would duplicate the proof of possession during key distribution.
• Deterministic signature: The generation of the ephemeral public key \( k \) can be made deterministic using a special key generation algorithm \( genk \). This involves hashing and symmetric encryption of data such as \( OID(H) \), \( d \), and \( H(X) \) to produce a unique \( k \).
Usage
package main import ( "fmt" "hash" "github.com/pedroalbanese/belt/hash/belt" "github.com/pedroalbanese/bign" "github.com/pedroalbanese/bign/curves" "crypto/rand" ) func main() { // Using the P256 curve as an example curve := curves.P256v1() // Generate private and public keys using the BignV1 library privKey, err := bign.GenerateKey(rand.Reader, curve) if err != nil { fmt.Println("Error generating private key:", err) return } pubKey := &privKey.PublicKey // Hardcoded data for the message and additional data msg := []byte("Example message") adata := bign.MakeAdata([]byte("OID"), []byte("additional data")) // Create a hash instance using the Belt library hashFunc := belt.New() // Sign the message with the private key using BignV1 sig, err := privKey.Sign(nil, msg, &bign.SignerOpts{ Hash: func() hash.Hash { return hashFunc }, Adata: adata, }) if err != nil { fmt.Println("Error signing the message:", err) return } // Create a new instance of the hash using the Belt library hashFunc.Reset() // Verify the signature with the public key using BignV1 valid, err := pubKey.Verify(msg, sig, &bign.SignerOpts{ Hash: func() hash.Hash { return hashFunc }, Adata: adata, }) if err != nil { fmt.Println("Error verifying the signature:", err) return } // Display the verification result if valid { fmt.Println("The signature is valid.") } else { fmt.Println("The signature is invalid.") } // Show the ASN.1 encoded signature fmt.Printf("ASN.1 encoded signature: %x\n", sig) }
Reference
Belarusian Standard STB 34.101.45-2013.Examples
Generate Key Pair:
Parse Keys:./edgetk -pkey keygen -algorithm bign [-bits 512] -prv "Private.pem" [-pass "passphrase"] -pub "Public.pem"
Generate Deterministic Signature:./edgetk -pkey text -key "Private.pem" [-pass "passphrase"]
./edgetk -pkey text -key "Public.pem"
Generate Stochastic Signature:./edgetk -pkey sign -algorithm dbign -md belt -id "OID" -info "AAD" -key "Private.pem" FILE > sign.txt
Transmit the Signature:./edgetk -pkey sign -algorithm bign -md belt -id "OID" -key "Private.pem" FILE > sign.txt
Verify Signature:sign=$(cat sign.txt|awk '{print $2}')
./edgetk -pkey verify -algorithm bign -md belt -id "OID" -key "Public.pem" -signature $sign FILE
echo $?
This example uses STB 34.101.31-2011 (Bel-T) Hash Function, whose OID is "1.2.112.0.2.0.34.101.31.81", but BASH Hash Function STB 34.101.77-2020 Belarusian Standard is recommended 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.
