暗号まわりのお勉強3～共通鍵暗号方式のブロック暗号～

ブロック暗号

方式

ブロック暗号は平文を固定長の長さに分割し、それぞれのブロックに対してある関数を用いて暗号化や復号を行います。

暗号化に用いる関数をE、復号に用いる関数をDとすると、DはEの逆関数の関係にあります。

D=E⁻¹

暗号化の際は、平文ブロックMを、鍵をKとする暗号関数EKを用いて処理を行うことで、暗号文Cを作成することができます。

EK(M) = C

復号の際は、暗号文Cを、鍵をKとする復号関数DKを用いて処理を行うことで、平文ブロックMを復元することができます。

DK(C) = EK⁻¹{EK(M)} = M

ストリーム暗号と比べたときのメリットとデメリット

構成法

ブロック暗号はいくつかの構成法があります。

Feistel構造

平文ブロックを2分割（それぞれL、Rとする）し、左右交互にデータ撹拌を繰り返す形式です。ラウンド関数Fと副鍵K（共通鍵から生成する暗号化に使うための複数の鍵）を用いて、暗号化と復号は次のようになります。

暗号化の場合...

Rn+1=Ln⊕F(Rn, Kn), Ln+1=Rn

復号の場合...

Ln=Rn+1⊕F(Ln+1,Kn), Rn=Ln+1

数式だけでは少々分かりにくいので、暗号化について数式を追って見てみましょう。初期の入力をL0、R0すると、これらはどのように暗号化されていくのでしょうか。

1ラウンド目は、R1=L0⊕F(R0, K0), L1=R0となります。

左の式について見てみると、この段階でL0が排他的論理和を取ることによって暗号化されていることが分かります。一方で右の式を見てみると、R0は次の入力値となっており、まだ暗号化されていません。

2ラウンド目は、R2=L1⊕F(R1, K1), L2=R1となります。

ここで左の式をもう一段回分解してみると、R2=L1⊕F(R1, K1)=R0⊕F(R1, K1)となり、R0も暗号化されることが分かります。右の式のR1は1ラウンド目でL0を暗号化したデータです。従って、この2ステップでひとまず初期入力L0、R0の暗号化ができていることが分かります。

Feistel構造のメリットとしては、暗号化と復号でロジックが共通している点が挙げられます。暗号化に使ったのと逆の順序で副鍵を使うことで簡単に復号ができるという点や、逆関数を計算する必要がないため使用できるラウンド関数の選択肢が多いことにつながります。また、ブロックを2つに分割するという性質上、扱うデータ領域が少なくて済む点もメリットと言えるでしょう。

一方、デメリットとしては1ラウンドで暗号化できるのは片方のみであるので、必然的に暗号化に必要な計算処理が多くなるという点が挙げられます。

Feistel構造は暗号学者Horst Feistel氏にちなんだ名称です。

SPN構造

SPNはSubstitution Permutation Networkの略称です。その名の通り、Sbox（Substitution box）と呼ばれる非線形置換と、複数のSboxからの出力を入力とする転置処理（Permutation）からなります。

Sboxは、平文と暗号文の相関関係を破壊するためのもので、多くの場合はルックアップテーブル参照によって実現されます。このテーブルは、入力バイトm、出力バイトnであるとき（mバイトの入力をnバイトの出力に置換するとき）、2のm乗のテーブルを必要とします。

以下にSPN構造を使用しているDESとAESについて簡単に見てみます。

DESは6ビット入力、4ビット出力で、入力値を中間4ビットとMSBLSB（最上位ビットと最下位ビットをつなげたもの）に分けて、4行16列（＝64＝2の6乗）のテーブルを8つ使用します。以下はそのうちの1つのテーブルにあたるS1です。行列は2進数表記、表の値は16進数表記にします。

AESは8ビット入力、8ビット出力で、入力値を下位4ビットと上位4ビットに分けて16行16列（＝256＝2の8乗）のテーブルを1つ使用します。以下はそのテーブル（Rijndael S-box）です。行列、表の値ともに16進数で表記します。

