เป็นไปได้อย่างไรที่จะได้รับเลขชี้กำลังสาธารณะจากคีย์ส่วนตัว RSA

ถามว่าใน RSA มีใครพบ $e$ ที่ให้ไว้ $d$ และ $N$. ฉันจะเพิกเฉยต่อข้อกำหนดของคำถามที่ว่า $e$ เป็นโคไพร์มด้วย $N$ซึ่งผิดปกติอย่างมากและไม่มีความเกี่ยวข้องทางคณิตศาสตร์ ฉันจะถือว่า $p\ne คิว$เพราะมันจำเป็นสำหรับที่ระบุไว้ $\varphi(N)=(p-1)\cdot(q-1)$ ที่จะถือ

ด้วยนิยามของคำถาม RSA วิธีค้นหา $e$ ไป

• ปัจจัย $N$ การค้นหา $p$ และ $คิว$
• คำนวณ $\varphi=(p-1)\cdot(q-1)$
• คำนวณ $e$ รู้ $e\cdot d\bmod\varphi=1$ และ $1<e<\varphi$. ที่ $e$ ถูกกำหนดโดยเฉพาะและส่วนผกผันของโมดูลาร์ของ $d$ ใน กลุ่มคูณของโมดูโลจำนวนเต็ม $\varphi$. สำหรับจำนวนน้อย วิธีการทำงานคือการลองผิดลองถูกจำนวนน้อย $e>1$. วิธีการที่สร้างสรรค์กว่าคือ (ครึ่ง)-อัลกอริทึมแบบยุคลิดแบบขยายซึ่งคำนวณ $e=d^{-1}\bmod \varphi$ โดยตรง. สำหรับอัลกอริทึมเชิงปฏิบัติที่ใช้เฉพาะจำนวนเต็มที่ไม่เป็นลบ:
  1. $a\gets d\bmod \varphi$ , $b\gets \varphi$ , $x\get0$ และ $y\get1$
     บันทึก: $a\cdot x+b\cdot y=\varphi$ จะถือต่อไป
  2. ถ้า $a=1$จากนั้นเอาต์พุต "ผกผันที่ต้องการ $e$ ของ $d$ โมดูโล $\varphi$ เป็น $y$" และหยุด
  3. ถ้า $a=0$จากนั้นเอาต์พุต "ผกผันที่ต้องการ $e$ ของ $d$ โมดูโล $\varphi$ ไม่ได้อยู่" และหยุด
  4. $r\gets\fชั้น b/a\rชั้น$
  5. $b\gets b-a\cdot r$ และ $x\gets x+r\cdot y$
  6. ถ้า $b=1$จากนั้นเอาต์พุต "ผกผันที่ต้องการ $e$ ของ $d$ โมดูโล $\varphi$ เป็น $\varphi-x$" และหยุด
  7. ถ้า $b=0$จากนั้นเอาต์พุต "ผกผันที่ต้องการ $e$ ของ $d$ โมดูโล $\varphi$ ไม่ได้อยู่" และหยุด
  8. $r\gets\fชั้น a/b\rชั้น$
  9. $a\gets a-b\cdot r$ และ $y\gets y+r\cdot x$
  10. ต่อที่ 2

โดยทั่วไปใช้วิธีเดียวกันนี้ในการคำนวณ $d$ จาก $e$, เนื่องจาก $d$ และ $e$ มีความสมมาตรใน $e\cdot d\bmod\varphi=1$. อย่างไรก็ตามนั่นไม่ใช่วิธีการ $d=11$ ถูกคำนวณในคำถาม ด้วยเหตุผลบางอย่างที่คำถามต้องการ $e<\varphi(N)$ แต่ไม่ $d<\varphi(N)$หรือมากกว่าปกติ $d<N$ หรือ $d<\ชื่อผู้ประกอบการ{lcm}(p-1,q-1)$.

ปัญหาร้ายแรงเกี่ยวกับแนวทางนี้สำหรับ RSA ตามที่ปฏิบัติ (ซึ่งมีขนาดใหญ่มาก $N$, ทศนิยมอย่างน้อยหลายร้อยหลัก): ใช้ไม่ได้เพราะ $N$ จะมีมากจนแยกตัวประกอบไม่ได้ ดังนั้น $\varphi$ ไม่สามารถคำนวณด้วยวิธีนี้ได้

