อัลกอริทึม RSA คำนวณอย่างไร ตัวอย่างขั้นตอนการเข้ารหัส-ถอดรหัส

RSA เป็นระบบเข้ารหัสแบบคีย์สาธารณะที่ใช้กันอย่างแพร่หลายสำหรับรักษาความปลอดภัยข้อมูลละเอียดอ่อน โดยเฉพาะการส่งผ่านเครือข่ายที่ไม่ปลอดภัย เช่น อินเทอร์เน็ต

อัลกอริทึม RSA เป็นอัลกอริทึมเข้ารหัสแบบคีย์อสมิตรที่นิยมมากที่สุด พึ่งพาข้อเท็จจริงทางคณิตศาสตร์ที่ว่าง่ายต่อการหาและคูณจำนวนเฉพาะขนาดใหญ่ แต่ยากต่อการแยกตัวประกอบ (Factor) ของผลคูณ ต้องใช้ทั้งคีย์ส่วนตัวและคีย์สาธารณะ

ตัวอย่างการคำนวณ RSA

มาดูตัวอย่างขั้นตอนเพื่อเข้าใจแนวคิด จะแสดงค่าตัวอย่างพร้อมกับขั้นตอนอัลกอริทึม

1. เลือกจำนวนเฉพาะขนาดใหญ่สองจำนวน P และ Q

   ให้ P = 7, Q = 17 (หมายเหตุ: บทความต้นฉบับมีค่า P=47 แต่คำนวณใช้ 7)

2. คำนวณ N = P × Q

   N = 7 × 17 = 119

3. เลือกคีย์สาธารณะ (Encryption Key) E โดยที่ E ไม่ใช่ตัวประกอบของ (P−1) × (Q−1)

   • หา (7−1) × (17−1) = 6 × 16 = 96
   • ตัวประกอบของ 96 คือ 2, 2, 2, 2, 2, 3 (เพราะ 96 = 2⁵ × 3)
   • ดังนั้นเลือก E ที่ไม่มีตัวประกอบเป็น 2 และ 3 ไม่เลือก 4 (มี 2), 15 (มี 3), 6 (มีทั้ง 2 และ 3)
   • เลือก E = 5 (หรือจำนวนอื่นที่ไม่มีตัวประกอบ 2 และ 3)

4. เลือกคีย์ส่วนตัว (Decryption Key) D ให้สมการต่อไปนี้เป็นจริง:

   (D × E) mod (P−1) × (Q−1) = 1

   • แทนค่า E, P, Q: (D × 5) mod (6) × (16) = 1
   • นั่นคือ (D × 5) mod 96 = 1
   • ลองคำนวณได้ D = 77 ตรวจสอบ: (77 × 5) mod 96 = 385 mod 96 = 1 ✓

5. การเข้ารหัส (Encryption) คำนวณข้อความเข้ารหัส (CT) จากข้อความต้นฉบับ (PT):

   CT = PT^E mod N

   สมมติเข้ารหัส PT = 10:

   CT = 10⁵ mod 119 = 100,000 mod 119 = 40

6. ส่ง CT = 40 ให้ผู้รับ

7. การถอดรหัส (Decryption) คำนวณข้อความต้นฉบับ (PT) จากข้อความเข้ารหัส (CT):

   PT = CT^D mod N

   PT = 40⁷⁷ mod 119 = 10 ซึ่งเป็นข้อความต้นฉบับเดิม ✓