Cryptography Reference
In-Depth Information
selects a random integer
k
such that 1
2 (it is very important that the sender choose
a different random value for each message); then she computes the two values
c
g
k
(mod
p
)
≤
k
≤
p
(0
≤
c
<
p
)
P
(
g
a
)
k
(mod
p
) (0
≤
d
<
p
).
The ciphertext to send is the pair of values
c
and
d
; that is,
d
Pr
k
C
= (
c
,
d
).
The intended recipient decrypts
C
by using the private key
a
to first compute the lnr
z
of
an inverse of
c
a
modulo
p
; that is,
(
c
a
)
z
(mod
p
)
(0
≤
z
<
p
).
He then recovers the plaintext
P
by computing
P
zd
(mod
p
) (0
≤
P
<
p
).
Why does this last computation recover the plaintext? If one references how each quan-
tity was created, it becomes obvious:
zd
(
c
a
)
P r
k
((
g
k
)
a
)
P
(
g
a
)
k
(
g
ak
)
g
ak
P
P
(mod
p
).
E
XAMPLE
.
We will now demonstrate ElGamal using very small numbers. The intended
recipient first chooses a prime
p
= 2357, and
g
= 2, a generator modulo 2357. She then
chooses a random integer
a
= 2001 which will serve as the private key. She then computes
2
2001
(mod 2357).
r
= 2034
She makes public the values of
p
,
g
, and
r
.
Suppose now someone wishes to send the message (regarded as an integer)
P
= 1622
to the aforementioned recipient. She must first generate a random integer
k
= 835 then com-
pute the two values
c
= 731
2
835
(mod 2357)
d
= 1326
1622
2034
835
(mod 2357)
She then sends these 2 values; the ciphertext is
C
= (731, 1326)
To decrypt, the recipient must first find an inverse of
c
a
modulo
p
; that is,
z
= 794
1980
(731
2001
)
(mod 2357).
She then retrieves the plaintext by computing the lnr of
zd
modulo
p
.
P
= 1622
794
1326 (mod 2357).
Search WWH ::
Custom Search