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…
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 discrete logarithm problem
Discrete logarithm problem (DLog problem)
Given p prime, ! a primitive element modulo p and
” ! Z!p find an element a, 0 ” a ” p # 2 such that
!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…
Recall the discrete logarithm problem
Discrete logarithm problem (DLog problem)
Given p prime, ! a primitive element modulo p and
” ! Z!p find an element a, 0 ” a ” p # 2 such that
!a $ ” (mod p)
Assume Oscar wants to forge a signature for a specific
message x. Is the di!culty of doing so related to the
discrete logarithm 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…
Yes…
If Oscar chooses ! and then tries to find the
corresponding ” he must find some ” such that
#!!” ! $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…
Yes…
If Oscar chooses ! and then tries to find the
corresponding ” he must find some ” such that
#!!” ! $x (mod p)
that is, Oscar must compute
” = log! $
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…
No…?
If Oscar chooses ” and then he must solve
#!!” ! $x (mod p) to find !
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 existential forgery
Assuming no hash function is used… there is a
key-only existential forgery
Oscar selects !, ” and x simultaneously
Conclusion: we need to use a hash function.
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 existential forgery
Assuming no hash function is used… there is a
key-only existential forgery
Oscar selects !, ” and x simultaneously
Conclusion: we need to use a hash function.
How does Oscar find !, ” and 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…
An existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (mod p)
2 Verification requires that #!!” ! $x (mod p), in
our case we have:
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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (mod p)
2 Verification requires that #!!” ! $x (mod p), in
our case we have:
#!!” ! $x (mod p)
$ #!$(i+aj)” ! $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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (mod p)
2 Verification requires that #!!” ! $x (mod p), in
our case we have:
#!!” ! $x (mod p)
$ #!$(i+aj)” ! $x (mod p)
$ #!$aj”$i” ! $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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (mod p)
2 Verification requires that #!!” ! $x (mod p), in
our case we have:
#!!” ! $x (mod p)
$ #!$(i+aj)” ! $x (mod p)
$ #!$aj”$i” ! $x (mod p)
$ #!#j” ! $x!i” (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 existential forgery
Select i, j such that 0 ” i, j ” p # 2.
1 Set ! = $i#j (mod p), this can be written as
! = $i#j (mod p)
= $i($a)j (mod p)
= $i+aj (mod p)
2 Verification requires that #!!” ! $x (mod p), in
our case we have:
#!!” ! $x (mod p)
$ #!$(i+aj)” ! $x (mod p)
$ #!$aj”$i” ! $x (mod p)
$ #!#j” ! $x!i” (mod p)
$ #!+j” ! $x!i” (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…
Example
Taking our earlier scheme with p = 107, $ = 2, a = 82,
# = 90. Oscar might select i = 23, j = 31 (and so
j!1 ! 65 (mod p # 1)). Oscar computes:
! = $i#j = 2239031 = 59 (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…
Example
Taking our earlier scheme with p = 107, $ = 2, a = 82,
# = 90. Oscar might select i = 23, j = 31 (and so
j!1 ! 65 (mod p # 1)). Oscar computes:
! = $i#j = 2239031 = 59 (mod p)
” = #!j!1 = #59 % 65 = 87 (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…
Example
Taking our earlier scheme with p = 107, $ = 2, a = 82,
# = 90. Oscar might select i = 23, j = 31 (and so
j!1 ! 65 (mod p # 1)). Oscar computes:
! = $i#j = 2239031 = 59 (mod p)
” = #!j!1 = #59 % 65 = 87 (mod p # 1)
x = i” = 23 % 87 = 93 (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…
Example
Taking our earlier scheme with p = 107, $ = 2, a = 82,
# = 90. Oscar might select i = 23, j = 31 (and so
j!1 ! 65 (mod p # 1)). Oscar computes:
! = $i#j = 2239031 = 59 (mod p)
” = #!j!1 = #59 % 65 = 87 (mod p # 1)
x = i” = 23 % 87 = 93 (mod p # 1)
You should check that this produces a valid signature.
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…
Things not to do!
Reveal the random number r
Use the same r twice
Accept values ! & p during verification
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…
Large signatures
A signed message might be functioning as a legal
document e.g. a will
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…
Large signatures
A signed message might be functioning as a legal
document e.g. a will
It is highly likely that we will need to be able to
verify a person signed a message many years after
they did so
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…
Large signatures
A signed message might be functioning as a legal
document e.g. a will
It is highly likely that we will need to be able to
verify a person signed a message many years after
they did so
Conclusion: it is important to take even more
precautions regarding the security of a signature
scheme than a cryptosystem
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…
Timeline
1985: ElGamal signature scheme
1989: Schnorr signature scheme
1991: Digital signature algorithm (DSA) proposed
1994: DSA adopted as a standard
2000: Elliptic curve digital signature scheme
algorithm (ECDSA) approved
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…