เคล็ดลับ Strauss-Shamir ในการคูณ EC ด้วยสเกลาร์

ฉันจะอธิบายเคล็ดลับ Shamir มาตรฐานที่ปรับให้เข้ากับบริบทของ การตรวจสอบลายเซ็น ECDSA. การลดดัชนีลง ส่วนที่แพงในการคำนวณคือการคำนวณ $$u\cdot G+v\cdot Q$$ ที่ไหน $u$ และ $v$ คือ (เราถือว่าเป็นจำนวนเต็มบวกอย่างเคร่งครัด) $G$ และ $คิว$ เป็นจุด Elliptic Curve และ $+$ เป็นการเพิ่มจุด (ซึ่งสำหรับการทำให้เข้าใจง่ายฉันถือว่าเป็นกล่องดำซึ่งการดำเนินการควบคุมค่าใช้จ่ายในการคำนวณ) จำได้ว่าโดยความหมายแล้ว $$u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{ เงื่อนไข}}$$

ทราบดี $\mathbin\|u\mathbin\|$ สำหรับจำนวนบิตที่เป็นจำนวนเต็ม $u$, นั่นคือ $\left\floor\log_2(u)+1\right\rfloor$; เหมือนกันสำหรับ $\mathbin\|v\mathbin\|$.

วิธีทั่วไปของการคำนวณ $u\cdot G$ คือการ

• ชุด $R:=G$
• สำหรับบิต $ข$ คัดลอกมาจากการแทนเลขฐานสองของ $u$, เริ่มต้นที่ดัชนี $\mathbin\|u\mathbin\|-1$ (บิตแรกทางขวาของซ้ายสุด $1$ บิต) ลงไปที่ $0$ (บิตขวาสุด)
  • ชุด $R:=R+R$
  • ถ้า $b=1$, ชุด $R:=R+G$

วิธีพื้นฐานในการคำนวณ $u\cdot G+v\cdot Q$ น่าจะเป็นการคำนวณ $u\cdot G$, แล้ว $v\cdot Q$ ด้วยวิธีการเดียวกัน แล้วนำผลลัพธ์ทั้งสองมาบวกกัน เคล็ดลับของ Shamir ดีขึ้น:

• ชุด $H:=G+Q$
• ถ้า $\mathbin\|u\mathbin\|>\mathbin\|v\mathbin\|$, ชุด $R:=G$;
• อย่างอื่นถ้า $\mathbin\|u\mathbin\|<\mathbin\|v\mathbin\|$, ชุด $R:=คิว$;
• อื่น (นั่นคือถ้า $\mathbin\|u\mathbin\|=\mathbin\|v\mathbin\|$ ), ชุด $R:=H$;
• สำหรับบิต $ข$ (ตอบกลับ $ค$) คัดลอกมาจากการแสดงเลขฐานสองของ $u$ (ตอบกลับ $v$) โดยมีตัวแทนของ $u$ หรือ $v$ เบาะซ้ายด้วยศูนย์เท่าที่จำเป็น ที่ดัชนีจาก $\max(\mathbin\|u\mathbin\|,\mathbin\|v\mathbin\|)-1$ ลงไป $0$
  • ชุด $R:=R+R$
  • ถ้า $b=1$ และ $ค=0$, ชุด $R:=R+G$
  • (อื่น ๆ ) ถ้า $b=0$ และ $ค=1$, ชุด $R:=R+Q$
  • (อื่น ๆ ) ถ้า $b=1$ และ $ค=1$, ชุด $R:=R+H$

ข้อความนี้เกือบจะเทียบเท่ากับข้อความที่ระบุใน คำตอบนี้ ภายใต้ชื่อ Strauss-Shamir trick (พอรู้ว่าเป็นกลลวงของชามีร์) ตัวแปรที่ฉันให้หลีกเลี่ยงความจำเป็นในการรู้จักกลุ่มที่เป็นกลาง แต่ต้องการ $\max(u,v)>0$.

ความถูกต้องของการคูณจุดมาตรฐานและเคล็ดลับของ Shamir สามารถพิสูจน์ได้อย่างเป็นทางการโดยการอุปนัย

สำหรับการสุ่มขนาดใหญ่ $u$ และ $v$ ของ $k$ บิต อัลกอริทึมไร้เดียงสาในการคำนวณ $u\cdot G+v\cdot Q$ ดำเนินการโดยเฉลี่ย $\ประมาณ3k$ การเพิ่มจุดเคล็ดลับของ Shamir ช่วยลดสิ่งนั้นลง $\ประมาณ1.75k$เช่น น้อยกว่า 42% (ผลประโยชน์ด้านต้นทุนต่ำกว่า ส่วนใหญ่เป็นเพราะจุดสองเท่า $R:=R+R$ เป็นการเพิ่มจุดที่เร็วที่สุดและจุดที่ลดลงมากที่สุด) มีการปรับปรุงเพิ่มเติมที่เป็นไปได้ เช่น จัดกลุ่มบิตทีละสองหรือมากกว่านั้น อาจมี "หน้าต่างเลื่อน" เมื่อ $b=0=c$.

โปรดสังเกตว่าในบริบทของการตรวจสอบลายเซ็น $u$, $v$, $G$ และ $คิว$ ทั้งหมดเป็นแบบสาธารณะ ดังนั้นแชนเนลด้านข้าง (การจับเวลา การดึงพลังงาน การปล่อย แคชâ¦) จึงไม่ใช่ปัญหาด้านความปลอดภัย เนื่องจากอยู่ในการสร้างลายเซ็น

ฉันไม่รู้เคล็ดลับของสเตราส์-ชามีร์ในคำถาม ข้อมูลอ้างอิงอื่น ๆแต่สงสัยอย่างคลุมเครือว่ามันปรับปรุงสิ่งนี้เพิ่มเติมโดยบางครั้งทำการลบแทนการบวก และ/หรือเข้ากันได้กับเทคนิคการเพิ่มความเร็วสำหรับการบวกจุด