ALBANESE Research Lab 🔍
Software Engineering & Systems Integration Solutions
EC-ElGamal 🇧🇷 🇪🇬
Elliptic Curve-based ElGamal Verifiable Encryption
ElGamal Encryption and Schnorr Proof
Buchanan, William J (2024).
The EC-ElGamal algorithm is a cryptographic scheme based on elliptic curves that enables the encryption of messages between two parties using a shared public key. Initially, each party generates its private key as a random number \(x\) and computes its corresponding public key \(Q = x \cdot G\), where \(G\) is a base point on the elliptic curve. To encrypt a message \(M\), the sender selects a random value \(r\) and computes \(C1 = r \cdot G\) and \(C2 = M \cdot H + r \cdot Q\) where \(H\) is another point on the elliptic curve. These values are then combined to form the additional authentication data (AAD), which is used along with the message for symmetric encryption. A nonce value is also generated to ensure randomness in the cipher. The receiver uses their private key \(x\) to derive \(t = x \cdot C1\) and from it, the symmetric key used to decrypt the message. The algorithm also includes a zero-knowledge proof (ZKP) mechanism based on Schnorr, allowing the receiver to verify the authenticity of the received message without revealing their private key.
With verifiable encryption, Bob can prove to Alice that he has used a given encryption key of a ciphertext with a NIZK (Non-interactive Zero Knowledge Proof). In this case we will use ElGamal encryption and generate a proof of the public key which has been used for the encryption. If Bob uses Trent's public key to encrypt some ciphertext for Alice, then Bob can produce a proof that it has been encrypted with Trent's public key. Alice will then be able to check this against Trent's public key. In this case, we will use the BLS12-381G1 elliptic curve, and use Anubis block cipher with OCB3 AEAD mode of operation to perform the actual encryption on the message.
Theory
We initially create a private key as a random number \(x\) and a public key of: \[ Q = x \cdot G \]
With standard ElGamal encryption, we generate a random value \(r\) to give: \[ t = r \cdot Q \]
We then create a symmetric key from this elliptic curve point: \[ \text{AEADKey} = \text{Derive}(t) \] and where \(\text{Derive}\) just converts a point on the curve to a byte array value that is the length of the required symmetric encryption key (such as for 32 bytes in the case of 256-bit Anubis).
Next, we compute the ciphertext values of:
\[ C1 = r \cdot G \]
\[ C2 = M \cdot H + r \cdot Q \]
and where \(M\) is the \(\text{msg}\) value converted into a scalar value. We then append these together to create the additional data that will be used for the symmetric key encryption of the message:
\[ \text{AAD} = C1 || C2 \]
We then generate a nonce value (\(\text{Nonce}\)) and then perform symmetric key encryption on the message: \[ \text{cipher} = \text{EncAEADKey}(\text{msg}, \text{Nonce}, \text{AAD}) \]
The ciphertext then has values of \(C1\), \(C2\), \(\text{Nonce}\), and \(\text{cipher}\). \(C1\), \(C2\) are points on the curve, and the \(\text{Nonce}\) value and \(\text{cipher}\) are byte array values. To decrypt, we take the private key (\(x\)) and derive: \[ t = x \cdot C1 \] \[ \text{AEADKey} = \text{Derive}(t) \] \[ \text{AAD} = C1 || C2 \] \[ \text{msg} = \text{DecAEADKey}(\text{cipher}, \text{Nonce}, \text{AAD}) \]
Here is an overview of the method:
To generate the proof, we generate a random value (\(r\)) and a blinding factor (\(b\)) to give two points on the elliptic curve: \[ R1 = r \cdot G \] \[ R2 = r \cdot Q + b \cdot H \]
Next, we create the challenge bytes with: \[ \text{chall} = C1 || C2 || R1 || R2 || \text{Nonce} \]
We take this value and hash it (\(H()\)), and create a scalar value with (\(ek\)) to produce: \[ c = H(\text{chall}) \cdot ek \]
We then create two Schnorr proof values: \[ S1 = b - c \cdot m \] \[ S2 = r - c \cdot b \]
To verify the proof, we reconstruct \(R1\): \[ R1 = c \cdot C1 + S2 \cdot G = c \cdot (b \cdot G) + (r - cb) \cdot G = (cb + r - cb) \cdot G = r \cdot G \]
We reconstruct \(R2\): \[ R2 = c \cdot C2 + S1 \cdot Q + S1 \cdot H \] This works because: \begin{align*} R2 & = c \cdot C2 + S1 \cdot Q + S1 \cdot H \\ & = c \cdot (b \cdot Q + m \cdot H) + (r - cb) \cdot Q + (b - cm) \cdot H \\ & = (cb + r - cb) \cdot Q + (cm + b - cm) \cdot H \\ & = r \cdot Q + b \cdot H \end{align*}
We then reconstruct the challenge with: \[ \text{chall} = C1 || C2 || R1 || R2 || \text{Nonce} \]
We take this value and hash it (\(H()\)), and create a scalar value with (\(ek\)) to produce: \[ c = H(\text{chall}) \cdot ek \]
This value is then checked against the challenge in the proof, and if they are the same, the proof is verified.
Golang Implementation
Golang
package main
import (
"fmt"
"os"
"github.com/pedroalbanese/ecka-eg/core/curves"
"github.com/pedroalbanese/ecka-eg/elgamal"
)
func main() {
argCount := len(os.Args[1:])
val := "hello"
if argCount > 0 {
val = os.Args[1]
}
domain := []byte("MyDomain")
bls12381g1 := curves.BLS12381G1()
ek, dk, _ := elgamal.NewKeys(bls12381g1)
msgBytes := []byte(val)
cs, proof, _ := ek.VerifiableEncrypt(msgBytes, &elgamal.EncryptParams{
Domain: domain,
MessageIsHashed: true,
GenProof: true,
ProofNonce: domain,
})
fmt.Printf("=== ElGamal Verifiable Encryption ===\n")
fmt.Printf("Input text: %s\n", val)
fmt.Printf("=== Generating keys ===\n")
res1, _ := ek.MarshalBinary()
fmt.Printf("Public key %x\n", res1)
res2, _ := dk.MarshalBinary()
fmt.Printf("Private key %x\n", res2)
fmt.Printf("=== Encrypting and Decrypting ===\n")
res3, _ := cs.MarshalBinary()
fmt.Printf("\nCiphertext: %x\n", res3)
dbytes, _, _ := dk.VerifiableDecryptWithDomain(domain, cs)
fmt.Printf("\nDecrypted: %s\n", dbytes)
fmt.Printf("\n=== Checking proof===\n")
rtn := ek.VerifyDomainEncryptProof(domain, cs, proof)
if rtn == nil {
fmt.Printf("Encryption has been verified\n")
} else {
fmt.Printf("Encryption has NOT been verified\n")
}
fmt.Printf("=== Now we will try with the wrong proof ===\n")
ek2, _, _ := elgamal.NewKeys(bls12381g1)
cs, proof2, _ := ek2.VerifiableEncrypt(msgBytes, &elgamal.EncryptParams{
Domain: domain,
MessageIsHashed: true,
GenProof: true,
ProofNonce: domain,
})
rtn = ek.VerifyDomainEncryptProof(domain, cs, proof2)
if rtn == nil {
fmt.Printf("Encryption has been verified\n")
} else {
fmt.Printf("Encryption has NOT been verified\n")
}
}
Reference
BSI TR-03111 ECKA-EG (Elliptic Curve Key Agreement based on ElGamal)Examples
EC-ElGamal asymmetric keypair generation (PEM format)
./edgetk -pkey keygen -algorithm ec-elgamal -curve BLS12381G1 [-prv Private.pem] [-pass "pass"] [-pub Public.pem]
Shared key negociation
./edgetk -pkey wrapkey -algorithm ec-elgamal -key Public.pem -id "Domain" > cipher.txt
ciphertext=$(cat cipher.txt|grep "Cipher"|awk '{print $2}')
./edgetk -pkey unwrapkey -algorithm ec-elgamal -key Private.pem -id "Domain" -cipher $ciphertext
ciphertext=$(cat cipher.txt|grep "Cipher"|awk '{print $2}')
./edgetk -pkey unwrapkey -algorithm ec-elgamal -key Private.pem -id "Domain" -cipher $ciphertext
Parse keys
./edgetk -pkey text -key Private.pem
./edgetk -pkey text -key Public.pem
./edgetk -pkey text -key Public.pem
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.
