文档介绍：Security Protocols
曹天杰
Tianjie Cao
******@cumt.
College puter Science and
Technology, China University of Mining and Technology, Xuzhou, China
中国矿业大学计算机科学与技术学院
1
secret splitting
Problem:
You are the CEO of Coca-Cola. You are responsible for bringing a refreshing taste to zillions of people all over the world, but want to keep the recipe secret from Pepsi’s industrial spies.
You could tell your most trusted employees
they could defect to the opposition
they could fall to rubber hose cryptanalysis
How can we split a secret among two parties where each piece by itself is useless?
2
secret splitting
Algorithm:
Assume Trent wishes to protect the message m:
Trent generates a random bit string r, the same length m.
putes m r = s
Trent gives Alice r
Trent gives Bob s
Each of the pieces is called a shadow.
To reconstruct m, Alice and Bob XOR their shadows together.
If r is truly random, the system is perfectly secure (OTP).
To extend the scheme to n people, generate n random bit strings . m r s t = u
3
secret sharing
Problem:
You are responsible for a small third world country’s nuclear weapons program.
You want to ensure that no single lunatic can launch a missile.
You want to ensure that no two lunatics can collude to launch a missile.
You want at least three of five officers to be lunatics before a missile can be launched.
We call this a (3,5) threshold scheme.
4
Threshold Scheme
N users and a threshold d
Any group of d or more users can jointly obtain the secret
Any group of d-1 or less users can not jointly obtain any information about the secret
Assume we have a dealer here who has the secret
5
(N,1) - (N,N) scheme
(N,1) :Make N copies of the secret and give each user a copy
(N,N) :Let s be the secret, let M be a large number
Let s1, s2,…, sN be N random numbers such that s1+ s2+…+ sN = s mod M
Assign si to the ith user
6
Adi Shamir (N,d)-Scheme
Pick a prime p
and a random polynomial
f (x) = ad-1xd-1 + ad-2xd-2 +…+ a0 mod p