Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question
    
@Tim - This question is very ambiguous and as it is probably impossible to answer. Even if you do clarify your "obscure and silly purposes", it may still be closed as being "too localized". Please review the FAQ and try to re-write the question to be more specific and useful. –  Iszi Mar 12 '11 at 17:50
    
@Iszi: The purpose should not play any part in answering the question. Please clarify what is ambiguous and how it is impossible to answer. "Yes, this gpg switch" and "No" would be fine answers. What do you mean with the question being both too localized and unspecific? –  user1633 Mar 12 '11 at 18:02
    
@Tim - "Too localized" can refer to things that only apply to cases which very few (or perhaps only one) may encounter. Your question is unspecific in that it does not describe the reasoning behind your intents, which can be very important to consider when providing an appropriate solution. Quote: This question would only be relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. –  Iszi Mar 12 '11 at 18:39
2  
@Iszi: I see. The purpose is to let the first part of an obfuscated program decrypt the second part using itself. –  user1633 Mar 12 '11 at 18:42
2  
Sounds like a lot of fun, with some intriguing spinoff possibilities. There are various reasons for wanting to generate a key that meets certain specifications. Well worth the time and space to cover it here :) –  nealmcb Mar 12 '11 at 20:34

4 Answers 4

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, V1 and V2. Let's assume that V1 and V2 have length k (in bits).
  • Generate potential random p values which "include" V1, i.e. p = 1 + 2*V1 + r*2k+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 V2.

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
If I understand the question correctly, it has nothing to do with the common modulus attack nor with Shamir secret sharing. –  D.W. Mar 16 '11 at 7:36
    
Both of those are cases where part of the key is decided. It sounds like his ultimate goal is to have a key made up of multiple pieces ("such a strategy could be used to hide keys in plain sight"). SSS is made for exactly that. –  Jeff Ferland Mar 16 '11 at 14:31

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...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.