การเข้ารหัสลับแบบสัมพรรค

Sunday, November 21, 2010, 11:45 PM

Cryptography

Linear Algebra

จากสองตอนที่ผ่านมา เราได้เห็นว่าการเข้ารหัสลับแบบเลื่อนนั้น เป็นกรณีพิเศษกรณีหนึ่งในการเข้ารหัสลับแบบจับคู่

แต่อาจเนื่องด้วยความยุ่งยากของการต้องใช้กุญแจขนาดใหญ่เพื่อไขรหัสให้ได้ บวกกับความง่ายเกินไปของการเข้ารหัสแบบเลื่อน

ทำให้เกิดการเข้ารหัสแบบสัมพรรค (affine cipher) ซึ่งดัดแปลงเพิ่มเติมจากการเข้ารหัสลับแบบเลื่อนขึ้นมา

เขียนอธิบายเป็นภาษาทั่วไปยากหน่อย วิธีนี้ดูสมการแล้วน่าจะเข้าใจง่ายกว่าจริงๆ

ให้

$P = C = \mathbb{Z}_{26}$
$K = \lbrace (a, b) \in \mathbb{Z}_{26}^2 : \gcd(a, 26) = 1 \rbrace$

สำหรับ $k = (a, b) \in K$ จะกล่าวว่า

\[\begin{align} e_k(x) &= ax + b \pmod{26} \\ d_k(y) &= a^{-1}(y - b) \pmod{26} \end{align}\]

อย่างที่บอกไว้ว่าวิธีนี้ดัดแปลงเพิ่มเติมจากการเข้ารหัสแบบเลื่อนแค่นิดเดียว

ลองมองผ่านๆ จะเห็นว่าวิธีการนี้เพียงแค่เพิ่ม $a$ เข้าไปคูณกับ $x$ ก่อนที่จะบวกด้วย $b$ เท่านั้นเอง

รู้แค่นี้ก็เอาไปใช้ได้แล้ว แต่ถ้าอยากใช้อย่างไม่ผิดพลาด ลองมาวิเคราะห์อะไรที่มันยากๆ ในนั้นกัน

เริ่มจาก $K = \lbrace (a, b) \in P^2 : \gcd(a, 26) = 1 \rbrace$ หมายความว่ากุญแจที่ใช้นี้ ต้องการตัวแปรเพื่อใช้เข้ารหัส 2 ค่า อันนี้ไม่ยากๆ

แต่จะยากตั้งแต่ตรงนี้ไปคือ $\gcd(a, 26) = 1$ หรือ $a$ ต้องเป็นจำนวนเฉพาะสัมพัทธ์กับ 26 เท่านั้น

เพราะถ้าไม่เป็นเช่นนั้นแล้ว ฟังก์ชัน $e_k$ จะไม่เป็น 1-1 ส่งผลให้ไม่สามารถใช้ $d_k$ ถอดรหัสย้อนกลับมาหาข้อความที่ถูกต้องได้

ลองพิจารณาตัวอย่าง สมมติให้ $a = 2, b = 0$ ข้อความ iamaboy จะแปลงได้เป็น QAYACCW

ซึ่งเห็นได้ว่า b, o ทั้งสองตัวแปลงเป็น C เหมือนกัน ทำให้การแปลง QAYACCW กลับเป็นข้อความตั้งต้น iamaboy นั้นไม่สามารถทำได้ (หรือไม่งั้นก็ต้องอาศัยการตีความเพิ่มว่าตัวอักษรตัวไหนคืออะไรกันแน่)

ตรงนี้เขียนเป็นทฤษฎีบทได้คือ $ax \equiv b \pmod{m}$ จะมีคำตอบเฉพาะสำหรับ $x \in \mathbb{Z}_m$ เมื่อ $b \in \mathbb{Z}_m$ ก็ต่อเมื่อ $\gcd(a, m) = 1$

สำหรับวิธีพิสูจน์จะขอละไว้ก่อน เนื่องจากใช้ความรู้ด้านทฤษฎีจำนวนที่ผมยังไม่ค่อยถนัดนัก

ขั้นต่อไปที่เราจะพิจารณา นั่นคือมี $a$ ใดบ้างที่เหลือให้เราใช้ได้

จาก $26 = 2 \times 13$ ดังนั้นเลขที่ใช้ได้จะต้องไม่มี $2$ กับ $13$ เป็นตัวประกอบ

ดังนั้นค่า $a$ สำหรับ $\mathbb{Z}_{26}$ ที่เป็นไปได้ คือ $\lbrace 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 25 \rbrace$

