ElGamal ECC Encryption with Ristretto group[ElGamal Home][Home]
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.
|
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" "bytes" "github.com/bwesterb/go-ristretto" b64 "encoding/base64" ) func main() { var privKey ristretto.Scalar var pubKey ristretto.Point var p ristretto.Point var r ristretto.Scalar var a ristretto.Point var b ristretto.Point var elgamalCalc, p2 ristretto.Point privKey.Rand() pubKey.ScalarMultBase(&privKey) // Encrypt point p with ElGamal to produce a ciphertext-pair (a,b) p.Rand() r.Rand() b.ScalarMultBase(&r) a.PublicScalarMult(&pubKey, &r) a.Add(&a, &p) // Decrypt (a,b) back to p elgamalCalc.ScalarMult(&b, &privKey) p2.Sub(&a, &elgamalCalc) fmt.Printf("Secret key:\t%v\n", privKey) fmt.Printf("Public Key:\t%v\n", pubKey) fmt.Printf("Random value:\t\t%s\n", b64.StdEncoding.EncodeToString(p.Bytes())) fmt.Printf("Recovered value:\t%s\n", b64.StdEncoding.EncodeToString(p2.Bytes())) fmt.Printf("Valid: %v", bytes.Equal(p.Bytes(), p2.Bytes())) }
A sample run is:
Secret key: XuTgs_Cj2yuUu63tQSbKmF_HTi6upL7GDOAByaqZPAE Public Key: lOaX4YCYZA7J1PiSYQQqLZe7wSc1VjpgzvqUSGiciTE Random value: 7uzowI/mNSQ8Tz6mqjTxkoMA9vIj6pr5J/T9XYzPnVA= Recovered value: 7uzowI/mNSQ8Tz6mqjTxkoMA9vIj6pr5J/T9XYzPnVA= Valid: true