CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Part VI
Signature schemes
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
The ElGamal signature scheme
Security of the ElGamal signature scheme
Careless uses of ElGamal signature scheme
A downside of ElGamal
ElGamal variants
A problem…
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Recall the definition
Definition (Signature scheme)
A signature scheme is a five-tuple (P,A,K,S,V)
P, a finite set of possible messages
A, a finite set of possible signatures
K, a keyspace, the finite set of possible keys.
For each key k there is a signing algorithm
sigk : P ! A and a corresponding verification
algorithm verk : P “A ! {t, f} such that for all
messages x and all signatures y:
verk(x, y) =
!
t if y = sigk(x)
f if y #= sigk(x)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
The ElGamal signature scheme
Security of the ElGamal signature scheme
Careless uses of ElGamal signature scheme
A downside of ElGamal
ElGamal variants
A problem…
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
ElGamal signature scheme
Select p prime and !, a primitive element modulo p
ElGamal signature scheme
P = Z!p, A = Z
!
p ” Zp”1
K = {(p, !, a, “) | ” $ !a (mod p)}
p, ! and ” are the public key, and a is the private
key
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
ElGamal signature scheme (cont).
Signature and verification functions
For k = (p, !, a, “) and for a (secret) random
number r % Z!p”1 we have
sigk(x, r) = (#, $)
where
# = !r (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
ElGamal signature scheme (cont).
Signature and verification functions
For k = (p, !, a, “) and for a (secret) random
number r % Z!p”1 we have
sigk(x, r) = (#, $)
where
# = !r (mod p)
and
$ = (x & a#)r”1 (mod p & 1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
ElGamal signature scheme (cont).
Signature and verification functions
For k = (p, !, a, “) and for a (secret) random
number r % Z!p”1 we have
sigk(x, r) = (#, $)
where
# = !r (mod p)
and
$ = (x & a#)r”1 (mod p & 1)
For x, # % Z!p and $ % Zp”1 we have
verk(x, (#, $)) = t ‘ ”
!#” $ !x (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
An example
Alice needs to sign x = 27 and send it to Bob.
Already chosen are public parameters: p = 107,
! = 2.
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
An example
Alice needs to sign x = 27 and send it to Bob.
Already chosen are public parameters: p = 107,
! = 2.
Now Alice generates her key, selecting private
key a = 82 and calculating
” $ !a (mod p)
$ 282 (mod 107) $ 90
Alice’s public key is p, ! and ” = 90
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Example: signing
Alice uses random number r = 25, note
gcd(25, 106) = 1 so she can calculate
r”1 = 25″1 $ 17 (mod 106)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Example: signing
Alice uses random number r = 25, note
gcd(25, 106) = 1 so she can calculate
r”1 = 25″1 $ 17 (mod 106)
Now to sign x = 27:
# = !r (mod p)
= 225 $ 88 (mod 107)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Example: signing
Alice uses random number r = 25, note
gcd(25, 106) = 1 so she can calculate
r”1 = 25″1 $ 17 (mod 106)
Now to sign x = 27:
# = !r (mod p)
= 225 $ 88 (mod 107)
and
$ = (x & a#)r”1 (mod p & 1)
= (27 & 82 ” 88) ” 17 $ 5 (mod 106)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Example: signing
Alice uses random number r = 25, note
gcd(25, 106) = 1 so she can calculate
r”1 = 25″1 $ 17 (mod 106)
Now to sign x = 27:
# = !r (mod p)
= 225 $ 88 (mod 107)
and
$ = (x & a#)r”1 (mod p & 1)
= (27 & 82 ” 88) ” 17 $ 5 (mod 106)
and Alice’s signature is (x, (#, $)) = (27, (88, 5))
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Example: verification
Bob (or anyone else) can now verify this:
“!#” = 9088 ” 885 $ 31 (mod 107)
and
!x = 227 $ 31 (mod 107)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Why does verification succeed?
If (#, $) is a correct signature then we have that
$ $ (x & a#)r”1 (mod p & 1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Why does verification succeed?
If (#, $) is a correct signature then we have that
$ $ (x & a#)r”1 (mod p & 1)
( r$ $ x & a# (mod p & 1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Why does verification succeed?
If (#, $) is a correct signature then we have that
$ $ (x & a#)r”1 (mod p & 1)
( r$ $ x & a# (mod p & 1)
( x $ a# + r$ (mod p & 1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Why does verification succeed?
If (#, $) is a correct signature then we have that
$ $ (x & a#)r”1 (mod p & 1)
( r$ $ x & a# (mod p & 1)
( x $ a# + r$ (mod p & 1)
Hence we see that:
“!#” $ !a!!r” (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Why does verification succeed?
If (#, $) is a correct signature then we have that
$ $ (x & a#)r”1 (mod p & 1)
( r$ $ x & a# (mod p & 1)
( x $ a# + r$ (mod p & 1)
Hence we see that:
“!#” $ !a!!r” (mod p)
$ !a!+r” (mod p) $ !x (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
Or, starting with the verification function we can derive
the signature function. We have:
!x $ “!#” (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
Or, starting with the verification function we can derive
the signature function. We have:
!x $ “!#” (mod p)
Substitute
# $ !r (mod p) ” $ !a (mod p)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
Or, starting with the verification function we can derive
the signature function. We have:
!x $ “!#” (mod p)
Substitute
# $ !r (mod p) ” $ !a (mod p)
But not in the exponent!
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
After the substitution we have:
!x $ !a!!r” (mod p)
$ !a!+r” (mod p) (1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
After the substitution we have:
!x $ !a!!r” (mod p)
$ !a!+r” (mod p) (1)
! is a primitive element modulo p
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
After the substitution we have:
!x $ !a!!r” (mod p)
$ !a!+r” (mod p) (1)
! is a primitive element modulo p
Congruence (1) is true if and only if the exponents
are equivalent modulo p & 1
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
After the substitution we have:
!x $ !a!!r” (mod p)
$ !a!+r” (mod p) (1)
! is a primitive element modulo p
Congruence (1) is true if and only if the exponents
are equivalent modulo p & 1
That is
x $ a# + r$ (mod p & 1)
CM30173:
Cryptography
Part IV
The ElGamal
signature scheme
Security of the ElGamal
signature scheme
Careless uses of
ElGamal signature
scheme
A downside of ElGamal
ElGamal variants
A problem…
Where did the signature function come
from?
After the substitution we have:
!x $ !a!!r” (mod p)
$ !a!+r” (mod p) (1)
! is a primitive element modulo p
Congruence (1) is true if and only if the exponents
are equivalent modulo p & 1
That is
x $ a# + r$ (mod p & 1)
Given x, a, # and r this produces the value of $ given in
the definition.
Signature schemes
The ElGamal signature scheme
Security of the ElGamal signature scheme
Careless uses of ElGamal signature scheme
A downside of ElGamal
ElGamal variants
A problem…