Encryption, bijection and reversibility

The whole point of this article is to tell you that you need to write reversible programs, or programs with results that are easy to undo. There, you’ve got the point. That’s it.

You still here? Then get ready for a bucket-load of concepts below.

The swap

How do you change DAN from a him to a HER? Add 4. Suppose you have the entire alphabet on one row and another set shifted by 4 placings:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
EFGHIJKLMNOPQRSTUVWXYZABCD

Can you see the correspondence? We can even undo the sex change, reversing HER back to DAN.

This is one of the simplest forms of encryption. It’s also easily broken with the use of computers (and programming of course). Still it illustrates the concept of changing something that’s RIGHT to something unintelligible like VMKLX.

The whole point of encryption is to scramble a plain text message into something obscure so no one except the intended can read it. There’s no point in having an obscure message without being able to get the plain text message back, is there? So encryption has to be reversible.

Now we’re going to do math.

Please, no trees

Let ALPHA be the set of all 26 English alphabets in upper case. Suppose a function F behaves such that if F(x) equals F(y), then x must be equal to y, where x and y belong to the set ALPHA. Then the function F is said to be injective.

Using the encryption model above, where our function F swaps the letters from the top row to the letters in the bottom row, let’s have the final letter be D. There’s only one letter that can map to D, and that’s Z. F is injective.

It might be a bit hard for you to visualise that. Let’s use the contrapositive version of the statement. If x not equal to y, then F(x) not equal to F(y). So if P not equal to Q (which is true), then F(P) = T which is not equal to U = F(Q).

Injectivity is a one-to-one relation. No tree-like structure, no linking of nodes, no multiple results from the same starting point, no multiple starting points ending in the same result.

Must start somewhere

Let ALPHA be the set of all 26 English alphabets in upper case. Suppose a function F behaves such that for every letter y in ALPHA, there’s another letter x in ALPHA such that F(x) = y, then F is said to be surjective.

Using the encryption model above, every letter in the bottom row has a corresponding letter in the upper row. So our function F that swaps the top letter to the bottom letter is surjective.

Surjectivity is a there-exists-a-starting-element concept. On a philosophical note, your life journey can be likened to surjectivity; you started somewhere didn’t you?

Two way street

A function F is said to be bijective if it is both injective and surjective. It is one-to-one, and for every destination, there’s a starting point. So you can go back and forth in a unique manner without fear of getting lost.

Bijections allow reversibility. Encryptions are bijections. Thus encryptions are reversible. Actually, I just thought I’d introduce you to the concept of encryption and bijection. Their relation to reversibility is hand-wavily tenuous… But I’m forging on anyway, so…

Can you write a bijective program?

I would have to say no, in general. There’s usually more than one way to do something, and that violates the injective rule. But if you conform to a stricter set of rules, you can approach the situation where there are fewer ways of writing code to do whatever you need done. So you get an almost injective state. Then you get a reversible program under strict rules.

What’s the whole point of this? A program whose results can be easily reversed is useful. Suppose the result isn’t satisfactory. Do you need to do a lot to undo that damage? A computer virus is (generally speaking) not useful. It’s effects are not easily reversible. In fact, its intent is to be as irreversible as possible.

A reversible program, a program that you can rerun with minimal fuss and effort. That’s useful. Why would reversibility be useful?

Because it allows humans to make mistakes.

And we will make mistakes, make no mistake about that *smile*. When users make a mistake, how have you written your program so it’s easy to recover from it?