有没有计算机就可以计算的简单哈希函数吗？

#1 楼

好吧，根据合理的参数以及可以手工可靠地进行计算的结果，您可能可以计算中等大小组中的模块化指数（例如，对于中等$ n $而言，例如$ Z_n $）。我认为通过重复平方求幂是可行的。

可能更实用的方法是像MD5一样的ad hoc混淆扩散原语。您需要使输入足够大，以使手工进行详尽的搜索变得不切实际（我认为应该做到32位吗？），然后使回合函数足够简单，以至于可以手工进行计算，但在经验上具有良好的冲突-抵抗性。最后，应用Merkle-Damgaard进行“几轮”回合。

我希望这与随机的加密同学一起合理地工作。如果您要与Adi Shamir对抗，您可能会被搞砸。

编辑：对于亲自承诺计划，您可以完全摆脱哈希函数。只需在折叠纸上写一串随机位，然后将其交给您的伴侣来提交这些位即可。但是更有趣的情况是通过监狱墙，通过电话或通过互联网进行此操作……那么您真的需要一些数学上的东西。

让我们以监狱墙为例：您想将另一个整数$ x $提交给另一名囚犯，并且您没有计算资源，但可以通过敲击（无纸）进行通信。我将执行以下操作：选择要提交的64位数字$ x $。确保您不能将其分解（它可能是素数，但是手动验证素数将是乏味的）。然后选择另一个较大的64位数字$ y $，这也很难手动考虑。

现在计算$ p = xy $（简单）并将$ p $发送给您的好友。如果$ x $和$ y $都难以分解，则$ p $也是如此，因此他无法从$ p $中提取$ x $或$ y $。现在显示，您发送$ x $和$ y $;他会验证$ p = xy $，并且$ x $是较小的整数。

重要的是，两者都是64位（或大小都相同），以防止在提交后$ p = x'（k y）$时更改为$ x'$。当然，如果$ x $和$ y $是素数，则不会发生这种情况，但是手动生成大素数并不容易。

#2 楼

我不知道在没有计算机的情况下可以轻松执行的任何安全加密哈希函数。如果找不到哈希函数，建议您使用随机预言。随机预言是哈希函数尝试近似的构造。在没有计算机的情况下实现随机预言非常简单。您只需要一张纸，一支笔和一个四分之一。

假设您需要一个随机的oracle，它将所有二进制字符串映射到8位输出。
$$ RO：\ {0，1 \} ^ {0 \ text {或} 1 \ text {或} 2 \ text {或} ... \ text {或} k} \ rightarrow \ {0 ，1 \} ^ 8 $$

问某人一个二进制输入字符串：纸返回相应的输出。
如果此输入不在纸上，则将其四分之一翻转8次（头为1，尾为0）来为其生成输出。在纸上写下新的输入/输出对。

几次输入后，您的纸应该看起来像：
您应该开始遇到冲突的16个输入。

#3 楼

我认为还没有提到基于RC4的结构，用一两副扑克牌或自制纸牌来实现将是微不足道的。它只有模块化的求和和交换，并且只有两个状态变量i和j :)

它很弱，但没有计算器就不应该破解。

编辑：是的，该消息将用于种子密码，流输出的选定长度是哈希。可以通过掷硬币或在甲板上乱码来生成随机数，这样我们就可以为相同的消息获得唯一的哈希值。每个块都播种一个RC4实例，该+下一个块的输出用于密钥下一个。最后一个实例用于生成哈希。

我想知道这种非标准结构已经变得多么不安全，特别是考虑到需要抗碰撞性。

编辑2：a相关的RC4-Hash文件：


在本文中，我们提出了一个新的哈希函数RC4-Hash，并声称它安全且非常快。此哈希函数基于RC4的简单结构。提出的哈希函数生成
可变大小的哈希输出（就像一系列哈希函数，例如SHA
系列）。它的结构不同于许多众所周知的hash
函数的结构。由于其全新的内部结构和巨大的内部状态
（大约1700位），它可以抵抗所有通用的
攻击以及Wang等人的路径中断攻击。

#4 楼

如何使用类似于Zobrist哈希的东西并通过硬币翻转生成查找表？

假设您要提交一个64位整数，并且能够提供查找表

将硬币翻转256 x 64次，每次翻转2秒需要9.1个小时，因此您可能不想每天都这样做：)可能有64个人在9分钟内并行执行此操作。

结果是64个随机的256位整数$ r_0，r_1，...，r_ {63} $。要提交64位值$ v $，请以二进制（$ i_n $$
v = 2 ^ {i_0} + 2 ^ { i_1} + 2 ^ {i_2} + ... + 2 ^ {i_n}
$$

并将哈希值$ h（v）$计算为
$$
h（v）= r_ {i_0} \ oplus r_ {i_1} \ oplus r_ {i_2} \ oplus ... \ oplus r_ {i_n}
$$
另一方。

要提交布尔值，您可能需要为$ v $生成63个随机位，然后选择第64位将承诺编码为奇偶校验。

实际上两者各方可以生成自己的查找表并进行交换，它们可以通过xorin合并或彼此附加。这应该减少恶意表的可能性。

