Cryptography Reference
In-Depth Information
For example, testing the parameters
dparams
generated above gives:
> DSADomainTest(dparams, 2048, 256);
Valid parameters
Exercise 9.9
Write a variant of the function
DSADomainGen
that additionally out-
puts the seed and the counter values, and a function to validate the primes generated
by this variant using the method indicated in [75, A.1.1.3].
Exercise 9.10
Write a variant of
DSADomainGen
that generates the generator
g
by the verifiable method described in [75, A.2.3]. Write a function that validates the
generators thus obtained following the method described in [75, A.2.4].
Exercise 9.11
Write a function
DSAKeyTest
which, on input a key pair
and
a valid list of domain parameters, checks whether the key pair is valid for the given
domain (the function should check that both parameters are in the appropriate ranges
and also that
g
x
[
x
,
y
]
≡
y
(
mod
p
)
). Use this function to check the previously generated
key pair
dsakey
.
We are now ready to give the functions that implement the signing algorithm and
the verification algorithm. For the first, it is necessary to generate an ephemeral key
k
(or 'per-message secret number' in the terminology of [75]). This number is, as we
have seen in our description of DSA, of the utmost importance for the security of the
scheme and hence it should either be randomly chosen or, at least, a strong PRGwith a
random seed of sufficient length should be used. We shall use the Blum-Blum-Shub
PRG as usual and the function is very similar to the key-generating function, having
the same input parameters with the exception of
format
, which is not necessary in
this case because the function will only be used inside the signing function and its
output will be in decimal format. The output is a list
[
k
,
invk
]
containing the secret
number and its inverse modulo the prime
q
.
> DSASecretGen := proc(domain::list, seed::{posint, string},
{bbslength::{512, 768, 1024} := 1024})
local d, p, q, g, s, B, L, N, c, k, invk;
d := stringposint
∼
(domain);
p := d[1];
q := d[2];
g := d[3];
L := intlog[2](p)+1;
N := intlog[2](q)+1;
if L <> 2048 and L <> 3072 or N <> 256 then
error "(L,N) pair not supported"
end if;
s := stringposint(seed);
B := RandomTools:-BlumBlumShub:-NewBitGenerator(s, primes = bbslength);
c := q-1;
while q-2 < c do
c := convert(cat(seq(B(), i=1..N)), decimal, binary)
end do;
k := c+1;
invk := kˆ(-1) mod q;
[k, invk]
end proc:
The next function implements the DSA signing algorithm. The required input
parameters are
domain
, used to specify the list of domain parameters,
