Security of an S-box based on modular multplicative inverse

Question

The construction of Rijndael's S-box starts with the multiplicative inverses of each number over a finite field. It seems like this is the main source of its non-linearity. I figured that modular multiplicative inverses could be used as well. In this case, determining the value of $S(x)$ starts out with finding $y$ such that $((x + 1) \times (y + 1)) \bmod 257 = 1$.

Here is the result:

00 80 55 C0 66 2A 92 E0 C7 B3 BA 95 B1 C9 77 F0
78 63 E5 59 30 DD BD 4A 47 58 ED 64 C2 3B C6 F8
93 BC EA 31 83 72 90 2C A2 98 05 6E 27 5E AE A5
14 23 7D AC 60 76 F2 B2 F7 E1 3C 1D 3A E3 65 FC
56 49 E9 DE 94 F5 B4 18 A8 41 17 B9 F6 C8 F3 96
A4 D1 5F CC 7E 02 40 B7 19 13 D0 AF 97 D7 2D 52
34 8A 86 11 1B 3E 04 D6 A3 B0 F4 BB DF F9 2B D9
73 7B 25 70 85 9E 35 0E 10 9D 8B 71 DB 32 54 FE
01 AB CD 24 8E 74 62 EF F1 CA 61 7A 8F DA 84 8C
26 D4 06 20 44 0B 4F 5C 29 FB C1 E4 EE 79 75 CB
AD D2 28 68 50 2F EC E6 48 BF FD 81 33 A0 2E 5B
69 0C 37 09 46 E8 BE 57 E7 4B 0A 6B 21 16 B6 A9
03 9A 1C C5 E2 C3 1E 08 4D 0D 89 9F 53 82 DC EB
5A 51 A1 D8 91 FA 67 5D D3 6F 8D 7C CE 15 43 6C
07 39 C4 3D 9B 12 A7 B8 B5 42 22 CF A6 1A 9C 87
0F 88 36 4E 6A 45 4C 38 1F 6D D5 99 3F AA 7F FF

I understand that this by itself would make for a terrible S-box given its symmetry and fixed points, but perhaps some other math stacked on top of it would make it better?

Answer 1

As far as I can tell you're using integer arithmetic modulo $257$ (which is a prime) but mapping with the +1 to the multiplicative group $Z_{257}^\ast$ for a $8\times8$ Sbox. And taking the standard binary representation of $x-1$ as the corresponding 8 bit vector $v(x)$.

The group $Z_{257}^\ast$ is of course cyclic. The difficulty is analyzing and proving the security of an Sbox based on such a mathematical object, in terms of nonlinearity, differential cryptanalysis, avalanche effect, etc. since the chosen operation is not simply related to the bit representation.

Jim Massey used a similar idea in the SAFER series of ciphers. The Sbox mapping $v(x)\mapsto S(v(x))$ is represented in $Z_{257}^\ast$ as $y+1=45^{(x+1)}\pmod{257}$ and its inverse is $x+1=\log_{45}(y+1).$ Note that $45$ is a primitive element and its powers generate $Z_{257}^\ast$.

This paper has some details. There is more on AES competition related pages, since SAFER or SAFER+ was a candidate, but the exact information is harder to locate there.