รหัสสาธารณะ RSA ที่ไม่มีความรู้

สมมติว่าบ๊อบมี $k>1$ กุญแจสาธารณะ RSA $(e_i, n_i)$ โดยไม่มีความรู้เกี่ยวกับคีย์ส่วนตัวที่เกี่ยวข้อง อลิซยังมีกุญแจสาธารณะทั้งหมด แต่ก็มีกุญแจส่วนตัวสำหรับกุญแจเพียงดอกเดียว พูด $(d_j, n_j)$. เป็นไปได้ไหมที่เธอจะพิสูจน์ให้ Bob เห็นว่าเธอมีคีย์ส่วนตัวอย่างน้อยหนึ่งคีย์โดยไม่เปิดเผย $เจ$

แก้ไข: เปลี่ยนสัญกรณ์ตามคำแนะนำของ fgrieu

นี่คือข้อเสนอ (จากหัวของฉัน) ภาพใหญ่

• บ๊อบสุ่มจับฉลาก $X$และส่งการเข้ารหัสตามที่กำหนดภายใต้คีย์สาธารณะแต่ละรายการ
• อลิซถอดรหัส $X$ ด้วยกุญแจสาธารณะที่เธอถืออยู่
• อลิซตรวจสอบว่าบ็อบทำตามที่คาดไว้ $X$
• อลิซเผย $X$ ถึงบ๊อบ

อย่างแม่นยำมากขึ้น:

• กำหนด ก $8b$แฮชบิต (พูด SHA-512) เช่นนั้น $\min(n_i)>2^{16b}$
• กำหนดฟังก์ชันการสร้างหน้ากาก (เช่น เอ็มจีเอฟ1 ด้วยแฮชนั้น) ดังนั้นสำหรับการทดสอบไบต์ $X$, $\operatorname{MGF}(X,\ell)$ เป็น $\ell$แฮช -byte ของ $X$
• กำหนดความยาวของไบต์ $\ell_i=\left\floor\log_2(n_i)/8\right\rfloor$ซึ่งได้แก่ $2^{8\ell_i}<n_i<2^{8\ell_i+8}$ (เพื่อหลีกเลี่ยงการโจมตีแบบจับเวลา เป็นที่พึงปรารถนาว่า $n_i$ มีขนาดบิตเท่ากัน จึงทำให้ $l_i$ เท่ากับ)
• บ๊อบสุ่มจับฉลาก $X\in\{0,1\}^{8b}$ (ก $ข$-byte ไบต์ทดสอบ)
• แต่ละ $i$, บ๊อบ
  • คำนวณ $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$
  • คำนวณ $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (หนึ่ง $l_i$-byte ไบต์ทดสอบ)
  • คำนวณและส่งออก $C_i={X_i}^{e_i}\bmod n_i$
• อลิซได้รับ $C_i$, รวมทั้ง $C_j$
• อลิซคำนวณ $f={C_j}^{d_j}\bmod n_j$
• อลิซแสดงออก $f$ เป็นการทดสอบไบต์ $M\mathbin\|G$ กับ $M$ ของ $l_i-b$ ไบต์และ $G$ ของ $ข$ ไบต์
• อลิซฟื้น $X$ โดยการคำนวณ $X=G\oplus H(M\mathbin\|J)$
• แต่ละ $i$อลิซ
  • คำนวณ $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$, ที่ไหน $I$ เป็นดัชนี $i$ เป็น bytesting
  • คำนวณ $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (หนึ่ง $l_i$-byte ไบต์ทดสอบ)
  • ตรวจสอบ ${X_i}^{e_i}\bmod n_i=C_i$ (เมื่อไร $i=j$การตรวจสอบนี้ $M=\operatorname{MGF}\bigl(X\mathbin\|H(n_j),l_j-b\bigr)$ เป็นผลข้างเคียง)
• เฉพาะในกรณีที่การตรวจสอบทั้งหมดผ่านและไม่มีการเปิดเผย (เช่น ตามเวลา) ว่ามีข้อผิดพลาดเกิดขึ้นที่ใด หรือที่ใด $X_i$ ถูกนำมาใช้ในการกู้คืน $X$
  • อลิซเผย $X$
