Cryptography ตอนที่ 4 การเข้ารหัสลับแบบสัมพรรค

จากสองตอนที่ผ่านมา เราได้เห็นว่าการเข้ารหัสลับแบบเลื่อนนั้น เป็นกรณีพิเศษกรณีหนึ่งในการเข้ารหัสลับแบบจับคู่
แต่อาจเนื่องด้วยความยุ่งยากของการต้องใช้กุญแจขนาดใหญ่เพื่อไขรหัสให้ได้ บวกกับความง่ายเกินไปของการเข้ารหัสแบบเลื่อน
ทำให้เกิดการเข้ารหัสแบบสัมพรรค หรือ Affine Cipher ซึ่งดัดแปลงเพิ่มเติมจากการเข้ารหัสลับแบบเลื่อนขึ้นมา
เขียนอธิบายเป็นภาษาทั่วไปยากหน่อย วิธีนี้ดูสมการแล้วน่าจะเข้าใจง่ายกว่าจริงๆ

ให้ P = C = Z₂₆ และให้ K = {(a, b) ใน Z₂₆ | gcd(a, 26) = 1}
สำหรับ K = (a, b) จะกล่าวว่า
e_K(x) = (ax + b) mod 26 และ d_K(y) = a^-1(y - b) mod 26 สำหรับ x, y ที่เป็นสมาชิกของ Z₂₆

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

เริ่มจาก K = {(a, b) ใน Z₂₆ | gcd(a, 26) = 1} หมายความว่ากุญแจที่ใช้นี้ ต้องการตัวแปรเพื่อใช้เข้ารหัส 2 ค่า อันนี้ไม่ยากๆ
แต่จะยากตั้งแต่ตรงนี้ไปคือ gcd(a, 26) = 1 หรือห.ร.ม.ของ a กับ 26 ต้องเป็น 1 เท่านั้น
นั่นก็เพราะว่า ถ้าห.ร.ม.ไม่เท่ากับ 1 แล้ว ฟังก์ชัน e_K จะไม่เป็น 1-1 ส่งผลให้ไม่สามารถใช้ d_K หาข้อความที่ถูกต้องได้
ลองพิจรณาตัวอย่าง สมมติให้ a = 2, b = 0 ข้อความ iamaboy จะแปลงได้เป็น QAYACCW
ซึ่งเห็นได้ว่า b, o ทั้งสองตัวแปลงเป็น C ทำให้แปลง QAYACCW กลับเป็น iamaboy ไม่ได้แล้ว

และเขียนเป็นทฤษฎีบทได้คือ ax = b (mod m) จะมีคำตอบเฉพาะสำหรับ x ที่อยู่ใน Z_m เมื่อ b ใน Z_m ก็ต่อเมื่อ gcd(a, m) = 1
สำหรับวิธีพิสูจน์จะขอละไว้ก่อน เนื่องจากมันค่อนข้างยาวและใช้ความรู้ด้าน Number theory ที่ผมยังไม่ค่อยถนัดนัก

ขั้นต่อไปที่เราะพิจรณาคือ จะมี a ใดบ้างที่เหลือให้เราใช้ได้
จาก 26 = 2 x 13 ดังนั้นเลขที่ใช้ได้จะไม่มี 2 กับ 13 ประกอบอยู่เมื่อเราแยกตัวประกอบ
ดังนั้น a สำหรับ Z₂₆ คือ 1, 3, 5, 7, 9, 11, 15, 17, 19, 21 และ 25 (ถ้าเปลี่ยน Z₂₆ เป็นอย่างอื่นก็ต้องหากันใหม่)
เห็นได้ว่าวิธีนี้มี a ที่ใช้ได้อยู่ 12 แบบ ส่วน b ยังเหมือนเดิม 26 แบบ ดังนั้น key space มีขนาด 12 x 26 = 312 วิธี (ไม่ปลอดภัย)

