Score:1

แก้ไขปัญหาลอการิทึมแบบไม่ต่อเนื่องใน Zp โดยเลือกชุดย่อยขององค์ประกอบกลุ่ม

ธง do

อนุญาต $g$ เครื่องกำเนิดของกลุ่มวัฏจักร $Z_p$ ของการสั่งซื้อ $p-1$, ที่ไหน $g$ สามารถสร้างองค์ประกอบกลุ่มทั้งหมด $\alpha \ใน Z_p$ เช่น $\alpha = g^x$ม็อด$p$, $x \in (0..p-1)$ซึ่งปัญหาลอการิทึมแบบไม่ต่อเนื่องเป็นเรื่องยาก เช่น การคำนวณ $x=$บันทึก$_ga$.

สมมติว่าเราสร้างอินสแตนซ์ของระบบการเข้ารหัสด้วยพารามิเตอร์ข้างต้น (เช่น รูปแบบการเข้ารหัสหรือรูปแบบลายเซ็นดิจิทัล) แต่ด้วยการแก้ไขเฉพาะค่าที่พิจารณา $x$ ถูกต้องเช่นนั้น $\alpha < t$, ที่ไหน $t \in (0..p-1)$ ค่า "เป้าหมาย" โดยสังหรณ์ใจแล้ว ความปลอดภัยของระบบนี้เทียบเท่ากับระบบที่ไม่มีการดัดแปลงนั้น (เช่น แนะนำข้อกำหนดว่าสามารถใช้เฉพาะ $x$ ส่งผลให้ $a$ อยู่ต่ำกว่าเป้าหมาย) เนื่องจากผู้โจมตียังคงต้องใช้กำลังทั้งหมด $x$ ที่ไม่พอใจสิ่งนี้

อย่างไรก็ตาม คำถามของฉันคือ สิ่งนี้เปิดการโจมตีทางทฤษฎีจำนวนที่อาจเกิดขึ้นหรือไม่? ตัวอย่างเช่น อาจเร่งการทำงานของผู้โจมตีโดยใช้สูตรทางคณิตศาสตร์เพื่อแยกส่วนที่ "ไม่ถูกต้อง" $x$ และลดความปลอดภัยของระบบ crypto โดยตรงหรือไม่

kelalaka avatar
in flag
ขั้นแรก ตรวจสอบให้แน่ใจว่า $p-1$ ไม่ก่อให้เกิดการโจมตีโดย Pohlig-Hellman ประการที่สอง มองหาจิงโจ้ของ Pollard ซึ่งทำงานได้ดีมากในระยะ
do flag
ดังนั้นเพื่อให้ Pohlig-Hellman ทำงานได้ $p-1$ ต้องเป็นพลังของไพรม์ ซึ่งใช้กับพารามิเตอร์เดิมด้วย (เช่น ดูเหมือนว่าการแก้ไขของฉันจะไม่ได้รับผลกระทบจากสิ่งนี้) อัลกอริทึมจิงโจ้ดูเหมือนจะใช้ได้กับการแก้ไขของฉัน แต่ฉันก็ยังไม่แน่ใจว่าจะลดความปลอดภัยของปัญหาดั้งเดิมได้อย่างไร เมื่อพิจารณาอัลกอริทึมใน https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm แม้ว่าช่วงที่ถูกต้องของฉัน (0,...t) จะน้อยมาก (เช่น ถ้า t=1 เป็นกรณีสุดโต่ง) ดังนั้น จิงโจ้ยังคงต้องคำนวณอนุกรมของจำนวนเต็ม $d_0,... ,d_p$ ซึ่งแพงใช่ไหม
fgrieu avatar
ng flag
เป็นการยากที่จะสร้างอินสแตนซ์ของระบบเข้ารหัสที่จำกัดไว้ที่ $x$ ด้วย $g^x\bmod p=\alpha
do flag
ฉันยอมรับว่าการเข้าถึง $t$ ต้องใช้ความพยายามในการคำนวณ สมมติว่า $t$ มีขนาดใหญ่พอที่ความพยายามนี้อยู่ในขอบเขตที่สมเหตุสมผล ดังนั้น โดยสังหรณ์ใจแล้ว ความปลอดภัยของระบบที่ดัดแปลง (เช่น ต้องใช้กำลังเดรัจฉานของผู้โจมตี) จะเป็น $p-t$ เนื่องจากผู้โจมตีรู้ว่า $t$ ฉันแค่พยายามเข้าใจว่ามีการโจมตีตามทฤษฎีตัวเลขที่ลดความปลอดภัยให้ต่ำกว่า $p-t$ หรือไม่ Kangaroo ที่กล่าวมาข้างต้นดูเหมือนจะไม่ใช่ปัญหาสำหรับฉัน

โพสต์คำตอบ

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