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+1$ với $P,Q,p,q$ số nguyên tố khác nhau.
và $a$ một gốc nguyên thủy của $p$ và $q$.
Để cho $s_0 = x_0$ là dư lượng bậc hai $\mod N$ và dãy tuần hoàn $S = \{x_0^{a^i} \mod N\}$
(chúng tôi bỏ qua các cơ sở trường hợp đặc biệt như $0,1$ đây)
Câu hỏi:
Làm cách nào để các thành viên ngẫu nhiên (giả) $x_r$ cùng dãy (không cần bằng $S$) được tạo ra mà không làm rò rỉ các biến liên quan đến bảo mật (như $P,Q,p,q$) hoặc chỉ số của chúng $i$ Trong
$$x_r = s_i = x_0^{a^i} \mod N $$
hoặc đưa ra nhiều giá trị ngẫu nhiên $x_1,x_2$ khoảng cách chỉ số của họ $j$ Trong
$$x_1=x_2^{a^j}\mod N$$
Một số thông tin thêm:
như số mũ $a$ là gốc nguyên thủy của $p,q$ độ dài $L_S$ của trình tự $S$ là (trong hầu hết các trường hợp)
$$L_S = \mathrm{lcm}(p-1,q-1)$$
Số dãy như vậy $N_S$ Là
$$N_S = \mathrm{gcd}(p-1,q-1)$$
Trường hợp đặc biệt: Đối với điểm xuất phát của $0$ hoặc $1$ độ dài chu kỳ chỉ là 1.
Nếu chúng ta có $p$-thứ sức mạnh ($\mod N$) chu trình sẽ chỉ có độ dài là $1$ Trong $\mathbb Z/p\mathbb Z$.
Kết hợp với độ dài chu kỳ cho $q$ chúng tôi nhận được một chiều dài của $\mathrm{lcm}(1,q-1) = q-1$
Như nhau $q$-thứ sức mạnh $\mathrm{lcm}(p-1,1) = p-1$
Có hai trong số mỗi cái, tùy thuộc vào việc nó có phải là bội số của $P^2 \mod N$ vì $p$-th sức mạnh hoặc bội số của $Q^2$ vì $q$-th-sức mạnh.
Đối với các giá trị bắt đầu $(P^2)^q,(Q^2)^p \mod N$ chúng tôi chỉ nhận được độ dài chu kỳ là $1$ mỗi như trong $\mathbb Z/p\mathbb Z$ với $P^2 \equiv 1 \mod p$ và sức mạnh $q$ còn lại cùng một giá trị.
Với điều này, chúng ta biết tổng số dư bậc hai $N_{x^2}$ giữa $\mathbb Z/N\mathbb Z$:
$$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$
-------------
giải thử
Để giải quyết vấn đề này, chúng ta có thể chuyển một biến ngẫu nhiên từ một chuỗi ngẫu nhiên sang chuỗi mục tiêu hoặc bằng cách nào đó giới hạn các số ngẫu nhiên của chúng ta cho các phần tử của chuỗi mục tiêu.
Để chuyển từ một chuỗi $s_1$ đến bất kỳ phần tử nào của dãy khác $s_2$ chúng tôi đang tìm kiếm một số mũ $b$ với
$$x_{s_1}^b \equiv x_{s_2}^{a^i} \mod N$$
Chúng tôi đã biết về $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. Bên cạnh gốc nguyên thủy $a$ đó cũng là trường hợp của tất cả các gốc nguyên thủy khác từ $p,q$.
Nhưng theo như tôi biết thì thật khó để kiểm tra một cách ngẫu nhiên $b$.
Tuy nhiên chúng tôi biết rằng $P,Q$ không thể là một sức mạnh của một gốc nguyên thủy. Cho nên $b$ có thể là một sức mạnh của những
$$ b \equiv P^k \mod \phi(N)$$
Chúng ta chỉ cần quan tâm đến điều này $k$ Là $\not= 1$ (điều này sẽ bị rò rỉ $P$) và tất cả $N_S$ các trình tự có thể được luân chuyển qua.
Chúng ta có thể làm điều này bằng cách thiết lập $k$ đến
$$ k = 1 + N_S \cdot n $$
với $n \in \mathbb{N_+}$ (và $b \not\in \{0,P\}$) (chỉnh sửa: điều này dường như không phải lúc nào cũng xoay vòng qua tất cả chúng)
Nhưng chúng tôi vẫn không biết nếu hiện tại của chúng tôi $x_r$ nằm trong chuỗi mục tiêu. Ngoài ra, điều này có thể mất một thời gian dài nếu $N_S$ là lớn (có lẽ là trường hợp trong trường hợp sử dụng).
Bất kỳ ý tưởng để khắc phục điều đó?
Một cách khác sẽ tạo ra một giá trị dựa trên $x_0$ và ẩn chỉ mục với số mũ $c$ Thích
$$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$
và tạo ra một giá trị ngẫu nhiên $x_r$ tại trình tự này
$$x_r = x_0^{c^r} \mod N$$
với một ngẫu nhiên $r$ của sự lựa chọn. Tuy nhiên ngày càng tăng $r$ by one sẽ luôn dịch chuyển chỉ số về cùng một lượng. Nếu sự khác biệt chỉ số được biết đến cho hai ngẫu nhiên $x_{r_1}, x_{r_2}$ nó sẽ được biết cho mọi giá trị ngẫu nhiên khác được tạo ra theo cách này. Ngoài ra, đây sẽ là một tính toán đắt tiền nếu không chia sẻ $\phi(N)$
Bất kỳ ý tưởng để khắc phục điều đó?
-------
Số ví dụ:
$N=6313, P=59, Q=107, p=29, q=53$
với $N_S = 4$ chu kỳ dài $L_S = 364$
và tổng cộng $N_{x^2} = 1620 $ hình vuông
Gốc nguyên thủy từ $p$ và $q$ sẽ là $a=3$
Công suất thay đổi trình tự $b$ có thể là
$$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$
Tuy nhiên điều này $b$ chỉ quay vòng giữa hai chuỗi và không phải tất cả chúng.
Ngoài ra còn có nhiều $b$ có thể quay vòng qua tất cả các chuỗi ($2912$ ?) nhưng chưa tìm ra cách tính toán chúng. nhỏ nhất như vậy $b$ sẽ là $5$.
Hoặc ở đây một số lựa chọn thay thế:
$$b \in [5 , 10 , 11 , 15 , 17, 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51,.. ]$$
Nếu chúng ta giới hạn $b$ đến số mũ được áp dụng $N_S = 4$ lần chỉ dẫn đến cùng một biến $32$ còn lại:
$$b \in [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3104, 3497, 3550, 3740, 3935, 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$
-------
(câu hỏi này dựa trên câu trả lời cho một câu hỏi tương tự )
