ラインダールSボックス

ラインダールSボックスは、ラインダール暗号で使用される置換ボックス（ルックアップテーブル）であり、高度暗号化標準（AES）暗号化アルゴリズムの基礎となっています。^[1]

S-box は、8 ビットの入力cを 8 ビットの出力s = S ( c )にマッピングします。入力と出力は両方ともGF(2)上の多項式として解釈されます。まず、入力は、ラインダールの有限体GF(2 ⁸ ) = GF(2) [ x ]/( x ⁸ + x ⁴ + x ³ + x + 1)内の逆数にマッピングされます。単位元であるゼロは、それ自身にマッピングされます。この変換は、発明者のKaisa NybergにちなんでNyberg S-boxとして知られています。^[2] 次に、逆数は、次のアフィン変換を使用して変換されます。

${\displaystyle {\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&0\\0&1&1&1&1&1 &1&1&0&0\\0&0&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\1\\1\\0\end{bmatrix}}}$

ここで、[ s ₇ , ..., s ₀ ]はSボックス出力であり、[ b ₇ , ..., b ₀ ]はベクトルとしての乗法逆数です。

このアフィン変換は、バイトをベクトルとして複数回回転させた合計であり、加算は XOR 演算です。

${\displaystyle s=b\oplus (b\lll 1)\oplus (b\lll 2)\oplus (b\lll 3)\oplus (b\lll 4)\oplus 63_{16}}$

ここで、b は乗法逆数、はビット単位の XOR演算子、は左ビット単位の循環シフト、定数63 ₁₆ = 01100011 ₂は16 進数で表されます。 ${\displaystyle \oplus}$${\displaystyle \lll}$

アフィン変換の同等の定式化は

${\displaystyle s_{i}=b_{i}\oplus b_{(i+4)\operatorname {mod} 8}\oplus b_{(i+5)\operatorname {mod} 8}\oplus b_{(i+6)\operatorname {mod} 8}\oplus b_{(i+7)\operatorname {mod} 8}\oplus c_{i}}$

ここで、s、b、cは8ビット配列、cは01100011 ₂であり、添え字はインデックス付きビットへの参照を示します。^[3]

もう一つの同等のものは次のとおりです。

${\displaystyle s=\left(b\times 31_{10}\mod {257_{10}}\right)\oplus 99_{10}}$^{[4] [5]}

ここで、はの多項式乗算であり、ビット配列として取られます。 ${\displaystyle \times }$${\displaystyle b}$${\displaystyle 31_{10}}$

逆 S ボックスは、単純に S ボックスを逆に実行したものです。たとえば、 b8 ₁₆の逆 S ボックスは9a ₁₆です。これは、最初に入力値の逆アフィン変換を計算し、次に乗法逆を計算して計算されます。逆アフィン変換は次のとおりです。

${\displaystyle {\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}={\begin{bmatrix}0&0&1&0&0&1&0&1\\1&0&0&0&1&0&0&1&0\\0&1&0&0&1&0&0&1\\1&0&0&0&0&1&0&0&1\\0&1&0&0&1&0&0&1&0\\0&0&1&0&0&1&0 &1&0&0&1\\1&0&0&1&0&0&0\\0&1&0&0&1&0&1&0\end{bmatrix}}{\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}+{\begin{bmatrix}1\\0\\1\\0\\0\\0\\0\\0\end{bmatrix}}}$

逆アフィン変換は、バイトの複数の回転の合計をベクトルとして表します。ここで、加算は XOR 演算です。

${\displaystyle b=(s\lll 1)\oplus (s\lll 3)\oplus (s\lll 6)\oplus 5_{16}}$

ここで、はビット単位の XOR演算子、は左ビット単位の循環シフト、定数5 ₁₆ = 00000101 ₂は16 進数で表されます。${\displaystyle \oplus}$${\displaystyle \lll}$

Rijndael S-box は、線形および差分暗号解読に耐性を持つように特別に設計されました。これは、入力/出力ビットの線形変換間の相関を最小限に抑え、同時に差分伝播確率を最小限に抑えることによって実現されました。

Rijndael S-box は Rijndael 暗号^[1]で置き換えることができるため、静的 S-box を利用する暗号に組み込まれたバックドアの疑いは払拭されます。著者らは、Rijndael 暗号構造は、相関/差分伝播特性が「平均的」な S-box が使用された場合でも、差分および線形暗号解析に対して十分な耐性を提供できると主張しています (Rijndael S-box の「最適な」特性を参照)。

次のCコードは S ボックスを計算します。

#include <stdint.h> 

#ROTL8(x,shift) を定義します ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox ( uint8_t sbox [ 256 ]) { uint8_t p = 1 , q = 1 ; /* ループ不変条件: ガロア体で p * q == 1 */ do { /* p を 3 倍にする */ p = p ^ ( p << 1 ) ^ ( p & 0x80 ? 0x1B : 0 );   
	      
	
	
	 
		
		              

		/* q を 3 で割ります (0xf6 を掛け算するのと同じです) */ 
q ^= q << 1 ; q ^= q << 2 ; q ^= q << 4 ; q ^= q & 0x80 ? 0x09 : 0 ;		    
		    
		    
		        

		/* アフィン変換を計算します */ 
uint8_t xformed = q ^ ROTL8 ( q , 1 ) ^ ROTL8 ( q , 2 ) ^ ROTL8 ( q , 3 ) ^ ROTL8 ( q , 4 );		               

		sbox [ p ] = xformed ^ 0x63 ; } while ( p != 1 );    
	    

	/* 0 は逆がないので特別なケースです */ 
sbox [ 0 ] = 0x63 ; }