ファイナンス、情報通信技術のスキル・アグリゲーション・サイト

情報セキュリティ・キーワード 2016 ⑤ 暗号技術編

クロード・エルウッド・シャノン（Claude Elwood Shannon）は、情報理論の考案者であり、アラン・チューリングやジョン・フォン・ノイマンらとともに今日のコンピュータ技術の基礎を作り上げた人物です。2016年4月30日は、シャノンの生誕 100 年となりました。

DES（Data Encryption Standard）は、広く使われてきた現代暗号のひとつで、暗号研究も活発です。その DES を中心に取り上げます。シャノンの理論が大きく関係しています。

１．暗号とは

１－１．暗号の用語
１－２．暗号化技術の要素
１－３．古典的暗号化アルゴリズム
１－４．暗号の安全性と強度
１－５．暗号の分類

２．慣用（対称鍵）暗号

２－１．シャノンの理論
２－２．ブロック暗号の構造
２－３．DES
２－４．DES のアルゴリズム
２－５．3DES
２－６．DES の操作モード
２－７．DES チャレンジ
２－８．AES
２－９．メッセージ認証コード

３．非対称鍵暗号方式

３ー１．Diffie-Hellman
３－２．RSA
３－３．ECC（楕円曲線暗号）

４．ハッシュ暗号
５．キーエスクロー
６．情報処理技術試験の過去問題

１．暗号とは

１－１．暗号の用語

平文（ひらぶん）は、プレーンテキスト（Plain Text）、クリアテキスト（ Clear Text ）など呼ばれます。暗号化の元となる文を指します。読み取った文そのままで認識が可能な状態です。

暗号化 （Encrypt、エンクリプト）は、平文を暗号文に変換することです。

暗号文 （Cipher Text、サイファーテキスト）は、平文を暗号化した文のことです。

復号（Decrypt、デクリプト）は、暗号文を元の平文に戻すことです。

１－２．暗号化技術の要素

暗号化アルゴリズム （Encryption Algorithm）は、平文を暗号化し、元の平文に復号する処理手順です。

鍵（Key、キー）は、同一の暗号化アルゴリズムを使用しても鍵を変えることで、同一の平文から異なる暗号文が生成されます。

１－３．古典的暗号化アルゴリズム

換字（かえじ、Substitution）は、別の文字や記号等に変換して暗号文を作成します。

転置（Permutation）は、文字を並べ替えて暗号文を作成します。

分置は、特定の位置に文章を分散させて埋め込みます。カルダングリル（Cardan grille）は、その鍵となる道具のことです。

１－４．暗号の安全性と強度

暗号解読 （Cryptanalysis）は、鍵を知らない第三者が暗号化された通信文を解読する技術です。

暗号の安全性については、暗号を解読する時間が、暗号文の情報が有効である期間より長いこと（計算量的安全性）がいわれます。

暗号の危殆化 （Compromise）は、コンピュータの性能が飛躍的に向上したり、暗号化アルゴリズムの効率的な解読手法が考案されたりすることにより、暗号アルゴリズムの安全性のレベルが低下した状況、または、その影響により暗号アルゴリズムが組み込まれているシステムなどの安全性が脅かされる状況をいいます。

暗号強度 （Cipher Strength）は、暗号を解読する困難さを表します。暗号アルゴリズムが複雑で、鍵の長さが長いほど、暗号強度は増し、解読が難しくなります。

１－５．暗号の分類

対称鍵暗号 （Symmetric key Encryption Scheme）は、暗号化（Encryption）と復号（Decryption）に同一の鍵を使う暗号方式です。慣用暗号方式（Conventional Encryptosystem）、共通鍵暗号方式（Common key Cryptosystem）、秘密鍵暗号方式（Secret Key Cryptosystem）とも呼ばれます。ブロック暗号やストリーム暗号は、この暗号方式です。

ブロック暗号 （block Cipher）は、固定長のデータに分割したブロック単位で処理する暗号です。

ストリーム暗号 （stream Cipher）ビット単位やバイト単位で処理を行う暗号です。

非対称鍵暗号方式 （Asymmetric Key Cryptosystem）は、対になる２つの鍵を使って暗号化・復号を行う暗号方式です。公開鍵暗号方式（Public Key Cryptosystem）とも呼ばれます。

ハッシュ暗号 は、ハッシュ関数を使用した暗号です。通常のハッシュ関数と比べて、暗号などの情報セキュリティの用途に適するような暗号数理的性質を持つハッシュ関数が使用されます。

