Math to replace s-boxes - Good or bad idea? The following was going through my brain for the past week. If my thoughts are generally known to the cryptographic community would someone provide a link or two. Even if I’m making a classic newbie mistake. 

Cryptographic internal functions operating like $x=f(x)$ can be table lookup s boxes with the inverse s box as a separate table.  A 16-bit sbox and its inverse can be implemented with a little math and no tables. Use the prime $m = (2^{16})+1$. Then pick constants $p$ and $q$ such that the recursion

Seed = Seed * p % m;


touches all values, 1..$2^{16}$.  Then select $q$ such that $p * q ~~mod~~ m = 1$.

p = 49374; // example values
q = 32065;
y = ((x+1) * p % m)-1; // forward
x = ((y+1) * q % m)-1; // reverse
// x+1 puts the 16-bit x into the range (1..2^16) where the recursion works.
// the -1 at the end makes the result fit in 16 bits.


There are over 32000 values of $p$ for which the recursion touches all $2^{16}$ values.

“Mod 0x10001” can be implemented with little more than a subtract. No actual division is required. Is this a reasonable part of a good encryption algorithm? Perhaps to replace 2 8-bit s box tables?



Getting carried away - - 32-bit (non invertible) sbox

Because $m=2^{32}+1$ is not a prime there is no full ($2^{32}$ term) sequence recursion of the form

Seed = Seed * const % m


This % m operation can also be formed with only a subtract if we don’t care to be super accurate. Or a test and subtract 1 it we want to be accurate.  Thus encryption code performing

z ^= ((x+1) * const % m)-1


can be performed in decryption to recover the prior value of $z$.

Is this “32-bit sbox” a useful concept?
The S-boxes in quite many encryption algorithms (for example, in AES) have been already built with math (the AES S-box is an inversion function in $GF(256)$ plus an affine transformation). The lookup tables exist solely to ease the implementation. In fact, modern Intel/AMD CPU are already equipped with AES round function instructions, so the tables are not needed at all.

When people design new S-boxes, the first question to answer is Why? and the next one is What properties do they have compared to the existing ones?. Until there are reasonable answers, the proposals are not used and even not being analyzed.