เป็นไปได้ไหมที่จะใช้ RSA กับจำนวนเชิงซ้อน?

RSA เป็นอัลกอริธึมการเข้ารหัสคีย์สาธารณะยอดนิยม มันมีสมมติฐานทางคณิตศาสตร์บางอย่างฉันหมายถึง เราไม่สามารถใช้ RSA กับองค์ประกอบของโครงสร้างพีชคณิตใดๆ องค์ประกอบจากโครงสร้างพีชคณิตบางอย่างมีสิทธิ์ใช้งานใน RSA เท่านั้น

ฉันต้องการทราบว่าจำนวนเชิงซ้อนอยู่ในโครงสร้างพีชคณิตเฉพาะเหล่านั้นหรือไม่ ถ้าไม่มี เนื่องจากไม่มีคุณสมบัติใด จำนวนเชิงซ้อนจึงไม่มีสิทธิ์อย่างน้อยในทางทฤษฎี?

ชุดของคอมเพล็กซ์ $\mathbb C$ ไม่เหมาะสำหรับ RSA นั่นเป็นเพราะ RSA (เช่นเดียวกับการเข้ารหัสทั้งหมด) จับคู่ข้อความธรรมดาและข้อความเข้ารหัสกับชุดที่จำกัด (เช่น $\mathbb Z_n$ หรือเป็นส่วนย่อย $\mathbb Z_n^*$), และ $\mathbb C$ เป็นอนันต์

ความพยายามใด ๆ ที่จะแสดงส่วนย่อยที่จำกัดของ $\mathbb C$ เหมาะสำหรับ RSA และ การใช้การคูณพื้นเมืองล้มเหลว ภายในมีรายละเอียดประกอบด้วย $0$ หรือไม่ความจำเป็นในการปิดเซตนี้ภายใต้การคูณทำให้เรามีเซต $\{e^{2i\pi/n}\text{ สำหรับ }i\in\mathbb N\text{ กับ }i<n\}$ เป็นเพียงความเป็นไปได้เท่านั้น ชุดนี้มีไอโซมอร์ฟิคเล็กน้อยสำหรับกลุ่ม $(\mathbb Z_n,+)$จึงไม่นำไปสู่ระบบการเข้ารหัสลับที่ปลอดภัย

^{ในทางกลับกัน เราสามารถสร้าง ความสัมพันธ์สมมูล $\ซิม$เข้ากันได้กับการคูณใน (ส่วนย่อยของ) $\mathbb C$ [นั่นคือ: สำหรับใด ๆ $a$, $a'$, $ข$, $ข'$ ใน $\mathbb C$ (หรือเซตย่อยดังกล่าว), $a\sim a'$ และ $b\ซิม b'$ หมายถึง $a\,b\sim a'\,b'$ ] ซึ่งชุดของ ชั้นเรียนที่เท่าเทียมกัน มีขอบเขตจำกัด และการคูณที่ได้นั้นอยู่ภายในกลุ่มผลหาร พิจารณาตัวอย่างเล็กน้อย $\mathbb Z_n\subset\mathbb R\subset\mathbb C$, และ $\ซิม$ กำหนดเป็นโมดูโลสมมูล $n$ สำหรับเซตย่อยนั้นของ $\mathbb C$. คำตอบนี้ ให้ตัวอย่างที่น่าสนใจมากขึ้น มีความเป็นไปได้มากขึ้นหากเรานิยามการคูณใหม่เพิ่มเติม ซึ่งรวมถึง อะนาล็อก Elliptic Curve ของ RSAซึ่งสามารถแมปใหม่ได้อย่างง่ายดาย $\mathbb C$. ฉันไม่เห็นว่าสิ่งเหล่านี้ตรงกับคำถามเดิม เนื่องจากเราเปลี่ยนทั้งชุด (ตามข้อจำกัด) และการดำเนินการ (เพื่อให้เป็นแบบภายใน)}

ที่ให้ไว้ $p,q$ ของแบบฟอร์ม $4k+3$เราสามารถกำหนด mod ของจำนวนเชิงซ้อนได้ $p$ หรือสมัย $คิว$. แบบรับประกันว่า $-1$ ไม่มีเครื่องหมายกรณฑ์ ดังนั้นเรากำลังทำงานกับส่วนขยายกำลังสองของ $GF(p)$ และ $GF(q)$, เช่น. $$GF(p^2) \simeq GF(p)[i]/(i^2+1)$$ และ $$GF(q^2) \simeq GF(q)[i]/(i^2+1).$$

เมื่อรวมเข้าด้วยกัน เราสามารถกำหนด RSA ได้ $(\mathbb{Z}/n\mathbb{Z})[i]/(i^2+1)$, $n=pq$เช่น จำนวนเชิงซ้อนที่มีการกำหนดส่วนจริงและส่วนจินตภาพ $n$. เลขคณิต (การคูณ การบวก ฯลฯ) ทำได้ในลักษณะเดียวกันกับจำนวนเชิงซ้อน เช่น. $$(a+bi)(c+di)\equiv (ac-bd) + (ad+bc)i \pmod{n}$$ (ค่าที่เก็บไว้เป็นคู่ $(ก,ข)$ และ $(ค,ง)$).

