0
$\begingroup$

My friend asked once a question which sounds very interesting:

If a function does not have inverse, does it mean that the message cannot be deciphered ?

What is the answer to this question ? In my opinion it is a definitely yes

$\endgroup$
  • 4
    $\begingroup$ Kind of depends on your definition of "deciphered", doesn't it? Take a simple function without an inverse, like $y = x^2$, for $x \neq 0$. Given $y$, there's two possible values for the message $x$, so it's impossible to know with 100% certainty what the original $x$ was. However, you probably don't want to leave any secrets lying around using this function. $\endgroup$ – bkjvbx Sep 22 '16 at 9:59
  • $\begingroup$ @bkjvbx but what for something more complex? Like functions that do not have inverse, not that they can have 2 solutions (like y=x^2) $\endgroup$ – SnuKies Sep 22 '16 at 10:06
  • 1
    $\begingroup$ Maybe invertible isn't the right question. Maybe one-way is what you really mean? $\endgroup$ – mikeazo Sep 22 '16 at 11:48
  • 1
    $\begingroup$ @SnuKies, for example, the function $f(x)=1$ for all $x$ is not invertible, in the mathematical sense. But, is such a function even useful for cryptography? Also, to add to my one-way function comment, there are also trapdoor one-way functions. $\endgroup$ – mikeazo Sep 22 '16 at 11:54
  • 2
    $\begingroup$ It also depends on how you use a one-way function. For example you could run a counter on the function and XOR (or otherwise combine reversible) this output (of some secret input?) with your message. Decryption pretty much equals encryption then (this is how the commonly used CTR mode works). $\endgroup$ – SEJPM Sep 22 '16 at 13:03
1
$\begingroup$

A function that doesn't have an inverse still has an inverse image or preimage. I.e., if we have $f : P \to C$, and we can efficiently compute the set $f^{-1}(c) = \{p \in P\; |\; f(p) = c\}$, then that tells us information about what are the possible plaintexts $p$ for a ciphertext $c$. It doesn't tell you which one of the alternatives is the "true" one, but in real life you very often have other, independent information about what the plaintext is likely to say. If you put that independent information together with the preimage of the ciphertext, you may well end up inferring the plaintext.

Or an even dumber attack, you can just enumerate your independently- generated guesses at the content of the plaintext, from more likely to less likely, apply the function to each them, and see if the result matches the ciphertext. Password cracking works precisely like this—the dictionaries and other tricks of the trade (masks, mutations, etc.) can be understood as hypotheses about which passwords real-world users are likely to pick, and the stolen outputs of the password hashes—which are functions without inverses—are used to test these hypotheses. It's wildly successful.

So I would not look at it as a yes/no question, but as a quantitative one: how much does the attacker's knowledge of the function and ciphertext help them achieve their goal, relative to whatever independent knowledge they have?

$\endgroup$
0
$\begingroup$

Not necessarily.

The classic example for this, is RSA:

Without going into detail (see https://www.cs.utexas.edu/~mitra/honors/soln.html for a tiny example) might be written in code as:

encrypted_message=rsa(message,public_key,modulus)

(note that message must be less than modulus, and encrypted_message will be less than the modulus).

Where public_key and modulus are normally distributed together.

There is no "inverse" of this function. Given the encrypted message, the public key, and the modulus, there is no way to reverse this process, short of trying different numbers.

There is, however, an "inverse" of the public key - this is the private key. This cannot be calculated for the public key alone, but the keys can be generated together, as a pair (follow the above link for an example).

In this case, the function is, in fact, exactly the same, but substituting the private key for the public key, and swapping the message and the encrypted message gives us:

message=rsa(encrypted_message,private_key,modulus)

... and you have back your original message.

In cryptography, the steps to follow should be public knowledge, only the keys should be private. In the case of public-key cryptography, the keys are different, so even someone with the public key should not be able to reverse the process. Sometimes public and private keys are generated together (as in the case of RSA), whereas for some other algorithms, the private key is randomly chosen, and the public key is derived from the private by a function that does not have an inverse.

$\endgroup$
  • 2
    $\begingroup$ "This function doesn't have an inverse" ... [proceeds to describe an inverse for the function] $\endgroup$ – Mikero Sep 23 '16 at 1:50
  • $\begingroup$ @Mikero the function does not have an inverse. The data has an inverse. Compare this to the calculation 3*2=6; you can reverse this either by taking the inverse of the "*" function which is "/": 6/2=3. Or, you can inverse the data: the inverse (for multiplication) of 2 is 0.5: 6 * 0.5 = 3. This distinction is very important for crypto, since the functions are well known, the parameters (=private key) may be secret. $\endgroup$ – AMADANON Inc. Sep 23 '16 at 2:15
  • $\begingroup$ Of course RSA encryption has an inverse with respect to the message, namely decryption. The inverse is merely hard to compute, but that has no effect on the existence of the inverse. $\endgroup$ – CodesInChaos Sep 23 '16 at 5:41

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.