The ElGamal algorithm is a public-key cryptography algorithm based on modular exponentiation, is known for its security based on the difficulty of solving the discrete logarithm problem and provides confidentiality and authentication properties. It was described by Taher A. Elgamal in 1985.
The parameter generation function involves the creation of key parameters for the ElGamal cryptosystem, which includes a large prime number P and a generator G. The function takes a desired bit size for the prime number (e.g., 3072 bits) as input. First, it generates a large prime number P of the specified bit size with Miller-Rabin primality test. Then, it selects a generator G in the range [2, P-2]. The resulting parameters, denoted as (P, G), serve as the foundation for the ElGamal public and private key pairs. These parameters are crucial for ensuring the security and effectiveness of the ElGamal encryption and signature schemes. Each entity possesses a private key (x), kept secret, and a public key (Y), derived from g^x mod p. Remembering that parameters (P, G) can be used to generate more than one key pair and are public.
1. Generate a large prime number \( p \).
2. Select a generator \( g \) in the range [2, \( p-2 \)].
3. Generate a private key \( x \) randomly.
4. Compute the public key \( Y = g^x \mod p \).
The ElGamal Signature Scheme is a digital signature algorithm based on the ElGamal cryptography system. It facilitates secure digital signing of messages, providing authenticity and integrity to the signed content. When signing a message (m), the entity selects a random value (k), computes two signature components, and produces the signature (r, s).
1. Select a random value \( k \) such that \( 1 < k < p-1 \) and \( \text{gcd}(k, p-1) = 1 \).
2. Compute the first signature component: \( r = g^k \mod p \).
3. Compute the second signature component: \( s \equiv (H(m) - x \cdot r) \cdot k^{-1} \mod (p-1) \).
The verification process involves checking whether the computed values from the received signature match those derived from the sender's public key and the message.
1. Receive the message \( m \) and the signature components \( (r, s) \).
2. Compute \( w \equiv s^{-1} \mod (p-1) \).
3. Compute \( u_1 \equiv H(m) \cdot w \mod (p-1) \).
4. Compute \( u_2 \equiv r \cdot w \mod (p-1) \).
5. Compute \( v \equiv g^{u_1} \cdot Y^{u_2} \mod p \).
6. The signature is valid if \( v \equiv r \mod p \).
The ElGamal Encryption is a public-key cryptography system that enables secure communication between two parties. To encrypt a symmetric key, the sender uses the session key, computes two components (a and b), and sends (g^k mod p, Y^k * key mod p) to the recipient. The recipient, using their private key, decrypts the symmetric key.
1. Bob generates his key pair \( (x_B, Y_B) \).
2. Bob shares his public key \( Y_B \) with Alice.
3. Alice generates a random symmetric key \( K_{\text{sym}} \).
4. Alice encrypts \( K_{\text{sym}} \) using Bob's public key: \( a = g^{k_A} \mod p \) and \( b = Y_B^{k_A} \cdot K_{\text{sym}} \mod p \).
5. Alice sends the ciphertext \((a, b)\) to Bob.
6. Bob decrypts the received ciphertext using his private key to obtain: \( K_{\text{sym}} = (b \cdot a^{-x_B}) \mod p \).
7. Now, both Alice and Bob have the shared symmetric key \( K_{\text{sym}} \) for further communication.
1. \( H(m) \) represents the hash value of the message.
2. \( k^{-1} \) denotes the modular multiplicative inverse of \( k \) modulo \( (p-1) \).
3. \( \text{gcd}(a, b) \) denotes the Greatest Common Divisor of \( a \) and \( b \).
4. \( k_A \) is a random secret key known only to Alice for this session.
5. \( \equiv \) indicates congruence.
This Go implementation of ElGamal demonstrates the practical application of the public-key cryptography algorithm in both message encryption and digital signature creation and verification.
The implementation includes functions for encryption (Key Agreement) and signing and verifying digital signatures. In the sign function, ElGamal is employed to generate a digital signature of the message using the sender's private key and a specified hash function. The verify function checks the authenticity of the signature using the sender's public key and the same hash function.
This practical implementation of ElGamal highlights the algorithm's versatility in providing confidentiality through encryption and authenticity through digital signatures. It proves useful in various information security applications.
Generate a large prime number \( p \).
Select a generator \( g \) in the range [2, \( p-2 \)].
// isPrime checks if a number is prime using Miller-Rabin primality test. func isPrime(n *big.Int) bool { // Perform Miller-Rabin primality test with 20 iterations return n.ProbablyPrime(20) } // generatePrime generates a prime number with exactly n bits. func generatePrime(length int) (*big.Int, error) { for { // Generate a random number with at least n bits randomBits := make([]byte, length/8) _, err := rand.Read(randomBits) if err != nil { return nil, err } // Set the most significant and least significant bits to ensure an odd number randomBits[0] |= 1 randomBits[len(randomBits)-1] |= 1 // Create a big integer from the generated bytes prime := new(big.Int).SetBytes(randomBits) // Adjust to exactly n bits prime.SetBit(prime, length-1, 1) // Check if the generated number is prime using Miller-Rabin test if isPrime(prime) { return prime, nil } // Print a dot to the console every second print(".") } } // generateGenerator generates a generator in the range [2, p-2] func generateGenerator(p *big.Int) (*big.Int, error) { // Calculate the safe prime factor q of p q := new(big.Int).Rsh(p, 1) // Define the upper limit for generating the generator max := new(big.Int).Sub(p, two) for { // Choose a random generator g in the range [2, p-2] g, err := rand.Int(rand.Reader, max) if err != nil { return nil, fmt.Errorf("error generating G: %v", err) } // Check if g^2 mod p != 1 and g^q mod p != 1 if g.Cmp(two) == 1 && new(big.Int).Exp(g, two, p).Cmp(one) != 0 && new(big.Int).Exp(g, q, p).Cmp(one) != 0 { return g, nil } } } // ElGamalParams contains parameters for the ElGamal system type ElGamalParams struct { P *big.Int G *big.Int } // generateElGamalParams generates parameters for the ElGamal system func generateElGamalParams() (*ElGamalParams, error) { // Desired size for the large prime number (P) pSize := *length // Generate the large prime number P with exactly pSize bits p, err := generatePrime(pSize) if err != nil { return nil, fmt.Errorf("error generating P: %v", err) } // Generate a generator G in the range [2, P-2] g, err := generateGenerator(p) if err != nil { return nil, fmt.Errorf("error generating G: %v", err) } return &ElGamalParams{ P: p, G: g, }, nil }
Generate a private key \( x \) randomly.
type PrivateKey struct { PublicKey X *big.Int } func generateRandomX(p *big.Int) (*big.Int, error) { x, err := rand.Int(rand.Reader, new(big.Int).Sub(p, big.NewInt(2))) if err != nil { return nil, err } return x, nil }
Compute the public key \( Y = g^x \mod p \).
type PublicKey struct { G, P, Y *big.Int } func setup(privateKey *big.Int, g, p *big.Int) *big.Int { publicKey := new(big.Int).Exp(g, privateKey, p) return publicKey }
var ( zero = big.NewInt(0) one = big.NewInt(1) two = big.NewInt(2) ) // Sign hash func sign(random io.Reader, priv *PrivateKey, hash []byte) (*big.Int, *big.Int, error) { k := new(big.Int) gcd := new(big.Int) var err error // choosing random integer k from {1...(p-2)}, such that // gcd(k,(p-1)) should be equal to 1. for { k, err = rand.Int(random, new(big.Int).Sub(priv.P, two)) if err != nil { return nil, nil, err } if k.Cmp(one) == 0 { continue } gcd = gcd.GCD(nil, nil, k, new(big.Int).Sub(priv.P, one)) if gcd.Cmp(one) == 0 { break } } // m as H(m) m := new(big.Int).SetBytes(hash) // r = g^k mod p r := new(big.Int).Exp(priv.G, k, priv.P) // xr = x * r xr := new(big.Int).Mod( new(big.Int).Mul(r, priv.X), new(big.Int).Sub(priv.P, one), ) // hmxr = [H(m)-xr] hmxr := new(big.Int).Sub(m, xr) // kInv = k^(-1) kInv := k.ModInverse(k, new(big.Int).Sub(priv.P, one)) // s = [H(m) -xr]k^(-1) mod (p-1) s := new(big.Int).Mul(hmxr, kInv) s.Mod(s, new(big.Int).Sub(priv.P, one)) return r, s, nil } // Verify hash func verify(pub *PublicKey, hash []byte, r, s *big.Int) (bool, error) { // verify that 0 < r < p signr := new(big.Int).Set(r) if signr.Cmp(zero) == -1 { return false, errors.New("elgamal: r is smaller than zero") } else if signr.Cmp(pub.P) == +1 { return false, errors.New("elgamal: r is larger than public key p") } signs := new(big.Int).Set(s) if signs.Cmp(zero) == -1 { return false, errors.New("elgamal: s is smaller than zero") } else if signs.Cmp(new(big.Int).Sub(pub.P, one)) == +1 { return false, errors.New("elgamal: s is larger than public key p") } // m as H(m) m := new(big.Int).SetBytes(hash) // ghashm = g^[H(m)] mod p ghashm := new(big.Int).Exp(pub.G, m, pub.P) // y^r * r*s mod p YrRs := new(big.Int).Mod( new(big.Int).Mul( new(big.Int).Exp(pub.Y, signr, pub.P), new(big.Int).Exp(signr, signs, pub.P), ), pub.P, ) // g^H(m) y^r * r*s mod p if ghashm.Cmp(YrRs) == 0 { return true, nil // signature is verified } return false, errors.New("elgamal: signature is not verified") } // r and s data type elgamalSignature struct { R, S *big.Int } // SignASN1 signs a hash (which should be the result of hashing a larger message) // using the private key, priv. If the hash is longer than the bit-length of the // private key's curve order, the hash will be truncated to that length. It // returns the ASN.1 encoded signature. func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) { r, s, err := sign(rand, priv, hash) if err != nil { return nil, err } return asn1.Marshal(elgamalSignature{ R: r, S: s, }) } // VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the // public key, pub. Its return value records whether the signature is valid. func VerifyASN1(pub *PublicKey, hash, sig []byte) (bool, error) { var sign elgamalSignature _, err := asn1.Unmarshal(sig, &sign) if err != nil { return false, err } return verify(pub, hash, sign.R, sign.S) }
In the encrypt function, ElGamal is used to encrypt a message using the recipient's public key. A random number k is generated to ensure the randomness of the cipher. The function returns the ciphertext in hexadecimal string format, consisting of the concatenated components a and b.
The decrypt function performs the inverse operation, decrypting an ElGamal ciphertext using the corresponding private key. The result is the original message as an array of bytes.
This works because: \( b^{ax \pmod{p}} = y^k \cdot M \cdot (g^k)^x \pmod{p} = (g^x)^k \cdot M \cdot (g^k)^x \pmod{p} = g^{xk} \cdot M \cdot g^{xk} \pmod{p} = M \)
These codes were taken from the EDGE Toolkit source code.type elgamalEncrypt struct { C1, C2 *big.Int } // Encrypt Asn1 func EncryptASN1(random io.Reader, pub *PublicKey, message []byte) ([]byte, error) { c1, c2, err := EncryptLegacy(random, pub, message) if err != nil { return nil, err } return asn1.Marshal(elgamalEncrypt{ C1: c1, C2: c2, }) } // Decrypt Asn1 func DecryptASN1(priv *PrivateKey, cipherData []byte) ([]byte, error) { var enc elgamalEncrypt _, err := asn1.Unmarshal(cipherData, &enc) if err != nil { return nil, err } return DecryptLegacy(priv, enc.C1, enc.C2) } // EncryptLegacy func EncryptLegacy(random io.Reader, pub *PublicKey, msg []byte) (c1, c2 *big.Int, err error) { m := new(big.Int).SetBytes(msg) k, err := rand.Int(random, pub.P) if err != nil { return } c1 = new(big.Int).Exp(pub.G, k, pub.P) s := new(big.Int).Exp(pub.Y, k, pub.P) c2 = s.Mul(s, m) c2.Mod(c2, pub.P) return } // DecryptLegacy func DecryptLegacy(priv *PrivateKey, c1, c2 *big.Int) (msg []byte, err error) { s := new(big.Int).Exp(c1, priv.X, priv.P) if s.ModInverse(s, priv.P) == nil { return nil, errors.New("elgamal: invalid private key") } s.Mul(s, c2) s.Mod(s, priv.P) em := s.Bytes() return em, nil }
./edgetk -pkey setup -algorithm elgamal -bits 4096 > Params.pem
./edgetk -pkey keygen -algorithm elgamal -params Params.pem [-priv Private.pem] [-pass "pass"] [-pub Public.pem]
./edgetk -pkey sign -algorithm elgamal -key Private.pem file.ext > sign.txt
sign=$(cat sign.txt|awk '{print $2}')
./edgetk -pkey verify -algorithm elgamal -key Public.pem -signature $sign file.ext
echo $?
./edgetk -pkey wrapkey -algorithm elgamal -key Public.pem > cipher.txt
ciphertext=$(cat cipher.txt|grep "Cipher"|awk '{print $2}')
./edgetk -pkey unwrapkey -algorithm elgamal -key Private.pem -cipher $ciphertext
./edgetk -pkey text -key Private.pem
./edgetk -pkey text -key Public.pem
./edgetk -pkey text -params Params.pem
Copyright (c) 2024 Pedro F. Albanese <pedroalbanese@hotmail.com>
Permission to use, copy, modify, and distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.