เห็นได้ว่าวิธีนี้มี $a$ ที่ใช้ได้อยู่ 12 แบบ ส่วน $b$ ยังเหมือนเดิม 26 แบบ ดังนั้น key space มีขนาด $12 \times 26 = 312$ วิธี (ทำอะไรให้ยุ่งยากตั้งมากมาย แต่ก็ยังไม่ปลอดภัยอยู่ดี …)

ในด้านจำนวนของกุญแจที่เป็นไปได้นี้ ก็มีทฤษฎีบทมารองรับเช่นกัน

สำหรับ $\mathbb{Z}_m$ จำนวนของสมาชิกที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $m$ จะเรียกว่า $\varphi(m)$ ซึ่งหาได้จาก

\[\varphi(m) = \prod_{i=1}^n (p_i^{e_i} - p_i^{e_i-1})\]

เมื่อเราสามารถถอดตัวประกอบของ $m$ ออกมาเป็นจำนวนเฉพาะได้ $n$ ตัว โดย $p_i$ คือจำนวนเฉพาะแต่ละตัว และ $e_i$ คือปริมาณของจำนวนเฉพาะ $p_i$ ตัวนั้นๆ (ไม่พิสูจน์อีกตามเคย ยากส์ส์)

ลองใช้ดีกว่า จากข้างต้น $26 = 2^1 \times 13^1$

ดังนั้น $\varphi(26) = (2^1 - 2^0)(13^1 - 13^0) = (2-1)(13-1) = 12$ ครับ

แต่ปัญหาก็ยังไม่หมดเท่านี้ เพราะแม้เราจะมี $a$ ทั้ง 12 แบบอยู่ในมือแล้ว แต่กลับไปดูด้านบนสุดจะเห็นว่าเราต้องการ $a^{-1}$ อีกด้วย … ถ้านี่เป็นการพิจารณาเลขในชีวิตประจำวัน มันก็ไม่น่ามีปัญหา เช่น $a = 3$ ดังนั้น $a^{-1} = 1/3$ ไม่เห็นยาก

แต่อย่าลืมว่าตอนนี้เรากำลังพิจารณาเลขใน $\mathbb{Z}_{26}$ ซึ่งเรานิยามแค่การบวกและคูณ ไม่ได้นิยามการหารไว้ด้วย

เราจึงต้องใช้สมบัติพื้นฐานที่ว่า $aa^{-1} \equiv a^{-1}a \equiv 1 \pmod{m}$

งานนี้ถึกก่อนได้เปรียบ ลองไล่หาดูเลยว่า $a$ แต่ละตัวที่ได้มานั้น นำไปคูณอะไรแล้ว $\pmod{26}$ เหลือ $1$ (ผลลัพธ์ออกมาดังข้างล่างครับ)

\[\begin{align} 1^{-1} &\equiv 1 \pmod{26} \\ 3^{-1} &\equiv 9 \pmod{26} \\ 5^{-1} &\equiv 21 \pmod{26} \\ 7^{-1} &\equiv 15 \pmod{26} \\ 11^{-1} &\equiv 19 \pmod{26} \\ 17^{-1} &\equiv 23 \pmod{26} \\ 25^{-1} &\equiv 25 \pmod{26} \end{align}\]

และในที่สุด เราก็ทราบเงื่อนไขทั้งหมดเพื่อใช้การเข้ารหัสแบบสัมพรรคอย่างถูกวิธีแล้ว

ต่อไปลองมาเขียนโค้ดกัน!

อย่างที่บอกไปแล้วว่า วิธีนี้ดัดแปลงเพิ่มจากการเข้ารหัสลับแบบเลื่อนเพียงนิดส์เดียว

ดังนั้นเราจะเริ่มด้วยการก๊อปปี้โค้ดเก่ามาเปลี่ยนรายละเอียดครับ (ข้อดีของการเขียนโค้ดให้แก้ง่าย)

ที่บรรทัด 1 เปลี่ยนชื่อ และเพิ่มเงื่อนไขของการใช้กุญแจเป็น 2 องค์ประกอบ
ที่บรรทัด 5 เปลี่ยน logic ของการคำนวณให้เข้ากับสมการคณิตศาสตร์ที่พึ่งเรียนไป

def affine(pain_text, a, b):
    cipher_text = ''
    for i in range(len(pain_text)):
        char_num = lower_to_number(pain_text[i])
        char_num = a*char_num + b
        char_num %= 26
        cipher_text += number_to_upper(char_num)
    return cipher_text

