บน Elliptic Curve เป็นไปได้ไหมว่าจาก $P$ เราสามารถบอกได้ว่า $a$ เป็นโมดูโลกากกำลังสอง $N$ หรือไม่

ลองนึกภาพว่า ในรูปแบบการเข้ารหัสแบบ Elliptic Curve โดยที่ $P=a\คูณ G$Bob แบ่งปันรหัสสาธารณะของเขา $พี$ กับอีฟ (ปีศาจที่ต้องการรู้ความลับที่เขาไม่ควรรู้) บ๊อบยังได้เปิดเผยเงื่อนงำเกี่ยวกับ $a$ บังเอิญ. เบาะแสสามารถเป็นรายการเดียวหรือหลายรายการจากรายการต่อไปนี้:

1. จำนวน $a$ เป็นจำนวนเต็มคี่/คู่
2. จำนวน $a$ มีขนาดใหญ่/เล็กกว่าครึ่งหนึ่งของคำสั่งซื้อกลุ่ม $N/2$.
3. จำนวน $a$ มี $x$ บิตที่มีความหมายเมื่อเขียนเป็นเลขฐานสอง (ที่นั่น $x$ คือจำนวนบิตของ $a$ตัวอย่างเช่น ถ้า $a=152=10011000$ แล้ว $x=8$
4. จำนวน $a$ เป็นโมดูโล RESIDUE/NON-RESIDUE กำลังสอง $N$.

คำถามที่ 1:

ความรู้เกี่ยวกับเงื่อนงำดังกล่าวจะถือเป็นจุดอ่อนที่สำคัญสำหรับกุญแจสาธารณะของ Bob เพื่อที่เราจะบอกว่ามันไม่ปลอดภัยอีกต่อไปที่จะใช้มันหรือไม่?

คำถามที่ 2:

เงื่อนงำดังกล่าวข้างต้นเป็นข้อมูลน้อยมากเกี่ยวกับ $a$ ฉันคิดว่า ฉันถูกไหม? จะเป็นอย่างไรหากเราสามารถเปิดเผยจุดทั้งหมดบนเส้นโค้งได้โดยใช้อัลกอริทึมเวทมนตร์

ฉันรู้ว่าสำหรับรายการที่ 1-3 ความรู้เกี่ยวกับอัลกอริทึมทั่วไปสำหรับข้อใดข้อหนึ่ง $P=a\คูณ G$ สามารถบอกเราได้อย่างแน่นอนว่า $a$ เป็นคี่/คู่ หรือ $a$ มากกว่า/เล็กกว่า $N/2$ หรือ $a$ มี $x$ บิตจะทำลายการรักษาความปลอดภัยของ Elliptic Curves อย่างสมบูรณ์ และด้วยเหตุนี้จึงเป็นไปได้ที่จะเรียกคืนได้ $a$ จาก $พี$.

แต่ข้อ 4 ล่ะ? ฉันหมายความว่าถ้าใครสามารถค้นพบอัลกอริทึมที่พวกเขาสามารถกำหนดสิ่งนั้นได้ $พี$, $a$ เป็นหรือไม่เป็นโมดูโลเรซิดิวกำลังสอง $N$พวกเขาจะสามารถกู้คืนได้อย่างสมบูรณ์หรือไม่ $a$ และทำลายรูปแบบการเข้ารหัส?

จะเป็นอย่างไรถ้าอัลกอริทึมสามารถบอกรากที่สองของ $a$ โมดูโล $N$?

อัปเดต 1:

คำถามเหล่านี้เกิดขึ้นเมื่อฉันศึกษาความเสี่ยงของฐานข้อมูลคีย์ส่วนตัวที่บางส่วนถูกบุกรุก นั่นคือสิ่งที่เกิดขึ้นหากผู้โจมตีรู้เบาะแสของกุญแจส่วนตัวของเรา

ผลกระทบต่อความปลอดภัยจากข้อ 1 และ 2 ถือได้ว่าไม่มีนัยสำคัญ สมมติว่าคุณมีความปลอดภัย 256 บิต นั่นหมายถึง $2^{256}$ ปุ่มต่าง ๆ ให้เลือก หากคุณรู้ว่าคีย์เป็นเลขคี่ ค่านี้จะลดลงเหลือ $2^{255}$ คีย์ที่แตกต่างกัน สำหรับ 2 มันคล้ายกัน

การรู้ว่ามีเลขหนึ่งและเลขศูนย์กี่ตัวถือเป็นความเสี่ยงที่สำคัญ สมมติว่าคุณมีคีย์ 256 บิตที่มี 1 หนึ่งคีย์ เหลือเพียง 256 คีย์ที่เป็นไปได้ ส่งผลให้เกิดคำถามว่ามีกี่วิธีในการเรียงสับเปลี่ยน สำหรับเลขฐานสองที่มีความยาว X ที่กำหนดและตัวเลขที่กำหนดหากมี N สิ่งนี้นำไปสู่จำนวนของคีย์ ซึ่งสามารถคำนวณได้โดยใช้:

$$ number\ of\ keys=\frac{(X!)}{ (N! * (X-N)!)} $$

ในกรณีที่ดีที่สุดสิ่งนี้ส่งผลให้ $\ประมาณ 2^{252}$ คีย์ที่เป็นไปได้สำหรับ 128 อัน แต่สำหรับจำนวนที่แตกต่างกันสิ่งนี้จะยิ่งแย่ลงเท่านั้น การโจมตีด้วยจังหวะเวลามักจะพยายามค้นหาว่ามีกี่ตัวและเลขศูนย์ที่แตกต่างกัน (หรือแม้แต่พยายามค้นหาตำแหน่งบางอย่าง) การโจมตีเหล่านี้มักเป็นปัญหาร้ายแรง การโจมตีเหล่านี้บางส่วนพยายามคาดเดา 1 ของคีย์โค้งวงรี เนื่องจากอัลกอริทึมแบบเก่าบางตัวมีเวลาในการคำนวณที่แตกต่างกันขึ้นอยู่กับตำแหน่งของ 1 ที่นำหน้า สิ่งนี้จะต้องไม่เสี่ยง เช่น 1 คือบิตแรกหรือบิตที่สอง แต่ถ้าผู้นำอยู่ในตำแหน่ง $i$ ความปลอดภัยจะลดลงไปที่ $2^{256-i}$. ขึ้นอยู่กับ $i$ นี่อาจเป็นความเสี่ยงที่สำคัญ โดยเฉพาะอย่างยิ่งหากเลือกคีย์ทั้งหมดโดยการสุ่ม คุณไม่ต้องการความเสี่ยงเหล่านี้อย่างแน่นอน

สำหรับ 4 ฉันไม่แน่ใจ ฉันจะแก้ไขสิ่งนี้หากฉันพบคำตอบที่ดี