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

Sunday, November 21, 2010, 11:45 PM

Cryptography

Linear Algebra

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

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

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

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

ให้

$P = C = Z_{26}$
$K = {(a, b) \in Z_{26}^{2} : gcd (a, 26) = 1}$

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

\begin{aligned} e_{k} (x) & = a x + b (\mod 26) \\ d_{k} (y) & = a^{- 1} (y - b) (\mod 26) \end{aligned}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

φ (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}$

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

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

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

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

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

\begin{aligned} 1^{- 1} & \equiv 1 (\mod 26) \\ 3^{- 1} & \equiv 9 (\mod 26) \\ 5^{- 1} & \equiv 21 (\mod 26) \\ 7^{- 1} & \equiv 15 (\mod 26) \\ 11^{- 1} & \equiv 19 (\mod 26) \\ 17^{- 1} & \equiv 23 (\mod 26) \\ 25^{- 1} & \equiv 25 (\mod 26) \end{aligned}

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

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

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

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

ที่บรรทัด 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) \neq 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}$ ก็ได้ แต่มันง่ายไปแถมถ้าเราเปลี่ยนจาก $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