�Introduction to Cryptology

​

​

​

​

​

​

​

​

​

​

21.10.2025

​

Lecture-6

Public-Key Cryptography

ElGamal Public-Key Crypto-System

Page : 1

bfolieq.drw

​

​

• Public-key Objective
• ElGamal Public-Key Encryption System
• ElGamal Public-Key Signature System
• ElGamal Security considerations
• Public Key Signature Standard

​

Lecture Outlines

Page : 2

bfolieq.drw

​

​

Y = E (Z,X)

Channel

Message

Sender

Receiver

Message

X

E ( Z,X )

D ( Z,Y )

X

The Target of Public Key Cryptography

Ciphering

De-Ciphering

Page : 3

bfolieq.drw

​

​

ElGamal Crypto-System, 1985

​

​

​

​

Taher ElGamal: BsC, EE from Cairo University, � MsC and PhD Stanford University advisor M. Hellmann

ElGamal Cryptosystem became a NIST standard called DSA in 1994.

Basic idea: Multiplication instead of exponentiation

Taher ElGamal

Page : 4

bfolieq.drw

​

​

NIST standards are guidelines and frameworks developed by the National Institute of Standards and Technology (NIST), a U.S. government agency, to promote innovation, industrial competitiveness, and security. They include standards for measurement science, technology, and cybersecurity, such as the widely used Cybersecurity Framework, which helps organizations manage and reduce cyber risk. Businesses and government agencies use these standards for instrument calibration, data protection, and to ensure security and quality control

Page : 5

bfolieq.drw

​

​

ElGamal Crypto-System 1985

M • Z =C

Is that possible?: Yes,

By using groups arithmetic in in GF !

Basic idea: Multiplication instead of exponentiation

The inverse key Z^-1 should not be computable if Z is known

Galois Field, a finite set of numbers where addition, subtraction, multiplication, and division (except by zero) are possible and follow specific rules

Page : 6

bfolieq.drw

​

​

ElGamal Crypto-System 1985

X

Z^-1 = (α^R) ^–x = α - ^{X . R}

M

That is possible by using arithmetic in GF(q) !

Basic idea: Multiplication instead of exponentiation for encryption

Z = y^R = α ^x·R

​

R= Random secret generated ad-hoc by sender

C = M . α ^{X . R}

Public directory:

α primitive element in GF(q)

Page : 7

bfolieq.drw

​

​

ElGamal Secrecy-System (1985)

X

X

(y_b)^R

​

M

C = M . α ^{Xb . R}

M

α primitive element in GF(p)

Xa = secret key of A

α ^Xa

Xb = secret key of B

α ^Xb

r = α ^R

R

y_b

(r)^-Xb =α - ^{Xb. R}

Random Generator : R = 1 ... p-1

User A encrypts M to B

User B decrypts

y_a = α ^Xa public key of A

y_b = α ^Xb public key of B

α ^R

- Xb = (p-1) - Xb

Z^-1 = α - ^{Xb. R}

Z = α ^{Xb. R}

/

m

/

m-bits

m = log₂ p

r

C

Notice 2: The scheme applies similarly over GF(2^m) , with α as a primitive element in GF(2^m) .

Notice 1: a new R is needed for every M! Otherwise, Z can be easily revealed if M is known!

- Xb

Page : 8

bfolieq.drw

​

​

Example 1: Setup ElGamal Encryption System using GF(11). Send the message M=10 from user A to B. The secret key of B is6and for A is 7

X

X

(9)^R

​

- Xb = -6

M=10

C = M .α ^{Xb . R} = 10 . 3 =8

M =32 mod 11 =10

α = 2 = primitive element in GF(11)

Xa = secret key of A=7

α ⁷ = 7

Xb =6= secret key of B

Y_b=α ^Xb= 2⁶ = 9

r =2 ⁸ =3

R=8

y_b

(3)^-Xb = (3)⁴ =4

Random Generator : R = 1 ... p-1 ,

we select R= 8

User A sends M to B

User B receives

y_a = α ^Xa public key of A = 7

y_b = α ^Xb public key of B = 9

α ^R

• Xb = (p-1) – Xb

-Xb = (11-1)-6 = 4

Z=9 ⁸ = (2 ⁶)⁸ = 2^{48 mod 10} =2⁸ =3

