neizod's speculation

insufficient data for meaningful answer

การเข้ารหัสลับวิจเญอแนร์

Friday, December 3, 2010, 11:16 PM

เราจะเห็นว่าการเข้ารหัสลับในสามตอนที่ผ่านมานั้น จะจับคู่จากตัวอักษรตั้งต้นไปยังรหัสตัวเดิมเสมอ (monoalphabetic)

ซึ่งนั่นส่งผลให้เราใช้วิธีง่ายๆ เช่น การวิเคราะห์ความถี่ตัวอักษรและ/หรือไล่แทนค่าตัวอักษรไปเรื่อยๆ (brute-force) เพื่อทดลองถอดรหัสได้ แม้ว่ามันจะกินเวลาอยู่บ้างก็ตาม

ในปี 1553 จึงได้มีการคิดค้นวิธีเข้ารหัสลับแบบที่อักษรหนึ่งตัวสามารถแปลงเป็นรหัสลับได้หลายแบบ (polyalphabetic) ขึ้นมา ซึ่งนับว่าเป็นรากฐานแนวคิดสำคัญให้กับการเข้ารหัสลับในปัจจุบันเลยทีเดียว

ผู้คิดค้นคือ Giovan Battista Bellaso แต่เนื่องด้วยเหตุผลทางประวัติศาสตร์ในช่วงศตวรรษที่ 19 ทำให้ผู้ที่ได้รับเครดิทกลายเป็น Blaise de Vigenère แทน เราจึงรู้จักชื่อวิธีการเข้ารหัสนี้ว่า การเข้ารหัสแบบวิจเญอแนร์ (Vigenère cipher)

ข้อดีของการเข้ารหัสลับด้วยวิธีนี้คือ เข้ารหัสง่าย แต่โจมตีรหัสยาก (อย่างน้อยถ้าไม่มีคอมพิวเตอร์มาช่วยวิเคราะห์)

ขั้นตอนการเข้ารหัสก็ง่ายเหลือหลายอย่างที่ว่ามา แค่เลือกชุดตัวเลขที่จะใช้เป็นกุญแจมาชุดหนึ่ง แล้วก็เอาอักษรตัวแรกบวกกับเลขในกุญแจอันแรก อักษรตัวที่สองบวกเลขตัวที่สองไปเรื่อยๆ จนเมื่อชุดตัวเลขในกุญแจที่ใช้หมด ก็กลับไปเริ่มเลขตัวแรกในกุญแจใหม่อีกครั้ง ง่ายจริงๆ ให้ดินตายเลย (งั้นไปดูคณิตศาสตร์ก่อนที่จะดิ้นตายดีกว่า 555+)

ให้

  • $P = C = \mathbb{Z}_{26}$
  • $K = \mathbb{Z}_{26}^m$ เมื่อ $m$ คือความยาวของกุญแจที่จะใช้เข้ารหัส

สำหรับ $k \in K$ ที่ $k = (a_1, a_2, \dots, a_m)$ สร้าง $k^* = (a_1, a_2, \dots, a_m, a_1, a_2, \dots)$ ซึ่งเป็นกุญแจที่มีความยาวเป็นอนันต์

และจะได้ว่าการเข้า/ถอดรหัสที่มีความยาว $n$ ตัว เมื่อสนใจตัวอักษรตำแหน่ง $1 \le i \le n$ แต่ละตัว จะได้ว่า

โดยที่ $a_i \in k^*$

จะเห็นว่าวิธีนี้ให้ key space ที่ใหญ่ขึ้นอย่างรวดเร็ว เพียงแค่เพิ่มตัวเลขในกุญแจ ซึ่งคือ $26^m$ นั่นเอง

เช่น เลขในกุญแจเพียงแค่ $5$ ตัวจะสร้าง key space ที่ใหญ่ถึง $26^5 \approx 1.2 \times 10^7$ เลยทีเเดียว


นอกจากนี้ก็ไม่มีอะไรยากแล้ว ไปเอาโค้ดการเข้ารหัสลับแบบเลื่อนมาแก้ไขนิดเดียวก็ใช้ได้แล้วครับ

  • บรรทัด 1 เปลี่ยนชื่อ และเปลี่ยนเงื่อนไขการใช้กุญแจจากแบบเลขตัวเดียว เป็นลิสต์เลขหลายตัว
  • บรรทัด 5 เปลี่ยน logic ของการคำนวน คือให้ใช้เลขในกุญแจตามลำดับที่เปลี่ยนไปเรื่อยๆ
def vigenere(pain_text, key_list):
    cipher_text = ''
    for i in range(len(pain_text)):
        char_num = lower_to_number(pain_text[i])
        char_num += key_list[i%len(key_list)]
        char_num %= 26
        cipher_text += number_to_upper(char_num)
    return cipher_text

จะเห็นว่า ทางคอมพิวเตอร์นั้น เราไม่จำเป็นต้องสร้าง $k^*$ เหมือนทางคณิตศาสตร์ก็ได้ แต่จะใช้ modulo เพื่อวนเรียกใช้เลขที่เราต้องการเมื่อเราใช้เลขในลิสต์หมดครับ

อ๋อ เวลาเรียกฟังก์ชันนี้ขึ้นมาใช้ ตัวแปรด้านหลังต้องพิมพ์เป็นตัวแปรแบบลิสต์อย่างนี้นะครับ

>>> encrypt.vigenere('testvigenerecipher', [4, 25, 7, 12, 0])

ส่วนผลลัพท์จะออกมาเป็นอย่างไร ต้องฝากเป็นการบ้านไว้พร้อมกับการเขียน decrypt ครับ

เจอกันคราวหน้าครับ 😁