เครื่องจำลองการเข้ารหัส RSA ทีละขั้นตอน

การเข้ารหัส RSA คืออะไร?

RSA (Rivest-Shamir-Adleman) เป็นหนึ่งในระบบรหัสลับแบบกุญแจสาธารณะ (Public-key Cryptosystem) ระบบแรกๆ เผยแพร่ในปี 1977 โดย Ron Rivest, Adi Shamir และ Leonard Adleman ต่างจากการเข้ารหัสแบบสมมาตร (ที่ใช้กุญแจดอกเดียวกันในการเข้ารหัสและถอดรหัส) RSA ใช้ คู่กุญแจ (Key Pair): กุญแจสาธารณะที่ใครๆ ก็ใช้เข้ารหัสข้อมูลได้ และกุญแจส่วนตัวที่มีเพียงเจ้าของเท่านั้นที่ใช้ถอดรหัสได้

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

ขั้นตอนการสร้างกุญแจ RSA

กระบวนการสร้างกุญแจ RSA ประกอบด้วย 5 ขั้นตอนพื้นฐาน:

• ขั้นตอนที่ 1 – เลือกจำนวนเฉพาะ: เลือกจำนวนเฉพาะ p และ q ที่แตกต่างกันและมีค่ามาก ยิ่งจำนวนเหล่านี้ใหญ่เท่าไหร่ กุญแจก็จะยิ่งปลอดภัยมากขึ้น
• ขั้นตอนที่ 2 – คำนวณ Modulus: คำนวณ n = p × q ความยาวบิตของ n จะเป็นตัวกำหนดขนาดของกุญแจ (เช่น 2048 บิต)
• ขั้นตอนที่ 3 – ฟังก์ชันโทเชียนต์ของออยเลอร์: คำนวณ φ(n) = (p−1)(q−1) ค่านี้สำคัญมากในการเลือก e และคำนวณ d
• ขั้นตอนที่ 4 – เลขชี้กำลังสาธารณะ: เลือก e โดยที่ 1 < e < φ(n) และ ห.ร.ม.(e, φ(n)) = 1 ตัวเลือกมาตรฐานคือ 65537
• ขั้นตอนที่ 5 – เลขชี้กำลังส่วนตัว: คำนวณ d โดยใช้อัลกอริทึมแบบยุคลิดส่วนขยาย (Extended Euclidean Algorithm) เพื่อให้ d × e ≡ 1 (mod φ(n))

อัลกอริทึมแบบยุคลิดส่วนขยาย (Extended Euclidean Algorithm)

การคำนวณเลขชี้กำลังส่วนตัว d ต้องใช้การหา ตัวผกผันการคูณมอดุลาร์ (Modular Multiplicative Inverse) ของ e มอดุโล φ(n) อัลกอริทึมแบบยุคลิดส่วนขยายช่วยแก้ปัญหานี้ได้อย่างมีประสิทธิภาพ โดยขยายจากอัลกอริทึม ห.ร.ม. มาตรฐานเพื่อหาค่าสัมประสิทธิ์ x และ y ที่ทำให้ a·x + b·y = ห.ร.ม.(a, b)

เมื่อ ห.ร.ม.(e, φ(n)) = 1 อัลกอริทึมจะให้ค่า x ที่ทำให้ e·x ≡ 1 (mod φ(n)) ซึ่งจะได้ d = x mod φ(n)

ข้อควรพิจารณาด้านความปลอดภัยของ RSA

• ขนาดกุญแจ: RSA สมัยใหม่ใช้กุญแจขนาด 2048 หรือ 4096 บิต จำนวนเฉพาะขนาดเล็กในตัวจำลองนี้มีไว้เพื่อการศึกษาเท่านั้นและสามารถแยกตัวประกอบได้ทันที
• รูปแบบการเติมข้อมูล (Padding): ในการใช้งานจริง RSA จะใช้การเติมข้อมูล (เช่น OAEP, PKCS#1) เพื่อป้องกันการโจมตีทางคณิตศาสตร์ต่อข้อมูลดิบ
• ประสิทธิภาพ: RSA ช้ากว่าการเข้ารหัสแบบสมมาตรมาก ในทางปฏิบัติ RSA มักใช้เข้ารหัสกุญแจสมมาตรแบบสุ่ม แล้วจึงใช้กุญแจนั้นเข้ารหัสข้อมูลจริง (การเข้ารหัสแบบผสม หรือ Hybrid Encryption)
• ภัยคุกคามจากควอนตัม: อัลกอริทึมของ Shor บนคอมพิวเตอร์ควอนตัมที่มีประสิทธิภาพเพียงพอ สามารถแยกตัวประกอบจำนวนขนาดใหญ่ได้อย่างรวดเร็ว ซึ่งเป็นภัยต่อ RSA ปัจจุบันมีการพัฒนาวิทยาการรหัสลับหลังควอนตัม (Post-quantum cryptography) เพื่อเป็นมาตรการตอบโต้

การใช้งาน RSA ในทางปฏิบัติ

• TLS/SSL (HTTPS): RSA ถูกใช้ในระหว่างการ Handshake เพื่อแลกเปลี่ยนกุญแจเซสชันแบบสมมาตรอย่างปลอดภัย
• ลายเซ็นดิจิทัล: RSA ใช้ลงนามในเอกสารโดยการเข้ารหัสค่าแฮชด้วยกุญแจส่วนตัว ซึ่งตรวจสอบได้ด้วยกุญแจสาธารณะ
• การเข้ารหัสอีเมล: PGP และ S/MIME ใช้ RSA ในการเข้ารหัสการสื่อสารทางอีเมล
• การตรวจสอบสิทธิ์ SSH: คู่กุญแจ RSA ช่วยให้สามารถตรวจสอบสิทธิ์เพื่อเข้าถึงเซิร์ฟเวอร์ระยะไกลได้โดยไม่ต้องใช้รหัสผ่าน
• การลงนามรหัส (Code Signing): ผู้เผยแพร่ซอฟต์แวร์ลงนามในไฟล์ที่รันได้ด้วย RSA เพื่อพิสูจน์ความแท้จริงและความถูกต้องของข้อมูล

คำถามที่พบบ่อย