KECCAK ทำงานบนสถานะอาร์เรย์ที่เต็มไปด้วยศูนย์อย่างไร?
ฉันพยายามใช้ฟองน้ำใน Java สถานะเริ่มต้นเป็นอาร์เรย์ว่างเปล่า 200 ไบต์ของศูนย์ทั้งหมด ในเอกสารตัวอย่าง KMAC จาก NIST สิ่งต่อไปนี้จะเกิดขึ้น:
(เส้นสีดำคือตัวแบ่งหน้า pdf)
วิธีที่ฉันอ่านสิ่งนี้คือสถานะที่มีเลขศูนย์จำนวนมากถูกส่งไปยัง KECCAK จากนั้นสถานะที่มีข้อมูลสุ่มอย่างเห็นได้ชัดจะถูกส่งกลับ SHA3 / KECCAK เปลี่ยนข้อมูลเปล่าให้เป็นข้อมูลสุ่มหรือไม่? ฉันกำลังถามคำถามที่ถูกต้องที่นี่หรือไม่? ความช่วยเหลือใด ๆ ที่ได้รับการชื่นชม
คำตอบ
ฉันเองพบว่าเอกสาร Keccak.team Psuedo Codeมีประโยชน์มากในการทำความเข้าใจว่า Keccak-p เป็นอย่างไร
ดังที่ DannyNiu กล่าวในความคิดเห็นการเปลี่ยนรูปแบบการเข้ารหัส (ทั้งหมด?) ส่วนใหญ่ใช้ "ค่าคงที่รอบ" ค่าคงที่เหล่านี้ผสมกันในสถานะ Keccak
เอกสารรหัสเทียมให้ค่าคงที่กลมเป็นตาราง:
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
และอธิบายถึงวิธีการใช้งาน ในขั้นตอน iota ของ$n^\text{th}$ Keccak-p รอบ, $n^\text{th}$ ค่าคงที่รอบ $RC[n]$ ได้รับการแนะนำและได้รับ XOR เป็นคำแรกเลนแรก
นอกเหนือจากค่าคงที่รอบแล้วการเปลี่ยนแปลงของ Keccak ยังมีการแพร่กระจายที่ดีมาก: บิตเดียวที่อยู่ในสถานะเริ่มต้นจะมีส่วนอย่างมากต่อบิตเอาต์พุตจำนวนมาก
การรวมกันของทั้งสองหมายความว่าการเรียงสับเปลี่ยน Keccak ของคุณดูสุ่มมาก แน่นอนว่ามันไม่สามารถเปลี่ยนเอนโทรปีเป็นศูนย์ให้เป็นแบบสุ่มได้เนื่องจากไม่มีอัลกอริธึมที่ จำกัด สามารถทำเช่นนั้นได้ แต่เป้าหมายของ Keccak คือการผสมผสานสิ่งต่างๆและทำให้มันเป็นแบบสุ่ม
โดยปกติฟังก์ชันการเรียงสับเปลี่ยนของ Keccak จะแมปอินพุตศูนย์ (บิตทั้งหมดเป็น 0) เข้ากับเอาต์พุตศูนย์หากไม่ใช่สำหรับขั้นตอน iota ซึ่งคำหนึ่งคำของสถานะคือ XORed ด้วยค่าคงที่ที่ไม่ใช่ศูนย์
ประมาณสาม (จาก 24) รอบก็เพียงพอสำหรับการแพร่กระจายอย่างสมบูรณ์นั่นคือทุกบิตของสถานะจะส่งผลต่อบิตอื่น ๆ สามรอบในภายหลัง อาจกล่าวได้ว่าการเปลี่ยนแปลงผสมสถานะแปดครั้งอย่างสมบูรณ์ นั่นหมายความว่าถ้าบิตเดียวคือ 1 มันจะกระจายไปทั่วสถานะอย่างรวดเร็วเพื่อให้ 3 รอบต่อมาประมาณครึ่งหนึ่งของบิตสถานะเป็น 1
ปล่อย $R$เป็นชุดของค่าสถานะซึ่งสามารถเรียกได้อย่างสมเหตุสมผลว่า "การมองปกติ" (ตามคำจำกัดความที่แน่นอนใด ๆ ก็ตาม) เช่นบิตทั้งหมดหรือเกือบทั้งหมดมีค่าเท่ากันหรือรูปแบบบิตสั้น ๆ จะทำซ้ำเป็นประจำ ในบรรดา$2^{1600}$ รัฐผู้ที่อยู่ใน $R$เป็นเศษส่วนเล็กน้อย ไม่น่าเป็นไปได้มากที่รัฐใด ๆ ใน$R$ ถูกแมปลงบนเอาต์พุตด้วย $R$. สิ่งนี้ถือได้ว่า$|R| \ll 2^{800}$ (ดู "ความขัดแย้งวันเกิด")
นั่นหมายความว่าไม่มีอินพุตแบบปกติที่แมปเข้ากับเอาต์พุตที่กำลังมองหาปกติ และความน่าจะเป็นของสถานะที่กำหนดใด ๆ ที่จะแมปกับเอาต์พุตใน$R$ มีความสำคัญเล็กน้อยกล่าวคือผลลัพธ์จะมีลักษณะสุ่มเสมอยกเว้นมีใครบางคนจงใจสร้างอินพุตโดยการคำนวณค่าผกผันของการเรียงสับเปลี่ยน