อีกทั้งเงื่อนไขของคำถาม $e\cdot d\bmod\varphi(N)=1$ เป็นเงื่อนไขที่เพียงพอ แต่ไม่ใช่เงื่อนไขที่จำเป็นสำหรับการเข้ารหัส RSA แบบเรียน $(จ,น)$ จะถูกยกเลิกโดยการถอดรหัส RSA โดยใช้ $(d,N)$, และในทางกลับกัน. เงื่อนไขที่จำเป็นคือ $e\cdot d\bmod\lambda(N)=1$, ที่ไหน $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. เงื่อนไขนั้นมักใช้ในทางปฏิบัติ: ได้รับอนุญาตจาก พีเคซีเอส#1และได้รับอาณัติจาก ม.ป.ป.186-4. ตัวอย่างเล็ก ๆ เทียม: $N=341$, $e=7$, $d=13$ ใช้งานได้ดีสำหรับการเข้ารหัส/ถอดรหัส RSA แบบเรียน $e\cdot d\bmod\varphi(N)=1$ ไม่ถือ (ในตัวอย่างนี้ $p=11$, $q=31$, $\varphi(N)=300$, $\แลมบ์ดา(N)=30$ ).

อย่างไรก็ตาม ใน RSA ในทางปฏิบัติ $e$ มีขนาดเล็กก็มักจะมีขนาดเล็กนั่นเอง $e$ สามารถพบได้โดยการแจงนับ ดังนั้นวิธีการอาจเป็น:

• คำนวณ $c\gets2^d\bmod N$
• คำนวณ $c_2\gets c^2\bmod N$
• ชุด $e\get1$
• ทำซ้ำ
  • ชุด $e\ได้ e+2$
  • ชุด $c\gets c\cdot c_2\bmod N$; สังเกต $c=2^{d\cdot e}\bmod N$
  • ถ้า $ค=2$
    • สำหรับ $m$ หนึ่งร้อยจำนวนเฉพาะแรก (หมายเหตุ: สำหรับจำนวนน้อย $N$เราต้องการหยุดทันทีที่ $m^2>N$ )
      • ถ้า $m^{e\cdot d}\bmod N\ne m$, ต่อที่ ทำซ้ำ ข้างต้น
    • เอาต์พุต $e$ และหยุด

เกือบจะแน่นอนว่าถ้า $e$ เป็นเอาต์พุตก็ใช้ได้ในแง่ที่ว่าการเข้ารหัส RSA แบบเรียนใช้ $(จ,น)$ ถูกยกเลิกโดยการถอดรหัส RSA โดยใช้ $(d,N)$, และ (เทียบเท่า) $e\cdot d\bmod\lambda(N)=1$. มันไม่ค่อยแน่ใจ $e\cdot d\bmod\varphi(N)=1$แต่ที่รู้ๆ $e\cdotd$ และ $N$ เป็นไปได้ที่จะแยกตัวประกอบ $N$ (โดยใช้ นี้ อัลกอริทึม) แล้วคำนวณ เดอะ $e$ กับ $e\cdot d\bmod\varphi(N)=1$ และ $1<e<\varphi(N)$ถ้าต้องการด้วยเหตุผลบางอย่าง

นอกจากนี้: ข้างต้นยังห่างไกลจากความเหมาะสม เมื่อไร $\delta=\ln(e)/\ln(N)$ ต่ำกว่าเกณฑ์ที่กำหนดตามลำดับ $0.292$มีวิธีที่จะแยกตัวประกอบ $N$ (และแก้ปัญหาด้วยวิธีแรกที่กล่าวถึง) โดยทั่วไปเราแลกเปลี่ยน $d$ และ $e$ ใน Dan Boneh และ Glenn Durfee's การเข้ารหัสของ RSA ด้วยคีย์ส่วนตัว $d$ น้อยกว่า $N^{0.292}$, ใน การดำเนินการของ Eurocrypt 1999. ดู ที่นั่น สำหรับข้อมูลเพิ่มเติม