ขั้นตอนของ RSA ในความปลอดภัยข้อมูล

อัลกอริทึม RSA เป็นอัลกอริทึมลายเซ็นคีย์สาธารณะที่พัฒนาโดย Ron Rivest, Adi Shamir และ Leonard Adleman RSA ยังสามารถเข้ารหัสและถอดรหัสข้อมูลทั่วไปเพื่อแลกเปลี่ยนข้อมูลอย่างปลอดภัย พร้อมกับการจัดการการตรวจสอบลายเซ็นดิจิทัล

อัลกอริทึม RSA พึ่งพาความซับซ้อนของการแยกตัวประกอบจำนวนขนาดใหญ่ RSA ขึ้นอยู่กับข้อเท็จจริงที่ว่าไม่มีวิธีที่มีประสิทธิภาพในการแยกตัวประกอบจำนวนขนาดใหญ่มาก ดังนั้นการ推导คีย์ RSA จะใช้เวลาและกำลังประมวลผลมหาศาล

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

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

ขั้นตอนในอัลกอริทึม RSA

1. การสร้างคีย์ (Generating the Keys)

• เลือกจำนวนเฉพาะขนาดใหญ่สองจำนวน คือ P และ Q (ต้องใหญ่พอที่จะยากต่อการค้นหา)
• คำนวณ N = P × Q
• เลือกคีย์สาธารณะ (Encryption Key) E ที่ไม่ใช่ตัวประกอบของ (P−1) และ (Q−1)
• เลือกคีย์ส่วนตัว (Decryption Key) D ให้สมการนี้เป็นจริง:
  (D × E) mod (P−1) × (Q−1) = 1
• เข้ารหัส: คำนวณ CT จาก PT ด้วย CT = PT^E mod N
• ส่ง CT ให้ผู้รับ
• ถอดรหัส: คำนวณ PT จาก CT ด้วย PT = CT^D mod N

2. ฟังก์ชันเข้ารหัส/ถอดรหัส (Encryption/Decryption Function)

หลังจากสร้างคีย์แล้ว สามารถส่งพารามิเตอร์ไปยังฟังก์ชันที่คำนวณข้อความเข้ารหัสและข้อความต้นฉบับโดยใช้คีย์แต่ละคีย์

• ถ้าข้อความต้นฉบับคือ m, ข้อความเข้ารหัส = m^e mod n
• ถ้าข้อความเข้ารหัสคือ c, ข้อความต้นฉบับ = c^d mod n

3. ตัวอย่างตัวเลข

ให้ p = 17, q = 13 ค่า e สามารถเป็น 5 ได้ เพราะตรงเงื่อนไข 1 < e < (p−1)(q−1)

• N = p × q = 91
• D = e⁻¹ mod (p−1)(q−1) = 29
• คู่คีย์สาธารณะ = (91, 5)
• คู่คีย์ส่วนตัว = (91, 29)
• ถ้าข้อความต้นฉบับ m = 10 เข้ารหัสด้วย m^e mod n = 10⁵ mod 91 = 82
• ถอดรหัส c = 82 ด้วย c^d mod n = 82²⁹ mod 91 = 10 (คืนค่าต้นฉบับ) — หมายเหตุ: บทความต้นฉบับเขียนผลลัพธ์เป็น 29 ซึ่งอาจเป็นข้อผิดพลาด ค่าที่ถูกต้องคือ 10