算法及时计算，但快速验证计算结果

我想给用户一个随机密钥，要求他在这个密钥上执行算法。算法的计算成本很高。应该不存在已知的解决方法来减少所需的计算时间。而且我应该能够以非常高的成本验证计算值是从我给出的关键字计算出来的。算法及时计算，但快速验证计算结果

有没有适合这种用途的算法？

来源

2014-01-10 Ski

我想你正在描述* public-key cryptography *，其中大整数的因式分解扮演着你引用的算法的角色。我建议求助于你最喜欢的搜索引擎。 –

采取两个大素数。乘以它们。给用户结果并让他找到两个主要因素。 –

您正在寻找NP难题。非常粗略地说，那些很难解决但很容易验证。（大多数需要的不仅仅是一个随机密钥作为输入，但你可以使用该密钥来说，种子一个随机数生成器，用于生成一个图并解决NP-hard图问题。） – borrible

哦，是的，有。比特币例如使用这样的东西，它被称为Proof-of-work system，也看Hashcash。

对不起，我不能帮你实际的代码，但应该有大量的开源资料。对于比特币，根据我的理解，有一个很小的机会来快速完成这个工作证明，但平均来说非常困难。使用普通的电脑将需要不止几十年。

来源

2014-01-10 15:54:26 user2843099

密码学在这里浮现在脑海。取一个数据集A，使用密钥K对它进行加密，结果为B.给用户A和B，要求他恢复K.当然，你必须选择密钥大小和算法，这样才能使这个任务变得切实可行。
或者采取一个简短的随机字符串，如10或20个字符。计算SHA1哈希。给用户散列，并要求他恢复原始字符串。
或分解。给用户两个大素数的产品，并要求他恢复这些因素。

来源

2014-01-10 15:35:22 pentadecagon

算法及时计算，但快速验证计算结果

回答

相关问题