1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 30, 2022 at 18:59
  • $\begingroup$ @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? $\endgroup$
    – J. Doe
    Mar 30, 2022 at 19:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.