CS计算机代考程序代写 scheme algorithm CM30173: Cryptography\reserved@d =[@let@token art IV

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…