Score:2

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

ธง us

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

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

Score:3
ธง cn
jjj

ใช่ เป็นไปได้แม้ไม่มีการโต้ตอบใดๆ (ไม่มีอะไรที่ Bob ต้องส่งถึงอลิซ) วิธีการนี้เรียกว่า "ลายเซ็นแหวน"

สมมติว่าเธอต้องการเซ็นข้อความเช่น "ฉันชื่ออลิซ เพื่อเป็นหลักฐานให้บ็อบรู้ว่าฉันรู้จักกุญแจดอกหนึ่ง" เธอแฮชเพื่อให้ได้มา $m$.

ตอนนี้อลิซสร้างค่าแบบสุ่ม $r_i$ สำหรับกุญแจสาธารณะทุกอัน $k_i$ และเข้ารหัสเพื่อให้ได้มา $y_i$.

โปรดทราบว่าพวกเขาทั้งหมด $y_i$ เป็นค่าสุ่มเทียมที่คาดเดาไม่ได้ เพียง $y_i$ เธอสามารถเลือกได้ว่าเป็นกุญแจของเธอ $k_j$เธอแค่เลือก $y_j$ และลงชื่อเพื่อรับ $r_j$ ($r_j$ ดูเหมือนข้อมูลสุ่มอื่น ๆ ทั้งหมด)

ตอนนี้เธอสามารถเลือกได้ $y_j$ เพื่อให้ xor ของทั้งหมด $y_i$ เท่ากับ $m$.

เธอส่งข้อความและทั้งหมด $r_i$ ถึง Bob (หากคำสั่งไม่ชัดเจน ให้เพิ่มหมายเหตุว่า $r_i$ เป็นของคีย์ใด)

ในการยืนยัน Bob เพียงแค่เข้ารหัสทุกๆ $r_i$ ด้วยรหัสสาธารณะ $k_i$ เพื่อรับ $y_i$, xor พวกเขาทั้งหมดและตรวจสอบว่ามันเท่ากันหรือไม่ $m$.

ตั้งแต่ทั้งหมด $y_i$ ก็เหมือนกับการสุ่มตัวเลข เมื่อคุณไม่รู้คีย์ ไม่มีทางที่จะปลอมแปลงลายเซ็นโดยที่ไม่รู้คีย์ส่วนตัว นอกจากนี้ยังไม่มีวิธีที่จะบอกได้ว่า $y_i$ และ $r_i$ ไม่ได้สร้างแบบสุ่มเพราะทั้งหมดดูสุ่ม

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

jjj avatar
cn flag
jjj
@fgrieu ฉันเปลี่ยนชื่อ von $e$ เป็น $y$ ขอบคุณสำหรับสิ่งนั้น คุณสามารถเลือกโดยการ xor-ing $y_i$ และ $m$ อื่นๆ ทั้งหมดเพื่อรับ $y_j$ ไม่จำเป็นต้องลองผิดลองถูกเมื่อคุณทราบคีย์ส่วนตัวของ $k_j$ ปัญหาความยาวสามารถแก้ไขได้ง่าย ๆ โดยจำกัดจำนวนบิตเป็น xor เป็นจำนวนบิตใน m และละเว้นส่วนอื่น ๆ
fgrieu avatar
ng flag
ใช่ การปิดบังบิตลำดับสูงที่เพียงพอ (เพียงหนึ่งบิตหาก $n_i$ มีขนาดบิตเท่ากัน) ทำให้สามารถหลีกเลี่ยงการลองผิดลองถูกได้ อีกครั้ง วิธีเลือกบิตคำสั่งสูงของ $y_j$ ต้องพิจารณาอย่างรอบคอบ
fgrieu avatar
ng flag
เมื่อแฮชเป็น $h$-bit ฉัน [told](https://crypto.stackexchange.com/a/92216/555) มี [การโจมตี](https://doi.org/10.1007/ 3-540-45708-9_19) ของราคา $\mathcal O(2^{h/(1+\log_2(k))})$ ซึ่งอาจสร้างความกังวลให้กับ $k$ จำนวนมาก ในอีกมุมหนึ่ง ฉันพบว่าไม่ใช่เรื่องเล็กน้อยที่จะป้องกันไม่ให้ฝ่ายตรงข้ามได้เปรียบ (เล็กน้อย) ในการเดา $j$ โดยเฉพาะอย่างยิ่งเมื่อ $h$ เข้าใกล้ความกว้างของ $n_i$ ที่เล็กที่สุด
jjj avatar
cn flag
jjj
@fgrieu ตกลง ฉันตรวจสอบและสังเกตเห็นว่าฉันจำอัลกอริทึมไม่ถูกต้อง ฐานความคิดยังคงถูกต้อง ฉันเพิ่มบันทึกในคำตอบของฉัน ขอบคุณสำหรับการตรวจสอบ ฉันยังคงคิดว่าลายเซ็นแหวนนั้นดีสำหรับปัญหานี้จริงๆ
fgrieu avatar
ng flag
ใช่ ลายเซ็นแหวนใช้ได้กับสิ่งนี้ แต่รายละเอียดที่สำคัญขาดหายไปในบทความ Wikipedia และคำตอบ: โดเมนสำหรับ $r_i$ และ $y_i$ จะต้องทำให้มีขนาดเท่ากันแม้ว่า $n_i$ จะต่างกันก็ตาม เพื่อป้องกันการรั่วไหลของข้อมูลเกี่ยวกับ $j $. หัวข้อนี้ระบุไว้ในส่วน [การขยายการเรียงสับเปลี่ยนของประตูกับดักเป็นโดเมนทั่วไป](https://link.springer.com/content/pdf/10.1007/3-540-45682-1_32.pdf#page=6)ของ กระดาษ Rivest-Shamir-Tauman
us flag
@jjj นี่คือสิ่งที่ฉันกำลังมองหา ขอบคุณทุกคน!
Score:2
ธง ng

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

  • บ๊อบสุ่มจับฉลาก $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และทำให้อลิซแสดงให้บ็อบแสดงความสามารถของเธอในการเซ็นข้อความท้าทาย

jjj avatar
cn flag
jjj
ไม่จำเป็นต้องให้ Bob วาดอะไรเลย อลิซทำได้ เพื่อป้องกันไม่ให้อลิซเลือกแทนที่จะวาดภาพ เราสามารถใช้แฮชของข้อความที่เธอเผยแพร่ได้
fgrieu avatar
ng flag
@jjj: คำแนะนำของคุณทำให้โปรโตคอลเสี่ยงต่อการเล่นซ้ำ ดูหัวข้อย่อยที่สี่ใหม่ในเหตุผล
jjj avatar
cn flag
jjj
ไม่จำเป็น ขึ้นอยู่กับข้อความที่แฮช หนึ่งสามารถรวม nonce

โพสต์คำตอบ

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