PANTIP.COM : X3095702 ข้อสงสัยเรื่องการ encryption โดยใช้ public key [วิศวกรรมและเทคโนโลยี]

ความคิดเห็นที่ 14

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

สมมติว่ามีตัวเลขจำนวน 10 ตัว คือ 1 ถึง 10 เราสามารถสร้างการเข้ารหัสแบบง่าย ๆ โดยใช้วิธีการคูณ และ การ Modulo (ต่อไปจะเรียกว่า mod หมายถึงการหารเอาเศษ เช่น 10 mod 3 เท่ากับ 1) ได้ เช่น สมมติให้ใช้คีย์ 3 เป็นคีย์ที่ใช้ในการเข้ารหัส สมมติว่าตัวเลขที่จะเข้ารหัส คือ 4 เราจะนำ 3 x 4 เท่ากับ 12 แล้ว mod ด้วย 10 เท่ากับ 2 (2 ถือเป็น Cipher Text) จากนั้นก็ส่ง 2 ไปยังผู้รับ ผู้รับก็จะนำคู่ของ 3 คือ 7 มาคูณกับ Cipher Text คือ 2 x 7 เท่ากับ 14 แล้ว mod ด้วย 10 ก็จะได้ค่าเดิมออกมา คือ 4 ดังนั้นในกรณีนี้ 3 จะเท่ากับเป็นไพรเวทคีย์และ 7 จะเป็นพับลิกคีย์

ในตัวเลขระหว่าง 1 ถึง 10 จะมีตัวเลขในแบบนี้ อยู่ 2 คู่ คือ 3 กับ 7 สำหรับเลข 9 นั้น คู่ของมันก็เป็นเลข 9 เช่นเดียวกัน ดังนั้นจะเห็นได้ว่าตัวเลขระหว่าง 1 กับ 10 นั้นมีเพียง 3 และ 7 เท่านั้น ที่เหมาะสมสำหรับนำไปใช้เป็นคีย์ เพราะการใช้ 9 เป็นคีย์จะทำให้พับลิกคีย์และไพรเวทคีย์เป็นค่าเดียวกัน ซึ่งไม่เหมาะสมจะใช้ในระบบพับลิกคีย์ แต่ตัวเลขข้างต้นเป็นเพียงตัวอย่างเท่านั้น เพราะตัวเลข 1 ถึง 10 นั้น ง่ายเกินกว่าจะนำไปใช้งานเป็นคีย์จริงๆ ได้ สำหรับการใช้งานจริงนั้น จะใช้ตัวเลขที่มีความยาวมาก ๆ เป็นคีย์ เช่น ความยาว 512 บิต และฟังก์ชันที่ใช้จะไม่ใช้ฟังก์ชันคูณ แต่จะใช้เป็นฟังก์ชันยกกำลัง (Exponential) เพราะจะมีความยากในการเข้ารหัสและถอดรหัสมากกว่า

คราวนี้มาดูอัลกอริทึม RSA

การทำงานของอัลกอริทึม RSA จะเริ่มจากการหาค่า Prime หรือจำนวนเฉพาะ p และ q ที่แตกต่างกัน และจะต้องมีขนาดของความยาว (ในหน่วยเป็นบิต) เท่ากัน จากนั้นนำ p และ q มาคูณกันได้เป็น n และนำ (p-1) คูณกับ (q-1) จะได้เป็น Q (n) จากนั้นสุ่มค่าของ e ขึ้นมาโดย e จะต้องมากกว่า 1 และน้อยว่า Q และตัวหารร่วมมากของ Q และ e จะต้องเป็น 1 จากนั้นใช้คณิตศาสตร์ Extended Euclidean Algorithm คำนวณหาค่า d (d จะต้องมากกว่า 1 และน้อยว่า Q) ที่ทำให้ ed mod Q แล้วได้เท่ากับ 1 และ e จะทำหน้าที่เป็น Public Key และ d จะทำหน้าที่เป็น Private Key

