บรรจวบ เข้าสู่ระบบ
Score:3
LeonMSH avatar Crypto

อัลกอริทึมที่ดีกว่าสำหรับการยกกำลังแบบโมดูลาร์บน secp256k1/r1

ธง us
LeonMSH

ฉันรู้จักการยกกำลังแบบโมดูลาร์ ($r = b^e \bmod m$) มีความสำคัญสำหรับ RSA และฉันสามารถหาอัลกอริธึมบางอย่างที่หาก e แสดงในรูปแบบไบนารี (สำหรับ exp: )-ในลักษณะนี้สำหรับ e ยาว n บิต เราคาดหวังได้ ~1.5n รอบคูณการดำเนินการแบบโมดูลาร์

ฉันกำลังสร้างวิธีการกู้คืนคีย์สาธารณะสำหรับ ECC เช่น secp256k1/r1 มีการใช้งานที่มีประสิทธิภาพมากใน secp256k1 lib แต่ถูกเข้ารหัสในรหัส ASM ซึ่งเข้าใจยาก แต่อย่างน้อยฉันก็รู้ขั้นตอนที่ 1 - คุณต้องกู้คืน $ry$ จาก $rx$ (เช่น r ของลายเซ็น) มันง่ายมากที่จะได้รับ $ry^2$ จาก $rx$แต่ต่อไปฉันจะต้องทำสแควร์รูทแบบโมดูลาร์ ซึ่งสามารถแปลงเป็นโมดูลการยกกำลังบนฟิลด์ นั่นคือ $e= (p+1)/4.$

ตกลง ตอนนี้คำถามคือ:

  1. มีอัลกอริทึมที่ดีกว่านอกเหนือจากการยกกำลังแบบโมดูลาร์ตามปกติหรือไม่ เพื่อคำนวณ ($r = b^e \bmod m$)?
  2. หรืออีกทางหนึ่ง มีอัลกอริทึมทางลัดสำหรับ secp256k1 โดยเฉพาะหรือไม่ที่ฉันไม่จำเป็นต้องเรียกใช้การยกกำลังแบบโมดูลาร์เลย และยังสามารถกู้คืน $ry$ จาก $rx$?
101
0 + 0
Score:2
fgrieu avatar Crypto
ธง ng
fgrieu

ไม่มีการแทนที่การคูณแบบโมดูลาร์ในระบบเข้ารหัสลับของคำถาม บางภาษาเช่น Python ทำให้ง่ายสำหรับการศึกษา เท่านั้น.

ใน RSA และ DSA และการเข้ารหัสลับ ECC ในระดับที่น้อยกว่า secp256k1 หรือ secp256r1หนึ่งต้องคำนวณ $b^e\bmod m$ สำหรับขนาดใหญ่ $e$. อัลกอริทึมที่เร็วที่สุด (เช่น การยกกำลังหน้าต่างบานเลื่อน) ดำเนินการเกี่ยวกับ $\log_2 อี$ โมดูลาร์กำลังสองและอื่น ๆ $\ประมาณ0.2\,\log_2 e$ การคูณแบบแยกส่วน อย่างไรก็ตาม มีอัลกอริทึมอื่นๆ ที่มีราคาแพงกว่าเล็กน้อยเท่านั้น (เช่น บันไดของมอนต์โกเมอรี่) ที่อาจดีกว่าจากมุมมองของการรักษาความปลอดภัยจากช่องด้านข้าง

แต่ละโมดูลาร์คูณหรือกำลังสองโมดูโล $m$สำหรับการบวกหรือคูณจุดด้านบนหรือ (ใน ECC) ด้วยสเกลาร์ มีค่าใช้จ่ายด้านการคำนวณเพิ่มขึ้นมากที่สุดเช่น $(\log ม)^2$ เมื่อใช้อัลกอริทึมที่เรียนในโรงเรียนประถมที่ปรับให้เข้ากับคำในคอมพิวเตอร์แทนตัวเลข ที่สามารถลดลงได้ถึง $(\log m)^{\ประมาณ1.6}$ กับ คาราสึบะ หรือ $(\log ม.)^{\ประมาณ1.5}$ กับ ทูม-3แต่ใน ECC โมดูลัส $m$ ไม่ใหญ่พอที่จะจ่ายมาก ($m$ เป็น 'เพียง' หลายร้อยบิตใน ECC แทนที่จะเป็นหลายพันใน RSA/DSA)

เมื่อพัฒนาลายเซ็นหรือการเข้ารหัสโดยใช้ secp256k1 หรือ secp256r1 ตั้งแต่เริ่มต้นเพื่อวัตถุประสงค์ทางการศึกษา โดยทั่วไปจะมีขั้นตอนต่างๆ ดังนี้

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

การอ้างอิงออนไลน์บางส่วนเกี่ยวกับการคูณและการยกกำลังแบบโมดูลาร์ (ไม่ใช่ ECC):

0 + 0
ธงชาติไทย
Kulap
คำถามนี้เป็นภาษาอื่นๆ:

โพสต์คำตอบ

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