r=3

C=8

Solution :

Computing order of α =2: 2²=4≠1, 2³=8, 2⁴=5, 2⁵=10 ≠1, => order of 2 is 10 => 2 is a primitive element !.

​

p=11=2 . 5+1, Possible orders = divisors of p-1=2x5, that is 1,2,5,10.

(4)

Notice : If an attacker knows �one message, say M=10

The ecryption key Z can be revealed simply� as Z= M^-1.C= 10^-1.8 mod 11 =3

Page : 9

bfolieq.drw

​

​

ElGamal Crypto-System (1985)

• based on discrete logarithm problem
• Security is as that of DH system
• DL problem needs less key-bits than RSA

for the same security

• Asymmetric workload: good for some

applications

• ElGamal encryption is probabilistic, meaning that a single plaintext would be encrypted to many possible ciphertexts as a new random R is required for each encrypted block..

Disadvantages

Advantages

• The cryptogram needs more bits

than the plaintext (double)

• A new random is needed for

every encrypted message

• Asymmetric workload: bad for

some applications

Page : 10

bfolieq.drw

​

​

ElGamal Signature Scheme

Signed Message

M

k ^-1 ( M - r . X_a ) mod (p-1) = S

Then M is authentic.

User A cannot deny �having signed message M

α is primitive in GF(p)

X_a = Secret Key of A

​

α ^Xa = y_a

k

User A signs M

Verifier

y_a = public key of A

k Random unit in Z_p-1

That is: gcd (k, p-1 ) = 1

r = α^k

M

​

S

​

r

α ^M = y_a^r . r ^S mod p

If

public directory

p, α, y_a

Page : 11

bfolieq.drw

​

​

Digital Signature Standard DSS (1994)

Explicit true signature based on ElGamal Signature System (1985)

Secure Hash Algorithm

(SHA) see later

M

H(M) 160 bits

Digital Signature Algorithm

(DSA)

Random

Source

160 bits 160 bits

( r , S )

Signature

M

k

Signed Message

Data digest (compression)

using Hash functions

Page : 12

bfolieq.drw

​

​

Digital Signature Algorithm DSA

Standardized (1994) Based on ElGamal Signature Scheme

Signed Message

M

or H(M)

k ^-1 ( H(M) + r . X_a ) in GF(q) = S

Then M is authentic

α is element in GF(p) with order q

where q = large prime (160 bits)

(q divides p-1 )

X_a = Secret Key of A

α ^Xa = y_a

k

User A signs M

Verifier

y_a = public key of A

k Random unit in GF(q)

For which gcd (q,k)=1 is valid

k = 1 to q-1 (160 bit)

R_q [ R_p(α^k) ] = r

M

​

S

​

r

R_q(M . S ^-1 )

R_p[α . y_a ] = U

R_q(r . S ^-1)

If

- p is a prime with 512 ... 1024 bits, q divides p-1 with a size of 160 bits,

- fresh k is required for every message!

public directory

p, q, α, y_a

r = R_q( U )

160 bits

160 bits

Page : 13

bfolieq.drw

​

​

Example 2: 1. Sign the message M=6 by using the Digital Signature Algorithm DSA, Use GF(p)=GF(11).

2. Check the resulting electronic signature

​

Signed Message M=6

M = 6

or H(M)

k ^-1 ( M + r . X_a ) in GF(q)=3(6+4x3) mod 5=4 = S

This true, Thus M is authentic

α =3 is element in GF(p=11) with order q=5

where 5 = large prime

X_a = Secret Key of A =3

y_a =3 ³ = 5 in GF(11)

K=2

User A signs M

Verifier

y_a = 5= public key of A

K=2 Random invertible mod (q=5)

K^-1 = 3 (mod 5)

R₅[ R₁₁(3²) ] = 4 = r

M=6

​

S=4

​

r=4

R_q(M . S ^-1 )

R_p[α . y_a ] = U

R_q(r . S ^-1)

If

public directory

p, q, α, y_a

Check if r = R_q( U )

4 = R₅( 9 )

4 = 4

R₅(6 . 4 )

U=R₁₁[3 . 5 ] = 9

R₅(4 . 4)

Solution:

