Cryptography Reference
In-Depth Information
its authenticity can be verified. This can be achieved, for example, by the public
keys being digitally signed by the participants and the associated certificate
of a certification authority being sent with them (see in this regard page 400,
Section 17.3), which is implemented, for example, in the SSL protocol. IPSec and
IPv6 use a complexly constructed procedure with the name ISAKMP/Oakley,
5
which overcomes all the drawbacks of the Diffie-Hellman protocol (for details see
[Stal], pages 422-423).
To determine a primitive root modulo
p
,thatis,avalue
a
whose powers
a
i
mod
p
with
i
=0
,
1
,...,p−
2
constitute the entire set of elements of the
multiplicative group
Z
p
=
{
1
,...,p−
1
}
(see in this regard Section10.2), the
following algorithm can be used (see [Knut], Section 3.2.1.2, Theorem C). It is
assumed that the prime factorization
p
1=
P
e
1
1
p
e
k
Z
p
is
−
···
of the order of
known.
Finding a primitive root modulo
p
1.
Choose a random integer
a
∈
[0
,p
−
1]
and set
i
←
1
.
2.
Compute
t ← a
(
p
−
1)
/p
i
mod
p
.
3.
If
t
=1
, go to step 1. Otherwise, set
i ← i
+1
.If
i ≤ k
, go to step 2. If
i>k
,
output
a
and terminate the algorithm.
The algorithm is implemented in the following function.
ad hoc generation of a primitive root modulo
p
(
2
<p
prime)
Function:
int primroot_l (CLINT a_l, unsigned noofprimes,
clint **primes_l);
Syntax:
noofprimes
(number of distinct prime factors in
p −
1
,
the order of the group)
primes_l
(vector of pointers to
CLINT
objects, beginning with
p −
1
, then follow the prime divisors
p
1
,...,p
k
of the
group order
p
Input:
1=
p
e
1
p
e
k
−
···
,
k
=
noofprimes
)
a_l
(primitive root modulo
p_l
)
Output:
Return:
E_CLINT_OK
if all is ok
−
1
if
p −
1
odd and thus
p
is not prime
5
ISAKMP: Internet Security Association and Key Management Protocol.
