ไม่มีการลบขั้นสุดท้ายในการคูณมอนต์โกเมอรี่ระดับคำ

ฉันกำลังพยายามสร้างโมดูล RSA ใน VHDL ซึ่งจะนำไปปรับใช้กับ FPGA ฉันกำลังพยายามใช้อัลกอริทึมมอนต์โกเมอรีแบบสมบูรณ์ ซึ่งหมายความว่าฉันกำลังทำงานกับอัลกอริทึมการยกกำลังของมอนต์โกเมอรี และอัลกอริทึมการคูณมอนต์โกเมอรี การทดสอบส่วนใหญ่ของฉันประกอบด้วยการสร้างตัวเลขสุ่ม (คีย์, โมดูลัส, r, ข้อความ) ที่ฉันใช้ในการเข้ารหัส/ถอดรหัส หากข้อความต้นฉบับเท่ากับข้อความที่ถอดรหัส แสดงว่าการทดสอบผ่าน

ก่อนอื่นฉันสร้างโค้ดระดับสูงของ Montgomery Multiplication เวอร์ชันบิตใน Python ขณะที่พยายามกำจัดการลบสุดท้าย ฉันพบ นี้ โพสต์โดย Brett บน Stack Overflow เขาตั้งกระทู้ด้วย ที่นี่ เกี่ยวกับสิ่งเดียวกัน สิ่งนี้ช่วยให้ฉันได้รับอัลกอริทึมระดับบิตเพื่อทำงานใน Python โดยไม่มีการลบขั้นสุดท้าย นอกจากนี้ ดูเหมือนว่าจะทำงานใน VHDL เมื่อทำการจำลอง

ต่อไปคือการทำให้อัลกอริทึมระดับคำทำงานได้ พบการอ่านเอกสาร c03gfp โดย Ãetin Kaya Koç ที่นี่ฉันจัดการเพื่อให้โค้ด Python ระดับสูงของอัลกอริทึมระดับคำทำงานได้ แต่ไม่เป็นไปตามที่ฉันหวังไว้ เพราะฉันต้องทำการลบขั้นสุดท้ายการใช้ R เดียวกันกับที่ใช้ในรหัสระดับบิตใช้ไม่ได้กับรหัสระดับคำ จริง ๆ แล้วฉันไม่แน่ใจว่า Brett กำลังถามเกี่ยวกับสิ่งเดียวกันหรือไม่ ที่นี่แต่เขาอาจจะเป็น

ฉันได้พยายามหาเอกสารที่อธิบายว่าควรทำสิ่งนี้โดยใช้กูเกิลเป็นหลัก แต่ฉันไม่มีโชคในการค้นหาเลย ถ้าฉันพบสิ่งที่สามารถช่วยฉันกำจัดการลบขั้นสุดท้ายในอัลกอริทึมระดับคำได้ แสดงว่าฉันไม่เข้าใจเนื้อหาของเอกสารในกรณีนั้น

ฉันมีความคิดที่ว่าฉันสามารถลองเพิ่ม R ให้มากกว่าที่ทำเมื่อใช้การปรับให้เหมาะสม Walter สำหรับอัลกอริทึมระดับบิต ถือว่าฉันกำลังทำงานกับ ระดับคำ อัลกอริทึม ทำไมไม่ให้ R เป็นหนึ่งคำที่กว้างกว่าโมดูลัส

สำหรับอัลกอริทึมระดับบิตที่ฉันตั้งไว้ R = 2^(2 * NUM_BITS) ม็อด n ตามที่ มองซิเออร์ Pacalet, ที่ไหน NUM_BITS = 256 + 2 ในกรณีของฉันขณะที่ฉันทำงานกับตัวเลข 256 บิต

