[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 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 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.