Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

13.2 The ElGamal Signature Scheme

The ElGamal encryption method from Section 10.5 can be modified to give a signature scheme. One feature that is different from RSA is that, with the ElGamal method, there are many different signatures that are valid for a given message.

Suppose Alice wants to sign a message. To start, she chooses a large prime $p$ $p$ and a primitive root $α$ $α$ . Alice next chooses a secret integer $a$ $a$ such that $1 \leq a \leq p - 2$ $1 \leq a \leq p - 2$ and calculates $β \equiv α^{a} (m o d p)$ $β \equiv α^{a} (m o d p)$ . The values of $p$ $p$ , $α$ $α$ , and $β$ $β$ are made public. The security of the system will be in the fact that $a$ $a$ is kept private. It is difficult for an adversary to determine $a$ $a$ from $(p, α, β)$ $(p, α, β)$ since the discrete log problem is considered difficult.

In order for Alice to sign a message $m$ $m$ , she does the following:

Selects a secret random $k$ $k$ with $1 \leq k \leq p - 2$ $1 \leq k \leq p - 2$ such that $gcd (k, p - 1) = 1$ $gcd (k, p - 1) = 1$ .
Computes $r \equiv α^{k} (m o d p)$ $r \equiv α^{k} (m o d p)$ (with $0 < r < p$ $0 < r < p$ ).
Computes $s \equiv k^{- 1} (m - a r) (m o d p - 1)$ $s \equiv k^{- 1} (m - a r) (m o d p - 1)$ .

The signed message is the triple $(m, r, s)$ $(m, r, s)$ .

Bob can verify the signature as follows:

Download Alice’s public key $(p, α, β)$ $(p, α, β)$ .
Compute $v_{1} \equiv β^{r} r^{s} (m o d p)$ $v_{1} \equiv β^{r} r^{s} (m o d p)$ , and $v_{2} \equiv α^{m} (m o d p)$ $v_{2} \equiv α^{m} (m o d p)$ .
The signature is declared valid if and only if $v_{1} \equiv v_{2} (m o d p)$ $v_{1} \equiv v_{2} (m o d p)$ .

We now show that the verification procedure works. Assume the signature is valid. Since $s \equiv k^{- 1} (m - a r) (m o d p - 1)$ $s \equiv k^{- 1} (m - a r) (m o d p - 1)$ , we have $s k \equiv m - a r (m o d p - 1)$ $s k \equiv m - a r (m o d p - 1)$ , so $m \equiv s k + a r (m o d p - 1)$ $m \equiv s k + a r (m o d p - 1)$ . Therefore (recall that a congruence mod $p - 1$ $p - 1$ in the exponent yields an overall congruence mod $p$ $p$ ),

v_{2} \equiv α^{m} \equiv α^{s k + a r} \equiv (α^{a})^{r} (α^{k})^{s} \equiv β^{r} r^{s} \equiv v_{1} (m o d p) .

$v_{2} \equiv α^{m} \equiv α^{s k + a r} \equiv (α^{a})^{r} (α^{k})^{s} \equiv β^{r} r^{s} \equiv v_{1} (m o d p) .$

Suppose Eve discovers the value of $a$ $a$ . Then she can perform the signing procedure and produce Alice’s signature on any desired document. Therefore, it is very important that $a$ $a$ remain secret.

If Eve has another message $m$ $m$ , she cannot compute the corresponding $s$ $s$ since she doesn’t know $a$ $a$ . Suppose she tries to bypass this step by choosing an $s$ $s$ that satisfies the verification equation. This means she needs $s$ $s$ to satisfy

β^{r} r^{s} \equiv α^{m} (m o d p) .

$β^{r} r^{s} \equiv α^{m} (m o d p) .$

This can be rearranged to $r^{s} \equiv β^{- r} α^{m} (m o d p)$ $r^{s} \equiv β^{- r} α^{m} (m o d p)$ , which is a discrete logarithm problem. Therefore, it should be hard to find an appropriate $s$ $s$ . If $s$ $s$ is chosen first, the equation for $r$ $r$ is similar to a discrete log problem, but more complicated. It is generally assumed that it is also difficult to solve. It is not known whether there is a way to choose $r$ $r$ and $s$ $s$ simultaneously, though this seems to be unlikely. Therefore, the signature scheme appears to be secure, as long as discrete logs mod $p$ $p$ are difficult to compute (for example, $p - 1$ $p - 1$ should not be a product of small primes; see Section 10.2).

Suppose Alice wants to sign a second document. She must choose a new random value of $k$ $k$ . Suppose instead that she uses the same $k$ $k$ for messages $m_{1}$ $m_{1}$ and $m_{2}$ $m_{2}$ . Then the same value of $r$ $r$ is used in both signatures, so Eve will see that $k$ $k$ has been used twice. The $s$ $s$ values are different; call them $s_{1}$ $s_{1}$ and $s_{2}$ $s_{2}$ . Eve knows that

s_{1} k - m_{1} \equiv - a r \equiv s_{2} k - m_{2} (m o d p - 1) .

$s_{1} k - m_{1} \equiv - a r \equiv s_{2} k - m_{2} (m o d p - 1) .$

Therefore,

(s_{1} - s_{2}) k \equiv m_{1} - m_{2} (m o d p - 1) .

$(s_{1} - s_{2}) k \equiv m_{1} - m_{2} (m o d p - 1) .$

