如何为SHA-256生成电路？

Question

在的“sha-256布尔电路”中，作者给出了一个用于SHA-256的布尔电路.我觉得这个方法很复杂。

请问如何构造散列函数的布尔电路？我的意思是，给出一个散列函数的算法，如何像本文一样把它转换成一个电路？

Answer 1

给出了一个散列函数的算法，如何将其转换成一个电路？

最重要的是，我们首先要更好地陈述这个问题。

• 什么哈希函数？
• 我们想要一个完整的哈希函数和一个固定长度的输入电路，还是用于散列的某些部分(例如，如果我正确地读取了链结材料中的一个填充消息块，就像一个带有输入的哈希函数)？
• 为什么我们想要“一个电路”？这将影响我们生产的产品的性质。
  • 包含散列的零知识证明，如链接示例中的那样？这将指向一个表达式，它是一个限制于某些品种的长链门(在这里是异或、和和反转 )。
  • 测试纯卫星解算器如何处理与哈希相关的问题(比如预图像)？表达式通常会受到更多的限制(没有XOR)，另一方面，否定通常是免费的。
  • 硅或FPGA的优化实现？通常，过于深入的纯布尔表达式将是无用的，我们将需要中间锁，除非整个事情是深流水线或杂凑非常不规则，我们将有一些逻辑重用在各个回合。我不会报道这件事。

• 我们想要什么形式的输出？对于纯粹的布尔电路，大多数格式都会对变量进行编号。我猜示例有512个输入，编号从0到511,116246个门(每行一个)，为总共116758个变量生成一个新变量，以及256个输出(可能是116502到116757，我不确定)，每一个简单约定在前两行中描述了这一点。下面是每一行一个门，我猜每个都是这样
  • 输入数
  • 产出数量
  • 投入清单(S)
  • 产出清单(S)
  • 大门的名字

其余的则大致遵循穴居人吃猛犸象的技术(一次吃一大块)和从那里取得的进步(工具)。

我们将算法一步一步地进行，展开每个循环，并将每一步表示为布尔方程。例如，如果所有变量都是32位(如SHA-256中的)：

• 像C = A ^ B这样的语句可以转换为C的32个新变量，由32个异或门输出，需要32行。我们需要跟踪指定分配给C的新变量的数字。
• E = C + D需要中间变量，因此需要更多行。我们需要30 满加法器，然后是两个简化的(对于高oder位不执行，从而减少到一个异或；对于第一个没有进位，从而减少到一个异或和一个和)。
• F = (E<<3)|(E>>29)不需要行，只需要为E重新分配变量。

有些技巧有时可以得到更简单的表达式，但对于密码学方面的兴趣，表达式将保持较长的长度。如果不是的话，哈希就会很弱。

从零开始制作这样的程序是相当容易的，根据我的经验，这比找到和掌握足够的东西更容易。现有的工具可以自动简化表达式，但是对于大多数密码散列的分析，对哈希方程的分析将得到最简单的结果，这是可能的，并且可能比自动化工具提供更好的结果。