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

David Leon Gil coruus at gmail.com
Wed Oct 15 17:46:19 EDT 2014

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.

    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?)

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?

Also, it seems like this would have made an interesting exercise in a
number theory book; is it possible that the observation that you can
choose half the bits in a semiprime by one of the methods in the
papers above described anywhere in that literature?

- David

More information about the cryptography mailing list