Elgamal Encryption

• Extension of diffie-helman

Elgamal

• Develop by Taher Elgamal in 1985
• As this is a public key encryption, can make some efficiency savings by not sending all the information both ways every time
• If ...

Computational Efficiency

• Both the exponentiations during encryption can be pre-computed during downtime
• Can also improve on the decryption step using Fermats little theorem

Practicalities

• Elgamal is a probabilistic encryption scheme. Uses an ephemeral key pair a and k_E and ...
• .....

DSA

• Based on Elgamal, developed by NIST as an alternative to RSA
• Computed in a subgroup of prime orders q, which is usually 160 bits
• Means the signature (r,s) 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
• In practice larger keys would be required now

ECDSA

• Identical to DSA, operates on an elliptic curve over $Z_p$ with the signature calculated over a large subgroup of prime order #q
• More efficient, does not require modulus of thousands of bits
• Security level is based on generic attacks against EC
• Deterministic generation of k is often used for security
• Other variants like EdDSA using Edwards curves