Cipher follow-up: pairing functions, revisited
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
In my last article[1] 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 Szudzik[2], "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[3] 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 Szudzik:
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 Szudzik 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.
[1]
gopher://tilde.town/0/~wrmr/writs/20250925-a-diagonal-cipher.txt
[2]
http://szudzik.com/ElegantPairing.pdf
[3]
https://en.wikipedia.org/wiki/Pairing_function#Inverting_the_Cantor_pairing_function
