在網上看到一篇講門限密碼的blog，講挺好的，但個人感覺有一些細節部分缺失，自己再補充一些。
鏈接
（如何有條件的話，動手畫個圖會幫助自己理清思路。）

背景

大家都看過諜戰片，傳遞消息的時候為了防止線人叛變，往往會將消息切分成多部分進行傳遞，即使有個別內鬼，也無法解析出消息的含義。當然，這樣的壞處也是顯而易見的，如果內鬼叛變，自己人也無法或者消息的內容。

基于此，門限密碼也應運而生了，其目的在于保證只有收到m個消息及以上接收方才能正確的計算出消息。
換句話說，老大發出n個消息，只有m個以上特工叛變，敵方才能得到的秘密；同理，只要有m個以上的特工順利到達，消息就能夠被順利的解析。
這樣的問題就被稱做(m,n)門限。

解決方案

有了這個idea，如何實現它呢？
首先，我們有n個特工，門限為m，則存在如下約束：

• 約束1：只要收到m個以上的消息就能解析出加密數據。
• 約束2：收到不足m個消息則不能解析出加密數據。

那么，我們有以下幾個待求解問題：

• 一個完整的數據應該切成幾片？
• 每個數據片應該分給幾個特工？

從簡單的開始，假定所有特工攜帶相同數目的數據塊且不能有兩個不同的數據分塊由相同的特工們投遞。
根據約束1，每個數據片只需要放在n-m+1個特工上即可實現。
（此時有m-1個特工沒有數據片，此時無論m怎么取，總能獲得一個帶有數據片的特工。

滿足了約束1、下一步我們將嘗試用上述規則滿足約束2。
對于n個特工，n-m+1個碎片，總共有C(n-m+1,n)種分配方法。
我們暫時假定，分配方法的數量就表示著完整數據的切片數量。

• 首先證明C(n-m+1,n)符合約束2：
  因為C(n-m+1,n)覆蓋了所有的排列組合方式，所以對于m-1及以下，總存在一個秘鑰分片是m-1個特工所沒有的。（例如存在分塊k，其分配方式是第m號特工攜帶，1~m-1不攜帶，此時不違反約束1.
  故約束2滿足。
• 隨后證明數據塊數目不能大于C(n-m+1,n):
  很顯然，如果切片數量大于C(n-m+1,n)，則系統必會出現兩個不同的數據塊，以同樣的方式被n個特工攜帶，失去了數據分片的意義。
  以下圖門限(5,3)為例子，倘若數據塊數量大于20時必然存在數據塊的分配方式與之前20塊相同。
  (如圖所示，第21塊數據塊的攜帶方式與第1塊相同)

攜帶數據塊 特工1 2 3 21 1 1 1 1 1 2 1 1 0 1 3 1 0 1 1 4 0 1 1 0 5 0 0 0..... 0

• 最后，嘗試證明不能小于C(n-m+1,n):
  缺少的那個數據分片B的攜帶方式將成為一個bug。假設B規定1~m-1號特工不攜帶數據，則選取1到m-1這m-1個特工即可覆蓋所有的數據塊。與約束二矛盾。
  （道理也不復雜，因為只有B這個數據塊是m-1個特工都不具有的。
  （約束1規定某一個數據塊最多只有m-1個特工不攜帶。

至此,我們就完美解決了(m,n)門限的問題了.做法是只需要把密鑰分成C(m-1,n)份，每份擁有n-m+1份拷貝。

實現

有了以上基礎，下一步的問題就是如何切分秘鑰呢？

空間幾何

這是一個十分美的解決辦法.還是先從個上面的(3,5)門限的例子來說把,只要把密鑰編碼成空間中的一個點,每個特工手上拿著一個平面方程.所有特工所持有的平面方程全部都交于一個點.因為只有三個或以上的平面才能交于一個點,所以,只要有三個特工到達,拿出他們手里的平面方程一解,答案就是密鑰.用這種解決辦法,對于(m,n)門限,只要把空間的維數相應的改變成m就可以了。

中國剩余定理

todo

總結

以上是生活随笔為你收集整理的门限密码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。