# Unique numbers with $P^aQ^bR^c \mod N$ for each combination of $a,b,c$ possible? Would it be safer than separate form (like $T^a \mod P$ for each)?

## Main question: Is the computation of $$a,b,c$$ in $$P^aQ^bR^c \mod N$$ (much) harder than in $$T_p^a \mod P$$, $$T_q^b \mod Q$$, $$T_r^c \mod R$$ ?

(assuming the first form exists)

## $$P^aQ^bR^c \mod N$$

With $$P^aQ^bR^c$$ you create unique numbers (e.g. with primes $$P,Q,R$$) for combinations of $$a,b,c$$ with $$a=0..a_{max},b=0..b_{max},c=0..c_{max}$$, in total $$(a_{max}+1)(b_{max}+1)(c_{max}+1)=M$$ different numbers. The highest number you can generate will be much higher than $$M$$. (For usage purpose each max exponent value should be about the same size (<+/-25%)).

Now is there a way to remove the gaps and make it cyclic by computing

$$P^aQ^bR^c \mod N$$

instead, which still generates $$M$$ different numbers, but the highest number is much closer to $$M$$, best case $$N. For security reasons $$P,Q,R$$ and $$M$$ should be high numbers (impact?). Furthermore it need to by cyclic. So for values greater than max exponent values it starts again.

Or more general $$a,b,c$$ are part of a set of numbers each, instead of an continuous interval, e.g. $$a \in A$$ and $$M=|A||B||C|$$. Successor and predecessor of each member need to be quite easy to compute. Or higher $$N$$ with $$N < kM$$, and $$k<.

## Use case and possible attack

Target use case would be an algorithm which computes some sort of ciphers $$e$$ which have the form $$e_{abc}= P^aQ^bR^c \mod N$$. But instead of direct computation it starts at a given $$e_0$$ (user dependend) and computes a next with e.g.

$$e_{a+1}'=e_0P \mod N$$ , or

$$e_{b+1}'=e_0Q \mod N$$ , or

$$e_{c+1}'=e_0R \mod N$$

or also combinations or multiple steps is possible, like

$$e'=eP^2Q^{42}R \mod N$$.

After this $$e'$$ will be the next $$e_0$$ and you can do the same again (any you like). Different to most other crypto algorithms the cipher $$e$$ is not to main interest. The way how to compute it (out of another) should be secured. A potential attacker does know the source code and all runtime variables. So he knows his current $$e_0$$ as well (and $$P,Q,R,N$$). He does not know his current $$a_0,b_0,c_0$$. It should be as hard as possible to compute those. Furthermore he can get the knowledge of other $$e_j$$. As above it should be hard to compute $$a_{j},b_{j},c_{j}$$ with $$e_j = P^{a_j}Q^{b_j}R^{c_j} \mod N$$ and also the computation $$e_j$$ out of $$e_0$$, which need $$a_{0j},b_{0j},c_{0j}$$ in $$e_j = e_0P^{a_{0j}}Q^{b_{0j}}R^{c_{0j}} \mod N$$ should be hard in most cases.

How would an attacker derive $$a,b,c$$? 3 times discrete logarithm? factorization needed?

## Separate form, like $$T^a \mod P$$

Alternative way would be

$$u = T_p^a \mod P$$

$$v = T_q^b \mod Q$$

$$w = T_r^c \mod R$$

With $$P,Q,R$$ primes and $$T_i$$ a corresponding prime root. (any better?)

Out of $$u,v,w$$ a single variable from $$0$$ to $$M-1$$ could be computed. But in use case those $$u,v,w$$ are internal variables of source code and a potential attacker can see those anyways. So in this case a cipher $$e_0$$ has 3 parts $$(u_0,v_0,w_0)$$. A next cipher $$e_0'$$ could be

$$e_0'=(u_0T_p \mod P, v_0, w_0 T_r \mod R)$$

In this case an attack need to compute 3 times discrete algorithm to get $$a,b,c$$, right?.

Assuming the form $$P^aQ^bR^c \mod N$$ exists. Would there be any benefit using it to increase the security of $$a,b,c$$?

## Edit:

Did some testing. With $$N=173, P=3, Q=5, R=7, a,b,c \in[0..3]$$ this form generates 64 unique numbers. But it is not cyclic.

So far I only found a 2D which is cyclic as well: $$N=126, P=17, Q=13, (R=1), a,b \in[0..5]$$ generates 36 unique numbers.

• Regarding "also the computation [of] $e_j$ out of $e_0$ [...] should be hard in most cases", surely that's trivial if the attacker knows all the parameters. After all, the legitimate user should presumably be able to compute $e_j$, and if the attacker knows everything the legitimate user does, then they can also compute all the same things. Apr 20, 2019 at 11:00
• More generally, while you've done a commendable job in actually providing a use case and a potential attack scenario for your scheme, it's still a bit unclear to me what it's actually supposed to achieve. It kind of sounds like you're trying to design some kind of a ratchet scheme, but I'm not sure if that's actually the case. Also, it's not clear to me what the three variables $a$, $b$ and $c$ are meant for, and why there are three instead of two or four? In all your examples, only $a$ ever seems to change AFAICT. Apr 20, 2019 at 11:10
• @IlmariKaronen: The attacker (same as the user) does not know the exponents $a,b,c$ of each of those factors. Toy example with only one factor: Your $e_0$ is 7. You know another $e_j$ which is 5. Neither a attacker nor the user should know how to compute $e_j$ out of $e_0$. The attacker knows it is something like $e_j = e_0T_p^{a_{0j}} mod P$, he knows the variables, in toy example: $5 = 7*6^{a_{0j}} mod 13$, the variable $a_{0j}$ he don't know and need to derive. As alternative he could also compute $a_{0j}$ out $a_j$ and $a_0$ for $e_j = T_p^{a_j} mod P$ and $e_0 = T_p^{a_0} mod P$, Apr 20, 2019 at 12:37
• @IlmariKaronen 2.0: $a,b,c$ are the exponents of those factors. e.g. $PQQRPQQRR = P^aQ^bR^c$ with $a=2$, $b=4$, $a=3$. But those are not written in source code. If you multiply a given $e_0$ with e.g. a number $Q$ you only know the exponent $b$ increased by one. You don't know the actual size of $b$. Each user has his own $e_0$, this can he multiply with $P,Q,R$ as like to get some new $e$'s. Other than for a ratchet the use case will also have inverse elements of $P,Q,R$ to reduce the exponents again. So he can move his ratchet back and forth. Apr 20, 2019 at 13:17
• Question: instead of depending on Dlogs, why not use some construct like $e_{n+1} = \text{Hash}(e_n)$? What property are you depending on that your construction provides that this simpler one doesn't? Apr 20, 2019 at 13:39