0
$\begingroup$

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<M+4$. 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<<M$.


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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Apr 20 at 11:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Apr 20 at 11:10
  • $\begingroup$ @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$, $\endgroup$ – J. Doe Apr 20 at 12:37
  • $\begingroup$ @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. $\endgroup$ – J. Doe Apr 20 at 13:17
  • 1
    $\begingroup$ 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? $\endgroup$ – poncho Apr 20 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.