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 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 Szudnik's Elegant Pairing Function 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: