Cryptography Reference
In-Depth Information
Exercise 12.2.3
For certain cryptosystems based on the discrete logarithm problem it is
required to produce a
k
1
-bit prime
p
such that
p
1 has a
k
2
-bit prime factor
q
.Givea
method that takes integers
k
2
<k
1
and outputs
p
and
q
such that
p
is a
k
1
-bit prime,
q
is a
k
2
-bit prime and
q
−
1).
Exercise 12.2.4
For certain cryptosystems based on the discrete logarithm problem (see
Chapter
6
) it is required to produce a
k
1
-bit prime
p
such that
k
(
p
) has a
k
2
-bit prime
factor
q
(where
k
(
x
)isthe
k
th cyclotomic polynomial). Give a method that takes integers
k,k
1
,k
2
such that
k
2
<ϕ
(
k
)
k
1
and outputs
p
and
q
such that
p
is a
k
1
-bit prime,
q
is a
k
2
-bit prime and
q
|
(
p
−
k
(
p
).
Exercise 12.2.5
A
strong prime
is defined to be a prime
p
such that
q
|
=
−
(
p
1)
/
2is
+
−
prime, (
p
1)
/
2 is prime (it is conjectured that infinitely many
such primes exist). Some RSA systems require the RSA moduli to be a product of strong
primes. Give an algorithm to generate strong primes.
1)
/
2 is prime and (
q
12.2.1 Primality certificates
For cryptographic applications it may be required to provide a
primality certificate
.This
is a mathematical proof that can be checked in polynomial-time and that establishes the
primality of a number
n
.Pratt[
440
] showed that there exists a short primality certificate
for every prime. Primality certificates are not so important since the discovery of the AKS
test, but primes together with certificates can be generated (and the certificates verified)
more quickly than using the AKS test, so this subject could still be of interest. We refer to
Section 4.1.3 of Crandall and Pomerance [
150
] and Maurer [
363
] for further details.
One basic tool for primality certificates is Lucas' converse of Fermat's little theorem.
Theorem 12.2.6
(Lucas) Let N
∈ N
. If there is an integer a such that
gcd(
a,N
)
=
1
,
a
N
−
1
1(mod
N
)
and a
(
N
−
1)
/l
≡
≡
1(mod
N
)
for all primes l
|
(
N
−
1)
then N is prime.
Exercise 12.2.7
Prove Theorem
12.2.6
.
In practice, one can weaken the hypothesis of Theorem
12.2.6
.
Theorem 12.2.8
(Pocklington) Suppose N
FRwhere the complete factorisation of
F is known. Suppose there is an integer a such that a
N
−
1
−
1
=
≡
1(mod
N
)
and
a
(
N
−
1)
/q
≡
1(mod
N
)
for every prime q
|
F. Then every prime factor of N is congruent to 1 modulo F. Hence, if
≥
√
N then N is prime.
F
Exercise 12.2.9
Prove Theorem
12.2.8
.
Exercise 12.2.10
A
Sophie Germain prime
(in cryptography the name
safe prime
is
commonly used) is a prime
p
such that (
p
1)
/
2 is also prime. It is conjectured that
there are infinitely many Sophie Germain primes. Give a method to generate a
k
-bit Sophie
Germain prime together with a certificate of primality, such that the output is close to
uniform over the set of all
k
-bit Sophie Germain primes.
−
