อัลกอริทึม RSA เป็นอัลกอริธึมลายเซ็นคีย์สาธารณะที่ก่อตั้งโดย Ron Rivest, Adi Shamir และ Leonard Adleman RSA ยังสามารถเข้ารหัสและถอดรหัสข้อมูลทั่วไปเพื่อแลกเปลี่ยนข้อมูลได้อย่างปลอดภัยพร้อมกับการจัดการการตรวจสอบลายเซ็นดิจิทัล
อัลกอริทึม RSA ขึ้นอยู่กับความซับซ้อนที่มีอยู่ในการแยกตัวประกอบของจำนวนมาก อัลกอริธึม RSA ขึ้นอยู่กับข้อเท็จจริงที่ว่าไม่มีวิธีใดที่มีประสิทธิภาพในการแยกตัวประกอบตัวเลขจำนวนมาก ดังนั้น การอนุมานคีย์ RSA จึงต้องใช้เวลาและกำลังประมวลผลเป็นจำนวนมาก
อัลกอริธึม RSA เป็นอัลกอริธึมการเข้ารหัสแบบอสมมาตร เนื่องจากทำงานบนคีย์ที่แตกต่างกันสองคีย์ เช่น คีย์สาธารณะและคีย์ส่วนตัว กุญแจสาธารณะมักเป็นของทุกคน และคีย์ส่วนตัวยังคงเป็นส่วนตัว กุญแจสาธารณะประกอบด้วยตัวเลขสองตัว ซึ่งหนึ่งในนั้นเป็นการคูณจำนวนเฉพาะขนาดใหญ่สองตัว
ในการเข้ารหัส RSA ข้อความจะถูกเข้ารหัสด้วยรหัสที่เรียกว่ากุญแจสาธารณะซึ่งไม่จำเป็นต้องซ่อน โดยอิงตามคุณสมบัติทางคณิตศาสตร์ของอัลกอริทึม RSA เนื่องจากข้อความได้รับการเข้ารหัสด้วยกุญแจสาธารณะ จึงถอดรหัสได้ด้วยคีย์อื่นเท่านั้น ซึ่งเรียกว่าคีย์ส่วนตัว ดังนั้น จึงจำเป็นต้องใช้ชุดคีย์ ซึ่งเป็นคีย์สาธารณะและคีย์ส่วนตัวเพื่ออ่านข้อความดังกล่าว
มีขั้นตอนต่อไปนี้ในอัลกอริทึม RSA ซึ่งมีดังนี้ -
- กำลังสร้างคีย์
-
เลือกจำนวนเฉพาะขนาดใหญ่สองจำนวน เช่น P และ Q จำนวนเฉพาะที่ต้องการให้มีขนาดใหญ่ เพื่อที่จะได้ซับซ้อนสำหรับคนที่จะคิดออก
-
คำนวณ N =P x Q
-
เลือกคีย์สาธารณะ (เช่น คีย์เข้ารหัส) E เพื่อไม่ให้เป็นปัจจัยของ (P-1) และ (Q-1)
-
เลือกคีย์ส่วนตัว (เช่น คีย์ถอดรหัส) D เพื่อให้สมการต่อไปนี้เป็นจริง -
(D x E) mod (P - 1) x (Q – 1) =1
-
สำหรับการเข้ารหัส ให้คำนวณข้อความเข้ารหัส (CT) จากข้อความธรรมดา (PT) ดังนี้ -
CT =PT E mod N
-
ส่ง CT เป็นข้อความรหัสไปยังผู้รับ
-
สำหรับการเข้ารหัส ให้คำนวณข้อความธรรมดา (PT) จากข้อความเข้ารหัส (CT) ดังนี้ -
PT =CT D mod N
-
-
ฟังก์ชันการเข้ารหัส/ถอดรหัส − เมื่อสร้างคีย์ได้แล้ว และส่งพารามิเตอร์ไปยังฟังก์ชันที่คำนวณข้อความเข้ารหัสและข้อความธรรมดาโดยใช้คีย์ที่เกี่ยวข้องได้
-
หากข้อความธรรมดาคือ m แสดงว่า ciphertext =me mod n.
-
หากข้อความเข้ารหัสเป็น c ข้อความธรรมดา =cd mod n
-
-
ตัวอย่างเช่น โดยที่ p =17 และ q=13 ค่าของ e สามารถเป็น 5 ได้ เนื่องจากเป็นไปตามเงื่อนไข 1
N =p * q =91
D =e-1 mod (p-1) (q-1) =29
คู่กุญแจสาธารณะ =(91, 5)
คู่คีย์ส่วนตัว =(91, 29)
หากค่าข้อความธรรมดา (m) คือ 10 ก็สามารถเข้ารหัสได้โดยใช้สูตร me mod n =82
ในการถอดรหัสข้อความเข้ารหัสนี้กลับเป็นข้อมูลดั้งเดิม ควรใช้สูตร cd mod n =29
