มีคีย์สาธารณะใดที่สามารถรับคีย์ส่วนตัวได้ง่าย (ECDSA) หรือไม่

คำนำ

ด้านหนึ่งของการรักษาความปลอดภัยของ ECDSA ขึ้นอยู่กับความปลอดภัยของลอการิทึมแบบไม่ต่อเนื่องของ Elliptic Curve ที่ใช้ (เรียกว่า $E$). เส้นโค้งวงรีก่อตัวเป็นกลุ่มพีชคณิตเพิ่มเติมของคำสั่ง $n$. หากกลุ่มที่เกิดขึ้นจากเส้นโค้งที่ใช้เป็นกลุ่มทั่วไป การโจมตีแบบคลาสสิกที่ดีที่สุดคือ $\mathcal{O}(\sqrt{2^n})$ - โรของพอลลาร์ด

ECDSA

คีย์ส่วนตัว $k$ คำนวณเป็นจำนวนเต็มแบบสุ่มในช่วงเวลา $[1,n-1]$ และเก็บเป็นความลับตลอดเวลา โปรดทราบว่าคีย์ส่วนตัว $k$ เป็นจำนวนเต็ม ไม่ใช่จุดบนเส้นโค้ง $E$.

กุญแจสาธารณะ $พี$ในทางกลับกัน จะคำนวณเป็นจุด $p = [k]G$ ที่ไหน $G$ เป็นจุดฐานของเส้นโค้งที่กำหนดไว้ในมาตรฐานและการปฏิบัติงาน $[k]G$ เรียกว่าการคูณสเกลาร์ที่กำหนดเป็น;

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-ครั้ง}$$

ไม่ควรสับสนกับการคูณ ไม่ใช่ นี่คือสิ่งที่เราเขียนเพื่อลดความซับซ้อนของ $k$เพิ่มครั้ง

เดอะ $[k]P$ สามารถคำนวณได้อย่างน้อยด้วยอัลกอริทึมแบบ double-and-add เพื่อเร่งการคำนวณให้เร็วขึ้น $\mathcal{O}(\log k)$-เวลา.

คะแนน

ตอนนี้อย่างที่เราเห็นแม้แต่ $k=0$ ไม่เป็นปัญหาใน ECDSA เนื่องจากไม่ใช่ค่าที่ถูกต้องสำหรับ $k$.

ถ้าล็อกไม่ต่อเนื่องก็ง่าย

• หากบันทึกแยกนั้นง่ายในเส้นโค้งนี้ นั่นคือการค้นหา $k$ ที่ให้ไว้ $[k]G$จากนั้นทุกค่าจะได้รับมาอย่างง่ายดาย

• หากเส้นโค้งลับกับจุดฐานอื่น $H$เช่น บางคนสามารถแก้ลอการิทึมแยกเป็นฐานได้ $H$ บนกลุ่มเส้นโค้ง จากนั้นพวกเขาสามารถใช้สิ่งนี้เพื่อแก้ปัญหา Dlog บนฐาน $G$ ง่ายมาก

  • พวกเขาคำนวณ $G = [t]H$ สำหรับ $t \ใน [1,n-1]$ ครั้งเดียวเท่านั้น
  • พวกเขาแก้ปัญหา $P =[k\cdot ก]G$ ไปที่ฐาน $H$ สำหรับ $a \ใน [0,n-1]$. ครั้งหนึ่ง $ka$ จะพบ $k$ สามารถคำนวณได้เป็น $k = a \cdot k \cdot a^{-1}$ เนื่องจากเรารู้ว่า $a$ และ $a^{-1} \cdot a = 1 \bmod n$.

ถ้าบันทึกไม่ต่อเนื่องไม่สะดวก

ในกรณีนี้ เราสามารถคำนวณบางส่วนได้ถึงกำลังสูงสุด สมมติว่าคุณสามารถใช้ Supercomputer Summit และคุณมีอำนาจในการคำนวณ $2^{70}$ สองเท่าและเพิ่มสำหรับตัวเลขที่กำหนด $t$. พวกเขาคำนวณและตั้งค่าตารางแฮชเพื่อสอบถามอย่างรวดเร็วสำหรับการมีอยู่ของบันทึกแยกในช่วง $[1,2^{70}]$. การดำเนินการในหนึ่งปีและการจัดเก็บที่จำเป็นคือ $2^{70}*256*3$-บิต (~147574 เพตะไบต์) ที่เก็บข้อมูลเป็นปัญหาอย่างหนึ่งและอีกอย่างคือตารางแฮชอาจไม่ใช่ $\mathcal{O}(1)$ อีกต่อไป. สมมติว่าคุณได้แก้ไขปัญหานี้แล้ว ความน่าจะเป็นที่คุณจะพบรหัสส่วนตัวที่กำหนดจากรหัสสาธารณะคือเท่าไร ค่าที่แน่นอนขึ้นอยู่กับกลุ่มเส้นโค้ง สมมติว่ากลุ่มหนึ่งใช้กลุ่มเส้นโค้งที่มีขนาด $2^{256}$ เพื่อความปลอดภัยจากการโจมตี Dlog มาตรฐาน ความน่าจะเป็นในการตีคือ $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ สิ่งนี้ยังมีความเป็นไปได้น้อยกว่ามาก $\dfrac{1}{100}$ดังนั้นเราจึงบอกว่ามันจะไม่เกิดขึ้น!

ไม่ แทนที่จะเลือกลำดับสุ่มของ $t$เปลี่ยนผลลัพธ์ ไม่!

หมายเหตุพิเศษ1:0x0000...0000 เป็นการเข้ารหัสตามปกติของ $\mathcal{O}(n)$ เนื่องจาก $(0,0)$ ไม่อยู่บนทางโค้ง สิ่งนี้ไม่ได้รับการยอมรับว่าเป็นรหัสสาธารณะที่ถูกต้อง ก.ล.ต.1 เวอร์ชั่น 2.0 ส่วน 3.2.2.1.

หมายเหตุพิเศษ2: เส้นโค้งวงรีบางส่วนเป็นเส้นโค้งเฉพาะ ซึ่งหมายความว่ากลุ่มที่เกิดขึ้นมีลำดับเฉพาะ ในกรณีนี้ ทุกองค์ประกอบเป็นตัวสร้าง ยกเว้นองค์ประกอบเอกลักษณ์ หากลำดับไม่ใช่จำนวนเฉพาะ เช่นใน Curve25519 เราก็มีปัจจัยร่วม $h = \#E(K)/n$ ที่ไหน $n$ เป็นจำนวนเฉพาะที่ใหญ่ที่สุดหารลำดับของเส้นโค้ง หากใช้กลุ่มเต็ม จะสังเกตเห็นองค์ประกอบคำสั่งขนาดเล็กได้ง่าย เพียงตรวจสอบ $[o]P = \mathcal{O}$ หรือไม่ที่ไหน $o$ เป็นคำสั่งขนาดเล็ก สำหรับ Curve25519, the $o$ ค่าเป็น $2,4,$ และ $8$. นี่ไม่ใช่ปัญหาด้านความปลอดภัยเนื่องจาก ผู้ใช้ที่ถูกต้องมักจะเลือก $k \equiv 0 \pmod 8$.