ลำดับของกลุ่มการคูณคือ $\mathrm{lcm}(p^2-1, q^2-1)$ดังนั้นเราจึงต้องการ $$e\cdot d \equiv 1 \pmod{\mathrm{lcm}(p^2-1, q^2-1)}.$$

แฟคเตอริ่งแน่นอน $n$ ทำลายแผนการ ดังนั้นจึงไม่มีการเพิ่มความปลอดภัย

อีกปัญหาที่เป็นไปได้คือจำนวนเชิงซ้อนมีบรรทัดฐาน (กำลังสอง) ซึ่งเป็นการคูณและคำนวณได้ง่ายโดยไม่รู้ตัว $p$ และ $คิว$: $$N(a+bi) \equiv a^2+b^2 \pmod{n},$$ $$N(c) \equiv N(m^e) \equiv N(m)^e \pmod{n}.$$ เนื่องจากบรรทัดฐานอาศัยอยู่ใน $GF(p)\times GF(q)$เราลดเป็น mod RSA พื้นฐาน $n$. หากผู้โจมตีสามารถทำลาย RSA mod ได้ $n$ผู้โจมตีจะกู้คืนบรรทัดฐานของข้อความ

สรุป:

เป็นไปได้ที่จะกำหนด RSA บนจำนวนเชิงซ้อนโมดูโลไพรม์ อย่างไรก็ตาม ข้อดีของการทำเช่นนี้ยังไม่ชัดเจน เนื่องจากความปลอดภัยไม่เพิ่มขึ้นเมื่อเทียบกับ RSA พื้นฐาน และประสิทธิภาพลดลงเล็กน้อย

ฉันไม่เห็นการโจมตีที่สำคัญอื่นๆ ในโครงการนี้ ฉันยินดีที่จะทราบว่ามีการโจมตีดังกล่าวหรือไม่

ปรับปรุง: แทน $\sqrt{-1}$ เราสามารถใช้อย่างอื่นได้ $\sqrt{d}$ ที่ไม่ได้อยู่ในฟิลด์ฐาน เช่น ทำงานกับ $\mathbb{Z}[\sqrt{d}]/n\mathbb{Z}$. สิ่งนี้ทำในรูปแบบของ ลายเซ็น OSS. (OSS ใช้งานไม่ได้แต่เพียงเพราะมันอ่อนแอเอง RSA ที่กำหนดมากกว่าจำนวนเต็มกำลังสองน่าจะใช้ได้)

องค์ประกอบจากโครงสร้างพีชคณิตบางอย่างมีสิทธิ์ใช้งานใน RSA เท่านั้น

ฉันไม่แน่ใจว่าคุณหมายถึงอะไร การเข้ารหัส RSA สามารถถูกมองว่าเป็น:

• ใช้บิตสตริงข้อความธรรมดา (ความยาวสูงสุดบางส่วนจะเล็กกว่าขนาดโมดูลัสเล็กน้อย)

• รันผ่านฟังก์ชันเติมเพื่อแปลง (บวกการสุ่ม) เป็นตัวเลขระหว่าง 0 ถึง N-1

• เรียกใช้การดำเนินงานสาธารณะของ RSA เพื่อแปลงเป็นตัวเลขอื่นระหว่าง 0 ถึง N-1

• แปลงตัวเลขนั้นเป็นบิตสตริงข้อความเข้ารหัส

(และการดำเนินการถอดรหัสและลายเซ็นก็คล้ายกัน)

ด้วยเหตุนี้ ค่าใดๆ ที่สามารถแสดงด้วยบิตสตริง (ขนาดขอบเขต) จึงสามารถจัดการได้โดย RSA

ตอนนี้ สิ่งนี้จะทำลายคุณสมบัติโฮโมมอร์ฟิคของ RSA (ไม่ใช่อุบัติเหตุ คุณสมบัติเหล่านี้ไม่ค่อยมีประโยชน์สำหรับผู้ใช้และอาจมีประโยชน์สำหรับผู้โจมตี ดังนั้นเราจึงต้องการแยกมันออก) ในทางกลับกัน ยังไม่ชัดเจนว่ามีประโยชน์อย่างไรกับจำนวนเชิงซ้อน

แน่นอนว่าการเข้ารหัส RSA สามารถนำไปใช้กับจำนวนเชิงซ้อนได้ เนื่องจากจำนวนเชิงซ้อนจะถูกแมปกับข้อมูลตามอำเภอใจ ซึ่งแสดงเป็นจำนวนจริงสองตัว (ขนาดและเฟสหรือจำนวนจริงและจินตภาพ) หากสามารถใช้ RSA กับจำนวนจริงได้ ก็จะขยายไปสู่จำนวนเชิงซ้อนได้อย่างง่ายดาย ในที่สุดทั้งสองจะแสดงเป็นข้อมูลที่สามารถเข้ารหัสได้