Secure code unlocked by any 3 of 5 different people PROBLEM

[markddd]

So the problem is, how to set up a situation where a code can be unlocked by any 3 of any 5 different known people in any combination.

Example using 3 people: Ginger, Gilligan, Skipper, each posses a code, when combined, will equal enough parts to complete the final "password" to unlock the code. The difficulty is setting it up so any combination of less than 3 are not able to unlock the "code", or where any given combination of 3 might fail to unlock the code.

Here's an example which is only functional with 3 people:
Ginger has code A & B (gets C from Skipper and D from Gilligan) = ABCD
Gilligan has code A & D
Skipper has code B & C

There is no restriction on the amount of code segments, i.e., could continue with E,F,G, etc... and no restriction on the number of segments per person, i.e., ABC or ABCD or ABCDE, etc...

 

[Steven G]

Sorry but this is a math help forum and as such we do not solve problems for students.

 

[markddd]

Sorry but this is a math help forum and as such we do not solve problems for students.

I'm not a student. This is a personal math problem that I have struggled with for too long. I have looked far and wide without a solution.

 

[Steven G]

If you struggled then you must have done some work on it. Please show us your work and we can guide you to the correct answer. Please post back.

 

[markddd]

I posted as far as I have been able to get, and that is 3 people. Whenever I add a forth, I either end up with to little information to be able to solve with any combination of 3, or too much information and 2 people are able to complete the code. I am only able to attempt solutions with brute force speculation. If there is a mathmatical method to solve, I don't have the skills.

 

[markddd]

I either end up with to too little information...

 

[Cubist]

I'm a bit concerned that you said this needs to be secure. For best security you really need to use an established method of password access. There are trusted software libraries out there for this kind of thing. Therefore just design an access screen that accepts 6 fields:- user1, pass1, user2, pass2, user3, pass3. Then check for 3 valid usernames/ passwords.

--

BUT if you don't really need a lot of security, and are just interested in a simple mechanism for a computer game or something, then I have a suggestion. You could build the passwords up like this:-

Step 1 (the space is added for clarity and should not be in the final password):-

ABCD EFGH
ABCD E
ABCD F
ABCD G
ABCD H

Step 2:-

ABCD EFGH
ABCD EIJK
ABCD FI
ABCD GJ
ABCD HK

Step 3:-

ABCD EFGH
ABCD EIJK
ABCD FILM
ABCD GJL
ABCD HKM

Step 4:-

ABCD EFGH
ABCD EIJK
ABCD FILM
ABCD GJLN
ABCD HKMN

Hopefully you can see the pattern. Just add the same (new) letters across and down, until the block is complete.


Then the rule for combining two passwords is:- keep the next pair of letters that match. Remove any letters that don't match while keeping the password in alphabetical order. So...

  ABCDEFGH
+ ABCDFILM
= ABCDF

  ABCDF
+ ABCDGJLN
= ABCD

So the block of letters on the left will form the final password. The block on the right will be eliminated after 3 passwords are combined.

To make this less obvious you must:-
1. add more blocks of letters (and include more right-hand "elimination" blocks)
2. randomize the letters used (this will randomize the column order when the password is sorted)

For an example of (2), these random mappings A -> j, B -> l, C -> f, D -> c, E -> n, F -> e, G -> a, H -> h, I -> i, J -> d, K -> b, L -> g, M -> m, N -> k turn the above passwords into:-
acefhjln
bcdfijln
cefgijlm
acdfgjkl
bcfhjklm
(then the final expected password is cfjl)

But I would not claim that this is secure, since after two people combine their passwords then most of the "bad" letters are eliminated. Therefore you only need to go through combinations of removing one more letter (or 2+ more letters if you have extra columns like the RHS block).

 

[markddd]

Cubist, thank you for your reply. For simplicity, I left out how it was to be used real world. My intention is to replace each letter with a hardened key. I'm impressed you saw through to my ultimate purpose . I intend to provide 5 people the series of "passwords" or "keys" that only three combined can use to decrypt a secure file and any less cannot.

Functionally, the final key would work like this (but with greater complexity in each segment):
A= F$g0%
B= %gTh^
C= ^83Cy
D= ya635
E= 5H&@x

The final password = F$g0%%gTh^^83Cyya6355H&@x

Although not required, I would use the matching characters at the end and beginning of each segment to aid end users to complete the key successfully.

You've given me a lot to think about. I'll digest what you posted as time permits. Again, thank you.

 

[Cubist]

I thought of a much simpler method now. Here are the 5 keys...
1. E F G H I J
2. B C D H I J
3. A C D F G J
4. A B D E G I
5. A B C E F H

Now you can combine any two keys in an additive way, by writing down all the letters that both keys have (writing each letter once). So to combine the first two keys above E F G H I J +B C D H I J = B C D E F G H I J. Note that letter "A" is missing from this result. But "A" is present in all three remaining keys. In fact whichever two keys you combine, there will always be a single letter missing - and that letter can be obtained by combining with a third (different) key.

To generate these keys, I considered the ways of choosing two numbers from five:- 12, 13, 14, 15, 23, 24, 25, 34, 35, 45. Then for each of these results I assigned a unique letter A12, B13, C14, D15, E23, F24, G25, H34, I35, J45. Then, every key has letter A except keys 1&2. Also, every key has letter B except keys 1&3. Repeat for all letters up to J which is in all keys except 4&5.

 

[markddd]

I thought of a much simpler method now. Here are the 5 keys...
1. E F G H I J
2. B C D H I J
3. A C D F G J
4. A B D E G I
5. A B C E F H

Now you can combine any two keys in an additive way, by writing down all the letters that both keys have (writing each letter once). So to combine the first two keys above E F G H I J +B C D H I J = B C D E F G H I J. Note that letter "A" is missing from this result. But "A" is present in all three remaining keys. In fact whichever two keys you combine, there will always be a single letter missing - and that letter can be obtained by combining with a third (different) key.

To generate these keys, I considered the ways of choosing two numbers from five:- 12, 13, 14, 15, 23, 24, 25, 34, 35, 45. Then for each of these results I assigned a unique letter A12, B13, C14, D15, E23, F24, G25, H34, I35, J45. Then, every key has letter A except keys 1&2. Also, every key has letter B except keys 1&3. Repeat for all letters up to J which is in all keys except 4&5.

By golly you got it! Thank you Cubist!³