# How to generate a key using any m passwords out of total n?

My application requires an AES-256 key K for some secure operation. In order to avoid saving this key in application, I have implemented following scheme:

1. There are 5 individuals who enters their passwords in application. Lets call them PW1..PW5
2. Using these passwords, I have generated the key as:

K = KDF(PW1 || PW2 || PW3 || PW4 || PW5)


The problem is that now I need to modify the application such that it works even if only 3 out of 5 passwords are available (but no less than 3). This is required because even if we lose one or two passwords (accident, person refusing to enter password etc.), we are able to recover from that situation.

Please can you advise how it can be achieved?

-
Possible duplicate of Can I pre-define the points in Shamir's Secret Sharing algorithm. (Your question is somewhat more general, since it doesn't mention Shamir's scheme explicitly, but the answers apply to the more general case as well.) –  Ilmari Karonen Jan 23 '13 at 18:29

One option would be to generate a random key, split it using Shamir's secret sharing, then encrypt each of the split parts individually under a key derived from each user's password.

So for example:

key = read from os.urandom()
d1,d2,...d5 = split(key=key,n=5,k=3)
e1 = encrypt(d1, KDF(PW1)), e2 = encrypt(d2, KDF(PW2))...


key can then be derived from all of the encrypted shares (e1, ...) and user's passwords (PW1, ...). You could store the encrypted shares in the application and be confident that without at least three of the passwords you wouldn't be able to derive the key.

-
Thanks @Michael. You rock! (and I feel so stupid that I couldn't think of extending the scheme). –  Hemant Jan 24 '13 at 14:19