Cryptography Reference
In-Depth Information
8.5.
Compute the two public keys and the common key for the DHKE scheme with
the parameters
p
= 467,
α
= 2, and
1.
a
= 3,
b
= 5
2.
a
= 400,
b
= 134
3.
a
= 228,
b
= 57
In all cases, perform the computation of the common key for Alice
and
Bob. This is
also a perfect check of your results.
8.6.
We now design another DHKE scheme with the same prime
p
= 467 as in
Problem 8.5. This time, however, we use the element
= 4. The element 4 has
order 233 and generates thus a subgroup with 233 elements. Compute
k
AB
for
1.
a
= 400,
b
= 134
2.
a
= 167,
b
= 134
α
Why are the session keys identical?
8.7.
In the DHKE protocol, the private keys are chosen from the set
{
2
,...,
p
−
2
}
.
Why are the values 1 and
p
−
1 excluded? Describe the weakness of these two
values.
8.8.
Given is a DHKE algorithm. The modulus
p
has 1024 bit and
α
is a generator
2
160
.
1. What is the maximum value that the private keys should have?
2. How long does the computation of the session key take on average if one modular
multiplication takes 700
of a subgroup where ord(
α
)
≈
μ
s, and one modular squaring 400
μ
s? Assume that the
public keys have already been computed.
3. One well-known acceleration technique for discrete logarithm systems uses short
primitive elements. We assume now that
is such a short element (e.g., a 16-bit
integer). Assume that modular multiplication with
α
s. How
long does the computation of the public key take now? Why is the time for one
modular squaring still the same as above if we apply the square-and-multiply
algorithm?
α
takes now only 30
μ
8.9.
We now want to consider the importance of the proper choice of generators in
multiplicative groups.
1. Show that the order of an element
a
∈
Z
p
with
a
=
p
−
1 is always 2.
2. What subgroup is generated by
a
?
3. Briefly describe a simple attack on the DHKE which exploits this property.
8.10.
We consider a DHKE protocol over a Galois fields
GF
(2
m
). All arithmetic
is done in
GF
(2
5
) with
P
(
x
)=
x
5
+
x
2
+ 1 as an irreducible field polynomial. The
primitive element for the Diffie-Hellman scheme is
=
x
2
. The private keys are
α
a
= 3 and
b
= 12. What is the session key
k
AB
?
