# Security of an S-box based on modular multplicative inverse

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?

• Fundamentally, irreducible polynomials are used for S-Boxes as they cannot be factored. Your example shows some polynomial reductions. Even if you mask over it with something else to remove the fixed points, it will be more complex than using an irreducible polynomial. What was the motivation for this over an irreducible polynomial-based S-Box? Nov 29, 2017 at 4:09
• @bdegnan I figured that modular multiplicative inverses were a good way to start given their non-linearity and that they're the normal arithmetic equivalent of multiplicative inverses in a finite field. Nov 29, 2017 at 11:48
• could you please explain what is x and y in the equation ((X+1)*(Y+1)) mod 257 -1 =1 May 4, 2019 at 6:37
• a very similar operation is used in IDEA Jun 15, 2021 at 10:18

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$$.