การรั่วไหลของ $k$ ใน RSA นั้นเลวร้ายแค่ไหน?

ใน RSA โดยใช้เลขยกกำลังสาธารณะขนาดเล็ก $e$ เช่น $65537$, มันแย่แค่ไหนถ้าค่า $k$ รั่วไหล? $k$ ดังสมการต่อไปนี้

$ed - 1 = k \phi(n)$

หรือ

$ed - 1 = k \cdot \operatorname{lcm}(p-1,q-1)$

โดยสังหรณ์ใจแล้ว สิ่งนี้จะลดความซับซ้อนของการทำลายระบบลงเท่านั้น $65535$ ครั้งไม่มีที่ไหนใกล้พอที่จะมีความสำคัญแม้ว่าฉันจะคิดว่า GNFS จะไม่ได้รับการปรับปรุงโดยการรู้ $k$.

แก้ไข: สิ่งนี้เกิดขึ้นในความคิดว่าจะเกิดอะไรขึ้นถ้า สูง บิตของ $d$ รั่วไหลเมื่อเทียบกับบิตต่ำ บิตต่ำของ $d$ การรั่วไหลนำไปสู่การแยกตัวประกอบที่สำคัญ อย่างไรก็ตามส่วนสูงก็เปิดเผย $k$, เพราะ $n$ สามารถใช้เป็นค่าประมาณของ $\phi(n)$ เพื่อคำนวณครึ่งสูงของ $d$ ที่ให้ไว้ $k$.

มันไม่เลวเลย

ข้อโต้แย้งเชิงปฏิบัติ: การคำนวณการใช้งานจำนวนมาก $d$ เช่น $e^{-1} \mod \mathrm{lcm}(p-1,q-1)$ (OpenSSL, wolfCrypt, Mbed TLS) หรือ $e^{-1} \mod \mathrm{(p-1)(q-1)}$ (Cryptlib, ตำแย). ดังนั้น ในทางปฏิบัติ คู่ต่อสู้สามารถคาดเดาได้ดีอยู่ดี

อาร์กิวเมนต์ Meta: เลขชี้กำลังส่วนตัวของ RSA ที่ตรงกับคีย์สาธารณะ $(น,อี)$ แต่อย่างใด $d$ ดังนั้น $\forall x, (x^e)^d = x \mod{n}$. ตัวเลือกใดก็ได้ที่จะทำ â มิฉะนั้นการถอดรหัส RSA จะไม่ทำงาน เนื่องจากการเข้ารหัสขึ้นอยู่กับ $n$ และ $e$. ดังนั้นการเปิดเผยว่าตัวเลือกใดของ $d$ การใช้ผู้ถือคีย์ส่วนตัวจะไม่ทำให้ข้อมูลใด ๆ เกี่ยวกับคีย์ส่วนตัวรั่วไหล มันรั่วเฉพาะข้อมูลเกี่ยวกับวิธีการทำงานของคีย์ส่วนตัวเท่านั้น

อาร์กิวเมนต์ทางคณิตศาสตร์: คุณเลือกเลขยกกำลังส่วนตัว $d = k \, a$ ที่ไหน $a = \mathrm{lcm}(p-1,q-1)$. สมมติว่าฝ่ายตรงข้ามพบค่าของ $k$และใช้ความรู้นี้เพื่อค้นหาเลขชี้กำลังส่วนตัวของผู้สมัคร $d'$. ฝ่ายตรงข้ามทดสอบการคาดเดาโดยการคำนวณ $(x^e)^{d'} \mod{n}$. ไม่สำคัญว่าพวกเขาจะพบเลขชี้กำลังส่วนตัวเดียวกันกับที่คุณใช้หรือไม่ ซึ่งไม่ส่งผลต่อการตรวจสอบความถูกต้องของการคาดเดา $d'$และไม่ส่งผลกระทบต่อประโยชน์ของการรู้ $d'$.

เหตุผลเดียวที่รั่วไหล $k$ สิ่งที่สำคัญคือหากมีช่องทางด้านข้างในการดำเนินการของการดำเนินการคีย์ส่วนตัว และการรู้ว่ามีการใช้เลขชี้กำลังส่วนตัวใดจะช่วยในการใช้ประโยชน์จากช่องทางด้านข้างนี้ สำหรับการวิเคราะห์ทางคณิตศาสตร์ ขั้นตอนที่ได้รับผลกระทบคือ “ใช้ความรู้นี้เพื่อค้นหาเลขชี้กำลังส่วนตัวของผู้สมัคร”: หากขั้นตอนนี้ใช้รายละเอียดภายในของการใช้งานของคุณ มันอาจจะง่ายกว่าถ้า $k$ เป็นที่รู้จัก สิ่งนี้เกี่ยวข้องกับการใช้งานที่ใช้เลขชี้กำลังส่วนตัวเท่านั้น: การใช้งานส่วนใหญ่ใช้การปรับให้เหมาะสม CRT โดยมีการยกกำลังเป็นพลังของ $d_P$ และ $d_Q$และขนาดของค่าทั้งสองนั้นไม่มีความสัมพันธ์กับขนาดของ $d$ (เพื่อสร้างความสัมพันธ์ดังกล่าว คุณจำเป็นต้องรู้ $p$ และ $คิว$ซึ่งจะเป็นการแตกแยกของมันเอง) ช่องด้านข้างมีแนวโน้มที่จะเปิดเผยขนาดโดยประมาณของ $d$ ถึงอย่างไร. ช่องด้านข้างที่รั่วไหลของข้อมูลบางอย่างเกี่ยวกับ $d$ การไม่เปิดเผยขนาดของมันดูเกินจริงสำหรับฉัน แต่ฉันไม่มีข้อโต้แย้งที่ชัดเจนว่ามันไม่สามารถเกิดขึ้นได้