เราก็จะได้โค้ดของการเข้ารหัสลับแบบสัมพรรคมาใช้อย่างถูไถละครับ

ก่อนที่เราจะเขียนโค้ดส่วนนี้ต่อ สังเกตุว่า $\gcd(a, 26) = 1$ เท่านั้น

ดังนั้น เราจึงต้องเขียนป้องกันไม่ให้ $a$ ที่รับมามี $\gcd(a, 26) \ne 1$ ด้วย

วิธีที่จะเขียนตรวจสอบ $\gcd(a, 26)$ นั้นก็มีหลายวิธีครับ ตั้งแต่ไล่หาค่าเองด้วยมือตามด้านบนที่ทำมาแล้ว ไปจนถึงการใช้คณิตศาสตร์มาช่วยเลย

สำหรับวิธีที่จะนำเสนอนี้ เป็นการใช้ขั้นตอนวิธีของยูคลิด โดยอยู่ในรูป recursion ครับ

def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

เรียบร้อยแล้วก็กลับมาปรับปรุงโค้ดของเราครับ

def affine(pain_text, a, b):
    if gcd(26, a) != 1:
        raise ValueError('gcd(26, {}) must be 1'.format(a))
    cipher_text = ''
    for i in range(len(pain_text)):
        char_num = lower_to_number(pain_text[i])
        char_num = a*char_num + b
        char_num %= 26
        cipher_text += number_to_upper(char_num)
    return cipher_text

สองตอนที่แล้วปล่อยให้คิดวิธีเขียน decode เอง แต่คราวนี้ค่อนข้างยากเพราะมีเรื่องของ $a^{-1}$ ด้วย

เราอาจจะใช้ตัวแปรดิกชันนารีเพื่อจับคู่ $a$ กับ $a^{-1}$ ก็ได้ แต่มันง่ายไปแถมถ้าเราเปลี่ยนจาก $\mathbb{Z}_{26}$ เป็นอย่างอื่นแล้วก็ต้องมาหาคู่อินเวอร์สใหม่

ถ้าอย่างนั้นแล้วเรามาดูฟังก์ชันที่มันสนุกๆ กันดีกว่าครับ

แต่ก่อนอื่น เพื่อให้เรื่องต่างๆ เป็นระเบียบและจัดการง่าย เราจะสร้างไฟล์ใหม่ที่ชื่อว่า cryptologic.py ครับ

และจากตอนที่ผ่านๆ มา จะเห็นว่ามีฟังก์ชันสั้นๆ ที่ไม่ใช่ฟังก์ชันที่เราจะเรียกใช้โดยตรง จะใช้แค่ประกอบในฟังก์ชันหลัก

เช่นพวก lower_to_number(text), gcd(a,b) เราย้ายมันมาไว้ที่นี่ครับ

แล้วจึงเพิ่มโค้ดอันแสนสนุกสนานนี้เข้าไปร่วมกับเพื่อนๆ ครับ

def mul_inv(a, b, s=0, t=1):
    if a%b == 0:
        if b == 1:
            return t
        else:
            raise ValueError('no inverse')
    else:
        return mul_inv(b, a%b, t, (s-t*(a//b))%26)

จะเห็นว่า ฟังก์ชันนี้เป็น recursion อีกแล้ว และที่บรรทัดแรกนั้นมีตัวแปร 4 ตัว คือ a, b, s, t

แต่เวลาจะใช้งานนั้น s เริ่มที่ 0 และ t เริ่มที่ 1 เสมอ หลังจากนั้นจึงค่อยเปลี่ยนแปลงค่าของมันโดยส่งค่าที่คำนวณระหว่างทางเข้าไป

เราจึงสามารถกำหนด s = 0 และ t = 1 ได้ตั้งแต่เริ่ม และเรียกใช้ฟังก์ชันโดยใส่ค่าเพียง a กับ b ก็พอ

อย่าลืมเขียนโค้ด import ที่ไฟล์ encrypt.py เพื่อเรียกใช้งานฟังก์ชันที่อยู่ต่างไฟล์ออกไปนะครับ

from cryptologic import *

ส่วนการโค้ดรับรหัสลับเพื่อนำมาถอดเป็นข้อความก็จะเป็นดังนี้ครับ (ไฟล์ใหม่ decrypt.py ครับ)

def affine(cipher_text, a, b):
    a_inv = mul_inv(26, a)
    pain_text = ''
    for i in range(len(cipher_text)):
        char_num = upper_to_number(cipher_text[i])
        char_num = a_inv*(char_num - b)
        char_num %= 26
        pain_text += number_to_lower(char_num)
    return pain_text