２．慣用（対称鍵）暗号

２－１．シャノンの理論

情報理論は、クロード・エルウッド・シャノン（Claude Elwood Shannon）の論文 "A Mathematical Theory of Communication"（通信の数学的理論、1948年）が始まりとされます。また、暗号の理論的研究についても、"Communication Theory of Secrecy Systems"（秘匿系の通信理論、1949年）の論文が始まりとされます。

合成暗号 （Product Cipher）は、換字（Substitution）、転置（Permutation）、剰余加算、剰余積算、リニア（Linear、線形な）変換など、いくつかの弱い操作を繰り返して構成するブロック暗号のひとつです。

ラウンド （Round）は、暗号化、復号を繰り返して、暗号の強度（解読の困難さ）を増します。

SPN （Substitution-Permutation Network）は、換字（Substitution）と転置（Permutation）を繰り返す、暗号化アルゴリズムを実装する際の構造のひとつです。

拡散（Diffusion）は、暗号文に平文の統計的な特徴（特定の文字や単語の出現率など）を反映させないようにします。

かく乱 （Confusion）は、暗号文と鍵の数学的な関係を可能な限り複雑にします。

２－２．ブロック暗号の構造

ブロック暗号は、データスクランブル部（スクランブラ）と、鍵スケジュール部（鍵スケジューラ）の２つを主な要素とします。そのうち、データスクランブル部は、Product Cipher になっている場合が多くあります。

Feistel 構造 （Feistel Structure）は、入力されたブロックデータを左右２個のサブブロックに分けます。片方のサブブロックに鍵の値を混ぜ込んだ後、変換を行い、他方のサブブロックに XOR 処理によって重ね合わせます。処理後は、左右のサブブロックを置き換えて同じように処理を繰り返します。 DES は、Feistel 構造を持ちます。

SPN 構造 （Substitution Permutation Network）は、換字（Substitution）と転置（Permutation）の構成が繰り返し適用されます。AES がこの構造を採用しています。 Feistel 構造である DES も Feistel（F）関数内部は SPN 構造です。

２－３．DES

DES （Data Encryption Standard）は、慣用暗号（対称鍵暗号）のブロック暗号です。鍵の長さは 56 ビット（ 7 バイト）で、データブロック長は 64 ビット（ 8 バイト）です。

1973年5月15日に NBS（National Bureau of Standards、米国商務省標準局）が公募し、IBM が提出した Feistel 暗号（ LUCIFER の改良版）が採用され、1977年1月15日に公表されました。

ファイステルが IBM で研究開発した Feistel（ファイステル）暗号の製品名が LUCIFER（ルシファー）。

現在は、FIFS（Federal Information Processing Standerd、連邦情報処理標準）46-3 が作成され、DES および 3DES の標準文書となっています。

２－４．DES のアルゴリズム

DES のアルゴリズムの詳細と例は、「Data Encryption Standard - Wikipedia」、「マスターIT／暗号技術：第2回　DES暗号化 - ＠IT」を参照し、引用しています。

入力された 64bit のデータに対して「初期転置」を行い、「ラウンド処理」の入力とします。そして、ラウンド処理の出力の上位 32bit と下位 32bit を入れ替えて結合し、最後に「最終転置」を行います。最終転置は初期転置のちょうど逆変換になっています。

転置は、入力されたビット位置を別の場所へ移動させる（入れ替える）ビット操作です。例えば「初期転置」では、第1bit を第40bit の位置へ、第2bit を第8bit の位置へそれぞれ移動させる、といった処理を行います。

DES の ラウンド処理 は、入力された 64bit のデータを 32bit ずつに分けます。下位 32bit（R）は「暗号化関数」の入力となります。そして、上位 32bit（L）は暗号化関数の出力と XOR 演算し、上下を入れ替えて次段へと回します。16 回分の処理が終わると、それが出力となります。

XOR（排他的論理和）は、0 xor 0 = 0、0 xor 1 = 1、1 xor 0 = 1、1 xor 1 = 0 となるビット演算です。

DES の 暗号化関数 Feistel（F）関数は、入力された 32bit のデータは、48bit に「拡大転置」します（Expansion）。その後、「鍵スケジュール」で生成した 48bit のラウンド鍵と XOR 演算します（Key Mixing）。それを 6bit の 8 グループに分け、このグループごとに「Sボックス」で、それぞれ 4bit に変換します（Substitution）。そして、4bit の 8 グループを 32bit のデータに結合し、このデータを転値します（Permutation）。これを出力とします。

拡大転置 （Expansion Permutation）は、32bit から 6bit ずつ取り出して 8 つのグループを作ります。一部の bit は重複して利用されます。

S ボックス （Substitution Box）は、bit データの「変換」を行います。6bit の入力から 4bit を取り出す S ボックスが 8 つ定義されており、それぞれ異なるパターンでデータを変更しています。

例えば、S1 ボックスは、暗号化関数への入力 32bit のデータのうち、「bit 32」「bit 1」「bit 2」「bit 3」「bit 4」「bit 5」の 6bit 分のデータが入力されています。S ボックス内では、入力された 6bit のうち、両側の 2bit でルックアップテーブルの行を選択し、真ん中の 4bit でルックアップテーブルの列を選択します。例えば入力された 6bit のデータが「110010」なら、「2（2進数の10）」の行と「9（2進数の1001）」の列を選択して、テーブルの交点にあるデータを出力とします。

鍵スケジュール は、ラウンド鍵を生成するアルゴリズムです。

まず、パリティを含む 64bit の入力から 56bit を選択して並べ替えます（Permuted Choice 1）。その 56bit は 2 つの 28bit に分割して別々に処理します。ラウンドを次に進める際に、それぞれを左に 1 ビットか 2 ビットローテートします（ラウンドによってローテートするビット数が異なります）。そして、それぞれの 28bit から 24bit ずつ選択して別々に並べ替えて、48bit のラウンド鍵を出力します（Permuted Choice 2）。

ローテート は、ビットを左または右にシフトし、あふれたビットを末尾に回すビット操作です。

２－５．3DES

DES で使用する鍵を３回使う方法を 3DES、Triple DES、DES3 と呼びます。

・ EDE 方式（異なる鍵で、データを Encrypt → Decrypt → Encrypt の順で暗号化します。）

・ EEE 方式（異なる鍵で、データを Encrypt → Encrypt → Encrypt の順で暗号化します。）

56 ビット鍵を３個使う場合、鍵の長さは 168 ビットになります。EDE 方式では鍵を２個使う方法が一般的です。その場合は１回目と３回目に同じ鍵を使います。

２－６．DES の操作モード

FIPS 81 では４つのデータ操作モード（Block cipher modes of operation）を定義しました。

・ ECB（Electronic Code Block）は、メッセージはブロックに分割され、それぞれのブロックは独立して暗号化されます。

・CBC（Cipher Block Chaining）は、平文の各ブロックは前の暗号文との XOR を取ってから暗号化されます。最初のブロックの暗号化には初期化ベクトルが用いられます。

初回、最初の平文ブロック→IVとXOR→暗号化→暗号文。

次回以降、次の平文ブロック→前回の暗号文とXOR→暗号化→暗号文。

・ CFB（Cipher Feedback）は、初期化ベクトルを暗号化し、これと平文ブロックの XOR を取ることで暗号文を得ます。さらに、この暗号文を次の暗号化の入力にフィードバックし、かつ、これと次の平文ブロックの XOR を取ることで暗号文を得ます。

初回、IV→暗号化→最初の平文ブロックとXOR→暗号文。

次回以降、前回の暗号文→暗号化→次の平文ブロックとXOR→暗号文。

・ OFB（Output Feedback）は、初期化ベクトルを暗号化した結果を次の暗号化の入力にフィードバックし、かつ、これと平文ブロックのXORを取ることで暗号文を得ます。

初回、IV→暗号化→最初の平文ブロックとXOR→暗号文。

次回以降、前回のIVの暗号化の結果→暗号化→次の平文ブロックとXOR→暗号文。

初期ベクトル （IV、initialization vector）は、最初の平文ブロックとXORをとるとき使用される値です。

２－７．DES チャレンジ

RSA データセキュリティ社は、DES の 56 ビット長の鍵の安全性が問題であることを示すため、DES の暗号解読コンテストを開催し、解読に成功しています。1997年より毎年実施。

２－８．AES

DES が短時間で解読される可能性が高まり、より強固な標準暗号を NIST（アメリカ国立標準技術研究所）が AES （Advanced Encryption Standard）と名付けて 1997年9月に公募しました。

2000年10月に NIST は Rijndael（ラインダール）を選定し、AES の規格は、2001年3月に FIPS PUB 197 で公表されました。

