จะสร้างวงจรสำหรับ SHA-256 ได้อย่างไร?

ด้วยอัลกอริทึมของฟังก์ชันแฮช จะแปลงเป็นวงจรได้อย่างไร

สิ่งสำคัญที่สุดคือเราต้องการระบุปัญหาให้ดีขึ้นก่อน

• ฟังก์ชันแฮชอะไร
• เราต้องการวงจรสำหรับฟังก์ชันแฮชแบบเต็มและอินพุตความยาวคงที่ [ซึ่งดูเหมือนจะตรงกับคำถามที่สุด] หรือสำหรับบางส่วนของแฮช [เช่น รอบของฟังก์ชันแฮชที่มีอินพุตหนึ่งบล็อกข้อความบุนวมใน วัสดุที่เชื่อมโยง, ถ้าฉันอ่านไม่ผิด]?
• ทำไมเราถึงต้องการ "วงจร"? สิ่งนี้จะส่งผลกระทบต่อธรรมชาติของสิ่งที่เราผลิต
  • หลักฐานที่ไม่มีความรู้ที่เกี่ยวข้องกับแฮชตามตัวอย่างที่เชื่อมโยงหรือไม่ ที่จะนำไปสู่การแสดงออกเป็นโซ่ยาวของประตู จำกัด เฉพาะบางพันธุ์ (ที่นี่ เอ็กซ์ออร์, และ, และ INV)
  • ทดสอบว่าบริสุทธิ์แค่ไหน โปรแกรมแก้ปัญหา SAT จัดการกับปัญหาที่เกี่ยวข้องกับแฮช (เช่น ภาพพรีอิมเมจ) ได้หรือไม่ โดยทั่วไป นิพจน์จะถูกจำกัดมากยิ่งขึ้น (ไม่มี XOR) ในทางกลับกัน การปฏิเสธมักจะไม่มีค่าใช้จ่าย
  • การปรับให้เหมาะสมในซิลิคอนหรือ FPGA? โดยปกติจะลึกเกินไปอย่างหมดจด นิพจน์บูลีน จะไร้ประโยชน์ เราจะต้องมีสลักตัวกลาง และเว้นแต่ว่าสิ่งทั้งหมดนั้นถูกวางท่อลึกหรือมีการแฮชที่ผิดปกติอย่างมาก เราจะใช้ตรรกะบางอย่างซ้ำในรอบต่างๆ ฉันจะไม่ครอบคลุมเรื่องนั้น
• เราต้องการผลลัพธ์ในรูปแบบใด สำหรับวงจรบูลีนล้วน รูปแบบส่วนใหญ่จะเป็นตัวแปรตัวเลข ฉันเดาว่า ตัวอย่าง มี 512 อินพุตที่มีหมายเลขตั้งแต่ 0 ถึง 511, 116246 เกท (หนึ่งรายการต่อบรรทัด) แต่ละอันสร้างตัวแปรใหม่หนึ่งตัวสำหรับตัวแปรทั้งหมด 116,758 ตัวและเอาต์พุต 256 ตัว (อาจเป็นตัวแปร 116502 ถึง 116757 ฉันไม่แน่ใจ) ด้วยคำอธิบายนี้ ในสองบรรทัดแรกตามข้อตกลงง่ายๆ ด้านล่างนี้คือหนึ่งประตูต่อหนึ่งบรรทัด โดยฉันเดาว่าสำหรับแต่ละประตู
  • จำนวนอินพุต [1 สำหรับ NOT และ 2 สำหรับอื่นๆ ในตัวอย่าง]
  • จำนวนเอาต์พุต [1 ในตัวอย่าง]
  • รายการอินพุต
  • รายการของเอาต์พุต [หนึ่ง] รายการ
  • ชื่อของเกต [XOR, AND, INV ในตัวอย่าง]

ส่วนที่เหลือเป็นไปตามเทคนิคของมนุษย์ถ้ำในการกินแมมมอธ (ทีละชิ้น) และความคืบหน้าจากที่นั่น (เครื่องมือ)

เราใช้อัลกอริทึมทีละขั้นตอน คลี่แต่ละลูป และแสดงแต่ละขั้นตอนเป็นสมการบูลีน ตัวอย่างเช่น หากตัวแปรทั้งหมดเป็นแบบ 32 บิต (เช่นใน SHA-256):

• คำสั่งเช่น C = A^B สามารถแปลเป็นตัวแปรใหม่ 32 ตัวสำหรับ C เอาต์พุตโดยเกต 32 XOR ซึ่งต้องใช้ 32 บรรทัด เราจำเป็นต้องติดตามตัวเลขที่กำหนดตัวแปรใหม่ที่กำหนดให้ ค.
• E = C + D ต้องใช้ตัวแปรกลาง บรรทัดจึงมากขึ้น เราต้องการ 30 บวกเต็มและจากนั้นสองตัวที่เรียบง่าย (ไม่มีการดำเนินการสำหรับบิตอื่น ๆ ที่สูงซึ่งจะลดเหลือ XOR หนึ่งตัว ไม่มีการพกพาสำหรับตัวแรกซึ่งลดเป็นหนึ่ง XOR และหนึ่ง AND)
• F = (E<<3)|(E>>29) ไม่จำเป็นต้องมีบรรทัด เพียงกำหนดตัวแปรใหม่สำหรับ อี.

มีเคล็ดลับเล็กน้อยที่บางครั้งสามารถแสดงนิพจน์ที่ง่ายขึ้นได้ แต่สำหรับแฮชที่สนใจในการเข้ารหัส นิพจน์จะยังคงยาว ถ้าไม่ใช่แฮชก็จะอ่อนแอ

เป็นเรื่องง่ายพอสมควรที่จะสร้างโปรแกรมที่ทำสิ่งนี้ตั้งแต่เริ่มต้น และจากประสบการณ์ของฉันนั้นง่ายกว่าการค้นหาและเชี่ยวชาญในสิ่งที่เพียงพอ เครื่องมือที่มีอยู่อาจมีประโยชน์ในการลดความซับซ้อนของนิพจน์โดยอัตโนมัติ แต่สำหรับแฮชการเข้ารหัสส่วนใหญ่ การวิเคราะห์สมการแฮชเพียงเล็กน้อยจะทำให้การทำให้นิพจน์ง่ายขึ้นมากที่สุดเท่าที่จะเป็นไปได้ และอาจให้ผลลัพธ์ที่ดีกว่าเครื่องมืออัตโนมัติ