纠错密钥加密
假设我有一个从 N 个不同输入派生密钥的方案。每个输入可能并不完全安全（例如错误的密码），但组合起来它们是安全的。执行此操作的简单方法是将所有输入按顺序连接并使用哈希作为结果。
现在我想允许仅在 N 输入中给出 N-1 进行密钥派生（或者更确切地说是密钥解密）。实现此目的的一个简单方法是生成随机密钥 K，从输入的不同 N 子集中生成 N 个临时密钥，每个密钥都包含缺少一个输入（即 Hash(input_{1}, ..., input_{N-1})、Hash(input_{0}, input_{2}, ..., input_{N-1}) , 哈希(输入_{0}, 输入_{1}, 输入_{3},..., 输入_{N-1}), ..., 哈希(输入_{0}, ..., 输入_{N-2 })) 然后使用 N 密钥中的每一个对 K 进行加密并存储所有结果。
现在我想要一个通用的解决方案，我可以使用 N 输入中的 K 来解密密钥。扩展上述方案的简单方法需要存储（N 选择NK）值，这很快就变得不可行。
是否有一个好的算法，不需要这么多的存储空间？
我想过一种使用沙米尔秘密共享方案之类的方法，但想不出一个好方法，因为输入是固定的。
Say I have a scheme that derives a key from N different inputs. Each of the inputs may not be completely secure (f.x. bad passwords) but in combination they are secure. The simple way to do this is to concatenate all of the inputs in order and use a hash as a result.
Now I want to allow key-derivation (or rather key-decryption) given only N-1 out of the N inputs. A simple way to do this is to generate a random key K, generate N temporary keys out of different N subsets of the input, each with one input missing (i.e. 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})) then encrypt K with each of the N keys and store all of the results.
Now I want to a generalized solution, where I can decrypt the key using K out of N inputs. The naive way to expand the scheme above requires storing (N choose N-K) values, which quickly becomes infeasible.
Is there a good algorithm for this, that does not entail this much storage?
I have thought about a way to use something like Shamir's Secret Sharing Scheme, but cannot think of a good way, since the inputs are fixed.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
纠错码是解决问题最直接的方法。然而，它们并不是特别容易实施。
最好的方法是使用里德所罗门代码。当您第一次导出密码时，您还可以计算代码所需的冗余并存储它。当您想要重新计算密钥时，您可以使用冗余来纠正错误或丢失的输入。
Error Correcting Codes are the most direct way to deal with the problem. They are not, however, particularly easy to implement.
The best approach would be using a Reed Solomon Code. When you derive the password for the first time you also calculate the redundancy required by the code and store it. When you want to recalculate the key you use the redundancy to correct the wrong or missing inputs.
加密/创建：
获取 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：这基本上就是他的/她说，但我认为更明确/更清楚。）
To encrypt / create:
Take the N inputs. Turn each into a block in a good /secure way. Use Reed Solomon to generate M redundancy blocks from the N block combination. You now have N+M blocks, of which you need only a total of N to generate the original N blocks.
Use the N blocks to encrypt or create a secure key.
If the first, store the encrypted key and the M redundancy blocks. If the second, store only the M redundancy blocks.
To decrypt / retrieve:
Take N - R correct input blocks, where R =< M. Combine them with the redundancy blocks you stored to create the original N blocks. Use the original N blocks to decrypt or create the secure key.
(Thanks to https://stackoverflow.com/users/492020/giacomo-verticale : This is essentially what he/she said, but I think a little more explicit / clearer.)
Shamir 的共享秘密 是一种当您想要将秘密分割为多个共享时使用的技术这样只有最少 k 个部分的组合才能揭示最初的秘密。如果您不确定发起者的正确性并且想要验证这一点，请使用可验证的秘密共享 .两者均基于多项式插值
Shamir's share secret is a techinique that is used when you want to split a secret in multiple shares such that only a combination of minimum k parts would reveal the intial secret. If you are not sure about the correctness of the initiator and you want to verify this you use verifiable secret sharing .both are based to polynomial interpolation
一种方法是生成一个纯随机密钥（或者通过散列所有输入，如果您出于某种原因想避免 RNG），使用 k-of-n 阈值方案对其进行分割，并使用单独的密钥对每个共享进行加密密码输入（例如，通过 PBKDF2 发送 100000 次迭代，然后使用 AES-CTR/HMAC 加密/MAC）。这比存储哈希子集需要更少的存储空间；大约 N * （共享大小 + salt 大小 + MAC 大小）
One approach would be to generate a purely random key (or by hashing all of the inputs, if you want to avoid an RNG for some reason), split it using a k-of-n threshold scheme, and encrypt each share using the individual password inputs (eg send them through PBKDF2 with 100000 iterations and then encrypt/MAC with AES-CTR/HMAC). This would require less storage than storing hash subsets; roughly N * (share size + salt size + MAC size)
您不应简单地允许大量输入中出现一些错误，而应将输入分为几组，并在每组中允许一定数量的错误。如果您允许 64 个输入中有 4 个错误，那么您必须拥有 15,249,024 个加密密钥，但如果您将其分为两组，每组 32 个，每组允许两个错误，那么您只需要拥有 1984 个加密密钥。
一旦您解密了每个组的密钥信息，然后将其用作您最终想要的解密密钥的输入。
此外，与您最终想要的密钥相比，从每个组获取的密钥一定不能微不足道。不要简单地将 256 位密钥分解为 8 个 32 位密钥。这样做将允许能够解密其中 7 个关键部分的人尝试对最后一个部分进行暴力攻击。如果您想要访问 256 位密钥，那么您必须在整个过程中使用 256 位密钥。
Rather than simply allowing a few errors out of a large number of inputs, you should divide the inputs up into groups and allow some number of errors in each group. If you were to allow 4 errors out of 64 inputs then you would have to have 15,249,024 encrypted keys, but if you break that up into two groups of 32, allowing two errors per group then you would only need to have 1984 encrypted keys.
Once you have decrypted the key information from each group then use that as input into decrypting key that you ultimately want.
Also, the keys acquired from each group must not be trivial in comparison to the key that you ultimately want. Do not simply break up a 256 bit key into 8 32bit key pieces. Doing this would allow someone that could decrypt 7 of those key pieces to attempt a bruteforce attack on the last piece. if you want access to a 256 bit key, then you must work with 256 bit keys for the whole procedure.