ฉันมีคำถามเกี่ยวกับการมอบหมายการเขียนโปรแกรมครั้งแรกในหลักสูตรการเข้ารหัสของ Dan Boneh บน Coursera คุณได้รับ ciphertexts 10 รายการที่เข้ารหัสด้วยคีย์เดียวกัน และคุณสามารถคาดเดาได้ว่าข้อความธรรมดาประกอบด้วยตัวอักษรและช่องว่างเท่านั้น
คำใบ้ระบุว่าคุณควรพิจารณาว่าจะเกิดอะไรขึ้นเมื่อช่องว่างถูก xor-ed ด้วยตัวอักษร แนวคิดคือการตรวจสอบว่าส่วนย่อย xor-ed ของชุดค่าผสมไซเฟอร์เท็กซ์ตรงกับตัวอักษรหรือไม่ ซึ่งจะช่วยให้เราสามารถหาคีย์ได้
หากเราพบจดหมาย ฉันคิดว่าเราควรจะสามารถกู้คืนส่วนนั้นของคีย์ได้ ซึ่งตรงกับจดหมายที่เรากำลังดำเนินการอยู่ โดยทำดังต่อไปนี้:
อนุญาต c_sub1 และ c_sub2 เป็นส่วนย่อยของไซเฟอร์เท็กซ์ ค1 และ ค2 ที่เราตรวจสอบและปล่อยให้ m_sub1 และ m_sub2 เป็นส่วนย่อยที่สอดคล้องกันของข้อความธรรมดา หนึ่งใน m_sub1 หรือ m_sub2 ต้องเป็นช่องว่าง ในการหาว่าอันไหน เราลองทำดังนี้:
ทะลึ่ง m_sub1 เป็นช่องว่าง รับส่วนย่อยที่เกี่ยวข้องของคีย์ (k_sub) โดย xor-ing c_sub1 กับ 00100000 (การแสดงเลขฐานสองของถ่านช่องว่าง) k_sub = xor (c_sub1,00100000)และตรวจสอบว่าเข้ารหัสตัวอักษรที่พลิกตัวพิมพ์หรือไม่ (เนื่องจาก xor-ing ที่มีช่องว่างสีขาวจะพลิกตัวพิมพ์) ด้วย k_sub ผลตอบแทน c_sub2ถ้าเป็นเช่นนั้นเราควรรู้ว่า k_sub เป็นส่วนย่อยที่ถูกต้องของคีย์ ถ้าไม่ ให้ลองทำแบบเดียวกันโดยถือว่า m_sub2 เป็นช่องว่าง
ฉันไม่พบข้อผิดพลาดเชิงตรรกะใดๆ ในเหตุผลนั้น แต่การใช้งานของฉันให้วิธีแก้ปัญหาที่ไม่ถูกต้อง และฉันค่อนข้างมั่นใจว่าฉันได้ขจัดความเป็นไปได้ของข้อผิดพลาดอื่นๆ ทั้งหมดแล้ว ใครช่วยบอกฉันทีว่าวิธีนี้ผิดไหม
ตรวจสอบว่าเข้ารหัสตัวอักษรที่พลิกตัวพิมพ์หรือไม่ (เนื่องจาก xor-ing ที่มีช่องว่างสีขาวจะพลิกตัวพิมพ์) ด้วย k_sub ให้ผล c_sub2 หากเป็นเช่นนั้น เราควรรู้ว่า k_sub เป็นส่วนย่อยที่ถูกต้องของคีย์ ถ้าไม่ ให้ลองทำแบบเดียวกันโดยถือว่า m_sub2 เป็นช่องว่าง
ขณะนี้ คุณกำลังจับคู่สตรีมข้อความเข้ารหัสสองรายการ ในขณะที่คุณมี 10 รายการ คุณควรเลือกหนึ่งสตรีมจาก 10 จากนั้นดำเนินการ XOR กับอีก 9 รายการในตำแหน่งเดียวกัน หากสตรีมส่วนใหญ่ส่งกลับตัวอักษร (และไม่มีการผสม XOR ที่ไม่ถูกต้อง - แต่ทดสอบได้ยากกว่า) คุณก็ค่อนข้างแน่ใจว่าอักขระที่เข้ารหัสนั้นเป็นช่องว่าง และคุณสามารถค้นหารหัสตาม XOR ที่คุณดำเนินการในคำตอบของคุณ .
ฉันคิดว่าอาจเป็นกรณีนี้ในการมอบหมายงานของ Boneh แต่ระวังว่าคุณอาจพบชุดข้อความธรรมดาที่รวมกันอาจสร้างจดหมายได้เช่นกัน ดังนั้นคุณจึงไม่สามารถดำเนินการ XOR ด้วยสองสตรีมและตรวจสอบการเดาของคุณด้วยวิธีนั้นได้ ยิ่งคุณมีสตรีมมากเท่าไหร่ คุณก็ยิ่งแน่ใจมากขึ้นเท่านั้น ในตอนท้าย คุณสามารถตรวจสอบได้โดยดูที่ข้อความธรรมดาและ/หรือใช้ทักษะทางภาษาของคุณเพื่อเติมลงในช่องว่าง
ถ้าฉันจำไม่ผิดฉันใช้มันแตกต่างกันเล็กน้อย ฉันใช้หนึ่งสตรีม วนซ้ำกับอักขระทั้งหมดในตัวอักษร (หมายเหตุ: อักขระอินพุตที่เป็นไปได้เรียกว่า "ตัวอักษร" ที่นี่ ฉันไม่ได้หมายถึง ABC) สำหรับแต่ละตำแหน่ง จากนั้น XOR'ed ทั้งสามเข้าด้วยกัน หากสตรีมทั้งหมดให้ผลลัพธ์เป็นตัวอักษร แสดงว่าฉันกดอักขระที่ถูกต้อง สิ่งนี้ช่วยให้คุณจัดการเฉพาะอักขระในตัวอักษร ไม่ใช่ชุดค่าผสม XOR แปลก ๆ
หากพบอักขระหลายตัว ให้ใช้อักขระที่สร้างอักขระที่ใช้มากที่สุดในสตรีมทั้งหมดพร้อมกัน (การวิเคราะห์ความถี่)
หากยังไม่เกิดผลลัพธ์ คุณสามารถลองสตรีมอื่นๆ ได้เช่นกัน (แน่นอนว่าคุณจะต้องเปรียบเทียบสตรีม 2 กับ 8 สตรีมเท่านั้น เนื่องจากคุณได้เปรียบเทียบ #1 และ #2 แล้ว)
ตกลง สมมติว่าเรามีตำแหน่งแรก (ตำแหน่งไม่ได้ระบุในชื่อตัวแปร) และชุดของสตรีม ตอนนี้ให้เราเริ่มต้นด้วยสตรีมแรกและ XOR กับสตรีมอื่น ๆ ทั้งหมดซึ่งแสดงโดย $y$ ที่ไหน $y != 1$.
คุณมีค่าไซเฟอร์เท็กซ์สองค่าที่ประกอบด้วย $c_1 = p_1 \oบวก k$ และ $c_y = p_y \oบวก k$. ดังนั้น XOR'ing ร่วมกันช่วยให้คุณ $r = c_1 \oplus c_y = p_1 \oplus p_y$ (ไม่มีอะไรใหม่ที่นี่). ตอนนี้ถ้าคุณเดา $p_1$ และเรียกมันว่า $p'_1$ คุณจะได้รับ $p'_1 \oplus p_1 \oplus p_y = p'_y$. ตอนนี้ถ้า $p'_y$ เป็นอักขระที่ไม่ถูกต้องอย่างเห็นได้ชัด $p'_1$ เป็นการคาดเดาที่ผิด หากคุณโชคไม่ดี คุณต้องทำการวิเคราะห์ความถี่ของผลลัพธ์ทั้งหมด $p'_y$. แต่จำไว้ว่าคุณสามารถทำได้ด้วย ทั้งหมด $\binom{n+1}2$ คู่ ก่อนที่จะหันไปใช้สิ่งนั้น
เมื่อคุณมี $p'_1 = p_1$ เห็นได้ชัดว่ากุญแจสำคัญคือ XOR ที่มีอักขระไซเฟอร์เท็กซ์: $c_1 \oplus p_1 = k$. ซึ่งหมายความว่าคุณจะต้องวนซ้ำตามตัวอักษรแทนที่จะใช้ปุ่มทั้งหมด และคุณสามารถยกเลิกการลองผิดๆ ได้อย่างรวดเร็ว
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
