很多人使用密碼管理器來(lái)保密存儲(chǔ)自己在用的各種密碼。密碼管理器的關(guān)鍵環(huán)節(jié)之一是主密碼，主密碼保護(hù)著所有其它密碼。這種情況下，主密碼本身就是風(fēng)險(xiǎn)所在。任何知道你的主密碼的人，都可以視你的密碼保護(hù)若無(wú)物，暢行無(wú)阻。自然而然，為了保證主密碼的安全性，你會(huì)選用很難想到的密碼，把它牢記在腦子里，并做所有其他你應(yīng)該做的事情。

[[335963]]

但是萬(wàn)一主密碼泄露了或者忘記了，后果是什么?也許你去了個(gè)心儀的島上旅行上個(gè)把月，沒(méi)有現(xiàn)代技術(shù)覆蓋，在開心戲水之后享用美味菠蘿的時(shí)刻，突然記不清自己的密碼是什么了。是“山巔一寺一壺酒”?還是“一去二三里，煙村四五家”?反正當(dāng)時(shí)選密碼的時(shí)候感覺(jué)渾身都是機(jī)靈，現(xiàn)在則后悔當(dāng)初何必作繭自縛。

當(dāng)然，你不會(huì)把自己的主密碼告訴其它任何人，因?yàn)檫@是密碼管理的首要原則。有沒(méi)有其它變通的辦法，免除這種難以承受的密碼之重?

