Chúng ta có thể đảo ngược chức năng đường cong elip mul không?

Tôi có một hệ thống đường cong elip chỉ có một điểm P. Giả sử máy khách A và máy chủ B tạo ra R1 và R2 bí mật.

A đang gửi X1 = mul(R1, P) tới B và B đang gửi X2 = mul(R2, P) tới A sau đó chia sẻ bí mật là giống nhau cho cả hai: S = X1R2 = X2R1

Hệ thống chỉ có một điểm và tôi có X1, X2 và P. Tôi đang cố tính toán bí mật được chia sẻ bằng cách tính R1 và R2. Tuy nhiên, hàm đường cong khó đảo ngược vì n = n // 2.

Chức năng :

#R là số riêng được tạo phía máy khách/máy chủ
# P là điểm
xác định mul(R, P):
         
        Q = P.bản sao()
        Q2 = PointInf()
        trong khi R > 0:
            nếu R% 2 == 1:
                Q2 = thêm(Q2, Q)
            Q = thêm (Q, Q)

            R //= 2
    
        trở lại quý 2

Với số n nhỏ ta có thể dễ dàng đảo ngược hàm tìm R vì số lần lặp không nhiều nên có thể lấy xấp xỉ rồi bruteforce, còn R lớn thì làm được gì (trường hợp của mình là 175 lần lặp).

Điều đó có khả thi về mặt toán học không?

Những gì bạn đang mô tả là Diffie-Hellman trên một số nhóm với trung lập ĐiểmInf() [sau đây lưu ý $\infty$] và pháp luật cộng() [sau đây lưu ý $\boxplus$]. Báo cáo vấn đề không nói điều gì, nhưng tiêu đề gợi ý một nhóm Đường cong Elliptic trên một số trường hữu hạn. Chức năng mul(R, P) tính phép nhân vô hướng $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{ term}}$. Từ tính liên tưởng của $\boxplus$ nó đi theo $R\boxtimes P$ được xác định rõ ràng, và điều đó $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)$ [ở đâu $\times$ là phép nhân số nguyên].

Tôi đang cố tính toán bí mật được chia sẻ, bằng cách tính toán $R_1$ và $R_2$.

$R_2\boxtimes P$ và $R_1\boxtimes P$ đã biết, do đó kẻ tấn công chỉ cần tính toán $R_1$ hoặc $R_2$ để khôi phục chia sẻ $S$.

Trên số lượng nhỏ $n$, chúng ta có thể dễ dàng đảo ngược chức năng và tìm thấy $R$ bởi vì không có nhiều lần lặp lại, vì vậy chúng tôi có thể thực hiện một phép tính gần đúng và sau đó là bruteforce, nhưng chúng tôi có thể làm gì cho lớn $R$ (trường hợp của tôi là 175 lần lặp).

Nếu thực sự chúng ta đang ở trên một Đường cong Elliptic trên một trường hữu hạn nào đó, thì tôi không hiểu làm thế nào chúng ta có thể "xác định". Tôi sẽ giả sử cả hai $R_i$ là ngẫu nhiên trong $[0,n)$ với $n\boxtimes P=\infty$ hoặc một khoảng thời gian tương tự, và $\log_2(n)\approx175$.

Chúng ta có thể đảo ngược phép nhân Đường cong Elliptic không?

Phát hiện $R$ được cho $R\boxtimes P$ và $P$ là bài toán logarit rời rạc. Nó được biết đến nhiều nhất tổng quan phương pháp để tìm $S$. nổi tiếng nhất tổng quan các phương pháp để giải DLP (ví dụ: rho của Pollard phân tán với các điểm phân biệt) có chi phí theo thứ tự $2\sqrt n$ bổ sung và điều đó nằm ngoài tầm với (trừ khi người ta có thể đầu tư hàng tỷ đô la vào việc thiết kế, sản xuất và vận hành các thiết bị chuyên dụng). Tuy nhiên

• có nhiều thuật toán tốt hơn cho một số Đường cong Elliptic (ví dụ: siêu dị thường hoặc khi $n$ là hợp chất).
• có lẽ một trong những $R_i$ không thực sự ngẫu nhiên
• có lẽ một số rò rỉ thông tin bổ sung (như thời gian cần thiết để tính toán $R\boxplus P$hoặc các dòng bộ đệm CPU được sử dụng bởi tính toán đó; cả hai đều có thể giúp đỡ).
• hoặc có lẽ đây là một CTF quỷ quyệt và vấn đề không yêu cầu tìm kiếm $S$.