Building a More Trusted Data World: Authenticated ElGamal Encryption using Kryptology

Building a More Trusted Data World: Authenticated ElGamal Encryption using Kryptology

And Just Ready for Homomorphic Encryption

Let’s look at the beauty of combining public-key encryption, symmetric key encryption and authenticated ciphertexts.

As an active researcher, the first thing I do when an important new research-focused software library comes along is to break it down and understand its operation. This will prove the principles and also verify the methods. And, so Kryptology — created by Coinbase — has come along and it promises a whole new privacy-preserving world, with homomorphic encryption, Shamir Secret Shares, blinded commitments and ultra-fast code. One of the key elements in the library is the usage of authenticated encryption (AE) and homomorphic encryption. This is achieved through the ElGamal encryption method using elliptic curves. So let’s give it a try.

Initially, Alice will generate a private key (x) and a public key of:

Y=x.G

and where G is the base point on the curve. She can share this public key (Y) with Bob. When Bob wants to encrypt something for Alice, he generates a random value (r) and then computes:

C1=r.G

He will then will take the message (Msg) and hash it to a point:

M:=HashToPoint(Msg)

Next, he computes:

C2=r.Y+M

Bob then derives the AES key to be used from the random value for the message and Alice’s public key:

t=r.Y

and then produces the additional authentication data (AAD) using:

AAD=C1||C2

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=x.C1

and then recreating the AAD with:

AAD=C1||C2

and with the nonce, and cipher key, she can now decrypt with:

Cipher=AESt(AEAD,AAD)

Bob and Alice will create the same key, as Bob generates:

t=rY

and Alice generates:

t=xC1=xrG=rY

The method is thus:

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 scale, 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 [here]:

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)

////////////////////////////////////////////////////////////////////
//Alice will decrypt. Using aead, C1, C2, and her 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: %s\n", mymsg)
 fmt.Printf("\nAlice's private key: %x\n", x.Bytes())
 fmt.Printf("Alice's public key: %x\n", Y.ToAffineCompressed())
 fmt.Printf("\nC1: %x\n", C1.ToAffineCompressed())
 fmt.Printf("C2: %x\n", C2.ToAffineCompressed())
 fmt.Printf("Message to point: %x\n", M.ToAffineCompressed())
 fmt.Printf("AAD: %x\n", aad1)
 fmt.Printf("Encrypted: %x\n", aead)
 fmt.Printf("\nRecovered message: %s\n", msg)

}

A sample run [here]:

Orginal message: hello

Alice's private key: ff8a79990bf511e8ee823e013afaac65c117327afb3fed621d0da46d66e95209
Alice's public key: 1318ce8d838f0efb82d3cdb8d478a00cc9458084e559d6ea508be5c260fba425

C1 77531db290b10224ebf6d9b736200c755bd4e697057d50d575eda642fdc2fa7f
C2: 9077d993b6f06f624c51732cf226a3e10c5853d92eb26a89fd689fdbd7624ed7
AAD 12d00229d8a4d1bc22a9a08bf02ec68e1e2d55e7ce4abeea9895935219805e5c77531db290b10224ebf6d9b736200c755bd4e697057d50d575eda642fdc2fa7f51d90e109dc328b13f88b656a1a0bec4cb3dc6a0d118b08147247951ae66ee0a9077d993b6f06f624c51732cf226a3e10c5853d92eb26a89fd689fdbd7624e57
Encrypted: 9b4b250cc855ce94fd50b4f008b651e991d31e5ea0

Recovered message: hello

And here is the Replit code:

Conclusions

There’s old crypto, and there’s new crypto. Let’s go and build a more trusted, secure and robust data world …