• บ๊อบเช็คอลิซเผยสิทธิ์ $X$

เหตุผล:

• อลิซพิสูจน์ว่าเธอสามารถถอดรหัสหนึ่งในรหัสลับได้ $C_i$ดังนั้นเธอจึงถือกุญแจส่วนตัว
• เธอไม่เปิดเผยว่าอันไหน เนื่องจากเธอตรวจสอบแล้วว่ารหัสลับทั้งหมดตรงกัน $X$. ไม่มีความเสี่ยงที่จะเกิดอคติในบิตที่มีลำดับสูงในบางปริมาณ $[0,n_j)$ ทำให้ได้เปรียบในการคาดเดา $เจ$ (อาจเป็นกรณีในการใช้งานที่ไร้เดียงสาของ คำตอบอื่น ๆ).
• ตัวแทน $X_i$ ของ $X$ กำลังแพร่กระจายไป $[0,n_i)$ เช่นเดียวกับใน RSASSA-สศปพร้อมฟังก์ชั่นการเติมอิสระ ขอให้สังเกตว่าการเข้ารหัสโดยตรง $X_i=X$, หรือ $X_i=F(X)$ สำหรับการฉีดแบบคงที่ $F$จะปล่อยให้ระบบเสี่ยงต่อ การโจมตีออกอากาศของ HÃ¥stad; นอกจากนี้ อาจเป็นไปไม่ได้ที่จะกำหนดความกว้างทั่วไปที่ปลอดภัยสำหรับ $X_i$, เช่น. ถ้า $n_0$ เป็น 2048 บิต $n_1$ 8192 บิต $e_1=3$; ช่องว่างภายในแก้ปัญหานั้น
• เนื่องจาก $X$ เป็นความท้าทายที่ Bob วาดขึ้น โปรโตคอลไม่สามารถเล่นซ้ำได้: Alice ไม่สามารถหนีจากข้อมูลที่เธอคำนวณล่วงหน้าก่อนที่จะสูญเสียการเข้าถึงคีย์ส่วนตัวของเธอ หรือข้อมูลที่ Amanda คำนวณไว้ก่อนหน้านี้ซึ่งถือคีย์ส่วนตัวเช่นกัน

การปรับปรุงที่เป็นไปได้เพื่อป้องกันอลิซจากการกลายเป็นออราเคิลถอดรหัส Bob จากการปรับแต่ง $X$และอาจทำให้การพิสูจน์ง่ายขึ้น:

• อลิซวาดก่อน $ข$-ไบต์ $Y$ และส่งคำมั่นสัญญา $H(Y\mathbin\|S_0)$
• บ๊อบวาดมัน $ข$-ไบต์ $X$ และส่งคำมั่นสัญญา $H(X\mathbin\|S_1)$
• อลิซเผย $Y$บ๊อบตรวจสอบกับ $H(Y\mathbin\|0)$
• โปรโตคอลข้างต้นได้รับการแก้ไข
  • มันใช้ $M_i=\operatorname{MGF}\bigl(X\mathbin\|Y\mathbin\|H(n_i),l_i-b\bigr)$
  • มันใช้ $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|Y\mathbin\|H(n_i)))$
  • อลิซตรวจสอบเพิ่มเติม $H(X\mathbin\|1)$ การแข่งขัน
  • อลิซเผย $H(X\mathbin\|S_2)$ ค่อนข้างมากกว่า $X$
  • บ๊อบตรวจสอบว่า (ที่ไหน $S_i$ เป็น bytestings สั้นๆ ที่ไม่ว่างเปล่าโดยพลการที่แตกต่างกัน)

อัปเดต: วิธีอื่นที่ระบุไว้ใน คำตอบอื่นนี้, คือการใช้ ลายเซ็นแหวนตาม RSAและทำให้อลิซแสดงให้บ็อบแสดงความสามารถของเธอในการเซ็นข้อความท้าทาย