SPN構造のメリットとしては、平文ブロックの分割を行わないことが挙げられます。これにより、1ラウンドでブロック全体を撹拌でき、少ないデータ撹拌数でFeistel構造と同等の強度の暗号化を行うことができます。

一方、デメリットとしては、暗号化と復号のロジックが異なることから、逆関数を計算できる（すなわち、全単射の）関数でなければならず、関数の選択幅が狭いことが挙げられます。

暗号利用モード

暗号利用モードは、ブロック暗号を利用して、既定のブロック長よりも長いブロック長でも暗号化可能にするための方法を指します。

今回は有名な5つのモードを紹介しますが、中でもCBCモードとCTRモードは

以降では、特に断りがない限り、次の記号を利用します。

• 暗号関数・・・Ekと表記します。
• 復号関数・・・Dkと表記します。
• n番目の平文・・・Mnと表記します。
• n番目の暗号文・・・Cnと表記します。
• 初期ベクトル・・・IVと表記します。
• n番目の鍵ストリーム・・・Znと表記します。
• n番目のカウンタ・・・CNTnと表記します。

ECBモード(electronic codebook mode, 電子符号表モード)

次のように暗号化・復号を行う形式です。

暗号化の場合...

Cn=Ek(Mn)

復号の場合...

Mn=Dk(Cn)

最後の平文ブロックがブロック長に満たない場合はパディングという詰め物をしてブロック長に合わせたのち、暗号化を行います。

ビット単位のエラーがある暗号文を復号した場合、平文におけるエラーの範囲は、対応するブロックとなります。

シンプルで暗号化・復号ともに並列処理ができる点がメリットですが、同じ平文から同じ暗号文が作られてしまう、攻撃者が暗号文ブロックを操作可能であるなど、脆弱で使用は推奨されません。

ECBモードに対する主な攻撃手法として、リプレイアタック（replay attack, 再生攻撃, 反射攻撃）があります。

★CBCモード(cipher block chaining mode, 暗号ブロック連鎖モード)

次のように暗号化・復号を行う形式です。

暗号化の場合...

Cn=Ek(Cn-1⊕Mn), ただし、C0=IV

復号の場合...

Mn=Dk(Cn)⊕Cn-1, ただし、C0=IV

後述するCTRモードと合わせて最もよく利用される暗号利用モードです。

ECBモードと同様にブロック長に満たない場合はパディングという詰め物を施してから処理を行う必要があります。その方式から、Mnの暗号文ブロックにあたるCnは、それより前の全ての平文ブロックM1～Mn-1に依存します。従って、暗号化においては並列処理はできません。

一方、復号においては、復号したい暗号文ブロックとその1つ前の暗号文ブロックのみを利用することから、並列処理が可能です。

ただし、一番最初の暗号化においてはC1=Ek(IV⊕M1)であるため、初期化ベクトルを定数にしてしまうと、M1が同一であるような暗号文では同じC1が発生してしまい、脆弱となってしまいます。このことから、IVは都度変更することが求められます。（※CBCモードに限らず、IVやnonceを利用する場合は、値を固定せず都度変更するのが通常の運用です。）

ビット単位のエラーがある暗号文を復号した場合、平文におけるエラーの範囲は、対応するブロック全体と次のブロックの対応するビットとなります。

CBCモードに対する攻撃手法として、リプレイアタックがあります。

CFBモード(cipher-feedback mode, 暗号フィードバックモード)

次のように暗号化・復号を行う形式です。

暗号化の場合...

Cn=Ek(Cn-1)⊕Mn, ただし、C0=IV

復号の場合...

Mn=Ek(Cn-1)⊕Cn, ただし、C0=IV

Mnの暗号文ブロックにあたるCnは、それより前の全ての平文ブロックM1～Mn-1に依存します。従って、暗号化においては並列処理はできません。

一方、復号においては、復号したい暗号文ブロックとその1つ前の暗号文ブロックのみを利用することから、並列処理が可能です。また復号の際にも暗号化と同一の関数Ekを利用しており実装コストを下げられる点、パディング処理を必要としない点は特徴と言えます。

