# How much more secure is $c = mg_1^r + g_2(g_1(g_1^r-1)/(g_1-1)) \mod p$ compared to just $c = mg_1^r \mod p$ (dis. log), all known but $r$?

To encode a message $$m$$ to a cipher $$c$$ you can use the only hard solvable problem of computing the discrete logarithm with a generator $$g$$ in base over a prime $$p$$.

$$c = mg_1^r$$ mod p

If an attacker want to derive $$r$$ he can use e.g. the Baby-step giant-step algorithm. He can solve this in $$\mathcal{O}(\sqrt{p})$$. I'm looking for a way to make it harder to reduce the size of $$p$$ and still be safe.

## Are there any records about solving something like this:

$$c = mg_1^r + g_2\frac{g_1(g_1^r-1)}{g_1-1} \mod p$$

Or do you know any? Would it (significantly) increase the solve time $$\mathcal{O}(\sqrt{p})$$?

The potential attacker has the source code and so he knows $$g_1, g_2$$ and $$p$$. So if he picks a known $$m$$ and $$r$$ he can also compute $$c$$. In my usage scenario each computed $$c$$ can be used as $$m$$ to compute the next $$c$$. So the main aspect is not to encode a message. I'm looking for a way to make the computation of r as hard as possible for a given $$m$$ and $$c$$. That means the attacker has by default a given $$m$$ and some $$c$$'s. He should not be able to compute the respective $$r$$'s which allows him to compute those $$c$$'s out of the $$m$$. And if he somehow managed to compute $$r$$ for a $$m$$ to get $$c$$ it should not be easier if $$m$$ or $$c$$ changes.

## Derivation of formula:

If you use $$+$$ instead of $$*$$ operator you can encode like:

$$c_1 = m+g_2 \mod p$$

$$c_2 = m+g_2+g_2\mod p$$

so for $$c_r$$ you can shorten it with multiplication by r

$$c_r = m+rg_2\mod p$$

But this can easy be solved with computing $$g_2^{-1}$$ with e.g. eucl. algorithm.

But how about a combination with $$*$$ operator?

$$c_1 = (m+g_2)*g_1\mod p$$

$$c_2 = ((m+g_2)*g_1+g_2)*g_1 = mg_1^2+g_2g_1^2+g_2g_1\mod p$$

$$c_3 = mg_1^3+g_2g_1^3+g_2g_1^2+g_2g_1\mod p$$

so for $$c_r$$

$$c_r = m*g_1^r + g_2*\sum_{i=1}^r g_1^i \mod p$$

$$c_R = mg_1^r + g_2\frac{g_1(g_1^r-1)}{g_1-1} \mod p$$

## 1 Answer

If the attacker knows everything (including $$m$$) except for $$r$$, he can rewrite it to:

$$g_1^r = (c + g_1 g_2 (g_1 - 1)^{-1}) ( m + g_1 g_2( g_1 - 1)^{-1})^{-1} \pmod{p}$$

He knows everything on the RHS, and so it's a simple discrete log problem.

BTW: for the $$\mathbb{Z}_p^*$$ group, there are much faster attacks than Baby-step-Giant-step

• @J.Doe: perhaps use an elliptic curve group instead? – poncho Apr 19 at 21:17
• oh dear, how could I not see that. Thanks for quick response. Need to think about another way to solve it. Or do you or anyone know a better way? – J. Doe Apr 19 at 21:17
• use case need to be in 3 dimension. With elliptic curves I would miss the factorization (or at least I think so -> will create new question). As long there is no way to have some single number and 3 generator (one for each ellip. curve) which can be used on it, including no internal representation of each dimension because attacker can see source code. – J. Doe Apr 19 at 21:32