Cryptography ตอนที่ 6 การเข้ารหัสลับแบบฮิลล์

สวัสดีครับ หายหน้าหายตาไปหลายตอนเลย
พอดีวันนี้ไปยืม SyntaxHighlighter มาแปะเว็บเล่น
เลยถือโอกาสอัพอะไรที่มันต้องใช้ขมองหน่อยละกัน ;)

แล้วเราก็มาต่อกันที่ การเข้ารหัสลับแบบฮิลล์ (Hill Cipher)
ซึ่งได้ชื่อมาจาก Lester S. Hill นักคณิตศาสตร์ชาวอเมริกัน
โดยวิธีการนี้ได้ถูกคิดค้นและตีพิมพ์ในปี 1929 ครับ

วิธีการนี้จะกำหนดเมทริกซ์ 1 ตัวขึ้นมาเป็นกุญแจ
แล้วเอาคำที่ต้องการเข้ารหัสมาคูณกับเมทริกซ์นี้ครับ
ฟังดูไม่ยาก แต่ก็มีรายละเอียดเยอะมากทีเดียว
ไปดูกันเลยครับ

ให้ m >= 2 เป็นจำนวนนับ ให้ P = C = (Z₂₆)^m
K = {m x m เมทริกซ์ที่มีอินเวอร์สบน Z₂₆}
สำหรับ K นี้ จะกล่าวว่า
e_K(x) = xK และ d_K(y) = yK^-1
เมื่อโอเปอเรชันทุกตัวทำงานบน Z₂₆

ไม่มีอะไรยากเลยจริงๆ ครับ
เพียงแต่ต้องระวังว่า การใช้กุญแจนั้น ต้องวางไว้หลังคำที่จะแปลงรหัสเสมอ
งั้นก็ไปดูการเขียนโค้ดกันเลยดีกว่าครับ

เมทริกซ์ในโลกคอมพิวเตอร์นั้น สร้างได้ง่ายๆ โดย array 2 มิติ
ในภาษา python ก็คือการใช้ลิสต์ซ้อนลิสต์ เช่น [[1, 2], [3, 4]] ครับ
แต่เนื่องจากตัวเลขทั้งหลายของเราดันไปอยู่บน Z₂₆ ซะหนิ
การเขียนฟังก์ชันสำหรับการคูณ/หาอินเวอร์สจึงต้องดัดแปลงเยอะอยู่
ดังนั้น ในที่นี้เราเล่นกับเมทริกซ์ขนาด 2x2 เท่านั้นครับ

def matrix(a00 = 0, a01 = 0, a10 = 0, a11 = 0):
 return([[a00%26, a01%26], [a10%26, a11%26]])

ในเมื่อเราต้องการเมทริกซ์ขนาดแค่ 2x2 เท่านั้น
การนั่งเขียน [[1, 2], [3, 4]] ทุกครั้งก็มีโอกาสพลาดได้ง่ายๆ
ดังนั้น การกำหนดฟังก์ชันขึ้นมาใช้งานเฉพาะเลยจึงเข้าท่ากว่า

def matrix_multiple(matrix_1, matrix_2):
 result_matrix = matrix()
 for i in range(len(matrix_1)):
  for j in range(len(matrix_2[0])):
   for k in range(len(matrix_1[0])):
    result_matrix[i][j] += matrix_1[i][k] * matrix_2[k][j]
    result_matrix[i][j] %= 26
 return(result_matrix)

แล้วเราก็มาเขียนการคูณเมทริกซ์กันครับ
อันนี้เป็นการเขียนสำหรับเผื่อการใช้คูณเมทริกซ์ธรรมดาด้วย
แต่ต้องตัดบรรทัดที่เอาผลลัพท์ไป modulo 26 ทิ้งไป
แล้วเช็คตอนแรกว่า มิติของเมทริกซ์เป็นไปตามกฏการคูณหรือเปล่า?

def determinant_inv(m):
 determinant = m[0][0]*m[1][1] - m[0][1]*m[1][0]
 if determinant != 0:
  return(multiple_inv(26, determinant%26))

อันนี้เป็นการหา determinant ที่อินเวอร์สเรียบร้อยแล้วครับ
เพราะเราไม่มีความจำเป็นที่ต้องใช้ค่า det เปล่าๆ
แถมการได้ det ที่มีค่าเป็น 0 ก็ไม่มีประโยชน์ในที่นี้อีกครับ

def matrix_inv(m):
 det_inv = determinant_inv(m)
 if det_inv != None:
  inverse = matrix(m[1][1], -m[0][1], -m[1][0], m[0][0])
  for i in range(2):
   for j in range(2):
    inverse[i][j] *= det_inv
    inverse[i][j] %= 26
  return(inverse)

อินเวอร์สเมทริกซ์ซึ่งสามรถประยุกต์กับเมทริกซ์ 2x2 ทั่วไปได้เหมือนด้านบน

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

def hill(pain_text, matrix):
 if len(pain_text)%2 != 0:
  return("text lenght must be even number")
 if matrix_inv(matrix) == None:
  return("matrix must have inverse in order to decrypt")
 else:
  cipher_text = ""
  char_num = [[0, 0]]
  for i in range(int(len(pain_text)/2)):
   char_num[0][0] = lower_to_number(pain_text[2*i])
   char_num[0][1] = lower_to_number(pain_text[2*i + 1])
   char_num = matrix_multiple(char_num, matrix)
   cipher_text += number_to_upper(char_num[0][0])
   cipher_text += number_to_upper(char_num[0][1])
  return(cipher_text)

ทีนี้เวลาเรียกใช้งาน ถ้าจะให้ง่ายก็ทำการเก็บตัวแปรที่เป็นเมทริกซ์ไว้ก่อนครับ เช่น

>>> a = encrypt.matrix(1, 5, 3, 4)
>>> encrypt.hill("testhill", a)
'FHXKFPSV'

ส่วนการถอดรหัสก็ง่ายเหมือนเดิมครับ
เลยฝากไว้เป็นการบ้านละกัน :P

HJIFLQSEKGZQ