Cryptography Reference
In-Depth Information
Therefore, the input parameter
k
, which corresponds to the security parameter in the
algorithm, is used to specify the number of bytes (instead of bits). Thus this function
generates two
(
4
k
+
1
)
-bit Blum primes whose product is a
(
8
k
+
2
)
-bit modulus as
specified in [34]. First, a
-Blum prime is generated and then the second prime
is searched for in the subinterval consisting of the integers that multiplied by the first
selected prime give an
(
4
k
+
1
)
(
8
k
+
2
)
-bit modulus whose two most significant bits are '10'.
This is done by generating
-bit integers by means of Blum-Blum-Shub and
discarding those that fall outside this subinterval.
The required input parameters are, in addition to
k
,
seed1
and
seed2
, which
serve to specify the random seeds that the BBS PRG will use to search for each of
the two primes (the seeds can be given either as positive integers or as hexadecimal
strings). There is, furthermore, an optional keyword parameter
format
to spec-
ify the format in which the keys will be given. This format can be either
hex
(for
hexadecimal, which is the default) or
decimal
. As on other similar occasions we
allow, for demonstration purposes only, the generation of keys without explicitly
supplying seeds to the function, in which case they will be pseudo-randomly gener-
ated with smaller seeds taken by Maple from the system. We stress, again, that this
method is insecure and that, for proper use, externally generated random seeds of
sufficient length should be supplied to the function.
The output of the function is a list whose first element is the modulus, i.e., the
public key, and whose second element is the private key given as another list. Thus
the output format is
(
4
k
+
1
)
[
n
,
[
p
,
q
,
pinv
,
qinv
]]
, where
p
and
q
are
(
4
k
+
1
)
-bit Blum
=
(
+
)
primes, and
n
-bit integer.
pinv
and
qinv
are, respectively, the
inverse of
p
modulo
q
and the inverse of
q
modulo
p
, which may be used to speed
up decryption by means of the Chinese remainder theorem.
> RabinKeyGen := proc(k::posint, seed1::{posint, string}, seed2::{posint, string},
{format::name := hex, bbslength::{512, 768, 1024}:=1024})
local pLen, s, p, q, min, max, key;
pLen := 4*k+1;
if _params['seed1'] = NULL then
RandomTools:-MersenneTwister:-SetState();
s := RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 2ˆ127 .. 2ˆ256)
else
s:=stringposint(seed1)
end if;
p := BlumPrime(pLen, s, ':-bbslength' = bbslength);
min := ceil(2ˆ(8*k+1)/p);
max := floor(3*2ˆ(8*k)/p);
if _params['seed2'] = NULL then
RandomTools:-MersenneTwister:-SetState();
s := RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 2ˆ127 .. 2ˆ256)
else
s := stringposint(seed2)
end if;
q := BlumPrime(pLen, s, ':-min' = min, ':-max' = max, ':-bbslength' = bbslength);
igcdex(p, q, 'pinv', 'qinv');
key := [p*q, [p, q, pinv mod q, qinv mod p]];
if format = decimal then
key
elif format = hex then
StringTools:-LowerCase
∼∼
(convert
∼∼
(key, hex))
else
error "Unrecognized key format"
end if
end proc:
pq
is an
8
k
2
