第3回　AES暗号化：マスターIT／暗号技術

今回は、DESに代わる標準暗号規格として制定されたAESを解説。DESと違って128bit以上の長い鍵を使って暗号強度を高めると共に、比較的シンプルなアルゴリズムで高速な処理を可能としている。

» 2015年06月18日 05時00分公開

[打越浩幸，デジタルアドバンテージ]

この記事は会員限定です。会員登録（無料）すると全てご覧いただけます。

連載目次

このマスターIT連載は、IT Pro初心者に向けて、さまざまなITテクノロジを紹介、解説するコーナーである。まずは暗号化について取り上げる。

　前回は代表的な共通鍵暗号方式であるDESについて取り上げた。今回はその後継であるAESについて見ていく。

AESとは

　「AES（Advanced Encryption Standard）」は、DESの後継として米国の国立標準技術研究所（NIST：National Institute of Standards and Technology）によって制定された新しい暗号化規格である。

　1997年にDESの後継となる共通鍵方式の暗号化規格が公募され、世界中から21の方式が提案された。それらは暗号の専門家などを中心にして、その暗号強度や安全性、ハードウエアやソフトウエアでの実装のしやすさや性能（速度）、計算に必要なハードウエアリソースや必要な電力、鍵長やブロック長などに対する柔軟性、知的財産的な評価（無償で利用できること）など、さまざまな視点から評価・検討された（選定過程については次の報告書参照）。

Report on the Development of the Advanced Encryption Standard (AES)［PDF］（NIST）

　そして最終的に2001年に「Rijndael（ラインダール）」という暗号化方式が選ばれた。開発者はベルギーの暗号学者、「Joan Daemen（ホァン・ダーメン）」と「Vincent Rijmen（フィンセント・ライメン）」であり、Rijndaelという名称は2人の名前から取られた（とされている）。

　DESと違って、Rijndaelは鍵長やブロック長が可変の共通鍵方式のブロック暗号である。提案されたRijndaelではいくつかの鍵長やブロック長が選べたが、最終的には次のようなパラメーターだけを使うことになり、これが正式なAES規格となった。


方式	鍵長	ブロック長
Rijndael	128／168／192／224／256bit	128／168／192／224／256bit
AES	128／192／256bit	128bit
RijndaelとAESの鍵長とブロック長の違い提案されたRijndaelのバリエーションのうち、実装の単純化や実用性などを考慮して、AESでは3種類の鍵長と1種類のブロック長のみを採用した。

　AESの仕様書はNISTのサイトで公開されている。

FIPS-197「Advanced Encryption Standard」［PDF］（NIST）

AESのアルゴリズム

　AESには鍵長に応じて「AES-128」「AES-192」「AES-256」の3種類のバリエーションがある。鍵長を長くすれば、それだけ安全性が増すと考えられるが、その分計算量が増えるのでどれを使うかはケースバイケースである。現在の所は、（推測しやすい鍵データを使ったりしない限り）AES-128でも十分と考えられている。


AES規格	鍵長	ブロック長	ラウンド数
AES-128	128bit	128bit	10段
AES-192	192bit	128bit	12段
AES-256	256bit	128bit	14段
AES規格のバリエーション AESには、ブロック長に応じて3種類のバリエーションがある。ラウンド数はAES内部における計算処理の繰り返し段数。詳細は後述。

　DESでは、入力されたデータを上下32bitずつに分け、それに対して16段の暗号化処理を繰り返し適用するという、「ファイステル構造」を使っていた。

　AESでも入力されたデータに対して同じような処理を何回か繰り返し適用するという仕組みになっているが、ファイステル構造ではなく「SPN構造（Substitution Permutation Network Structure）」という構成を取っている。SPN構造では、入力されたブロックの全ビットを対称に処理を行い、それを繰り返す。入力されたデータをいくつかのブロックに分けてbitデータの「置換（substitution）」を行い、それらをまとめてブロック全体へ「転置（permutation）」するので、こう呼ばれている。

　DESのようなファイステル構造では、例えばブロック内のビットデータを1ラウンドごとに半分ずつ処理するので計算に必要なリソースが少なくて済むが、十分な“攪拌（かくはん）”効果を得るためには段数が多くなってしまう。SPNではブロック全体を処理対象にするので、少ない段数（ラウンド数）でも効果が高い。

