Score:4

จะรับคีย์อย่างปลอดภัยจากรายการของไบต์สุ่มที่เรียงลำดับได้อย่างไร

ธง us

เป็นไปได้หรือไม่ที่จะได้รับคีย์เข้ารหัสที่ปลอดภัยจากอาร์เรย์ของไบต์ที่เรียงลำดับ โดยถือว่าไบต์นั้นถูกสร้างขึ้นในลักษณะที่ปลอดภัย (เช่น จากปรากฏการณ์ควอนตัม)

อะไรคือแนวทางที่ดีที่สุดสำหรับปัญหานี้

Maarten Bodewes avatar
in flag
ฉันคิดว่าค่าไบต์ที่ซ้ำกันได้รับอนุญาตหรือไม่ มิฉะนั้นหลังจาก 256 ไบต์จะเหลือเอนโทรปีเป็นศูนย์ ฉันกำลังพยายามคำนวณว่ามีเอนโทรปีเท่าใดสำหรับจำนวนไบต์ที่ระบุ แต่ล้มเหลว
us flag
ใช่ อนุญาตให้ใช้ค่าที่ซ้ำกันได้ ขอบคุณ
Maarten Bodewes avatar
in flag
ไม่เป็นอะไร. หลังจากที่เราทราบวิธีรับเอนโทรปี 128 บิตด้วยไบต์ที่เรียงลำดับแล้ว คุณสามารถใช้ KDF เพื่อรับคีย์ได้ การเข้ารหัสบางตัวอาจใช้คีย์ที่มีขนาดและรูปแบบใดก็ได้ ดังนั้นคุณสามารถใช้ไบต์โดยตรงได้ในกรณีที่คุณมีเพียงพอ (แต่ฉันอาจใช้ค่าเริ่มต้นเป็น KDF เพื่อความแน่ใจ)
kelalaka avatar
in flag
นี่เป็นปัญหาเกี่ยวกับความน่าจะเป็น เนื่องจากกล่อง 16 กล่องวางหมายเลขตั้งแต่ 0 ถึง 255 เพื่อเพิ่มลำดับและทำซ้ำได้ [ความน่าจะเป็นของการเพิ่มลำดับ](https://www.cut-the-knot.org/Probability/IncreasingSequence.shtml)
kelalaka avatar
in flag
สงสัยต้นตอของปัญหา. แหล่งที่มาคืออะไร ทำไมคุณถึงได้รับลำดับสุ่มที่เพิ่มขึ้น
kelalaka avatar
in flag
เพื่อให้ได้คำตอบที่ชัดเจน คุณต้องกำหนดแหล่งที่มาของไบต์ คุณมีแหล่งที่มาที่เพิ่มลำดับของไบต์หรือแหล่งที่มาสร้างไบต์แบบสุ่มให้คุณ จากนั้นคุณกำลังเรียงลำดับ
Score:4
ธง ru

สมมติว่าคุณรู้ว่าแหล่งที่มาของคุณกำลังสร้าง IID ไบต์ สิ่งที่คุณมีในกรณีนี้คือตัวอย่างจาก การกระจายพหุนาม กับ $k=256$. หากคุณมีความคิดที่ดีเกี่ยวกับความน่าจะเป็นของแต่ละไบต์ (เช่น 1/256 หากมีความน่าจะเป็นเท่ากัน) คุณสามารถคำนวณเอนโทรปีในการแจกแจงซึ่งจะเติบโตไปพร้อมกับ $n$ (ขนาดของอาร์เรย์) ตามที่แนะนำในความคิดเห็น สูตรสำหรับเอนโทรปีมีอยู่ในบทความ Wikipedia

อย่างไรก็ตาม เอนโทรปีของแชนนอนยังคงซ่อนความน่าจะเป็นแต่ละรายการที่เกิดขึ้นบ่อยเกินไปสำหรับคีย์เข้ารหัสที่ดี แต่คุณควรตรวจสอบให้แน่ใจว่าเอนโทรปีขั้นต่ำ $H_\infty$ ค่อนข้างใหญ่กว่าขนาดคีย์ที่ต้องการ สำหรับไบต์ที่เท่าเทียมกันและสำหรับ $256|n$, นี้จะเป็น $$-\log \left(\frac{n!}{\left(\frac n{256}\right)!^{256}}256^{-n}\right) .$$

อีกครั้งนี้จะเติบโตด้วย $n$. เมื่อคุณมีเอนโทรปีขั้นต่ำเพียงพอที่จะรู้สึกสบายแล้ว ให้นับจำนวนไบต์และป้อนเข้าไปในฟังก์ชันการหาค่าหลักที่คุณเลือก

ETA: @fgrieu ขอสูตร min-entropy สำหรับค่าทั่วไปเพิ่มเติมของ $n$. ต่อไปนี้ยุ่งยากกว่า แต่ฉันคิดว่ามันจับค่าโมดอลของพหุนามได้อย่างถูกต้อง สำหรับ $n=256d+r$ กับ $0\le r<256$ สูตรคือ $$-\log \left(\frac{n!}{(d!)^{256-r}((d+1)!)^r}256^{-n}\right) .$$

Paul Uszak avatar
cn flag
เหล่านี้คือ _"เรียงลำดับไบต์"_ ดังนั้นจึงไม่ใช่ I.I.D. ดังนั้นจึงไม่สามารถเท่าเทียมกันได้ แชนนอนง่าย ๆ ใช้ไม่ได้ที่นี่
Daniel S avatar
ru flag
@paul ฉันเข้าใจผิดหรือเปล่า ฉันใช้คำถามเพื่อหมายความว่าไบต์ถูกสร้างขึ้นในลักษณะ IID แล้วจัดเรียง
kelalaka avatar
in flag
ใช่แล้ว.. อาร์เรย์ถูกจัดเรียงและคำถามไม่สามารถตอบได้ทั้งหมด และฉันไม่แน่ใจว่านี่เป็นความอยากรู้อยากเห็นอย่างแท้จริงจาก OP หากเป็นมือใหม่ให้ระวังไว้เสมอว่าอาจเป็น HW
us flag
ขอบคุณสำหรับคำตอบ เหตุผลที่ฉันถามคือฉันสามารถเข้าถึงเครื่องควอนตัมที่ฉันหวังว่าจะใช้สร้างคีย์การเข้ารหัส แต่ผลลัพธ์ที่ฉันได้รับจากการถ่ายภาพซ้ำๆ นั้นมีผลลัพธ์ที่เรียงลำดับ ไม่ใช่ตามลำดับเวลา
kelalaka avatar
in flag
ถ้าเรียงผลจะสุ่มได้อย่างไร
us flag
ตามที่ @DanielS สังเกต การสุ่มไม่ได้มาจากตัวเลข แต่มาจากความถี่ที่เกิดขึ้น อย่างน้อยนั่นเป็นวิธีที่ฉันเข้าใจคำตอบของเขา
Daniel S avatar
ru flag
@fgrieu: ขอบคุณสำหรับ eagle eyes: ฉันละเว้นแฟคทอเรียลซึ่งสร้างความแตกต่างอย่างเห็นได้ชัด! โปรดทราบว่าสูตรนี้เก็บเฉพาะ $256|n$ เท่านั้น เป็นบันทึกของความน่าจะเป็นโมดอลในการแจกแจงพหุนาม
fgrieu avatar
ng flag
@Daniel: ฉันเห็นด้วยกับสูตรใหม่สำหรับ $n=0$ และ $n=256$ อย่างน้อย (สำหรับ $0$ และ $364.004$ บิตของ min-entropy) สูตรสำหรับค่ากลางจะดี

โพสต์คำตอบ

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