Đưa ra một EC với cardinality $C=P^3+c$ với $P$ một số nguyên tố $P \approx \sqrt[3]{C}$ và $c>0$.
Trong số một máy phát điện nhất định $G$ chúng tôi tạo ra hai máy phát điện bổ sung $F,H$ với
$$F = P \cdot G$$
$$H = P^2 \cdot G$$
(tất cả vẫn sẽ tạo ra một chuỗi độ dài $P^3+c$)
Cho bây giờ một thành viên ngẫu nhiên $M_1$ của EC đó, chúng ta có thể tạo ra một $P\times P \times P$ khối lập phương của các thành viên khác nhau với
$$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$
$$ i,j,k \in [0,P-1]$$
$$|\{V_{M_1ijk}\}| = P^3$$
Mọi thành viên ngẫu nhiên khác $M_2$ có thể được sản xuất ra khỏi $M_1$ với:
$$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$
$$ i,j,k \in [0,P]$$
Câu hỏi:
Hiện có hai thành viên ngẫu nhiên $M_1,M_2 $ có bao nhiêu bước là cần thiết để tìm các liên quan $i,j,k$ (về thời gian trung bình)? Làm thế nào mà làm việc đó?
Sẽ (nhiều) an toàn hơn nếu chúng ta chọn $P = 2\cdot p+1$ với $p$ một số nguyên tố?
Sẽ (nhiều) an toàn hơn nếu chúng ta chọn ba thừa số nguyên tố (bí mật) $P_1,P_2,P_3$ thay thế? với $P_1 \cdot P_2 \cdot P_3 \approx C$
(Tôi đang tìm kiếm các ước tính sơ bộ liên quan đến $C,P$ Trong ($O$-ký hiệu). Chúng ta có thể ví dụ bỏ qua tác động khác nhau liên quan đến độ dài bit khi nhân 2 số)
kẻ thù không biết về EC đã sử dụng, máy phát điện $G,F,H$ và nghịch đảo của họ $G^{-1},F^{-1},H^{-1}$, các thành viên ngẫu nhiên $M_1,M_2$ và cấu trúc bên trong. Anh ấy không biết về $P,d$ nhưng vì không có quá nhiều lựa chọn nên chúng tôi cho rằng anh ấy cũng biết điều này.
Anh muốn tìm ẩn số $i,j,k$ để biết ngẫu nhiên $M_1,M_2$.
Câu hỏi phụ: Có bất kỳ hạn chế nào của EC an toàn có thể được sử dụng cho việc này không? Ví dụ.
sẽ M-221 với $y^2 = x^3+117050x^2+x$ $\bmod p = 2^{221} - 3$ làm việc cho điều này?
Sự thử nghiệm:
Nếu chúng ta chỉ có một máy phát điện duy nhất $G$ nó nên mất $O(\sqrt{C})$ sử dụng baby-step-giant-step. Nếu $P$ đã được biết đến $i,j,k$ có thể được xây dựng từ điều này.
Với $F,H$ chúng ta có thể làm một bề mặt xung quanh $M_1$ và một đường thẳng với $G$ tại $M_2$ cho đến khi một giao điểm của những người. Điều này sẽ mất $O(P^2+P)\rightarrow O(P^2)$ cái nào sẽ lớn hơn $O(\sqrt{C})=O(P\sqrt{P})$. Cho nên $F,H$ không có sự giúp đỡ ở đây.
Có thể những máy phát điện $F,H$ giúp làm cho nó nhanh hơn bằng cách nào đó?