Joint Advanced Students Seminar 2005

The ElGamal Cryptosystem

Andreas V. Meier
meiera@in.tum.de

TUM Informatik

Andreas V. Meier The ElGamal Cryptosystem p.1/23

Structure
Public Key Cryptography Assigned Complexity Problems ElGamal Cryptosystem Importance of Correct Implementation Summary

Andreas V. Meier The ElGamal Cryptosystem p.2/23

Public Key Cryptography

Introduced 1976 by Dife and Hellman Basic concept: Trapdoor functions (see following presentation) Features:
sender verication private key part remains at owner public key part freely distributable no secret channel neccessary no pre-shared keys

Prominent representative: RSA (1977) ... and ElGamal

Andreas V. Meier The ElGamal Cryptosystem p.3/23

Public Key Cryptography - Procedure

Scenario:
Alice wants to send an encrypted message to Bob

Procedure 1. Bob computes a public and a private key, the keypair 2. Bob publishes his public key 3. Alice Encrypts the message using Bobs public key 4. Alice sends the message to Bob. 5. Bob encrypts the message using his private key Effect:
Nobody intercepting the message can read nor alter it unrecognized

Andreas V. Meier The ElGamal Cryptosystem p.4/23

Public Key Cryptography - Scheme

public key Alice encrypt using public key Bob decrypt using private key

encrypted message

Andreas V. Meier The ElGamal Cryptosystem p.5/23

Public Key Cryptography - Algorithm

Two public parameters:
p: prime number g: generator such that n [1; p 1] : k; n = g k mod p Alice generates a private random integer a Bob generates a private random integer b Alice generates her public value g a mod p Bob generates his public value g b mod p Alice computes g ab = (g a )b mod p Bob computes g ba = (g b )a mod p

Procedure: 1. 2. 3.

4. Both now have a shared secret k since k = g ab = g ba

Andreas V. Meier The ElGamal Cryptosystem p.6/23

Public Key Cryptography - Summary

Features
able to set up a secure channel between two parties based on the Discrete Logarithm Problem

Problems
vulnerable to the man-in-the-middle attack vulnerable to chosen-plaintext attacks ( signed keys) not useful for one way communication (e.g. email)

Andreas V. Meier The ElGamal Cryptosystem p.7/23

Dife-Hellmann Problem DH
Instance:
A multiplicative group (G, ), a generator g of G, two public key parts g a and g b

Question:
Find the common key g ab

Andreas V. Meier The ElGamal Cryptosystem p.8/23

Discrete Logarithm Problem - DL

Instance:
A multiplicative group (G, ), a generator g of G, |G| = n, and an element x

Question:
Find the unique integer a, 0 a n 1, such that g a = x. a can be described as logg x

Andreas V. Meier The ElGamal Cryptosystem p.9/23

Complexity of DL and DH
Lower bound: (p) with p = greatest prime divisor of the group order Related problem: Decision DH (DDH)
Instance: the triple g a , g b and g c Question: is c ab

(mod p)?

Andreas V. Meier The ElGamal Cryptosystem p.10/23

Algorithms for DL
Given: Generator g of G, beta G Wanted: a,1 < a < p 1 Assumption: Multiplication of x, y G in O(1) 2. sort the list wrt. the second coordinate 3. given a , perform a binary search on the list First step: O(n), Second step: O(n log n), Third step: O(log n) Neglecting logarithmic factors: Precomputation-time: O(1) Space: O(n), Solving in O(1)
Shank, Pollard Rho, Pholig-Hellman

1. compute all possible g i into a list of pairs (i, g i )

Andreas V. Meier The ElGamal Cryptosystem p.11/23

Complexity of DL - Reduction to Addition

So far we had a multiplicative Group (G, ) Idea: DL in Additive Group (G, +)

Andreas V. Meier The ElGamal Cryptosystem p.12/23

ElGamal Cryptosystem
Presented in 1984 by Tather Elgamal Key aspects:
Based on the Discrete Logarithm problem Randomized encryption

Application:
Establishing a secure channel for key sharing Encrypting messages

Andreas V. Meier The ElGamal Cryptosystem p.13/23

ElGamal Cryptosystem - Key Generation

