Întrebare despre lungimea/numărătorul/securitatea secvenței $x\mapsto x^\alpha \mod (N=Q\cdot R)$, cu $Q=2q_1q_2+1$ și $R=2r_1r_2+1$ și $\alpha = 2q_2r_2$

Dat un număr $N$ cu $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ cu numere prime diferite $P,Q,q_1,q_2,r_1,r_2$.

Dacă alegem acum un exponent $\alpha$ conţinând factori primi ai $Q,R$ cu $$\alpha=2 \cdot q_2 \cdot r_2$$ putem genera o secvență $S$ cu elemente $$s_{i+1} = s_i^\alpha \mod N$$ începând de la o valoare $s_0$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ cu}\textbf{ }x\in [1,N-1]$$ putem genera o secvență cu (în majoritatea cazurilor) o lungime constantă $|S|_{\max}$.

Poartă: Caut o modalitate de a minimiza $|S|_{\max}$ menținând totuși securitatea și putând genera valori aleatorii $\în S$ fără scurgeri de parametri de securitate.Menținerea securității se bazează pe păstrarea dimensiunii $|S|$ iar cu aceasta factorizarea a $N$ ascuns de un potențial adversar pentru a evita pașii mari. În plus, adversarul nu ar trebui să poată determina decalajul indicelui $i-j$ între două elemente de secvență generate aleatoriu $s_i,s_j \in S$

Rezolvarea procesului: următoarea parte poate conține ecuații incomplete/greșite. De asemenea, pot necesita ipotezele făcute mai sus.

Numărul de valori unice $x^\alpha \mod N$ este $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

Dimensiunea secvențelor:

Pentru a determina lungimea secvenței cea mai comună și cea mai mare $S_{\max}$ mai întâi trebuie să determinăm lungimea secvenței dintre factorii primi $q_1,r_1$ cu $$ g_q \equiv \alpha \mod q_1$$ $$ L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ pentru } k\in [1,q_1-1]\}|$$ $$ g_r \equiv \alpha \mod r_1$$ $$ L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ pentru } k\in [1,r_1-1]\}|$$

Lăsa $C$ fie produsul din mulțimea factorilor primi comuni dintre factorizarea lui $L_{q_1}$ și $L_{p_1}$ (deci nu există puteri primare în $C$)
Știind acest lucru, putem determina $|S|_{\max}$ (în cele mai multe cazuri) cu $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (o problemă de cunoștință: nu funcționează dacă $L_{q_1}$ este un divizor complet de $L_{r_1}$ sau vice versa)

Număr de secvențe:

În funcție de ales $s_0$ poate face parte din $1$ din $N_S$ secvențe diferite cu lungime $|S_{\max}|$ sau în unele cazuri rare, de asemenea, parte dintr-o secvență cu lungime $q_1-1$,$r_1-1$ sau $1$.
Numărul total de secvențe $N_S$ ar fi (în majoritatea cazurilor) $$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}) }$$ (ca mai sus, acest lucru nu va funcționa dacă $L_{q_1}$ este un divizor complet de $L_{r_1}$ sau vice versa)
Numărul de secvențe diferite este întotdeauna cel puțin $N_S > 2$. Scopul este de a menține acest lucru cât mai mic posibil.

Trebuie să avem grijă și de exponent $\alpha$ fiind suficient de mare pentru a evita factorizarea.

Întrebări:

Știind acest lucru, putem găsi un lucru greu de factorizat $N$ cu $\alpha$ si un mic $|S|_{\max}$. Dar cât de mic poate $|S|_{\max}$ fie pentru a menține securitatea?

Îl numim suficient de sigur dacă un adversar care a generat două elemente ale secvenței aleatorii $s_i, s_j$ nevoi în medie $2^{100}$ pași de calcul pentru a calcula decalajul indicelui dintre acestea $i$ și $j$ (presupunând $s_i,s_j$ parte a aceleiași secvențe).

Î1: Ar fi un $\aproximativ 102$-pic $|S|_{\max}$ suficient? Dacă nu, cât de mare trebuie să fie?
Î2: Are factorizarea de $|S|_{max}$ un impact asupra securității? De exemplu. mai bine alege $|S|_{max} = d\cdot p$ cu mici $d$ și prim mare $p$?
Q3: Dacă alegem $|S|_{max} = A\cdot B \cdot C$ cu $A,B,C$ cât mai prim și cât mai asemănător și, în plus, înlocuiți $\alpha$ cu $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ Elementele generate aleatoriu ar avea $3$-indici ca $s_{abc}$. Câți pași sunt necesari pentru a calcula decalajul indicelui $s_{def}$?
De exemplu. decalajul indicelui $a-d$ ar fi calculat cu $\alpha_A$.
Q3: Ar fi mai rapid decât $O(AB+C)$ (intersecția suprafeței cu linia)?

Bonus-Q: Există vreo formulă mai completă/corectă/mai ușoară pentru $|S|_{max}$ și $N_S$?

Exemplu: alegem a $2048$-pic $N = P \cdot Q$ cu factori primi $q_2 \gg q_1$ și $r_2 \gg r_1$. Cu asta $\alpha = q_2\cdot r_2$ ar putea fi $\aproximativ 1800$-bit și cele înrudite $|S|_{\max}$ ar putea fi $100/200/300$-pic

Exemplu de jucărie:

*exemplu de eroare, ecuații prezise $1560$ in schimb

Câteva întrebări și răspunsuri conexe: despre $N_\alpha$ ,$\spațiu$ despre acele secvențe