Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm curious about exploring uses for a distributing a single RSA private key with a passphrase instead of trying to secure the private key and distribute the public key. With the private key (and passphrase) the public key could be created as needed.

What is the work effort to break the passphrase on an 1024 or 2048 bit RSA private key?

The idea is that I could generate a private key and store it outside the entity in a non-secure location but not worry (as much) about it since it is protected by a passphrase.

The whole private key might be stored in several places - in fact and I have to assume they are all publicly-accessible (like a web page). But when the entity wants to do something with the key it requests it back from the storage places and then (with the users password) decrypts it and uses it for what is needed.

share|improve this question
What is the purpose of distributing an RSA private key? Why can't multiple hosts have their own keypair? – Stephen Touset Mar 28 '13 at 16:48
The entity to which the private key belongs cannot store it themselves and must use a/multiple 3rd parties to store it. – Xeoncross Mar 28 '13 at 16:50
Will the RSA key be unlocked and used on those machines? Or will it be transferred to a controlled environment first? – Stephen Touset Mar 28 '13 at 16:54
The RSA key will be returned to the owning party when it's needed which will then use it to do what it needs done. The problem is that the owning party can't store the key. – Xeoncross Mar 28 '13 at 17:02
They don't, the physical user of the owning entity must remember it. (If they could remember the RSA key the problem would be solved right there). – Xeoncross Mar 28 '13 at 18:32

Based on skimming the relevant RFCs, I can't find any outright problems. Key derivation from the password is performed via PBKDF2, and best I can tell, the choice of cipher is left up to the implementation. As long as a good cipher is chosen, a truly random 30-character passphrase consisting of uppercase letters, lowercase letters, and digits should have roughly 178 bits of entropy. This is significantly higher than that of a 128-bit key, which is considered to be secure.

It still gives me a bad feeling that I can't shake. But as long as keys are only ever decrypted on trusted devices, I can't personally find a reason why it would be unsafe.

Not that this should be considered an endorsement by any stretch of the imagination.

share|improve this answer
@Xeoncross: of course, the above is entirely dependent on the passphrase being random (or mostly); if the 30 character passphrase is "abcdefghijklmnopqrstuvwxyz1234", then all bets are off. – poncho Mar 28 '13 at 20:45

So, you have several requirements.

  1. Multiple parties share ownership of a part of the key.
  2. Parties will use human memory to store their parts.
  3. The passphrase must be a minimum of 30 characters.

The first requirement definitely sounds like a job for Shamir's Secret Sharing algorithm, where you have to bring together at least $m$ of $n$ shares in order to recover the original secret.

The second sounds like a need for a strong password hashing algorithm.

The third simply requires a compliance policy on passwords.

All together, it sounds like you are trying to recreate a Key Ceremony, for which standards and practices already exist. Perhaps it would be better to start there than to rebuild it all from scratch, as you could easily make a mistake in a home-grown plan. This is especially true if the practice will be externally audited, as auditors (like PCI assessors or SOX auditors) love to see organizations using standards for these activities.

share|improve this answer
Actually, multiple parties can have a whole copy of the key. There is no sharding/splitting of the key and the only thing remembered is by the original human is the passphrase - the private key is stored somewhere out in the public. – Xeoncross Mar 28 '13 at 20:52
I believe @JohnDeters' point is that your problem is equivalent to a secret sharing scheme with $m = n = 2$. Data derived from the passphrase would constitute one of the two shares, and each server would possess the single remaining share needed to reconstruct the key. – Stephen Touset Mar 28 '13 at 21:13
Yes, in the case of each person having full ownership of the key, SSS would still work, but so would individual asymmetric encryption of the key. I'd still recommend SSS; key splitting is recommended for master root key applications, and it sounds like you have a circle of people who have a strong interest in the key. Allowing any single entity the opportunity to turn rogue and "rule them all" is a risky practice. – John Deters Mar 28 '13 at 22:32

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.