มีตัวแปรที่มีประสิทธิภาพของ RSA โดยใช้ CRT:
\begin{align*} d_p &= d \pmod{p-1}\ d_q &= ง \pmod{p-1} \ q_{\operatorname{inv}} &= q^{-1} \pmod{p} \end{จัดตำแหน่ง*}
โดยทำการถอดรหัสดังนี้
\begin{align*} c_p &= ค \pmod{p} \ c_q &= ค \pmod{q} \ m_p &= c_p^{d_p} \pmod{p} \ m_q &= c_q^{d_q} \pmod{q} \ h &= q_{\operatorname{inv}}(m_p - m_q) \pmod{p} \end{จัดตำแหน่ง*}
คำถามแรกของฉันค่อนข้างกว้าง: ฉันจะใช้อัลกอริทึม CRT ได้ที่ไหน (ตามที่เขียนไว้ที่นั่น) ฉันหมายถึงการตั้งค่า RSA กำหนดฉันแล้ว $p,q,d,c$ ดังนั้นฉันจึงไม่มีระบบที่สอดคล้องกัน
คำถามที่สองของฉันเกี่ยวข้องกับความซับซ้อน สมมติ $\log d = \log n = B$ และ $\log p = \log q = \frac{B}{2}$ และ $d, d_p, d_q$ มีมากมายไม่แพ้กัน $0$ทราย $1$ส. ฉันจะพูดอะไรเกี่ยวกับจำนวนการดำเนินการของขนาด $B$ ของตัวแปรนี้?
มีตัวแปรที่มีประสิทธิภาพของ RSA โดยใช้ CRT
ตามวิธีที่เราใช้คำศัพท์โดยทั่วไป มันไม่ใช่ 'ตัวแปร' แต่เป็นการใช้งานทางเลือกแทน นั่นคือ การเปลี่ยนแปลงที่ทำกับอัลกอริทึม RSA เท่านั้นที่ทำกับการดำเนินการส่วนตัว (และรูปแบบของคีย์ส่วนตัว) ใครก็ตามที่ดำเนินการเฉพาะสาธารณะไม่จำเป็นต้องมีความรู้ว่าการใช้งานส่วนตัว (การสร้างลายเซ็นหรือถอดรหัสคีย์สาธารณะ) กำลังทำอะไรอยู่
ฉันจะใช้อัลกอริทึม CRT ได้ที่ไหน (ตามที่เขียนไว้ที่นั่น)
เมื่อใดก็ตามที่คุณต้องการประสิทธิภาพที่เพิ่มขึ้น (4 เท่า) และไม่ต้องกังวลกับความซับซ้อนที่เพิ่มขึ้นเล็กน้อย ส่วนใหญ่แล้วนี่เป็นการแลกเปลี่ยนที่คุ้มค่า
ฉันหมายถึงการตั้งค่า RSA กำหนดฉัน p,q,d,c อยู่แล้ว ดังนั้นฉันจึงไม่มีระบบที่สอดคล้องกัน
ที่จริงแล้ว พารามิเตอร์เพิ่มเติมทั้งหมด $d_p, d_q, qinv$ คำนวณได้อย่างง่ายดายในช่วงเวลาการสร้างคีย์ และนั่นคือสิ่งที่เรามักจะทำ
สมมติ $\log d = \log n=B$ และ $\log p = \log q = B/2$ และ $d,d_p,d_q$ มี 0 และ 1 จำนวนเท่าๆ กัน ฉันจะพูดอะไรเกี่ยวกับจำนวนการดำเนินการของขนาด $B$ ของตัวแปรนี้?
ที่จริงแล้ว จำนวน 0 และ 1 ส่วนใหญ่ไม่เกี่ยวข้องกัน เราสามารถทำการยกกำลังแบบโมดูลาร์ของ $B$ ค่าบิตด้วย $(1 + o(1)) \log_2 B$ การคูณแบบโมดูลาร์ (ขึ้นอยู่กับน้ำหนักการตอกของเลขยกกำลัง); อยู่ในช่วงการพิจารณาของ B อาจเป็นได้ $(1 + 1/6) \log_2 B$.
ด้วยการดำเนินการส่วนตัวของตำราเรียน RSA สิ่งนี้เกี่ยวข้องกับการยกกำลังแบบโมดูลาร์เดียวของ a $B$ ค่าบิตโดย a $B$ เลขชี้กำลังบิต; เป็นเรื่องเกี่ยวกับ $(1 + 1/6) \log_2 B$ ทวีคูณ ถ้าเราใช้ $O(n^2)$ อัลกอริธึมการคูณแบบแยกส่วน (ซึ่งเหมาะสมที่สุดสำหรับช่วงของ B ที่เราพูดถึง - มีรูทีนการคูณที่มีความซับซ้อนเชิงซีมโทติคต่ำกว่า แต่มีค่าคงที่ของสัดส่วนที่มากกว่า) เรากำลังพูดถึง $(1 + 1/6) (\log_2 B)^3$
ตอนนี้ ด้วย CRT มีการยกกำลังแบบโมดูลาร์ของสอง $B/2$ ทีละนิด $B/2$ เลขชี้กำลังบิต (รวมถึงการดำเนินการบางอย่างทั้งก่อนและหลัง - ทั้งสองอย่างค่อนข้างรวดเร็ว) ใช้ตรรกะเดียวกันก็ประมาณนี้ $2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B)$นั่นคือเร็วประมาณ 4 เท่า (ใช่ นี่คือการเพิกเฉยต่อปัจจัยเล็กๆ น้อยๆ) แม้ว่าเราจะคำนึงถึงปัจจัยเล็กๆ เหล่านั้น แต่ CRT ก็ยังคงอยู่ อย่างมาก เร็วขึ้น
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
