Cryptography Reference
In-Depth Information
The differences with the previous function are just two. On the one hand, we will
now use Maple's
isprime
as primality test (instead of
MillerRabin
) in order
to make the function a little faster. The other change is that now there is an optional
input parameter
min
that, when looking for a
k
-bit prime, can be used to specify a
'minimum value' for the prime to be found, so that the function looks for primes in
the interval of length 2
k
−
1
whose initial point is this minimum value. The default
value for the
min
parameter is 2
k
−
1
so that, if no value is passed to this parameter,
then the function just looks for a
k
-bit prime. If the value
m
of
min
is greater than
2
k
−
1
, then the function looks for a prime in the interval
2
k
−
1
[
m
,
m
+
−
1
]
(so that
the prime obtained may actually have
k
1 bits in some cases). The remaining
optional input parameter
bbslength
is used to set the length of the primes used
by Blum-Blum-Shub as we have done on other similar occasions.
> RSAPrime := proc(k::posint, seed::posint,
min:=2ˆ(k-1), bbslength::{512, 768, 1024}:=1024)
local B, prime, gap, p;
B := RandomTools:-BlumBlumShub:-NewBitGenerator(seed, primes = bbslength);
prime := false;
gap := min-2ˆ(k-1);
if gap mod 2 = 1 then
gap := gap + 1
end if;
while not prime do
p := gap + convert(cat(1, seq(B(), i=1..k-2), 1), decimal, binary);
prime := isprime(p)
end do;
p
end proc:
We are now ready to give the RSA key generation function,
RSAKeyGen
.The
required input parameters are
k
,
seed1
and
seed2
. The first is used to specify that
the modulus of the key should be a 2
k
-bit number and the remaining two to provide
two random seeds in the form of hexadecimal strings of no less than 128 bits (or the
corresponding integer) that will be used by Blum-Blum-Shub. Then the function
uses
RSAPrime
to find the primes
p
,
q
such that the RSA modulus is
n
+
pq
.For
convenience of use we have also provided the function with automatic seeding, so
that it will generate a key even if no seeds are passed as arguments. But we warn
that this solution produces highly insecure keys and is given only for demonstration
purposes. In this case, the seeds are provided by Mersenne Twister in the form of
integers in the range 0
=
2
256
and, of course, they are not random because they have
been generated from a 32-bit seed obtained from the system. Hence the keys thus
generated would be vulnerable to a brute-force attack capable of doing a 2
32
-size
search.
Bearing in mind these remarks we insist that the Blum-Blum-Shub PRG that
finally generates the primes should be provided with random seeds of sufficient size
through the parameters
seed1
and
seed2
. The remaining optional parameters are
two keyword parameters,
e
and
format
. The parameter
e
is used to specify the
desired encryption exponent and takes as default the value 2
16
..
1 for the reasons
explained in the preceding paragraphs. The parameter
format
, on the other hand,
is used to specify the way in which the key will be represented and it takes as value
a name that can be either
'hex'
or
'decimal'
, with the former as default.
+
