0
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @J.Doe: perhaps use an elliptic curve group instead? $\endgroup$ – poncho Apr 19 at 21:17
  • $\begingroup$ 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? $\endgroup$ – J. Doe Apr 19 at 21:17
  • $\begingroup$ 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. $\endgroup$ – J. Doe Apr 19 at 21:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.