ElGamal (with Elliptic Curve Cryptography)Alice first creates a private key (\(a\)) and a public key (\(aP\)), and where \(P\) is the base point on a curve. If Bob wants to send Alice an encrypted message (\(M\)), he creates a random value (\(k\)) and uses her public key (\(A\)) to produce a cipher messages of: \(K=kP\) and \(C=kA + M\), and where \(M\) is matched to a point on the elliptic curve. Now Alice receives (\(K\) and \(C\)), and computes the shared secret (\(S\)) using her private key (\(a\)): \(S=aK\) and then computes the message with: \(M = C - S\). |
Method
With ECC, we take points on a defined curve - such as Curve 25519 - and then perform point addition and subtraction. So how can we convert the ElGamal method into ECC? First, Alice first creates a private key (\(a\)) - and which is a random scalar value - and a public key (\(aP\)) - and which is a point on the elliptic curve. \(P\) is the base point on a curve. Alice's public key will then be:
\(A=aP\)
If Bob wants to send Alice an encrypted message (\(M\)), he creates a random value (\(k\)) and uses her public key (\(A\)) to produce a cipher messages of:
\(K=kP\)
and:
\(C=kA + M\)
and where \(M\) is matched to a point on the elliptic curve. Now Alice receives (\(K\) and \(C\)), and computes the shared secret (\(S\)) using her private key (\(a\)):
\(S=aK\)
and then computes the message with:
\(M = C - S\)
As \(C\) and \(S\) will be points on the elliptic curve, this will be done with a point subtraction operation. Overall this will recover the original message as:
\(C - S = kA + M - aK = kaP + M - akP = M\)
Outline
The following is the code [taken from here]:
package main import ( "fmt" "os" "go.dedis.ch/kyber" "go.dedis.ch/kyber/group/edwards25519" "go.dedis.ch/kyber/util/random" ) func ElEncrypt(group kyber.Group, pubkey kyber.Point, message []byte) ( K, C kyber.Point, remainder []byte) { // Embed the message (or as much of it as will fit) into a curve point. M := group.Point().Embed(message, random.New()) fmt.Printf("Message point:\t%s\n" , M.String()) max := group.Point().EmbedLen() if max > len(message) { max = len(message) } remainder = message[max:] // ElGamal-encrypt the point to produce ciphertext (K,C). k := group.Scalar().Pick(random.New()) // ephemeral private key K = group.Point().Mul(k, nil) // ephemeral DH public key S := group.Point().Mul(k, pubkey) // ephemeral DH shared secret C = S.Add(S, M) // message blinded with secret return } func ElDencrypt(group kyber.Group, prikey kyber.Scalar, K, C kyber.Point) ( message []byte, err error) { // ElGamal-decrypt the ciphertext (K,C) to reproduce the message. S := group.Point().Mul(prikey, K) // regenerate shared secret M := group.Point().Sub(C, S) // use to un-blind the message message, err = M.Data() // extract the embedded data return } func main() { M:="Testing" argCount := len(os.Args[1:]) if (argCount>0) {M= string(os.Args[1])} suite := edwards25519.NewBlakeSHA256Ed25519() // Alice's key pair (a,A) a := suite.Scalar().Pick(suite.RandomStream()) A := suite.Point().Mul(a, nil) fmt.Printf("Private key (Alice):\t%s\n" ,a.String()) fmt.Printf("Public key (Alice):\t%s\n" , A.String()) fmt.Printf("\n\n--- Now Bob will cipher the message for Alice\n") fmt.Printf("Bob's message:\t%s\n",M) m := []byte(M) K, C, _ := ElEncrypt(suite, A, m) fmt.Printf("\nBob cipher (K):\t%s\n" , K.String()) fmt.Printf("Bob cipher (C):\t%s\n" , C.String()) fmt.Printf("\n\n--- Now Alice will decipher the ciphertext (K,C) with her private key (a)\n") M_decrypted, err := ElDencrypt(suite, a, K, C) if err != nil { fmt.Println("Error: " + err.Error()) } fmt.Printf("\nOutput:\t%s",string(M_decrypted)) }
A sample run is:
Private key (Alice): 7182fa86214b1672f36113d139b2f84ca6acbbf1dbe2202e2ad99665e4fdac00 Public key (Alice): 31dfde321f1f56228feeacaeff9550c3d489ee5fd3e4e9d2e48fd41cfd9f09f6 --- Now Bob will cipher the message for Alice Bob's message: Testing 123 Message point: 0b54657374696e6720313233aca5a2888970256a3bb93cde2898f95fcdfd96ef Bob cipher (K): c794b9c278298dc3abd64b0e3af62a2f7390c6c51c13a491930dea6b2dbc6ce4 Bob cipher (C): 27ac77843effff5b723abe990e7175ba0c7659da0f5aec98421f0a89b78f2d82 --- Now Alice will decipher the ciphertext (K,C) with her private key (a) Output: Testing 123
Presentation