試試 Shamir 秘密共享算法(Shamir's Secret Sharing)，這是一種可以將保密內(nèi)容進(jìn)行分塊保存，且只能將片段拼合才能恢復(fù)保密內(nèi)容的算法。

先分別通過(guò)一個(gè)古代的和一個(gè)現(xiàn)代的故事，看看 Shamir 秘密共享算法究竟是怎么回事吧。

這些故事的隱含前提是你對(duì)密碼學(xué)有起碼的了解，必要的話，你可以先溫習(xí)一下 密碼學(xué)與公鑰基礎(chǔ)設(shè)施引論。

一個(gè)古代關(guān)于加解密的故事

古代某國(guó)，國(guó)王有個(gè)大秘密，很大很大的秘密：

def int_from_bytes(s): 
    acc = 0 
    for b in s: 
        accacc = acc * 256 
        acc += b 
    return acc 
secret = int_from_bytes("terrible secret".encode("utf-8")) 

大到連他自己的孩子都不能輕易信任。他有五個(gè)子女，但他知道前路危機(jī)重重。他的孩子需要在他百年之后用這個(gè)秘密來(lái)保衛(wèi)國(guó)家，而國(guó)王又不能忍受自己的孩子在他們還記得自己的時(shí)候就知道這些秘密，尤其是這種狀態(tài)可能要持續(xù)幾十年。

所以，國(guó)王動(dòng)用大力魔術(shù)，將這個(gè)秘密分為了五個(gè)部分。他知道，可能有一兩個(gè)孩子不會(huì)遵從他的遺囑，但絕對(duì)不會(huì)同時(shí)有三個(gè)或三個(gè)以上會(huì)這樣：

from mod import Mod 
from os import urandom 

國(guó)王精通 有限域 和 隨機(jī) 魔法，當(dāng)然，對(duì)他來(lái)說(shuō)，使用巨蟒分割這個(gè)秘密也是小菜一碟。

第一步是選擇一個(gè)大質(zhì)數(shù)——第 13 個(gè) 梅森質(zhì)數(shù)(2**521 - 1)，他讓人把這個(gè)數(shù)鑄造在巨鼎上，擺放在大殿上：

P = 2**521 - 1 

但這不是要保密的秘密：這只是 公開數(shù)據(jù)。

國(guó)王知道，如果 P 是一個(gè)質(zhì)數(shù)，用 P 對(duì)數(shù)字取模，就形成了一個(gè)數(shù)學(xué) 場(chǎng)：在場(chǎng)中可以自由進(jìn)行加、減、乘、除運(yùn)算。當(dāng)然，做除法運(yùn)算時(shí)，除數(shù)不能為 0。

國(guó)王日理萬(wàn)機(jī)，方便起見(jiàn)，他在做模運(yùn)算時(shí)使用了 PyPI 中的 mod 模塊，這個(gè)模塊實(shí)現(xiàn)了各種模數(shù)運(yùn)算算法。

他確認(rèn)過(guò)，自己的秘密比 P 要短：

secret < P 

TRUE 

將秘密轉(zhuǎn)換為 P 的模，mod P：

secret = mod.Mod(secret, P) 

為了使任意三個(gè)孩子掌握的片段就可以重建這個(gè)秘密，他還得生成另外兩個(gè)部分，并混雜到一起：

polynomial = [secret] 
for i in range(2): 
    polynomial.append(Mod(int_from_bytes(urandom(16)), P)) 
len(polynomial) 

3 

下一步就是在隨機(jī)選擇的點(diǎn)上計(jì)算某 多項(xiàng)式 的值，即計(jì)算 polynomial[0] + polynomial[1]*x + polynomial[2]*x**2 ...。

雖然有第三方模塊可以計(jì)算多項(xiàng)式的值，但那并不是針對(duì)有限域內(nèi)的運(yùn)算的，所以，國(guó)王還得親自操刀，寫出計(jì)算多項(xiàng)式的代碼：

def evaluate(coefficients, x): 
    acc = 0 
    power = 1 
    for c in coefficients: 
        acc += c * power 
        power *= x 
    return acc 

再下一步，國(guó)王選擇五個(gè)不同的點(diǎn)，計(jì)算多項(xiàng)式的值，并分別交給五個(gè)孩子，讓他們各自保存一份：

shards = {} 
for i in range(5): 
    x = Mod(int_from_bytes(urandom(16)), P) 
    y = evaluate(polynomial, x) 
    shards[i] = (x, y) 

正如國(guó)王所慮，不是每個(gè)孩子都正直守信。其中有兩個(gè)孩子，在他尸骨未寒的時(shí)候，就想從自己掌握的秘密片段中窺出些什么，但窮極所能，終無(wú)所獲。另外三個(gè)孩子聽說(shuō)了這個(gè)事，合力將這兩人永遠(yuǎn)驅(qū)逐：

del shards[2] 
del shards[3] 

二十年彈指一揮間，奉先王遺命，三個(gè)孩子將合力恢復(fù)出先王的大秘密。他們將各自的秘密片段拼合在一起：

retrieved = list(shards.values()) 

然后是 40 天沒(méi)日沒(méi)夜的苦干。這是個(gè)大工程，他們雖然都懂些 Python，但都不如前國(guó)王精通。

最終，揭示秘密的時(shí)刻到了。

用于反算秘密的代碼基于 拉格朗日差值，它利用多項(xiàng)式在 n 個(gè)非 0 位置的值，來(lái)計(jì)算其在 0 處的值。前面的 n 指的是多項(xiàng)式的階數(shù)。這個(gè)過(guò)程的原理是，可以為一個(gè)多項(xiàng)式找到一個(gè)顯示方程，使其滿足：其在 t[0] 處的值是 1，在 i 不為 0 的時(shí)候，其在 t[i] 處的值是 0。因多項(xiàng)式值的計(jì)算屬于線性運(yùn)算，需要計(jì)算 這些 多項(xiàng)式各自的值，并使用多項(xiàng)式的值進(jìn)行插值：

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 

這代碼是在太復(fù)雜了，40 天能算出結(jié)果已經(jīng)夠快了。雪上加霜的是，他們只能利用五個(gè)秘密片段中的三個(gè)來(lái)完成這個(gè)運(yùn)算，這讓他們?nèi)f分緊張：

retrieved_secret = retrieve_original(retrieved) 

后事如何?

retrieved_secret == secret 

TRUE 

