Cryptography Reference
In-Depth Information
automatic seeding to generate the safe prime. We use Maple's built-in function
numtheory:-safeprime
which, as we have observed, generates safe primes
in a non-uniform way since the gaps between such primes may have large variations
in size (in fact, it has not even been proved that the set of these primes is infinite
although there are heuristic arguments that suggest this is the case). Again, this is
not a problem because these parameters are going to be public. The function takes as
input a positive integer that specifies the number of bytes of the safe prime (and also
of the Sophie Germain prime) to be generated. Actually, on input
k
, the function will
probably generate an 8
k
-bit safe prime
p
and hence an
(
8
k
−
1
)
-bit Sophie Germain
prime
q
, as well as two generators of
QR
p
. The output is a list of length 3, where
the first element is the Sophie Germain prime
q
and the two remaining elements are
the generators of the group, which are given as integers in the interval
[
2
,
p
−
2
]
,
Z
p
.
> GroupGen := proc(k::posint)
local bitlength, p, q, g1, g2;
uses RandomTools:-MersenneTwister;
SetState();
bitlength := 8*k;
p := numtheory:-safeprime(GenerateInteger(range=2ˆ(bitlength-1)..2ˆbitlength-1));
q := (p-1)/2;
g1 := GenerateInteger(range = 2 .. q)ˆ2 mod p;
g2 := GenerateInteger(range = 2 .. q)ˆ2 mod p;
[q, g1, g2]
end proc:
The function
CSKeyGen
below completes the implementation of the Cramer-
Shoup key generation algorithm. There is only one required input parameter,
seed
,
by means of which a random seed of sufficient length (say, at least 128 bits) is
specified, either as a positive integer or as a hexadecimal string that will be con-
verted to decimal form inside the function. The supplied value serves to seed the
Blum-Blum-Shub PRG that will take care of generating the integers in the inter-
val
i.e., as elements of
. These integers are obtained by generating bit strings of length
equal to the bit length of
q
and discarding them when the integer they define
is
[
0
,
q
−
1
]
q
.
The remaining input parameters are optional keyword parameters. The first of
them,
k
, serves to specify the byte length of the Sophie Germain prime to be gener-
ated, in the way indicated for the preceding function. Its default value is 128 and the
only effect of this parameter is to feed the next parameter,
G
, if no value is passed
to it.
G
is used to specify a group of the form described above (in the format pro-
duced by the function
GroupGen
) and, if not specified, a default value for it will
be generated by invoking
GroupGen
with the value of
k
specified in the previous
parameter. The next parameter
bbslength
is used to specify the bit length of the
primes used by Maple's Blum-Blum-Shub PRG among the three possible ones—
with default value 1024—as we have already done on other similar occasions. The
final keyword parameter
format
is used to specify the format in which the key will
be returned and it can be either
hex
(the default) for the key components to be given
as hexadecimal strings or
decimal
, in which case the key parameters are given as
decimal integers.
≥
