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