はじめに

AESは現在デファクトスタンダードのブロック暗号アルゴリズムで、だいたい使用する時は第一選択になります。
そのデファクトスタンダードであるAESを高速に実装するために、x64系CPUではAES-NI命令が実装されています。(AES-NI命令のメリットは高速化だけではなく、キャッシュ攻撃という攻撃に対する安全性があります)

さて、あまり素人には推奨されないのですが、オリジナルのブロック暗号、ストリーム暗号またはハッシュ関数を設計する際に、高速実装のために、AES-NIの命令を利用したいことがあります。そこで、ここではAES-NI命令をうまく使ってどのようなことができるかを示します。

AESの各関数

AESは複数の関数の組み合わせで出来ています。FIPS197によると

SubBytes
ShiftRows
MixColumns
AddRoundKey
SubWord
RotWord
です。また、これらの関数のうち、SubBytes、ShiftRows、MixColumnsは復号のために逆関数が定義されています。この記事では、
InvSubBytes
InvShiftRows
InvMixColumns
と記載します。
AddRoundKeyは逆関数が関数と一致するため、SubWordとRotWordは復号でも逆関数は使用しないため、定義されていません。関数の中身は詳しくはFIPS197で。
ここで、少しだけ簡単な説明をします。

SubBytes

16バイトの内部状態S[0,0]~S[3,3]に対して、変換テーブルを使って変換します。逆関数は元に戻します。

ShiftRows

内部状態を4×4のテーブルと見なして、各行で巡回シフト(ローテート)します。ローテートのパラメータは行ごとに違います。
逆関数は元に戻すため、ローテートの方向が逆になります。

MixColumns

内部状態を4×4のテーブルと見なして、各列で計算します。この計算はちょっとややこしいのでここでは省略します。逆関数は元に戻します。
ShiftRowsで行をシャッフルし、MixColumnsで列を混合することにより、SubBytesの効果を内部状態全体に広げます。

AddRoundKey

内部状態に対して秘密鍵生成された拡大鍵を排他的論理和します。

SubWord

拡大鍵生成に使います。4バイトの値をバイトごとに変換テーブルを使って変換します。変換テーブルはSubBytesと同じです。

RotWord

拡大鍵生成に使います。4バイトの値を8ビット右ローテートします。

AES-NI命令

AES-NI命令は

AESENC
AESENCLAST
AESDEC
AESDECLAST
AESKEYGENASSIST
AESIMC
の6命令で構成されています。それぞれの中身を説明します。

AESENC

AESENCは内部状態128bitと拡大鍵128ビットを引き数に持ち、SubBytes, ShiftRows, MixColumns, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの暗号化1ラウンド分に相当します。

AESENCLAST

AESENCLASTは内部状態128bitと拡大鍵128ビットを引き数に持ち、SubBytes, ShiftRows, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの暗号化最終ラウンドに相当します。AESENCとの違いはMixColumnsを実行しない点です。

AESDEC

AESDECは内部状態128bitと拡大鍵128ビットを引き数に持ち、InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの復号1ラウンド分に相当します。

AESDECLAST

AESDECは内部状態128bitと拡大鍵128ビットを引き数に持ち、InvSubBytes, InvShiftRows, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの復号最終ラウンドに相当します。AESDECとの違いはInvMixColumnsのみです。

AESKEYGENASSIST

AESKEYGENASSISTは現在のラウンドの拡大鍵を引き数に持ち次のラウンドの拡大鍵を生成します。SsubWordとRotWordが使用されていますが、それだけではありません。

AESIMC

AESIMCは内部状態128ビットを引き数に持ち、InvMixColumnsを実行します。暗号化用拡大鍵から復号用拡大鍵を生成します。

AES-NI命令をちょっとマニアックに使う

というわけで、応用編です。いくつかの関数を組み合わせた命令を使って、存在しない組み合わせを作り出せないか？という話です。

SubBytes+ShiftRows+MixColumns

AESENCから、AddRoundKeyを抜いたものです。AddRoundKeyは単に排他的論理和ですので、オール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。

SubBytes+ShiftRows

SubBytes+ShiftRows+MixColumnsがあるのだから、MixColumnsはInvMixColumnsで打ち消せば...と思ってしまいそうですが、AESENCLASTを使えばより高速に実装できます。つまり、AESENCLASTにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。

SubBytes

SubBytesを単独で実装するのなら、仕様書通りに実装したほうが良いと思いがちですが、16回のテーブル参照を行う位なら、InvShiftRows(4回のローテート)を実装してやったほうがよさげです。（テーブル参照はキャッシュ攻撃という弱点を引き込む可能性もあります。
つまり、前項のSubBytes+ShiftRowsにInvShiftRowsを組み合わせるのです。
ただ、当然処理はSubBytes+SfitRowsより遅くなります。何かを設計するのなら、SubBytesを単独で使うのは良くないと言えます。

ShiftRows+SubBytes

SubBytesとShiftRowsを入れ替えても結果は変わりません。これは何かに使えそうです。

InvSubBytes+InvShiftRows+InvMixColumns

これも、AESDECにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。

InvSubBytes+InvShiftRows

これも、AESDECにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。

InvSubBytes

SubBytes同様、ShiftRowsを実装してやるほうが速そうです。

InvShiftRows+InvSubBytes

InvSubBytesとInvShiftRowsは入れ換え可能ですので、InvShiftRows+InvSubBytesも計算可能です。

MixColumns

さて、単体でMixColumnsを抽出してみましょう。使うものは二つ、

InvShiftRows+InvSubBytes
SubBytes+ShiftRows+MixColumns

です。
この二つを連結してやると、
InvShiftRows+InvSubBytes+SubBytes+ShiftRows+MixColumns
になります。ところが、InvSubBytesとSubBytesは逆変換なので、この二つを連結すると無変換になります。つまり
InvShiftRows+ShiftRows+MixColumns
ですね。
さらに、InvShiftRows+ShiftRowsも逆変換なので消えます。つまり、
MixColumns
が残ります。

結論

以下の関数の連結はAES-NI命令一つで実装可能

SubBytes+ShiftRows+MixColumns
SubBytes+ShiftRows
InvSubBytes+InvShiftRows+InvMixColumns
InvSubBytes+InvShiftRows

以下の関数はAES-NI命令二つで実装可能

MixColumns

逆に、SubBytesやShiftRowsをAES-NI命令のみで実装するのは困難です。うまくこの組み合わせを利用すれば、AES-NIを用いて高速実装可能なブロック暗号・ハッシュ関数等が設計可能と言えます。