RSA rsa เรซิดิวคลาสริง

ฉันทำงานกับวิธี RSA มาหลายสัปดาห์แล้วและฉันไม่เข้าใจว่าคลาสที่เหลือนี้เกี่ยวกับอะไร

ฉันเข้าใจว่าถ้า

$ x^e \bmod n$ จะต้องมี $x<n$ เพราะความชัดเจนของผลลัพธ์

อย่างไรก็ตาม ฉันไม่เข้าใจว่ามันมีประโยชน์อะไรอีกบ้าง

เมื่อฉันมองหาความพยายามในการจัดการบนอินเทอร์เน็ต การคำนวณแบบโมดูโลนั้นง่ายมากเสมอ:

$(s^e y)^d \equiv s^{ed}x^{ed} \equiv (sx)^{ed} \bmod n$

แต่ทำไมมันถึงทำงานง่ายจัง เปล่าเลย $y=x^d \bmod n$ ?

สำหรับจำนวนเต็มคงที่ $n\ge2$เราสามารถกำหนด ความสัมพันธ์สมมูล ใน แหวน $(\mathbb Z,+,\cdot)$. ความสัมพันธ์นั้นเรียกว่า "คอนกรูเอนซ์โมดูโล $n$", "โมดูโลความเท่าเทียมกัน $n$" หรือ "โมดูโลสมมูล $n$".มีข้อสังเกต $u\equiv v\pmod n$ เมื่อเป็นจำนวนเต็ม $u$ และ $v$ มีความหมายว่า สัมพันธ์

• $u$ และ $v$ เป็นเช่นนั้น $v-u$ เป็นผลคูณของ $n$
• นั่นคือมีจำนวนเต็มอยู่ $k$ ดังนั้น $v-u=k\,n$.

และความสัมพันธ์สมมูลดังกล่าวใช้ในการสร้าง วงแหวนคลาสสารตกค้าง $\mathbb Z/nZ$ซึ่ง (ใน crypto) มักจะถูกบันทึกไว้ $(\mathbb Z_n,+,\cdot)$ หรือเพียงแค่ $\mathbb Z_n$.

$v\bmod n$โดยไม่ต้องใส่วงเล็บทางด้านซ้ายของ$\bmod$ ก็ไม่เช่นกัน $\equiv$ เครื่องหมายที่ระดับเดียวกันของนิพจน์ สามารถกำหนดให้เป็นสมาชิกที่เล็กที่สุดของชุดจำนวนเต็มอนันต์ที่ไม่เป็นลบ $u$ กับ $u\equiv v\pmod n$. มันถือ $u=v\bmod n$, ที่ไหน$\bmod$ เป็นผู้ดำเนินการ

สัญกรณ์ $y=x^e\bmod n$ หมายถึง $0\le y<n$, แต่ $y\equiv x^e\pmod n$ ไม่. ดังนั้น $y=x^e\bmod n$ กำหนดจำนวนเต็มที่ไม่ซ้ำกัน $y$ เป็นหน้าที่ของ $x$, $e$ และ $n$, เมื่อไร $y\equiv x^e\pmod n$ ไม่.

เอาต์พุตของฟังก์ชันการเข้ารหัส RSA (ตำรา/ดิบ) $x\mapsto y=x^e\bmod n$ (กับ $x$ จำนวนเต็มและ $0\le x<n$ซึ่งฉันถือว่าทั้งหมดต่อไปนี้) เป็นจำนวนเต็มที่กำหนดไม่ซ้ำกัน $y$, ขนาดสูงสุดที่ $n$. โดยเฉพาะอย่างยิ่ง (สำหรับ $n>2$ และ $e>1$) ฟังก์ชันนั้นไม่สามารถส่งคืนได้ $y=x^e$ สำหรับทุกอย่าง $x$, ที่ $y\equiv x^e\pmod n$ อนุญาต

ความแตกต่างมีความสำคัญเนื่องจาก $x\mapsto y=x^e$ เป็นฟังก์ชันที่ง่ายต่อการกลับด้าน (โดยการแตกไฟล์ $n^\text{th}$ รากในจำนวนเต็ม); แต่ด้วย $n$ และ $e$ เลือกอย่างถูกต้องสำหรับ RSA ซึ่งเป็นฟังก์ชัน (กลับด้านทางคณิตศาสตร์) $x\mapsto y=x^e\bmod n$ ถูกคาดเดาว่ายากที่จะกลับด้านการคำนวณ $n$, $e$และสุ่ม $y$ หรือ $y$ สำหรับการสุ่มที่ไม่รู้จัก $x$เว้นแต่จะได้การแยกตัวประกอบของ $n$ หรือข้อมูลที่เทียบเท่าเช่น $d$.

การคำนวณแบบโมดูโลนั้นง่ายมากเสมอ: $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d}\equiv(s\,x)^{e\,d}\pmod n$

^{หมายเหตุ: สมการที่แก้ไขชี้แจงว่าที่นี่$\bmod$ ไม่ใช่ตัวดำเนินการ แต่เป็นตัวกำหนดความสัมพันธ์สมมูล $\equiv$}

นี่คือข้อเท็จจริงที่ถือไว้สำหรับ $(n,e,d)$ เช่นเดียวกับใน RSA และจำนวนเต็มทั้งหมด $x$, $y$, $s$ กับ $y\equiv x^e\pmod n$. ไม่อนุญาตให้แยกตัวประกอบ $n$หรือคำนวณจาก $(น,อี)$ ก $d$ การทำ $y\mapsto x=x^d\bmod n$ ฟังก์ชันผกผันของ $x\mapsto y=x^e\bmod n$หรือสลับฟังก์ชันนั้นเพื่อสุ่ม $y$ หรือ $y$ สำหรับการสุ่มที่ไม่รู้จัก $x$.

ข้อเท็จจริงดังกล่าวจะอนุญาตให้มีการปรับเปลี่ยนบางอย่าง ถ้า ฟังก์ชั่น RSA ตำราเรียน $x\mapsto y=x^e\bmod n$ ถูกใช้โดยตรงในการเข้ารหัส $x$หรือถ้าเป็นฟังก์ชันผกผัน $y\mapsto x=y^d\bmod n$ ถูกใช้โดยตรงเพื่อลงนาม $y$. แนวทางปฏิบัติทั่วไปป้องกันการจัดการดังกล่าวโดยการเลือก $x$ หรือ $y$ ใกล้พอที่จะสุ่มได้แล้ว