Participant A generates the public/private key pair 1. Generate large prime p and generator g of the multiplicative Group Z pf of the integers modulo p. p 2. Select a random integer a, 1 a p 2, and compute g a mod p. 3. As Public key is (p, g, g a ); As Private key is a.

Andreas V. Meier The ElGamal Cryptosystem p.14/23

ElGamal Cryptosystem - Encryption Procedure

Participant B encrypts a message m to A 1. Obtain As authentic public key (p, g, g a ). 2. Represent the message as integers m in the range {0, 1, . . . , p 1}. 4. Compute = g k mod p and = m (g a )k . 5. Send ciphertext c = (, ) to A 3. Select a random integer k , 1 k p 2.

Andreas V. Meier The ElGamal Cryptosystem p.15/23

ElGamal Cryptosystem - Decryption Procedure

Participant A receives encrypted message m from B 1. Use private key a to compute ( p1a ) mod p. Note: p1a = a = aak 2. Recover m by computing ( a ) mod p.

Andreas V. Meier The ElGamal Cryptosystem p.16/23

ElGamal Cryptosystem - Encryption Sample

Alice choses her public key (17, 6, 7):
Prime p = 17 Generator g = 6 Private key part a = 5 Public key part g a mod p = 65 mod 17 = 7

Bob encrypts his message m = 13:

He chooses a random k = 10 He calculates = g k mod p = 610 mod 17 = 15 He encrypts = m g k mod p = (13 710 ) mod 17 = 9

Bob sends = 15 and = 9 to Alice.

Andreas V. Meier The ElGamal Cryptosystem p.17/23

ElGamal Cryptosystem - Decryption Sample

Alice receives = 15 and = 9 from Bob.
Her public key is (p, g, g a ) = (17, 6, 7) Her private key is a = 5

Alice now decrypts the message using her private key:

Decryption factor

Decryption: ( 9) mod p = (9 9) mod 17 = 13

( a ) mod p = 155 mod 17 = 1511 mod 17 = 9

Alice has now decrypted the message and received: 13

Andreas V. Meier The ElGamal Cryptosystem p.18/23

ElGamal Cryptosystem - Summary

Features:
use of a random factor k for encryption variant of DH: shared secret is g ak

Problems:
Duplicates message length Depends on intractability of DL and DH

Andreas V. Meier The ElGamal Cryptosystem p.19/23

Importance of Correct Implementation - GnuPG Issue

Problem discovered late 2003 by Phong Q. Nguyen in GnuPG
Too small private exponent and too short nonce used for signature generation. Present for almost four years!

Effects
All signatures created with GnuPG up to the day of x

considered compromised

Andreas V. Meier The ElGamal Cryptosystem p.20/23

Importance of Correct Implementation - Code Sample

/ IMO u s i n g a k much l e s s e r than p i s s u f f i c i e n t and i t g r e a t l y improves t h e e n c r y p t i o n performance . and add a l a r g e s a f e t y margin . / n b i t s = wiener_map ( o r i g _ n b i t s ) 3 / 2 ; nbytes = ( n b i t s +7) / 8 ; We use Wiener s t a b l e

Wiener Table: |p| 512 768 qbit 119 145

1024 165

1280 183

1536 198

1792 212

2048 225

2304 237

... ...

Small k in signature lattice attack

Andreas V. Meier The ElGamal Cryptosystem p.21/23

Summary
What have we heared in this presentation?
Public Key scheme - suitable for sharing symetric keys Discrete Logarithm Problem - even harder than

F ACT ORIZE

ElGamal Cryptosystem Importance of correct implementation of cryptosystems

Andreas V. Meier The ElGamal Cryptosystem p.22/23

Discussion
Questions from the audience? Why are hybrid cryptosystems used for encrypting e.g. a

vpn?

Andreas V. Meier The ElGamal Cryptosystem p.23/23

Literature
Cryptography: Theory and practice, Douglas R. Stinson New directions in cryptography, Dife and Hellman Handbook of applied Cryptography, Menezes, van

Oorschot, Vanstone

A Public Key Cryptosystem and a Signature Scheme Based

on Discrete Logarithms, Tather Elgamal

Andreas V. Meier The ElGamal Cryptosystem p.24/23