这是基于以下可能不正确的假设：


给出$ v $，很容易计算$ h（v）$
给出$ h（v）$很难恢复$ v $
该表是合法的，并且值在mod 2意义上是“线性”独立的，因此不可能发生冲突（不确定手动检查它很容易，而没有模拟它的可能性）

我认为类似的算法被用于秘密共享，同态加密或相关的东西。自然，可以根据需要调整使用的值64和256。我忘记了“反转” $ h（v）$的工作量。

编辑：将“ 256个随机的64位整数”修复为“ 64个随机的256位整数”
编辑2：这可以通过从每个$ r $中找到64个“独立”位，形成64 x 64个“线性”方程（模2）并求解$ \ mathbf {A} \ vec {x} = \ vec {b来解决} $？可能要花费$ O（n ^ 3）$的时间，在这种情况下，n为64（高斯消去）。 h（v）$只是$ O（n）$。但是$ r $需要有足够的位才能确信它们是“独立的”，即使是随机生成的也是如此。

评论

---

$ \ begingroup $
可能不需付出太多努力就可以对256 x 64矩阵“ r”应用高斯消除：/大脑目前还不太配合。
$ \ endgroup $
– NikoNyrh
16年5月5日在18:58

---

$ \ begingroup $
如上面评论中指出的，高斯消除允许找到原像（如果有），这意味着它不是抗碰撞的。
$ \ endgroup $
–fgrieu♦
16年1月6日在16:39

---

$ \ begingroup $
是的，但是O（n ^ 3）对于较大的实例来说非常繁琐。不确定满足“没有任何简单的方法（手动）找到碰撞”条件应该达到多少。
$ \ endgroup $
– NikoNyrh
16年1月6日在21:11

---

#5 楼

下列简单的“校验”算法通常用于检测意外错误。
以下算法是“位置敏感的”，使它们能够检测意外交换连续2位数字的常见错误（一个简单的校验和加上的数字-无法检测到。）

以增加的复杂度（和增加发现冲突的能力）的顺序：用于计算最终校验位的算法。 （但是它只有1位数字，因此您将在3条消息后期望发生冲突，并在第10条消息的“最佳”情况下保证发生冲突）。

Luhn mod N算法（可以是适用于计算“校验位”，该校验位可以是任意数量的十进制数字或任意数量的二进制位。 las，故意从已知消息中构造冲突很容易-只需交换消息中奇数位置的任何两位数字即可；或消息中偶数位置的任何两位数字。
具有足够位数的Fletcher校验和（也许是Fletcher-64吗？）。

要计算Fletcher校验和，我们开始于：


初始化主校验和P1 = 0，而简单的辅助校验和S2 =1。
将消息散列成“块”。
（Fletcher-64使用32位块，但也许像3个字母的块那样用手更容易处理A = 01和Z = 26，所以块ZAB变为十进制260102）。
对于每个块：在继续下一个块之前，将块添加到简单的辅助校验和，然后（使其对位置敏感）将辅助校验和添加到主校验和。
P1和S2总结消息。对于您的演示，也许您可​​以将{P1 concatenate S2}直接用作简单的散列，跳过“进一步的计算”步骤。
Fletcher校验和与加密安全的哈希值相去甚远，但对于快速的纸笔演示来说可能就足够了。

#6 楼

几个世纪以前，科学家使用七字谜词公开证明他们何时发现了某些东西，却没有确切透露他们发现了什么。基本上，这是一个句子中使用了多少个独特字符的计数。该方法不会像SHA-256这样的加密摘要生成固定长度的字符串，但是它们可以用笔和纸来写。

创建一个描述您要提交的事实的独特句子。按字母顺序对所有字符进行排序，以使它们的顺序丢失，但字符数保持不变。发布按字母顺序排列的字符列表。

示例：

今天在今年5月20日的第一天，二十二十我发布了fuzxxl在堆栈交换上发布的问题的答案关于如何使用字谜来证明语句的存在

a16，b3，c3，d5，e21，f4，g2，h7，i6，j0，k1，l2，m4，n13，o12， p3，q1，r5，s11，t23，u5，v1，w5，x4，y8，z1

#7 楼

很抱歉发送垃圾邮件，但这是一个有趣而实用的主题：)

我认为手动准备GSM的A5 / 1算法是可行的，方法是准备大约40至50个1和0或80总共达到100个（假设状态的64位中大约有50％是1 s和50％的0 s）。 + 23 = 64），显示的值例如是蒸汽输出的128位。也许应该丢弃前128位或256位，以更好地隐藏内部状态，并使找到冲突的成本更高。我也不知道它的像前电阻。其他（临时性的）基于LFSR的系统将更易于仿真，但不会那么安全。

#8 楼

免责声明：这不是数学/密码哈希函数，但它是一种单向承诺方案，确实具有一些密码属性（图像还原，抗碰撞）：

在一张纸，签字，然后撕纸，
确保撕裂将文本分成2部分。然后将另一半移交给另一方。

验证“哈希” ，您需要两半，并检查它们是否匹配。在分子水平上，它最终是安全的。当然，它既不灵活，也不可扩展，但可以很好地用作有关承诺方案的CS课程的示例。