RSA เป็นระบบการเข้ารหัสลับสำหรับการเข้ารหัสคีย์สาธารณะ และใช้กันอย่างแพร่หลายสำหรับการรักษาความปลอดภัยข้อมูลที่ตอบสนอง โดยเฉพาะเมื่อส่งผ่านเครือข่ายที่ไม่ปลอดภัยรวมทั้งอินเทอร์เน็ต
ในการเข้ารหัส RSA ทั้งคีย์สาธารณะและคีย์ส่วนตัวสามารถเข้ารหัสข้อความได้ คีย์ผกผันจากรหัสที่ใช้ในการเข้ารหัสข้อความใช้เพื่อถอดรหัส คุณลักษณะนี้เป็นเหตุผลหนึ่งที่ RSA ได้พัฒนาเป็นอัลกอริธึมที่ไม่สมมาตรที่ใช้กันอย่างแพร่หลายที่สุด สนับสนุนแนวทางการรักษาความลับ ความสมบูรณ์ ความถูกต้อง และความไม่น่าเชื่อถือของการเชื่อมต่อทางดิจิทัลและการจัดเก็บข้อมูล
RSA ต้องการกลุ่มการคูณ G =
อัลกอริทึมการสร้างคีย์สาธารณะและส่วนตัวเป็นองค์ประกอบที่ยากที่สุดของการเข้ารหัส RSA มีการสร้างจำนวนเฉพาะขนาดใหญ่สองจำนวนคือ p และ q โดยใช้อัลกอริธึมการทดสอบของ Rabin-Miller เป็นหลัก
โมดูลัส n คำนวณโดยการคูณ p และ q หมายเลขนี้สามารถใช้ได้ทั้งกับกุญแจสาธารณะและส่วนตัว และสนับสนุนการเชื่อมต่อระหว่างกัน ความยาวซึ่งโดยทั่วไปกำหนดเป็นบิตเรียกว่าความยาวคีย์
กุญแจสาธารณะประกอบด้วยโมดูลัส n และเลขชี้กำลังสาธารณะ e ซึ่งปกติตั้งไว้ที่ 65537 เนื่องจากเป็นจำนวนเฉพาะที่ไม่ใหญ่เกินไป ตัวเลข e ไม่จำเป็นต้องเป็นหมายเลขเฉพาะที่เลือกไว้เป็นการส่วนตัว เนื่องจากจะมีการแชร์คีย์สาธารณะกับทุกคน
คีย์ส่วนตัวรวมถึงโมดูลัส n และเลขชี้กำลังส่วนตัว d ซึ่งคำนวณโดยใช้อัลกอริธึม Extended Euclidean เพื่อค้นหาผกผันการคูณที่เกี่ยวข้องกับค่าโทเทนต์ของ n
เมื่อพิจารณาโมดูโลเลขคณิต n ให้เราบอกว่า e เป็นจำนวนเต็มที่ร่วมเฉพาะกับ totient φ(n) ของ n นอกจากนี้ยังสามารถพูดได้ว่า d เป็นตัวผกผันการคูณของ e modulo φ (n) คำจำกัดความของสัญลักษณ์ต่างๆ เหล่านี้แสดงไว้ด้านล่างเพื่อความสะดวก:
n =โมดูลัสสำหรับเลขคณิตแบบแยกส่วน
φ (n) =ผลรวมของ n
e =จำนวนเต็มที่เชื่อมโยงเฉพาะกับ φ(n)
[T เขารับประกันว่า e จะมีโมดูโลผกผันการคูณ φ(n)]
d =จำนวนเต็มที่เป็นตัวผกผันการคูณของ e modulo φ(n)
ขั้นตอนการคำนวณสำหรับการสร้างคีย์คือ
-
สร้างจำนวนเฉพาะที่แตกต่างกันสองจำนวนรวมถึง p และ q
-
คำนวณโมดูลัส n =p × q
-
คำนวณ totient φ(n) =(p − 1) × (q − 1)
-
เลือกเลขชี้กำลังสำหรับเลขชี้กำลังสาธารณะ e เช่น 1
-
คำนวณหาค่าเลขชี้กำลังไพรเวตสำหรับ d โดยที่ d =e-1 mod φ(n)
-
กุญแจสาธารณะ =[e, n]
-
คีย์ส่วนตัว =[d, n]
