Một chuỗi tuần hoàn có thể được tạo ra với
$$s_{i+1} = s_i^a \mod N$$
với $N = P \cdot Q$ và $P = 2\cdot p+1$ và $Q = 2\cdot q\cdot r+1$ và $r = 2\cdot u \cdot v \cdot w +1$ với $P,Q,p,q,r,u,v,w$ số nguyên tố khác nhau
Bây giờ chúng ta có thể chiếu một số ngẫu nhiên $x_R$ thành một không gian con có kích thước $2(r-1)+4$ với
$$s_R = x_R^{\beta} \mod N$$
$$\beta = 2\cdot p \cdot q \cdot n \mod \phi(N)$$
với một yếu tố $n$ của sự lựa chọn.
Nếu bây giờ chúng ta sử dụng một gốc nguyên thủy $\alpha$ từ $r$ chúng ta có thể tạo ra một chuỗi tuần hoàn với:
$$s_{R_{i+1}} = s_{R_i}^\alpha \mod N $$
Trong hầu hết các trường hợp, nó sẽ có chiều dài $r-1$. Nếu $s_r =0$ hoặc $s_r =1$ hoặc là $n \equiv r \mod \phi(N)$ chúng tôi chỉ nhận được một chiều dài chu kỳ của $1$. Chúng có thể được kiểm tra và bỏ qua (trong tổng số $4$ các giá trị khác nhau).
Vì vậy, trong hầu hết các trường hợp, chúng tôi dự đoán giá trị ngẫu nhiên $x_R$ đến một thành viên của một trong hai chuỗi có độ dài $r-1$.
Hầu hết thời gian một thành viên của trình tự $S_1$ ngoại trừ nếu $X_R$ là bội số của $P \mod N$ hơn nó sẽ là một phần của trình tự $S_2$ (trừ những trường hợp đặc biệt nêu trên).
Như chúng tôi đã định nghĩa $r=2\cdot u \cdot v \cdot w +1$ với số nguyên tố $u,v,w$ chúng ta có thể sử dụng $r$gốc nguyên thủy của $\alpha$ sản xuất 3 hướng
$$\alpha_1 = \alpha^{2vw} \mod \phi(N)$$
$$\alpha_2 = \alpha^{2uw} \mod \phi(N)$$
$$\alpha_3 = \alpha^{uv} \mod \phi(N)$$
Với cái này $\alpha_1$,$\alpha_2$,$\alpha_3$ kéo dài một $u \times v \times 2w$ khoảng trống.
ba chức năng $f_1,f_2,f_3$ với $f_d: s\mapsto s^{\alpha_d} \mod N$ có thể đi qua mọi điểm của dãy ($f_0 : s\mapsto s^\alpha \mod N$).
Câu hỏi:
Đưa ra các giá trị ngẫu nhiên $x_A$ và $x_B$ và với điều này dự kiến của họ ($x^\beta$) giá trị $s_A$, $s_B$ nó sẽ khó khăn như thế nào để tìm thấy $k$ Trong $s_B \equiv s_A^{\alpha^k} \mod N$ hoặc $k_1,k_2,k_3$ Trong $s_B \equiv s_A^{\alpha_1^{k_1}\cdot \alpha_2^{k_2} \cdot \alpha_3^{k_3} } \mod N$ (giả sử chúng là một phần của cùng một chuỗi)
Hay nói cách khác là có cách nào nhanh hơn là áp dụng $f_0$ hoặc $f_1,f_2,f_3$ nhiều lần cho đến khi khớp?
(đối thủ cũng biết các chức năng nghịch đảo của $f_d$ với liên quan của họ $\bar{\alpha_d}$)
Mục tiêu là mã hóa mối quan hệ giữa các điểm 3D mà không giảm nó thành vấn đề 1D (giống như đối với $g^i \mod P_{thời gian}$)
câu hỏi phụ:
Làm thế nào lớn như vậy $r$ cần phải được an toàn?
Liệu kiến thức của $\beta$, $\alpha$ giúp đối thủ đưa ra yếu tố $N$ (giả sử chúng tôi đã chọn một yếu tố lớn $n$)?
Trong trường hợp có một cách nhanh hơn nhiều sẽ là một yếu tố $r=2u+1$ với 3 gốc nguyên thủy tốt hơn?
Giải quyết thử nghiệm:
Để được an toàn $N$ cần phải đủ lớn để tránh nhân tử hóa. Với cách tiếp cận này, chúng ta có một thang đo $N$ lớn như chúng tôi muốn trong khi vẫn duy trì kích thước chuỗi mục tiêu $r-1$.
Không có hệ số hóa, đối thủ không thể tính toán $\phi(N)$ và với điều này anh ta không thể làm những bước lớn.
Để tìm một trận đấu của $s_A$, $s_B$ anh ta có thể tính toán tất cả các thành viên của một bề mặt được tạo ra bằng $f_1,f_2$ (áp dụng cho $s_A$) và một dòng với $f_3$ (áp dụng cho $s_B$).
Nếu chúng ta định nghĩa máy tính $f_d$ như một bước tính toán (với chi phí không đổi), nó sẽ mất $O(u\cdot v +w)$ các bước để tìm một trận đấu.
Trong số sẽ ví dụ: 150-bit $r$ với một $4096$ chút $N$ hợp lý? Trừ khi có một cách nhanh hơn $\khoảng 2^{100}$ bước cần thiết để tính toán $s_A$ ra khỏi $s_B$.
Hoặc nó có thể được thực hiện nhanh hơn?
Số ví dụ (để thử nghiệm):
$N = 4151547901$, $P = 54959$, $Q=75539 = 2\cdot179 \cdot 211 +1$
$r = 211 = 2 \cdot 3 \cdot 5 \cdot 7 +1$
$\beta = 2qp = 9837482$
$\alpha = 17, \alpha_1 = 882104001, \alpha_2 = 2662481205, \alpha_3 = 3818265481$
(một số liên quan câu hỏi với một số thông tin thêm)
