ALBANESE Research Lab 🔍

Software Engineering & Systems Integration Solutions

HOME | PROJECTS | UNIX TOOLS

BN256 Cryptosystem 🇧🇷

Elliptic Curve Bilinear Pairing-based Cryptographic Functions

---

Introduction to Pairing-Based Cryptography (PBC)

Albanese, Pedro F (2024).

Adopted as an International Standard (ISO/IEC 15946-5)

The Barreto-Naehrig 256-bit curve (BN256) is an elliptic curve used in pairing-based cryptography, specifically designed to enable efficient implementation of bilinear pairings, is a Weierstrass curve developed by Paulo S. L. M. Barreto (from Escola Politécnica da Universidade de São Paulo, Brazil) and Michael Naehrig (Microsoft). The BN256 curve is defined over a finite field of size \( 2^{256} \), and it is widely used in applications requiring pairing-based operations as BLS Signatures (Boneh–Lynn–Shacham) due to its efficiency and relatively small key size. BN256 is an International Standard (ISO/IEC 15946-5:2022).

Asymmetric Encryption

Key Generation

 • Private Key: \( sk \in \mathbb{Z}_n \), where \( \mathbb{Z}_n \) is the finite field used for private keys and \( n \) is the order of the elliptic curve.

 • Public Key: \( pk = sk \cdot G_2 \), where \( G_2 \) is the base point of the elliptic curve, and \( pk \) is the public key.

Encryption

 • Select a random value \( k \in [1, n-1] \), where \( n \) is the order of the group \( G_1 \).

 • Compute the point: \( C_1 = k \cdot G \), where \( G \) is the base point in \( G_1 \), the group used for encryption.

 • Pairing: \( e(C_1, pk) \), where \( C_1 \) is in \( G_1 \) and \( pk \) is in \( G_2 \). This pairing computes an element in the target group \( G_T \).

 • Derive the session key: \( S = H(e(C_1, pk)) \), where \( H \) is a cryptographic hash function applied to the pairing result.

 • Hash of the message: \( C_2 = H(m \parallel S) \)

 • Encrypt the message: \( C_3[i] = m[i] \oplus S[i \mod \text{len}(S)] \)

 • Ciphertext: \( (C_1, C_2, C_3) \), where \( C_1 \) is a point in \( G_1 \), \( C_2 \) is the hash of the message, and \( C_3 \) is the encrypted message.

