รำลึกความหลังอันสุดเซ็ง

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

รถชนรับปีใหม่...

... 2 ปีติด

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

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

ความเปลี่ยนแปลง???

เวลาเปลี่ยน ใจคนเปลี่ยน
เพราะใจเปลี่ยน ความคิดเลยเปลี่ยน
เมื่อความคิดเปลี่ยน การกระทำก็เปลี่ยนด้วย

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

เริ่มปีใหม่อย่างงงๆ

มาจดไว้ว่า พลาดตั้งแต่ต้นปีเลยตรู
ที่ๆ ควรจะอยู่ก็ไม่ยอมเดินทางตามฝันไป
ยังมัวห่วงใยในที่ๆ ควรทำใจปล่อยวางอยู่ได้
ปีใหม่ทั้งที เฮ้อออ พลาดซะละ

Cryptography ตอนที่ 5 การเข้ารหัสลับวิจเญอแนร์

เราจะเห็นว่าการเข้ารหัสลับในสามตอนที่ผ่านมานั้น จะจับคู่จากอักษรไปยังอักษรตัวเดิมเสมอ
ซึ่งนั่นส่งผลให้เราใช้วิธีง่ายๆ คือไล่แทนอักษรไปเรื่อยๆ (brute force) ได้ แม้ว่ามันจะกินเวลาก็ตาม
เราเรียกวิธีเข้ารหัสจากทั้งสามตอนนั้นว่าเป็นแบบ monoalphabetic หรือแบบอักษรตายตัวครับ

ในปี 1553 จึงได้มีการคิดค้นวิธีเข้ารหัสลับแบบ polyalphabetic หรือแบบอักษรไม่ตายตัวขึ้น
ผู้คิดค้นคือ Giovan Battista Bellaso แต่เนื่องด้วยเหตุผลทางประวัติศาสตร์ในช่วงศตวรรษที่ 19
ทำให้ผู้ที่ได้รับเครดิทกลายเป็น Blaise de Vigen?re แทน เราจึงรู้จักวิธีนี้ในชื่อ Vigen?re Cipher

ข้อดีของการเข้ารหัสลับด้วยวิธีนี้คือ เข้ารหัสง่าย แต่โจมตีรหัสยาก (อย่างน้อยถ้าไม่มีคอมฯ)
ขั้นตอนการเข้ารหัสก็ง่ายเหลือหลายอย่างที่ว่ามา แค่เลือกชุดตัวเลขที่จะใช้เป็นกุญแจมาชุดหนึ่ง
แล้วก็เอาอักษรตัวแรกบวกกับเลขในกุญแจอันแรก อักษรตัวที่สองบวกเลขตัวที่สองไปเรื่อยๆ
จนเมื่อชุดตัวเลขในกุญแจที่ใช้หมด ก็กลับไปเริ่มเลขตัวแรกในกุญแจใหม่อีกครั้ง
ง่ายจริงๆ ให้ดินตายเลย (งั้นไปดูคณิตศาสตร์ก่อนที่จะดิ้นตายดีกว่า 555+)

ให้ P = C = Z₂₆ และให้ K = {(a₁, a₂, a₃, ... , a_i) ใน Z₂₆ สำหรับ i ใน N}
สำหรับ K = (a₁, a₂, a₃, ... , a_i) สร้าง K* = (a₁, a₂, a₃, ... , a_i, a₁, ...) และกล่าวว่า
e_K(x) = (x_j + a_j) mod 26 และ d_K(y) = (y_j - a_j) mod 26
สำหรับ x, y ที่เป็นสมาชิกของ Z₂₆ และ a_j ที่เป็นสมาชิกของ K*

สำหรับนักคณิตศาสตร์แล้ว จะแปลงกุญแจจากสั้นๆ ให้เป็นอนันต์ก่อน แล้วจึงค่อยนำกุญแจไปใช้
จะเห็นว่าวิธีนี้ key space ใหญ่ขึ้นอย่างรวดเร็ว เพียงแค่เพิ่มตัวเลขในกุญแจ ซึ่งคือ 26ⁱ นั่นเอง
เลขในกุญแจเพียงแค่ 5 ตัวจะสร้าง key space ที่ใหญ่ถึง 25⁵ = 11.8 x 10⁶ เลยครับ

นอกจากนี้ก็ไม่มีอะไรยากแล้ว ไปเอาโค้ดการเข้ารหัสลับแบบเลื่อนมาแก้ไขนิดเดียวก็ใช้ได้แล้วครับ

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

def vigenere(pain_text, key_list):
 cipher_text = ""
 for i in range(len(pain_text)):
  char_num = lower_to_number(pain_text[i])
  char_num += key_list[i%len(key_list)]
  char_num %= 26
  cipher_text += number_to_upper(char_num)
 return(cipher_text) 

จะเห็นว่า ทางคอมพิวเตอร์นั้น เราไม่จำเป็นต้องสร้าง K* เหมือนทางคณิตศาสตร์ก็ได้
แต่จะใช้ modulo เพื่อวนเรียกใช้เลขที่เราต้องการเมื่อเราใช้เลขในลิสต์หมดครับ
อ๋อ เวลาเรียกฟังก์ชันนี้ขึ้นมาใช้ ตัวแปรด้านหลังต้องพิมพ์เป็นตัวแปรแบบลิสต์อย่างนี้นะครับ

>>> encrypt.vigenere("testvigenerecipher", [4, 25, 7, 12, 0]) 

ส่วนผลลัพท์จะออกมาเป็นอย่างไร ต้องฝากเป็นการบ้านไว้พร้อมกับการเขียน decrypt ครับ
เจอกันคราวหน้าครับ ^__^

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) 

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

Cryptography ตอนที่ 3 การเข้ารหัสลับแบบจับคู่

การเข้ารหัสลับด้วยวิธีต่อมานั้นก็คือ Substitution Cipher หรือแบบจับคู่
วิธีการก็ไม่รู้ว่าจะอธิบายให้ยุ่งยากทำไมเนาะ - -"
แต่ก็เอาถอะ ไหนๆ ก็พูดในเชิงคณิตศาสตร์ละ งั้นก็ลงอธิบายแบบคณิตศาสตร์เลยละกัน

ให้ P = C = Z₂₆, ส่วน K คือวิธีเรียงสับเปลี่ยนของเลข 0 ถึง 25 ทั่งหมดที่เป็นไปได้ ให้ ? เป็นสมาชิกของ K จะกล่าวว่า
e_?(x) = ?(x) และ d_?(x) = ?^-1(x) เมื่อ ?^-1 คืออินเวอร์สของ ?

จะเห็นว่า วิธีนี้ให้ key space ที่ใหญ่มากถึง 26! หรือประมาณ 4.03 x 10²⁶ เลยทีเดียว (แต่ก็ยังไม่ปลอดภัยอยู่ดี!)

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

>>> list = []
>>> for i in range(26):
...  list.append(i)
... 

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

>>> import random
>>> for i in range(26):
...  temp = random.randint(0, 25)
...  list[i], list[temp] = list[temp], list[i]
... 

จัดการเปลี่ยนมันให้เป็นตัวอักษร และเซฟเป็นไฟล์ *.txt ซะ (เพราะต้องได้ใช้ในอนาคตแน่นอน!)

>>> mapping = ""
>>> for i in range(26):
...  mapping += chr(list[i] + ord('A'))
... 
>>> f = open("map_key.txt", 'w')
>>> f.write(mapping)
>>> f.close 

ตอนนี้ เราจะได้ไฟล์ map_key.txt ออกมา ซึ่งบรรจุการจับคู่ของตัวอักษรแล้วครับ
สำหรับการจับคู่ของผมในครั้งนี้ (ไล่จาก a ไป z) คือ XLNYKIHFJWTRBMVPGSAUZQECOD
ต่อมา เช่นเดียวกับที่เราได้เขียนฟังก์ชันไว้ใช้ในตอนที่แล้ว คราวนี้เราจะเปิดไฟล์เดิมมาเขียนเพิ่ม ดังนี้ครับ

def substitution(pain_text, key_file):
 cipher_text = ""
 mapping = []
 for i in range(26):
  mapping.append(0)
 f = open(key_file)
 for i in range(26):
  mapping[i] = upper_to_number(f.read(1))
 f.close()
 for i in range(len(pain_text)):
  char_num = lower_to_number(pain_text[i])
  char_num = mapping[char_num]
  cipher_text += number_to_upper(char_num)
 print(cipher_text)

def upper_to_number(text):
 return(ord(text) - start_upper) 

เสร็จเรียบร้อย ลองเรียกใช้ฟังก์ชันโดยการ import encrypt เข้ามาก่อน
และเรียกที่อยู่ฟังก์ชัน encrypt.substitution("canyoureadme", "map_key.txt ")
ก็ได้ผลลัพท์เป็น NXMOVZSKXYBK ครับ

AKKOVZMKCUUJBK

Cryptography ตอนที่ 2 การเข้ารหัสลับแบบเลื่อน

การเข้ารหัสลับแบบแรกที่ง่ายที่สุดนั้น คือการเข้ารหัสแบบ Shift Cipher หรือการเข้ารหัสแบบเลื่อน
วิธีการก็เป็นไปตามชื่อเลย คือทำการเลื่อนตัวอักษรออกไปตามความยาวที่ต้องการ เท่านั้นเองครับ
ชื่อเฉพาะที่น่าสนใจของวิธีนี้คือ Caesar Cipher อันเนื่องมาจากนี่เป็นวิธีที่จูเลียส ซีซาร์ใช้ในการส่งข้อความลับโดยการเลื่อนอักษรออกไป 3 ตำแหน่งนั่นเอง

เราสามารถเขียนการเข้ารหัสแบบเลื่อนเป็นภาษาคณิตศาสตร์ที่รัดกุมได้ ดังนี้

ให้ P = C = K = Z₂₆, สำหรับ 0 ≤ K ≤ 25 จะกล่าวว่า
e_K(x) = (x + K) mod 26 และ d_K(y) = (y - K) mod 26 สำหรับ x, y ที่เป็นสมาชิกของ Z₂₆

สำหรับบรรทัดแรก จะกล่าวถึงขนาดของ space ข้อมูลที่เราสนใจ ซึ่งในที่นี้ก็คืออักษรภาษาอังกฤษ 26 ตัวตามที่ตกลงกันแต่แรก
ส่วนต่อมาคือการกำหนด key space ที่ถูกนำไปใช้ในบรรทัดต่อไปว่ามีค่าอยู่ในช่วงระหว่าง 0 ถึง 25 นั่นเอง ซึ่งก็คือ 26 แบบนั่นเอง (ไม่ปลอดภัยอย่างแรง!!!)
ตรงนี้ที่ต้องเขียนบอกให้ชัดเจนเพราะเราอาจเขียนมันในกรณีอื่นอีกก็ได้ เช่นสำหรับ K ที่เป็นเลขคู่ให้เลื่อนไปด้านหน้า ส่วน K ที่เป็นเลขคี่ให้เลื่อนไปด้านหลัง เป็นต้นครับ
บรรทัด 2 คือการบอกว่าสำหรับ k ต่างๆ ที่อยู่ใน K นั้นใช้อย่างไร ในที่นี้ก็คือเลื่อนไปด้านหน้าตามขนาดของ K นั่นเองครับ
สังเกตว่าเราใช้ K ตัวใหญ่ใน e_Kและ d_K นั่นก็เพราะว่าเราเขียนระบุในเรื่องของเซตครับ ซึ่งหมายรวมว่าเราสามารถจับ k ใน K ใดๆ ก็ได้มาแทนตรงนั้น

ต่อมาเราจะมาวิเคราะห์อัลกอริทึมกัน โดยทดลงใน Python Shell ตรงๆ
ในเบื้องต้นนั้น เราต้องรับค่าของข้อความที่ต้องการในรูปแบบของ String และกำหนด key ที่เราต้องการให้เลื่อนอักษรไป

>>> pain_text = "testshiftcipher"
>>> k = 3 

ต่อมา ให้สร้างตัวแปร String สำหรับเก็บรหัส และใช้ loop วนเข้าไปเพื่อแปลงค่าของตัวอักษรแต่ละตัวๆ ออกมา
เนื่องจากรหัสอักษรในคอมพิวเตอร์นั้นเป็นรหัส ASCII ซึ่งเรียงกันไปตั้งแต่ a = 97 ถึง z = 122 อยู่แล้ว
ในขั้นต้นเพื่อความง่าย เราจะบวกค่าเหล่านี้เข้าไปทันทีด้วยค่า k แล้วแปลงกลับเป็นตัวอักษรเหมือนเดิม

>>> cipher_text = ""
>>> for i in range(len(pain_text)):
...  cipher_text += chr(ord(pain_text[i]) + k)
... 

เราสามารถเรียก cipher_text ออกมาดูได้ จะเห็นว่าคำที่เราแปลงนั้นกลายเป็น whvwvkliwflskhu (เกือบ) เป็นที่เรียบร้อย
แต่ว่าโค๊ดตรงนี้ยังมีปัญหาอยู่ เพราะว่าถ้าเราใส่อักษรท้ายๆ เข้าไปนั้น เมื่อแปลงเป็นรหัสแล้วก็มีสิทธิ์หลุดออกจากเซตของตัวอักษรอังกฤษไปเป็นอักษรแปลกๆ ได้
เช่นข้อความว่า howareyoutoday เมื่อใช้อัลกอริทึมเก่าจะได้ข้อความ KRZDUH|RXWRGD| จะเห็นว่ามี | ซึ่งไม่ใช่อักษรอังกฤษโผล่เข้ามา
ดังนั้นเราจึงต้องใช้ if เพื่อเช็คว่าค่าที่ได้นั้นเกิน z หรือยัง ถ้าเกินแล้วให้ลบค่าออกด้วย 26
นอกจากนี้ เนื่องจากเราต้องการให้อักษรที่เข้ารหัสแล้วเป็นตัวพิมพ์ใหญ่ด้วย
จาก A = 65 ดังนั้น a - A = 32 เราจึงต้องลบค่าอักษรแต่ละตัวออกไปอีกตัวละ 32 ดังนี้

>>> pain_text = "howareyoutoday"
>>> k = 3 
>>> cipher_text = ""
>>> for i in range(len(pain_text)):
...  temp = ord(pain_text[i]) + k
...  if temp > 122:
...    temp -= 26
...  temp -= 32
...  cipher_text += chr(temp)
... 

คราวนี้เมื่อเราใส่ข้อความ howareyoutoday เข้าไป ก็จะได้ผลลัพท์เป็น KRZDUHBRXWRGDB เรียบร้อยแล้วครับ
ต่อไป เราจะสร้างไฟล์ *.py ขึ้นมาเพื่อเก็บฟังก์ชันที่เขียนให้ง่ายต่อการเรียกใช้ในครั้งถัดๆ ไป
โดยคราวนี้เราจะไม่เขียนลวกๆ แล้ว เพราะการเขียนที่เป็นระเบียบจะทำให้ดูแลและพัฒนา code ต่อภายหลังได้ง่ายขึ้น

start_lower = ord('a')
start_upper = ord('A')

def shift(pain_text, key):
 cipher_text = ""
 for i in range(len(pain_text)):
  char_num = lower_to_number(pain_text[i])
  char_num += key
  char_num %= 26
  cipher_text += number_to_upper(char_num)
 print(cipher_text)

def lower_to_number(text):
 return(ord(text) - start_lower)

def number_to_upper(num):
 return(chr(num + start_upper)) 

จัดการบันทึกไฟล์ที่เขียนนี้ (ในที่นี้ใช้ชื่อ encrypt.py) แล้ว import ไฟล์ผ่าน python shell
เวลาจะเข้ารหัสก็เรียงฟังก์ชันนี้โดยพิมพ์ encrypt.shift("abcdefg", key) เข้าไปเลย
(abcdefg คือคำที่ต้องการให้เข้ารหัส, key คือตัวเลขที่ต้องการให้เลื่อน) แค่นี้ก็เรียบร้อยแล้วครับ ^__^

