國王的秘密：如何保護你的主密碼
很多人使用密碼管理器來保密存儲自己在用的各種密碼。密碼管理器的關鍵環(huán)節(jié)之一是主密碼，主密碼保護著所有其它密碼。這種情況下，主密碼本身就是風險所在。任何知道你的主密碼的人，都可以視你的密碼保護若無物，暢行無阻。自然而然，為了保證主密碼的安全性，你會選用很難想到的密碼，把它牢記在腦子里，并做所有其他你應該做的事情。
但是萬一主密碼泄露了或者忘記了，后果是什么?也許你去了個心儀的島上旅行上個把月，沒有現(xiàn)代技術覆蓋，在開心戲水之后享用美味菠蘿的時刻，突然記不清自己的密碼是什么了。是“山巔一寺一壺酒”?還是“一去二三里，煙村四五家”?反正當時選密碼的時候感覺渾身都是機靈，現(xiàn)在則后悔當初何必作繭自縛。
當然，你不會把自己的主密碼告訴其它任何人，因為這是密碼管理的首要原則。有沒有其它變通的辦法，免除這種難以承受的密碼之重?
試試 Shamir 秘密共享算法(Shamir's Secret Sharing)，這是一種可以將保密內(nèi)容進行分塊保存，且只能將片段拼合才能恢復保密內(nèi)容的算法。
先分別通過一個古代的和一個現(xiàn)代的故事，看看 Shamir 秘密共享算法究竟是怎么回事吧。
這些故事的隱含前提是你對密碼學有起碼的了解，必要的話，你可以先溫習一下 密碼學與公鑰基礎設施引論。
一個古代關于加解密的故事
古代某國，國王有個大秘密，很大很大的秘密：
- 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"))
大到連他自己的孩子都不能輕易信任。他有五個子女，但他知道前路危機重重。他的孩子需要在他百年之后用這個秘密來保衛(wèi)國家，而國王又不能忍受自己的孩子在他們還記得自己的時候就知道這些秘密，尤其是這種狀態(tài)可能要持續(xù)幾十年。
所以，國王動用大力魔術，將這個秘密分為了五個部分。他知道，可能有一兩個孩子不會遵從他的遺囑，但絕對不會同時有三個或三個以上會這樣：
- from mod import Mod
- from os import urandom
國王精通 有限域 和 隨機 魔法，當然，對他來說，使用巨蟒分割這個秘密也是小菜一碟。
第一步是選擇一個大質(zhì)數(shù)——第 13 個 梅森質(zhì)數(shù)(2**521 - 1)，他讓人把這個數(shù)鑄造在巨鼎上，擺放在大殿上：
- P = 2**521 - 1
但這不是要保密的秘密：這只是 公開數(shù)據(jù)。
國王知道，如果 P 是一個質(zhì)數(shù)，用 P 對數(shù)字取模，就形成了一個數(shù)學 場：在場中可以自由進行加、減、乘、除運算。當然，做除法運算時，除數(shù)不能為 0。
國王日理萬機，方便起見，他在做模運算時使用了 PyPI 中的 mod 模塊，這個模塊實現(xiàn)了各種模數(shù)運算算法。
他確認過，自己的秘密比 P 要短：
- secret < P
- TRUE
將秘密轉(zhuǎn)換為 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 ...。
雖然有第三方模塊可以計算多項式的值，但那并不是針對有限域內(nèi)的運算的，所以，國王還得親自操刀，寫出計算多項式的代碼：
- 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)
正如國王所慮，不是每個孩子都正直守信。其中有兩個孩子，在他尸骨未寒的時候，就想從自己掌握的秘密片段中窺出些什么，但窮極所能，終無所獲。另外三個孩子聽說了這個事，合力將這兩人永遠驅(qū)逐：
- del shards[2]
- del shards[3]
二十年彈指一揮間，奉先王遺命，三個孩子將合力恢復出先王的大秘密。他們將各自的秘密片段拼合在一起：
- retrieved = list(shards.values())
然后是 40 天沒日沒夜的苦干。這是個大工程，他們雖然都懂些 Python，但都不如前國王精通。
最終，揭示秘密的時刻到了。
用于反算秘密的代碼基于 拉格朗日差值，它利用多項式在 n 個非 0 位置的值，來計算其在 0 處的值。前面的 n 指的是多項式的階數(shù)。這個過程的原理是，可以為一個多項式找到一個顯示方程，使其滿足：其在 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 天能算出結(jié)果已經(jīng)夠快了。雪上加霜的是，他們只能利用五個秘密片段中的三個來完成這個運算，這讓他們?nèi)f分緊張：
- retrieved_secret = retrieve_original(retrieved)
后事如何?
- retrieved_secret == secret
- TRUE
數(shù)學這個魔術的優(yōu)美之處就在于它每一次都是那么靠譜，無一例外。國王的孩子們，曾經(jīng)的孩童，而今已是壯年，足以理解先王的初衷，并以先王的錦囊妙計保衛(wèi)了國家，并繼之以繁榮昌盛!
關于 Shamir 秘密共享算法的現(xiàn)代故事
現(xiàn)代，很多人都對類似的大秘密苦不堪言：密碼管理器的主密碼!幾乎沒有誰能有足夠信任的人去完全托付自己最深的秘密，好消息是，找到至少有三個不會串通起來搞鬼的五人組不是個太困難的事。
同樣是在現(xiàn)代，比較幸運的是，我們不必再像國王那樣自己動手分割要守護的秘密。拜現(xiàn)代 開源 技術所賜，這都可以使用現(xià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
這確實是個非常牛的主密碼：long legs travel fast，絕不能把它完整的托付給任何人!那就把五個片段分別交給還比較可靠的伙伴，張三、李四、王五、趙六和錢大麻子。
- 把 1 給張三。
- 把 2 給李四。
- 把 3 給王五。
- 把 4 給趙六。
- 把 5 給錢大麻子。
然后，你開啟你的愜意之旅，整整一個月，流連于海邊溫暖的沙灘，整整一個月，沒碰過任何電子設備。沒用多久，把自己的主密碼忘到了九霄云外。
李四和王五也在和你一起旅行，你托付給他們保管的密鑰片段保存的好好的，在他們各自的密碼管理器中，但不幸的是，他們和你一樣，也忘了自己的 主密碼。
沒關系。
聯(lián)系張三，他保管的密鑰片段是 1-797842b76d80771f04972feb31c66f3927e7183609;趙六，一直替你的班，很高興你能盡快重返崗位，把自己掌握的片段給了你，4-97c77a805cd3d3a30bff7841f3158ea841cd41a611;錢大麻子，收到你給的跑腿費才將自己保管的片段翻出來發(fā)給你，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
就這么簡單，有了 開源 技術加持，你也可以活的像國王一樣滋潤!
自己的安全不是自己一個人的事
密碼管理是當今網(wǎng)絡生活必備技能，當然要選擇復雜的密碼，來保證安全性，但這不是全部。來用 Shamir 秘密共享算法，和他人共同安全的存儲你的密碼吧。
