ถ้า RSA ใช้ $e$ กับ $\gcd(e,\phi(N))\ne1$ แต่ $e$ นั้นแยกตัวประกอบได้ยาก ฝ่ายตรงข้ามยังคงได้เปรียบในการหา $d$ สำหรับ $m^{ed}\equiv m\mod N$?

โดยปกติแล้ว RSA จะใช้เลขชี้กำลังการเข้ารหัส $e$ กับ $\gcd(e,\phi(N))=1$.
นี้ คำถาม แสดงให้เห็นว่าเหตุใดจึงต้องเป็นเช่นนั้น: สำหรับ $\ne1$ อาจไม่มีเลขชี้กำลังการถอดรหัส $d$ เพราะอื่นๆ $m'\ne ม$ สามารถอยู่กับ $m^e \equiv (m')^e \bmod N$.

แต่ถ้าเราผลิตของเรา $m$ ชอบ: $$m = m_0^{e} \mod N$$ หรือทั่วไปมากกว่านั้น $$m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I}$$

เราสามารถค้นหาเลขชี้กำลังการถอดรหัสได้เสมอ (ยกเว้นกรณีพิเศษบางกรณีที่เราเพิกเฉย) $d$ สำหรับ $c \equiv m^e \mod N$ $$d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N)$$ กับ $$c^d \equiv (m^{e})^d \equiv m^{\displaystyle e^1\cdot e^{{\phi(\phi(N))-1}}} \equiv m^ {\displaystyle e^{{\phi(\phi(N))}}} \equiv m \mod N$$

แน่นอนข้อความนี้ $m$ ไม่สามารถส่งข้อมูลเป้าหมายได้มากนัก ข้อมูลบิตต่ำบางอย่างสามารถส่งได้โดยการสร้างแบบสุ่ม $m$ จนกว่าบิตแรกจะมีข้อมูลเป้าหมาย ไม่มีประสิทธิภาพเลย แต่นั่นไม่สำคัญที่นี่

คำถามคือ มันจะง่ายกว่า (มาก) หรือไม่สำหรับฝ่ายตรงข้ามในการค้นหาเลขชี้กำลังการถอดรหัส $d$ สำหรับการดังกล่าว $e$?

ถ้า $\gcd(e,\phi(N))\gg 1$ เป็นที่ทราบกันดีอยู่แล้วว่าการแยกตัวประกอบของ $N$ สามารถทำได้ง่ายขึ้นมากและด้วยการหยุดความปลอดภัยของ RSA
ไตรมาสที่ 1: แต่จะเกิดอะไรขึ้นถ้า $\gcd(e,\phi(N))\gg 1$ เป็น ไม่ เป็นที่รู้จัก? เพื่อให้แน่ใจว่าเราเลือก $e$ ซึ่งแยกตัวประกอบได้ยาก
มีศัตรูยังประโยชน์ใหญ่เพียงแค่รู้ $\gcd \ne1$ ?

อาจขึ้นอยู่กับปัจจัยที่เลือกอย่างมาก
เราถือว่าที่นี่ (กรณีการใช้งานเป้าหมาย) $$N = P \cdot Q$$ $$P = 2 \cdot p_s \cdot p_b +1$$ $$Q = 2 \cdot q_s \cdot q_b +1$$ $$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b$$ $$e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (แยกตัวประกอบยาก)}$$ $$\gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0 +1) = $$ $$B > 2^{2000} \text{ (แยกตัวประกอบยาก)}$$ $$\phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0)$$ $$\phi(p_s) \cdot \phi(q_s) /4= S \ประมาณ 2^{200} \ll B$$ (ในกรณีการใช้งานเป้าหมาย $p_s,q_s$ มีแบบฟอร์ม $p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1$)
(ตัวประกอบเฉพาะตัวแปรทั้งหมดไม่ซ้ำกัน)

$e$ จำเป็นต้องเป็นกำลังสองของโมดูโลรากดั้งเดิม $p_s$ และ $q_s$.
ด้วยวิธีนี้เราสามารถผลิต $S$ ค่าต่างกับ $m^{e^i} \bmod N$. ขึ้นอยู่กับการเริ่มต้น $m$ เราได้ชุดแยกขนาดนั้น 4 ชุด (รวมถึงกรณีพิเศษที่เล็กกว่าบางกรณีที่เราเพิกเฉยที่นี่)
ปัจจัยเพิ่มเติม $e_b$ จำเป็นต้องซ่อนความสัมพันธ์กับ $\phi(น)$ และ $B$. ด้วยสิ่งนี้ $e\gg N$ ที่นี่.
เราถือว่าฝ่ายตรงข้ามรู้เช่นกัน $S$ รวมถึงการแยกตัวประกอบเฉพาะด้วย

ไตรมาสที่ 2: คำถามที่เกี่ยวข้องกับกรณีการใช้งานยังอนุญาตค่าเป้าหมาย $n\ne ม$ แต่สร้างแบบ $(\text{I})$ (และรู้ว่ามีวิธีแก้ไข):
ปฏิปักษ์หาได้ $i$ ใน $n\equiv m^{e^i} \bmod N$ ด้วยเป็นที่รู้จัก $e,n,m,N,S$ เร็วกว่า $O(p_s + q_s) \ประมาณ O(\sqrt{S})$?
ซึ่งสามารถทำได้โดยการหาทางออกสำหรับ $j,k$ ใน $n^{\displaystyle p_s} \equiv (m^{\displaystyle {p_s}})^{e^j} \bmod N$ และ $n^{\displaystyle q_s} \equiv (m^{\displaystyle {q_s}})^{e^k} \bmod N$ ด้วยการทดสอบทีละขั้นตอน ก้าวยักษ์ไม่ได้ดั่งใจ $\phi(น)$ ไม่เป็นที่รู้จักและ $e^{2^{50}}$ ใหญ่เกินไปที่จะคำนวณโดยไม่ได้ หรือทำได้เร็วกว่านี้?

(ของเล่น)-ตัวอย่าง:
ที่นี่ $p_b,q_b < p_s,q_s$ ถูกนำมาใช้ ในกรณีการใช้งานเป้าหมายจะเป็น $p_b,q_b \gg p_s,q_s$ (และค่าทั้งหมดใหญ่กว่ามาก)

$N=P\cdot Q = 6565236619157488809896588016937$
$P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403$
$Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779$
$p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283$
$p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847$
$q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043$
$q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823$
$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756$ $\phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3$
$\phi(\phi(N)) = 3282361465954844745126356151456$

เลขยกกำลัง $e,d$ มีตัวประกอบขนาดใหญ่เพียงตัวเดียวที่จะทำให้การแยกตัวประกอบทำได้ยาก $e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $
$d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $

ที่นี่ $B<S$ แต่ในกรณีการใช้งานเป้าหมาย $B \gg S$ $S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353$
$B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676$

ศัตรูจะรู้ $N$,$e$,$S$ รวมทั้งการแยกตัวประกอบของ $S$. แต่เขาไม่รู้การแยกตัวประกอบของ $N,e,B$.