Generating OpenPGP key pair with restrictions

Question

I intend to generate an OpenPGP RSA key pair where a part (~half) of the private key is as I specify, i.e. a specific string. Are there tools for generating a key pair with such restrictions, or will I have to investigate the protocol?

Despite some cryptographical limitations, such a strategy could be used to hide keys in plain sight.

Answer 1

You have to define with some precision what you mean by "RSA private key".

In RSA, there is a modulus, i.e. a big integer n which is equal to the product of two equal-sized prime integers called p and q. Also, there is a public exponent e (usually small, traditionally equal to 65537 in the context of PGP) and a corresponding private exponent d. The size of d is roughly the same than the size of n; d is such that e*d = 1 when taken modulo either p-1 or q-1.

The public key consists in n and e. The public key operation involves elevating an integer to the power e modulo n. The private key is anything which allows the computation of the inverse operation (finding the e-th root modulo n). The following sets of information all allow extracting e-th roots, and thus all of them can be deemed "the private key":

• n and d
• p, q and d
• p, q, d mod p-1, d mod q-1
• p, q and e

So you have to decide what you define as "RSA private key" and what "half" you are talking about.

Let's see what OpenPGP defines. In section 5.5.3, we see that there is a standard storage format for RSA private keys, within the context of OpenPGP. That format stores the public key (n and e), and also d, p, q and a value called u, which is the inverse of p modulo q (this value helps in implementing RSA efficiently; it could be recomputed on the spot, but storing it yields faster operations). Actually p, q and e are all that can be set, since the other values can be deterministically computed from those three. And e is traditionally set, and should anyway remain small (for efficiency and interoperability). So you have p and q to "hide" your preset value.

RSA key generation roughly work like this:

• Generate a random integer p of the right size (half the target modulus size).
• Test if p is prime. If not, try again until you get a prime.
• Generate q the same way. Make sure that q is in the right range so that n = pq has the intended target size. Also, OpenPGP mandates that q is greater than p (if you get a smaller q, you can always swap them).

So you could theoretically alter the process like this:

• Split the value V that you want to hide into two halves, V₁ and V₂. Let's assume that V₁ and V₂ have length k (in bits).
• Generate potential random p values which "include" V₁, i.e. p = 1 + 2*V₁ + r*2^k+1 for random integer values r of the "right size" so that p length is, say, 512 bits (if you target a 1024-bit modulus). Try again until you hit a prime p.
• Do the same for q, embedding V₂.

This process will work as long as you can have r values of size at least a dozen bits. Otherwise, there could be no prime at all with the desired format. The "*2" and the "+1" are there to force p to be odd: a big prime cannot be even.

I do not know of any software which implements that, but it should not be difficult to slap together with a big-integer library. I suggest using Java, which has appropriate java.math.BigInteger, and then Bouncy Castle for the encoding-into-OpenPGP-format part.

Beware that an attacker knowing that you play such tricks may try to attack your key by exploiting whatever structure your hidden value has. Also, implementing your own crypto is extremely rarely a good idea. And I said nothing about whether your idea of "hiding a key in plain sight" made sense; I only show how it could be done.

Answer 2

Sure, it's possible. I'd even say, it's easy. If you're using RSA, once you choose p and q, then you can choose d almost freely (subject only to the restriction that gcd(d, (p-1)(q-1)) = 1, which is not very restrictive, especially if you choose p,q so that (p-1)/2 and (q-1)/2 are prime). Thus, you can choose d to contain the specific string you chose.

However, I don't expect there any existing tools to do this for you. What you are asking for is an extremely unusual and peculiar functionality, so don't expect someone else to have already coded it up for you. You will probably need to learn a little bit about the RSA key generation algorithm and then implement it yourself.

Answer 3

Reminds me of the "Common Modulus" attack. Maybe not what you're thinking of, but it is a thought: http://members.tripod.com/irish_ronan/rsa/attacks.html

Also reminds me of http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing.

So, there are some thoughts. It sounds like you're really looking for something implement the Shamir secret sharing. Beware the caveats about choosing non-random data, too.

Answer 4

Each half of the private key is a prime number. As you want part of they key to be source code I see a simple way by terminating the source code with a single line comment token (e.g. C++ "//"), then consider the program string as the binary representation of a number, then adding to it until you pass a Rabin-Miller test (or cheat and use e.g. Maple's nextprime function that does it for you), the resulting number should be seen as valid source code that is also a prime number. You may need a bit of luck so line termination char are not added in the process or that would render the source code invalid.

There are many variation around that scheme, playing with comments, spacing... until the source code seen as a number is prime...