Computing order of α =3: 3²=9≠1, 3³=5, 3⁴=4, 3⁵=1 => order of 3 is 5

P=11=2 . 5+1, Possible orders = divisors of p-1=2x5, that is 1,2,5,10. Select q=5

11, 5, 3, 5

Page : 14

bfolieq.drw

​

​

ElGamal Signature System (1985), DSS (1994)

• Computations on Signer site are

less complex than verifier site

​

• Security is based on the

discrete logarithm problem which is� still seen as computationally� infeasible.

Disadvantages

Advantages

• A new random is required

to sign every message

• more computations than RSA

are needed

• DSS may be less secure than� RSA as the security in GF(q)� with the order of about 160 Bits

Page : 15

bfolieq.drw

​

​

Security of ElGamal Public Key Crypto-System

(Equivalent to DH system)

Security considerations and known facts:

1. Based on the assumption/claim that the discrete logarithm is still not efficiently computable according to the public literature
2. A primitive element α from GF(p) or GF(2^m) is used to make exhaustive search algorithms infeasible. If y =α^t , only y and α are known. To break the system, we need to find t. To get t , α is repeatedly multiplied by itself i times when αⁱ =y, then t=i.

The order of α (as a primitive element) is p-1 in GF(p) or 2^m-1 in GF(2^m). Therefore, p is selected as 1000 to 4000 bits prime or m> 1000.

3. Caution: There is no evidence that no efficient algorithms can be found to break the system.
4. p-1 should have large prime factor to make the discrete logarithm computation infeasible (p is called a strong prime).

​

Page : 16

bfolieq.drw

​

​

Hash Functions

Iterated Hash Function: generates a digest of the data after being sequentially processed through the so-called Hash function. In general as follows:

Hash

Mapping

H_i

H_i-1

H₀ Initial value memory

x_i

Input String

X = (x₁ x₂ ...x_i .... x_n)

Output H is the digest of Input X :

​

H = Hash(H₀ , X)

Example: SHA (Secure Hash Algorithm) proposed as a standard with DSA

with N=160 bits (exposed to many attacks !) not more recommended !!!

N bits: size of hash value (digest)

Hash functions are needed to generate message digest

Non-linear

state machine

Page : 17

bfolieq.drw

​

​

Few Recommended

“Practical Hash Functions”

by deploying

“Block Ciphers”

Page : 18

bfolieq.drw

​

​

Hash Functions

Based on block ciphers

DM Scheme (Davis and Meyer)

Input String

X = (x₁ x₂ ...x_i .... x_n)

Digest of Input X is:

H = Hash(H₀ , X)

BC: Block Cipher

KEY

H_i

H_i-1

H_i = E_xi (H_i-1) ⊕ H_i-1

/ N

/

N

Cipher key length = Hash Block length = N

x

Y

Page : 19

bfolieq.drw

​

​

BC: Block Cipher

KEY

Cipher key length = 2 x Cipher block length N

Hash Functions

Based on block ciphers

LM Scheme (Lai and Massey 1992)

Input String

X = (x₁ x₂ ...x_i .... x_n)

Digest of Input X is:

H = E (H₀ , X)

H_i

H_i-1

H_i = E (H_i-1)

/ N

/

N

H_i-1| x_i

N /

Page : 20

bfolieq.drw

​

​

BC

H_i-1

H_i

x_i

BC

g

H_i

x_i

H_i-1

Davis-Meyer

Miyaguchi-Preneel

Traditional Hash Functions

Based on deploying block ciphers (BC)

(well known constellations. See NIST standards)

BC: Block Cipher

state

X

Y

key

Page : 21

bfolieq.drw

​

​

Block-Cipher based Hash Functions alternatives 1/2

Source: Handbook of Applied Cryptography

by Alfred J. Menezes, Paul C. Van Oorschot, Scott A. Vanstone, CRC Press (October 16, 1996) (available free of charge on the WEB)

Page : 22

bfolieq.drw

​

​

Block-Cipher based Hash Functions alternatives 2/2

Source: Handbook of Applied Cryptography

by Alfred J. Menezes, Paul C. Van Oorschot, Scott A. Vanstone, CRC Press (October 16, 1996) (available free of charge on the WEB)

Page : 23

bfolieq.drw

​

​