For emergencies: share part of pass with 4 people, decryptable with 2 persons

Question

Let's say I have a password:

AAABBBCCCDDD I could easily give person A the first part (AAA), person B the second part and so on.

But is there an option any two of the four people can decrypt/form the password from a part of text I give them? Obviously, from only the parts AAA and DDD the password can not be formed.

How? :)

Thorbert

In which language are you planning to implement this? – Aubigny

I'm not aware of any encryption algorithms that can do this, but I'm assuming the only way this will work is if you implement your own software for this. So why not just have 4 separate password and require your system to dual-authenticate. So instead of crazy encryption logic, you'll just have a UI that accepts 2 sets of credentials – Krell

I don't understand your question. Are you asking how to create a security system so that 2 or more, out of a total of 4, people is enough to access the system? In other words, one person cannot access it, but any combination of 2, 3, or all 4, people can? If so, what does the last sentence mean "Obviously, from only the parts AAA and DDD the password can not be formed".? – Oeflein

This kind of algorithm is known as a "secret sharing" scheme. There is a section on it in Applied Cryptography. – Celia

Answer 1

This is known as "Secret sharing", "Key splitting" or "Key distribution", and can be done with some public key cryptography algorithms.

Here are a few links on the subject:

• Wikipedia article: Key distribution
• Wikipedia article: Secret sharing

An easy way to do 2 out of 4 would be to split the key into 4 pieces, and distribute 3 pieces to everyone. The distributed parts would know which parts they have.

Here's a sample distribution:

1. 1+2+3
2. 1+2+4
3. 1+3+4
4. 2+3+4

As you can see, no matter which two people you pick, they will always have all four pieces. There are more mathematical methods the more people and combinations you get to, but it is certainly doable.

Oeflein

Answer 2

Is giving up 3/4 of the password to each person acceptable?

Person A: AAABBBCCC
Person B: AAABBBDDD
Person C: AAACCCDDD
Person D: BBBCCCDDD

Any two people would have the whole thing. They'd have to do a little trial and error with with splitting and merging their components, but it's probably doable.

Karelia

yep, this may be one simple and neat answer – Asset

Answer 3

Say your password is "password", give each person the following:

A: XXssword

B: paXXword

C: passXXrd

D: passwoXX

Theron

What would you use for the 'X' so that you know it's a placeholder and not part of the password string? – Karelia

You could use any escape sequence or an otherwise illegal character. I don't know the language you are using, or if you are just handing the partial passwords to 4 people on pieces of paper. But if * is not a legal character in your password, you could give B "pa*word". If a linefeed is an illegal character, you could give them "pa\nword" – Theron