暗号技術入門12 乱数

担当:谷

目次

  • 乱数の性質
    • 無作為性
    • 予測不可能性
    • 再現不可能性
  • 疑似乱数生成器
    • 線形合同法
    • 一方向性ハッシュ
    • 暗号
    • ANSI X9.17
  • 乱数に対する攻撃
    • 種に対する攻撃
    • ランダムプールに対する攻撃

乱数

乱数列

  • ランダムな数列のこと
  • 数学的に述べれば、今得られている数列 x1, x2, …, xn から次の数列の値 xn+1 が予測できない数列
  • 乱数列の各要素を乱数という

乱数の性質

【弱い疑似乱数】無作為性(randomness):暗号技術として使用不可

  • 統計的な偏りがなく,でたらめな数列になっている性質
  • 攻撃者に「見破られないこと」が重要なため,暗号技術として使用するのは不向き(例:線形合同法)
  • 通常のコンピュータゲームで使用する乱数は無作為性を満たしていれば十分
    • 乱数の検定
      • 疑似乱数列が無作為であるかどうかを調べる方法
      • たくさんの種類がある

【強い疑似乱数】予測不可能性(unpredictability):暗号技術として使用可

過去の数列から次の数を予測できないという性質

【真の乱数】再現不可能性:暗号技術として使用可

  • 同じ数列を再現できないといった性質
  • 再現するためには数列そのものを保持しておく必要あり

乱数の性質 – 予測不可能性 –

  • 疑似乱数生成器のアルゴリズムは攻撃者が知っている
  • 疑似乱数の種(疑似乱数を生成するための初期値)は攻撃者に秘密

上記の2つを満たす場合,たとえ過去の疑似乱数列を攻撃者に知られても,次に出力する疑似乱数は予測不可能

予測不可能性を持つ疑似乱数生成器を作る方法
→「一方向性ハッシュ関数の一方向性」や「暗号の機密性」などの他の暗号技術を用いて,疑似乱数生成器の予測不可能性を確保する

乱数の性質 – 再現不可能性 –

  • ある乱数列と同じ数列を再現することができない性質
  • ある乱数列を再現するためには,ある乱数列そのものを保存しておく以外方法がない場合に,ある乱数列は再現不可能性を持つといえる

ソフトウェアだけでは再現不可能性乱数列を作成することは不可能!

  • ソフトウェアを支えているコンピュータが有限の内部状態しか持たないため
  • ソフトウェアは同じ内部状態から必ず同じ乱数を生成するため,いつか繰り返しになる.
  • ソフトウェアが生成する乱数は常に有限の周期をもつため,再現不可能性とは言えない.
    • 周期
      • 繰り返しに陥るまでの数列の長さ

再現不可能性をもつ乱数の身近な例

公開鍵生成時に使用したツール「PuttyGen」の鍵生成時に行った,ゲージ100%になるまでマウスぐるぐる

再現不可能性を持つ乱数列

  • マウスぐるぐる
  • キーボードを打つ時の時間間隔
  • 放射線観測機からの出力
    上記はいずれもハードウェアから得られた情報をもとに生成した数列

疑似乱数生成器

乱数生成器(random number generator/RNG)

熱や音の変化等の予測や再現が事実上不可能である自然現象をセンサーで検知した結果をもとに乱数列を生成するハードウェアのこと

疑似乱数生成器(pseudo random number generator/PRNG)

  • 乱数を生成するソフトウェアのこと
  • ソフトウェアのみで真の乱数を生成することはできないため「疑似」がつく
    • 線形合同法
    • 一方向ハッシュ関数を使う方法
    • 暗号を使う方法
    • ANSI X9.17

疑似乱数生成器 – 種と内部状態 –

内部状態

  • 疑似乱数生成器が管理しているメモリの値
  • 内部状態を攻撃者に知られてはいけない

c12_image01

種(seed)

  • 疑似乱数生成器の内部処理を初期化するために使用
  • ランダムなビット列かつ予測不可能な値
  • 種を攻撃者に知られてはいけない

疑似乱数生成器 – 線形合同法(liner congruential method) –

非常によく使われる疑似乱数生成器だが,予測不可能性を持たないため暗号技術には使用不可

疑似乱数 = (A * 内部状態 + C) mod M
  • 最初の疑似乱数を求める場合に限り,「内部状態」の部分に「種」が入る
  • A,C,Mは定数でA<M,C<Mを満たすこと

c12_image02

周期とかについてはもうPHPで説明する (liner_seed.php)
PHPでの計算をもとに説明
* 疑似乱数列の結果を見ると偏りがあることがわかる。
* A,C,Mの値を注意深く選択(周期が大きいもの)すれば,偏りについては解決できるため,無作為性の性質は持つ

Cのライブラリ関数randやJavaのjava.util.Randomクラスなどは線形合同法を使用している

疑似乱数生成器 – 一方向ハッシュ関数を使用する方法 –

攻撃者が過去に出力した疑似乱数列を入手しても,次の疑似乱数列を予測するのは不可能
※予測するには一方向ハッシュ関数の一方向性を破らないといけないため
→一方向ハッシュ関数の一方向性が疑似乱数生成器の予測不可能性を満たしている

c12_image03

疑似乱数生成器 – 暗号を使用する方法 –

攻撃者が次の疑似乱数列を使用するには,現在のカウンタを知る必要あり出力される疑似乱数列は暗号化されているため,カウンタを知るためには暗号を解読する必要あり解読は困難のため,暗号の機密性が予測不可能性を満たしている

c12_image04

内部状態(カウンタ)を初期化

  1. 鍵を使用しカウンタを暗号化したものを疑似乱数として出力
  2. 疑似乱数1つ生成ごと内部状態のカウンタを1増加する

必要なだけの疑似乱数列を得られるまで上記を繰り返す

疑似乱数生成器 – ANSI X9.17 –

c12_image05

  • 現在時刻自体は攻撃者が予測できるが,攻撃者は暗号化の鍵を知らないため,かき混ぜ役を予測することはできない
  • かき混ぜ役はビット列をランダムに反転するために使用される
  • 暗号を解読しないことには攻撃者は見破ることができないため,これまでに出力された疑似乱数列から内部状態を推測することはできない
  • 疑似乱数生成器の内部状態を暗号がガードしている

攻撃

種に対する攻撃

種は暗号の「鍵」に匹敵する重要性をもつ
攻撃者に疑似乱数生成器のアルゴリズムを知られている状態で,
種まで知られてしまうと,疑似乱数列をすべて知られることになる
 →攻撃者に知られないよう,再現不可能性を持つ乱数を種とする必要がある

ランダムプールに対する攻撃

ランダムプール

  • ファイルにランダムなビット列を蓄えておく方法
  • 暗号ソフトウェアが疑似乱数の種を必要とするときは,
  • このランダムプールから必要なだけのランダムなビット列を取り出して使用する
    攻撃者にランダムプールを知られてしまうと,疑似乱数の種を予測されてしまう可能性がある

乱数の使用例

ノンス(nonce) と ソルト(salt)

ノンス(nonce)

 暗号通信で使用される使い捨てのランダムな値.
 認証の過程で使われリプレイ攻撃(再生攻撃)を行えないようにする働きを担う
 サーバが401 Unauthorizedを返すため,リプレイ攻撃はほぼ不可能

ノンスの使用例

 HTTPのダイジェスト(Digest)認証
  パスワードのMD5ダイジェストを生成する過程で使用
  ダイジェスト認証はBasic認証では防げなかった盗聴や改ざんを防ぐために考案された

ソルト(salt)

 パスワードを暗号化する際に付与されるデータ
 ブルートフォース攻撃にはほとんど効果がない物の,レインボー攻撃に対しては有効

ブルートフォース攻撃

  総当たりにハッシュ値を計算

レインボー攻撃 

  あらかじめハッシュ値を計算し,標的のパスワードのハッシュ値と比較することでパスワードを推察.
  ブルートフォース攻撃に比べ短時間でパスワードを解読することが可能

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第12章 乱数(p312-p332)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門12 乱数 はコメントを受け付けていません

暗号技術入門11 鍵

担当:千葉

目次

  • 鍵とは何か
  • さまざまな鍵
  • 鍵を管理する
  • Diffe-Hellman鍵交換
  • パスワードを元にした暗号(PBE)
  • 安全なパスワードを作るには
  • まとめ

鍵とは何か

鍵とは何か

  • 鍵とはとても大きな数
  • 鍵は平文と同じ価値を持つ
  • 暗号アルゴリズムと鍵

鍵とはとても大きな数

  • 対象暗号、公開鍵暗号、メッセージ認証コード、デジタル署名などの暗号技術を使うには必ず鍵(key)と呼ばれる大きな数が必要
  • 「鍵空間の大きさ」=「可能な鍵の総数」
  • 鍵空間の大きさは鍵のビット長で決まる

鍵の例

DESの鍵

実質56ビット長(7バイト長)
51 EC 4B 12 3D 42 03

トリプルDESの鍵

DES-EDE2の鍵は実質112ビット長(14バイト長)
51 EC 4B 12 3D 42 03 30 04 D8 98 95 93 3F
DES-EDE3の鍵は実質168ビット長(21バイト長)
51 EC 4B 12 3D 42 03 30 04 D8 98 95 93 3F 24 9F 61 2A 2F D9 96

AESの鍵

AESの鍵は128,192,256の各ビット長から選択
以下は256ビット長(32バイト長)の場合の例
51 EC 4B 12 3D 42 03 30 04 D8 98 95 93 3F 24 9F 61 2A 2F D9 96 B9 42 DC A0 AE F4 5D 60 51 F1

鍵は平文と同じ価値を持つ

暗号化の目的は「平文の秘密を守りたいから暗号化を行う」

[対象暗号の場合]
盗聴者に暗号文を盗まれても、盗聴者は平文の内容を知ることはできない
盗聴者に鍵が盗まれた場合、盗聴者は平文の内容を知ることが出来る

鍵は平文と同じ価値を持つと言える

暗号アルゴリズムと鍵

  • 暗号アルゴリズムそのものを秘密にすることで情報の機密性を守ろうとするのは危険
  • 情報の機密性は、鍵を秘密にすることで守るべき

さまざまな鍵

さまざまな鍵

  • 対象暗号の鍵と公開鍵暗号の鍵
  • メッセージ認証コードの鍵とデジタル署名の鍵
  • 機密性のための鍵と認証のための鍵
  • セッション鍵とマスター鍵
  • コンテンツを暗号化する鍵と、鍵を暗号化する鍵

対象鍵暗号の鍵と公開鍵暗号の鍵

対象鍵暗号

公開鍵暗号

メッセージ認証コードの鍵とデジタル署名の鍵

メッセージ認証コード

デジタル署名

機密性のための鍵と認証のための鍵

  • 機密性を守るための鍵
    • 対象暗号や公開鍵暗号で使われる鍵
  • 認証のための鍵
    • メッセージ認証コードやデジタル署名の鍵

セッション鍵とマスター鍵

  • セッション鍵
    • 通信ごとに1度しか使われない鍵
  • マスター鍵
    • セッション鍵に対して、繰り返し使われる鍵をマスター鍵と呼ぶことがある

コンテンツを暗号化する鍵と、鍵を暗号化する鍵

  • CEK(contents encrypting key)
    • ユーザが直接利用する情報(コンテンツ)を暗号化の対象とする
  • KEK(key encrypting key)
    • 鍵を暗号化する鍵

コンテンツを暗号化する鍵と、鍵を暗号化する鍵

さまざまな鍵

鍵を管理する

  • 鍵を作る
  • 鍵を配送する
  • 鍵を更新する
  • 鍵を保存する
  • 鍵を捨てる

鍵を作る

  • 乱数から鍵を作る
  • パスワードから鍵を作る – パスワードを元にした暗号(PBE) –

鍵を配送する

  • 鍵の事前共有
  • 鍵配布センター
  • 公開鍵暗号
  • Diffe-Hellman鍵交換

鍵を更新する

  • 鍵更新(key updating):通信の機密性を高めるテクニックの一つ
  • 鍵が盗聴された場合、鍵更新を行った時点よりも過去にさかのぼって通信を復号化することが出来ない
  • 一方向ハッシュ関数の性質によって逆算が困難であることを保証している
  • 過去にさかのぼった解読を防止することをバックワードセキュリティと呼ぶ

鍵を保存する

  • 鍵は記憶できないため、鍵の保存を考えなければならない
  • 鍵を盗まれた時から、その鍵を攻撃者が使うことが出来るまでの時間を稼ぐため、鍵を暗号化して保存するというテクニックが使われる

鍵を捨てる

  • 今後使わない不要な鍵は確実に削除しなければならない
  • 盗聴者に鍵を盗まれた場合、過去の暗号文を復号化されてしまうため

Diffe-Hellman鍵交換

  • Diffe-Hellman鍵交換とは何か
  • Diffe-Helman鍵交換の手順
  • 盗聴者は鍵を計算できないのか
  • 生成元とは
  • 具体例

Diffe-Hellman鍵交換とは何か

  • 1976年にホイットフィールド・ディフィーとマーティン・ヘルマンによって発明されたアルゴリズム
  • 他人に知られても構わない情報を二人が交換するだけで、共通の秘密の数を作り出すという方法
  • 作り出した秘密の数を対象暗号の鍵として使う
  • IPsecではDiffe-Hellman鍵交換を改良した方法を使っている

Diffe-Helman鍵交換の手順

盗聴者は鍵を計算できないのか

  • 盗聴者が知りえる数は P,G,G^A mod P,G^B mod P
  • G^A mod P から数Aを簡単に計算するアルゴリズムは、まだ発見されていない
  • これを有限体上の離散対数問題と呼ばれ、これを解くことの難しさが, Diffe-Helman鍵交換 というアルゴリズムを支えている

生成元とは

Pが13としたときの各要素の累乗の表を見てみる(G^P mod P)

具体例

パスワードを元にした暗号(PBE)

  • パスワードを元にした暗号とは何か
  • PBEの暗号化
  • PBEの複合化
  • ソルトの役割
  • パスワードの役割
  • PBEの改良

パスワードを元にした暗号とは何か

  • パスワードを元にした暗号(password based encryption : PBE)とは,その名の通り,パスワードを元にして作った鍵で暗号化を行う方法
  • 暗号化と複合化の両方で同じパスワードが必要.

PBEの暗号化

PBEの復号化

ソルトの役割

  • ソルトは疑似乱数生成器で作られるランダムな数
  • ソルトは、辞書攻撃を防ぐためにある。辞書攻撃とは、前もって鍵の候補を計算して準備しておく方法
  • KEKを作る際にソルトを使うと、KEKの候補のバリエーションがソルトのビット長だけ増えることになるので、KEKの候補を前もって作ることが困難になる

パスワードの役割

  • PBEでは、パスワードで作った鍵(KEK)でセッション鍵(CEK)を暗号化する
  • パスワードで作った鍵(KEK)は、疑似乱数生成器で作ったセッション鍵(CEK)よりも弱い
  • そのため、パスワードを元にした暗号(PBE)を用いる場合には、ソルトと暗号化したCEKを物理的に守る方法を併用するべき

PBEの改良

  • KEKを作る際に、一方向ハッシュ関数を何度も通すようにすれば安全性を高めることができる
  • ユーザにとってはハッシュ関数を何度も繰り返すのはそれほど負担とはならない
  • 攻撃者にとっては、この小さな違いが大きな負担となる

安全なパスワードを作るには

  • 自分だけが知りえる情報を使うこと
    • 大事なものの名前を使ってはいけない
    • 自分に関する情報を使ってはいけない
    • 他人が目にする情報を使ってはいけない
  • 複数のパスワードを使い分けること
    • 忘れては困るからと安易なパスワードを選ぶよりも疑似乱数生成器で作ったランダムな文字列を安全な場所に保存する方が有効かもしれない
    • パスワードの一部のみをメモすることも有効
  • メモを有効に使うこと
    • パスワードが英数字8文字と想定した場合、
    • 英数字1文字は62文字のうちのどれかとなるため
    • 62^8 = 218340105584896
    • から、約218兆通りとなる
    • 大きな数字に見えるが、鍵のビット長でいえば48ビットに過ぎない
    • これは、ブルート・フォース・アタックが可能なサイズである
  • パスワードの限界を知ること
  • パスワード生成/管理ツールを使うこと
    • パスワード生成/管理ツールは乱数を使って推測が難しいパスワードを生成する
    • ただし、ツールとその開発元を信用できるかどうかが大事になる

まとめ

  • 暗号化アルゴリズムが平文を守り、平文の代わりに自分たちは鍵を守る
  • 鍵こそが暗号技術の「鍵」である

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第11章 鍵(p282-p310)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門11 鍵 はコメントを受け付けていません

暗号技術入門10 証明書

担当:福田

目次

  • 証明書
  • 公開鍵基盤(PKI)
  • 証明書に対する攻撃
  • まとめ

証明書

証明書とは何か

公開鍵が正しいものかどうかを証明するものが「証明書」

【運転免許証】

写真,氏名,生年月日,有効期限,運転できるクルマの種類など+公安委員会の押印.
公安委員会が「この人は運転する資格がある」と認められていることが分かる.

【公開鍵証明書(Public-Key Certificate : PKC)】

名前,所属,メールアドレスと,その人の公開鍵+認証局(Certification Authority : CA)によるデジタル署名.
認証局が「この公開鍵は確かにこの人のものである」と認めたことが分かる.

認証局

  • 「この公開鍵は確かにこの人のものである」と認めて,デジタル署名をできる人や組織.
  • 国際的な組織や政府が作ったもの,認証局のサービスの提供を業務としている一般企業.
  • 個人で認証局を作ることも可能.

証明書を使うシナリオ

証明書の標準規格

  • 証明書の形式がばらばらになっていては不便なため,証明書の規格が定められている.
  • 最も広く使われているのは,X.509
  • X.509以外の公開鍵証明書フォーマットとしては SPKIやSDSIなどが存在するが,SSLなどの多くのセキュリティプロトコルが ベースとしているX.509がデファクトスタンダードとなっている.

X.509 サーバ証明書の構造

  1. バージョン情報
  2. シリアル番号
  3. 署名アルゴリズム
  4. 発行者情報
  5. 有効期間の開始
  6. 有効期間の終了
  7. サブジェクト(発行先の情報)
  8. 公開鍵のアルゴリズム
  9. 公開鍵
  10. 署名アルゴリズム
  11. 拇印

公開鍵基盤(PKI)

公開鍵基盤(Public-Key Infrastructure: PKI )

  • 公開鍵を効果的に運用するために定められた規格や仕様.
  • あくまで総称であり,単独の規格や仕様を指すものではない.

PKIの構成要素

利用者:PKIを利用する人.
認証局:証明書を発行する人.
リポジトリ:証明書を保管しているデータベース.

利用者

  • アリスやボブのようなPKIを利用する人のこと.
  • PKIを使って自分の公開鍵を登録したいと思っている人と,登録されている公開鍵を使いたいと思っている人が存在する.

公開鍵を登録する利用者

  • 鍵ペアを作成する.
  • 認証局に公開鍵を登録する.
  • 認証局から証明書を発行してもらう.
  • 認証局に登録した公開鍵を無効にしてもらう.
  • 受信した暗号文を復号化する.
  • メッセージにデジタル署名を行う.

公開鍵を使う利用者

  • メッセージを暗号化して受信者に送信する.
  • デジタル署名の検証を行う.

認証局( Certification authority:CA)

  • 鍵ペアを作成する(利用者が作成する場合もある)
  • 公開鍵の登録の際に,本人を認証する.
  • 証明書を作成し発行する.
  • 証明書を破棄する.

リポジトリ

  • 証明書を保存しておき,PKIの利用者が証明書を入手できるようにしたデータベース.
  • 証明書ディレクトリとも呼ばれる.

認証局の仕事

  • 鍵ペアの作成
  • 証明書の登録
  • 証明書の破棄とCRL

鍵ペアの作成

  • 利用者の鍵ペアの作成は,PKI利用者が行う場合と,認証局が行う場合がある.
  • 認証局が鍵ペアを作成する場合,認証局は「プライベート鍵を利用者に送る」仕事を行う必要がある.
  • 「プライベート鍵を利用者に送る」方法として,RFC7292(PKCS #12 Personal Information Exchange Syntax Standard)などで規定されている.

証明書の登録

  • 利用者が鍵ペアを作った場合,利用者は認証局に証明書の作成を依頼する.
  • 証明書を申請するときの規格は,RFC2986(PKCS #10 Certification Request Syntax Specification:証明書署名要求※)などで規定されている.
  • 認証局は運用規定に基いて利用者を認証し,証明書を作成する.
  • 証明書を作成するときには,認証局のプライベート鍵を使ってデジタル署名を行う.

※証明書署名要求(CSR):証明書を申し込むために申請者から認証局へ送られるメッセージ.

証明書の破棄とCRL

  • 利用者がプライベート鍵をなくしたり,盗まれたりした場合,証明書を破棄して無効にする必要がある.
  • 証明書はデジタルデータであるため,リポジトリから削除しても,コピーが利用者の手元に残っているため破棄したことにはならない.
  • そのため,証明書を破棄する場合,証明書破棄リスト(Certificate Revocation List:CRL)を作成する.
  • CRLは破棄された証明書のシリアル番号の一覧に対して,認証局がデジタル署名をつけたもの.
  • PKI利用者は認証局の最新のCRLを調べて,その証明書が有効かどうかの確認が必要.

階層になった証明書

利用者は証明書に施されている認証局のデジタル署名を,認証局の公開鍵を使って検証する.→利用者は公開鍵の正当性をどうやって判断するのか?

  • 認証局の公開鍵に対して,別の認証局がデジタル署名を施すことで,認証局の公開鍵を検証することができる.
  • 認証局が別の認証局の公開鍵を検証するという関係は何重にも繰り返すことが可能.

ボブのデジタル署名をアリスが検証したい場合

さまざまなPKI

  • PKIは「権威を持った認証局が1つだけ存在している」,「全世界のPKIは,たった1つのルートCAのもとで認証される」わけではない.
  • 国や自治体といった公共の組織や団体が認証局を作ってPKIを実現する場合も,ビジネスで使うために会社が社内だけでPKIを構築することも,実験用に友達同士でPKIを構築することも可能.
  • どのようなPKIを構築するかは,目的や規模によって異なり,やり方が固定的に決まっているわけではない.

政府認証基盤(GPKI)

日本が定めているPKIは政府認証基盤(GPKI)と呼ばれていて,認証局の階層や,運用規約,公開鍵の登録・証明書の発行などについて定めている.

証明書に対する攻撃

  • 公開鍵の登録前を攻撃
  • 似た人間を登録する攻撃
  • 認証局のプライベート鍵を盗み出す攻撃
  • CRLの隙を突く攻撃(1)
  • CRLの隙を突く攻撃(2)

公開鍵の登録前を攻撃

認証局がデジタル署名を行う前に,マロリーが公開鍵をすり替える.

似た人間を登録する攻撃

似たような名前の別のユーザー情報を登録したマロリーが,偽証明書をボブになりすましてアリスに送る.

対策

認証局が正しく本人確認を行うことでなりすましを防止する

認証局のプライベート鍵を盗み出す攻撃

CRLの隙を突く攻撃(1)

対策

  • ボブは,プライベート鍵を盗まれないようにする.
  • ボブは,公開鍵が無効になったら可能な限り早く認証局に伝える.
  • 認証局は,CRLを素早く発行する.
  • アリスは,CRLをきちんと更新する.
  • アリスは,公開鍵を利用する前に,公開鍵が無効になっていないかを再確認する.

CRLの隙を突く攻撃(2)

対策

なし

※公開鍵や証明書などの技術を使ってボブの犯罪を検出することはできず,通常の犯罪の捜査が必要.

まとめ

  • 公開鍵が正しいものかどうかを証明するものが証明書.
  • 証明書を発行する人や組織が認証局.
  • 公開鍵を効果的に運用するための規格や仕様が公開鍵基盤(PKI)
  • CRLはきちんと更新,確認する.
  • 認証局,企業,個人にかかわらず,プライベート鍵は厳重に管理する.

memo

  • CAの仕組みは、10年単位で使える

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第10章 証明書(p252-p277)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門10 証明書 はコメントを受け付けていません

暗号技術入門09 デジタル署名

担当:髙橋

目次

1. 署名とは
2. デジタル署名の暗号化方法
3. デジタル署名付きデータの送受信
4. 利点
5. 攻撃
6. 問題点
7. まとめ

1.署名とは

署名

本人が自筆で氏名を手書きすること.(印刷された氏名+捺印も含む)

書類や契約書に署名することにより「本人のもの」であることを証明する.

デジタル署名

インターネット世界における自分自身を証明する「署名(サイン)」のこと.

送信されたデータが本人のものであることを証明するのための技術.

※暗号化を使用するが,データを読解できなくするわけではない.

2.デジタル署名の暗号化方法

公開鍵暗号化と一方向ハッシュ関数を使用

暗号化方式 説明
公開鍵暗号化方式 「公開鍵」で暗号化し,「秘密鍵」で複合化する.
デジタル署名 「秘密鍵」で暗号化し,「公開鍵」で複合化する.

3.デジタル署名付きデータの送受信

前準備

4.利点

1. ハッシュで改ざんを検出
2. 公開鍵暗号でなりすましを検出
3. 否認防止

否認防止

何かの都合で,秘密鍵を持つデータ作者が自分が作成したものではないと言い張っても,いったん公開鍵で復号化できた以上,データを発行した本人であることを否定することはできない.

疑問

デジタル署名は本当に署名の代わりになるのか?

  • デジタル署名は通常の印鑑や手書きの署名よりも信用できる,と考えるのは危険です.
  • さまざまなトラブルに対する解決法が見いだされて,初めて,実社会に受け入れられる技術になっていくのではないでしょうか?

デジタル署名の利用例

1. セキュリティー情報のアナウンス(ホームページ)
2. ソフトウェアのダウンロード(Androidのインストール,起動)

5.攻撃

デジタル署名を使って公開鍵暗号を攻撃

公開鍵暗号の暗号をデジタル署名で複合化する.

対応策

デジタル署名で使う鍵ペアと公開鍵暗号で使う鍵ペアを別にする.

6.問題点

前提

公開している「公開鍵」で,誰にでも復号化することが可能になることにより,「秘密鍵で送信してきたということは,本人に間違いない」ことが証明できる.

問題点

本文とデジタル署名,公開鍵のすべてを「なりすまし」によって差し替えられた場合,最初に受け取る公開鍵が,本人から送られてきたことを証明できない.

7.まとめ

  • 送信相手に送る鍵は,公開鍵
  • 受け取ったデータとデジタル署名から,改ざんとなりすましを検出できる.
  • 最初に受け取る公開鍵が,本人から送られてきたことを証明できない

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第9章 メッセージ認証コード(p224-p250)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門09 デジタル署名 はコメントを受け付けていません

暗号技術入門08 メッセージ認証コード

担当:佐々木

アジェンダ

  • メッセージ認証コードとは
  • メッセージ認証コードの利用例
  • GCMとGMAC、HMAC
  • メッセージコードで解決できない問題
  • まとめ

メッセージ認証コードとは

メッセージ認証とは「メッセージが正しい送信者からのものである」と言う性質の事.

メッセージ認証コードとは何か?(message authentication code)

頭文字をとってMACと呼ばれています。

ここでもやっぱり出てくる鍵配送問題

メッセージ認証コードの利用例

  • SWIFT(国際銀行間通信協会)
  • IPsec
  • SSL/TLS

メッセージ認証コードの実現方法

  1. 一方向ハッシュ関数を使って実現(SHA-2のような一方向ハッシュ関数を使う)前回の19Page参照
  2. ブロック暗号を使って実現(AESのようなブロック暗号を使う)
  3. その他の方法で実現(ストリーム暗号や公開鍵暗号などを使う)

GCMとGMAC

GCMとは?(Galois/Counter Mode)

認証つき暗号の一種

HMAC

HMACとは?

  • 一方向ハッシュ関数を用いて, メッセージ認証コードを構成する手法の事
  • 頭にHMACをつけて呼ばれる
    • SHA-1
    • SHA-224
    • SHA-256
    • SHA-384
    • SHA-512
    • HMAC-SHA-1
    • HMAC-SHA-224
    • HMAC-SHA-256
    • HMAC-SHA-384
    • HMAC-SHA-512

ブロック再生攻撃

ブロック再生攻撃を防ぐには?

  • シーケンス番号を振る
  • タイムスタンプを埋め込む
  • ノンスと呼ばれるワンタイムパスなどを埋め込む

メッセージコードで解決できない問題

  • 第三者に対する証明
  • 否認防止

メッセージは正しく送られてきたか

第三者に対する証明ができない.

否認防止とは?


メッセージ認証コードは…
* メッセージの正真性を確認する技術である。
* 送信者、受信者が共有する鍵を使ってなりすまし、改ざんされてないかをチェックする事が可能。
* 一方向ハッシュ関数や対象暗号などを用いて実現が可能。(特にHMAC)

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第8章 メッセージ認証コード(p206-p220)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門08 メッセージ認証コード はコメントを受け付けていません

暗号技術入門07 一方向ハッシュ関数

担当:野田

アジェンダ

  • 一方向ハッシュ関数とは
  • 一方向ハッシュ関数の性質
  • 一方向ハッシュ関数の応用例
  • 一方向ハッシュ関数の紹介

一方向ハッシュ関数とは

バイナリによる正真性確認

ファイルが巨大!なものだったら?
* コピー
* 保管
* 比較
時間がかかる

入力 (メッセージ)、出力 (ハッシュ値)

ハッシュ値の計算

一方向ハッシュ関数の性質

  1. 任意長のメッセージから固定長のハッシュ値を計算する
  2. ハッシュ値を高速に計算できる
  3. メッセージが異なればハッシュ値も異なる

一方向ハッシュ関数の性質 – 衝突

一方向ハッシュ関数の性質 – 弱衝突耐性

一方向ハッシュ関数の性質 – 強衝突耐性

一方向ハッシュ関数の性質 – 一方向性

一方向ハッシュ関数の応用例

  • パスワードを元にした暗号化
  • メッセージ認証コード
  • デジタル署名
  • 擬似乱数生成器
  • ワンタイムパスワード

一方向ハッシュ関数の紹介


一方向ハッシュ関数では、改ざんを検出できるが、なりすましは検出できない。

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第7章 一方向ハッシュ関数(p170-p203)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門07 一方向ハッシュ関数 はコメントを受け付けていません

暗号技術入門06 ハイブリッド暗号システム

担当:藤井

ハイブリッド暗号システムとは

対称暗号と公開鍵暗号の両者を組み合わせて、暗号化する方法

対称暗号と公開鍵暗号

対称暗号方式では、送信者と受信者で共通の鍵を共有する必要があり、鍵を安全な経路を使って配送しないといけないという「鍵配送問題」がありました。

この「鍵配送問題」を克服したのが、公開鍵と秘密鍵を使う公開鍵暗号方式です。

しかし、この公開鍵暗号には2つの問題点があります。

  1. 対称暗号方式に比べて処理速度が遅いこと
  2. 中間者攻撃に弱いということ

ハイブリッド暗号システムは、この問題のうち、1番の処理速度の問題を解決する手法です。

概要

  • セッション鍵は、疑似乱数生成器で生成します。
  • メッセージを、セッション鍵を用いて対称暗号で暗号化します。
  • セッション鍵を、公開鍵暗号で暗号化します。

暗号化の流れ

セッション鍵とは、今回の通信のために一時的に作成される鍵のことです。

セッション鍵は疑似乱数生成器で生成され、メッセージの対称暗号の鍵に使われます。

次に、セッション鍵は、公開鍵暗号によって暗号化されます。

公開鍵暗号の暗号化には「受信者の公開鍵」が使われます。

セッション鍵は、メッセージ本文に比べ短いのが普通であるため、公開鍵暗号の処理が遅くてもそれほど時間はかかりません。

セッション鍵は、対称暗号にとっては鍵で、公開鍵暗号にとっては平文になるということです。

暗号化したメッセージと暗号化したセッション鍵を結合すると、ハイブリッド暗号システムにおける暗号文になります。

以上が、暗号化の流れです。

次に、復号化の流れについてです。

受け取った暗号文を「暗号化されたメッセージ」と「暗号化されたセッション鍵」の二つに分割します。

受信者と送信者の間で、暗号文がどういう構造をしているかを取り決めておけば、容易に分割できます。

次に、「暗号化されたセッション鍵」を受信者のプライベート鍵を用いて復号化します。

最後に、復号化されたセッション鍵を用いて、暗号化されたメッセージを復号化します。

以上が復号化の流れです。これは、ちょうど暗号化の流れと逆になっています。

使用例

ハイブリッド暗号システムの使用例

  • SSL/TLS
  • 有名な暗号ソフトウェアPGP

強いハイブリッド暗号システムとは

  • ブルートフォースアタック(総当たり攻撃)でセッション鍵を推測されないような品質の疑似乱数生成器を使用する。
  • 対称暗号は、強いアルゴリズム、鍵長を適切な長さ、適切なブロック暗号のモードを使用する。
  • 公開鍵暗号も強い暗号アルゴリズム、充分に長い鍵長を使用する。
  • セッション鍵が破られると今回の通信のみが解読されるが、公開鍵暗号が破られると(同じ公開鍵を使った)すべての通信が解読される。

強いハイブリッド暗号システムは、以下の項目が重要になります。

セッション鍵を生成する疑似乱数生成器は、推測されないような品質のものを使用する必要があります。

一部でも推測されると、総当たり攻撃がされやすくなってしまいます。

対称暗号は、〰必要があります。

公開鍵暗号も〰必要があります。

セッション鍵が破られると今回の通信のみが解読されますが、公開鍵暗号が破られると、すべての通信が解読されるため、公開鍵暗号をより強くすべきです。

まとめ

ハイブリッド暗号システムは、

  • 対称暗号と公開鍵暗号の両者を組み合わせて、暗号化する方法。
  • メッセージを対称暗号で暗号化、対称暗号のセッション鍵を公開鍵暗号で暗号化する。
  • 対称暗号の鍵配送問題、公開鍵暗号の処理速度の遅さを解消する。

補足

中間者攻撃とは、

公開鍵暗号の通信において、受信者が送信者に公開鍵を送信する際に、第三者が妨害できれば中間者攻撃が可能となる。

SSL/TLS

処理の流れ

  1. クライアントはWebサーバに接続要求を出す
  2. Webサーバは鍵ペアから公開鍵をクライアントに送ります
  3. クライアントは共通鍵暗号化方式でデータ本体の暗号化を行います
  4. クライアントが生成した共通鍵をWebサーバの公開鍵で暗号化します
  5. クライアントは暗号化したデータと暗号化した共通鍵をWebサーバに送ります
  6. Webサーバは暗号化された共通鍵をWebサーバの秘密鍵で複合化します
  7. Webサーバは取り出した共通鍵でデータを複合化します
カテゴリー: 勉強会 | タグ: , | 暗号技術入門06 ハイブリッド暗号システム はコメントを受け付けていません

暗号技術入門05 公開鍵暗号

目次

  1. 公開鍵暗号とは
  2. RSA暗号
  3. 他の公開鍵暗号
  4. 公開鍵暗号の問題

公開鍵暗号とは

暗号化の鍵を一般に公開できる

公開鍵暗号の歴史

出来事
1976 ホイットフィールド・ディファーとマーティン・ヘルマンがアイデアを発表
1977 ナップサック暗号が作られる
1978 ロン・リヴェスト、アディ・シャミア、レナード・アルマンによりRSA暗号が発表される

1976年に公開鍵暗号のアイデアが発表され、その1年後ナップサック暗号という暗号が作られました。しかし、この暗号は後に安全でないことがわかりました。
そして、1978年RSA暗号が発表され、このRSA暗号が現在の標準となっています。

しかし、この歴史には裏話があり

1960年代に公開鍵暗号と同じアイデアがすでに考案されており、
1973年RSAと同様の暗号を生み出していたそうです

公開鍵暗号とは

受信者が公開鍵とプライベート鍵のペアを作成し、
メッセージの送信者へ送ります。

送信者は受け取った公開鍵で暗号化した暗号文を受信者へ送ります
その暗号文を受信者はプライベートキーで複合化します。

RSA暗号

平文を示す数をE乗して、Nで割ったあまりが暗号文になります。
このE乗してNで割るというのが暗号化をあらわしています
秘密鍵暗号ではXORやらビットの移動やらしていましたが、これだけです
また、複合化はD乗してN割ったあまりが平文となります
もちろんD乗してN割るというのが複合化をしめしています。

ここでEとNが公開鍵
DとNが秘密鍵となります
ここで登場するN、E,Dを決めるというのは
すなわち公開鍵とプライベート鍵を作るというのと同じいみです
次のページから実際にどうやって鍵を作るか見てみます

Nは二つの素数pとqをかけたものです
このpとqはだいたい約300桁の素数になります
次に
Lはp-1とq-1の最小公倍数です
Eは1~Lの間でEとLの最大公約数は1になる数字です。
これは、EとLの素数で共通部分がない組→これが最大公約数が1になります
次にDこれは
Eとかけて割ったあまりが1になる数字です。

これで
EとDとLを求めることが出来ました。
公開鍵とプライベート鍵を作る際には中でこんなことが起こってるそうです

ここで公開鍵の中で
EとNの値がわかってしまいます。
どうにかしてDの値が求められないかやってみましょう

EとNからDはわかるか?

EとDの関係式は

E×D mod L=1

2つの素数pとqを知られると不味い

他の公開鍵暗号

  • ElGamal方式
  • Rabin方式
  • 楕円曲線暗号

他の公開鍵暗号として
えるがまる方式
ラビン方式
楕円曲線暗号が存在します

この中で覚えていてほしいのが楕円曲線暗号通称ECCです
これはRSAにくらべビット数を少なく出来、最近注目されている暗号アルゴリズムです
詳しくは調べてください

公開鍵暗号の問題

共通鍵暗号よりもとても遅い

公開鍵暗号は共通鍵暗号に比べてデータの処理速度が遅いという問題があります。

そこで、ハイブリット方式という手法がとられます

共通鍵を渡すときに公開鍵暗号を使い
それ以降は渡した共通鍵でやり取りをするという方式です

このハイブリット方式については次の章で紹介します。

結論

鍵を作るときは2048bitで

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第5章 公開鍵暗号(p112-p152)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門05 公開鍵暗号 はコメントを受け付けていません

暗号技術入門04 ブロック暗号のモード〜ブロック暗号をどのように繰り返すのか〜

担当:勝見

目次

  • はじめに
  • 暗号アルゴリズム
  • 暗号モードの種類
  • 各暗号モードの仕組みと特徴
  • まとめ

はじめに

  • 前回の対象暗号では、1ブロック(※)分の暗号化についての説明でした。
  • 任意の長さの平文を暗号化するためには、ブロック暗号を繰り返す必要がある。
  • ブロック暗号を繰り返す方法のことをブロック暗号の「モード」と呼ぶ。
    (※)1ブロック= 64ビット(8バイト)、128ビット(16バイト)など

分割イメージ

  • 例えば、32バイトのデータがあった場合、AESで暗号化すると、2つのブロックに分割される。
  • 分割されたデータは、それぞれブロック毎に処理される。

単純に暗号化すると1

単純に暗号化すると2

今回のポイント

  • 同じ入力があったたとき、暗号化された結果の出力が同じにならないようにする方法。
  • 暗号化/復号化するときに一工夫して、ブロックごとに操作して、より複雑さを加える方法。

暗号アルゴリズム

暗号アルゴリズムは、次の2つに大きく分けられる。
* ブロック暗号
* ストリーム暗号

ブロック暗号(block cipher)

  • ある特定のビット数の「まとまり」を一度に処理する暗号アルゴリズムの総称。
  • ブロック単位で処理が完了する。
  • 第3章の「対称暗号」で紹介された、DES, 3DES, AESが相当する。

ストリーム暗号(stream cipher)

  • データの流れ(ストリーム)を順次処理していく暗号アルゴリズム
  • 1ビット、8ビット、32ビットなどの単位で暗号化や復号化が行われる
  • データの流れを順次処理し、内部状態を持っている
  • 第3章の「対称暗号」で紹介された「使い捨てパッド」が相当する。

ブロック暗号のモード

  • ブロック暗号
    • ECBモード: Electronic CodeBook mode(電子符号表モード)
    • CBCモード: Cipher Book Chaining mode(暗号ブロック連鎖モード)
  • ストリーム暗号
    • CFBモード: Cipher-FeedBack mode(暗号フィードバックモード)
    • OFBモード: Output-FeedBack mode(出力フィードバックモード)
    • CTRモード: CounTeR mode(カウンタモード)

暗号化方式表記例

平文ブロックと暗号ブロック

各モードを説明する前に

ECB(Electric CodeBook)モード

  • 平文ブロックを暗号化したものが、そのまま暗号文ブロックになる
  • どのモードよりも最もシンプル→ なぜなら特別なことは一切行わない

ECBモードの暗号化・復号化

ECBモードの危険性

ピクセルパターンが同一となるブロックは、同一の暗号パターンとなるので、オリジナルの画像は滲んで復元できる。

※ 出典:暗号利用モード(検索日時:2017年03月31日)
https://commons.wikimedia.org/wiki/File:Tux.jpg?uselang=ja
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Tux_ecb.jpg
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Tux_secure.jpg

ECBモードへの攻撃 1/2


image09

ECBモードへの攻撃 2/2

ECBモード:利点と欠点

CBC(Cipher Block Chaining)モード

一つ前の暗号ブロックと平文ブロックのXORを取ってから暗号化を行う

CBCモードによる暗号化

CBCモードによる復号化

初期ベクトルIV

  • 1ブロック前の平文ブロックを使用するが、最初の平文ブロックの前にはブロックは存在しない。
  • 最初の1ブロック分のみ、代わりのものを用意する。
  • 初期ベクトル(initialization vector)と呼ばれ、一般的にIVと呼ばれる。

ECBモードとCBCモードの比較

CBCモードの特徴1

  • 平文ブロックは、必ず「一つ前の暗号ブロック」とXORを取ってから暗号化される。
  • もし、平文ブロック1と2の値が等しくても、暗号文ブロック1と2の値は同じになるとは限らない。
  • ECBモードの欠点は、この仕組みでCBCモードにはない。

パディングオラクル攻撃1

  • 平文のデータ長が必ずしも、16の倍数(AESの場合)にならない。
  • 足りない分は、16の倍数になるように詰め物(パディング)を行う。

パディングオラクル攻撃2

  • パディングの内容を変化させながら、暗号文を何度も送信させ、受信側でエラーにならないデータを作り出して、平文の情報の一部を得ようとするもの。
  • CBCモードに限らずパディングを行うモードすべてに使える
  • 2014年SSL3.0へのPOODLE攻撃として大問題になった。

初期ベクトル(IV)への攻撃

  • 初期ベクトル(IV)は予測不能な乱数として与える必要がある。
  • SSL/TLSのTLS1.0では、IVが予測不可能な乱数として与えられていなく、前回CBCモードで暗号化した際の最後のブロックが使われていた。
  • TLS1.1以降では、IVを明示的に与えらえるように変更された。

CBCモード:利点と欠点

CFB(Cipher FeedBack)モード

  • CFBモードでは、1つ前の暗号文ブロックを暗号アルゴリズムの入力に戻す。
  • フィードバックというのは、入力へ戻すということを意味する。
  • 「平文ブロック」は暗号アルゴリズムによって直接暗号化を行わない。
  • 「平文ブロック」と「暗号アルゴリズムの出力(鍵ストリーム)」とをXORして「暗号文ブロック」を作り出す。

CFBモードによる暗号化

CFBモードによる復号化

鍵ストリーム

暗号アルゴリズムが生成するビット列のことを鍵ストリーム(key stream)と呼ぶ。

CFBモードとストリーム暗号

  • CFBモードの構造は、「使い捨てパッド」と似ている。
  • 使い捨てパッドは、「平文」と「ランダムなビット列」とをXORして「暗号文」を作りだす。

補足

  • 暗号アルゴリズムの出力は計算で作り出しているので、真のランダムなビット列ではない。
  • CFBモードが使い捨てパッドのように理論的に解読不能になるわけではない。

CBCモードとCFBモードの比較

再生攻撃(Replay Attack)

同じカギを使ったって暗号化をすると改ざんができる。

CFBモード:利点と欠点

OFB(Output-FeedBack)モード

  • 「平文ブロック」は暗号アルゴリズムによって直接暗号化を行わない。
  • 「平文ブロック」と「暗号アルゴリズムの出力」とをXORして「暗号文ブロック」を作り出す。
  • OFBモードは、CFBモードに似ている。

CFBモードによる暗号化

CFBモードによる復号化

CFBモードとOFBモードの比較

OFBモードとCFBモードでは、暗号アルゴリズムの入力だけが異なっている。

OFBモード:利点と欠点

CTR(CounTeR)モード

  • CTRモードは、1ずつ増加していくカウンタを暗号化して、鍵ストリームを作り出す
  • ストリームカウンタを文字列化したビット列と、平文ブロックとのXORを取った結果が、暗号ブロックとなる。

カウンタの作り方1

カウンタの初期値は、暗号化のたびに異なる値(ノンス)を元にして作る。ブロック長が128ビット(16バイト)の場合は、以下のようになる

カウンタの作り方2

  • 前半の8バイトがノンスと呼ばれ、固定の値となる。
  • 後半の8バイトはブロック番号で、この部分がカウントアップされていく
  • カウンタ値が増え毎回異なるので、それで暗号化した鍵ストリームもブロックごとに異なるビット列となる

CTRモードによる暗号化

CTRモードによる復号化

OFBモードとCTRモードの比較

  • OFBモードは暗号文ブロックをフィードバックする
  • CTRモードではカウンター値を増加させる

CTRモードの特徴

  • CTRモードの暗号化と復号化は同じ構造となるので、プログラムの実装が容易
  • CTRモードでは、暗号化・復号化の際に使うカウンタをノンスとブロック番号から求めるので、ブロックを任意の順番で暗号化・復号化することができる。
  • 任意の順序で暗号化・復号化できる性質を持っているので、処理を並列に実行できる。

CTRモード:利点と欠点

まとめ

  • ECBモード以外を使用する。
  • IVは、毎回ランダムに作成する。
  • 改ざんなどの攻撃は可能だが、第8章「メッセージ認証コード」を組み合わせることで、改ざんが検知可能。

AESのデフォルト値

  • MySQL 5.7 AES-128-ECB モードを変更して、IVを管理する方法 を考える必要あり
  • Laravel5.1以降 AES-256-CBC IVは自動管理(IV+暗号化データが生成)
  • PHP 自分で全て指定

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第4章 ブロック暗号のモード(p82-p109)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門04 ブロック暗号のモード〜ブロック暗号をどのように繰り返すのか〜 はコメントを受け付けていません

暗号技術入門03 対称暗号(共通鍵暗号)

担当:生田

目次

  1. 対称暗号とは
  2. ワンタイムパッド
  3. 安全性
  4. ブロック暗号
    1. DES
    2. 3DES
    3. AES

対称暗号とは

見方が異なる呼称が存在する

  1. 同じ鍵を共有するから「共有鍵暗号」
  2. 暗号化と復号で同じ鍵を使うから「対称暗号」
  3. 共有する鍵を秘密にするから「秘密鍵暗号」

※公開鍵暗号との比較

様々な実現方式が存在する

暗号が根拠とする安全性

  1. 情報理論的安全性
  2. 計算量的安全性
  3. 統計量的安全性

ワンタイムパッド

まず排他的論理和

排他的論理和の計算例1

排他的論理和の計算例2

GF(2):有限体

有限体(ガロア体)

四則演算(+,-,×,÷)が定義され閉じている有限集合

`XOR` は `GF(2)` の加法 (+)
1. 集合 F={0,1} 上に加法・乗法が定義されている。
2. 集合 F={0,1} に単位元が存在する。(加法の単位元を0、乗法の単位元を1)
3. 集合 F={0,1} の任意の要素 a に対して、
    a+b=0 を満たす加法の逆元: b = -a、
零元を除いて、
    a * c = 1 を満たす乗法の逆元: c = a-1 が存在する
4. GF(2)上で結合則、分配則、結合則を満たす
    4.1. A xor B = B xor A
    4.2. A xor B xor C = A xor (B xor C)
    4.3. A and (B xor C) = A and B xor A and C

同じビット列を2回xorすると元に戻る

A xor B xor B = A

乱数Rとxorをとる=>暗号

A xor R = E

暗号と乱数Rのxorをとる => 復号

E xor R = A

平文と同じサイズの鍵が必要…

鍵の保管、配送、同期、生成が困難

鍵の保管、配送、同期、生成が困難

解読の難しさは?

鍵長と安全性

  1. 情報理論的安全性
    1. 平文候補の中から正しい平文を見つけるのと、鍵候補の中からその鍵を使って復号した平文候補が正しいとわかることの難しさが同じ
    2. |K| ≧|m|⇔Pr(m)=Pr(m|c)
    3. 「鍵にヒントがない」
  2. 計算量的安全性
    1. 鍵候補から復号した平文候補の数より、平文候補の数の方が少ない
    2. |K|<|m|⇔Pr(m)<Pr(m|c)
    3. 「鍵をヒントとして使える」
    4. しかし鍵候補から正しい鍵を見つけることは現実的には難しい

実際の共通鍵暗号

  1. 現実的な鍵長
    1. 保管、配送、同期、生成が容易なサイズ
    2. 計算量的安全性を確保
    3. 平文をブロック化して |k|と|m|の差が大きくならないようにする工夫
  2. 共通規格化
  3. オープン化

DES~Data Encryption Standard~

ブロック暗号


ブロック内は対称暗号

Feistel構造


暗号化の漸化式表現

復号の漸化式表現

DESまとめ

  1. Feistel構造のまとめ
    1. ラウンド関数は式変形で消える
      1. どれだけ複雑にしても暗号化/復号可能
      2. ラウンド関数に逆関数が存在しなくてもよい
      3. 暗号化の困難さ=ラウンド関数の複雑さ
  2. ハードでの実装が単純、etc
  3. 安全性
    1. 鍵長|k|=56 。既に計算量的安全性がない
    2. 使用禁止

計算量的安全性の考察

DESを選択平文攻撃する場合の解読時間
* プロセッサの比較計算能力 10^10 個/秒
* 並列実行するプロセッサの数 10^5 個
* プロセッサの平均稼働時間 n 秒
* 全数探索の平均計算量 2^|k|/2 = 2^55

10^10 * n * 10^5 > 2^55
⇔ n > 2^55 / 10^15
⇔ n > 36.028797018963968

3DES~Tripple DES~

DES3段重ね

DESの上位互換

3DESのまとめ

  • 計算量的安全性は満たされている
  • DESとの互換性が必要な場合のみ使用
  • ほとんどの場合AESを採用すべき

AES~Advanced Encryption Standard~

デファクトスタンダード

  • 2000年に選定された対称暗号アルゴリズム
  • 安全性、速度、実装のしやすさ、etc
  • Rijndeal
  • オープン。仕様書・ソースコード完全公開
  • 「隠すことによるセキュリティ」はなし
  • 対称暗号を使う場合は普通この暗号を採用すべき

ブロック暗号

ブロック内は対称暗号

SPN構造

SubBytes

ShiftRows

MixColumns

AddRoundKey

AESのまとめ

  • 計算量的安全性は満たされている |k|=256 : 比較的マージンが高い
  • 1回のラウンドで全てのビットがかく拌される
  • 単純かつ高速
    • ラウンド内の全ての処理をビット演算で記述可能
    • 並列化可能

対称鍵暗号を使うときはAES256を使うこと

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第3章 対象暗号(p48-p79)

カテゴリー: 勉強会 | タグ: , | 暗号技術入門03 対称暗号(共通鍵暗号) はコメントを受け付けていません