Cryptography Reference
In-Depth Information
The output is a list of length two whose elements are also lists. The first of
them contains the public key in the form
[
,
,
,
,
,
]
, where
q
is the Sophie
Germain prime that defines the group of order
q
,
g
1
and
g
2
are generators of the
group and
c
,
d
,
h
are the elements mentioned—with this same notation—in the
description of the key generation algorithm. Note that we do not include the hash
function
H
in the public key because it will be regarded as a system parameter
but we include
q
, which is also a system parameter, for convenience. The second
element is the private key in the form
q
g
1
g
2
c
d
h
where
q
is, again, the
Sophie Germain prime defining the group and the remaining elements are pseudo-
randomly chosen elements of
[
q
,
x
1
,
x
2
,
y
1
,
y
2
,
z
]
Z
q
whose role was explained in the description of the
scheme.
> CSKeyGen:=proc(seed::{posint, string}, {k::posint:=128, G::list:=GroupGen(k),
bbslength::{512, 768, 1024}:=1024, format::name:=hex})
local q, g1, g2, p, qbitLen, s, B, sk, j, x, pk, c, d, h;
q := G[1];
g1 := G[2];
g2 := G[3];
p := 2*q+1;
qbitLen := intlog[2](q)+1;
s := stringposint(seed);
B := RandomTools:-BlumBlumShub:-NewBitGenerator(s, primes = bbslength);
sk := [q];
forjto5do
x:=q;
while q <= x do
x := convert(cat(seq(B(), i=1..qbitLen)), decimal, binary)
end do;
sk := [op(sk), x]
end do;
c := (Power(g1, sk[2]) mod p)*(Power(g2, sk[3]) mod p) mod p;
d := (Power(g1, sk[4]) mod p)*(Power(g2, sk[5]) mod p) mod p;
h := Power(g1, sk[6]) mod p;
pk := [q, g1, g2, c, d, h];
if format = decimal then
[pk, sk]
elif format = hex then
StringTools:-LowerCase
∼∼
(convert
∼∼
([pk, sk], hex))
else
error "Unrecognized key format"
end if
end proc:
Example 8.17
Let us generate a Cramer-Shoup key using a 16-byte (128-bit)
seed. We can do it in one step by executing, for example, a command such as
CSKeyGen(seed);
where only the seed is specified. But we can also do it in
two steps by first generating the system-wide parameters
q
,
g
1
,
g
2
(i.e., the prime
q
that specifies the group and the two generators
g
1
,
g
2
) and then calling
CSKeyGen
with an appropriate seed. Using the latter method we start by calling
GroupGen
with
k = 128
, which will likely generate a 1023-bit Sophie Germain prime
q
(and
hence a 1024-bit safe prime);
q
is the first element in the output list and the remaining
two elements are the generators: