バックアップTweet追加された行はこの色です。削除された行はこの色です。当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。興味がある方は[[宣伝サイト:http://s-akademeia.sakura.ne.jp/main/books/cipher/]]を参照してください。[[Amazon:https://www.amazon.co.jp/dp/4798148814/securityakade-22]]でも発売中です。Code)''とはメッセージを認証するための仕組みである。アドバーサリーによるなりすましやメッセージの改ざんを防止することが目的である。実はメッセージ認証は暗号化に劣らず重要といえる。暗号化が必要ない場合であっても、そのメッセージが信頼できるものであることは常に確かめることができなければならないからである。MACは[[デジタル署名]]に対応するセキュリティ機能を実現するものである。チェックできるが、MACの場合は正真性・認証しかできない。-MAC--共通鍵暗号系用--正真性・認証をチェックできる。MACは2つのアルゴリズムである、鍵生成アルゴリズムGと認証子生成アルゴリズムSで表される。次にMACの仕組みを示す。1:送信者と受信者はGで生成された秘密鍵Kを共有しておく。ここでのセキュリティパラメータkとはビット長を意味する。ここは共通鍵暗号系での暗号化のときと同様に一番最初に必要な準備である。共通鍵暗号系の安全性はこの鍵配送に強く依存しているが、MACの場合でも同様である。2:次に送信者はKを利用して、メッセージMに対する認証子(MAC値)Tagを生成して、ペア(M,Tag)を受信者に送る。3:受信者は(M,Tag)を受け取ったら、Kを利用して(M,Tag)の正当性をチェックする。受信者が納得(accept)してしまうような(M,Tag)を敵が生成してしまうことを偽造と呼ぶ。一般に鍵Kを求めるよりも、偽造するほうが容易である。暗号設計者はKを求められないことは当然だが、偽造すら不可能であるようなMACを構成する必要がある。鍵Kを知らずに検証式を満たすような(M,Tag)を作れないとき、MACは安全であるという。敵の最も単純な攻撃方法は、送信者が送信した(M,Tag)を何も見ずに偽造を試みることである。強力なアドバーサリーの攻撃方法は、選択メッセージ攻撃がある。選択メッセージ攻撃とは何らかの方法で複数のメッセージと認証子の組を入手し、その情報を偽造することである。選択メッセージ攻撃のモデルは、メッセージMSUB{1};,...,MSUB{q};を自由に選んで、それに対応する認証子を入手できる状況において偽造を試みると考えることができる(図4参照)。M_q");であるような(M,Tag)を偽造できたとき、敵は偽造に成功したことになる。[定義]~アドバーサリーが偽造できる確率が無視できる程度に小さいとき、そのMAC方式は''選択メッセージ攻撃に対して安全である''という。MACは[[ブロック暗号]](あるいは[[鍵付きハッシュ関数]]((通常のハッシュ関数はメッセージだけを入力として計算できるが、鍵付きハッシュ関数はメッセージの他に秘密鍵も知らないと計算できない)))を利用して実現できる。情報の作成者と検証者が互いに共有している秘密鍵を利用してMACの作成や検証を行う。秘密鍵を知らなければMACの生成も検証もできないが、検証者が正しいMACを作ることは可能なので、作成者と検証者が互いに信用できなければならない方式といえる。[[ブロック暗号の利用モード]]には数種類が存在する。その中でも安全な部類に入るのは、CBCモードとCTRモードである。MACではCBCを用いた方式が使われている。それがCBC-MACである。他にはいくつか種類がある。CBC-MAC方式はブロック暗号の利用モードのひとつであるCBCモードを利用して実現した方式である。m_t)");として、各iにおいて|mSUB{i};|=n(mSUB{i};はnビット長であることを意味する)であるとする。このときCBC-MAC方式は次のように記述される。鍵はブロック暗号の鍵Kとして、認証子生成アルゴリズムは次のように計算する。最後に認証子をTag=cSUB{t};とする。各メッセージの長さtが一定の場合、CBC-MAC方式は選択メッセージ攻撃に対して安全であることが証明されている。異なる長さのメッセージを許すとき、即ち可変長の場合は簡単に偽造されてしまう。その偽造例を次に示す。アドバーサリーはnビット長のmに対する認証子Tagを入手したとする。次に、M'=(m,m+Tag)すれば、(M',Tag)というメッセージと認証子のペアでCBC-MACの検証式を通過して受信者にacceptさせてしまうことができる。アドバーサリーがMにm+Tagを付加させると、受信者は次のように計算するはずだからである。Tag'がTagと一致すれば受信者はacceptする。Tag'=Tagを導くことが目標となる。よって、敵は偽造に成功したことになる。例1:M=(mSUB{1};,mSUB{2};)に対する認証子がTagであったとする。\}^n");である。この情報を利用して偽造してみる。CBC-MACの構造に仮定を満たすように書き下していく。すると次の関係式が成り立つ。このとき、アドバーサリーはM'=(m1,m2,m1+Tag,m2)を偽造すればうまくいく。これは先ほどの結果から推測するわけだが、ここではm1とm2の2つあるから少し複雑になっていることに注意。それでは、これが本当に偽造に成功しているかを示す。M'に対してCBC-MACの仕組みを適用させる。すると、次が成り立つ。最終的にTag'=Tagが確認できたので偽造成功である。[#jbdd2cb8][問題]~ブロック暗号がランダム置換族である場合を考える。M=(mSUB{1};,mSUB{2};)に対する認証子をTag、M'=(mSUB{1};',mSUB{2};')に対する認証子をTag'としたとき、Tag=Tag'となる確率を求めよ。MとM'の関係について場合分けして考えよ。M,M'それぞれにおいて、2番目の暗号化アルゴリズムESUB{K};への入力は次のようになる。よって、Tag=Tag'となる必要十分条件は次が成り立つときである。○」と見ると、左辺の2つの□は(mSUB{1};,mSUB{1};')というペアの入力、右辺の2つの○は出力を考えることができる。そこで次のように4つに場合分けする。このときmSUB{1};≠mSUB{1};'は起こりえない。よって、Pr[Tag=Tag']=0である。このとき必ずTag≠Tag'となる。よって、Pr[Tag=Tag']=0である。次図のように考えて、(*)を満たすパターンの総数を求める。ポイントは(*)という式に縛られてる状態での総数ということである。これは普通に代入してもわかるように、(*)は0SUP{n};=0SUP{n};となり、常に成り立つ。[#c72f3848][問題]~M=(mSUB{1};,mSUB{2};)に対する認証子をTag、M'=(mSUB{1};',mSUB{2};')に対する認証子をTag'としたとき、Tag=Tag'となる確率が1/2であった。このとき{E_K}は擬似ランダム置換族でないことを証明せよ。{0,1}SUP{n};上の置換πをオラクルとする識別アルゴリズムDを次のように構成する。DはまずπをCBC-MAC方式の暗号アルゴリズムとして利用して、Mに対する認証子Tag、M'に対する認証子Tag'を求める。このときTag=Tag'ならDSUP{π};=1、Tag≠Tag'ならDSUP{π};=0とする。このときπが{ESUB{K};}からランダムに選ばれていると仮定すると、次のようになる。πがランダム置換族PSUB{n};からランダムに選ばれているときは、練習問題の問1の結果より次のようになる。よって、Dのアドバンテージは次のように計算できる。ゆえに{ESUB{K};}は擬似ランダム置換族ではないことがわかる。[#gc28a6f8]-64ビットブロック暗号である[[DES]]の場合は、MAC長が16〜64ビットとなる。-擬似乱数生成器によって生成されたひとつの秘密鍵を用いることとし、他の目的の秘密鍵と共有してはならない。各メッセージの長さtが一定の場合、CBC-MAC方式は選択メッセージ攻撃に対して安全であることが証明されている。EMAC方式は可変長のメッセージに対しても安全なMAC方式である。ブロック暗号の鍵が2つ必要という特徴を持つ。EMAC方式はCBC-MAC方式における認証子を新しい鍵K2で暗号化して認証子Tagを生成する。各メッセージの長さがブロック長nの整数倍であると仮定する。このときEMAC方式は選択メッセージ攻撃に対して安全であることが証明されている。CMAC方式はブロック暗号の鍵がひとつですみ、メッセージ長がブロック長nの整数倍である必要がないという特徴を持つMAC方式である。鍵はブロック暗号の鍵Kとして、認証子生成アルゴリズムはまず次のように計算する。m_t)");に対して次のように計算する。最後に認証子を次のように求める。|=n");となるように選びます(||は連結を意味する)。uは拡大体GF(2SUP{n};)上の特定の要素であり、「・」はGF(2SUP{n};)上の乗算を表す。L・uSUP{-1};に置き換えても、安全性・効率はほぼ同じになる。以上を図にすると次のようになる。それほど大きく変わらない。そのため、現在では依然としてCBC-MAC方式が使われているが、今後はCMAC方式に移行していくと思われる。[#p2f7a875]-MAC長はブロック暗号のブロック長-擬似乱数生成器によって生成されたひとつの秘密鍵を用いることとし、他の目的の秘密鍵と共有してはならない。CMAC方式は任意の可変長のメッセージにおいて、選択メッセージ攻撃に対して安全であることが証明されている。あることが確認されている。[#a0dc77ea]-ゼミノート-『現代暗号の基礎数理』-。