Let $d = gcd (s_{1} - s_{2}, p - 1)$ $d = gcd (s_{1} - s_{2}, p - 1)$ . There are $d$ $d$ solutions to the congruence, and they can be found by the procedure given in Subsection 3.3.1. Usually $d$ $d$ is small, so there are not very many possible values of $k$ $k$ . Eve computes $α^{k}$ $α^{k}$ for each possible $k$ $k$ until she gets the value $r$ $r$ . She now knows $k$ $k$ . Eve now solves

a r \equiv m_{1} - k s_{1} (m o d p - 1)

$a r \equiv m_{1} - k s_{1} (m o d p - 1)$

for $a$ $a$ . There are $gcd (r, p - 1)$ $gcd (r, p - 1)$ possibilities. Eve computes $α^{a}$ $α^{a}$ for each one until she obtains $β$ $β$ , at which point she has found $a$ $a$ . She now has completely broken the system and can reproduce Alice’s signatures at will.

Example

Alice wants to sign the message $m_{1} = 151405$ $m_{1} = 151405$ (which corresponds to one, if we let $01 = a, 02 = b, \dots$ $01 = a, 02 = b, \dots$ ). She chooses $p = 225119$ $p = 225119$ . Then $α = 11$ $α = 11$ is a primitive root. She has a secret number $a$ $a$ . She computes $β \equiv α^{a} \equiv 18191 (m o d p)$ $β \equiv α^{a} \equiv 18191 (m o d p)$ . To sign the message, she chooses a random number $k$ $k$ and keeps it secret. She computes $r \equiv α^{k} \equiv 164130 (m o d p)$ $r \equiv α^{k} \equiv 164130 (m o d p)$ . Then she computes

s_{1} \equiv k^{- 1} (m_{1} - a r) \equiv 130777 (m o d p - 1) .

$s_{1} \equiv k^{- 1} (m_{1} - a r) \equiv 130777 (m o d p - 1) .$

The signed message is the triple $(151405, 164130, 130777)$ $(151405, 164130, 130777)$ .

Now suppose Alice also signs the message $m_{2} = 202315$ $m_{2} = 202315$ (which is two) and produces the signed message $(202315, 164130, 164899)$ $(202315, 164130, 164899)$ . Immediately, Eve recognizes that Alice used the same value of $k$ $k$ , since the value of $r$ $r$ is the same in both signatures. She therefore writes the congruence

- 34122 k \equiv (s_{1} - s_{2}) k \equiv m_{1} - m_{2} \equiv - 50910 (m o d p - 1) .

$- 34122 k \equiv (s_{1} - s_{2}) k \equiv m_{1} - m_{2} \equiv - 50910 (m o d p - 1) .$

Since $gcd (- 34122, p - 1) = 2$ $gcd (- 34122, p - 1) = 2$ , there are two solutions, which can be found by the method described in Subsection 3.3.1. Divide the congruence by 2:

- 17061 k \equiv - 25455 (m o d (p - 1) / 2) .

$- 17061 k \equiv - 25455 (m o d (p - 1) / 2) .$

This has the solution $k \equiv 239 (m o d (p - 1) / 2)$ $k \equiv 239 (m o d (p - 1) / 2)$ , so there are two values of $k (m o d p)$ $k (m o d p)$ , namely 239 and $239 + (p - 1) / 2 = 112798$ $239 + (p - 1) / 2 = 112798$ . Calculate

α^{239} \equiv 164130, α^{112798} \equiv 59924 (m o d p) .

$α^{239} \equiv 164130, α^{112798} \equiv 59924 (m o d p) .$

Since the first is the correct value of $r$ $r$ , Eve concludes that $k = 239$ $k = 239$ . She now rewrites $s_{1} k \equiv m_{1} - a r (m o d p - 1)$ $s_{1} k \equiv m_{1} - a r (m o d p - 1)$ to obtain

164130 a \equiv r a \equiv m_{1} - s_{1} k \equiv 187104 (m o d p - 1) .

$164130 a \equiv r a \equiv m_{1} - s_{1} k \equiv 187104 (m o d p - 1) .$

Since $gcd (164130, p - 1) = 2$ $gcd (164130, p - 1) = 2$ , there are two solutions, namely $a = 28862$ $a = 28862$ and $a = 141421$ $a = 141421$ , which can be found by the method of Subsection 3.3.1. Eve computes

α^{28862} \equiv 206928, α^{141421} \equiv 18191 (m o d p) .

$α^{28862} \equiv 206928, α^{141421} \equiv 18191 (m o d p) .$

Since the second value is $β$ $β$ , she has found that $a = 141421$ $a = 141421$ .

Now that Eve knows $a$ $a$ , she can forge Alice’s signature on any document.

The ElGamal signature scheme is an example of a signature with appendix. The message is not easily recovered from the signature $(r, s)$ $(r, s)$ . The message $m$ $m$ must be included in the verification procedure. This is in contrast to the RSA signature scheme, which is a message recovery scheme. In this case, the message is readily obtained from the signature $s$ $s$ . Therefore, only $s$ $s$ needs to be sent since anyone can deduce $m$ $m$ as $s^{e_{A}} (m o d n)$ $s^{e_{A}} (m o d n)$ . It is unlikely that a random $s$ $s$ will yield a meaningful message $m$ $m$ , so there is little danger that someone can successfully replace a valid message with a forged message by changing $s$ $s$ .

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 13.2 The ElGamal Signature Scheme

Create new playlist

Sign In

Sign Up

Table of Contents for
13.2 The ElGamal Signature Scheme