John Napier’s Legacy Lives on in the 21st Century within ElGamal Encryption

John Napier’s Legacy Lives on in the 21st Century within ElGamal Encryption

I am lucky to work in the tower where John Napier discovered logarithms:

Now discrete logarithms are used as a base to perform key exchanges over the Internet. They are also being used within encryption — using the ElGamal method.

Public key encryption is typically used to sign for things (and where we use the private key to encrypt something and prove this with the public key) and within key exchange methods. The core methods used are RSA and Elliptic Curve. But an alternative is to use discrete logarithms. One of the most interesting is ElGamal, and was created by Taher Elgamal in 1985.

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:

His public key is then (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:

Bob then receives these and decrypts with:

This works because:

Some sample code is [here]:

package main

import (
    "crypto/rand"
    "math/big"
    "io"
    "fmt"
    "os"

)

func get_g_p(size string)(g, p *big.Int) {

    if (size=="512") {
        p,_ = new(big.Int).SetString("FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17",16)

        g,_ = new(big.Int).SetString("678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4",16)
    
    }
    if (size=="768") {
        p,_ = new(big.Int).SetString("E9E642599D355F37C97FFD3567120B8E25C9CD43E927B3A9670FBEC5D890141922D2C3B3AD2480093799869D1E846AAB49FAB0AD26D2CE6A22219D470BCE7D777D4A21FBE9C270B57F607002F3CEF8393694CF45EE3688C11A8C56AB127A3DAF",16)

        g,_ = new(big.Int).SetString("30470AD5A005FB14CE2D9DCD87E38BC7D1B1C5FACBAECBE95F190AA7A31D23C4DBBCBE06174544401A5B2C020965D8C2BD2171D3668445771F74BA084D2029D83C1C158547F3A9F1A2715BE23D51AE4D3E5A1F6A7064F316933A346D3F529252",16)
    
    }
    if (size=="1024") {
        p,_ = new(big.Int).SetString("FD7F53811D75122952DF4A9C2EECE4E7F611B7523CEF4400C31E3F80B6512669455D402251FB593D8D58FABFC5F5BA30F6CB9B556CD7813B801D346FF26660B76B9950A5A49F9FE8047B1022C24FBBA9D7FEB7C61BF83B57E7C6A8A6150F04FB83F6D3C51EC3023554135A169132F675F3AE2B61D72AEFF22203199DD14801C7",16)

        g,_ = new(big.Int).SetString("F7E1A085D69B3DDECBBCAB5C36B857B97994AFBBFA3AEA82F9574C0B3D0782675159578EBAD4594FE67107108180B449167123E84C281613B7CF09328CC8A6E13C167A8B547C8D28E0A3AE1E2BB3A675916EA37F0BFA213562F1FB627A01243BCCA4F1BEA8519089A883DFE15AE59F06928B665E807B552564014C3BFECF492A",16)
    
    }
    return 
}

func fromHex(hex string) *big.Int {
    n, ok := new(big.Int).SetString(hex, 16)
    if !ok {
        panic("failed to parse hex number")
    }
    return n
}
type PublicKey struct {
    G, P, Y *big.Int
}

type PrivateKey struct {
    PublicKey
    X *big.Int
}

func Encrypt(random io.Reader, pub *PublicKey, msg []byte) (a, b *big.Int, err error) {


    k, _ := rand.Int(random, pub.P)


    m :=new(big.Int).SetBytes(msg)

    a = new(big.Int).Exp(pub.G, k, pub.P)
    s := new(big.Int).Exp(pub.Y, k, pub.P)
    b = s.Mul(s, m)
    b.Mod(b, pub.P)

    return
}

func Decrypt(priv *PrivateKey, a, b *big.Int) (msg []byte, err error) {
    s := new(big.Int).Exp(a, priv.X, priv.P)
    s.ModInverse(s, priv.P)
    s.Mul(s, b)
    s.Mod(s, priv.P)
    em := s.Bytes()

    
    return em, nil
}


func main() {

s:="hello world"
x:="40"
plen:="512"

    s = string(os.Args[1])
    x = string(os.Args[2])
    plen =string(os.Args[3])

    fmt.Printf("Input message: %s\n",s)
    fmt.Printf("Prime number size: %s\n\n",plen)

    xval,_ := new(big.Int).SetString(x, 10)

    g,p:=get_g_p(plen)

    priv := &PrivateKey{
        PublicKey: PublicKey{
            G: g,
            P: p,
        },
        X: xval,
    }
    priv.Y = new(big.Int).Exp(priv.G, priv.X, priv.P)

    message := []byte(s)
    a, b, _ := Encrypt(rand.Reader, &priv.PublicKey, message)

    message2, _ := Decrypt(priv, a, b)

    fmt.Printf("====Private key (x):\nX=%d",priv.X)
    fmt.Printf("\n\n====Public key (Y,G,P):\nY=%d\n\nG=%d\n\nP=%d",priv.Y,priv.PublicKey.G,priv.PublicKey.P)


    fmt.Printf("\n\n====Cipher (a=%s)\n\n(b=%s): ",a,b)
    fmt.Printf("\n\n====Decrypted: %s",string(message2))


}

In this case I have used Diffie Hellman group parameters for g, and p. A sample run is:

Input message: hello
Prime number size: 512

====Private key (x):
X=42

====Public key (Y,G,P):
Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678

G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796

P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223

====Cipher (a=10503137704154464640139409096180378450280945842974790197762651686774136663204267255536427109860643340473705516672240368851788858115494182159810217684111037)

(b=4054818746976519740094945741473934294426146873627558873251145631446282787632223746599936736928462111195626161828687198260149999269066225763403094068906537): 

====Decrypted: hello

A demo is here: