EP 7: Homophonic Substitution Cipher

Namtan · July 13, 2022, 2:41am

EP 7: ทุกคนสามารถ คลิกรูปภาพด้านล่าง เพื่อศึกษาวิธีการเข้ารหัสแบบ Homophonic Substitution Cipher

ไม่รู้ทุกคนจะจำได้กันหรือเปล่าว่าใน EP 4 เราได้พาทุกคนไปเข้ารหัสแบบ Simple Substitution Cipher กันมาแล้ว หากใครจำไม่ได้สามารถย้อนกลับไปอ่านกันก่อนได้เลย เพราะว่าใน EP นี้ การเข้ารหัสที่เรานำมาให้ทุกคนได้ทดลองทำกันนั้น เป็นการเข้ารหัสแบบ Substitution Cipher (การเข้ารหัสโดยการแทนที่ตัวอักษร) เช่นกัน แต่เป็นการเข้ารหัสที่มีการเพิ่มตัวอักษรแทนที่ (Cipher Text Alphabet) ให้มากขึ้น! และยากขึ้น! อีกด้วย

ไปเริ่มกันเลย

การเข้ารหัสใน EP นี้ก็คือ “Homophonic Substitution Cipher” เป็นการเข้ารหัส โดยการเเทนที่ตัวอักษรด้วยตัวอักษรหรือตัวเลข ซึ่งไม่ใช่การแทนที่อย่างง่ายแบบ 1 ต่อ 1 แต่เป็นการแทนที่ ที่มีการสร้างตัวอักษรแทนที่ (Cipher Text Alphabet) ให้มากขึ้น โดยสามารถคำนวณจำนวนตัวอักษรแทนที่ได้จากตัวอักษรในข้อความ เช่น ถ้าในข้อความของเรา มีตัว E คิดเป็นร้อยละ 3 ของข้อความทั้งหมดเราสามารถสร้างตัวอักษรแทนที่ E ได้ ทั้งหมด 3 ตัวขึ้นไปได้ หรืออาจจะสร้างตัวอักษรแทนที่ให้ E มากกว่าตัวอักษรธรรมดาอื่นๆ ตามจำนวนที่ต้องการได้ แต่ไม่ควรใช้ ตัวอักษรเพียงตัวเดียวในการแทนที่ E ทั้งหมด เนื่องจากว่า ถ้าเราใช้ตัวอักษรแทนที่ (Cipher Text Alphabet) ตัวเดียวในการแทนที่ตัว E ทั้งหมดในข้อความ จะส่งผลให้มีการใช้ตัวอักษรแทนที่ตัวนั้นเยอะเกินไปในรหัสลับ (ความถี่ในการใช้งานสูง) ทำให้ฝั่งตรงข้ามสามารถคาดเดารูปแบบการเข้ารหัสของเราได้ง่ายขึ้น ดังนั้นเราจึงต้องสร้างตัวอักษรแทนที่ (Cipher Text Alphabet) ให้กับ E มากขึ้น เพื่อหลีกเลี่ยงปัญหานี้

นอกจากนั้นในการเข้ารหัสแบบ Homophonic Substitution Cipher ยังสามารถใช้หลักการ Frequency Analysis มากำหนดเงื่อนไขในการสร้างตาราง Cipher Text Alphabet ได้ โดยการเลือกตัวอักษรที่ถูกใช้งานบ่อย ๆ ในภาษาอังกฤษ อย่าง E, T, A, O, I, N, S, H, R, D, L, U ขึ้นมาเพื่อสร้างตัวอักษรแทนที่ (Cipher Text Alphabet) ให้มากกว่าตัวอักษรธรรมดาอื่น ๆ ใน Plain Text Alphabet

ทีนี้มาถึงตรงนี้หลายคน คงอาจจะสงสัยแล้วว่า ให้ตายเถอะ เงื่อนไขในการสร้างตาราง (Cipher Text Alphabet) เยอะแยะขนาดนี้ เราจะส่งให้คู่สนทนาของเรายังไงหมด และถ้าส่งไปแล้วมันเกิดโดนขโมยล่ะ จะทำยังไง

คำตอบ ก็คือ ก่อนที่ทั้งฝั่งผู้รับและผู้ส่งจะออกปฏิบัติภารกิจ พวกเขาจะต้องมีการตกลงเงื่อนไขในการสร้างตาราง Cipher Text Alphabet กันให้เรียบร้อยก่อน เพื่อให้ทั้งสองฝั่งเข้าใจตรงกัน อย่างเช่น ถ้าในคีย์มีตัวเลข จะให้ตัวเลขที่เหลือต่อจากคีย์ อยู่ในบรรทัดที่ 2 ก่อนตัวอักษรอื่น ๆ เป็นต้น หรือหากในกรณีที่ยังไม่ได้ตกลงเงื่อนไขต่าง ๆ กันให้เรียบร้อย ทางฝั่งที่เข้ารหัส จะสามารถส่งเงื่อนไขต่าง ๆ มาพร้อมกับรหัสลับและคีย์ได้ แต่ !!! ในสงครามจริง เขาคงไม่เขียนเงื่อนไขกันไปแบบโต้ง ๆ บอกหมดหรอกนะ แต่อาจจะมีการส่งไปในรูปแบบของรหัสมอร์ส หรือคลื่นวิทยุ ไปนั่นเอง

เกริ่นมาซะยาวขนาดนี้ ทุกคนอาจจะเบื่อแล้ว เราไปเข้ารหัสกันเถอะ

ทุกคนสามารถ คลิกรูปภาพด้านล่าง เพื่อศึกษาวิธีการเข้ารหัสแบบ Homophonic Substitution Cipher

กำหนดข้อความที่ต้องการเข้ารหัส คือ “THIS IS A SECRET MESSAGE.”
กำหนดคีย์ที่จะใช้ในการเข้ารหัส โดยสามารถกำหนดได้ทั้งตัวอักษรและตัวเลข คือคำว่า “BACKGROUND56789” จากนั้นสร้างตาราง Plain Text Alphabet ขึ้นมาโดยตารางนี้ภายในจะเป็นการเรียงตัวอักษร A-Z ตามลำดับ
สร้างตาราง Cipher Text Alphabet โดยนำคีย์ไว้ที่ตอนต้นของตาราง ดังรูปที่ 1

เมื่อเราใส่คีย์ลงในตารางเรียบร้อยแล้ว ให้ใส่ตัวอักษรภาษาอังกฤษที่เหลือลงไปในตารางตามลำดับเดิม (Alphabetical Order : A-Z) โดยที่ตัดตัวอักษรที่มีอยู่แล้วในคีย์ออก ตัวอย่างเช่น จากตารางรูปที่ 1 หลังจากคีย์ คำว่า BACKGROUND56789 ตัวอักษรถัดมาคือ E เนื่องจาก A, B, C, D เป็นตัวอักษรที่มีอยู่แล้วในคีย์ เป็นต้น

นอกจากนั้น ในตารางรูปที่ 1 จะเห็นว่าเราจะให้ ตัวเลข 0- 4 มาแทรกโดยเป็นการขึ้นแถวใหม่ของตาราง Cipher Text Alphabet (สามารถนำตัวเลขที่เหลือแทรกที่ช่องใดก็ได้ตามเงื่อนไขที่ตกลงกันในตอนแรก ) และตัวอักษรแทนที่ในแถวที่ 3 ของตาราง Cipher Text Alphabet จะอยู่ในคอลัมน์ของ ตัวอักษรอย่าง A, E, I, S, T ซึ่งกำหนดเงื่อนไขในการเพิ่มตัวอักษรแทนที่ จากการนับจำนวนตัวอักษรที่มีอยู่ในข้อความธรรมดาถ้าตัวใดมีจำนวนเกิน 2 ตัวขึ้นไปจะกำหนดตัวอักษรแทนที่เพิ่มให้อีก 2 ตัว รวมทั้งหมดเป็น 3 ตัว

*** รูปแบบการสร้าง Cipher Text Alphabet สามารถกำหนดได้ตามต้องการไม่มีกฏตายตัว แต่จำเป็นที่จะต้องตกลงเงื่อนไขในการสร้างให้ชัดเจน และทั้งฝั่งผู้รับและผู้ส่งจะต้องเข้าใจตรงกัน เพราะคุณจะไม่สามารถถอดรหัสออกมาได้เลยถ้า ตาราง Cipher Text Alphabet ของทั้งสองฝั่งไม่ตรงกัน เหมือนคุณพูดคนละภาษาที่มีทางเข้าใจกันได้นั่นเอง ***

นำตาราง Plain Text Alphabet และ Cipher Text Alphabet มาสร้างรหัสลับ โดยเราจะใช้ตัวอักษรที่อยู่ในตำแหน่งเดียวกันของทั้งสองตารางมาเขียนเป็นรหัสลับ เช่น “T” ให้เขียนเป็น “J” ส่วนตัวอักษรที่มีตัวอักษรแทนที่หลายตัว ให้ใช้เรียงกันไปตามลำดับ เช่น “A” ตัวแรกในข้อความ ให้เขียนเป็น “B” และ “A” ตัวที่สองของข้อความ ให้เขียนเป็น “0” เป็นต้น

Homophonic substitution cipher-2

เมื่อเขียนจนครบเราจะได้ข้อความใหม่ เป็นข้อความที่ถูกเข้ารหัสแล้ว คือ “JUNI2 3BYGC H147W I30OG”

ในการเข้ารหัสลับ เราสามารถเขียนรหัสเรียงติดกัน โดยไม่ต้องเว้นช่องว่างได้ แต่เพื่อให้ง่ายต่อการจำและการเขียน ส่วนใหญ่จึงเขียนเป็นกลุ่มตัวอักษร กลุ่มละ 5 ตัว จำนวนกลุ่มขึ้นอยู่กับจำนวนของตัวอักษรทั้งหมด (n/5)

รีบส่งรหัสลับพร้อมกับคีย์ให้กับกองทัพของคุณโดยเร็ว

เมื่อกองทัพของคุณได้รับรหัสลับ “JUNI2 3BYGC H147W I30OG” และคีย์แล้วสามารถทำตามขั้นตอนด้านล่างเพื่อถอดรหัส ดังนี้

เราจะต้องทราบคีย์ที่ใช้ในการถอดรหัส ในตัวอย่างนี้คือ “BACKGROUND56789” และที่สำคัญคือจะต้องทราบรูปแบบการสร้างตาราง Cipher Text Alphabet ที่ตรงกับฝั่งผู้เข้ารหัสทุกประการ
สร้างตาราง Plain Text Alphabet ขึ้นมา โดยวิธีการสร้างจะเหมือนกับขั้นตอนที่ 2 ของการเข้ารหัส
นำคีย์ไปสร้างตาราง Cipher Text Alphabet โดยให้นำคีย์ไปใส่ไว้ในตอนต้นของตาราง ดังรูปที่ 3 (เงื่อนไขเช่นเดียวกับขั้นตอนที่ 3 ของการเข้ารหัส)

นำรหัส “JUNI2 3BYGC H147W I30OG” ไปเทียบกับ Cipher Text Alphabet แล้วเทียบกับ Plain Text Alphabet จะได้ข้อความก่อนที่จะทำการเข้ารหัสออกมา ดังรูปที่ 4

Homophonic substitution cipher-4

ถอดรหัสและเรียงข้อความออกมาได้เป็น “THIS IS A SECRET MESSAGE.”

เป็นอย่างไรกันบ้าง สำหรับการเข้ารหัสแบบ Homophonic Substitution Cipher ที่เรานำมาเล่ากันใน EP นี้

การเข้ารหัสแบบ Homophonic Substitution Cipher มีความซับซ้อนมากใช่มั้ยล่ะ เพราะเราสามารถออกแบบการเข้ารหัสได้แทบจะทุกขั้นตอนกันเลยทีเดียว แบบนี้เวลาที่จะใช้งานจริง ๆ คงต้องตกลงกับคู่สนทนาของคุณให้ชัดเจน ไม่งั้นคงได้ถอดรหัสกันไม่ถูกแน่นอน แต่ถ้ามีโจรขโมยรหัสลับของเราไป คราวนี้ก็คงแก้ได้ยากมาก ๆ แน่นอนเลย

References

Namtan · July 13, 2022, 3:45am

(อันนี้อาจจะเพิ่มเป็น EP ก่อน EP 7 Homophonic Substitution Cipher หรืออาจลงไปพร้อมกัน )

Cryptanalysis คืออะไร

Cryptanalysis มาจากภาษากรีก kryptós เเปลว่า ซ่อน และ analýein แปลว่า วิเคราะห์ คือกระบวนการวิเคราะห์ระบบข้อมูล เพื่อทำความเข้าใจกับขั้นตอนการทำงาน และศึกษาระบบการเข้ารหัส เพื่อค้นหาจุดอ่อนหรือการรั่วไหลของข้อมูล รวมถึงศึกษาการโจมตีแบบ Side-Channel Attack ซึ่งเป็นลักษณะการโจมตี ที่ผู้โจมตีจะเก็บและใช้ข้อมูลจากการทำงานของระบบเพื่อทำการโจมตี แตกต่างจากการโจมตีแบบทั่วไปที่จำเป็นต้องหาจุดอ่อน หรือช่องโหว่ของระบบก่อนทำการโจมตี

.
ย้อนอ่าน 3 ตอนก่อนหน้า
EP 4: Simple Substitution Cipher - https://bit.ly/3aIvhWD
EP 5: Route Cipher - https://bit.ly/3INH5mZ
EP 6: Nomenclator Cipher ฆ่า Mary Queen of Scots ได้อย่างไร - https://bit.ly/3PnES4j
.

ใน Cryptanalysis มีกระบวนการสำคัญหนึ่งที่เรียกว่า Frequency Analysis คือการศึกษาความถี่ของตัวอักษรหรือกลุ่มของตัวอักษรในข้อความเข้ารหัส ซึ่งกระบวนการนี้เป็นกระบวนการที่สามารถใช้ในโจมตีการเข้ารหัสแบบ Classical Cryptography ได้

การวิเคราะห์ความถี่ของตัวอักษรหรือกลุ่มตัวอักษร จะตั้งอยู่บนพื้นฐานข้อเท็จจริงที่ว่าในภาษาใดก็ตาม มักจะมีตัวอักษรหรือคู่ตัวอักษรที่ถูกใช้งานบ่อย และตัวอักษรที่แทบจะไม่ถูกใช้งานเลย เช่น ในภาษาอังกฤษ ตัวอักษร E, T, A และ O เป็นตัวอักษรที่พบได้บ่อย ต่างจากตัวอักษร Z, Q, X และ J ซึ่งเป็นตัวอักษรที่พบได้น้อย หรือ คู่ตัวอักษรอย่าง TH, ER, ON, และ AN เป็นคู่ตัวอักษรที่พบได้บ่อย เหมือนกับคู่ตัวอักษรที่ทำซ้ำอย่าง SS, EE, TT, และ FF

นอกจากนั้น จากกราฟ Frequency Analysis แสดงให้เห็นว่าตัวอักษรที่ถูกใช้งานบ่อยที่สุดมีอยู่ทั้งสิ้น 12 ตัว คือ E, T, A, O, I, N, S, H, R, D, L, U ตามลำดับ

เหตุผลที่เราอยากให้ทุกคนเข้าใจในเรื่องของ Frequency Analysis นอกจากสาเหตุที่ว่ามันเป็นกระบวนที่สามารถโจมตีการเข้ารหัสแบบ Classical Cryptography ได้แล้วนั้น ยังเป็นเพราะ Frequency Analysis เป็นกระบวนการที่ทำให้การเข้ารหัสหลาย ๆ ตัวถูกพัฒนาขึ้นเพื่อป้องกันการโจมตีของ Frequency Analysis ให้ได้อีกด้วย

ใน EP หน้าที่เราจะพาทุกคนไปรู้จักกับการเข้ารหัสแบบ Homophonic Substitution Cipher การเข้ารหัสที่นำเอาหลักการของ Frequency Analysis มาใช้ จะเป็นอย่างไร ?

References

supanut · July 17, 2022, 9:03am

@Namtan ฝากแก้ไขด้วยครับ

ย้ายไปไว้ตอนท้ายดีไหมครับ ?

ซึ่งไม่ใช่การแทนที่อย่างง่ายแบบ 1 ต่อ 1

สามารถเอา

@Pantitas ตรงภาพอยากให้ในตาราง row 4 column 1 เขียนตัว Y แบบจางๆ ให้รู้ว่าจริงๆ จะต้องมีตัว Y ตรงนี้นะแต่พอดี Y มีซ้ำใน key เลยตัดออก (อาจจะกากบาทแดงๆ ใส่ตัว Y ก็ได้ครับลองออกแบบดู)

@Pantitas ทำภาพใส่ลำดับและสัญลักษณ์ที่แสดงให้เห็นว่ามันจะวน loop ลำดับไปเรื่อยๆ เวลาจะหยิบมันมาแทนที่

Namtan:

นำตาราง Plain Text Alphabet และ Cipher Text Alphabet มาสร้างรหัสลับ โดยเราจะใช้ตัวอักษรที่อยู่ในตำแหน่งเดียวกันของทั้งสองตารางมาเขียนเป็นรหัสลับ เช่น “T” ให้เขียนเป็น “H” ส่วนตัวอักษรที่มีตัวอักษรแทนที่หลายตัว ให้ใช้เรียงกันไปตามลำดับ เช่น “A” ตัวแรกในข้อความ ให้เขียนเป็น “C” และ “A” ตัวที่สองของข้อความ ให้เขียนเป็น “1” เป็นต้น

Pantitas · July 18, 2022, 4:19am

ประโยคนี้ค่อนข้าง งง ค่ะ อ่านวนแล้วยังไม่เข้าใจความหมายค่ะ

Namtan · July 18, 2022, 5:47am

คือว่า ถ้าเป็นตัวอักษรที่มันใช้งานบ่อย อย่างในประโยค ของเรา “THIS IS A SECRET MESSAGE.” จะะเห็นว่า มี ตัว E อยู่ในประโยคหลายตัวเลย ถ้าสมมุติ ว่าเราใช้ T ตัวเดียวในการแทนที่ E ทั้งในข้อความ นั่นหมายความว่า มันจะมีการใช้ T เยอะ (ความถี่ในการใช้ T มันจะสูง) แต่ถ้า เรากำหนด ตัวอักษรอื่น ๆ มาแทนที่ E เพิ่ม เราก็จะใช้ T น้อยลง (ความถี่ในการใช้ T มันจะลดลง) ประมาณนี้จ้า

Pantitas · July 19, 2022, 2:56am

Artwork concept

IMG 1: Cover - แนว ๆ Cryptography การเข้ารหัส (ยังไม่แน่ใจว่าจะออกมาเป็นแบบไหน)
IMG 2: อธิบาย Cryptoanalysis คืออะไร → พูดถึง Frequency analysis ใน description
IMG 3: Frequency analysis คืออะไร
IMG 4: โชว์ graph - Frequency analysis ของการใช้ตัว Alphabet
IMG 5: Ending

Update