ElGamal ECC Encryption (using message string)[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 a range of elliptic curves, including secp256k1, secp256r1 (P256), ED25519, PALLAS, BLS12377G1 and BLS12377G2.
|
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() { name:="K256" argCount := len(os.Args[1:]) msg := "Hello" if argCount > 0 { msg = os.Args[1] } if argCount > 1 { name = os.Args[2] } curve := curves.K256() if name == "K256" { curve = curves.K256() } else if name == "P256" { curve = curves.P256() } else if name == "ED25519" { curve = curves.ED25519() } else if name == "PALLAS" { curve = curves.PALLAS() } else if name == "BLS12377G1" { curve = curves.BLS12377G1() } else if name == "BLS12377G2" { curve = curves.BLS12377G2() } rand.Seed(time.Now().UnixNano()) 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("Curve: %s\n", curve.Name) fmt.Printf("\n\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 for sepc256k1:
Message: Hello Curve: secp256k1 x=23a6eef96449d820b0e88a3a116a060344ecaf2321a773509bc728120642cb49 Y=042d4d41602d28972b6e22296f975f84f39aeb107fd7df5befa7d1a0768b3f1997a6ed131235431127254fd66509e3270911e21fe4a3b16f8b3c09c58daa6364f3 C1=046827633cec825cb77e50aebbe705e2f8f27c63cd9a92b86b69ab2fcaacfcb28b3af07f6fc947d1c43c7eccb4d3647e747bdd881cef875ba969b7fd5b2aa7c9ec C2=59336021793747421920085183247922000428685985721452982637808121588616665534479043152873970176233760374823408136940763997479007399026242141945334167943348637 Decrypted: Hello
A sample run for Ed25519:
Message: Hello Curve: ed25519 x=32e75403b81543650171c0c59b8ee1c8d3e71be55764f0be9b90c58c9b06d103 Y=1023c4873350d8ed9545f18dfe243af6659c84322f104a1652366da3e415f937d6b280b2700fc9a2a14ba065a90e4cabaa18981746f3f772a3c2f09619b87207 C1=136a5362c4dc6d48ad59addc0b69f295ffb375a260b86b2a26283d17468697508e69d412c97b66e00d8b4a482e929d39bf398ee301b2f2e19f0e37938f8ce578 C2=8209444547317232328880006462670587738619950742754519661730419176691772621631507506337619788270964840169637769557714859213532446399512137530558377435959250 Decrypted: Hello