สำหรับอัลกอริทึมระดับคำ ในทางกลับกัน ฉันได้ลองตั้งค่า R = 2^(2 * (NUM_BITS + WORD_WIDTH)) ม็อด n. ในกรณีของฉัน NUM_BITS = 256 และ WORD_WIDTH = 32, แต่ WORD_WIDTH อาจเป็น 8, 16, 64 หรือ 128 เป็นต้น (โปรดทราบว่า WORD_WIDTH $\leq$ NUM_BITS). สิ่งนี้ใช้งานได้และใช้ได้กับการทดสอบทั้งหมดที่ฉันทำใน Python ด้วยตัวเลขสุ่ม ฉันยังไม่ได้ใช้สิ่งนี้ใน VHDL เนื่องจากฉันต้องการตรวจสอบว่าถูกต้องหรือไม่ก่อนที่จะดำเนินการ หรืออย่างน้อยก็มีพื้นฐานเพิ่มเติมสำหรับการดำเนินการนี้

ดังนั้นคำถามของฉันคือการตั้งค่าถูกต้องหรือไม่ R = 2^(2 * (NUM_BITS + WORD_WIDTH)) ม็อด n สำหรับการคูณมอนต์โกเมอรีระดับคำอย่างที่ฉันทำไปแล้ว นอกจากนี้ มีเอกสารใด ๆ ที่อธิบายเรื่องนี้หรือไม่?

แก้ไข 1

ดูเหมือนว่าหลังจากจัดรูปแบบคำถามของฉันในขณะที่ฉันกำลังค้นหาไปรอบๆ ฉันก็สะดุดเข้ากับ นี้ โพสต์ของ เซฟ. คำตอบจาก Thomas Pornin ดูเหมือนว่าจะ เกือบ ตอบคำถามของฉัน เนื่องจากคำถามของฉันโดยพื้นฐานแล้วเป็นคำถามเดียวกับที่ Saf ถาม

โทมัส พรอินทร์ เขียนว่าถ้าโมดูลัส $n$ มีขนาด NUM_BITSแล้วฉันควรจะมองหาทวีคูณถัดไปของ WORD_WIDTH.

ทำซ้ำตัวอย่าง Thomas Pornins โดยที่ WORD_WIDTH = w = 32: สำหรับโมดูลัส 1024 บิต ซึ่งเป็นผลคูณของ 32 ให้คุณใช้ $R=2^{1024}$. สำหรับโมดูลัส 1025 บิต คุณจะใช้ $R=2^{1056}$.

เรื่องนี้ดูเหมือนจะไม่เป็นกรณีสำหรับฉันเว้นแต่ฉันจะเข้าใจผิดบางอย่าง ผ่านการทดสอบของฉันกับ NUM_BITS = 256 และ WORD_WIDTH = 32 ฉันพบการตั้งค่านั้นแล้ว $R=2^{256}$ อาจ แม้ว่าล้มเหลว $n$ เป็นตัวเลขขนาด 256 บิต และแม้ว่า $n$ เป็นตัวเลข 255 บิต ในทางกลับกัน การทดสอบมักจะประสบความสำเร็จเมื่อ $R=2^{256 + 32\cdot c}$, ที่ไหน $ค$ เป็นจำนวนเต็มบวก ฉันได้ทดสอบกับ $c = [1,2,3]$ดังนั้นฉันจึงไม่สามารถรับประกันได้ว่าจำนวนบวกทั้งหมดจะใช้ได้ เราควรคำนึงถึงคุณภาพของการทดสอบของฉันด้วย และจำนวนที่ฉันทำได้ ($+1000000$).

สิ่งต่อไปนี้มาจากคำตอบของ Thomas Pornins สำหรับคำถามของ Safs: กรณีคือการคูณมอนต์โกเมอรี่เหมาะสมเฉพาะกับขนาดคำเท่านั้น กับ $w$ ขนาดเป็นคำแล้ว $R=2^{กิโลวัตต์}$ สำหรับจำนวนเต็ม k ซึ่งควรเลือกให้น้อยที่สุดเท่าที่จะทำได้ $R\ge N$.

สำหรับฉันดูเหมือนว่า $R > N$ ควรเป็นกรณี ความคิดเห็นใด ๆ เกี่ยวกับเรื่องนี้?