การยกกำลังแบบโมดูลาร์ด้วยดัชนีสาธารณะถือเป็นการเปลี่ยนรูปแบบที่ปลอดภัยได้หรือไม่

การยกกำลังแบบโมดูลาร์ด้วยดัชนีสาธารณะถือเป็นการเปลี่ยนรูปแบบที่ปลอดภัยได้หรือไม่

ฉันจะถือว่าการเรียงสับเปลี่ยนความคิดคือ $f_{(n,e)}:\ x\mapsto x^e\bmod n$ ด้วยความแปลก $n>2$, แปลก $e>1$, และ $x$ ในชุด $\{0,1,\ldots n-2,n-1\}$ หักเซตย่อยของ $\{0,1,n-1\}$.

$f_{(n,e)}$ เป็นการเปลี่ยนแปลงเมื่อ $n$ เป็น ไร้เหลี่ยม, และ $e$ เป็นโคไพร์มด้วย $\varphi(n)$.

เมื่อไร $n$ มี $k$ (แตกต่าง) ปัจจัยสำคัญ $f$ มี $3^k$ จุดคงที่: ใด ๆ $x$ กับ $x\bmod p\in\{0,1,p-1\}$ สำหรับทุกๆ ไพรม์ $p$ การแบ่ง $n$. ซึ่งรวมถึง $0$, $1$, และ $n-1$ซึ่งเป็นเหตุผลที่เราอาจต้องการนำออก

ถ้า $2^i+3$ เป็นจำนวนเฉพาะ (นั่นคือสำหรับ $i$ ใน A057732), และ $e$ เป็นโคไพร์มด้วย $2^i+2$, แล้ว $g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$ เป็นการสับเปลี่ยนของ $[0,2^i)$ (ซึ่งจับคู่กับชุดของ $i$-bit bitstrings) โดยลบจุดตายตัวสามจุดออก เราอาจยังต้องการ $e>i$และอาจต้องการ $e$ น้ำหนักแฮมมิ่งต่ำ ตัวอย่างการก่อสร้างที่อาจเป็นประโยชน์: $(i,e)=(30,65)$, หรือ $(i,e)=(784,1025)$. ต่อมาคือการเปลี่ยนลำดับ 98 ไบต์ที่ประเมินได้เร็วพอสมควร มีการสนับสนุนฮาร์ดแวร์ที่ดีในสภาพแวดล้อมการเข้ารหัสบางอย่าง

การเรียงสับเปลี่ยนผันกลับได้ง่ายเมื่อแยกตัวประกอบของ $n$ เป็นสาธารณะ: เราทำใน RSA ที่แย่กว่านั้นคือ $\log_2(n)/\log_2(e)$ มีราคาแพงกว่าการเปลี่ยนแปลงโดยตรง

ปลอดภัยหรือไม่? ขึ้นอยู่กับการใช้งาน มันถือ $f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$ซึ่งทำให้การเปลี่ยนแปลงนั้น $f_{(n,e)}$ พิเศษมากและมีคุณสมบัติแบบอะนาล็อกสำหรับ $g_{(i,e)}$. ดังนั้นเราจึงไม่มีสิ่งทดแทนที่ดีสำหรับการเรียงสับเปลี่ยนแบบสุ่มในทุกกรณีการใช้งานของสิ่งเหล่านี้ แต่นั่นอาจทำได้เมื่อรวมกับ XOR สองสามรอบใน crypto ดั้งเดิมแบบสมมาตร