home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

ขั้นตอนการสร้างคีย์ด้วยอัลกอริทึม RSA

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

ในการเข้ารหัส RSA ทั้งคีย์สาธารณะและคีย์ส่วนตัวสามารถเข้ารหัสข้อความได้ คีย์ตรงข้ามกับที่ใช้เข้ารหัสจะถูกใช้ในการถอดรหัส คุณสมบัตินี้เป็นเหตุผลหนึ่งที่ทำให้ RSA กลายเป็นอัลกอริทึมแบบอสมิตร (Asymmetric Algorithm) ที่นิยมใช้มากที่สุด รองรับการטיחความลับ ความสมบูรณ์ ความถูกต้อง และการปฏิเสธไม่ได้ (Non-repudiation) ของการเชื่อมต่อและการจัดเก็บข้อมูลดิจิทัล

RSA ต้องการกลุ่มเชิงคูณ (Multiplicative Group) G =< Zфn, *, X > สำหรับการสร้างคีย์ กลุ่มนี้ให้การคูณและการหารเท่านั้น ซึ่งจำเป็นสำหรับการสร้างคีย์สาธารณะและคีย์ส่วนตัว กลุ่มนี้ถูกเก็บเป็นความลับจากสาธารณะ เนื่องจากมอดุลัส φ(n) ถูกปิดบังจากสาธารณะ

อัลกอริทึมการสร้างคีย์สาธารณะและคีย์ส่วนตัว เป็นส่วนที่ซับซ้อนที่สุดของการเข้ารหัส RSA มีการสร้างจำนวนเฉพาะขนาดใหญ่สองจำนวน p และ q โดยใช้การทดสอบ Rabin-Miller

คำนวณมอดุลัส n = p × q จำนวนนี้ใช้ร่วมกันระหว่างคีย์สาธารณะและคีย์ส่วนตัว และเป็นตัวเชื่อมโยงระหว่างกัน ความยาวของ n โดยทั่วไปวัดเป็นบิต เรียกว่า ความยาวคีย์ (Key Length)

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

คีย์ส่วนตัวประกอบด้วย มอดุลัส n และเลขยกกำลังส่วนตัว d ซึ่งคำนวณโดยใช้อัลกอริทึมยุคลิดขยาย (Extended Euclidean Algorithm) เพื่อหาค่าผกผันเชิงคูณ (Multiplicative Inverse) เทียบกับทอเทียนต์ (Totient) ของ n

พิจารณาเลขคณิตแบบมอดุลัส n ให้ e เป็นจำนวนเต็มที่เป็นเฉพาะร่วมกับ φ(n) ของ n และ d เป็นผกผันเชิงคูณของ e มอดุลัส φ(n) สัญลักษณ์ต่างๆ สรุปดังนี้:

  • n = มอดุลัสสำหรับเลขคณิตแบบมอดุลัส
  • φ(n) = ทอเทียนต์ของ n
  • e = จำนวนเต็มที่เป็นเฉพาะร่วมกับ φ(n) [รับประกันว่า e จะมีผกผันเชิงคูณมอดุลัส φ(n)]
  • d = จำนวนเต็มที่เป็นผกผันเชิงคูณของ e มอดุลัส φ(n)

ขั้นตอนการคำนวณสร้างคีย์

  1. สร้างจำนวนเฉพาะสองจำนวนที่ต่างกัน คือ p และ q
  2. คำนวณมอดุลัส n = p × q
  3. คำนวณทอเทียนต์ φ(n) = (p − 1) × (q − 1)
  4. เลือกเลขยกกำลังสาธารณะ e เป็นจำนวนเต็ม ที่ 1 < e < φ(n) และ gcd(φ(n), e) = 1
  5. คำนวณเลขยกกำลังส่วนตัว d ที่ d = e−1 mod φ(n)
  6. คีย์สาธารณะ = [e, n]
  7. คีย์ส่วนตัว = [d, n]