Câu hỏi về độ dài/số lượng/bảo mật trình tự của $x\mapsto x^\alpha \mod (N=Q\cdot R)$, với $Q=2q_1q_2+1$ và $R=2r_1r_2+1$ và $\alpha = 2q_2r_2$

Cho một số $N$ với $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ với các số nguyên tố khác nhau $P,Q,q_1,q_2,r_1,r_2$.

Nếu bây giờ chúng ta chọn một số mũ $\alpha$ chứa các thừa số nguyên tố của $Q,R$ với $$\alpha=2 \cdot q_2 \cdot r_2$$ chúng ta có thể tạo ra một chuỗi $S$ với các yếu tố $$s_{i+1} = s_i^\alpha \mod N$$ bắt đầu từ một giá trị $s_0$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ với}\textbf{ }x\in [1,N-1]$$ chúng ta có thể tạo một chuỗi có (trong hầu hết các trường hợp) độ dài không đổi $|S|_{\max}$.

Ghi bàn: Tôi đang tìm cách để giảm thiểu $|S|_{\max}$ trong khi vẫn duy trì bảo mật và có thể tạo các giá trị ngẫu nhiên $\in S$ mà không làm rò rỉ các tham số liên quan đến bảo mật.Duy trì an ninh phụ thuộc vào việc giữ kích thước của $|S|$ và với điều này, hệ số hóa của $N$ ẩn khỏi một đối thủ tiềm năng để tránh các bước lớn. Hơn nữa, đối thủ sẽ không thể xác định khoảng cách chỉ số $i-j$ ở giữa hai phần tử trình tự được tạo ngẫu nhiên $s_i,s_j \in S$

Giải quyết thử nghiệm: phần sau có thể chứa các phương trình không đầy đủ/sai. Họ cũng có thể yêu cầu các giả định được thực hiện ở trên.

Số lượng giá trị duy nhất $x^\alpha \mod N$ Là $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

Kích thước của trình tự:

Để xác định độ dài chuỗi phổ biến nhất và lớn nhất $S_{\max}$ trước tiên chúng ta cần xác định độ dài chuỗi trong số các thừa số nguyên tố $q_1,r_1$ với $$ g_q \equiv \alpha \mod q_1$$ $$ L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ cho } k\in [1,q_1-1]\}|$$ $$ g_r \equiv \alpha \mod r_1$$ $$ L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ cho } k\in [1,r_1-1]\}|$$

Để cho $C$ là tích của tập hợp các thừa số nguyên tố chung trong số các thừa số của $L_{q_1}$ và $L_{p_1}$ (vì vậy không có lũy thừa nguyên tố nào trong $C$)
Biết được điều này chúng ta có thể xác định $|S|_{\max}$ (trong hầu hết các trường hợp) với $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (một vấn đề đã biết: nó không hoạt động nếu $L_{q_1}$ là một ước số đầy đủ của $L_{r_1}$ hoặc ngược lại)

Số trình tự:

Tùy theo lựa chọn $s_0$ nó có thể là một phần của $1$ ra khỏi $N_S$ trình tự khác nhau với độ dài $|S_{\max}|$ hoặc trong một số trường hợp hiếm hoi cũng là một phần của chuỗi có độ dài $q_1-1$,$r_1-1$ hoặc $1$.
Tổng số trình tự $N_S$ sẽ là (trong hầu hết các trường hợp) $$N_S = \frac{\frac{q_1-1}{L_{q_1}}\cdot \frac{r_1-1}{L_{r_1}}}{\gcd(L_{q_1},L_{r_1}) }$$ (như trên, điều này sẽ không hoạt động nếu $L_{q_1}$ là một ước số đầy đủ của $L_{r_1}$ hoặc ngược lại)
Số các dãy khác nhau luôn ít nhất $N_S > 2$. Mục tiêu là để giữ cho điều này càng nhỏ càng tốt.

Chúng ta cũng cần quan tâm đến số mũ $\alpha$ đủ lớn để tránh phân tích thành thừa số.

câu hỏi:

Biết được điều này, chúng ta có thể tìm thấy một yếu tố khó $N$ với $\alpha$ và một nhỏ $|S|_{\max}$. Nhưng nhỏ làm sao có thể $|S|_{\max}$ được để duy trì an ninh?

Chúng tôi gọi nó là đủ an toàn nếu một đối thủ đã tạo ra hai phần tử chuỗi ngẫu nhiên $s_i, s_j$ nhu cầu trong ý nghĩa $2^{100}$ các bước tính toán để tính khoảng cách chỉ số ở giữa $i$ và $j$ (giả định $s_i,s_j$ thuộc cùng một dãy).

Q1: Sẽ một $\xấp xỉ 102$-chút $|S|_{\max}$ hợp lý? Nếu không, nó cần lớn bao nhiêu?
quý 2: Có thừa số hóa của $|S|_{max}$ ảnh hưởng đến an ninh? Ví dụ. chọn tốt hơn $|S|_{max} = d\cdot p$ với nhỏ $d$ và thủ tướng lớn $p$?
Quý 3: Nếu chúng ta chọn $|S|_{max} = A\cdot B \cdot C$ với $A,B,C$ là nguyên tố và giống nhau nhất có thể và hơn nữa thay thế $\alpha$ với $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ Các phần tử được tạo ngẫu nhiên sẽ có $3$-chỉ số như $s_{abc}$. Có bao nhiêu bước cần thiết để tính khoảng cách chỉ số để $s_{def}$?
Ví dụ. khoảng cách chỉ số $a-d$ sẽ được tính toán với $\alpha_A$.
Quý 3: Nó sẽ nhanh hơn $O(AB+C)$ (giao điểm bề mặt với dòng)?

Tiền thưởng-Q: Có một số công thức đầy đủ hơn/chính xác/dễ dàng hơn cho $|S|_{max}$ và $N_S$?

Ví dụ: Ta chọn một $2048$-chút $N = P \cdot Q$ với các yếu tố chính $q_2 \gg q_1$ và $r_2 \gg r_1$. Với cái này $\alpha = q_2\cdot r_2$ có thể là $\khoảng 1800$-bit và những thứ liên quan $|S|_{\max}$ có thể là $100/200/300$-chút

Ví dụ về đồ chơi:

* ví dụ về lỗi, phương trình dự đoán $1560$ thay thế

Một số câu hỏi & câu trả lời liên quan: xung quanh $N_\alpha$ ,$\dấu cách$ về các trình tự đó