Cryptography Reference
In-Depth Information
When
k
is specified as security parameter, the function first searches for a
k
-bit
prime which is pseudo-randomly chosen by the Blum-Blum-Shub bit generator.
When a
k
-bit prime
p
is found, the function checks whether the condition gcd
(
p
−
1
1 is satisfied for the value of the encryption exponent chosen and if this is
not the case, the prime is discarded and the seed value increased in order to search
for a new prime. When
e
is small, as happens, for example, in the case
e
,
e
)
=
3, this
procedure is not optimal from a performance point of view and it would be preferable
to discard the integers that do not satisfy the gcd condition before submitting them to
the primality test but with larger exponents such as the default 2
16
=
1 it is unlikely
that a prime chosen this way does not satisfy this condition. Once the first prime
p
is
chosen, the second prime
q
is chosen in a similar way, with the difference that now
the search interval is
+
2
k
−
1
2
2
k
−
1
. Thus both primes
are pseudo-randomly chosen from intervals of length 2
k
−
1
and the modulus obtained
by multiplying them is a 2
k
-bit number.
The output is an RSA key in the form of a list containing two sublists. The first
sublist is the public key
[
m
,
m
+
−
1
]
, where
m
=
/
p
and the second sublist contains the private key. The
first two terms of this sublist are the modulus and the decryption exponent, and they
are followed in order by the primes
p
,
q
, the values
d
p
(
n
,
e
)
=
d
mod
(
p
−
1
)
and
d
q
that will be used to speed up decryption by means of the
Chinese remainder theorem and, finally, the values of
p
−
1
mod
q
and
q
−
1
mod
p
.
Note that there is a lot of redundant information in the private key but we include
it in order to facilitate experimentation. For example, the first two components of
the private key suffice to decrypt but do not allow the use of the Chinese remainder
theorem. To use it for decryption the items in positions 3-6 in the private key list will
be required. The last two items may also optionally be used to compute the plaintext
using the Chinese remainder theorem in the form described in Eq.
8.1
.
=
d
mod
(
q
−
1
)
> RSAKeyGen := proc(k::posint, seed1::{posint,string}, seed2::{posint, string},
{e::posint:=2ˆ16+1, format::name:=hex, bbslength::{512,768,1024}:=1024})
uses RandomTools:-MersenneTwister;
local s, g, p, q, m, n, d, key;
if _ params['seed1'] = NULL then
SetState();
s := GenerateInteger(':-range' = 2ˆ127 .. 2ˆ256)
else
s := stringposint(seed1)
end if;
g:=0;
while g <> 1 do
p := RSAPrime(k, s, ':-bbslength' = bbslength);
s:=s+16;
g := igcd(p-1, e)
end do;
m := ceil(2ˆ(2*k-1)/p);
if _ params['seed2'] = NULL then
SetState();
s := GenerateInteger(':-range' = 2ˆ127 .. 2ˆ256)
else
s := stringposint(seed2)
end if;
g:=0;
while g <> 1 do
q := RSAPrime(k, s, min = m, ':-bbslength' = bbslength);
s:=s+16;
