อัลกอริทึม RSA คำนวณอย่างไร

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

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

ตัวอย่างอัลกอริทึม RSA

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

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

  ให้ P =47, Q =17

• คำนวณ N =P x Q

  เรามี N =7 x 17 =119

• เลือกคีย์สาธารณะ (เช่น คีย์เข้ารหัส) E เพื่อไม่ให้เป็นองค์ประกอบของ (P -1) x (Q – 1)

  • ให้เราหา (7 - 1) x (17 -1) =6 x 16 =96

  • ตัวประกอบของ 96 คือ 2, 2, 2, 2, 2 และ 3 (เพราะ 96 =2 x 2 x 2 x 2 x 2 x 3)

  • ดังนั้นจึงสามารถเลือก E ได้ โดยที่ตัวประกอบของ E ตัวใดตัวหนึ่งไม่เป็น 2 และ 3 เราไม่สามารถเลือก E เป็น 4 ได้ (เพราะมันมีตัวประกอบ 2 ตัว), 15 (เพราะมี 3 ตัวเป็นตัวประกอบ) และ 6 (เพราะมันมีตัวประกอบอยู่ 3 ตัว) มี 2 ​​และ 3 ทั้งคู่เป็นตัวประกอบ)

  • ให้เราเลือก E เป็น 5 (อาจเป็นตัวเลขอื่นที่ไม่ใช่ตัวประกอบเป็น 2 และ 3)

• เลือกคีย์ส่วนตัว (เช่น คีย์ถอดรหัส) D รวมทั้งสมการต่อไปนี้เป็นจริง:

  (D x E) mod (P – 1) x (Q – 1) =1

  • ให้เราแทนค่า E, P และ Q ในสมการ

  • เรามี (D x 5) mod (7 – 1) x (17 – 1) =1.

  • นั่นคือ (D x 5) mod (6) x (16) =1

  • นั่นคือ (D x 5) mod (96) =1

  • หลังจากคำนวณแล้ว ให้เราใช้ D =77 จากนั้นสิ่งต่อไปนี้ก็เป็นจริง:(77 x 5) mod (96) =385 mod 96 =1 ซึ่งเป็นสิ่งที่เราต้องการ

• สำหรับการเข้ารหัส ให้คำนวณข้อความเข้ารหัส (CT) จากข้อความธรรมดา (PT) ดังนี้:

  CT =PT ^E mod N

  สมมติว่าเราต้องการเข้ารหัสข้อความธรรมดา 10 จากนั้นเรามี

  CT =10 ⁵ mod 119 =100000 mod 119 =40.

• ส่ง CT เป็นข้อความรหัสไปยังผู้รับ

  ส่ง 40 เป็นข้อความรหัสไปยังผู้รับ

• สำหรับการถอดรหัส ให้คำนวณข้อความธรรมดา (PT) จากข้อความเข้ารหัส (CT) ดังนี้:

  PT =CT ^D mod N

  มันดำเนินการดังต่อไปนี้:

  PT =CT ^D mod N

  นั่นคือ

  PT =40 ⁷⁷ mod 119 =10 ซึ่งเป็นข้อความธรรมดาดั้งเดิมของขั้นตอนที่ 5