如何為 SHA-256 生成電路？

在Steven Goldfeder的“SHA-256 的布爾電路”中，作者給出了 SHA-256 的布爾電路。我覺得這個方法很複雜。

請問如何為雜湊函式構造布爾電路？我的意思是，給定雜湊函式的算法，如何將其轉換為文章中的電路？

給定雜湊函式的算法，如何將其轉換為電路？

最重要的是，我們首先要更好地說明問題

• 什麼雜湊函式？

• 我們想要一個完整的散列函式電路和一個固定長度的輸入嗎$$ which seem best matches the question $$，或者對於雜湊的某些部分如果我沒看錯的話，就像一輪雜湊函式，在[連結的材料中輸入一個填充的消息塊]？

• 為什麼我們想要“電路”？這將影響我們生產的產品的性質。

  • 像連結範例中那樣涉及雜湊的零知識證明？這將指向一個表達式，作為一個長鏈門，僅限於某些品種（這裡XOR，AND和INV）
  • 測試純SAT 求解器如何處理與雜湊相關的一些問題（如原像）？表達式通常會受到更多限制（沒有 XOR），另一方面，否定通常是免費的。
  • 在矽片或 FPGA 中優化實現？通常，一個過深的純布爾表達式是沒有用的，我們需要中間鎖存器，除非整個事情是深度流水線或散列非常不規則，否則我們將在輪次中重用一些邏輯。我不會涵蓋那個。

• 我們想要以什麼形式輸出？對於純布爾電路，大多數格式都會對變數進行編號。我猜這個例子有 512 個輸入，編號從 0 到 511，116246 個門（每行一個），每個門產生一個新變數，總共 116758 個變數，以及 256 個輸出（可能是變數 116502 到 116757，我不確定） ，根據一些簡單的約定，在前兩行中對此進行了描述。下面是每行一個門，我猜每個

  • 輸入數量$$ 1 for NOT and 2 for others in the example $$
  • 輸出數量$$ 1 in the example $$
  • 輸入列表
  • 名單$$ one $$輸出
  • 門的名字$$ XOR, AND, INV in the example $$

其餘的大致遵循穴居人吃猛獁象的技術（一次一塊）以及從那裡取得的進展（工具）。

我們一步一步地採用算法，展開每個循環，並將每個步驟表示為布爾方程。例如，如果所有變數都是 32 位的（如在 SHA-256 中）：

• 像這樣的語句C = A ^ B可以翻譯成 C 的 32 個新變數，由 32 個 XOR 門輸出，需要 32 行。我們需要跟踪指定分配給 的新變數的數字C。
• E = C + D需要中間變數，因此需要更多的行。我們需要 30 個全加器，然後是兩個簡化的加法器（高位沒有進位，因此減少到一個 XOR；第一個沒有進位，因此減少到一個 XOR 和一個 AND）。
• F = (E<<3)|(E>>29)不需要任何行，只需重新分配E.

有一些技巧有時可以得到更簡單的表達式，但對於密碼學興趣的雜湊，表達式將保持很長。如果不是，則雜湊將很弱。

從頭開始製作一個程序相當容易，而且根據我的經驗，這比找到和掌握足夠的東西要容易。現有工具可用於自動簡化表達式，但對於大多數加密散列，對散列方程的一點分析將獲得盡可能多的簡化，並且可能比自動化工具提供更好的結果。

引用自：https://crypto.stackexchange.com/questions/95167