ElGamal and Elliptic Curve Cryptography (ECC)

ElGamal and Elliptic Curve Cryptography (ECC)

Discrete Logs and ECC in a Modern Worlds

Almost every working day, I have the privilege to work in a place that once hosted one the greats: John Napier. It was John who discovered logarithms, and showed the world that g^a times g^b is g^(a+b), and that g^a divided by g^b is g^(a-b). In our modern world, we use this type of method so often in our cryptography implementation, and it often provides the core around privacy-enhancing methods (such as with Zero-Knowledge Proof and Anonymisation). As our numbers become very large, though, we often define them within a finite field (Z_p), and where we select a large prime number (p), and then perform all our operations with the magic of the (mod p) operation.

I think if John Napier were alive today he would wonder at how discrete logarithms have been used to secure our world. I am also sure he would strike-up an immediate bond with Taher Elgamal and who, in 1985, published this classic paper [here]:

Within the paper he proposed the ElGamal discrete logarithm encryption system and also the ElGamal signature scheme (and which which became the core of the DSA signature method). In 2009, Elgamal was award the RSA Conference 2009 Lifetime Achievement Award and where he was dubbed the “father of SSL”.

At its core of the ElGamal public key methods is the Discrete Logarithm Problem, and where we have:

Y= g^x (mod p)

and where it is difficult to determine x, even if we have Y, g and p (as long as p is a large enough prime number). And so it is used in the Diffie-Hellman method for key exchange. We also use it to sign a message, and where we create a key pair (a public key and a private key). The private key is used to encrypt something (such as the hash of the message), and then the public key is used to prove the signing.

With ElGamal, initially, Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y which is [here]:

Y=g^x (mod p)

His public key is (Y,g,p)

and he will send this to Alice. Alice then creates a message (M) and selects a random value k). She then computes a and b:

a=g^k(mod p)

b=y^k M(mod p)

Bob then receives these and decrypts with:

M=b/(a^x) (mod p)

You can try this here.

ElGamal and ECC

But, Elliptic Curve Cryptography (ECC) methods are just everywhere just now. 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 message of:

K=kP

and then the next with:

C=kA+M

and where M is matched to a point on the elliptic curve. Now Alice receives (K) and (C), and computes:

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

The following is come Go code to implement this [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

And there you go, ElGamal using ECC:

.