Cryptography Reference
In-Depth Information
KeyGen
(
κ
): Run a parameter generation algorithm on security parameter
κ
that outputs an
algebraic group
G
over a finite field
F
q
) has a prime divisor
r
and all known
algorithms for the discrete logarithm problem in a subgroup of
G
(
F
q
)oforder
r
require at least
2
κ
bit operations.
F
q
such that #
G
(
Compute
g
∈
G
of prime order
r
.
Choose a random integer 0
<a<r
and set
h
=
g
a
. The public key is (
G,g,h
) and the private
key is
a
.
The message space is
M
κ
=
G
.
The ciphertext space is
C
κ
=
G
×
G
.
Encrypt
(
m
): (where
m
∈
G
).
Obtain the public key
h
of the recipient, Alice.
Choose a random 0
<k<r
and set
c
1
=
g
k
.
m
h
k
.
Transmit the ciphertext (
c
1
,
c
2
).
Set
c
2
=
Decrypt
(
c
1
,
c
2
): Check that
c
1
,
c
2
∈
G
. If so, compute and output
=
c
2
c
−
1
.
m
Box 20.1
Classic textbook Elgamal encryption
KeyGen
(
κ
): Generate an algebraic group or algebraic group quotient
G
as in Box
20.1
. Choose
a random
g
∈
G
of prime order
r
.
Choose a message size
l
and a cryptographic hash function
H
:
G
→{
0
,
1
}
l
.
Choose a random integer 0
<a<r
and set
h
=
g
a
. The public key is (
G,H,g,h
) and the
private key is
a
.
The message space is
M
κ
={
0
,
1
}
l
.
The ciphertext space is
C
κ
=
G
×{
0
,
1
}
l
.
l
).
Obtain the public key of the recipient, Alice.
Choose a random 0
<k<r
and set
c
1
=
g
k
.
Set
c
2
=
m
⊕
H
(
h
k
).
Transmit the ciphertext (
c
1
,
c
2
).
Encrypt
(
m
): (where
m
∈{
0
,
1
}
Decrypt
(
c
1
,
c
2
): Check that
c
1
∈
G
and
c
2
∈{
0
,
1
}
l
. If so, compute and output
=
c
2
⊕
H
(
c
1
)
.
m
Box 20.2
Semi-textbook Elgamal encryption
