แบบสอบถามเกี่ยวกับโครงสร้างแฮชเอาต์พุต SHA256 เทียบกับเอนโทรปีอินพุต

กำหนดสตริงอินพุตจำนวน N ไบต์ โดยที่บางตำแหน่งไบต์ในสตริงเป็นแบบคงที่/ไม่เปลี่ยนรูป (F Bytes) และตำแหน่งไบต์ที่เหลือสามารถมีค่าใดๆ ตามที่เราต้องการหรือสามารถกำหนดค่า/เปลี่ยนแปลงได้ (V = N-F Bytes)

SHA256(SHA256(N)) = H (256 บิต)

ตอนนี้ กำหนดสตริงอินพุตจำนวน N ไบต์ ค่าของ N, F, V และตำแหน่งที่สามารถเปลี่ยนแปลงได้และที่ไม่สามารถ:

เราจะคำนวณความน่าจะเป็น/สูตรได้อย่างไรว่าสำหรับการกำหนดค่าอย่างน้อย 1 ค่าใน V ค่า H ที่คำนวณได้มี k นำหน้าเป็น 0

เช่น: สำหรับสตริงอินพุตแบบสุ่มขนาด N, N=80, F=40, V=40 (โดยสมมติว่าระบุข้อมูลตำแหน่งด้วย) เราจะทราบ/คำนวณความน่าจะเป็นได้อย่างไรว่าสำหรับการกำหนดค่าอย่างน้อย 1 ค่าใน V k ไบต์แรกของ H คือ 0?

ฉันพยายามค้นหาการวิเคราะห์เกี่ยวกับเรื่องนี้ แต่ไม่พบคำตอบใดๆ ใครสามารถช่วยได้บ้าง

ตามที่กล่าวไว้ก่อนหน้านี้ ตำแหน่งของไบต์คงที่หรือจำนวนของไบต์นั้นไม่สำคัญหากเราคิดว่าผลลัพธ์นั้นถูกสุ่ม

สมมติว่าบิตดังนั้น $v = 8 \cdot V$.

ตอนนี้สำหรับค่าเดียว โอกาสของมันเริ่มต้นด้วย $k$ บิตสามารถนำมาลงเพื่อโอกาสที่หนึ่ง $k$ บิตมีค่าคงที่ ขนาดของแฮชไม่สำคัญ ดังนั้นสำหรับการลองครั้งนี้เป็นเพียง $1 \มากกว่า 2^k$.

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

นั่นหมายความว่าความน่าจะเป็นเท่ากับ 1 ลบโอกาสที่ค่าคงที่ของ $k$ ไม่ได้โยนบิต:

$$1 - \bigg({{2^k-1} \over {2^k}}\bigg)^{2^v} = 1 - (1 - 2^{-k})^{2^v} $$

ตอนนี้ดูเหมือนจะน่ากลัว แต่คุณสามารถเล่นกับค่า (เล็กน้อย) ได้ ใช้ WolframAlpha.

โปรดทราบว่าหาก $v$ มีขนาดใหญ่กว่า $k$ จากนั้นความน่าจะเป็นจะเข้าสู่ 1 อย่างรวดเร็ว ในขณะที่มันจะเคลื่อนที่อย่างรวดเร็วเป็นศูนย์เมื่อนั้น $k$ กลายเป็นขนาดใหญ่กว่า $v$ - ซึ่งก็สมเหตุสมผลแล้ว พวกมันถูกใช้เป็นเลขยกกำลัง

เนื่องจากเราคิดว่า SHA-256 สุ่มเอาต์พุตแล้ว ดูเหมือนว่าจะไม่เกี่ยวข้องกับเอนโทรปีเลย ซึ่งเป็นตัวนับที่มีขนาด $v$ จะทำงานเช่นเดียวกับการป้อนข้อมูลแบบสุ่ม - ดีกว่าแม้ว่าจะไม่มีโอกาสทำซ้ำก็ตาม