糾正密鑰加密的錯誤

Question

假設我有一個方案從N不同的輸入中派生出密鑰。每個輸入可能不完全安全（f.x.錯誤的密碼），但組合它們是安全的。執行此操作的簡單方法是按順序連接所有輸入，並使用散列作爲結果。

現在我想允許從N輸入中只給出N-1的密鑰派生（或更確切地說是密鑰解密）。一個簡單的方法來做到這一點是生成一個隨機密鑰K，產生N臨時密鑰對輸入的不同N子集，每一個輸入缺失（即Hash(input_{1}, ..., input_{N-1}), Hash(input_{0}, input_{2}, ..., input_{N-1}), Hash(input_{0}, input_{1}, input_{3},..., input_{N-1}), ..., Hash(input_{0}, ..., input_{N-2})），然後與每個N鍵加密K和存儲所有的結果。

現在我想要一個廣義的解決方案，我可以在N輸入中使用K解密密鑰。要擴大上述方案的天真方式需要存儲（N選擇N-K）值，這很快就變得不可行。

是否有一個良好的算法對於這一點，這並不意味着這多少存儲空間？

我曾經想過一個辦法使用類似Shamir的祕密共享方案，但想不出一個好辦法，因爲投入是固定的。

Answer 1

糾錯碼是解決問題最直接的方法。但是，它們並不是特別容易實施。

最好的辦法是使用Reed Solomon Code。當您第一次獲得密碼時，還可以計算代碼所需的冗餘並存儲它。如果要重新計算密鑰，請使用冗餘來糾正錯誤或缺少的輸入。

Answer 2

一種方法是生成一個純粹的隨機密鑰（或者通過散列所有輸入，如果因爲某種原因想要避免RNG），使用k-n門限方案進行分割並且對每個共享使用個人密碼輸入（例如，通過PBKDF2發送100000次迭代，然後使用AES-CTR/HMAC加密/ MAC）。這比存儲散列子集需要更少的存儲空間;大致N *（共享大小+鹽大小+ MAC尺寸）

Answer 3

而不是簡單地允許一些差錯出大量的投入的，則應該劃分輸入成組，並允許每個組中的錯誤的某些數量。如果你在64個輸入中允許有4個錯誤，那麼你將不得不擁有15249024個加密密鑰，但是如果你把它分成兩組，每組允許兩個錯誤，那麼你只需要有1984個加密密鑰。

一旦你從每個組解密的密鑰信息，然後用其作爲輸入解密，你最終要的關鍵。

此外，從各組獲得的密鑰必須不能相比，你最終要的關鍵微不足道。不要簡單地將256位密鑰分解爲8個32位密鑰片。這樣做會讓那些能夠解密這些關鍵部分中的7個的人在最後一部分上嘗試進行暴力攻擊。如果你想訪問256位密鑰，那麼你必須使用256位密鑰來完成整個過程。

Answer 4

要加密/創建：

取N個輸入。以良好/安全的方式將每個塊轉換爲塊。使用Reed Solomon從N塊組合中生成M個冗餘塊。您現在有N + M個塊，其中只需要總共N個來生成原始N個塊。

使用N個塊來加密或創建安全密鑰。

如果第一個存儲加密密鑰和M個冗餘塊。如果第二個，只存儲M個冗餘塊。

要解密/檢索：

取N - R的正確的輸入塊，其中R = < M.結合將它們與您存儲創建原始N個塊的冗餘塊。使用原始的N個塊來解密或創建安全密鑰。

（感謝https://stackoverflow.com/users/492020/giacomo-verticale：這基本上是他/她說了什麼，但我覺得有點更明確的/更清晰）

Answer 5

Shamir's share secret是當你要分割在多個共享一個祕密，使用techinique這樣只有最小k個部分的組合才能揭示初始祕密。如果您不確定啓動程序的正確性，並且您想驗證這一點，則可以使用verifiable secret sharing。兩者均基於多項式插值