Bugtraq mailing list archives
RE: Joint encryption?
From: "David Schwartz" <davids () webmaster com>
Date: Sat, 19 Feb 2005 12:13:59 -0800
The authentication works as below: - N users may authenticate to access the data - A magnitude M of authenticated users is needed to access the data - N >= 3 > M >= 2 The case where N = 1 is simple authentication; the case where N = M is an easily solvable problem in the scope I'm looking at. I'm interested in the case where N > M and the data is encrypted. - Key is fragmented - Fragments are indpendently encrypted - Each user who can authenticate can decrypt PART of the key, but not all of it - M of the N users are needed to decrypt enough of the key to access the key in total The problem is that I need a guaranteed way to create data for any valid N and M where N >= 3 > M >= 2 in which access to M fragments of the key (each fragment is encrypted) can be used to gain access to the rest of the fragments, which in turn allows any selection of M users to authenticate and gain physical access to the key. Reminder that the idea here is to use a physical method, not bare access control that can be evaded by loading a modified kernel. The most obvious methods I can think of create explosive data growth as M and N increase. The amount of data needed in any way I can think of grows linearly with M and exponentially with N. Are there any known ways to do this?
There's a ludicrously simple and incredibly brilliant way to do this. For a polynomial of order N, you need N points on the polynomial to find the equation that describes the polynomial. So if you want to share a secret amount 28 people such that any 15 are needed to know it, just make the secret the coefficients of a 15th order polynomial and compute 28 points that satisfy the polynomial. So, for the 28/15 example, pick 15 random coefficients (C1, C2, C3, ...), and then your 28 pieces of the key (K1 ... K25) are the solutions to: Kx = C1 + C2 * x + C3 * x^2 + C3 * x^3 ... C15 * x^14 For x=1 to 28. With any 15 solutions to the equation above, you can compute C1 through C15. With any 14, you can't even get started. DS DS
Current thread:
- Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Damian Menscher (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Casper . Dik (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Robert C. Helling (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? devnull (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? peter zulu (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Gandalf The White (Feb 21)
- RE: Joint encryption? David Schwartz (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 21)
- Re: Joint encryption? Valdis . Kletnieks (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 21)
- Re: Joint encryption? Ruud H.G. van Tol (Feb 21)
- Re: Joint encryption? Damian Menscher (Feb 19)