With ElGamal encryption using elliptic curves, Alice generates a private key (\(y\)) and a public key of \(Y=y.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 Encryption and ECC using secp256k1 and Kryptology |
Background
With ElGamal encryption using elliptic curves, Alice generates a private key (\(y\)) and a public key of:
\(Y=y.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 (\(y\)) and computes:
\(M=C_2-y.C_1\)
This works because:
\(M=C_2-y.C_1 = r.y.G+M - y.r.G=M\)
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" "strconv" "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, x int, G curves.Point, Y curves.Point) (C1 curves.Point, C2 *big.Int) { 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, big.NewInt(int64(x))) C1 = rG return } func decrypt(y curves.Scalar, C1 curves.Point, C2 *big.Int) (p *big.Int) { yC := C1.Mul(y) yCval := new(big.Int).SetBytes(yC.ToAffineUncompressed()) p = new(big.Int).Sub(C2, yCval) return } func main() { argCount := len(os.Args[1:]) x := 5 if argCount > 0 { x, _ = strconv.Atoi(os.Args[1]) } rand.Seed(time.Now().UnixNano()) curve := curves.K256() G := curve.Point.Generator() y := curve.Scalar.Random(crand.Reader) Y := G.Mul(y) C1, C2 := encrypt(curve, x, G, Y) x_decrypted := decrypt(y, C1, C2) fmt.Printf("Value: %d\n", x) fmt.Printf("\nC1=%x: C2=%s\n", C1.ToAffineUncompressed(), C2) fmt.Printf("\nDecrypted: %s\n", x_decrypted) }
A sample run:
Value: 5 C1=0485698418747618625437e9b45a8557b68c67164af38102d167da2c779431dfa628d0b7381ac567b2d77d3ddbb7dff511160a2178c5b8802ddafeb8bab9284f3d: C2=58329869436517041815271907636572077418169934604996388602168546772101792052597093358006763508235206306012630257502220898098749352342107817299378833517565348 Decrypted: 5