เราสามารถย้อนกลับ mul ฟังก์ชันเส้นโค้งวงรีได้หรือไม่?

ฉันมีระบบเส้นโค้งวงรีที่มีจุด P เพียงจุดเดียว สมมติว่าไคลเอนต์ A และเซิร์ฟเวอร์ B สร้างความลับ R1 และ R2

A กำลังส่ง X1 = mul(R1, P) ไปยัง B และ B กำลังส่ง X2 = mul(R2, P) ไปยัง A ความลับที่ใช้ร่วมกันจะเหมือนกันสำหรับทั้งสอง: S = X1R2 = X2R1

ระบบมีจุดเดียวและฉันมี X1, X2 และ P ฉันกำลังพยายามคำนวณความลับที่ใช้ร่วมกัน โดยการคำนวณ R1 และ R2 อย่างไรก็ตาม ฟังก์ชันเส้นโค้งย้อนกลับได้ยากเนื่องจาก n = n // 2

ฟังก์ชั่น :

#R คือหมายเลขส่วนตัวที่สร้างจากฝั่งไคลเอ็นต์/เซิร์ฟเวอร์
#พีคือประเด็น
def mul (R, P):
         
        Q = P.copy()
        Q2 = PointInf()
        ในขณะที่ R > 0:
            ถ้า R % 2 == 1:
                Q2 = เพิ่ม (Q2, Q)
            Q = เพิ่ม (Q, Q)

            ร //= 2
    
        ผลตอบแทน Q2

ในจำนวน n น้อยๆ เราสามารถย้อนกลับฟังก์ชันและหา R ได้ง่ายเพราะไม่มีการวนซ้ำจำนวนมาก ดังนั้นเราจึงทำการประมาณค่าแล้วใช้ bruteforce ได้ แต่เราจะทำอะไรกับ R ขนาดใหญ่ได้บ้าง (กรณีของฉันคือ 175 วนซ้ำ)

เป็นไปได้ทางคณิตศาสตร์หรือไม่ ?

สิ่งที่คุณกำลังอธิบายคือ Diffie-Hellman ในกลุ่มที่เป็นกลาง PointInf() [ต่อไปนี้จะสังเกต $\infty$] และกฎหมาย เพิ่ม() [ต่อไปนี้จะสังเกต $\boxplus$]. คำสั่งปัญหาไม่ได้บอกว่าข้อใด แต่ชื่อแนะนำกลุ่ม Elliptic Curve บนเขตข้อมูลจำกัด การทำงาน มัล(R, P) คำนวณการคูณสเกลาร์ $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{ เงื่อนไข}}$. จากสมาคม $\boxplus$ มันตามมา $R\boxtimes P$ มีการกำหนดไว้อย่างดีและนั่น $R_1\boxtimes (R_2\boxtimes P)=(R_1\times R_2)\boxtimes P=(R_2\times R_1)\boxtimes P=R_2\boxtimes (R_1\boxtimes P)$ [ที่ไหน $\times$ เป็นการคูณจำนวนเต็ม].

ฉันกำลังพยายามคำนวณความลับที่ใช้ร่วมกัน โดยการคำนวณ $R_1$ และ $R_2$.

$R_2\boxtimes P$ และ $R_1\boxtimes P$ เป็นที่ทราบกันดีอยู่แล้ว ดังนั้นผู้โจมตีจึงจำเป็นต้องคำนวณเท่านั้น $R_1$ หรือ $R_2$ เพื่อกู้คืนการแบ่งปัน $S$.

ในจำนวนน้อย $n$เราสามารถย้อนกลับฟังก์ชันและค้นหาได้อย่างง่ายดาย $R$ เพราะการวนซ้ำมีไม่มากนัก ดังนั้น เราสามารถทำการประมาณค่าแล้วทำการ bruteforce แต่เราจะทำอะไรให้ใหญ่ขึ้นได้ $R$ (กรณีของฉันคือ 175 การทำซ้ำ)

หากเราอยู่บนเส้นโค้งวงรีบนสนามที่มีขอบเขตจำกัด ผมไม่เห็นว่าเราจะ "ประมาณค่า" ได้อย่างไร ฉันจะถือว่าทั้งสอง $R_i$ สุ่มเข้ามา $[0,น)$ กับ $n\boxtimes P=\infty$ หรือช่วงเวลาใกล้เคียงกัน และ $\log_2(n)\ประมาณ175$.

เราสามารถย้อนกลับการคูณ Elliptic Curve ได้หรือไม่?

หา $R$ ที่ให้ไว้ $R\boxtimes P$ และ $พี$ คือปัญหาลอการิทึมไม่ต่อเนื่อง เป็นที่รู้จักกันดีที่สุด ทั่วไป วิธีการหา $S$. ที่รู้จักกันดีที่สุด ทั่วไป วิธีการแก้ปัญหา DLP (เช่น การกระจาย Pollard's rho ที่มีจุดแตกต่าง) มีค่าใช้จ่ายตามลำดับ $2\sqrtn$ การเพิ่มเติมและเกินเอื้อม (เว้นแต่ใครจะลงทุนหลายพันล้านในการออกแบบ ผลิต และใช้งานอุปกรณ์เฉพาะทางได้) อย่างไรก็ตาม

• มีอัลกอริทึมที่ดีกว่ามากสำหรับ Elliptic Curves บางตัว (เช่น supersingular หรือ when $n$ เป็นแบบประกอบ)
• อาจเป็นหนึ่งใน $R_i$ ไม่สุ่มจริงๆ
• อาจมีข้อมูลเพิ่มเติมรั่วไหล (เช่น เวลาที่ต้องใช้ในการคำนวณของ $R\boxplus P$หรือบรรทัดแคชของ CPU ที่ใช้โดยการคำนวณนั้น ทั้งสองสามารถช่วยได้)
• หรือบางทีนี่อาจเป็น CTF ที่คดเคี้ยวและปัญหาไม่ได้เรียกร้องให้ค้นหา $S$.