AES は、SPN 構造のブロック暗号で、ブロック長は 128 ビット、鍵長は 128 ビット・ 192 ビット・ 256 ビットの３つが利用できます。鍵長によって変換のラウンド数が異なります。

鍵長 128 ビットのとき、ラウンド数は 10 回。

鍵長 192 ビットのとき、ラウンド数は 12 回。

鍵長 256 ビットのとき、ラウンド数は 14 回。

２－９．メッセージ認証コード

メッセージ認証コード （MAC、Message Authentication Code）は、慣用（対称鍵）暗号を使用する認証コードです。

「メッセージは正しい送信者から送られてきたこと」、「メッセージは改竄されていないこと」の確認に使用されます。なお、ハッシュ暗号も同様の確認に使用されます。

DES-MAC は、CBC 処理モードで動作します。

３．非対称鍵暗号方式

３ー１．Diffie-Hellman

Diffie-Hellman （ディフィー-ヘルマン）は、ネットワーク上で共有鍵を安全に交換するためのアルゴリズムです。

Diffie-Hellman アルゴリズムは、離散対数の計算が極めて困難であり、大きな素数を使った場合の離散対数計算が限りなく不可能に近いという特性を利用しています。

素数 p とその素数 p の原子根（primitive root）となる整数 a、原子根 a を累乗する整数 i（ i は 1 から p-1 の間の整数）、a の i 乗を p で割った答えの余り（剰余）の値 b を使います。

通信を行う L と M は、極めて大きな値の素数 p と原子根 a を共有しておきます。それぞれ乱数で生成した整数 r と s を秘密鍵とします。原子根 a を r と s でそれぞれ累乗し、p で剰余計算し、それぞれの剰余 b と c を求め、それらを公開鍵とします。

例えば、素数 p=7、原子根 a=5、整数 r=4、s=5、とすると、b=2、c=3、共有鍵 k=4 となります。

L の公開鍵 2 = 5⁴ mod 7

M の公開鍵 3 = 5⁵ mod 7

公開鍵 2 と 3 を交換します。

L の共有鍵 4 = 3⁴ mod 7

M の共有鍵 4 = 2⁵ mod 7

３－２．RSA

発明者であるロナルド・リベスト（Ron Rivest）、アディ・シャミア（Adi Shamir）、レオナルド・エーデルマン（Len Adleman）の頭文字をとって Rivest-Shamia-Adleman（RSA）方式と呼ばれます。

Diffie-Hellman と同様に素数の離散対数計算の困難性を使用します。通信データの暗号化、署名、鍵交換などに使用されます。

３－３．ECC（楕円曲線暗号）

ECC （Elliptic Curve Cryptography）は、楕円曲線上の離散対数計算の困難性を使用します。通信データの暗号化、署名、鍵交換などに使用されます。1024 ビットの鍵を使用する RSA 方式と同程度の安全性を 160 ビットの鍵を使用する ECC で実現し、短い鍵のため処理が高速です。

４．ハッシュ暗号

ハッシュ暗号 は、暗号数理的性質を持つハッシュ関数を使用した暗号で、元の平文に戻せない性質（不可逆性）があります。ハッシュ関数は、メッセージからメッセージダイジェスト（Message Digest）を生成します。単にダイジェスト（Digest）とも呼ばれます。メッセージへの改ざんの有無の確認に使用します。

衝突困難性 （Collision Resistance）は、２つの異なる入力値からは、同じハッシュ値となる可能性が低いという性質です。

MD4 （Message Digest Algorithm 4）は、128 ビットのハッシュ値を出力します。

MD5 （Message Digest Algorithm 5）は、前身である MD4 の安全性を向上させたものです。128 ビットのハッシュ値を出力します。

SHA-1 （Secure Hash Algorithm 1）は、160 ビットのダイジェストを作成します。SHA-1 のアルゴリズムは MD4 を元にし、さまざまなセキュリティのアプリケーションやプロトコルに採用されています。なお、SHA-1 ハッシュ関数の危殆化により、SHA-2 への移行が進められています。

SHA-2 （Secure Hash Algorithm 2）は、SHA-1 に多くの改良が加えられています。224、256、384、512 ビットのいずれかのダイジェストを作成します。

HMAC （Hash-based Message Authentication Code）は、ハッシュ関数と慣用（対称鍵）暗号の鍵を使用してメッセージダイジェストを生成します。