3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – b degnan
    Nov 29 '17 at 4:09
  • $\begingroup$ @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. $\endgroup$
    – Melab
    Nov 29 '17 at 11:48
  • $\begingroup$ could you please explain what is x and y in the equation ((X+1)*(Y+1)) mod 257 -1 =1 $\endgroup$
    – hardyrama
    May 4 '19 at 6:37
  • $\begingroup$ a very similar operation is used in IDEA $\endgroup$
    – Fractalice
    Jun 15 '21 at 10:18
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.