ดัชนีความบังเอิญร่วมกัน

ขณะนี้ฉันกำลังพยายามแก้ Caesar Cipher โดยไม่รู้กุญแจ ฉันจะแก้ไขปัญหาโดยใช้ดัชนีความบังเอิญร่วมกันเพื่อพิจารณาว่าอะไรคือกุญแจสำคัญ ฉันได้แก้ไขปัญหาด้วยวิธีอื่นโดยใช้คุณสมบัติทางสถิติของภาษาอังกฤษแล้ว แต่ฉันก็อยากลองใช้วิธีนี้เช่นกัน

ฉันเพิ่งพบว่าดัชนีของความบังเอิญและดัชนีของความบังเอิญร่วมกันนั้นเป็นสองสิ่งที่แตกต่างกัน เมื่อใช้การเข้ารหัสแบบตัวอักษรเดียว ดัชนีความบังเอิญจะส่งกลับ ~0.067 เสมอ (สำหรับภาษาอังกฤษ) อย่างไรก็ตาม ดูเหมือนจะไม่เป็นเช่นนั้นจากสิ่งที่ฉันได้รับ

ฉันต้องการความช่วยเหลือในการทำความเข้าใจวิธีสร้างอัลกอริทึมเพื่อระบุดัชนีร่วมของความบังเอิญตามสูตร

สูตร MIC

เนื่องจาก ป้อนคำอธิบายรูปภาพที่นี่ โดยที่ fi คือการเกิดขึ้นของตัวอักษรที่ ith ในตัวอักษรและ N คือความยาวของข้อความและ qi+k

จากสิ่งที่ฉันเข้าใจ (ฉันวิชาคณิตศาสตร์แย่มาก) ฉันต้องวนซ้ำ i 0-25 และรับดัชนีของดัชนีความบังเอิญร่วมกันสูงสุดในกลุ่ม 25 และนั่นจะทำให้ฉันมีกุญแจสำหรับการเข้ารหัส ในการทำเช่นนั้น ฉันต้องคูณ pi ด้วย qi+k อย่างไรก็ตาม หาก pi มีค่าประมาณเท่ากับ qi+k สำหรับ i ทั้งหมด ไม่ได้หมายความว่า pi? ถ้าอย่างนั้น สมการก็เป็นผลบวกของพายกำลังสองไม่ใช่หรือ?


encryption algorithm math caesar-cipher
person Jon K    schedule 11.07.2020    source แหล่งที่มา
comment
ฉันถือว่า p_i เป็นความถี่ที่คาดหวังของตัวอักษร (กำหนดโดยการวิเคราะห์ความถี่ของข้อความภาษาอังกฤษ) ฉันคิดว่าคุณพลาดบางคำไป ฉันคิดว่าข้อความต้นฉบับบอกว่าคุณต้องค้นหา k (ตั้งแต่ 0 ถึง 25) โดยที่แต่ละ p_i มีค่าประมาณเท่ากับ q_{i+k} สำหรับแต่ละ i ดัชนีความบังเอิญร่วมกันคือการวัดว่าเวกเตอร์สองตัวอยู่ใกล้กันแค่ไหน (โดยพื้นฐานแล้วเทียบเท่ากับความคล้ายคลึงของโคไซน์) ดังนั้น k ที่มี MIC สูงที่สุดจึงเป็นตัวเลือกที่ดีสำหรับคีย์ต้นฉบับ   -  person Paul Hankin    schedule 11.07.2020
comment
ใช่ ฉันคิดว่าคุณคิดถูกที่จะหา k (0-25) โดยที่ p_i แต่ละตัวมีค่าประมาณเท่ากับ q_{i+k} สำหรับแต่ละ i แม้ว่าคำถามจะระบุเพียง i ทั้งหมดก็ตาม ฉันไม่แน่ใจว่าฉันพลาดรายละเอียดจากคำถามอีกต่อไปหรือไม่ (หวังว่าจะไม่) แต่ฉันติดอยู่เล็กน้อยในการเริ่มต้นรับ MIC สำหรับแต่ละ k   -  person Jon K    schedule 11.07.2020
comment
ปัญหาเฉพาะของคุณคืออะไร? คุณได้คำนวณความถี่ 26 q[i] แล้วหรือยัง? คุณมีความถี่ตัวอักษร (ฉันเดาว่าภาษาอังกฤษ) p[i] หรือไม่?   -  person Paul Hankin    schedule 11.07.2020
comment
ในโค้ดของฉัน ฉันจัดการเพื่อรับความถี่ตัวอักษรของอักขระทั้งหมดสำหรับแต่ละคีย์ตั้งแต่ 0 ถึง 25 แต่ฉันไม่แน่ใจว่าฉันจะรับ MIC จากที่นั่นได้อย่างไร ฉันคิดว่า p_i q_{i+k} หมายถึง (f_{i+k} / N) * (f_{i+k} /N) สรุป แต่ฉันรู้ว่ามันเป็นสิ่งเดียวกัน (และไม่ได้ให้ฉัน ปิด MIC ต่อไป) ดังนั้นฉันต้องคิดผิดที่พยายามสร้างสูตรเพื่อคำนวณ MIC สำหรับแต่ละ k   -  person Jon K    schedule 11.07.2020
comment
อืม p[i] ควรเป็นเวกเตอร์ที่มีลักษณะประมาณ [0.082, 0.014, 0.028, ...] (ความถี่ตัวอักษรสำหรับภาษาอังกฤษจาก en.wikipedia.org/wiki/) q[i] ควรเป็นเวกเตอร์ที่เก็บความถี่ที่สังเกตได้ของตัวอักษรแต่ละตัวในไซเฟอร์เท็กซ์ หารด้วยความยาวของไซเฟอร์เท็กซ์   -  person Paul Hankin    schedule 11.07.2020
comment
MIC[k] คือ sum(p[i] * q[(i+k)%26] for i in range(26)) ในหลาม   -  person Paul Hankin    schedule 11.07.2020
comment
สูตรที่ให้มาถูกต้องแล้ว ขอบคุณมาก! @พอลแฮนกิน   -  person Jon K    schedule 12.07.2020

คำตอบ (1)


arrow_upward
0
arrow_downward

ขอบคุณมากสำหรับ Paul Hankin สำหรับการชี้แจง p_i ในกรณีนี้จริงๆ แล้วไม่ใช่ q_{i+k} แต่เป็นความน่าจะเป็นที่จะเกิดขึ้นของตัวอักษรแต่ละตัวในภาษาอังกฤษ (ซึ่งได้รับการแก้ไขแล้ว) และ q_{i+k} หมายถึงการเกิดขึ้นของตัวอักษรแต่ละตัวที่ถูกเลื่อนด้วยกุญแจ ในไซเฟอร์เท็กซ์

คำตอบของ Paul โดยที่ MIC[k] คือ sum(p[i] * q[(i+k)%26] for i in range(26)) ถูกต้อง - ผลลัพธ์จากสมการจะต้องหารด้วย N เพื่อให้ได้ดัชนีความบังเอิญร่วมกัน

person Jon K    schedule 12.07.2020