In my last article about
transposition ciphers, there was a digression of trying to follow diagonal
lines through a rectangle in only one loop, by using the classic Cantor pairing
function: (x^2 + 3x + 2xy + y + y^2)/2. To quote Szudnik, “the pairing
function can be understood as an ordering of the points in the plane” — it
allows us to take the (x, y) coordinates of any given position in 2d space,
given x>0 and y>0, and return its index into that function's ordered set
of all points.
I got stuck on trying to iterate over all cells on our grid and do something useful with the pairing function's index for each point, but that won't work, because it orders all points, not just those on the grid: so the indices wind up going out of bounds. But what if instead we do the opposite, and try to determine the coordinates from the index? That way we could just iterate over indices until all cells have been hit.
For the Cantor pairing function, Wikipedia gives us:
z = π(x, y)
w = floor((sqrt(8z + 1) - 1) / 2)
t = (w^2 + w) / 2
y = z - t
x = w - y
And after flipping the order of x and y, that can be plugged into
encrypt() to give us a single-loop algorithm that yields the same
output.
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 z = 0, j = 0; j < n; z++) {
int w = (isqrt(8*z + 1) - 1) / 2;
int t = (w*w + w) / 2;
int x = z - t;
int y = w - x;
if (y < lines && x < cols) {
y = lines - 1 - y;
int i = y * cols + x;
if (i < n) dest[j++] = src[i];
}
}
}
This is, I would say, ultimately a worse implementation of the diagonal cipher, since it's both more confusing and likely more computationally expensive, looping for more indices than there are cells, repeatedly calling that software square root routine. But it frees us up to try the same thing with other pairing functions! Here's Szudnik:
void encrypt(char *dest, const char *src, int n) {
int cols = n < 1 ? 1 : isqrt(n);
int lines = (n + cols - 1) / cols;
int j = 0;
for (int z = 0; j < n; z++) {
unsigned u = isqrt(z);
int w = z - u*u;
int x = w<u ? w : u;
int y = w<u ? u : w-u;
if (y < lines && x < cols) {
int i = (lines - 1 - y) * cols + x;
if (i < n) dest[j++] = src[i];
}
}
}
And here's a sample of its output, run on an earlier part of this article:
sd ijuhcs Taethatesvs a eterme itfiposite ut rn,tead webnewoe ds. Butetram ad up going eiay tnowoso the indnlt thd huithose on th ewhe atcel points, nha ee t t e oecause it ordilo cr osgteat won't wtlvcioytif r ror each point, b. eono hf wijsru function's indecrudrte bidu ktxful with the paire ledo ion:s, iand do something ulidxi onud ta tfnsl cells on our gridln ?ndpsn lbhoge g to iterate over alI got stuck on tryin
The results of following a Szudnik ordering in the character grid are honestly kinda cool. Because it traces the edge of squares, instead of diagonal lines, random chunks of text are completely coherent and the same as in the source, before it goes vertical and gets strange again. These islands of coherence also grow longer as the text goes on, because they fall on the border of larger squares. So, not a great cipher, but I'm glad to have tried it.
Next time, maybe a Hilbert curve cipher.