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 person’s 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 9
k1 = 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) is 6a + 3M = 10 (mod 13) [Note 36 == 10]
� 2 * (equation 2) is 6a + 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 12
previous, with only the last being useful.
� The cheater is then revealed early on.