38 / 62
38
นิตยสาร สสวท.
ผู้อ่านคงสงสัยว่าทำ
�ไมคนสองคนที่สื่อสารกันต้องชื่ออลิส
และบ็อบ ใช้ชื่ออื่นไม่ได้หรือ คำ
�ตอบก็คือได้ แต่เป็นที่รู้กันใน
วงการที่เกี่ยวกับการสื่อสารรหัสลับว่า เมื่อกล่าวถึงอลิส และ
บ็อบจะหมายถึงคนสองคนใด ๆ ที่ต้องการสื่อสารกัน เพียง
เพื่อสะดวกต่อการอธิบายเท่านั้น ที่จริงแล้วยังมีอีกคนหนึ่งที่
มีบทบาทสำ
�คัญ คือ อีฟ(Eve) ซึ่งเป็นที่รู้กันว่าอีฟคือผู้ร้ายที่
คอยดักขโมยข้อมูลระหว่างทาง
บรรณานุกรม
Trappe, Wade & Washington, Lawrence C. (2006).
Introduction to
Cryptography with Coding Theory
. ( 2nd edition). New Jersey:
Prentice-Hall.
ขั้นตอนการสร้างระบบรักษาความปลอดภัย
สมมุติว่าอลิสต้องการส่งข้อความซึ่งแทนด้วยจำ
�นวนเต็ม
บวก m ให้บ็อบ
1.บ็อบเลือกจำ
�นวนเฉพาะสองจำ
�นวนคือ p และ q แล้วหา
ผลคูณ n = pq
2.บ็อบเลือกเลขชี้กำ
�ลัง e ซึ่งสอดคล้องกับสมบัติ gcd
(e, (p – 1)(q – 1)) = 1
3.บ็อบสามารถประกาศค่าของ n และ e ให้สาธารณะรู้ได้
แต่บ็อบต้องเก็บ p และ q ไว้เป็นความลับ ไม่ให้ใครล่วงรู้
4.อลิสเข้ารหัส m โดยคำ
�นวณค่า c
≡
m
e
(mod n) แล้ว
ส่ง c ไปให้บ็อบ
5.เนื่องจากบ็อบเป็นคนเดียวที่รู้ค่าของ p และ q บ็อบ
สามารถคำ
�นวณค่า (p – 1)(q – 1) ได้โดยง่าย ซึ่งจะทำ
�ให้บ็อบ
สามารถหา d ที่สอดคล้องกับ de
≡
1 (mod(p – 1)(q – 1))
ได้ จะเห็นว่า p และ q เปรียบเสมือนกุญแจส่วนตัวที่ใช้สำ
�หรับ
ถอดรหัส ผู้ที่จะคำ
�นวณค่า d ได้ จะต้องรู้ p และ q นั่นคือรู้
p – 1 และ q – 1
6.เมื่อบ็อบได้รับ c บ็อบทำ
�การถอดรหัส โดยการคำ
�นวณค่า
c
d
ดังนี้ เนื่องจาก c = m
e
ดังนั้น
c
d
= (m
e
)
d
= m
de
= m mod(p – 1)(q – 1)
เพราะ de
≡
1 (mod(p – 1)(q – 1)) จะเห็นว่า c
d
= m
ซึ่งก็คือจำ
�นวนเต็มบวกที่อลิสต้องการส่งให้บ็อบนั่นเอง
ตัวอย่าง 6
สมมุติว่า m = 75 แทนข้อความที่อลิสต้องการส่งให้บ็อบ
1.บ็อบเลือกจำ
�นวนเฉพาะ p = 13 และ q = 17
ดังนั้น n = pq = 221 และ (p – 1)(q – 1) = 192
2.บ็อบเลือกเลขชี้กำ
�ลัง e = 7 ซึ่ง gcd (7, (p – 1)(q – 1))
= gcd (7, 192) = 1 ดูตัวอย่าง 2
3.บ็อบประกาศค่า n = 221 และ e = 7 ให้สาธารณะ
รวมทั้งอลิสรู้
4.อลิสเข้ารหัสข้อความ m โดยคำ
�นวณค่า c
≡
m
e
(mod n) จะได้ c
≡
75
7
≡
114 (mod 221) แล้วส่งค่า
c = 114 ให้บ็อบ
5.เนื่องจากบ็อบรู้ค่า p และ q บ็อบสามารถคำ
�นวณค่า
(p – 1)(q – 1) = 192 แล้วใช้ความรู้เรื่องขั้นตอนวิธีของยุคลิด
หาค่า d ที่สอดคล้องกับ de
≡
1 mod(192) จากตัวอย่าง 2
จะเห็นว่า
1 = 55 . 7 – 2 . 192
ดังนั้น 1
≡
55 . 7 mod(192) เพราะ 2 . 192
≡
0 mod(192)
แสดงว่า d = 55
6.บ็อบคำ
�นวณค่า c
d
(mod n) จะได้
c
d
≡
114
55
≡
75 (mod 221) ดูตัวอย่าง 3
ซึ่งตรงกับจำ
�นวนที่อลิสส่งให้บ็อบนั่นเอง
เห็นได้ชัดว่า ถ้ารู้ p และ q เราสามารถหา n = pq ได้โดย
ง่าย แต่ในทางกลับกัน ถ้ารู้ n จะหาจำ
�นวนเฉพาะ p และ q ที่
มีผลคูณเท่ากับ n ทำ
�ได้ยากมาก ซึ่งเป็นสาเหตุให้การถอดรหัส
ทำ
�ได้ยาก ส่วนการเข้ารหัสทำ
�ได้โดยง่าย
เพื่อให้การถอดรหัสทำ
�ได้ยาก ในทางปฏิบัติ จะเลือก
p และ q ที่มีขนาดใหญ่ เช่น อาจเลือก p = 885320963
และ q = 238855417 ซึ่งจะทำ
�ให้ผลคูณ n = pq =
211463707796206571 และอาจเลือกเลขชี้กำ
�ลัง e = 9007 ซึ่ง
gcd (9007, (p – 1)(q – 1)) = 1 เป็นต้น ซึ่งไม่สามารถคำ
�นวณ
ด้วยเครื่องคิดเลขปกติได้ ต้องอาศัยคอมพิวเตอร์ช่วย ถ้า n มี
ค่าใหญ่พอ การคำ
�นวณด้วยคอมพิวเตอร์อาจต้องใช้เวลาถึงร้อย
ปี ซึ่งไม่คุ้มค่ากับความพยายามถอดรหัสข้อความ และข้อความ
นั้นก็อาจจะล้าสมัยแล้วก็ได้