さらに、暗号化の式を見て分かる通り、暗号化関数に通すのは直前の暗号文ブロックだけであり平文が直接暗号化されるわけではありません（Mに対して何らの直接的な処理は加えられていません）。このことからストリーム暗号として利用することもできます。

ビット単位のエラーがある暗号文を復号した場合、平文におけるエラーの範囲は、対応するブロック全体と次のブロックの対応するビットとなります。

CFBモードに対する攻撃手法としてリプレイアタックがあります。

OFBモード(output-feedback mode, 出力フィードバックモード)

次のように暗号化・復号を行う形式です。

暗号化の場合...

Cn=Mn⊕Zn, ただし、Zn=Ek(Zn-1), Z0=IV

復号の場合...

Pn=Cn⊕Zn, ただし、Zn=Ek(Zn-1), Z0=IV

暗号化の形式を見て分かる通り、暗号化関数に通すのは直前の暗号文ブロックだけであることから平文が直接暗号化されるわけではなく、復号の際にも暗号化と同一の関数Ekを利用しており実装コストを下げられる点は特徴と言えます。また、パディング処理を必要としません。これらはCFBモードと同様の特徴です。

さらに、暗号化の形式を見て分かる通り、暗号化関数に通すのは直前の暗号文ブロックだけであり平文が直接暗号化されるわけではありません。このことからストリーム暗号として利用することもできます。

ただし、暗号化・復号のどちらについても並列処理はできない点はCFBモードと異なります（※）。

OFBモードにおける暗号化関数Ekはランダム関数であるため、IVは定数でないものであれば（例えば1ずつインクリメントするカウンタのような簡易なものであっても）脆弱とはなりません。

暗号化と復号の事前計算をしておくことが可能ですが、一方で事前計算結果が漏洩すると平文を全て解読されてしまう、IVが変化すると全ての暗号文ブロックの復号に失敗するという諸刃の剣でもあります。

ビット単位のエラーがある暗号文を復号した場合、平文におけるエラーの範囲は、対応するビットのみに留まります。

※並列処理できない...の厳密な解釈について。

OFBモードでは、暗号化・復号のどちらにおいても平文ではなくIVまたはIVをもとにした直前の鍵ストリームのみを暗号化関数の変数として取るため、事前計算可能です。しかし、こちらはそれ以前の操作に依存することから並列処理はできません。一方、鍵ストリームと平文または暗号文の排他的論理和を取って暗号文または平文を求める操作は独立しています。従って、予め鍵ストリームを作成する処理をしておくことで、最後に排他的論理和をとる処理自体は並列して行うことが可能です。

★CTRモード(counter mode, カウンタモード)

次のように暗号化・復号を行う形式です。

暗号化の場合...

Cn=Ek(CNTn)⊕Mn, ただし、CNTn=CNTn-1+1, CNT0=0

復号の場合...

Mn=Ek(CNTn)⊕Cn, ただし、CNTn=CNTn-1+1, CNT0=0

CBCモードと合わせて最もよく利用される暗号利用モードです。

暗号化・復号共に隣接するブロック間で依存性がないので、並列処理をすることができます。合わせて、暗号化・復号のどちらにおいても平文ではなくカウンタを暗号化関数の変数として取るため事前計算可能です。また、暗号化・復号共に同一の関数Ekを利用しており実装コストを下げられます。さらに、パディングも必要としません。

ビット単位のエラーがある暗号文を復号した場合、平文におけるエラーの範囲は、対応するビットのみに留まります。

さらに、暗号化の形式を見て分かる通り、暗号化関数に通すのは直前の暗号文ブロックだけであり平文が直接暗号化されるわけではありません。このことからストリーム暗号として利用することもできます。

なお、上記の式でCNTn=CNTn-1+1, CNT0=0としていますが、これは一般的な例であり、単調増加で値が重ならないものであれば使用可能です。また、実際のCNTnは、ナンス（Nonce, ノンス）と呼ばれるその暗号化の時のみ利用される使い捨てのランダムな値とカウンタの役割を果たす何らかの値とを連結、加算、または排他的論理和をとることによって組み合わせたものを用います。

ブロック暗号のアルゴリズム

ブロック暗号のアルゴリズムには、AESやDESなどがあります。