Decryption

 • Compute the point: \( C_1' = sk \cdot C_1 \), where \( sk \) is the private key in \( G_2 \) and \( C_1 \) is in \( G_1 \).

 • Pairing: \( e(C_1', G) \), where \( C_1' \) is in \( G_1 \) and \( G \) is the base point in \( G_2 \). This pairing computes an element in the target group \( G_T \).

 • Derive the session key: \( S' = H(e(C_1', G)) \), where \( H \) is the cryptographic hash function applied to the pairing result.

 • Decrypt the message: \( m[i] = C_3[i] \oplus S'[i \mod \text{len}(S')] \)

 • Verify integrity: The hash \( H(m \parallel S') \) of the decrypted message should match the original hash.

Go Playground
Test This Example and the IBE Approach.

Hardcoded in Golang

package main

import (
	"crypto/sha256"
	"fmt"
	"math/big"
	"crypto/rand"
	"encoding/asn1"
	
	"github.com/pedroalbanese/bn256"
)

// Key generation (public and private keys)
func generateKeys() (*big.Int, *bn256.G2) {
	// Generate the private key (random number between 1 and the order of the curve)
	privateKey, err := rand.Int(rand.Reader, bn256.Order)
	if err != nil {
		panic(err)
	}

	// The public key is the private key multiplied by the generator point G
	publicKey := new(bn256.G2).ScalarBaseMult(privateKey)

	return privateKey, publicKey
}

// Encryption function
func encrypt(message string, publicKey *bn256.G2) (*bn256.G1, *big.Int, []byte) {
	// Convert the message to a byte array
	messageBytes := []byte(message)

	// Generate a random value k
	k, err := rand.Int(rand.Reader, bn256.Order)
	if err != nil {
		panic(err)
	}

	// Compute k * G (C1 point)
	C1 := new(bn256.G1).ScalarBaseMult(k)

	// Derive the session key from the pairing (k * pk)
	pairingResult := bn256.Pair(C1, publicKey)
	sessionKey := sha256.Sum256(pairingResult.Marshal())

	// Encrypt the message using the derived session key via XOR
	encryptedMessage := make([]byte, len(messageBytes))
	for i := range messageBytes {
		encryptedMessage[i] = messageBytes[i] ^ sessionKey[i%len(sessionKey)]
	}

	// Compute the hash of the message
	hash := sha256.Sum256(append(messageBytes, sessionKey[:]...))

	return C1, new(big.Int).SetBytes(hash[:]), encryptedMessage
}

// Decryption function
func decrypt(C1 *bn256.G1, C2 *big.Int, encryptedMessage []byte, privateKey *big.Int) string {
	// Compute sk * C1 (C1MulPrivate point)
	C1MulPrivate := new(bn256.G1).ScalarMult(C1, privateKey)

	// Derive the session key from the pairing (sk * C1)
	pairingResult := bn256.Pair(C1MulPrivate, new(bn256.G2).ScalarBaseMult(big.NewInt(1)))
	sessionKey := sha256.Sum256(pairingResult.Marshal())

	// Decrypt the message using the derived session key via XOR
	decryptedMessage := make([]byte, len(encryptedMessage))
	for i := range encryptedMessage {
		decryptedMessage[i] = encryptedMessage[i] ^ sessionKey[i%len(sessionKey)]
	}

	// Verify the integrity of the message using the hash
	hash := sha256.Sum256(append(decryptedMessage, sessionKey[:]...))
	if new(big.Int).SetBytes(C2.Bytes()).Cmp(new(big.Int).SetBytes(hash[:])) != 0 {
		panic("Message integrity has been compromised!")
	}

	// Convert the message back to a string
	return string(decryptedMessage)
}

// ASN.1 Serialization structures
type Ciphertext struct {
	C1  []byte // Marshal C1 to bytes
	C2  *big.Int
	C3  []byte // Encrypted message
}

// Serialize the ciphertext components into ASN.1 format
func serializeToASN1(C1 *bn256.G1, C2 *big.Int, encryptedMessage []byte) ([]byte, error) {
	// Marshal C1 to bytes
	C1Bytes := C1.Marshal()

	// Prepare the structure to hold the ciphertext components
	cipher := Ciphertext{
		C1:  C1Bytes,
		C2:  C2,
		C3:  encryptedMessage,
	}

	// Serialize using ASN.1 encoding
	serialized, err := asn1.Marshal(cipher)
	if err != nil {
		return nil, err
	}

	return serialized, nil
}

// Deserialize the ASN.1 format back into the ciphertext components
func deserializeFromASN1(serialized []byte) (*bn256.G1, *big.Int, []byte, error) {
	var cipher Ciphertext

	// Deserialize from ASN.1 format
	_, err := asn1.Unmarshal(serialized, &cipher)
	if err != nil {
		return nil, nil, nil, err
	}

	// Unmarshal C1 from bytes back into bn256.G1
	C1 := new(bn256.G1)
	_, err = C1.Unmarshal(cipher.C1)
	if err != nil {
		return nil, nil, nil, err
	}

	// Return the components of the ciphertext
	return C1, cipher.C2, cipher.C3, nil
}

func main() {
	// Generate public and private keys
	privateKey, publicKey := generateKeys()

	// The message to encrypt
	message := "Hello, this is a secret message!"

	// Encrypt the message
	C1, C2, encryptedMessage := encrypt(message, publicKey)
	fmt.Printf("Encrypted message:\nC1 = %s\nC2 = %s\n", C1.String(), C2.String())
	fmt.Printf("Encrypted message (hex): %x\n", encryptedMessage)

	// Serialize the ciphertext to ASN.1 format
	serialized, err := serializeToASN1(C1, C2, encryptedMessage)
	if err != nil {
		panic("Failed to serialize ciphertext: " + err.Error())
	}

	// Output the serialized binary as hexadecimal for visibility
	fmt.Printf("Serialized ciphertext (ASN.1, hex):\n%x\n", serialized)

	// Deserialize the ciphertext from ASN.1 format
	deserializedC1, deserializedC2, deserializedMessage, err := deserializeFromASN1(serialized)
	if err != nil {
		panic("Failed to deserialize ciphertext: " + err.Error())
	}

	// Decrypt the message
	decryptedMessage := decrypt(deserializedC1, deserializedC2, deserializedMessage, privateKey)
	fmt.Printf("Decrypted message: %s\n", decryptedMessage)
}

Key Agreement (ECDH)

Key Generation

 • Each party selects a secret key \( sk \in \mathbb{Z}_n \), a random integer from \( 1 \) to \( n-1 \).

 • The public key is computed as \( pk = sk \cdot G_2 \), where \( G_2 \) is the elliptic curve generator point.

Key Exchange (Bilinear Pairing)

 • Party 1 computes the pairing \( e(baseG1, pk_2) \), using Party 2's public key.

 • Party 2 computes the pairing \( e(baseG1, pk_1) \), using Party 1's public key.

Shared Secret Computation

 • Party 1 computes the shared secret \( K_1 = e(baseG1, pk_2)^{sk_1} \), using their private key and Party 2's public key.

 • Party 2 computes the shared secret \( K_2 = e(baseG1, pk_1)^{sk_2} \), using their private key and Party 1's public key.

 • Both parties should obtain the same secret \( K_1 = K_2 \), enabling secure communication.

Verification

 • Both parties verify that \( K_1 = K_2 \). If true, the key exchange is successful.

 • The verification is done by checking if \( e(baseG1, pk_2)^{sk_1} = e(baseG1, pk_1)^{sk_2} \).

Go Playground
Test This Example and the IBE Approach.

Hardcoded in Golang

package main

import (
	"bytes"
	"fmt"
	"math/big"
	"crypto/rand"

	"github.com/pedroalbanese/bn256"
)

// Key generation (public and private keys)
func generateKeys() (*big.Int, *bn256.G2) {
	// Generate the private key (random number between 1 and the order of the curve)
	privateKey, err := rand.Int(rand.Reader, bn256.Order)
	if err != nil {
		panic(err)
	}

	// The public key is the private key multiplied by the generator point G
	publicKey := new(bn256.G2).ScalarBaseMult(privateKey)

	return privateKey, publicKey
}

func main() {
	// Generate the private and public keys for two parties
	privKey1, pubKey1 := generateKeys() // Party 1 keys
	privKey2, pubKey2 := generateKeys() // Party 2 keys

	// The base point of G1
	baseG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(1048576)) // Arbitrary scalar for base point G1

	// Compute the pairing e(baseG1, pubKey1) and e(baseG1, pubKey2)
	pairing1 := bn256.Pair(baseG1, pubKey1) // e(baseG1, pubKey1)
	pairing2 := bn256.Pair(baseG1, pubKey2) // e(baseG1, pubKey2)

	// Compute shared keys by multiplying pairings with the corresponding private key
	sharedKey1 := new(bn256.GT)
	sharedKey1.ScalarMult(pairing1, privKey2) // Party 1 computes shared key using Party 2's private key

	sharedKey2 := new(bn256.GT)
	sharedKey2.ScalarMult(pairing2, privKey1) // Party 2 computes shared key using Party 1's private key

	// Output the shared keys
	fmt.Printf("Shared key (Party 1 computed): %x\n", sharedKey1.Marshal())
	fmt.Printf("Shared key (Party 2 computed): %x\n", sharedKey2.Marshal())

	// Verify if both shared keys are the same (they should be)
	if bytes.Equal(sharedKey1.Marshal(), sharedKey2.Marshal()) {
		fmt.Println("Shared keys match! Secure communication can be established.")
	} else {
		fmt.Println("Shared keys do not match. Something went wrong.")
	}
}

Digital Signature

Key Generation

 • Private Key: \( sk \in \mathbb{Z}_n \), where \( \mathbb{Z}_n \) is the finite field used for private keys and \( n \) is the order of the elliptic curve.

 • Public Key: \( pk = sk \cdot G_2 \), where \( G_2 \) is the base point of the elliptic curve.

Signing

 • Compute the hash of the message \( H(m) \), where \( m \) is the message to be signed.

 • The signature \( \sigma \) is computed as \( \sigma = sk \cdot H(m) \), where \( sk \) is the private key and \( H(m) \) is the hash of the message.

 • The final signature is \( \sigma \), which is the result of multiplying \( H(m) \) by the private key \( sk \), producing the signed message.

Verification

 • To verify the signature, the verifier checks if the pairing condition holds: \( e(\sigma, G_2) = e(H(m), pk) \), where \( e \) is the bilinear pairing.

 • If the pairing condition holds, the signature is valid; otherwise, it’s invalid.

Go Playground
Test This Example and the IBE Approach.

Hardcoded in Golang

package main

import (
	"bytes"
	"fmt"
	"math/big"
	"crypto/rand"

	"github.com/pedroalbanese/bn256"
)

// Function to generate public and private keys
func generateKeys() (*big.Int, *bn256.G2) {
	privKey, _, _ := bn256.RandomG2(rand.Reader) // Random private key
	pubKey := new(bn256.G2).ScalarBaseMult(privKey) // Public key derived from the private key
	return privKey, pubKey
}

// Function to hash a message with salt
func hashMessage(message []byte, salt []byte) *bn256.G1 {
	return bn256.HashG1(message, salt)
}

// Function to generate the signature
func generateSignature(privKey *big.Int, hash *bn256.G1) *bn256.G1 {
	// Signature generation: sigma = k * H(m)
	return hash.ScalarMult(hash, privKey)
}

// Function to verify the signature
func verifySignature(pubKey *bn256.G2, sigma *bn256.G1, message []byte, salt []byte) bool {
	// Hash the message
	h := hashMessage(message, salt)

	// Verify if the signature is valid using bilinear pairing
	rhs := bn256.Pair(h, pubKey)  // e(H(m), pk)
	lhs := bn256.Pair(sigma, new(bn256.G2).ScalarBaseMult(big.NewInt(1)))  // e(sigma, G2)

	// Compare the results of the pairings
	return bytes.Equal(rhs.Marshal(), lhs.Marshal())
}

// Function to display results
func displayResults(message string, privKey *big.Int, pubKey *bn256.G2, sigma *bn256.G1) {
	fmt.Printf("Message: %s\n", message)
	fmt.Printf("Private key: %x\n", privKey)
	fmt.Printf("\nPublic key: %s\n", pubKey)
	fmt.Printf("\nSignature (sigma): %x\n", sigma.Marshal())
}

func main() {
	// Hardcoded data
	salt := []byte("nonce")
	message := "Hello, this is a secret message!"

	msg := []byte(message)

	// Generate private and public keys
	privKey, pubKey := generateKeys()

	// Calculate the hash of the message
	hash := hashMessage(msg, salt)

	// Generate the signature
	sigma := generateSignature(privKey, hash)

	// Display the results
	displayResults(message, privKey, pubKey, sigma)

	// Verify the signature
	if verifySignature(pubKey, sigma, msg, salt) {
		fmt.Printf("\nSignature verified!")
	} else {
		fmt.Printf("\nSignature verification failed.")
	}
}

Reference

Barreto-Naehrig and Barreto-Lynn-Scott Curves ISO/IEC 15946-5:2022.

Check also:
- SM9 (ShangMi #9): Chinese IBE Standard Examples, GM/T 0044-2016.

---

IBE

In the IBE (Identity-Based Encryption) scheme, it is similar to the PKI (Public Key Infrastructure) system, but with some key differences. In IBE, a master key is generated, and the private keys are derived from the master key and an ID. There is only one public key, which is the master public key.

Key Generation

 • Master Key: \( sk_{master} \in \mathbb{Z}_n \), where \( \mathbb{Z}_n \) is the finite field used for private keys and \( n \) is the order of the elliptic curve.

 • Master Public Key: \( pk_{master} = sk_{master} \cdot G_2 \), where \( G_2 \) is the base point of the elliptic curve, and \( pk_{master} \) is the master public key.

 • User's Private Key: \( sk_{user} = sk_{master} \cdot h_{ID} \), where \( sk_{master} \) is the master private key, and \( h_{ID} \) is the hash of the user's ID.

 • User's Public Key: \( pk_{user} = pk_{master} \cdot h_{ID} \), computed automatically.

Examples (IBE)

Generate Master Key Pair:

./edgetk -pkey setup -algorithm bn256 -master "Master.pem" [-pass "passphrase"] -pub "MasterPublic.pem"

Generate User's Private Key:

./edgetk -pkey keygen -algorithm bn256 -master "Master.pem" [-pass "pass"] -prv "Private.pem" [-passout "pass"] -id "UID"

Parse Keys:

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

Encrypt with User Public Key:

./edgetk -pkey encrypt -algorithm bn256 -key "MasterPublic.pem" -id "UID" "plaintext.ext" > "ciphertext.enc"

Decrypt with User Private Key:

./edgetk -pkey decrypt -algorithm bn256 -key "Private.pem" [-pass "passphrase"] "ciphertext.enc"
echo $?

Key Agreement (ECDH):

./edgetk -pkey derive -algorithm bn256 -key "Private.pem" [-pass "pass"] -pub "MasterPublic.pem" -id "PeerUID"

Generate Signature:

./edgetk -pkey sign -algorithm bn256 -key "Private.pem" -salt "salt" FILE > sign.txt

Transmit the Signature:

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

Verify Signature:

./edgetk -pkey verify -algorithm bn256 -key "MasterPublic.pem" -id "UID" -salt "salt" -signature $sign FILE
echo $?

This example uses the standard US FIPS 180-2 Secure Hash Standard (SHS) SHA2 Algorithm for session key derivation and 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: 67354