With ElGamal encryption using elliptic curves, Alice generates 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 \(C_1 = r.G\) and then will take the message (\(M\)) and computes: \(C_2 = r.Y+M\). To decrypt, Alice takes her private key (\(y\)) and computes: \(M=C_2-y.C_1\). In this case we will use ElGamal ECC Encryption with a Ristretto group. Overall, Ristretto255 encodes group elements using 255 bits and provides a prime-order group of size \(2^{252}\), and implemented with Curve25519. We use a prime of \(2^{255}-19\). In this case, we will hash a string with SHA-512, and then map this to a point on the curve. This will be computed for Ristretto255 and an Edwards curve, and use the CIRCL library.
ElGamal ECC Encryption with Ristretto group using CIRCL |
Background (Discrete logs)
With ElGamal encryption using elliptic curves, Alice generates a private key (\(x\)) and a public key of:
\(Y=g^x \pmod p\)
and where \(g\) is the generator. She can share this public key (\(Y, g, p\)) with Bob. When Bob wants to encrypt something for Alice, he generates a random value (\(r\)) and the message value (\(M\)) and then computes:
\(a = g^r \pmod p\)
\(b = Y^r.M\)
To decrypt, Alice takes her private key (\(x\)) and computes:
\(M=\frac{b}{a^x}\)
This works because:
\(M=\frac{b}{a^x} = \frac{Y^r.M}{ {(g^r)}^x } = \frac{ g^{(r.x)}.M } { g^{(r.x)} } = M \pmod p \)
The following shows how Bob can encrypt data for Alice:
Background (ECC)
With ElGamal encryption using elliptic curves, Alice generates 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 the message value (\(M\)) and then computes:
\(C_1 = r.G\)
\(C_2 = r.Y+M\)
To decrypt, Alice takes her private key (\(x\)) and computes:
\(M=C_2-x.C_1\)
This works because:
\(M=C_2-y.C_1 = r.x.G+M - x.r.G=M\)
The following shows how Bob can encrypt data for Alice:
Coding
We can use the Kryptology library developed by Coinbase and use the secp256k1 curve:
package main import ( "fmt" "github.com/cloudflare/circl/group" "crypto/rand" ) func main() { g := group.Ristretto255 base := g.NewElement() pk := g.NewElement() sk := g.RandomScalar(rand.Reader) pk.MulGen(sk) // Encrypt point p with ElGamal to produce a ciphertext-pair (a,b) p := g.RandomElement(rand.Reader) r := g.RandomScalar(rand.Reader) b := g.NewElement() a := g.NewElement() b.MulGen(r) a.Mul(pk, r) a.Add(a, p) // Decrypt (a,b) back to p p2 := g.NewElement() b.Mul(b, sk) p2.Add(a, b.Neg(b)) fmt.Printf("Base point: %v\n",base) fmt.Printf("\nSecret key: %v\n",sk) fmt.Printf("Public key: %v\n",pk) fmt.Printf("\nRandom value:\t%v\n",p) fmt.Printf("\na: %v\n",a) fmt.Printf("b: %v\n",b) fmt.Printf("\nDecrypted:\t%v",p2) }
A sample run is:
Base point: 0000000000000000000000000000000000000000000000000000000000000000 Secret key: 0x039ed9b0f6236ce23a408bd7248f81c4f5adf3a92aa9e9d78e923759e6a47778 Public key: d0e1698cc2e6f5a7cb774262acf9f036b5672eadef4f9282ceea5467445fc213 a: 88721981f33fd59e4a95c17d2495ffff0ed4bae5c5dddfdad3a822437f1ece4f b: 546fcac99443464607aede2aa746a2d705eb41586387a0c0830df74abb383124 Random value: f43be9076d030dd5aeca508e728d3aaa8d81700980f8f18b670a471e24ef8e1e Decrypted: f43be9076d030dd5aeca508e728d3aaa8d81700980f8f18b670a471e24ef8e1ec