Score:1

Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

at flag

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$.

If we now choose an exponent $\alpha$ containing prime factors of $Q,R$ with $$\alpha=2 \cdot q_2 \cdot r_2$$ we can generate a sequence $S$ with elements $$s_{i+1} = s_i^\alpha \mod N$$ starting at a value $s_0$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ with}\textbf{ }x\in [1,N-1]$$ we can generate a sequence with (in most cases) a constant length $|S|_{\max}$.


Goal: I'm looking for a way to minimize $|S|_{\max}$ while still maintain security and being able to generate random values $\in S$ without leaking security related parameters. Maintaining security relies on keeping the size of $|S|$ and with this the factorization of $N$ hidden from a potential adversary to avoid big steps. Furthermore the adversary should not be able to determine the index gap $i-j$ in between two randomly generated sequence elements $s_i,s_j \in S$


Solving trial: the following part may contain in-complete/wrong equations. They also may require assumptions made above.

The number of unique values $x^\alpha \mod N$ is $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

Size of sequences:

To determine the most common and largest sequence length $S_{\max}$ we first need to determine the sequence length among the prime factors $q_1,r_1$ with $$ g_q \equiv \alpha \mod q_1$$ $$ L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ for } k\in [1,q_1-1]\}|$$ $$ g_r \equiv \alpha \mod r_1$$ $$ L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ for } k\in [1,r_1-1]\}|$$

Let $C$ be the product from the set of common prime factors among the factorization of $L_{q_1}$ and $L_{p_1}$ (so no prime powers in $C$)
Knowing this we can determine $|S|_{\max}$ (in most cases) with $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (one knowing problem: it does not work out if $L_{q_1}$ is a full divider of $L_{r_1}$ or vice versa)

Number of sequences:

Depending on chosen $s_0$ it can be part of $1$ out of $N_S$ different sequences with length $|S_{\max}|$ or in some rare cases also part of a sequence with length $q_1-1$,$r_1-1$ or $1$.
The total number of sequences $N_S$ would be (in most cases) $$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})}$$ (as above this won't work if $L_{q_1}$ is a full divider of $L_{r_1}$ or vice versa)
The number of different sequences is always at least $N_S > 2$. The goal is to keep this also as small as possible.

We also need to take care about the exponent $\alpha$ being large enough to avoid factorization.


Questions:

Knowing this we can find a hard-to-factorize $N$ with $\alpha$ and a small $|S|_{\max}$. But how small can $|S|_{\max}$ be to maintain security?

We call it secure enough if an adversary who generated two random sequence elements $s_i, s_j$ needs in mean $2^{100}$ steps of computation to calculate the index gap in between $i$ and $j$ (assuming $s_i,s_j$ part of the same sequence).

Q1: Would a $\approx 102$-bit $|S|_{\max}$ sufficient? If not, how much large does it need to be?
Q2: Has the factorization of $|S|_{max}$ an impact on security? E.g. better pick $|S|_{max} = d\cdot p$ with small $d$ and big prime $p$?
Q3: If we pick $|S|_{max} = A\cdot B \cdot C$ with $A,B,C$ as prime and as similar as possible and furthermore replace $\alpha$ with $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ Randomly generated elements would have $3$-indices like $s_{abc}$. How many steps needed to calculate the index gap to $s_{def}$?
E.g. index gap $a-d$ would be calculated with $\alpha_A$.
Q3: Would it be faster than $O(AB+C)$ (surface intersection with line)?

Bonus-Q: Are there some more complete/correct/easier formula for $|S|_{max}$ and $N_S$?


Example: We pick a $2048$-bit $N = P \cdot Q$ with prime factors $q_2 \gg q_1$ and $r_2 \gg r_1$. With this $\alpha = q_2\cdot r_2$ could be $\approx 1800$-bit and the related $|S|_{\max}$ could be $100/200/300$-bit


Toy example:

N primes primes primes $\alpha$ $N_\alpha$ $|S|_{\max}$ $N_S$ $L_{q_1}$ $L_{r_1}$
6302749 1787,3527 19,41 < 47,43 4042 840 360 2 18 40
65368909 7103,9203 53,43 < 67,107 14338 2376 546 4 13 42
22216573 3527,6299 41,47 < 43,67 5762 2016 920 2 40 23
12156997 1979,6143 23,37 < 43,83 7138 912 99 8 11 9
61533289 7103,8663 53,61 < 67,71 9514 3348 780* 4 52 60

*example for error, equations predicted $1560$ instead


Some related question & answers: about $N_\alpha$ ,$\space$ about those sequences

MostlyResults avatar
fr flag
Since the difficulty of factoring N is important: Did you see that N always ends up being of the form 12k+1? And that (2p1p2+1) is only prime when p1p2 = 6m+5 for p1, p2 > 3? ` N = (12u+11)(12v+11) = 12k+1 according to your definitions. ` This also points out that a back door is present to an adversary. Others can show if this small crack can lead to a full exploit. Hope this helps.
J. Doe avatar
at flag
@MostlyResults nope didn't notice that so far (beside factor 3 has some special role). Thanks for the hint. This makes finding candidates easier. But would this be a backdoor? He still need to factorize $k$ which is only slightly smaller than $N$. Is it safer if I take care about $k$ being a prime as well?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.