**分存技术(现代虎符)-如何把**存在不同的地方

虎符

上周的一天午后散步，和同事聊起了古代的虎符，就下面这玩意儿：

这玩意儿作为调动军队的凭证在古代发挥了巨大的作用，现代美国依然是采用了类似的方式调动军队，可见，这种将权力分开存储的思想在古今中外是殊途同归的。

  那么，作为互联网安全的根基，现代密码学中是如何应用这种思想的呢？这里就用到了**分存的技术，该技术是如何实现把一个**拆开来分别保存在各处的呢？本文来解答。

  进入话题之前，例行声明，本文不会涉及复杂的技术，我也不懂hardened key(用不到，也没时间学)，本文仅仅是一篇技术散文，由虎符这个饭后百步走的聊天话题说开去。

---

**分存

不管是对称**，私钥还是口令，无论哪种密码，均面临一个两难的问题，通俗点说，即：

• 只存一份
  以口令为例，比如记在脑里子是最安全的，然而遗忘了就没有任何办法了。
• 备份多份
  仍以口令为例，为了防止遗忘，很多人会写在纸上，然而纸条被别人看到或者偷走怎么办？

显而易见的解决方案就是风险分担。这种想法来自中世纪欧洲的公司：一个个体户出海一损俱损，不妨多人共同出资成立一个股份制公司，共同抵御潜在的风险。

  在**分存技术上，需要找到一种类似的风险分担机制，即：

• m$m$人中任意n$n$(m>n>1$m>n>1$)个人均可以恢复**

可见，任何单独的个人均无法恢复**，就算其中一个人被坏人拿着枪指着脑袋，他也无法泄露机密，除非坏人一下子把n$n$个人同时抓住才可以，这就大大降低了密码泄漏的风险。让我们看看这是怎么做到的。

---

编码到曲线

把密码片段编码到曲线上就看的很清楚了。以下通篇，我均以数字2作为要分存的**，即主**，虽然这看起来有点傻，但足以说明问题了。在以下的例子中，我们不保存数字2本身，而是将它拆成多个数字，即分**，然后分开存储这多个数字，不同点在于，我们希望将来使用多少个分**来恢复主**。

• 希望2个分**来恢复
  请看曲线：y=0.5x+2$y=0.5x+2$
  
  以上，我们**编码到了直线上，点A,B,C,D,E$A,B,C,D,E$为分**，而点F$F$为主**。我们只需要记住点A,B,C,D,E$A,B,C,D,E$中的两个，两点成一线，就可以恢复主**F$F$，如果只知道其中一个点，那将无济于事。

  嗯，这就是现代虎符的数学原理，后面的就简单多了，简单看看。

• 希望3个分**来恢复
  如果我们希望更加安全一些，比如3个持有分**的人均到场，才能恢复主**，那么就需要二次曲线了，因为我们知道，形如y=ax2+bx+c$y=a{x}^2+bx+c$的曲线可以由3个点来确定(待定系数法)。

  依然是先来一条曲线：y=1.5x2−3x+2$y=1.5x^2-3x+2$

知道分**点A,B,C,D$A,B,C,D$中的任意3个，就能恢复主**点E$E$。

• 希望4个分**来恢复
  如果需要4个分**恢复主**呢？很简单了，3次曲线即可。

这里我们可以总结出规律了，如果需要n$n$个分**来恢复主**，则需要一条n−1$n-1$次曲线，而曲线可以用二项式表达：
y=a1xn−1+a2xn−2+a3xn−3+...an−1x+A$y=a_1{x}^{n-1}+a_2{x}^{n-2}+a_3{x}^{n-3}+...a_{n-1}x+A$
其中A$A$为主**在曲线上的编码，a1$a_1$到an−1$a_{n-1}$是编码曲线的待定系数。

---

妙处

妙处在哪？

  两点成一直线，三点成一条抛物线，四点…这些n$n$点次数和二项式系数一一对应，而这一切又能统一于泰勒级数！不得不佩服现代数学，感叹是现代数学支撑了现代文明。

  摆上一瓶酒，像我这个傻逼一般欣赏现代数学。多少落寞惆怅，都随晨曦飘散，别人是不懂的。

不对称**分存

假设有一群m$m$个人分存了一个**，我们说只要凑够其中的n$n$个人拿出他们的分**，就能恢复主**，注意，这n$n$个人是任意的n$n$个人。

  如果说有这么一个需求，即n$n$个人中必须有某个人，这该如何是好呢？换句话说，m$m$个人任何一个人都无法单独恢复主**，要想恢复主**，必须请出其中的A先生，然后在剩下的人中再选出任意的n−1$n-1$个人，这n$n$个人一起来恢复主**。

  要怎么做到呢？

  也简单。以以上例子中最基本的一次曲线为例，在编码分**点A,B,C,D,E$A,B,C,D,E$结束后，选择一个分**master点，比如是点A$A$，然后点B,C,D,E$B,C,D,E$分别和master交换一部分数据即可，以下是一个实现方式，但绝不仅仅局限于这一种：

这样在恢复主**的时候，则必须有A$A$出场，恢复主**需要两个步骤：
1. 被选中的n−1$n-1$个点首先和A$A$交换以横坐标排序对应的数据块；
2. n−1$n-1$个点和A$A$一起完成主**恢复工作。
这两个步骤缺一不可，虽然A$A$为master，但是少了其余的n−1$n-1$个点，它还是无法独立恢复主**。

  好了，到底为止，原理就讲完了。下面这一节与此无关了，就着编码到曲线这个话题，聊聊椭圆曲线的离散对数难题。

---

离散对数难

思考了一下离散对数求解难这个问题。且看我的想法有无道理。

  实域对数求解就很容易吗？其实也很难，只是没有离散对数那么难。
我们之所以觉得实域对数容易，是因为实数域是连续统，而基于连续统有一个超级超级超级超级强大的工具，那就是微积分，因此，用泰勒级数展开求对数，太容易了，想多精确都可以，这取决于你能容忍多小的余项。现代计算机计算器计算对数时，几乎都是使用级数算的。

  另外，实域的对数还可以用换底公式把复杂化为简陋，这个傻逼都会，就不说了。

  离散域便完全不同了！

  离散域就没有微积分工具了，或者说，至少目前为止，我们还没有发现离散域上类似微积分这样强大的工具，因此便不再有泰勒级数这等解法了，所以就只能挨个尝试，另外质数取模操作，连自然数的连续性都破坏掉了，这相当于取模洗牌操作！

  我们认为它难，那是针对我们目前所能想到的计算手段而言。数学上可计算并不意味着应用中可计算。我们现在hold不住指数时间是因为我们的计算模型是线性的，如果出现了量子计算机，并且它真的表现的像量子力学基础所宣称的那样，那么所谓的离散指数难这个问题可能将不再存在。