Cryptography Reference
In-Depth Information
The PKCS specifications further suggest a mask generation function MGF1 which
is based on a hash function. The MGF1
(
x
) string simply consists of the
leading
bytes of
H
(
x
||
00000000)
||
H
(
x
||
00000001)
||
H
(
x
||
00000002)
||···
in which
x
is concatenated to a four-byte counter.
The security proof of RSA-OAEP is far beyond the scope of these lecture notes.
We simply mention that it exists with the strongest security notion that we have seen,
i.e. IND-CCA, and that its significance was subject to a highly technical controversy.
9
9.4
ElGamal Encryption
Taher ElGamal initiated a famous family of digital signature schemes which will be dis-
cussed in Chapter 10 (see Refs. [63-65]). He also defined a nondeterministic encryption
scheme based on the discrete logarithm problem. Here is how it works.
Public parameter
: a large prime
p
, a generator
g
of
Z
p
.
Setup
: generate a random
x
g
x
∈
Z
p
−
1
, and compute
y
=
mod
p
.
Z
p
.
Message
: an element
m
∈
Public key
:
K
p
=
y
.
Secret key
:
K
s
=
x
.
Encryption
: pick a random
r
g
r
my
r
∈
Z
p
−
1
, compute
u
=
mod
p
and
v
=
mod
,v
).
Decryption
: Extract the
u
and
p
. The ciphertext is (
u
v
=
parts of the ciphertext and compute
m
v
u
−
x
mod
p
.
(See Fig. 9.11.) Obviously, the correct encryption followed by a correct decryption
recovers the correct message.
One benefit of this scheme is that a single prime number can be used for all users.
Hence key setup, encryption, and decryption take
(
s
3
) time where
s
O
=
log
p
. The
drawback is that the ciphertext size is twice the plaintext size.
For security analysis we distinguish the decryption problem from the key recovery
problem, as for the RSA cryptosystem.
EGDP (ElGamal Decryption Problem)
Parameters
: a prime number
p
and a generator
g
of
Z
p
Input
: a ciphertext (
u
,v
) and a public key
y
9
See Refs. [25, 26, 71, 169]. A nice survey is available in Ref. [120].
Search WWH ::
Custom Search