Cryptography Reference
In-Depth Information
s := stringposint(seed);
B := RandomTools:-BlumBlumShub:-NewBitGenerator(s, primes = bbslength);
prime := false;
while not prime do
n := convert(cat(1, seq(B(), i=1..length-2), 1), decimal, binary);
prime := MillerRabin(n, numbases)
end do;
n
end proc:
For example, a 1024-bit pseudo-random prime may be generated as follows:
> PseudoRandomPrime(199802651800947252166370807239068579415, 1024);
1560064807313562830819244623667442073204376420914967268320113583088310828660029865\
09464810349927749319945019711144184975891914444423243571809133771203612500967871\
87380732005317859772136401723917438533068081253881172231268304914745877313687757\
3049096319346151670082885140689281246081222876119459701438239776611
Let us now give a similar function to generate pseudo-random safe primes of a
given length. The parameters are the same as those of the previous function and a
safe prime of the required length is produced as output:
> PseudoRandomSafePrime := proc(seed::{posint, string}, length::posint,
{numbases::posint:=20, bbslength::{512, 768, 1024}:=1024})
local s, B, primep, primeq, q, p;
s := stringposint(seed);
B := RandomTools:-BlumBlumShub:-NewBitGenerator(s, primes = bbslength);
primep := false;
while not primep do
primeq := false;
while not primeq do
q := convert(cat(1, seq(B(), i=1..length-3), 1), decimal, binary);
if q mod 3 = 2 then
primeq := MillerRabin(q, numbases)
end if
end do;
p := 2*q+1;
primep := MillerRabin(p, numbases)
end do;
p
end proc:
Example 6.7
Let us generate a 1024-bit safe prime:
> PseudoRandomSafePrime(294779833764425581873162947825807970808, 1024);
1732816592546574774285214526534023654508256643278000043095875918508735298956394485\
45668561472408358613424691500556234745552754121109139057020414242904447393915530\
42650375069251425873018975650987503054441078072814883142442596299751031512182967\
6339640034779641357853974926946295373058442933189109231598423704283
6.4 The Integer Factorization Problem
We have alreadymentioned the integer factorization problemon several occasions. In
Chap.
2
we have seen that the factorization decision problem belongs to the classes
NP
and we have also mentioned that this problem is believed not to
belong to the class
and co
NP
. Later, in Definition 3.15, we have introduced the factoring
assumption, which formalizes the widely believed hypothesis that “factoring is hard”,
P
