0

I'm working on a code challenge, and I've figured out how messages are encoded, now I just need to reverse the process.

The device encodes strings as such:

For each character $c$ in the string $S$, replace it with the character at position $C$ of $key$ where:

$C = ((P + 1)2^{i + 1} - 1) \% L - d$

$i$ is the position of $c$ in $S$ (known)

$P$ is the position of $c$ in $key$

$L$ is the length of $key$ (known $L=67$)

$\%$ is the modulus operator

$d$ is either $1$ or $0$ depending on a condition ($i>46$)

If $C$ is known, how do I go about solving for $P$? I did a few searches for the inverse of modulus, but I'm not grokking how to apply that here.

Shmiddty
  • 101
  • There is no actual inverse of the modulus operation, for the simple reason that 5%3==8%3==2, so the inverse of 2 is both 5 and 8 (and a lot of others as well) simultaneously. That's not a good property for an operation to have, not even an inverse. That is why you haven't gotten any results. However, working modulo $L$, there might be an inverse to "add $1$, multiply by $2^{i+1}$, then subtract $1$". At least as long as $L$ is odd. – Arthur Oct 23 '16 at 19:16

1 Answers1

1

If you know (or can guess) $d$, you want $P$ with $1 \le P \le L$ and $ C + d + 1\equiv (P+1) 2^{i+1} \mod L$.

If $L$ is odd, you can do this, because $2$ is invertible mod $L$. In fact, since $2 ((L+1)/2) \equiv 1 \mod L$, you have $$P+1 \equiv (C+d+1) ((L+1)/2)^{i+1} \mod L$$

If $L$ is even, there might not be any solution at all, and if there is one it is not unique.

Robert Israel
  • 448,999
  • Thanks! This has gotten me closer. I'm getting the correct result for the first 12 characters.

    $P = ((C + d + 1)((L + 1)/2)^{i + 1}) % L - 1$

    I assume I'm missing a step.

     – Shmiddty Oct 23 '16 at 19:57