The Recycle Bin

A repository of comments, code, and opinions.

Sharing a Secret

with 3 comments

There is more to cryptography than simply hiding information.  One very useful extension of the field is into the area of information dissemination.  Imagine that you run a retail store with several employees.  This store has a code for it’s alarm system that must be set every night and cleared every morning.  Obviously, you can’t trust just any employee with the alarm key, because then they could enter the store at any time!  But you’re also a very busy person that can’t be bothered with actually opening and closing the store every day.  You would like to make a rule that there needs to be at least two people present at the store during opening and closing to prevent theft.  How are you going to implement this rule?  Fortunately you learned enough algebra is high school to do this!  You can split the key code into even but distinct halves, and then hand one out to each employee.  This way two employees would have to join their part together in order to open or close the door. 

That example isn’t very interesting.  How about enforcing the following rule:  four employees can open a door, or two employees and one manager, or two managers.  Now we need to split the key more finely, so that each manager gets two shares, each employee gets one, and it requires four parts to reassemble the key.  Now that we understand the problem, let’s discuss the math.

The trick is called the Shamir Threshold scheme and uses LaGrange Interpolation and the knowledge that two points are required to infer a line, three points for a quadratic, etc.  You simply define a polynomial with the secret number as the 0 root coefficient, and random numbers for the rest.  Let w be the number of participants in the system, and t be the number of shares needed to reassemble a secret message M.  Construct the follow polynomial:

poly

This polynomial defines a graph and the shares of the secret will be points along the graph.  Calculate a point for each person (w):  (1, f(1)) (2, f(2)) (3, f(3)) … (w, f(w)).  Each person now has a unique point on this graph.  They can then take t number of points and calculate the LaGrange coefficients to reassemble the polynomial, thus yielding the secret.

LaGrange states that given a set of x,y points
lag1
then
lag2
where
lag3

Wikipedia has a good page on LaGrange interpolation if you need more of an explanation that what I gave.

Let’s see an example.  We will take the first scenario I outlined:  there are 10 employees, at least two must be present to lock and unlock the door.  Let’s say the key code for the door is 25.

First we generate a polynomial:  f(x) = 25 + 73x^1.  The first coefficient is the secret, the second is a random number.

The second step is to generate unique points for each participant:
(Note:  All of the arithmetic here is done modulus some random n)

Modulus n: 163

(1, 98)
(2, 8)
(3, 81)
(4, 154)
(5, 64)
(6, 137)
(7, 47)
(8, 120)
(9, 30)
(10, 103)

As you can see, none of the participants know the secret number, but if you take two of their points you can calculate the secret.  Taking points (1,98) and  (2,8) gives the set of LaGrange constants as {-324, -1}.  Multiply -324 by 98, -1 by 8 and mod them by n=163 and you will be left with the secret, 25.

A more complicated example:  10 participants, 4 shares are required to reassemble.  Same secret, 25.

Modulus n: 181

Polynomial: 25 + 119x^1 + 159x^2 + 106x^3

(1, 47)
(2, 118)
(3, 150)
(4, 55)
(5, 107)
(6, 37)
(7, 119)
(8, 84)
(9, 25)
(10, 35)

Now if you try to reassembly the secret with only 3 points, then you will get an incorrect value.  Points (1, 47) (25, 107) (9, 25) will calculate a secret value of 40.  Point (3,150), and (6, 37) will give you 82.  Only if you select four or more point along the graph will you be able to calculate the correct secret.

Here is some Java code if you would like to play with this.

If you just want to see the program run, here is a pre-built JAR.

To run the JAR, use the command ‘java -jar secret.jar” provided you have a version of the JRE installed.

Advertisements

Written by Nathan

May 4, 2008 at 6:35 pm

Posted in Cryptography

Tagged with ,

3 Responses

Subscribe to comments with RSS.

  1. Really interesting… but where is the code?

    Javier

    January 15, 2009 at 8:27 pm

  2. heh. It looks like the links got removed. I’ll update the post. Thanks Javier.

    Nathan

    January 16, 2009 at 1:43 pm

  3. Thanks to you for fixing the links,

    Javier

    January 16, 2009 at 4:43 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: