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

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

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

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

1.暗号とは

1-1.暗号の用語

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

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

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

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

1-2.暗号化技術の要素

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

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

1-3.古典的暗号化アルゴリズム

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

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

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

1-4.暗号の安全性と強度

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

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

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

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

1-5.暗号の分類

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

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

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

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

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

2.慣用(対称鍵)暗号

2-1.シャノンの理論

情報理論は、クロード・エルウッド・シャノン(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)は、暗号文と鍵の数学的な関係を可能な限り複雑にします。

2-2.ブロック暗号の構造

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

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

 

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

2-3.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 の標準文書となっています。

2-4.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)。

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

2-5.3DES

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

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

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

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

2-6.DES の操作モード

FIPS 81 では4つのデータ操作モード(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をとるとき使用される値です。

2-7.DES チャレンジ

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

2-8.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 ビットの3つが利用できます。鍵長によって変換のラウンド数が異なります。

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

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

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

2-9.メッセージ認証コード

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

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

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

3.非対称鍵暗号方式

3ー1.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 = 54 mod 7

M の公開鍵 3 = 55 mod 7

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

L の共有鍵 4 = 34 mod 7

M の共有鍵 4 = 25 mod 7

3-2.RSA

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

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

3-3.ECC(楕円曲線暗号)

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

4.ハッシュ暗号

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

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

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)は、ハッシュ関数と慣用(対称鍵)暗号の鍵を使用してメッセージダイジェストを生成します。

5.キーエスクロー

キーエスクロー (key escrow)は、暗号化したデータの復号鍵をデータの受取人のほかに第三者にも預ける(供託する)ため、一方が復号鍵を紛失しても復号が可能となります。

6.情報処理技術試験の過去問題

試験問題の全文は、https://www.jitec.ipa.go.jp/1_04hanni_sukiru/_index_mondai.html をご覧ください。


平成23年度特別SC試験午前Ⅱ問題 問 1
平成27年度秋期SC試験午前Ⅱ問題
問 1 AES の暗号化方式を説明したものはどれか。

  • ア 鍵長によって, 段数が決まる。
  • イ 段数は, 6 回以内の範囲で選択できる。
  • ウ データの暗号化, 復号, 暗号化の順に 3 回繰り返す。
  • エ 同ーの公開を用いて暗号化を 3 回繰り返す。

正解 ア


平成27年度秋期共通試験午前Ⅰ問題
問12 公開鍵暗号方式の暗号アルゴリズムはどれか。

  • ア AES
  • イ KCipher-2
  • ウ RSA
  • エ SHA-256

正解 ウ


平成26年度秋期SC試験午前Ⅱ問題
問 2 ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち, 適切なものはどれか。

  • ア SHA-256 の衝突発見困難性を示す, ハッシュ値が一致する二つのメッセージの探索に要する最大の計算は, 256 の 2 乗である。
  • イ SHA-256 の衝突発見困難性を示す, ハッシュ値の元のメッセージの探索に要する最大の計算量は, 2 の 256 乗である。
  • ウ ハッシュ値が与えられたときに, 元のメッセージの探索に要する計算量の大きさによる, 探索の困難性のことである。
  • エ ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる, 探索の困難性のことである。

正解 エ


平成22年度春期SC試験午前Ⅱ問題 問 5
平成23年度秋期SC試験午前Ⅱ問題 問 6
平成25年度秋期SC試験午前Ⅱ問題
問 3 共通鍵暗号方式で, 100 人の送受信者のそれぞれが, 相互に暗号化通信を行うときに必要な共通鍵の総数は幾つか。

  • ア 200
  • イ 4,950
  • ウ 9,900
  • エ 10,000

正解 イ


平成22年度秋期共通試験午前Ⅰ問題 問14
平成25年度春期共通試験午前Ⅰ問題
問13 公開鍵暗号を使って n 人が相互に通信する場合, 全体で何個の異なる鍵が必要になるか。ここで, 一組の公開鍵と秘密鍵は 2 個と数える。

  • ア n+1
  • イ 2n
  • n(n-1)
    2
  • エ log2n

正解 イ


平成22年度秋期SC試験午前Ⅱ問題
平成24年度秋期共通試験午前Ⅰ問題
問14 暗号方式に関する記述のうち, 適切なものはどれか。

  • ア AES は公開鍵暗号方式, RSAは共通鍵暗号方式の一種である。
  • イ 共通鍵暗号方式では, 暗号化及び復号に使用する鍵が同ーである。
  • ウ 公開鍵暗号方式を通信内容の秘匿に使用する場合は, 暗号化に使用する鍵を秘密にして, 復号に使用する鍵を公開する。
  • エ ディジタル署名に公開鍵暗号方式が使用されることはなく, 共通鍵暗号方式が使用される。

正解 イ


平成22年度秋期SC試験午前Ⅱ問題 問 4
平成24年度春期SC試験午前Ⅱ問題
問 4 米国 NIST が制定した, AES における鍵長の条件はどれか。

  • ア 128 ビッ卜, 192 ビッ卜, 256 ビッ卜から選択する。
  • イ 256 ビット未満で任意に指定する。
  • ウ 暗号化処理単位のブロック長より 32 ビッ卜長くする。
  • エ 暗号化処理単位のブロック長より 32 ビッ卜短くする。

正解 ア


平成24年度秋期共通試験午前Ⅰ問題
問14 ディジタル署名などに用いるハッシュ関数の特徴はどれか。

  • ア 同じメッセージダイジェストを出力する異なる二つのメッセージが, 容易に求められる。
  • イ メッセージが異なっていても, メッセージダイジェストは同じである。
  • ウ メッセージダイジェストからメッセ一ジを復元することは困難である。
  • エ メッセージダイジェストの長さはメッセージの長さによって異なる。

正解 ウ


平成22年度春期SC試験午前Ⅱ問題 問 1
平成23年度秋期SC試験午前Ⅱ問題
問 2 セキュアハッシュ関数 SHA-256 を用いて, 32 ビット, 256 ビット, 2,048 ビットの三つの長さのメッセージからハッシュ値を求めたとき, それぞれのメッセージのハッシュ値の長さはどれか。

メッセージの長さ 単位 ビット

322562,048
32256256
322562,048
256256256
2562562,048

正解 ウ


平成23年度特別SC試験午前Ⅱ問題
問 4 暗号アルゴリズムの危殆化を説明したものはどれか。

  • ア 外国の輸出規制によって十分な強度をもつ暗号アルゴリズムを実装した製品が利用できなくなること
  • イ 鍵の不適切な管理によって, 鍵が漏えいする危険性が増すこと
  • ウ 計算能力の向上などによって, 鍵の推定が可能となり, 暗号の安全性が低下すること
  • エ 最高性能のコンピュータを用い, 膨大な時聞やコストを掛けて暗号強度をより確実なものとすること

正解 ウ

⑤暗号技術編を公開しました。

《アーカイブ》 情報セキュリティ試験直前対策メモ2006

第1回 無線LAN編

第2回 VPN編

第3回 暗号化編

(≪補足≫ 暗号・復号の基本フロー

第4回 認証編

第5回 PKI編

第6回 セキュリティプロトコル編

第7回 サーバセキュリティ編

第8回 脅威の実態編

第9回 アクセス監視編

最終回 規格編

『人間がつながったことが、インターネットのいちばん大きな意義だ。 … あきらめなくなくてもすむ社会にしたい。 … その足場の台が、インターネットの役割だ。』(序章より)

角川インターネット講座1 インターネットの基礎 情報革命を支えるインフラストラクチャー (角川学芸出版全集) amazon.co.jp Kindle本

『インターネットの文化として、実際に動くものを重視するというプラグマティズム(実用主義)の徹底がある。 … インターネットはソフトウェアで動いており、その多くの部分がオープンソースだから …』(序章より)

角川インターネット講座2 ネットを支えるオープンソース ソフトウェアの進化 (角川学芸出版全集) amazon.co.jp Kindle本

新スマホがぞくぞく登場!ラインアップ充実。

auネットワークで月々980円(税抜)~!【UQ mobile】

お名前.comのVPS

お名前.comの高性能VPS

現役エンジニアからオンライン上でマンツーマンでレッスンが受けられます。

オンラインプログラミング研修のCodeCamp

受講生に1人ずつ現役のプロのパーソナルメンターがつきます。

未経験からプロのエンジニアを育てるオンラインブートキャンプ

無料で使えるSSL証明書「Let's Encrypt」にも対応!

格安SSL証明書サービス、SSLボックス