ใน RSA gcd(e,phi) != 1 หมายถึงอะไร เหตุใดจึงเลือก e = 2^n +1 ไม่ใช่ 2^n

เมื่อเร็ว ๆ นี้ฉันมีประสบการณ์เล็กน้อยกับคำถามใน RSA ซึ่ง e คือ 2^n แทนที่จะเป็น 2^n+1 และนั่นนำไปสู่ ​​gcd(e, phi) ไม่เท่ากับ 1... สิ่งนี้จะทำให้รหัสส่วนตัวเป็นไปไม่ได้ ที่จะได้รับ? Rabin cryptosystem เป็นทางออกเดียวหรือไม่?

ใน RSA ทำอะไร $\gcd(e,\operatorname{phi})\ne1$ วิธี?

การเข้ารหัส RSA $m\mapsto m^e\bmod n$ เป็นการเข้ารหัสย้อนกลับของ $[0,น)$ ถ้าและถ้า

1. $n$ เป็นผลคูณของปัจจัยเฉพาะที่แตกต่างกัน $p_i$ (ซึ่งจะพบหาก $n=p\,q$ สำหรับจำนวนเฉพาะที่แตกต่างกันขนาดใหญ่สองตัว $p$ และ $คิว$การตั้งค่าที่พบบ่อยที่สุด)
2. และเลขชี้กำลังสาธารณะ $e$ มีผกผัน $d_i$ โมดูโลแต่ละตัว $p_i-1$, นั่นคือ $\exists d_i\in\mathbb N: e\,d_i\equiv1\pmod{p_i-1}$. อย่างเท่าเทียมกัน: และมันก็ถือ $\gcd(e,p_i-1)=1$ แต่ละ $p_i$. เงื่อนไขนี้เพื่อให้แน่ใจว่า $m\mapsto\left(m^e\right)^{d_i}\equiv m\pmod{p_i}$ สำหรับทุกๆ $m\in\mathbb N$.

เมื่อ (1) ถือ $\operatorname{phi}(n)=\prod(p_i-1)$ดังนั้นเงื่อนไข $\gcd(e,\operatorname{phi}(n))$ เท่ากับ (2)

ทำไมต้องเลือกเสมอ $e=2^k+1$ ไม่ $2^k$?

เราเลือกไม่ได้เสมอไป $e$ ของแบบฟอร์ม $2^k+1$. ตัวอย่างเช่น $e=37$ ค่อนข้างบ่อย (ดู นี้). เราเลือกได้เสมอ $e$ แปลกใน RSA เพราะมิฉะนั้นเงื่อนไข $\gcd(e,p_i-1)=1$ ไม่สามารถพบได้สำหรับ $p_i>2$, เพราะ $2$ เป็นจำนวนเฉพาะคู่เท่านั้น

ถ้าใครใช้แม้แต่ $e$นั่นไม่ใช่ RSA ที่สามารถเป็น ระบบเข้ารหัสของ Rabin.