Scribd
Upload
220 views7 pages

ElGamal Digital Signature Guide

The document describes the ElGamal digital signature algorithm. It involves a system public key (prime number p and primitive element α), each user having a private key x and public key y. To sign a message m, the signer randomly generates k, computes r=αk and solves for s in the signing equation. The signature is (r,s). Verification checks if αm=yrrs. The security relies on the difficulty of solving the discrete log problem to obtain the private key x from the public key y. An example demonstrates the signing and verification processes.

Uploaded by

AakashBarapatre
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
220 views7 pages

ElGamal Digital Signature Guide

The document describes the ElGamal digital signature algorithm. It involves a system public key (prime number p and primitive element α), each user having a private key x and public key y. To sign a message m, the signer randomly generates k, computes r=αk and solves for s in the signing equation. The signature is (r,s). Verification checks if αm=yrrs. The security relies on the difficulty of solving the discrete log problem to obtain the private key x from the public key y. An example demonstrates the signing and verification processes.

Uploaded by

AakashBarapatre
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

8. 4.

The ElGamal Digital Signature


Define GF(p) =Fp

System public key: p is a prime such that the discrete log problem in Fp is
infeasible,

Fp ,
*

a primitive element in Fp.

User Bob: Selects x, 0 < x < p with (x, p-1) = 1 as his private key.
Compute y = x as his public key.

Signing process: To sign a message m ( in the following, we always suppose


m is a hashed value of the message m.)

(a) Randomly picks k, 0 < k < p with (k, p-1) = 1.


(b) Computes r = k
(c) Solve for s in the equation:

m = xr + ks mod p 1

(called the signing equation)

i.e, s = k -1 (m xr ) mod p 1

Then, (r, s) is a digital signature of m.

(m, (r, s)) as a signed message

Verifying process: Check whether


m = yrrs

(i.e, s

y rs = r )

ElGamal and DSS Signing Process


m
Message
m

Hash
x: private key

m
r
s

x r= k

Sign

(r, s)

signature

k: secret number per message

ElGamal and DSS Verifying Process

m
r
s

Hash

Verifying

y = x: public key

Security of the ElGamal Signature Scheme:


Consider

m = xr + ks mod p 1

(1)

If the attacker can compute y = to obtain x, then he can forge any


signature since in (1) he can pick k to compute r, and therefore, obtain s.
x

Thus the security of the ElGamal digital signature algorithm is based on the
difficulty of solving discrete log problem in Fp .

Remark: The random number k should be different per message.

Example 1. System parameters: p = 23,


primitive in Z23

(p-1= 211) then = 5

User Bob: Private key: x = 3

y = 53 = 10

Public-key:
Signing Process:

Message m = 7 (We assume that this is the hashed value for simplicity,
i.e., h(m) = 7.)
(a) Pick a random number k = 9
(b) Compute r = 9 = 59 = 11 mod 23

(c) Solving for s in the equation:

m = xr + ks mod p-1

s = k 1 ( m xr) = 5(7 3 11) = 2 mod 22

Signature: (r, s) = (11, 20)

Verifying process: Check whether


m = yrr s

Compute:
m = 5 7 = 17

and

y r r s = 10111120 = 22 6 = 17

Thus, (11, 20) is a valid signature of m = 7.

You might also like