การพิสูจน์ว่าฟังก์ชั่นการเข้ารหัส RSA ด้วยโมดูลัสที่ไม่เป็นสี่เหลี่ยมจัตุรัสไม่ใช่การเปลี่ยนแปลง
นี่คือ backgroung สำหรับคำถามในมือ ในขณะที่เรียน RSA ฉันได้พบกับคำถามว่าจะเกิดอะไรขึ้นถ้า$p$ และ $q$มีส่วนร่วมในการคำนวณโมดูลัสไม่ใช่ช่วงเวลาจริงหรือ? มีหัวข้อที่เกี่ยวข้องอยู่แล้ว ( ทำไม RSA จึงต้องให้ p และ q เป็นจำนวนเฉพาะ ) แม้ว่าคำตอบส่วนใหญ่จะลดลงตามการพิจารณาด้านประสิทธิภาพและความปลอดภัย แต่ก็มีคำตอบเดียวที่ระบุว่าฟังก์ชันการเข้ารหัส RSA ที่มีโมดูลัสประกอบด้วยอำนาจที่สำคัญจะสูญเสียคุณสมบัติทางชีวภาพกล่าวคือไม่ใช่การเปลี่ยนรูปอีกต่อไป อย่างไรก็ตามพฤติกรรมนี้จะแสดงเฉพาะในตัวอย่างที่ไม่มีการพิสูจน์
ระบุว่าผมได้เริ่มต้นที่จะค้นหาหลักฐานของทรัพย์สินเปลี่ยนแปลงอาร์เอสและฉันพบเช่นหลักฐานที่นี่ แต่อีกครั้งระบุว่าการพิสูจน์ใช้ได้ผลก็ต่อเมื่อ$p \ne q$ในขณะที่ยังไม่ชัดเจนว่าทำไมจึงไม่เป็นเช่นนั้น $p = q$.
จากนั้นฉันก็เริ่มขุดมันด้วยตัวเอง จริงๆแล้วดูเหมือนจะค่อนข้างชัดเจนสำหรับ$p = q$ กรณีถ้า $p$เป็นนายก แล้วสำหรับ$N = p^2$เรามีชุดข้อความธรรมดา $\{m_i\}$ ดังนั้น $0 \leq m_i < N$ และ $m_i \equiv 0\pmod{p}$และมีเลขชี้กำลัง $e > 2$ เรายังได้รับ $m_i^e \equiv 0\pmod{p^2}$.
แต่ฉันไม่แน่ใจว่าจะสรุปกรณีอย่างไร $N = p^s, s > 2$; $N=p^sq, s > 1$; $N=p^sq^r, s > 2, r > 2$. ลองมาดูกรณีที่สอง ปล่อย$N=5^23= 75$แล้ว $\phi(N) = (5^2 - 5)(3 - 1) = 40$และ $e=3$เป็นเลขชี้กำลังที่ยอมรับได้ ต่อไปถ้าฉันคำนวณทั้งหมด$c_i=m_i^3\pmod{75}$ เพื่อทุกสิ่ง $0 < m_i < 75$, ฉันเห็นว่ามี 3 ชุดของความแตกต่าง $m_i$ ค่าที่ให้เหมือนกัน $c_i$ หลังจากการเข้ารหัส:
- $c_i = 0, m_i=\{0, 15, 30, 45, 60\}$
- $c_i = 50, m_i=\{5, 20, 35, 50, 65\}$
- $c_i = 25, m_i=\{10, 25, 40, 55, 70\}$
คิดถึงสิ่งนี้ $c_i$ ค่าฉันพบรูปแบบต่อไปนี้ $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$และอื่น ๆ ระบุว่าชัดเจนว่า:
- สำหรับ $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ เราได้ $c_i = 0$
- สำหรับ $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ เราได้ $c_i = 50$
- สำหรับ $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ เราได้ $c_i = 25$
และนั่นคือสิ่งที่ฉันติดอยู่ ฉันได้ลองสำรวจตัวอย่างสำหรับ$N = p^s$ และ $N=p^sq^r$และพบรูปแบบที่คล้ายกันดังที่แสดงไว้ด้านบน แต่ฉันยังต้องการเบาะแสบางอย่างเพื่อที่จะสรุปพฤติกรรมนี้และพิสูจน์ว่าการเข้ารหัส RSA ด้วยโมดูลัสที่ไม่เป็นสี่เหลี่ยมจัตุรัสไม่ใช่การเปลี่ยนแปลง ฉันเชื่อว่าควรมีแนวคิดง่ายๆบางอย่างที่ฉันขาดหายไป แต่เนื่องจากฉันไม่ค่อยสนใจทฤษฎีจำนวนมากนักฉันจึงต้องการความช่วยเหลือจากชุมชน
เพียงเพื่อความกระจ่าง. ฉันโอเคมากกับการพิจารณาด้านประสิทธิภาพและความปลอดภัยของ$p$ และ $q$เป็นสองนายกที่ชัดเจน สิ่งเดียวที่ฉันกังวลคือคุณสมบัติ bijection ของฟังก์ชันการเข้ารหัส RSA (หรือมันไม่มีอยู่ซึ่งเป็นกรณีนี้)
ขอบคุณล่วงหน้า.
UPD
@poncho ให้คำอธิบายที่ชัดเจนเกี่ยวกับการมีอยู่ของ preimages หลายรายการสำหรับ $c = 0$. แต่ก็เป็นการดีที่จะสรุปการมีอยู่ของการเข้ารหัสอื่น ๆ ที่สามารถมีหลายภาพก่อนหน้าได้
คำตอบ
แม้ว่าคำตอบส่วนใหญ่จะลดลงตามการพิจารณาด้านประสิทธิภาพและความปลอดภัย แต่ก็มีคำตอบเดียวที่ระบุว่าฟังก์ชันการเข้ารหัส RSA ที่มีโมดูลัสประกอบด้วยอำนาจที่สำคัญจะสูญเสียคุณสมบัติทางชีวภาพกล่าวคือไม่ใช่การเปลี่ยนรูปอีกต่อไป อย่างไรก็ตามพฤติกรรมนี้จะแสดงเฉพาะในตัวอย่างที่ไม่มีการพิสูจน์
มันค่อนข้างตรงไปตรงมาที่จะแสดงให้เห็น (สมมติ) $e>1$; ด้วย$e=1$มันเป็นการเปลี่ยนแปลง แต่ไม่ใช่สิ่งที่น่าสนใจ)
ค่า $N$ เป็น nonsquarefree หากมีค่า $p>1, q$ ดังนั้น $N = p^2q$ (สังเกตว่า $q$ อาจจะมี $p$เป็นปัจจัย). ถ้าเป็นเช่นนั้นให้พิจารณาการเข้ารหัสของทั้งสองค่า$0$ และ $pq$. ในสองกรณีเรามี:
$$0^e \equiv 0 \pmod N$$
$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$
สำหรับ $x = e-2$ และ $y = e-1$. ตอนนี้ทั้งสองอย่าง$x, y \ge 0$และอื่น ๆ $p^{2+x}q^{1+y}$ เป็นผลคูณของ $p^2q$ดังนั้นสิ่งหลังนี้จึงเทียบเท่ากับ $0 \bmod N$
เนื่องจากสองข้อความธรรมดาที่แตกต่างกันนี้แมปกับ ciphertext 0 เดียวกันการแมปจึงไม่สามารถเป็น bijective ได้