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$
