Keeping a Shared Secret … For a Trusted Group

Outline

Adi Shamir

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm which allows a secret to be split into parts, and only when a number of them are added together will the original message be created (paper). In these times when we need to integrate trust, his algorithm has many application areas.

So let’s take an example … let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken-over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.

Obviously, if this was a real scenario, we would create a password which would change over time, where we generate a one-time password, which cannot be used again (just in case!). For this we can use either a time-based mechanism, where the password is only relevant for a certain time window, such as with Time-based One Time Password (TOTP). Otherwise we can use an original seed password, which then changes each time we access it, where only those who know the original seed will be able to generate the next password. For this we can use a counter-based system such as for the Hash-based One Time Password (HOTP). With these schemes the same password would not be generated for each consecutive access, so that even when they had generated their password, they could only use it for a certain amount of time (with TOTP) or would differ for the next access (with HOTP).

Shamir’s Secret Sharing

In Shamir’s scheme, the number of generals can be represented by the number of shares, and the number generals who are required to generate the secret is represented by the threshold. Thus, in this example, we have a share value of six, and a threshold value of three. So we give out one of the shares to each of the generals, so that none of them have the same one. We will then require three generals to put together their shares in order for them to generate the password for the missile. To solve this problem and generate the shares (and also check the answer), I’ve created this Web page:

http://www.asecuritysite.com/Encryption/shamir

So for a password of “Fire The Missile”, with a share of six, and threshold of three we get:

000QAfeFBCViYHGKMOggJlP+HzuLCY=
001GaKHZb8bKNXIXJT9VVTE1KJ67Fc=
002u3yTKNa2y0HDPYoeFwycDpe7/8o=
0034tnKWXk4ahXNSd1DwsEXIkkvP7s=
004lja7FPgrDgKr9czMX4n8FfO0xfI=
005z5PiZVelr1algZuRikR3OS0gBYM=

for which each of these can be distributed to each of the generals. When three of them combine their codes, the result will be:

Fire the Missile

Basic theory

The basic theory relates to the number of points within a mathematical equation, that are required to reveal what the equation is (and thus determine the secret). For example if we have a secret of 15, and can only be revealed when two people combine their information. For this we thus need a linear equation, such as:

y= 2x + 15

The two pieces of information that could be generated to reveal the equation would thus be two points on this line, such as:

(1,17) and (2,19)

If we only know one point, such as (1,17), we cannot determine the equation of the line, but knowing two points we can determine the gradient:

gradient = (y2-y1)/(x2-x1) = (19-17)/(2-1) = 2

and from here we can determine the point it cuts the y-axis (c):

y = mx + c
c = y - mx
c = 17 - 2 * 1
c = 15

and thus we have the equation (y = 2x + 15), where the secret is 15.

In this example we have only two shares, if we require three shares we need a parabola, such as:

y = 2x^2 + 5x + 15

and share three points on the equation to generate the secret. If we require four shares then a cubic curve is required, and so on.

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