เลขคณิตแบบแยกส่วนในการรักษาความปลอดภัยข้อมูลคืออะไร?

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

ตัวอย่างเช่น Diffie-Hellman ต้องการกลุ่มการคูณของจำนวนเต็ม modulo a prime pp มีกลุ่มที่แตกต่างกันซึ่งสามารถทำงานได้ เลขคณิตแบบโมดูลาร์หรือเลขนาฬิกาเป็นเลขคณิตบนวงกลมแทนที่จะเป็นเส้นตัวเลข modulo N โดยสามารถใช้ได้เฉพาะตัวเลขสิบสองจำนวนตั้งแต่ 0 ถึง N-1

เลขคณิตแบบแยกส่วนเป็นที่เข้าใจกันเป็นอย่างดีในวิธีการของอัลกอริธึมสำหรับการดำเนินการพื้นฐานหลายอย่าง นั่นคือเหตุผลหนึ่งว่าทำไมจึงสามารถใช้ finite field (AES) ในการเข้ารหัสคีย์สมมาตรได้ การเข้ารหัสต้องการปัญหาที่ซับซ้อน ปัญหาบางอย่างพัฒนายากด้วยการคำนวณแบบแยกส่วน

ตัวอย่างเช่น ลอการิทึมเป็นเพียงการคำนวณบนจำนวนเต็มทั้งหมด แต่จะคำนวณได้ยากเมื่อสามารถทำให้เกิดการลดลงแบบแยกส่วนได้ เช่นเดียวกับการค้นพบรากเหง้า Mod-arithmetic เป็นศัพท์ทางคณิตศาสตร์กลางในการเข้ารหัส

ทฤษฎีจำนวนสมัยใหม่ส่วนใหญ่และปัญหาเชิงปฏิบัติบางส่วนเกี่ยวข้องกับเลขคณิตแบบแยกส่วน ในโมดูโลเลขคณิต N จะเกี่ยวข้องกับเลขคณิตกับจำนวนเต็ม โดยสามารถจดจำตัวเลขทั้งหมดที่แปรผันตามค่าทวีคูณของ N นั่นคือ

x=y mod N ถ้า x =y +mN สำหรับจำนวนเต็ม m.

การรู้จำนี้แบ่งจำนวนเต็มทั้งหมดออกเป็น N คลาสเดียวกัน โดยทั่วไปสามารถระบุสิ่งเหล่านี้โดยสมาชิกที่ง่ายที่สุดคือหมายเลข 0, 1, ….N-1

ถ้า a เป็นจำนวนเต็มและ n เป็นจำนวนเต็มบวก ให้แทน mod n ให้เป็นเศษเหลือเมื่อ a หารด้วย n จากนั้น $\mathrm{a\, =\, \left \lfloor a/n\right \rfloor\, x\, n\, +\, \left ( a\, mod\, n \right );}$

ตัวอย่าง − 11 mod 7 =4

ทฤษฎีบท − n คือความสัมพันธ์สมมูลของจำนวนเต็ม คลาสสมมูลรวมถึงจำนวนเต็มเหล่านั้นที่มีเศษเหลือเท่ากันในการหารด้วย n คลาสสมมูลเรียกอีกอย่างว่าคลาสคอนกรูเอนซ์ โมดูโล n แทนที่จะบอกว่าจำนวนเต็ม a และ b มีค่าเท่ากัน และสามารถกล่าวได้ว่าเป็นโมดูโลที่สอดคล้องกัน n

เซตของจำนวนเต็มทั้งหมดที่สอดคล้องกับโมดูโล n เรียกว่าคลาสเรซิดิว [a]

โมดูโลโอเปอเรเตอร์มีคุณสมบัติดังต่อไปนี้ -

• a ≡ b mod n ถ้า n|(a - b)

• (a mod n) =(b mod n) หมายถึง a ≡ b mod n.

• a ≡ b mod n หมายถึง b ≡ a mod n.

• a ≡ b mod n และ b ≡ c mod n หมายถึง a ≡ c mod n.

คุณสมบัติของการดำเนินการเลขคณิตแบบแยกส่วน

• [(a mod n) + (b mod n)] mod n =(a + b) mod n

• [(a mod n) - (b mod n)] mod n =(a - b) mod n

• [(a mod n) x (b mod n)] mod n =(a x b) mod n

ให้ Zn ={0, 1, 2,… (n-1)} เป็นเซตของโมดูลัสตกค้าง n.