Cryptography Reference
In-Depth Information
where 1
≤
j
≤
n
. Assume that the last cleartext
x
n
is known to Oscar and all cipher-
text.
Provide a formula with which Oscar can compute any of the messages
x
j
,1
≤
1. Of course, following Kerckhoffs' principle, Oscar knows the construction
method shown above, including the function
f
().
j
≤
n
−
8.16.
Given an Elgamal encryption scheme with public parameters
k
pub
=(
p
,
)
and an unknown private key
k
pr
=
d
. Due to an erroneous implementation of the
random number generator of the encrypting party, the following relation holds for
two temporary keys:
α
,
β
k
M
,
j
+1
=
k
2
M
,
j
mod
p
.
Given
n
consecutive ciphertexts
(
k
E
1
,
y
1
)
,
(
k
E
2
,
y
2
)
, ...,
(
k
E
n
,
y
n
)
to the plaintexts
x
1
,
x
2
, ...,
x
n
.
Furthermore, the first plaintext
x
1
is known (e.g., header information).
1. Describe how an attacker can compute the plaintexts
x
1
,
x
2
, ...,
x
n
from the given
quantities.
2. Can an attacker compute the private key
d
from the given information? Give
reasons for your answer.
8.17.
Considering the four examples from Problem 8.13, we see that the Elgamal
scheme is nondeterministic: A given plaintext
x
has many valid ciphertexts, e.g.,
both
x
= 33 and
x
= 248 have the same ciphertext in the problem above.
1. Why is the Elgamal signature scheme nondeterministic?
2. How many valid ciphertexts exist for each message
x
(general expression)?
How many are there for the system in Problem 8.13 (numerical answer)?
3. Is the RSA crypto system nondeterministic once the public key has been chosen?
8.18.
We investigate the weaknesses that arise in Elgamal encryption if a public key
of small order is used. We look at the following example. Assume Bob uses the
group
Z
29
with the primitive element
α
= 2. His public key is
β
= 28.
1. What is the order of the public key?
2. Which masking keys
k
M
are possible?
3. Alice encrypts a text message. Every character is encoded according to the simple
rule
a
→
0,
...
,
z
→
25. There are three additional ciphertext symbols:
a
→
26,
o
→
27,
u
→
28. She transmits the following 11 ciphertexts (
k
E
,
y
):
