Cryptography Fundamentals: ElGamal Encryption and Signature

Cryptography Fundamentals: ElGamal Encryption and Signature

In research, we build on the shoulders of giants, and Taher Elgamal is one of the giants of cybersecurity. His work on Netscape led to the creation of SSL, and for which much of our Web security is still built on. Along with this, he published this paper in 1985 [here]:

It was true classic, and has been reference over 12,500 times. Within the paper, Tahir outlined an encryption methods and a digital signature method. His ‘base’ was to take John Napier’s logarithm, and make them discrete. This discrete element meant that we only dealt with positive integer values, and where we worked within a finite field. This field was defined by a prime number (p).

While the core ElGamal encryption method was overtaken in its usage by RSA, and then by ECC (Elliptic Curve Cryptography), the signature method was adopted as the Digital Signature Standard (DSS) by NIST. This has since scaled into ECC to become ECDSA, and which is used by Bitcoin and Ethereum.

Tahir studied electrical engineering in the late 1970s at Stanford University. It was there he met Marty Hellman and who helped him spark an interesting in cryptography. He received his PhD in 1984 and it was Marty introduced him to Paul Kocker at Netscape Communications. Together, Paul and Tahir worked on a method to implement end-to-end encryption, and published SSL 3.0 in November 1996:

Examples are at:

https://asecuritysite.com/elgamal

The ElGamal Method

Befre we start we need to look at some of the basics of logarithms and where:

{g^a}^b is g^{ab}

and:

g^a . g^b = g^{a+b}

To make these discrete to add (mod p) in our operations and where p is a prime number. This constrains our integrates with a finite field, between 0 and p-1.

In the ElGamal method, 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:

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 (a and b), and then uses his private key (x) to decrypt the values and discover the message:

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

With the divide by (a^x) we basically take the inverse of (a^x) mod p, and then multiply. The operation works because:

ElGamal and Signatures

With ElGamal signing, Alice has a public key (y,g,p) and a private key of a. She then takes a message m and creates a signature (r,s). This signature can then be checked by Bob.

With ElGamal, Alice selects a generator (g), prime number of p and a private key of a. Her public key is then (y,g,p) and where y is:

y=g^a (modp)

To sign a message (m) we generate a secret random number (k) and we must make sure:

gcd(k,p−1)=1

Next we compute:

r=g^k (mod p)

Next we compute:

k^{−1} (mod p−1)

and then:

s=k^{−1}(h(m)−ar) (modp−1)

The signature is then (r,s). Bob verifies the signature by computing two values:

v1=y^r.r^s (mod p)

and:

v2=g^{h(m)} (mod p)

If v1 is equal to v2

the signature has been verified. The proof is given here:

https://asecuritysite.com/elgamal/el_sig2

While, ElGamal signing is not used these days, its method were applied into the Digital Signature Algorithm (DSA), and which was since been coverted into the Elliptic Curve Digital Signature Algorithm (ECDSA) method.

Converting from discrete logs to elliptic curves

In discrete logs we convert from:

Y=g^a (mod p)

to

Y=a.G

and where we have a exponential for discrete logs we have:

Y = {g^a}^ b

is equivalent to:

Y=a.b.G

and for a multiplication we have

Y=g^a.g^b (mod p) = g^{a+b} (mod p)

In elliptic curves we convert the multiplication to a point addition:

Y = a.G + b.G = (a+b) G

This exponential becomes point multiplication, and multiply/division becomes point addition/subtraction.

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 mainimport (
    "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:  0b54657374696e6720313233aca5a2888970256a3bb93cde2898f95fcdfd96efBob 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:

https://asecuritysite.com/elgamal/go_elgamal_ecc

Partical Homomorphic Encryption with ElGamal

With ElGamal public key encryption we have a public key of (Y,g,p) and a private key of (x). The cipher has two elements (a and b). With this, Bob selects a private key of x and the calculates Y= g^x (modp) for his public key. We can use it for partial homomorphic encryption, and where we can multiply the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result.

https://asecuritysite.com/homomorphic/go_el_homo

https://asecuritysite.com/elgamal/elgamal_ps2

g^a . g^b = g^{a+b}

Other applications

There are many other applications of the ElGamal method, including Authenticated Encryption and in Zero Knowledge Proofs. The days of using discrete logarithms are past, and most of the implementations use elliptic curve methods now. And, so, unlike many others, Tahir did not patent his method, and this allowed others to use it freely.