　AESの暗号化処理の概略は次の通りである。

AESアルゴリズムの擬似コード
前出のAESの仕様書より引用。state[ ] が入力データ（128bit）、w[ ] がラウンドキーのデータ、Nr がラウンド数（鍵長に応じて10／12／14）、Nbがブロックワード長（4）。入力されたデータに対して、SubBytes、ShiftRows、MixColumns、AddRoundKeyの処理を繰り返し適用している。

　SubBytes、ShiftRows、MixColumns、AddRoundKeyはそれぞれ置換、シフト、混合、XOR演算を行うためのAESの基本処理である。この一覧の処理をセットにして（これを1ラウンドとする）、入力されたデータに対して10～14回繰り返し適用する。

　AESではブロック長は128bitに固定なので、これらの処理は常に128bitずつを対象として行われる。鍵長は128／192／256bitのいずれかだが、これらを基にして128bitのラウンドキーデータを順次生成し、各ラウンドへ提供する。

　各ラウンドごとの処理は次の通りである。

1．入力データの分割
　入力された128bitのデータは8bitずつ16bytesに分けられる。

2．SubBytesによる置換
　分割されたバイトデータは、それぞれがSubBytesで置換される。SubBytesはDESのSボックスのようなものであり、8bitの入力から8bitの出力を得る、置換テーブルになっている。

3．ShiftRowsによるバイト位置の入れ替え
　SubBytesの出力は、ShiftRowsという処理によって、バイト単位で、位置の入れ替えを行う。これは線型変換になる。

4．MixColumnsによる演算
　各バイトごとにある演算（→ ガロア拡大体GF(2^8) による剰余演算。CPUやハードウエアで処理する場合は単なるビット演算になる）を行って、データを変換する。これは線型変換になる。

5．AddRoundKeyによる演算
　ラウンドキーデータ生成部で作ったデータとXOR演算を行う。

6．繰り返し処理
　鍵長に応じて、上の1．から5．の処理を10／12／14回繰り返す。

7．後処理
　最後にSubBytes、ShiftRows、AddRoundKeyを行って暗号結果とする。

　以上から分かるように、AESのアルゴリズムは比較的単純である。各ラウンドの処理内容は少し複雑に見えるかもしれないが、実際にはビットやバイト置換／演算、シフト演算、剰余演算などがメインであり、DESと大差ない。DESよりも大幅に暗号強度を強化しているのに、意外とアルゴリズムはシンプルであり、結果、計算に必要なリソースも少なくて済んでいる。それがRijndaelが選ばれた理由でもある。

AESの実装

　AESのアルゴリズムはハードウエアで実装するだけでなく、ソフトウエアで実装する場合にも効率がよくなるように、そして必要な計算リソース（ソフトウエアなら計算ステップ数、ハードウエアならゲート数）が少なくなるように決められている。暗号化技術は小型のデバイスやスマートカードなどでも利用されることを考えると、より少ないリソースで処理できるのは重要だからだ。

　DESではビット位置の入れ替えやSボックスによる変換、XOR演算などの処理を16段分繰り返しているが、そこではデータを4bitずつに分けて行う処理が多く使われていた。そのため、1byte（8bit）のデータと4bitのデータの相互変換やビット抜き出し、シフト処理などが多く必要になり、一般のCPUで処理する場合は少し効率が悪かった（通常のCPUはデータを8bit単位で扱うため）。これに対してAESでは、（CPUのアーキテクチャに応じて）8bitや16bit、32bitなどの単位でまとめて処理できるように設計されているし、繰り返し段数も少ないので、同じデータ長ならDESよりもAESの方が高速に処理できることが多い。

　AESをソフトウエアで実装した例は、例えばGitHubで「AES」を検索すると多数見つかる。

GitHubに登録されている「AES」プログラムの検索結果（GitHub）
AESのCプログラムの例（dhuertas氏のGitHubページ）

CPUによるAESのアシスト

　暗号化はコンピューターの重要な用途であるため、AESの計算をアシストするような機能を持っているCPUも多く作られている。例えばインテルのCPUでは、「AES-NI（AES New Instructions Set）」という名称で、AESの一部の演算処理を高速化する命令セットが用意されている。

