A diagonal cipher
=*=*=*=*=*=*=*=*=

Some days ago, when I was about to go to bed, there sprouted between my
ears the idea for a simple way to obscure messages by reordering their
contents, instead of substituting symbols like the ciphers I'm familiar
with do.  What I came up with is to take a message (say, "Hello world!"),
format it as a grid, then output characters found by tracing diagonal
lines through that grid.

Hel  ///  0 2 5
lo   ///  1 4 8  Hlewollo dr!
wor  ///  3 7 a
ld!  ///  6 9 b

That still looks a lot like the original message, but we get better
results by flipping it vertically:

Hel  \\\  6 9 b
lo   \\\  3 7 a  lwdlo!Hore l
wor  \\\  1 4 8
ld!  \\\  0 2 5

The best implementation I've managed to write so far is one that
determines lines in two steps, first moving up the lines connected to the
left edge of the grid, then along the top edge.  `isqrt()` can just be
replaced with a normal `sqrtf()` call if you're willing to link with
`-lm`, or removed entirely if you'd rather the width of the character grid
be constant --- I want it more or less square.  Decryption is super
simple, too, just replace `*dest++ = src[i]` with `dest[i] = *src++`.

unsigned isqrt(unsigned x) {
       if (x <= 1) return x;
       unsigned a = x/2, b = (a + x/a) / 2;
       while (b < a) a = b, b = (a + x/a) / 2;
       return a;
}

void encrypt(char *dest, const char *src, int n) {
       int cols = n < 1 ? 1 : isqrt(n);
       int lines = (n + cols - 1) / cols;

       for (int y = lines - 1; y >= 0; y--) {
               for (int x = 0; x < cols; x++) {
                       int i = (x + y) * cols + x;
                       if (i < n) *dest++ = src[i];
               }
       }

       for (int x = 1; x < cols; x++) {
               for (int y = 0; y < lines && x+y < cols; y++) {
                       int i = y * cols + x + y;
                       if (i < n) *dest++ = src[i];
               }
       }
}

This instinctually *feels* kinda ugly, since it needs two separate loops.
Cantor's pairing function[1] is a close fit for what we want to do, but
produces out-of-range results because it enumerates all positive integers
pairs, not just those within the subset of our grid dimensions.

For a 3x3 grid:

0 1 3
2 4 7
5 8 c

Clamping them within range just ends up with a bunch of duplicate indices;
it doesn't work.  Matthew Szudzik's Elegant Pairing Function[2] actually
does seem to fully enumerate all indices in the grid, but only if it's
perfectly square, and it traces the borders of square regions instead of
diagonal lines:

0 2 6
1 3 7
4 5 8

A few closing asides:

* This is simple enough someone's probably done it before.

* Consider using a substitution cipher to further obfuscate the encrypted
 message.  I find the current output charming, but it lets you piece
 together shorter messages with just anagrams.

* You could add bogus text at the end before encrypting and strip it off
 after decrypting, to mix it between the real payload.

* It might still be worth playing around more with the pairing functions.
 What would it look like to reorder text along square edges, like with
 Szudzik's?

* What about following various space-filling curves[3]?

* What about seeding a PRNG with the text's length, then using random
 indices until all have been hit?  Could that be made feasible for longer
 texts?  If not, maybe split it into chunks, randomly order those and
 their contents.

=> Cipher follow-up: pairing functions, revisited[4]

[1] https://en.wikipedia.org/wiki/Pairing_function
[2] http://szudzik.com/ElegantPairing.pdf
[3] https://en.wikipedia.org/wiki/Space-filling_curve
[4] gopher://tilde.town/0/~wrmr/writs/20250926-cipher-followup-pairing-functions.txt