เพื่อให้เข้าใจมากขึ้น จะขอยกตัวอย่าง สมมติว่าเราเลือกค่า Prime ได้เป็น p = 2357 และ q = 2551 เราจะคำนวณ n ได้เป็น pq = 6012707 และ Q = (p-1)(q-1) = 6007800 สมมติว่าเราเลือกค่า e = 3674911 และโดยใช้ Extended Euclidean Algorithm คำนวณหาจะได้ค่า d = 422191 ซึ่งจะทำให้ (e x d) mod Q = 1

คราวนี้เรามาลองเข้ารหัสและถอดรหัส เพื่อให้ดูง่ายขึ้นเราจะใช้ Private Key = 5 และ Public Key = 77 เพื่อไม่ให้ตัวเลขที่สร้างขึ้นใหญ่เกินไป สมมติว่า Plain Text คือตัวเลข 19 เราจะนำ 19 มายกกำลัง 5 แล้ว mod ด้วย 119 ซึ่งเป็นค่า n ได้เป็น 66 จากนั้นเราก็นำ 66 มายกกำลัง 77 แล้ว mod ด้วย n (119) ก็จะได้ค่า 19 ซึ่งเป็นค่าเดิมกลับมา

คราวนี้มาถึงคำถาม

1. เจ้าตัว function ที่ผมเอาไปกระทำกับข้อมูลที่ผมมีนี้ มันมีหน้าตาเป็นอย่างไรครับ

ANS : มักจะเป็นฟังก์ชันยกกำลัง ตามที่ยกตัวอย่างไปข้างต้น เพราะเป็นฟังก์ชันที่ใช้เวลาถอดนาน

2. ทั้งๆที่ใครๆก็รู้ public key เดียวกัน ถ้ามีคนเอาขัอมูลที่ผมทำการ encrypt แล้ว ไปใส่ inverse function ให้กลับมาเป็นข้อมูลแบบเดิมไม่ได้เหรอครับ

ANS : ได้ เพราะทุกคนรู้ Public Key แต่กรณีนี้ สิ่งที่จะได้คือจะยืนยันได้ว่าคุณเป็นคนเข้ารหัส เพราะการที่เขาถอดรหัสด้วย Public Key ของคุณได้แสดงว่าต้องเข้ารหัสด้วย Private Key ของคุณ ซึ่งมีคุณมีอยู่คนเดียว ทั้งนี้เนื่องจาก Public Key มีประโยชน์ 2 อย่าง คือ เข้ารหัสลับ (เข้าด้วย Public ถอดด้วย Private) และยืนยันตัวบุคคล (เข้าด้วย Private ถอดด้วย Public)

3. แล้ว private key ที่ไม่เหมือนกับ public key เนี่ย มันจะสามารถทำการ decrypt ได้อย่างไรครับ พี่ๆช่วยยกทฤษฏี หรือว่า ยกตัวอย่างให้หน่อยครับ

ANS : ยกตัวอย่างให้แล้วครับ

-------------------------------------------------------

คราวนี้ก็ขอแก้ข้อผิดพลาดที่ท่านอื่น Post ไว้ ขอออกตัวว่าไม่ได้เจตนาข่ม แต่อยากจะให้ข้อมูลที่ถูกต้องจริง ๆ

- Public Key กับ Hash Function เป็นคนละเรื่องกัน เพราะ Hash นั้นเป็นการหาเอกลักษณ์ของข้อความขนาดใหญ่ ๆ เพื่อพิสูจน์ว่าเป็นข้อมูลเดิม ไม่เกี่ยวกับการเข้ารหัสแต่อย่างใด

- Public Key ไม่ได้เป็น Function แต่เป็น Operation ทางคณิตศาสตร์ ดังนั้นที่บอกว่าเป็น One Way Function จึงไม่ถูกต้อง

แก้ไขเมื่อ 01 พ.ย. 47 23:01:12

จากคุณ : ผู้เฒ่าสายลม - [ 1 พ.ย. 47 22:58:05 ]