d3_0x07_intro_secret_sharing

eZine lover (@eZine)

Published in 

Do not fuck with a hacker

 · 5 years ago

  

|=-----------------------------------------------------------------=| 
|=-----=[ D O   N O T   F U C K   W I T H   A   H A C K E R ]=-----=| 
|=-----------------------------------------------------------------=| 
|=------------------------[ #3 File 0x07 ]-------------------------=| 
|=-----------------------------------------------------------------=| 
|=-------------------=[Intro to Secret sharing]=-------------------=| 
|=-----------------------------------------------------------------=| 
|=--------------------=[   By me.ssword   ]=-----------------------=| 
|=-----------------------------------------------------------------=| 
|=-----------------------=[ Jan 21 2014  ]=------------------------=| 
|=-----------------------------------------------------------------=| 

 
# Secret Sharing 

假设这样的场景：习大大要交给三胖一份机密文件，派一名大使千里迢迢奔赴他 
国，但是大使如果在半路被美帝高价收买，把机密信息泄漏给美帝怎么办？ 

派十个大使，每人只携带均分的一部分机密文件，好，这一来得不到完整的机密 
就没有意义，美帝最多收买一个，总不能收买一窝吧。可是如果半路有一个大使 
被美帝干掉怎么办？三胖也得不到完整的机密了。此外，得到一部分机密文件可 
以降低猜测其它部分的成本，如果美帝收买了六个人，剩下的机密也可以猜个八 
九不离十。 

而 Secret Sharing 就是为了解决这个问题。允许习大大将机密文件分成多份密 
文，对方得到多数密文才能够还原出机密文件。其中有一两位大使被收买没关系， 
他自己手中的密文没有任何意义；一两位大使被干掉也没关系，剩下的大使仍然 
可以将还原出完整的机密；部分密文被盗走也没关系，得知部分密文不会降低猜 
测剩余密文的成本。 

## (n-t) Threshold Scheme 

传统的保密方法往往保密性与可靠性不可得兼：机密信息见不得光，为了保密， 
机密信息最好隔离在单独的一台机器上；同时，机密信息往往不允许丢失，这又 
不可避免地要求将机密信息拷贝备份到多个地方。 

上文习大大最后采用的方法，学名叫做 (n-t)-Threshold Scheme： 将机密信息 
分散在 n个 share 中，每个单独的 share 没有意义，当集齐至少 t 个 share 
时才可以构造出原先的密码。要求得知一份 share 不能减少猜测整体密码的成本； 
每份 share 最好至少包含等同于原始密码的信息量，由熵来填充。 

 
## Shamir's Scheme 

(n-t) Threshold Scheme 描述了 Secret Sharing 的可行方法，Shamir's 
Scheme 则属于它的一个实现。 

原理并不难理解：在二维坐标轴上，两个点可以确定一条直线，三个点可以确定 
一条抛物线。t 个坐标可以确定一个唯一的 (t-1) 次多项式图像。 

以直线为例，方程为 y = a * x 。那么我们可以把机密信息编码为数值 a (如 
3)，然后在直线上取三个坐标 (3, 1), (0, 0), (6, 2)。拿到任意两个坐标即可 
还原出数值 a。放在 (n-t)-Threshold Scheme 里，这个例子的 t 为 2，n 为 
3。 

如果需要更大的 t，可以选择更高次的多多项式。比如 y = a * x ^ 2 + b * y 
+ c，可以把机密信息编码为 (a, b, c)，至少需要三个坐标才能还原出机密信息。 

 
## Blakley's Scheme 

Blakley's Scheme 是另一种实现方法，但是思路差异并不大：(t-1) 维空间中， 
t 个不平行的面足以确定唯一的一个点。 

那么我们可以把机密信息编码为 (t-1) 维空间中的一个点，将每份 share 拆为 
一个面。t个点确定一个面，那么每份 share 的内容就是 t 个 (t-1) 维空间中 
的点。每份 share将拥有相对于原密码 t 倍的信息量。 

 
## References 

- http://en.wikipedia.org/wiki/Secret_sharing 
- http://www.cs.tau.ac.il/~bchor/Shamir.html