输出更大的Poly1305变体？

Question

这是一个相当简单的问题，但答案无处可寻。是否有能提供更大输出(例如32而不是16字节)的Poly散列算法的任何变体？或者，是否有任何研究来讨论常数2^{130}-5的可变性，为什么这个数字是特殊的，或者是否有其他好的替代方案？我知道如果它是一个素数会更好，但是素数都是好的吗(忽略模算术的代价)？或者，我可以两次使用Poly1305和两对不同的(r,s)和级联来生成32字节的散列吗？

Answer 1

\newcommand{FP}{\mathbb F_p}是构建在Poly1305上的身份验证器，它遵循一个通用的结构，通过一个通用的散列和一个伪随机函数来构建Poly1305。因此，至少在理论上，增加字段大小以及输出大小(为了安全起见)是可能的。Poly1305精确地指结构的通用散列部分。它本身就是一个可以在任何字段多项式求值散列上通用定义的\FP。Poly1305的实际细节稍微复杂一些。但关键是，这种结构产生了一个很好的区别--不可预测的哈希。

“问题”来自于将这样的散列转换为MAC，特别是当p是素数时。在最纯的MAC方案中，我们只需在\FP中生成一个PRF值。但是，最实用和最有效的PRF，包括与Poly1305一起使用的AES，反而会生成n-bit字符串。留给我们两个关于p应该有多大的选择: 1)稍微大于2^n，或者2)稍小。Poly1305做了第一选择，这提供了一个很大的优势:消息可以在n-bit块中分解和处理。对于第二个选项，我们需要将输入作为字段元素处理。如果p是素数，这就不方便了。同样，实际的实现细节可能比这更复杂。

最后，要扩大外地规模，就需要相应地调整PRF大小。否则，可能没有重大的安全收益。这意味着我们还需要一个输出空间更大的性能PRF。

Answer 2

为了补充马克·伊隆加的优秀答案，我要指出，Poly1305的效率取决于平台。它涵盖了非常重要的软件空间，其中芯片指令可以包括高度优化的整数/浮点数乘法和加法操作。我相信，Poly1305中的选择非常适合当前芯片的功能。

在更有约束的环境中，可以更好地将多项式求值哈希建立在二进制字段\mathbb F_{2^w}上。这是在伽罗瓦计数器模式中使用的GHASH函数中完成的，尽管通常是在\mathbb F_{2^{128}}上描述的，但是2004年年GHASH纸描述了任何偶数w的GHASH。这也给出了块和字段元素之间的精确匹配，从而证明了普遍性。

在文献中，在测试性能的素数字段上还有其他一些多项式评估散列，其中包括p=2^{127}-1#qcStackCode#和p=2^{64}-59#qcStackCode#。