0
$\begingroup$

If we have a encrypting function f(x, y) (x for input, y for key) and let's say we composite this function n times inside itself with the same y (like f(f(f(x, y), y), y)) and set the output to be z. Does there exist another function g(v) so that g(z)=x? Can this be proven for any kind of encryption function f(x, y) stacked inside itself any times? Thanks.

$\endgroup$
5
  • 1
    $\begingroup$ I believe this is only possible if $f$ is linear, but pretty much every encryption algorithm is highly nonlinear, so you will not find a $g$ that meets your criteria for a given $y$, unless it is the multi-step inverse of your encryption operation $\endgroup$ Feb 18, 2016 at 2:48
  • $\begingroup$ @RichieFrame, why should "the multi-step inverse" not qualify? Or put another way, as long as the encryption is decryptable, isn't the answer clearly yes? $\endgroup$
    – otus
    Feb 18, 2016 at 5:47
  • $\begingroup$ @otus it sounds like he is looking for a function with a lower workload than the standard decryption function, ideally with a workload equal to a single decryption function $\endgroup$ Feb 18, 2016 at 5:59
  • $\begingroup$ @RichieFrame, I guess that's possible, but it is not stated in the question. user2180617: please clarify. $\endgroup$
    – otus
    Feb 18, 2016 at 6:00
  • $\begingroup$ I mean a function g(v) that it is "simpler" than all the inverses of the encryption function. $\endgroup$ Feb 19, 2016 at 0:57

1 Answer 1

1
$\begingroup$

By definition, there exists such a function. Your function $g(z)$ could be simply a table of all the possible values of $f(f(f(x, y), y), y)$ mapped back to one of the possible values of $x$.

I think that what you're asking is whether there is an efficient algorithm for unwinding this chaining. Generally, with cryptographic algorithms, the answer is no, and this is intentional (see RichieFrame's comment about nonlinearity).

There are exceptions, though. For example, with "raw" RSA, $f(x, y) = x^y \mod n$, for whatever $n$ is used alongside $y$ as the public key. Then:

$f(f(f(x, y), y), y) = ((x^y)^y)^y \mod n = x^{y^3} \mod n$

Let $d$ be the private key (exponent) corresponding to $y$. Then, you have:

$g(z) = z^{d^3} \mod n = x \mod n$.

In general, this property is something to avoid, because it often allows attackers to modify the contents of an encrypted message (to something useful) without being able to decrypt the message. In the case of "raw" RSA, it leads to attacks; real RSA implementations use padding to make RSA not have this property.

Closely related: malleability

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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