[Cryptography] RFC: Generating RSA moduli / semiprimes with predetermined bits

Samuel Neves sneves at dei.uc.pt
Wed Oct 15 20:50:42 EDT 2014

On 10/15/2014 10:46 PM, David Leon Gil wrote:
> Request for citations!
> Does anyone happen to know early references for the generation of
> semiprimes with prescribed bit-patterns?
> In particular, I know of the following articles:
>     Vanstone, Scott A., and Robert J. Zuccherato. "Short RSA keys and
> their generation." Journal of Cryptology 8, no. 2 (1995): 101-114.

[1] points out that [2, Section 2.1] predates Vanstone and Zuccherato, invalidating their 1994 patent on the technique.

[1] http://cr.yp.to/papers/sigs.pdf
[2] http://link.springer.com/chapter/10.1007%2F3-540-46877-3_42

>     Lenstra, Arjen K. "Generating RSA moduli with a predetermined
> portion." In Advances in Cryptology—Asiacrypt’98, pp. 1-10. Springer
> Berlin Heidelberg, 1998.
>     Young, Adam, and Moti Yung. "The Dark Side of “Black-Box”
> Cryptography or: Should We Trust Capstone?." In Advances in
> Cryptology—CRYPTO’96, pp. 89-103. Springer Berlin Heidelberg, 1996.
>     Desmedt, Yvo. "Abuses in cryptography and how to fight them." In
> Proceedings on Advances in cryptology, pp. 375-389. Springer-Verlag
> New York, Inc., 1990.
> Young and Yung cite Yvo Desmedt as having introduced the idea for RSA
> moduli in particular. (I don't have this conference proceeding to
> verify the citation; can anyone verify this?)

The article is freely available here, as far as I can tell:

Section 3.1 does mention that "Another method for leaking information is to choose p and q such that the least
significant bits of n have a special form not required by the specifications".

> There are also some works by GJ Simmons (e.g., "The subliminal channel
> and digital signatures") from 1984-85 that seem apropos; does anyone
> know if this is discussed there?

This one is also available here: http://link.springer.com/chapter/10.1007%2F3-540-39757-4_25. As far as I can tell,
there is no mention of generating special semiprimes; the subliminal channel are the signatures themselves, not the modulus.

More information about the cryptography mailing list