D. J. Bernstein
US patent 8218760, Joye, compressed RSA keys
Text of the patent
No reported enforcement attempts.
Priority date 2007.02.27.
"The general inventive idea consists in fixing a large part of an RSA modulus N
(e.g., up to its top half in the preferred embodiment)
so that the primes forming N can be drawn arbitrarily from an interval
(and not tried incrementally as was suggested in previous proposals)."
1998 Lenstra "Generating RSA moduli with a predetermined portion":
"If L-|p| is chosen larger,
then q can be chosen at random from among the primes in a much wider range".
2000 Bernstein "A secure public-key signature system with extremely fast verification":
"Generate a uniform random number p between 4 2^765 and 5 2^765
satisfying p mod 40 = 3; repeat until p is prime.
Generate a uniform random number q between ceil(2^800 pibar/p)
and ceil(2^800(pibar+1)/p) satisfying q mod 40 = 7;
repeat until q is prime."
2003 Bernstein "Compressing RSA keys and signatures":
"Reduce keys to 800 bits with fast key generation;
or 768 bits with fairly fast key generation".