Cryptography Reference
In-Depth Information
Exercise 20.5.1
Explain why the person-in-the-middle attack fails for this protocol (assum-
ing the public key authentication process is robust).
Exercise 20.5.2
Consider a key exchange protocol where Alice and Bob have public keys
h
A
=
g
b
, where Alice sends
g
x
and Bob sends
g
y
and where the shared key
is
g
ab
+
xy
. Show that if corrupt queries are allowed then this key exchange protocol does
not provide authentication.
g
a
and
h
B
=
Exercise 20.5.3
Give a person-in-the-middle attack on the Burmester-Desmedt protocol.
20.6 Efficiency considerations for discrete logarithm cryptography
All cryptographic protocols whose security is related to the DLP involve computations of
the form
g
a
at some stage, and this is usually the most demanding computation in terms of
time and computing resources. To make the cryptosystem fast it is natural to try to speed
up exponentiation. One could try working in a smaller group; however, it is important to
ensure that the security of the system is maintained. Indeed, many of the main topics in
this topic (e.g., tori, elliptic curves and hyperelliptic curves) are attempts to get the “most
efficient” group for a given security level.
A number of methods to speed up exponentiation in certain groups have already been
presented. Section
11.1
discussed signed expansions, which are suitable for groups (such
as elliptic and hyperelliptic curves or tori) where inversion is very efficient. Section
11.3
presented Frobenius expansions and the GLV method, which are suitable for elliptic curves.
Those methods all assume that the exponent
a
takes any value.
One can also consider methods that do not correspond to values
a
chosen uniformly at
random. Such methods can be much faster than the general methods already mentioned, but
understanding the security implications can be more complicated. We do not have space to
describe any of these methods in detail, but we briefly mention some of them.
1. Choose
a
to have low Hamming weight. This is mentioned by Agnew, Mullin,
Onyszchuk and Vanstone [
5
] and Schnorr [
470
].
2. Choose
a
to be a random Frobenius expansion of low Hamming weight. This is credited
to H. W. Lenstra Jr. in Section 6 of Koblitz [
312
].
3. Choose
a
to be given by a random addition chain (or addition-subtraction chain). This
is proposed in Section 3.3 of Schroeppel, Orman, O'Malley and Spatscheck [
479
].
4. Choose
a
to be a product of integers of low Hamming weight. This was proposed and
analysed by Hoffstein and Silverman [
262
].
5. Choosing
a
to be a random element in GLV representation, possibly with smaller than
typical coefficients.
6. Generate random elements using large amounts of precomputation. A solution that can be
used in any group is given by Boyko, Peinado and Venkatesan [
91
]. The method requires
precomputing and storing random powers
g
j
=
g
a
j
. One generates a random pair (
a,g
a
)
