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\).
ElGamal ECC Encryption (using message string) |
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 ( crand "crypto/rand" "fmt" "math" "math/big" "math/rand" "os" "time" "github.com/coinbase/kryptology/pkg/core/curves" ) func powInt(x, y int) int { return int(math.Pow(float64(x), float64(y))) } func encrypt(c *curves.Curve, msg [] byte,G curves.Point, Y curves.Point) (C1 curves.Point, C2 *big.Int) { x :=new(big.Int).SetBytes(msg) r := c.Scalar.Random(crand.Reader) rY := Y.Mul(r) rG := G.Mul(r) rYval := new(big.Int).SetBytes(rY.ToAffineUncompressed()) C2 = new(big.Int).Add(rYval, x) C1 = rG return } func decrypt(x curves.Scalar, C1 curves.Point, C2 *big.Int) (p []byte) { xC := C1.Mul(x) xCval := new(big.Int).SetBytes(xC.ToAffineUncompressed()) p = new(big.Int).Sub(C2, xCval).Bytes() return } func main() { argCount := len(os.Args[1:]) msg := "Hello" if argCount > 0 { msg = os.Args[1] } rand.Seed(time.Now().UnixNano()) curve := curves.K256() G := curve.Point.Generator() x := curve.Scalar.Random(crand.Reader) Y := G.Mul(x) C1, C2 := encrypt(curve, [] byte(msg), G, Y) x_decrypted := decrypt(x, C1, C2) fmt.Printf("Message: %s\n", msg) fmt.Printf("\nx=%x\nY=%x\n", x.Bytes(),Y.ToAffineUncompressed()) fmt.Printf("\nC1=%x\nC2=%s\n", C1.ToAffineUncompressed(), C2) fmt.Printf("\nDecrypted: %s\n", string(x_decrypted)) }
A sample run:
Message: Hello x=85690c51b228b614b515604f0d999cd1a28df605bac97d34633a0e7b86ee3c85 Y=04a03a7988620d1dafdb2baae48d5638ede01f7c00d7ca8430baf0ef17353920f341e55647c3fcde1fc6bf479724fd42276ddca4aa9ecf3c924d2048d2ed721157 C1=040775436fb3ec20816a85c50253b7bf3b82ac5bcc1e372b4f7bd7d812b9a675f0ac8d739fe5122dfba4cb798f9273e2e1483b22cd6347d36cb9b96df720f8a2fd C2=57874734037032100445317653665255429180084300986380534544295609387996620841581470710462217777364540827711653593330226141760413561202423334955662883749773613 Decrypted: Hello