「インテル AES New Instructions およびインテルセキュアキーによるインテルデータ・プロテクション・テクノロジー」（インテル）
AES-NI機能をサポートしているCPUの一覧（インテル）

　例えば「AESENC（Perform One Round of an AES Encryption Flow）」という命令を使うと、AESアルゴリズムのSubBytes／ShiftRows／MixColumns／AddRoundKeyという1ラウンドの処理を1命令で実行できる。つまりAESENCを10命令並べるだけで、AES-128の主要処理が完了する。

●AES-NIによる速度向上

・TIPS「Windows 8.1で Windowsエクスペリエンスインデックス値を計測する」

　AES-NIが利用可能なシステムにおけるAESの暗号化処理速度は、例えばWinSATコマンド（Windowsエクスペリエンスインデックスを算出するコマンド。関連記事参照）で測定できる。

※これはCore i7-4770S CPU（クロック3.10GHz、4コア8スレッド）上のWindows 8.1での測定例
C:\>winsat cpuformal ……WindowsエクスペリエンスインデックスのCPUスコアの測定コマンドを実行してみる
Windows システム評価ツール
> 実行中: 機能の列挙 ''
> 実行時間 00:00:00.00
> 実行中: メディアデコード/エンコードの評価結
……（中略）……
> CPU LZW 圧縮                      627.86 MB/s
> CPU AES256 暗号化                 3369.00 MB/s ……8コアでのAES-256の暗号化速度
> CPU Vista 圧縮                    1690.18 MB/s
> CPU SHA1 ハッシュ                 2105.24 MB/s
> ユニプロセッサ CPU LZW 圧縮       132.27 MB/s
> ユニプロセッサ CPU AES256 暗号化 504.20 MB/s ……シングルコアでの暗号化速度
> ユニプロセッサ CPU Vista 圧縮     345.16 MB/s
> ユニプロセッサ CPU SHA1 ハッシュ 575.51 MB/s
> Dshow ビデオエンコード時間       1.05267 s
> 合計実行時時間 00:01:09.64

C:\>

　これはAES-NIが有効なCPUでの測定例だが、5年ほど前の、AES-NIが未サポートのCPUで実行すると次のようになる。

※参考測定値。これはCore i7-950 CPU（クロック3.07Hz、4コア8スレッド）上での測定例
> CPU LZW 圧縮                      494.34 MB/s
> CPU AES256 暗号化                 241.18 MB/s ……8コアでの暗号化速度
> CPU Vista 圧縮                    1241.33 MB/s
> CPU SHA1 ハッシュ                 1514.21 MB/s
> ユニプロセッサ CPU LZW 圧縮       92.30 MB/s
> ユニプロセッサ CPU AES256 暗号化 53.24 MB/s ……1コアでの暗号化速度
> ユニプロセッサ CPU Vista 圧縮     227.06 MB/s
> ユニプロセッサ CPU SHA1 ハッシュ 386.39 MB/s
> Dshow ビデオエンコード時間       1.45472 s
> 合計実行時時間 00:01:11.15

　AES-256の暗号化速度は、新しいCPUの方が単純比較で10倍くらい速い。LZW圧縮やSHA1ハッシュの値からCPUの基本スカラー性能は3分の2程度と推測されるが、それを考慮してもAES-NIによる高速化の方が大きい（5倍程度速くなっている）。

AESの安全性

　ある暗号化アルゴリズムが安全かどうかは、それに対する攻撃法（解読方法）があるかどうかや、もしなければ、総当たり攻撃でどのくらいの計算量で解読できるか、などで評価される。

　AESの提唱後、さまざまな解読方法やアルゴリズム上の脆弱（ぜいじゃく）性などが研究されているが、いまのところ、誰でもすぐに実行できるような簡単な解読方法は発見されていない。ただし関連鍵攻撃（→WikiPediaのページ参照）やBiclique攻撃（次のリンク参照）のような、総当たり攻撃に必要な計算量をいくらか軽減させるような解読方法は研究されている。例えばAES-128に対してBiclique攻撃を使えば、2の128乗の計算量ではなく、2の126.1乗の計算量で済む、とされている。