แต่อาจเนื่องด้วยความยุ่งยากของการต้องใช้กุญแจขนาดใหญ่เพื่อไขรหัสให้ได้ บวกกับความง่ายเกินไปของการเข้ารหัสแบบเลื่อน
ทำให้เกิดการเข้ารหัสแบบสัมพรรค หรือ Affine Cipher ซึ่งดัดแปลงเพิ่มเติมจากการเข้ารหัสลับแบบเลื่อนขึ้นมา
เขียนอธิบายเป็นภาษาทั่วไปยากหน่อย วิธีนี้ดูสมการแล้วน่าจะเข้าใจง่ายกว่าจริงๆ
ให้ P = C = Z26 และให้ K = {(a, b) ใน Z26 | gcd(a, 26) = 1}
สำหรับ K = (a, b) จะกล่าวว่า
eK(x) = (ax + b) mod 26 และ dK(y) = a-1(y - b) mod 26 สำหรับ x, y ที่เป็นสมาชิกของ Z26
อย่างที่บอกไว้ว่าวิธีนี้ดัดแปลงเพิ่มเติมจากการเข้ารหัสแบบเลื่อนแค่นิดเดียว
ลองมองผ่านๆ จะเห็นว่าวิธีการนี้เพียงแค่เพิ่ม a เข้าไปคูณกับ x ก่อนที่จะบวกด้วย b เท่านั้นเอง
รู้แค่นี้ก็เอาไปใช้ได้แล้ว แต่ถ้าอยากใช้อย่างไม่ผิดพลาด ลองมาวิเคราะห์อะไรที่มันยากๆ ในนั้นกัน
เริ่มจาก K = {(a, b) ใน Z26 | gcd(a, 26) = 1} หมายความว่ากุญแจที่ใช้นี้ ต้องการตัวแปรเพื่อใช้เข้ารหัส 2 ค่า อันนี้ไม่ยากๆ
แต่จะยากตั้งแต่ตรงนี้ไปคือ gcd(a, 26) = 1 หรือห.ร.ม.ของ a กับ 26 ต้องเป็น 1 เท่านั้น
นั่นก็เพราะว่า ถ้าห.ร.ม.ไม่เท่ากับ 1 แล้ว ฟังก์ชัน eK จะไม่เป็น 1-1 ส่งผลให้ไม่สามารถใช้ dK หาข้อความที่ถูกต้องได้
ลองพิจรณาตัวอย่าง สมมติให้ a = 2, b = 0 ข้อความ iamaboy จะแปลงได้เป็น QAYACCW
ซึ่งเห็นได้ว่า b, o ทั้งสองตัวแปลงเป็น C ทำให้แปลง QAYACCW กลับเป็น iamaboy ไม่ได้แล้ว
และเขียนเป็นทฤษฎีบทได้คือ ax = b (mod m) จะมีคำตอบเฉพาะสำหรับ x ที่อยู่ใน Zm เมื่อ b ใน Zm ก็ต่อเมื่อ gcd(a, m) = 1
สำหรับวิธีพิสูจน์จะขอละไว้ก่อน เนื่องจากมันค่อนข้างยาวและใช้ความรู้ด้าน Number theory ที่ผมยังไม่ค่อยถนัดนัก
ขั้นต่อไปที่เราะพิจรณาคือ จะมี a ใดบ้างที่เหลือให้เราใช้ได้
จาก 26 = 2 x 13 ดังนั้นเลขที่ใช้ได้จะไม่มี 2 กับ 13 ประกอบอยู่เมื่อเราแยกตัวประกอบ
ดังนั้น a สำหรับ Z26 คือ 1, 3, 5, 7, 9, 11, 15, 17, 19, 21 และ 25 (ถ้าเปลี่ยน Z26 เป็นอย่างอื่นก็ต้องหากันใหม่)
เห็นได้ว่าวิธีนี้มี a ที่ใช้ได้อยู่ 12 แบบ ส่วน b ยังเหมือนเดิม 26 แบบ ดังนั้น key space มีขนาด 12 x 26 = 312 วิธี (ไม่ปลอดภัย)
สำหรับจำนวนของกุญแจที่เป็นไปได้นี้ ก็มีทฤษฎีบทมารองรับเช่นกัน
ก่อนอื่นเราจะกล่าวว่าเมื่อ a ? 1 และ m ? 2 เป็นจำนวนเต็ม ถ้า gcd(a, m) = 1 เราจะเรียกว่า a และ m เป็นจำนวนเฉพาะสัมพัทธ์
และจำนวนของสมาชิกใน Zm ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ m (ก็คือ a นั่นเอง) จะเรียกว่า ?(m)
ซึ่ง ?(m) จะเท่ากับผลคูณของ (piei - piei-1) ตั้งแต่ i = 1 ถึง n (ไม่พิสูจน์อีกตามเคย ยากส์ส์)
ลองใช้ดีกว่า จากข้างต้น 26 = 21 x 131
ดังนั้น ?(26) = (21 - 20)(131 - 130) = (2-1)(13-1) = 12 ครับ
แต่ปัญหาก็ยังไม่หมดเท่านี้ เพราะแม้เราจะมี a ทั้ง 12 แบบอยู่ในมือแล้ว แต่กลับไปดูด้านบนสุดจะเห็นว่าเราต้องการ a-1
ถ้านี่เป็นการพิจรณาเลขในชีวิตประจำวัน มันก็ไม่น่ามีปัญหา 3-1 ก็คือ 1/3 ไม่เห็นยาก
แต่อย่าลืมว่าตอนนี้เรากำลังพิจรณาเลขใน Z26 ซึ่งเรานิยามแค่การบวกและคูณ ไม่ได้นิยามการหาร
เราจึงต้องใช้สมบัติพื้นฐานที่ว่า 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 ก็ได้ แต่มันง่ายไปแถมถ้าเราเปลี่ยนจาก Z26 เป็นอย่างอื่นแล้วก็ต้องหาใหม่
ถ้าอย่างนั้นแล้วเรามาดูฟังก์ชันที่มันสนุกๆ กันดีกว่าครับ
แต่ก่อนอื่น เพื่อให้เรื่องต่างๆ เป็นระเบียบและจัดการง่าย เราจะสร้างไฟล์ใหม่ที่ชื่อว่า 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)
เดี๋ยวตอนหน้าจะมันส์กว่านี้อีกครับ ยังไงก็ติดตามกันด้วยนะครับ ^__^
