đưa ra một thuật toán của hàm băm, làm thế nào để chuyển đổi nó thành một mạch?
Quan trọng nhất, trước tiên chúng tôi muốn nói rõ hơn vấn đề
- Hàm băm gì?
- Chúng ta có muốn một mạch cho hàm băm đầy đủ và đầu vào có độ dài cố định [có vẻ phù hợp nhất với câu hỏi] hoặc cho một phần của hàm băm [như một vòng của hàm băm với đầu vào là một khối thông báo được đệm trong vật liệu liên kết, nếu tôi đọc chính xác]?
- Tại sao chúng ta muốn "một mạch"? Điều này sẽ tác động đến bản chất của những gì chúng tôi sản xuất.
- Bằng chứng không có kiến thức liên quan đến hàm băm như trong ví dụ được liên kết? Điều đó sẽ hướng tới một biểu hiện như một chuỗi dài các cổng giới hạn ở một số giống (ở đây XOR, VÀ, và INV)
- Kiểm tra làm thế nào một tinh khiết người giải SAT xử lý giải quyết một số vấn đề liên quan đến hàm băm (như hình ảnh trước)? Biểu thức thường sẽ bị hạn chế nhiều hơn (không có XOR), mặt khác, phủ định thường miễn phí.
- Tối ưu hóa thực hiện trong silicon hoặc FPGA? Điển hình là một quá sâu hoàn toàn biểu thức Boolean sẽ vô dụng, chúng tôi sẽ cần các chốt trung gian và trừ khi toàn bộ nội dung được xử lý sâu hoặc hàm băm cực kỳ bất thường, chúng tôi sẽ có một số logic được sử dụng lại qua các vòng. Tôi sẽ không bao gồm điều đó.
- Chúng ta muốn đầu ra ở dạng nào? Đối với một mạch hoàn toàn Boolean, hầu hết các định dạng sẽ đánh số các biến. tôi đoán ví dụ có 512 đầu vào được đánh số từ 0 đến 511, 116246 cổng (một cổng trên mỗi dòng), mỗi cổng tạo ra một biến mới cho tổng số 116758 biến và 256 đầu ra (có thể là các biến từ 116502 đến 116757, tôi không chắc), với mô tả này trong hai dòng đầu tiên trên một số quy ước đơn giản. Dưới đây là một cổng trên mỗi dòng, tôi đoán cho mỗi cổng
- số lượng đầu vào [1 cho KHÔNG và 2 cho những người khác trong ví dụ]
- số lượng đầu ra [1 trong ví dụ]
- danh sách (các) đầu vào
- danh sách [một] đầu ra
- tên của cổng [XOR, AND, INV trong ví dụ]
Phần còn lại nói chung tuân theo kỹ thuật của người thượng cổ để ăn một con voi ma mút (từng miếng một) và tiến trình từ đó (công cụ).
Chúng tôi thực hiện từng bước thuật toán, hủy kiểm soát từng vòng lặp và biểu thị từng bước dưới dạng phương trình Boolean. Ví dụ: nếu tất cả các biến đều là 32 bit (như trong SHA-256):
- một tuyên bố như
C = A ^ B có thể được dịch thành 32 biến mới cho C, xuất bằng 32 cổng XOR, yêu cầu 32 dòng. Chúng ta cần theo dõi các con số chỉ định các biến mới được gán cho C.
E = C + D yêu cầu các biến trung gian, do đó nhiều dòng hơn. Chúng tôi cần 30 bộ cộng đầy đủ, và sau đó là hai cái đơn giản hóa (không thực hiện đối với bit có thứ tự cao, do đó giảm xuống còn một XOR; không thực hiện đối với bit đầu tiên, do đó giảm xuống một XOR và một AND).F = (E<<3)|(E>>29) sẽ không yêu cầu dòng nào, chỉ cần gán lại các biến cho e.
Có một số thủ thuật đôi khi có thể nhận được các biểu thức đơn giản hơn, nhưng đối với các hàm băm quan tâm về mật mã, biểu thức sẽ tồn tại lâu. Nếu không, hàm băm sẽ yếu.
Thật dễ dàng để tạo một chương trình thực hiện điều này từ đầu và theo kinh nghiệm của tôi, điều đó dễ dàng hơn là tìm và thành thạo một thứ gì đó phù hợp. Các công cụ hiện có có thể hữu ích để tự động đơn giản hóa các biểu thức, nhưng đối với hầu hết các hàm băm mật mã, một phân tích nhỏ về phương trình của hàm băm sẽ nhận được hầu hết các đơn giản hóa có thể nhận được và có thể cho kết quả tốt hơn các công cụ tự động.
