[SOLVED] scheme algorithm 17crypto_L08

17crypto_L08

Multiple Key Cryptography

Crypto & SecDev 2017 Ron Poet:Lecture 8 1

Secret Splitting

Let us imagine that we have a secret that we cannot entrust
to just one person, but want to split between two people.

Both people are needed to reconstruct the message.

We cannot just give half the bits to each person.

Crypto & SecDev 2017 Ron Poet:Lecture 8 2

We cannot just give half the bits to each person.

It would make it easier for one person to make a brute
force attack to recover the other persons half.

Secret Splitting

The following protocol lets the boss Sam split the secret
between two underlings Alice and Bob.

Let M be the secret message.

Crypto & SecDev 2017 Ron Poet:Lecture 8 3

Let M be the secret message.

Sam obtains a truly random bit string R, the same length as
M, from the trusted third party Trent.

Sam calculates P = M R, gives P to Alice and R to Bob.
The message can be reconstructed as P R = M.
This technique cannot be broken by cryptographic

techniques, since R is a one time pad.

Splitting between more than two people

This technique is easily generalised to more than two
people.
Let us split the secret between Alice, Bob, Carol and Dave.

Sam provides three random bit strings, R, S and T.

Crypto & SecDev 2017 Ron Poet:Lecture 8 4

Sam provides three random bit strings, R, S and T.

The fourth string P = M R S T.
The four strings are distributed to the four underlings.

The original message is recovered by P R S T = M.

Limitations of this protocol
The boss has absolute power and can hand out rubbish if he wants.

All pieces of the encrypted message are necessary.

If Alice falls under a bus then the secret is lost.

Secret Sharing

It is possible to split a secret up into n pieces so that it can
be recovered with only m of the pieces.This is called a
threshold scheme.

With a (3,4) threshold scheme, the secret can be divided

Crypto & SecDev 2017 Ron Poet:Lecture 8 5

With a (3,4) threshold scheme, the secret can be divided
into 4 pieces and given to Alice, Bob, Carol and Dave.
Only three of them (any three) are needed to recover the secret.

If Alice falls under a bus then the secret is recoverable,

but if Bob is away at the time then Carol and Dave cannot recover
the secret by themselves.

The individual pieces are called shadows.

Lagrange Interpolation Scheme (Shamir)

This scheme is based on the numerical solution of linear equations.

Integers are used to avoid the problem of rounding errors that arise
when using real numbers.

Naturally, the integers are calculated mod p, so that division produces
an integer answer.

Crypto & SecDev 2017 Ron Poet:Lecture 8 6

an integer answer.

The shadows are calculated using a polynomial of the appropriate
degree.

This is not polynomial arithmetic, as discussed in an earlier lecture.
We are interested in solving the equation and finding x.

If 2 shadows are needed to construct the key then the appropriate
polynomial is a line which has two unknown coefficients a and b.

y(x) = a * x + b (mod p)

Lagrange Interpolation Scheme (2)

The algorithm when 2 shadows are needed.
Chose a prime number p which is larger than the number of shadows

(n) and the largest secret.

Prime p must be handed out along with the shadows and made
public.

Crypto & SecDev 2017 Ron Poet:Lecture 8 7

public.
Chose a random number < p for the coefficient a. It is only used to generate the shadows and is discarded after the shadows are calculated. It must be kept secret. The coefficient b is the secret message M. This produces the polynomial y(x) = a x + b (mod p)Lagrange Interpolation Scheme (3) The shadows are calculated by evaluating the polynomial at n different random values of x. I will use x = 1, 2, 3, 4 for simplicity. Each shadow is (x, y, p). shadow(1) = y(1)Crypto & SecDev 2017 Ron Poet:Lecture 8 8 shadow(2) = y(2) shadow(3) = y(3) shadow(4) = y(4) Since the straight line has two unknown coefficients a and b, any two shadows can be used to find them. The shadows generate two linear equations which can be solved for the two unknowns a and b. We want b, which is the secret M.Example Let the secret M be 11. Chose p = 13, a = 7. In practice, larger numbers will be used! Generate 4 keys from y(x) = 7 x + 11 (mod 13)Crypto & SecDev 2017 Ron Poet:Lecture 8 9k1 = y(1) mod 13 = 5(key = 1, 5, 13)k2 = y(2) mod 13 =12(key = 2,12, 13)k3 = y(3) mod 13 = 6(key = 3, 6, 13)k4 = y(4) mod 13 = 0(key = 4, 0, 13)Example (2) Now let us recover the secret from two keys, say k2, k3.2a + M = 12 (mod 13) — (1)3a + M =6 (mod 13) — (2) These equations must be solved.Crypto & SecDev 2017 Ron Poet:Lecture 8 10 We can eliminate a by 3 * (equation 1) 2 * (equation 2) 3 * (equation 1) is6a + 3M = 10 (mod 13)[Note 36 == 10] 2 * (equation 2) is6a + 2M = 12 (mod 13) Subtracting M = -2 = 11 (mod 13), the secret.Cheating with Secret Sharing Alice, Bob and Carol are sitting in a bunker when the message “Launch those missiles” comes from the president.Carol is a pacifist and so enters a random number rather than her shadow.The missiles stay in their silos and no one can find out why. Alice, Bob and Eve (disguised as Carol) are sitting in the bunker and Crypto & SecDev 2017 Ron Poet:Lecture 8 11 Alice, Bob and Eve (disguised as Carol) are sitting in the bunker and the same thing happens.Eve secretly notes down the shadows entered by Alice and Bob.The missiles stay in their silos but now Eve knows all three of the shadows.She can then retarget the missile and launch it herself.Preventing Cheating The Lagrangian protocol can be modified to make it easier to detect cheaters, with an increase in the complexity of the way the algorithm is applied. The basic approach is to have a series of secret, each linked to the previous, with only the last being useful.Crypto & SecDev 2017 Ron Poet:Lecture 8 12previous, with only the last being useful. The cheater is then revealed early on.