江苏龙网

  1. 首页 > 资讯 > 科技 > >

国王|国王的秘密：如何保护你的主密码 | Linux 中国( 二 )

P的模 ， mod P：
secret = mod.Mod(secret, P)
为了使任意三个孩子掌握的片段就可以重建这个秘密 ， 他还得生成另外两个部分 ， 并混杂到一起：
polynomial = [secret]
for i in range(2):

polynomial.append(Mod(int_from_bytes(urandom(16)), P))
len(polynomial)
3
下一步就是在随机选择的点上计算某 的值 ， 即计算polynomial[0] + polynomial[1]*x + polynomial[2]*x**2 ... 。
虽然有第三方模块可以计算多项式的值 ， 但那并不是针对有限域内的运算的 ， 所以 ， 国王还得亲自操刀 ， 写出计算多项式的代码：
def evaluate(coefficients, x):
acc = 0
power = 1
for c in coefficients:
acc += c * power
power *= x
return acc
再下一步 ， 国王选择五个不同的点 ， 计算多项式的值 ， 并分别交给五个孩子 ， 让他们各自保存一份：
shards = {}
for i in range(5):
x = Mod(int_from_bytes(urandom(16)), P)
y = evaluate(polynomial, x)
shards[i] = (x, y)
正如国王所虑 ， 不是每个孩子都正直守信 。 其中有两个孩子 ， 在他尸骨未寒的时候 ， 就想从自己掌握的秘密片段中窥出些什么 ， 但穷极所能 ， 终无所获 。 另外三个孩子听说了这个事 ， 合力将这两人永远驱逐：
del shards[2]
del shards[3]

二十年弹指一挥间 ， 奉先王遗命 ， 三个孩子将合力恢复出先王的大秘密 。 他们将各自的秘密片段拼合在一起：
retrieved = list(shards.values())
然后是 40 天没日没夜的苦干 。 这是个大工程 ， 他们虽然都懂些 Python ， 但都不如前国王精通 。
最终 ， 揭示秘密的时刻到了 。
用于反算秘密的代码基于， 它利用多项式在n个非 0 位置的值 ， 来计算其在0处的值 。 前面的n指的是多项式的阶数 。 这个过程的原理是 ， 可以为一个多项式找到一个显示方程 ， 使其满足：其在t[0]处的值是1 ， 在i不为0的时候 ， 其在t[i]处的值是0 。 因多项式值的计算属于线性运算 ， 需要计算 这些 多项式各自的值 ， 并使用多项式的值进行插值：
from functools import reduce
from operator import mul
def retrieve_original(secrets):
x_s = [s[0] for s in secrets]
acc = Mod(0, P)
for i in range(len(secrets)):
others = list(x_s)
cur = others.pop(i)
factor = Mod(1, P)
for el in others:
factor *= el * (el - cur).inverse()
acc += factor * secrets[i][1]

return acc
这代码是在太复杂了 ， 40 天能算出结果已经够快了 。 雪上加霜的是 ， 他们只能利用五个秘密片段中的三个来完成这个运算 ， 这让他们万分紧张：
retrieved_secret = retrieve_original(retrieved)
后事如何？


推荐阅读


上一篇：青年|日本主持将自家寺庙二次元化，并且亲自为宣传角色配音

下一篇：互联网|红星云亮相第五届SaaS应用大会,包揽两项大奖