Public-Key Encryption - Introduction to Cryptography with Maple - page 484

probably of a psychological nature and due to the fact that plain Rabin encryption is
so completely vulnerable to a CCA attack—which, of course, is completely irrelevant
for the Rabin-SAEP + scheme.

8.4.4 Rabin-SAEP + in Maple

The implementation of Rabin-SAEP + that follows makes use of many of the aux-
iliary functions that were used in the RSAES-OAEP implementation given in 8.3.7 .
We will use them without further comment and here we describe only the new func-
tions, starting with those required by the key generation algorithm. The next function
generates a Blumprime of specified bit length and is a minor variation on the function
we used to generate pseudo-random primes for RSA keys. The input parameters are
length , which serves to specify the bit length of the prime to be generated, and
seed , which requires a random seed given as a positive integer; as usual, care must
be taken that the seed is chosen uniformly at random from a set of strings of sufficient
length (at least 128-bit—or 16-byte—strings). There are three additional keyword
parameters. The first two of them, min , max serve to specify a minimum and a max-
imum value such that 2 length − 1 2 length and the default values

for them are, respectively 2 length − 1 and 2 length . Thus if the function is run with
default values it merely picks a Blum prime of the specified length , but if different
values for min and max are specified then it selects a prime in the subinterval [min ,
max] , which is useful if one wants to generate primes whose product is a modulus
of specified length. There is another optional keyword parameter, bbslength , that
serves to specify the bit length of the primes used by the Blum-Blum-Shub PRG,
which takes care of generating the prime candidates. The output is a probable Blum
prime in the interval [min , max] .
> BlumPrime := proc(length::posint, seed::posint,
{min := 2ˆ(length-1), max:=2ˆlength, bbslength::{512, 768, 1024}:=1024})
local B, prime, p, rightsize;
B := RandomTools:-BlumBlumShub:-NewBitGenerator(seed, primes = bbslength);
prime := false;
while not prime do
rightsize := false;
while not rightsize do
p := convert(cat(1, seq(B(), i=1..length-3), 1, 1), decimal, binary);
rightsize := evalb(min < p and p < max)
end do;
prime := isprime(p)
end do;
p
end proc:
In the function BlumPrime we ensure that the prime candidates are

≤ min < max ≤

)
by setting the two low order bits equal to 1. In a similar way, we could make the
function more efficient by adequately choosing some of the high order bits whenever
min is relatively large or max is relatively small. But we shall use this simple version,
which is sufficient for our purposes.
The next function implements the key generation algorithm for Rabin-SAEP + .We
follow the description in [34] but, as usual, the implementation will be byte-oriented.

≡ 3 ( mod 4