สำหรับจำนวนของกุญแจที่เป็นไปได้นี้ ก็มีทฤษฎีบทมารองรับเช่นกัน
ก่อนอื่นเราจะกล่าวว่าเมื่อ a ? 1 และ m ? 2 เป็นจำนวนเต็ม ถ้า gcd(a, m) = 1 เราจะเรียกว่า a และ m เป็นจำนวนเฉพาะสัมพัทธ์
และจำนวนของสมาชิกใน Z_m ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ m (ก็คือ a นั่นเอง) จะเรียกว่า ?(m)
ซึ่ง ?(m) จะเท่ากับผลคูณของ (p_i^e_i - p_i^e_i-1) ตั้งแต่ i = 1 ถึง n (ไม่พิสูจน์อีกตามเคย ยากส์ส์)

ลองใช้ดีกว่า จากข้างต้น 26 = 2¹ x 13¹
ดังนั้น ?(26) = (2¹ - 2⁰)(13¹ - 13⁰) = (2-1)(13-1) = 12 ครับ

แต่ปัญหาก็ยังไม่หมดเท่านี้ เพราะแม้เราจะมี a ทั้ง 12 แบบอยู่ในมือแล้ว แต่กลับไปดูด้านบนสุดจะเห็นว่าเราต้องการ a^-1
ถ้านี่เป็นการพิจรณาเลขในชีวิตประจำวัน มันก็ไม่น่ามีปัญหา 3^-1 ก็คือ 1/3 ไม่เห็นยาก
แต่อย่าลืมว่าตอนนี้เรากำลังพิจรณาเลขใน Z₂₆ ซึ่งเรานิยามแค่การบวกและคูณ ไม่ได้นิยามการหาร
เราจึงต้องใช้สมบัติพื้นฐานที่ว่า aa^-1 = a^-1a = 1 (mod m)
งานนี้ถึกก่อนได้เปรียบ ลองหาดูเลยว่า a แต่ละตัวที่ได้มานั้น นำไปคูณอะไรแล้ว mod 26 เหลือ 1 (ผลออกมาดังข้างล่างครับ)

1^-1 = 1
3^-1 = 9
5^-1 = 21
7^-1 = 15
11^-1 = 19
17^-1 = 23
25^-1 = 25

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

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

ที่บรรทัด 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)
 print(cipher_text) 

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

ก่อนที่เราจะเขียนโค้ดส่วนนี้ต่อ สังเกตุว่าห.ร.ม.ของ a กับ 26 หรือ gcd(a, 26) = 1
ดังนั้น เราจึงต้องเขียนป้องกันไม่ให้ a ที่รับมามี gcd(a, 26) != 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:
  return("gcd(26, %(a)i) must be 1") % locals()
 else:
  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₂₆ เป็นอย่างอื่นแล้วก็ต้องหาใหม่
ถ้าอย่างนั้นแล้วเรามาดูฟังก์ชันที่มันสนุกๆ กันดีกว่าครับ

แต่ก่อนอื่น เพื่อให้เรื่องต่างๆ เป็นระเบียบและจัดการง่าย เราจะสร้างไฟล์ใหม่ที่ชื่อว่า cryptologic.py ครับ
และจากตอนที่ผ่านๆ มา จะเห็นว่ามีฟังก์ชันสั้นๆ ที่ไม่ใช่ฟังก์ชันที่เราจะเรียกใช้โดยตรง จะใช้แค่ประกอบในฟังก์ชันหลัก
เช่นพวก lower_to_number(text), ged(a,b) เราย้ายมันมาไว้ที่นี่ครับ
แล้วจึงเพิ่มโค้ดอันแสนสนุกสนานนี้เข้าไปร่วมกับเพื่อนๆ ครับ

def multiple_inv(a, b, s = 0, t = 1):
 if a%b == 0:
  if b != 1:
   return(None) # case of no inverse
  else:
   return(t)
 else:
  return(multiple_inv(b, a%b, t, (s-t*int(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 = multiple_inv(26, a)
 if a_inv == None:
  return("%(a)i has no inverse") % locals()
 else:
  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) 

เดี๋ยวตอนหน้าจะมันส์กว่านี้อีกครับ ยังไงก็ติดตามกันด้วยนะครับ ^__^