With ElGamal encryption using elliptic curves, Alice generates a private key (\(x\)) and a public key of \(Y=xG\), and where \(G\) is the base point on the curve. She can share this public key with Bob. When Bob wants to encrypt something for Alice, he generates a random value (\(r\)) and then computes \(C_1 = r.G\) and then will take the message (\(Msg\)) and hash it to a point: \(M = Hash_{ToPoint}(Msg)\). Next he computes: \(C_2 = rY+M\). Bob then derives the AES key to be used from \(t=rY\) and then produces the additional authentication data (AAD) using: \(AAD=C_1 || C_2\). He will then create a random nonce of the encryption, and use AES encryption to produce the authenicated ciphertext: \((AEAD=AES_{t}(Msg, AAD)\). In this case, we will use the Kryptology library with the Ed25519 elliptic curve.
Authenticated ElGamal Encryption using Kryptology |
Background
Initially Alice will generate a private key (\(x\)) and a public key of:
\(Y=xG\)
and where \(G\) is the base point on the curve. She can share this public key with Bob. When Bob wants to encrypt something for Alice, he generates a random value (\(r\)) and then computes:
\(C_1 = r.G\)
He will then will take the message (\(Msg\)) and hash it to a point:
\(M := Hash_{ToPoint}(Msg)\)
Next, he computes:
\(C_2 = rY+M\)
Bob then derives the AES key to be used from the random value for the message and Alice's public key:
\(t=rY\)
and then produces the additional authentication data (\(AAD\)) using:
\(AAD=C_1 || C_2\)
and where "||" represents appending the bytes from the values. This will bind the encryption to the cipher, and will authenticate the cipher. He will then create a random nonce of the encryption, and use AES encryption to produce the authenticated ciphertext:
\(AEAD=AES_{t}(Msg, AAD)\)
Now Alice received the ciphertext (\(AEAD\)), and will decrypt by re-generating the encryption key with:
\(t=xC_1\)
and then recreating the AAD with:
\(AAD= C_1 || C_2\)
and with the nonce, and cipher key, she can now decrypt with:
\(Cipher=AES_{t}(AEAD, AAD)\)
Bob and Alice will create the same key, as Bob generates:
\(t=rY\)
and Alice generates:
\(t=xC1 = xrG = rY\)
Coding
We can use the Kryptology library developed by Coinbase and the Ed25519 curve to implement the method. Note that because we are using Ed25519 the private key and the public key will be of the same length, even though the private key is a scalar value, and the public key is a point on the curve. In Ed25519, we only need one of the co-ordinate points for the value on the curve.
package main import ( "crypto/aes" "crypto/cipher" crand "crypto/rand" "fmt" "math/big" "os" "github.com/coinbase/kryptology/pkg/core" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { mymsg := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { mymsg = os.Args[1] } curve := curves.ED25519() // priv =x, pub=xG x := curve.Scalar.Random(crand.Reader) Y := curve.Point.Generator().Mul(x) r := curve.Scalar.Random(crand.Reader) C1 := curve.Point.Generator().Mul(r) M := curve.Point.Hash([]byte(mymsg)) C2 := Y.Mul(r).Add(M) // Bob will derive key for AEAD t := Y.Mul(r) aeadKey, _ := core.FiatShamir(new(big.Int).SetBytes(t.ToAffineCompressed())) block, _ := aes.NewCipher([]byte(aeadKey)) aesGcm, _ := cipher.NewGCM(block) // add = C1 || C2 aad := C1.ToAffineUncompressed() aad = append(aad, C2.ToAffineUncompressed()...) var nonce [12]byte _, _ = crand.Read(nonce[:]) aead := aesGcm.Seal(nil, nonce[:], []byte(mymsg), aad) //////////////////////////////////////////////////////////////////////////// // Now Alice will decrypt. Using aead, C1, C2, nonce, and private key (x) // //////////////////////////////////////////////////////////////////////////// t = C1.Mul(x) aeadKey, _ = core.FiatShamir(new(big.Int).SetBytes(t.ToAffineCompressed())) block, _ = aes.NewCipher([]byte(aeadKey)) aesGcm, _ = cipher.NewGCM(block) aad1 := C1.ToAffineUncompressed() aad1 = append(aad1, C2.ToAffineUncompressed()...) msg, _ := aesGcm.Open(nil, nonce[:], aead, aad1) fmt.Printf("Orginal message:\t%s\n", mymsg) fmt.Printf("\nAlice's private key:\t%x\n", x.Bytes()) fmt.Printf("Alice's public key:\t%x\n", Y.ToAffineCompressed()) fmt.Printf("\nC1:\t%x\n", C1.ToAffineCompressed()) fmt.Printf("C2:\t%x\n", C2.ToAffineCompressed()) fmt.Printf("Message to point:\t%x\n", M.ToAffineCompressed()) fmt.Printf("AAD:\t%x\n", aad1) fmt.Printf("Nonce:\t\t%x\n", nonce) fmt.Printf("Encrypted:\t%x\n", aead) fmt.Printf("\n === Alice receives AEAD, Nonce, C1 and C2 and recovers message ===") fmt.Printf("\nRecovered message:\t%s\n", msg) }
An overview of the method is:
A sample run:
Orginal message: How much wood would a woodchuck chuck if a woodchuck could chuck wood? Alice's private key: 952fd8c95524d496390e334669921794581232232c0fd5bb29c00ad309051307 Alice's public key: 099dce0b871da00dbd601204c1c935735bcc5ee5fdc02f54423cc0b1bef5b8ad C1: bbf9cbff8b53a04a80cb10492ab17925ad23f1e696f091e920d83459d9dc2ebe C2: 61fa86747c8e0aca9f50f179ccaaf61c5b4a49138d71a689ccb3517aaf4764cc Message to point: 0314d2825da6a168507916e60425cf0c1cccd2bb4456c792d6aa86c25d60e4fb AAD: 99d7868cdd8a881b2a12452240f0b9e18cfef586184487b6159609debbb5e11ebbf9cbff8b53a04a80cb10492ab17925ad23f1e696f091e920d83459d9dc2e3ee7a026251d27213b08487095b599801e871f038c75047c1f773c7c04a21c901161fa86747c8e0aca9f50f179ccaaf61c5b4a49138d71a689ccb3517aaf47644c Encrypted: 54937d71bd2ab7b5bf4858cdda0564759a071b07243f0a64604607dee52863f389dcc4571d654a70e0abea1598058f8f8c3022c3e01fc59199a320eb98108747471ea3108508546b8fb50b4cdb2fbf08043c376a931d Recovered message: How much wood would a woodchuck chuck if a woodchuck could chuck wood?