數(shù)學(xué)這個(gè)魔術(shù)的優(yōu)美之處就在于它每一次都是那么靠譜，無(wú)一例外。國(guó)王的孩子們，曾經(jīng)的孩童，而今已是壯年，足以理解先王的初衷，并以先王的錦囊妙計(jì)保衛(wèi)了國(guó)家，并繼之以繁榮昌盛!

關(guān)于 Shamir 秘密共享算法的現(xiàn)代故事

現(xiàn)代，很多人都對(duì)類似的大秘密苦不堪言：密碼管理器的主密碼!幾乎沒(méi)有誰(shuí)能有足夠信任的人去完全托付自己最深的秘密，好消息是，找到至少有三個(gè)不會(huì)串通起來(lái)搞鬼的五人組不是個(gè)太困難的事。

同樣是在現(xiàn)代，比較幸運(yùn)的是，我們不必再像國(guó)王那樣自己動(dòng)手分割要守護(hù)的秘密。拜現(xiàn)代 開源 技術(shù)所賜，這都可以使用現(xiàn)成的軟件完成。

假設(shè)你有五個(gè)不敢完全信任，但還可以有點(diǎn)信任的人：張三、李四、王五、趙六和錢大麻子。

安裝并運(yùn)行 ssss 分割密鑰：

$ echo 'long legs travel fast' | ssss-split -t 3 -n 5 
Generating shares using a (3,5) scheme with dynamic security level. 
Enter the secret, at most 128 ASCII characters: Using a 168 bit security level. 
1-797842b76d80771f04972feb31c66f3927e7183609 
2-947925f2fbc23dc9bca950ef613da7a4e42dc1c296 
3-14647bdfc4e6596e0dbb0aa6ab839b195c9d15906d 
4-97c77a805cd3d3a30bff7841f3158ea841cd41a611 
5-17da24ad63f7b704baed220839abb215f97d95f4f8 

這確實(shí)是個(gè)非常牛的主密碼：long legs travel fast，絕不能把它完整的托付給任何人!那就把五個(gè)片段分別交給還比較可靠的伙伴，張三、李四、王五、趙六和錢大麻子。

• 把 1 給張三。
• 把 2 給李四。
• 把 3 給王五。
• 把 4 給趙六。
• 把 5 給錢大麻子。

然后，你開啟你的愜意之旅，整整一個(gè)月，流連于海邊溫暖的沙灘，整整一個(gè)月，沒(méi)碰過(guò)任何電子設(shè)備。沒(méi)用多久，把自己的主密碼忘到了九霄云外。

李四和王五也在和你一起旅行，你托付給他們保管的密鑰片段保存的好好的，在他們各自的密碼管理器中，但不幸的是，他們和你一樣，也忘了自己的 主密碼。

沒(méi)關(guān)系。

聯(lián)系張三，他保管的密鑰片段是 1-797842b76d80771f04972feb31c66f3927e7183609;趙六，一直替你的班，很高興你能盡快重返崗位，把自己掌握的片段給了你，4-97c77a805cd3d3a30bff7841f3158ea841cd41a611;錢大麻子，收到你給的跑腿費(fèi)才將自己保管的片段翻出來(lái)發(fā)給你，5-17da24ad63f7b704baed220839abb215f97d95f4f8。

有了這三個(gè)密鑰片段，運(yùn)行：

$ ssss-combine -t 3 
Enter 3 shares separated by newlines: 
Share [1/3]: 1-797842b76d80771f04972feb31c66f3927e7183609 
Share [2/3]: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611 
Share [3/3]: 5-17da24ad63f7b704baed220839abb215f97d95f4f8 
Resulting secret: long legs travel fast 

就這么簡(jiǎn)單，有了 開源 技術(shù)加持，你也可以活的像國(guó)王一樣滋潤(rùn)!

自己的安全不是自己一個(gè)人的事

密碼管理是當(dāng)今網(wǎng)絡(luò)生活必備技能，當(dāng)然要選擇復(fù)雜的密碼，來(lái)保證安全性，但這不是全部。來(lái)用 Shamir 秘密共享算法，和他人共同安全的存儲(chǔ)你的密碼吧。