Elgamal Encryption

Question 1

What is Elgamal?

Answer 1

Elgamal is added on to Diffie Hellman, in order to encrypt messages. It is based on the Discrete Logarithm Problem.

Question 2

How does Key Generation work in Elgamal?

Answer 2

• Choose a large prime number (p)
• Choose a generator (g) of the group (mod p)
• Choose a private key (x), which is a random number
• Compute the public key, using: y = g^x mod p
• Publish public key

Question 3

How does Elgamal encrypt messages?

Answer 3

• Choose a random ephemeral key (k), which is co-prime to (p - 1) and must also be different for each message
• Compute the masking key, using the public key
• Encrypt the message using the private key combined with the masking key, mod p

Question 4

How do you decrypt using Elgamal?

Answer 4

• You receive the encrypted message alongside the ephemeral key
• Re-compute the masking key using details from the ephemeral key mod p
• Decrypt the message using the private key that is calculated using the message and the masking key inverted

Question 5

What are the practicalities of using Elgamal?

Answer 5

• Elgamal has major weaknesses if you re-use an ephemeral key, and is also less efficient than simply using Diffie-Hellman then AES instead of Diffie-Hellman then Elgamal.
• It is highly popular for use in digital signatures

Question 6

What are some practicalities surrounding using Elgamal for Digital Signatures?

Answer 6

• Without hashing, it is vulnerable to existential forgeries and key recovery is possible if you re-use the ephemeral key.
• The combined message and signature m is roughly 3 times the size of the prime p, which makes Elgamal signatures quite inefficient.

Question 7

What are some properties of DSA?

Answer 7

• Computed in a subgroup of prime order q, which is usually 160 bits
• The signature is 320 bits
• Hashing is enforced by the algorithm, and a hash function must match the key size
• Index calculus does not apply to the sub-group, so 160 bit DSA signatures have a security of 80 bits

Question 8

What are some properties of ECDSA?

Answer 8

• Identical to DSA in function, but instead uses an elliptic curve
• More efficient, does not require modulus of thousands of bits
• Security level is based on generic attacks against Elliptic Curves
• Deterministic generation of k is often used for safety