Diffie-Hellman & RSA & (k,n) thr

Diffie-Hellman

目的是双方安全地建立shared key。方法：规定公共信息，质数p，和其generator g。generator可以看做是，g^i mod p这个数，覆盖了1~p-1的所有数。

甲方自己有一个key为a，算出g ^ a之后传输给乙方。乙方自己有一个key为b，进行计算：(g ^ a)^b，作为shared key。同样的，甲方也进行对应操作获得(g ^ b)^a。

这样一来保证了正确性，双方能确立一样的秘钥。
也保证了安全性。任何网络监听方，只能看到g ^ a和g ^ b，但需要a或者b才能算出秘钥。我们知道g^a mod p这个数，知道g也知道p，但是要求出a这个数，涉及到一个discrete log problem，是无法efficient求出来的。

RSA

由于Diffie-Hellman需要双方发送建密信息，不适合多方建密使用。可以利用RSA，规定一个public key的组合（e，n），其中e与phi(n)互质。

n由甲方选定，由甲方先选择两个大的质数p和q，然后算出n=p * q，从而能算出phi(n) = (p-1) * (q-1)，phi为Euler’s Totient Function。由于质数分解问题是NP-HARD，这个phi、q、p只有甲方知道。另外甲方自己有一个private key，选定原则：e * d = 1 mod phi(n) （这隐含的要求就是e与phi(n)互质，不然d无解），也就是说e * d=k * phi(n)+1，也就是说d=[k*phi(n)+1]/e。

乙方得到甲方的public key（e，n）之后，对要传输的数字m进行加密，加密方式：c = m^e mod n
甲方得到c之后，进行解密。解密方式：m=c^d mod n = m^ed mod n = m^(k * phi(m)+1) mod n = m。最后一个等式根据Euler's Theorem：m^(phi(n)) = 1 mod n进行变形转化得到m^(k*phi(n)+1) = m mod n。

这样一来保证了正确性。甲方能够解密得到乙方的原信息。
也保证了安全性。任何监听网络方只能得到e，n，c这三个信息，而解密需要d，也就是phi(n)，核心在于求出p和q，也就是质数分解问题。

这个方式可应用于signature。甲方可传递（m, s=m^d mod n）这个信息，其中m是信息本身，s是验证方式。而乙方接到信息之后，验证s^e = m mod n是否正确。如果正确，说明甲方拥有d这个private key，甲方是真实的甲方。但这样一来存在一个问题，也就是说如果丙方传递的信息是（m^e, m），那么验证起来也是正确的，我不知道传给我信息的到底是丙方还是甲方。

(k,n) Threshold

目的是希望将一共n份的secret的成分分给很多参与方，其中至少k个参与方参与才能将secret解密出来。利用多项式的性质：将一个secret看做一个点，k个secret能够确立一个k-1 degree的多项式，取x=0时y的值即为secret。若点数小于k个，无法确立唯一的多项式，这保证了安全性。若点数大于等于k个，能确立唯一的多项式，这保证了正确性。

设secret的各个成份点为：(x1, y1), (x2, y2), (x3, y3)，我们所要求的多项式为p。那么p(x1)=y1, p(x2)=y2, p(x3)=y3。可以构建一个函数L，使得L_i(x_i)=1，L_i(x_j)=0，这样的话，

利用Langrage interpolation, 可得到

举例：

如此一来，对于L_5(x)，L_5(5)=1，而L_5(7), L_5(12), L_5(30)为0，符合我们的需求。
因此，我们针对构建出的函数p(x)，只要将x=0代入即可求出y值。