國王的秘密：如何保護你的主密碼

很多人使用密碼管理器來保密存儲自己在用的各種密碼。密碼管理器的關鍵環節之一是主密碼，主密碼保護著所有其它密碼。這種情況下，主密碼本身就是風險所在。任何知道你的主密碼的人，都可以視你的密碼保護若無物，暢行無阻。自然而然，為了保證主密碼的安全性，你會選用很難想到的密碼，把它牢記在腦子裡，並做所有其他你應該做的事情。

但是萬一主密碼泄露了或者忘記了，後果是什麼？也許你去了個心儀的島上旅行上個把月，沒有現代技術覆蓋，在開心戲水之後享用美味菠蘿的時刻，突然記不清自己的密碼是什麼了。是「山巔一寺一壺酒」？還是「一去二三里，煙村四五家」？反正當時選密碼的時候感覺渾身都是機靈，現在則後悔當初何必作繭自縛。


（XKCD, CC BY-NC 2.5）

當然，你不會把自己的主密碼告訴其它任何人，因為這是密碼管理的首要原則。有沒有其它變通的辦法，免除這種難以承受的密碼之重？

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

先分別通過一個古代的和一個現代的故事，看看 Shamir 秘密共享演算法究竟是怎麼回事吧。

這些故事的隱含前提是你對密碼學有起碼的了解，必要的話，你可以先溫習一下 密碼學與公鑰基礎設施引論.

一個古代關於加解密的故事

古代某國，國王有個大秘密，很大很大的秘密：

def int_from_bytes(s):
    acc = 0
    for b in s:
        acc = acc * 256
        acc += b
    return acc

secret = int_from_bytes("terrible secret".encode("utf-8"))

大到連他自己的孩子都不能輕易信任。他有五個子女，但他知道前路危機重重。他的孩子需要在他百年之後用這個秘密來保衛國家，而國王又不能忍受自己的孩子在他們還記得自己的時候就知道這些秘密，尤其是這種狀態可能要持續幾十年。

所以，國王動用大力魔術，將這個秘密分為了五個部分。他知道，可能有一兩個孩子不會遵從他的遺囑，但絕對不會同時有三個或三個以上會這樣：

from mod import Mod
from os import urandom

國王精通 有限域 和 隨機 魔法，當然，對他來說，使用巨蟒分割這個秘密也是小菜一碟。

第一步是選擇一個大質數——第 13 個 梅森質數（2**521 - 1），他讓人把這個數鑄造在巨鼎上，擺放在大殿上：

P = 2**521 - 1

但這不是要保密的秘密：這只是 公開數據。

國王知道，如果 P 是一個質數，用 MARKDOWN_HASH44c29edb103a2872f519ad0c9a0fdaaaMARKDOWNHASH 對數字取模，就形成了一個數學 [場](https://en.wikipedia.org/wiki/Field(mathematics))：在場中可以自由進行加、減、乘、除運算。當然，做除法運算時，除數不能為 0。

國王日理萬機，方便起見，他在做模運算時使用了 PyPI 中的 mod 模塊，這個模塊實現了各種模數運算演算法。

他確認過，自己的秘密比 P 要短：

secret < P

TRUE

將秘密轉換為 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)

後事如何？

retrieved_secret == secret

TRUE

數學這個魔術的優美之處就在於它每一次都是那麼靠譜，無一例外。國王的孩子們，曾經的孩童，而今已是壯年，足以理解先王的初衷，並以先王的錦囊妙計保衛了國家，並繼之以繁榮昌盛！

關於 Shamir 秘密共享演算法的現代故事

現代，很多人都對類似的大秘密苦不堪言：密碼管理器的主密碼！幾乎沒有誰能有足夠信任的人去完全託付自己最深的秘密，好消息是，找到至少有三個不會串通起來搞鬼的五人組不是個太困難的事。

同樣是在現代，比較幸運的是，我們不必再像國王那樣自己動手分割要守護的秘密。拜現代 開源 技術所賜，這都可以使用現成的軟體完成。

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

安裝並運行 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

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

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

然後，你開啟你的愜意之旅，整整一個月，流連於海邊溫暖的沙灘，整整一個月，沒碰過任何電子設備。沒用多久，把自己的主密碼忘到了九霄雲外。

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

沒關係。

聯繫張三，他保管的密鑰片段是 1-797842b76d80771f04972feb31c66f3927e7183609；趙六，一直替你的班，很高興你能儘快重返崗位，把自己掌握的片段給了你，4-97c77a805cd3d3a30bff7841f3158ea841cd41a611；錢大麻子，收到你給的跑腿費才將自己保管的片段翻出來發給你，5-17da24ad63f7b704baed220839abb215f97d95f4f8。

有了這三個密鑰片段，運行:

$ 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

就這麼簡單，有了 開源 技術加持，你也可以活的像國王一樣滋潤！

自己的安全不是自己一個人的事

密碼管理是當今網路生活必備技能，當然要選擇複雜的密碼，來保證安全性，但這不是全部。來用 Shamir 秘密共享演算法，和他人共同安全的存儲你的密碼吧。

via: https://opensource.com/article/20/6/python-passwords

作者：Moshe Zadka 選題：lujun9972 譯者：silentdawn-zz 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive