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$).

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$

(some related question with some more information)


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$)

Comments (1)

  • +0 – oh dear, I though I finally found something working. How could I miss that. Thanks again. Do you have any idea to make something like this possible? — Mar 09, 2022 at 22:33