Jan 16, 2011

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

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

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

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

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

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

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