การโจมตีหลายเป้าหมายของคีย์สาธารณะ ECC

ฝ่ายตรงข้ามสามารถหาหนึ่งในคีย์ส่วนตัวที่ตรงกันในราคาที่ถูกกว่าการหาคีย์ส่วนตัวสำหรับคีย์ส่วนตัวได้หรือไม่?

ไม่ และนั่นสามารถพิสูจน์ได้ (และไม่ขึ้นกับเทคโนโลยีที่ใช้)

สมมติว่าเรามีกล่องดำที่สามารถเอาไปได้ $k$ กุญแจสาธารณะที่แตกต่างกัน $a_1G, a_2G, ..., a_kG$และกู้คืน $a_iG$ (สำหรับบางคน $i$) ใน $o(\sqrt{n})$ เวลา.

จากนั้น นี่คือวิธีที่เราสามารถใช้กล่องดำนั้นกับรหัสสาธารณะหนึ่งรหัส $aG$, กู้คืนคีย์ส่วนตัว $a$ ใน $o(\sqrt{n})$ เวลา. เราจะ:

• เลือก $k$ ค่าสุ่ม $r_1, r_2, ..., r_k$และคำนวณลำดับ $r_1(aG), r_2(aG), ..., r_k(aG)$ซึ่ง (โดยการกำหนด $b_i = r_i ก$) สามารถดูเป็น $b_1G, b_2G, ..., b_kG$

• ให้ลำดับ $b_1G, b_2G, ..., b_kG$ซึ่งจะฟื้นตัว $b_i$

• เราคำนวณ $a = r_i^{-1}b_i$และทำให้กู้คืนคีย์ได้

ขั้นตอนนอกเหนือจากการเรียกใช้กล่องดำใช้เวลา $O(k)$ เวลาซึ่งสามารถละเว้นได้ในขนาดที่เหมาะสม $k$.

โปรดทราบว่าลำดับ $b_1G, b_2G, ..., b_kG$ มีการกระจายอย่างสม่ำเสมอ และด้วยเหตุนี้แม้ว่ากล่องดำจะมีความน่าจะเป็น แต่ก็ยังช่วยให้เราสามารถกู้คืนรหัสสาธารณะได้