纠正密钥加密的错误

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。两者均基于多项式插值