Cryptography Reference
In-Depth Information
9.4.3 DSA in Maple
We now give aMaple implementation of DSA following the guidelines in [75]. There
are too many details in this standard to implement them all but we shall try to give a
reasonable approximation to the algorithm. We start with a function that generates
the system parameters (or 'domain parameters', as they are called in [75]). They are
contained in the triple
—in the notation of Sect.
9.4.1
—which describes the
group in which the algorithm operates, so this function will play a role similar to the
one played by the function
GroupGen
we used when implementing the Cramer-
may subsequently be shared by many users who only have to generate their keys
by means of another function which is much less computing-intensive. In [75] two
additional domain parameters are considered which contain the seed and the counter
used to generate
p
and
q
. These parameters are only used for validation of the primes
p
and
q
, and they allow another party to check that
p
and
q
were obtained by amethod
specified in the standard. However, these parameters are optional and we will not
include them as inputs in our functions.
The main input for the function that generates the domain parameters is the pair
(
p
,
q
,
g
)
(
described in Sect.
9.4.1
, which specifies the bit lengths of the primes
p
and
q
,
respectively. This pair must be one of the four approved pairs in the standard but we
will only allow the last two, which provide greater security strength. Following the
recommendations in [75], the hash function to be used should have an output length
of at least 256 bits in our case, and we will use SHA-256—which was implemented
in Sect.
5.6.3
—for this purpose.
Another required input for the group generating function in [75] is the length
of the seed, which is required to be
L
,
N
)
N
. We shall take this length to be equal to
N
, so this input parameter will not be necessary. The seed itself will be pseudo-
randomly generated inside the procedure as a hexadecimal string of hexadecimal
length
N
≥
4 and we will use one of Maple's built-in pseudo-random algorithms to do
the job, without caring much about its cryptographic strength because the generated
parameters are going to be public. The function that generates the domain parameters
is the following:
> DSADomainGen := proc(L::{2048, 3072}:= 2048, N::{256}:= 256, {H::name:='SHA256',
outlen::posint:= 256, format::identical(hex, decimal):= hex})
local prime, found, seed, n, b, U, q, offset, counter, W, j, V, X, c, p, e, t, g;
prime := false;
found := false;
while not found do
while not prime do
StringTools:-Randomize();
seed := StringTools:-Random(N/4, xdigit);
n := ceil(L/outlen)-1;
b := L-1-n*outlen;
U := OS2IP(H(seed, hex)) mod 2ˆ(N-1);
q := 2ˆ(N-1)+U+1-(U mod 2);
prime := isprime(q)
end do;
offset := 1;
prime := false;
for counter from 0 to 4*L-1 while not prime do
/