อ๋อ สำหรับวิธี decrypt นั้น ฝากเป็นการบ้านให้ไปคิดต่อละกันเน้อออ
JRRGOXFN

Cryptography ตอนที่ 1 ธรรมชาติของการเข้ารหัส (อย่างง่าย)

เมื่อเราลองวิเคราะห์ระบบรหัสลับนั้น เราจะกล่าวได้ว่ามันเป็น (P, C, K, E, D) 5-tuple
เริ่มมาก็งงเลยใช่ปะละ (คนแปลก็งงเหมือนกัน) งั้นเราค่อยๆ ดูกันไปทีละส่วนละกันครับ

tuple คำนี้อาจไม่คุ้นเคยและดูยุ่งยาก แต่ที่จริงแล้วมันเป็นเพียงวิธีการเขียนเรียงลำดับสมาชิกเท่านั้นเอง (ต่างจากเซตที่สมาชิกแต่ละตัวไม่มีความสำคัญในเรื่องลำดับ)
โดยสมาชิกของ tuple นั้นจะต้องมีจำนวนจำกัด n ตัวเสมอ n-tuple ที่เราคุ้นเคยกันดีก็คือ 2-tuple ที่อยู่ในรูป (x, y) หรือเรียกติดปากกันว่าคู่อันดับนั่นเอง
ดังนั้นการที่กล่าวได้ว่าระบบรหัสลับเป็น 5-tuple ก็หมายความว่าระบบนี้มีสิ่งที่สำคัญประกอบอยู่ 5 อย่างนั่นเอง ซึ่งมีความสัมพันธ์กันดังนี้

1. P (Plaintext) คือเซตจำกัดของข้อความอ่านออกที่เป็นไปได้
2. C (Ciphertext) คือเซตจำกัดของข้อความเข้ารหัสที่เป็นไปได้
3. K (Key) คือเซตจำกัดของกุญแจการเข้ารหัสที่เป็นไปได้
4. สำหรับแต่ละ k ที่เป็นสมาชิกของ K (ในทางคณิตศาสตร์ ตัวพิมพ์ใหญ่คือเซต ตัวพิมพ์เล็กคือสมาชิกของเซตนั้นๆ) จะมีวิธีการใช้กุญแจเข้ารหัส (Encryption) e_K ที่เป็นสมาชิกของ E และมีวิธีใช้กุญแจถอดรหัส (Decryption) d_K ที่เป็นสมาชิกของ D โดยที่ e_K : P -> C (e_K เป็นฟังก์ชันจาก P ไปยัง C หรือกล่าวง่ายๆ ว่าฟังก์ชัน e_K นี้มี P เป็น input ส่วน C เป็น output นั่นเอง) และ d_K : C -> P โดยที่ p = d_K(e_K(p))

จากข้อ 4 นี้ จะหมายความว่า d_K เป็นอินเวอร์สของ e_K เสมอ และเขียนได้ว่า d_K = e_K^-1
นอกจากนี้ e_K และ d_K ยังต้องเป็นฟังก์ชันแบบ 1-1 อีกด้วย (จับคู่กันและกันแค่คู่ต่อคู่เท่านั้น) เพราะถ้าไม่เป็นฟังก์ชัน 1-1 แล้ว เมื่อเราต้องการถอดรหัสกลับเป็นข้อความธรรมดา เราอาจไม่รู้เลยว่าคำที่ถูกต้องคืออะไรกันแน่ เพราะ 1 คำอาจถอดรหัสกลับได้หลายแบบนั่นเอง

จากที่เกริ่นมานี้หมายความว่า ถ้าเราสามารถล่วงรู้ e_K ได้ เราก็จะหา d_K เพื่อถอดรหัสลับได้เช่นกัน
หรือว่าถ้าเราสามารถดักจับข้อความลับ c ได้ และล่วงรู้ข้อความถูกต้อง p บางส่วน เราอาจทดลองหา k ที่ทำให้ c = e_k(p) จนสำเร็จ และหา d_k ได้ด้วย