Cryptography
rsa modular-arithmetic factoring security-definition complexity
Updated Sat, 16 Jul 2022 02:33:56 GMT

# How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?

A cyclic sequence can be produced with

$$s_{i+1} = s_i^a \mod N$$ with $$N = P \cdot Q$$ and $$P = 2\cdot p+1$$ and $$Q = 2\cdot q\cdot r+1$$ and $$r = 2\cdot u \cdot v \cdot w +1$$ with $$P,Q,p,q,r,u,v,w$$ different primes

We can now project a random number $$x_R$$ into a subspace of size $$2(r-1)+4$$ with $$s_R = x_R^{\beta} \mod N$$ $$\beta = 2\cdot p \cdot q \cdot n \mod \phi(N)$$ with a factor $$n$$ of choice.

If we now use a primitive root $$\alpha$$ from $$r$$ we can produce a cyclic sequence with: $$s_{R_{i+1}} = s_{R_i}^\alpha \mod N$$ In most cases it will have a length $$r-1$$. If $$s_r =0$$ or $$s_r =1$$ or for $$n \equiv r \mod \phi(N)$$ we only get a cycle length of $$1$$. Those can be tested and ignored (in total $$4$$ different such values).

So in almost all cases we project the random value $$x_R$$ to a member of one out of two sequences with length $$r-1$$.
Most times a member of sequence $$S_1$$ except if $$X_R$$ is a multiple of $$P \mod N$$ than it will be part of sequence $$S_2$$ (except those special cases mentioned above).

As we defined $$r=2\cdot u \cdot v \cdot w +1$$ with primes $$u,v,w$$ we can use $$r$$'s primitive root $$\alpha$$ to produce 3 directions $$\alpha_1 = \alpha^{2vw} \mod \phi(N)$$ $$\alpha_2 = \alpha^{2uw} \mod \phi(N)$$ $$\alpha_3 = \alpha^{uv} \mod \phi(N)$$ with this $$\alpha_1$$,$$\alpha_2$$,$$\alpha_3$$ span a $$u \times v \times 2w$$ space.
Three function $$f_1,f_2,f_3$$ with $$f_d: s\mapsto s^{\alpha_d} \mod N$$ can traverse every point of the sequence ($$f_0 : s\mapsto s^\alpha \mod N$$).

Question:
Given random values $$x_A$$ and $$x_B$$ and with this their projected ($$x^\beta$$) values $$s_A$$, $$s_B$$ how difficult would it be to find $$k$$ in $$s_B \equiv s_A^{\alpha^k} \mod N$$ or $$k_1,k_2,k_3$$ in $$s_B \equiv s_A^{\alpha_1^{k_1}\cdot \alpha_2^{k_2} \cdot \alpha_3^{k_3} } \mod N$$ (assuming they are part of the same sequence)
Or in other words is there some faster way than applying $$f_0$$ or $$f_1,f_2,f_3$$ multiple times until match?

(the adversary does also know the inverse functions of $$f_d$$ with their related $$\bar{\alpha_d}$$)
The goal is to encrypt the relation in between 3D points without reducing it to a 1D problem (like it is for $$g^i \mod P_{rime}$$)
side questions:
How big such an $$r$$ need be to be secure?
Would the knowledge of $$\beta$$, $$\alpha$$ help the adversary to factorize $$N$$ (assuming we picked a big factor $$n$$)?
In case there is a much faster way would a factor $$r=2u+1$$ with 3 primitive root better?

Solving trial:
To be secure $$N$$ need to be large enough to avoid factorization. With this approach we an scale $$N$$ as big as we want while maintaining the target sequence size $$r-1$$.
Without factorization an adversary could not compute $$\phi(N)$$ and with this he can't do big steps.
To find a match of $$s_A$$, $$s_B$$ he can compute all members of a surface produced with $$f_1,f_2$$ (applied to $$s_A$$) and a line with $$f_3$$ (applied to $$s_B$$).
If we define computing $$f_d$$ as one computation step (with constant cost) it would take $$O(u\cdot v +w)$$ steps to find a match.
In numbers would e.g. a 150-bit $$r$$ with a $$4096$$ bit $$N$$ sufficient? Unless there is a faster way $$\approx 2^{100}$$ steps needed to compute $$s_A$$ out of $$s_B$$.
Or can it be done faster?

Example numbers (for testing):
$$N = 4151547901$$, $$P = 54959$$, $$Q=75539 = 2\cdot179 \cdot 211 +1$$
$$r = 211 = 2 \cdot 3 \cdot 5 \cdot 7 +1$$
$$\beta = 2qp = 9837482$$
$$\alpha = 17, \alpha_1 = 882104001, \alpha_2 = 2662481205, \alpha_3 = 3818265481$$

## Solution

To be secure $$N$$ need to be large enough to avoid factorization.

Then you're insecure; we have $$s_i \equiv 1 \pmod P$$ for $$i > 0$$, hence $$\gcd( s_i - 1, N ) = P$$ (unless $$s_i = 1$$)