このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

*目次 [#j55607a5]

#contents

*宣伝 [#l4f120f5]

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。~

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

[[&ref(http://s-akademeia.sakura.ne.jp/main/books/cipher/img/cover_mini.jpg,nolink,『暗号技術のすべて』宣伝サイト);>http://s-akademeia.sakura.ne.jp/main/books/cipher/]]

 興味がある方は[[宣伝サイト:http://s-akademeia.sakura.ne.jp/main/books/cipher/]]を参照してください。[[Amazon:https://www.amazon.co.jp/dp/4798148814/securityakade-22]]でも発売中です。


*利用モード [#g6ce21bf]

 ブロック暗号の欠点はnビット以上使えないということである。利用モードとはブロック長nのブロック暗号Eを用いて、nより長い平文M=(mSUB{1};,…,mSUB{t};)を暗号化するための技術である。もう少し厳密にいうと、長さnの(擬似)ランダム置換が与えられたときに、長さntの擬似ランダム置換を作るのが、利用モードの目的である。

 ここで、|mSUB{i};|によってmSUB{i};の長さ(ビット長)を表すことにする。特に断らない限り、|mSUB{i};|=n(ブロック長がn)とする。


**利用モードの安全性 [#vb3fe31c]

 利用モードは安全に長い擬似ランダム置換を作るのが目的である。つまり、安全な擬似ランダム置換が作れたら、その利用モードは安全といえる。

 メリットとデメリットのところで、再生攻撃に弱いといったことも言及しているが、仮に弱いとしても利用モードの安全性には実は関係がない。そもそも利用モードとは再生攻撃をするような能動的なアドバーサリーに対する安全のことを考えて設計されていないのである。だから基本的に能動的アタックに弱いといえる。しかしながら、あらゆる攻撃を考えることは、アドバーサリー脳を作る訓練としては無駄ではない。そのため、あえて言及している。

 また、通信におけるビット反転やビット欠損などの[[誤り伝播]](同期はずれ)についてを利用モードの場面で触れている解説書もある。昔はそういったことも利用モードで議論されていたが、現在の暗号理論では誤り伝播は利用モードで議論しないようになってきている。本ページで誤り伝播に触れているのは、思考訓練のためと思っておいてもらいたい。


*ECBモード [#oa6aaec1]

 ''ECB(Electronic CodeBook:電子符号表)モード''とは、次の仕様にしたがい各mSUB{i};を単純に暗号化する方式である。

[1]暗号化

 平文M=(mSUB{1};,…,mSUB{t};)に対して、cSUB{1};=ESUB{k};(mSUB{1};),…,cSUB{t};=ESUB{k};(mSUB{t};)を計算して、暗号文をC=(cSUB{1};,…,cSUB{t};)とする。

[2]復号

 暗号文C=(cSUB{1};,…,cSUB{t};)に対して、mSUB{1};=DSUB{k};(cSUB{1};),…,mSUB{t};=DSUB{k};(cSUB{t};)を計算して、平文をM=(mSUB{1};,…,mSUB{t};)とする。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ecb.jpg)
#img(,clear)

 なお、最後の平文ブロックがブロック長に満たない場合には、パディングと呼
ばれるデータの詰め物を入れる。


**ECBモードに対するアタック [#mde38597]

***同じ平文を暗号化すると同じ暗号文になる [#gda1fdc7]

 図を見てもらえればわかるように、mSUB{i};=mSUB{j};ならcSUB{i=cSUB{j};となる。つまり平文ブロックと暗号文ブロックが一対一対応の関係にあるわけだ。これは安全性
の議論に直結する。

 直観的にも安全性に問題があることがわかる。例えば、平文の中に同じ値を持つ平文ブロックが複数存在したとする。それらをブロック暗号のECBモードで暗号化しますと、同じ値を持つ平文ブロックは同じ値の暗号文ブロックに変換されてしまう。これでは暗号文全体を見るだけで、平文の中に同じ値の繰り返しがあることが推測されてしまう。というのも、本来は暗号化の結果はあたかもランダム値に見えるのが理想的であり、同じビット長の繰り返しが何度も登場する確率はほとんどありえないことである。それにもかかわらず登場しているということは、アタッカーは暗号文だけを見ただけでECBモードのような脆弱な方式などを採用していると推測できるわけだ。さらに何らかのきっかけで暗号文の一部分が判明した場合、それがきっかけとして暗号解読が行われてしまう危険性もあるわけである。

 ランダム関数・擬似ランダム関数の概念を使えば、次の図のようにもう少し数学的・暗号学的に議論できる。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ecb2.jpg)
#img(,clear)

 アドバーサリー(アタッカーと同意)のAは適当にmを作る。そして、m=mSUB{1};=mSUB{2};として、ペア(mSUB{1};,mSUB{2};)を暗号アルゴリズムMSUB{ecb};(ESUB{k};)に送信する。ここでMSUB{ecb};とはモードのMでECBを利用していることを明示する記号とする。そうすると、暗号文のペア(cSUB{1};,cSUB{2};)が送られてくる。そのときMSUB{ecb};(ESUB{k};)が本当のランダム関数ならばcSUB{1};=cSUB{2};になる確率はほとんどない。しかしMSUB{ecb};(ESUB{k};)はE
CBモードの暗号化アルゴリズムなので、cSUB{1};=cSUB{2};となる。そうするとAはDが本当のランダム関数でなく、擬似ランダム関数であると認識できる。つまり、暗
号化アルゴリズムが認識できたということはECBの暗号化は安全でないことになる。

 このように2つの同じ平文が、同じ暗号文になってしまうと、別のレイヤーの特徴と併用されて、アドバーサリーは何らかの得をすることがある。

 したがって、ECBモードはデータを暗号化する場合にはあまり用いられない。ワーク鍵を暗号化するときなどに用いられることがある。


**暗号文ブロックの操作により、復号ブロックをピンポイントで操作できる [#qd2bc93f]

***例1 [#mcc3c1b8]

 能動的アドバーサリーのMallory((受動的アドバーサリーのEveと異なり、通信を妨害したり、暗号文を書き換えたりする。語源は「malicious」(悪意のある)である。))がいたとする。

 ブロック長が8ビットと仮定する。また、3つのブロックが次のように要素に対応しているようなシステムがあったとする。

-ブロック1=送金元の銀行口座番号
-ブロック2=送金先の銀行口座番号
-ブロック3=送金額(単位は万円)

 例えば、Alice(銀行口座番号は3番)が銀行のATMを操作して、Bob(銀行口座番号は5番)に8万円を振り込みしたいとする。ATMと銀行間では上記のシステムに乗っ取り、次の平文ブロックがECBモードで暗号化されたとする。

-mSUB{1};=0011(送金元の銀行口座番号は3番)
-mSUB{2};=0101(送金先の銀行口座番号は5番)
-mSUB{3};=1000(送金額は8万円)

 これに対応する暗号文ブロックは次の通りである。暗号化アルゴリズムは平文ブロックを鍵KでXOR演算する仕組みだっとたとする。ATMと銀行は秘密に鍵K=0010を共有していて、それを使っている。

-cSUB{1};=0001(Malloryにとって、送金元の銀行口座番号は?番)
-cSUB{2};=0111(Malloryにとって、送金先の銀行口座番号は?番)
-cSUB{3};=1010(Malloryにとって、送金額は?万円)

 この暗号文を盗聴しても、Malloryは鍵Kを知らないので、どんなESUB{K};内部で何でXOR演算されているかわからない。つまり、暗号文から平文を知らない。ところが、Malloryが暗号文ブロックのcSUB{1};とcSUB{2};の内容を入れ替えて、銀行に送信する。すると、銀行側には次のようなデータが到着する。

-cSUB{1};'=0111
-cSUB{2};'=0001
-cSUB{3};'=1010

 銀行は普通に復号しようとする。鍵はK=0010なので、0010でXOR演算して復号しようとする。復号した結果、次のような値になる。

-mSUB{1};'=0101(送金元の銀行口座番号は5番)
-mSUB{2};'=0011(送金先の銀行口座番号は3番)
-mSUB{3};'=1000(送金額は8万円)

 銀行は、この復号結果から、「Bob(銀行口座番号は5番)からAlice(銀行口座番号は3番)に8万円送信する」という指示と解釈してしまう。つまり、Malloryの攻撃が悪影響を与えていることがわかる。

 単に悪影響を与えるだけなら、Malloryがstaticアドバーサリーであっても可能だが、Malloryがadaptiveアドバーサリー(完全に中間者攻撃ができる)とすると、もっと有益な攻撃ができる。Mallory自身がATMで「自分からAliceへ100万円送る」ように指示したとする。

[補足]ただし、自分の銀行口座に100万円がなかったら、別のレイヤーでチェックされることが多いので、それはクリアしておく。また、「Aliceから自分へ100万円送る」という指示は別のレイヤーでのチェックにより、できないとする。これも一般的な考え方だろう。入金者と送金元の銀行口座番号が一致しなければ、そもそも変である。

 すると、ATMは仕様にしたがって、Kの値でXORして、暗号化して銀行に送る。この通信をMalloryが一旦奪ってしまう。そして先ほどと同じように第1暗号文ブロックと第2暗号文ブロックを入れ換えて、銀行に送信する。銀行側は「AliceからMalloryへ100万円送る」という指示が来たと思ってしまう。つまり、Malloryにとって有益な攻撃が成功したといえるだろう。

[補足]Aliceの銀行口座に100万円以上存在しないと、銀行員がおかしいと気付いてしまう可能性がある。よって、Malloryは念には念を入れて、Aliceの残高を調べておくとよい。


***例2 [#x91e0b7c]

 あるコンピュータシステムのパスワードファイルが、次のようにECBモードで暗号化されていたとする。ただし、ブロック長は128ビット(=16バイト)である。

 システムの仕様は一般的に公開されているので、アドバーサリーはECBモードで暗号化されているのを知ることができるは妥当といえる。

-mSUB{1};=2C AB 90 61(ユーザー1のユーザー名)
-mSUB{2};=DD 71 26 5F(ユーザー1のパスワード)
-mSUB{3};=E1 17 62 75(ユーザー2のユーザー名)
-mSUB{4};=AF 0A 0A 75(ユーザー2のパスワード)

 アドバーサリーはmSUB{2};にmSUB{1};のデータを上書きしたとする。同様に、mSUB{4};にmSUB{1};のデータを上書きしたとする。

-mSUB{1};'=2C AB 90 61
-mSUB{2};'=2C AB 90 61
-mSUB{3};'=E1 17 62 75
-mSUB{4};'=E1 17 62 75

 パスワードファイル上すべてのユーザーがJoeアカウントになっているので、ユーザー名を列挙に成功したら、ログインさえも成功できるわけだ。


***エラーに弱い [#n287be2d]

 暗号文に1ビットのエラー(ビット反転)が起こったとして復号すると、そのエラーが1ブロック全体に拡大する。エラー率は最大n倍、平均n/2倍となる(あるビットがランダムに選んだビットと一致する確率は0.5とする)。


**ECBモードの特徴 [#g5d7ba70]

-特徴
--使うべきではない。
-メリット
--仕組みはもっともシンプル。
--暗号化・復号どちらも並列処理できる
-デメリット
--平文の中の繰り返しが暗号文に反映する。
--再生攻撃が可能。
--暗号文ブロックの削除や入れ替えによる平文の操作が可能。
--ビット単位のエラーがある暗号文を復号すると、対応するブロックがエラーになる。


*CTRモード [#p86e0291]

 ''CTR(CounTR:カウンタ)モード''とは、次の仕様にしたがい各mSUB{i};を暗号化する方式である。カウンタの役割を果たす変数c+rを利用する。

[1]暗号化

 平文M=(mSUB{1};,…,mSUB{t};)に対して、cSUB{1};=mSUB{1};+ESUB{k};(ctr+1),…,cSUB{t};=mSUB{t};+ESUB{k};(ctr+1)を計算して、暗号文をC=(cSUB{1};,…,cSUB{t};)とする。

[2]復号

 暗号文C=(ctr,cSUB{1};,…,cSUB{t};)に対して、mSUB{1};=cSUB{1};+ESUB{k};(ctr+1),…,mSUB{t};=cSUB{t};+ESUB{k};(ctr+t)を計算して、平文をM=(mSUB{1};,…,mSUB{t};)とする。ここで、DではなくEを使うことに
注意。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ctr.jpg)
#img(,clear)

 このCTRモードはECBモードから比べると若干複雑になっている。

 特徴としてまずブロックを任意の順番で暗号化・復号化できるということがいえる。これはECBモードでも同様である。この特徴は実際に暗号をプログラムとして実装したときに各々の暗号化・復号の処理を並列処理させることができることを意味する。

 また、暗号化と復号はまったく同じ構造をしている。まして復号アルゴリズムは必要なく暗号化アルゴリズムを復号処理でも利用している。つまりプログラムとして実装するときはわざわざ復号アルゴリズムに対応する関数などを用意する必要がないということである。これは次回以降紹介するOFBモードと同じストリ
ーム暗号の特徴である。

 それではECBモードのときと同様に図で考えていこう。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ctr2.jpg)
#img(,clear)

 同じ平文のペア(mSUB{1};,mSUB{2};)をMSUB{ctr};(ESUB{k};)に投げてみる。すると暗号文(cSUB{1};,cSUB{2};)が返ってくるが、CTRモードの仕様によりcSUB{1};≠cSUB{2};となる。これだけ見てもECBモードよりも安全性の意味で強くなっていることがわる。

 実はAが2SUP{n};の計算能力があれば、CTRモードは安全でないことが証明されている。しかしながら一般のコンピュータはそれほどの能力は持たないので(多項式時間しか計算できないから当たり前)、CTRモードは推奨されている。


**CTRモードに対するアタック [#f124ea2d]

***ctrが定数ならば脆弱 [#kd10585b]

***ctrを更新させると情報理論的に安全でない [#kec74158]

 CTRモードではctrを必ず違う値に更新させてしまうと、情報理論的に安全でなくなる。一方、ctrをランダムに作ると、小さい確率でctrは変わらない。そうすると情報理論的に安全になるので、ctrはランダムに作ったほうがよい。


***ランダム置換族をブロック暗号として用いると情報理論的に安全でない [#ybda1a07]

 問題を解きながら考えてみる。

問:CTRモードについて、次の設問を解け。~
(1)平文M=(mSUB{1};,mSUB{2};)に対する暗号文がC=(ctr,cSUB{1};,cSUB{2};)であった。このときのESUB{k};(ctr+1)およびESUB{k};(ctr+2)の値を求めよ。~
(2)ランダム関数族をブロック暗号として用いるCTRモードを考える。アタッカーが暗号文C=(ctr,cSUB{1};,cSUB{2};)を入手した。このとき、平文が(mSUB{1};,mSUB{2};)である確率を求めよ。~
(3)ランダム関数族をブロック暗号として用いたCTRモードは、情報理論的に安
全であることを証明せよ。~
(4)ランダム置換族をブロック暗号として用いるCTRモードを考える。アタッカーが暗号文C=(ctr,cSUB{1};,cSUB{2};)を入手した。このとき、平文が(mSUB{1};,mSUB{2};)である確率を求めよ。~
(5)ランダム置換族をブロック暗号として用いたCTRモードは、情報理論的に安
全でないことを証明せよ。

 まず(1)から解いていく。カウンターモードの暗号化では、平文M=(mSUB{1};,…,mSUB{t};)に対して、cSUB{1};=mSUB{1};+ESUB{k};(ctr+1),…,cSUB{t};=mSUB{t};+ESUB{k};(ctr+t)を計算する。わ
かりやすいように縦に並べてみる。

&mimetex("c_{1} = m_{1} \oplus E_{k} \( ctr +1 \)");~
&mimetex("c_{2} = m_{2} \oplus E_{k} \( ctr +2 \)");~
…~
&mimetex("c_{t} = m_{t} \oplus E_{k} \( ctr +t \)");

 ただし問題の中では平文はmSUB{1};とmSUB{2};だけなので実質2つの式だけしかない。

&mimetex("c_{1} = m_{1} \oplus E_{k} \( ctr +1 \)");~
&mimetex("c_{2} = m_{2} \oplus E_{k} \( ctr +2 \)");~

 ここで+はXOR演算であることを思い出す。XOR演算の特徴として同じものを
足し合わせると消えるというのがある。例えば1+1=0になるわけである。2進数
で考えればこれは明らかである。101と101をXOR演算したとする。XOR演算は0+0=
0,0+1=1,1+0=1,1+1=1であるので、101+101=000になる。

 上に列挙した中で一番最初の式を変形していく。

&mimetex("c_{1} = m_{1} \oplus E_{k} \( ctr +1 \)");~
&mimetex("c_{1} \oplus m_{1} = m_{1} \oplus m_{1} \oplus E_{k} \( ctr +1 \)"); (∵両辺にmSUB{1};をXOR演算する)~
&mimetex("c_{1} \oplus m_{1} = E_{k} \( ctr +1 \)");~
&mimetex("E_{k} \( ctr +1 \) = c_{1} \oplus m_{1}"); (∵右辺と左辺を入れ替えた)

 同様に2番目の式を変形していく。

&mimetex("c_{2} = m_{2} \oplus E_{k} \( ctr +2 \)");~
&mimetex("E_{k} \( ctr +2 \) = c_{2} \oplus m_{2} ");

 次に(2)を解く。(2)の問題文が云わんとすることは、「M=(mSUB{1};,mSUB{2};)∧
C=(ctr,cSUB{1};,cSUB{2};)」が成り立つ確率を求めなさいということである。つまり、次のよ
うに計算していくことができる。

&mimetex("Pr \( M = \( m_{1},m_{2} \) | C = (ctr,c_{1},c_{2} \) ");~
&mimetex("=Pr \( E_{k} \( ctr + 1\) = c_{1} \oplus m_{1}, E_{k} \( ctr + 2\) = c_{2} \oplus m_{2} \)");~
&mimetex("=Pr \( E_{k} \( ctr + 1\) = c_{1} \oplus m_{1} \) \cdot Pr \( E_{k} \( ctr + 2\) = c_{2} \oplus m_{2}\)"); (ESUB{K};を共有しているので、一般的に分解できない。ここでは擬似ランダム関数なので独立になり、分解できる)~
&mimetex("= \frac{1}{2^n} \cdot \frac{1}{2^n}");~
&mimetex("= \frac{1}{2^{2n}}");

 ところで、数学の問題が小さい問が連続して出題されているときは、前の問題がヒントになっていることが多い。ここでも(1)の答えを使って、上記の式変形の1つ目から2つ目に式変形していく。

 3つ目から4つ目の変換で実際に確率の計算している。前半の「Pr(ESUB{k};(ctr+1)=cSUB{1};+mSUB{1};)=1/2^n」部分を見ていく。cSUB{1};やmSUB{1};はnビットなので、それをXOR演算したcSUB{1};+mSUB{1};はnビットである。つまりcSUB{1};+mSUB{1};の総パターンは2^n通りである。これがESUB{k};(ctr+1)とちょうど一致するのは、1/2^nとなる。後半のPr(ESUB{k};(ctr+2)=cSUB{2};+mSUB{2};)=1/2^n」部分も同様に考えればよい。

 それでは(3)を解く。[[情報理論的な安全性]]ということなので、示したいことは次が成り立つことになる。

&mimetex("Pr \( M = \(m_{1},m_{2}\)\) = Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)  \)");

 ここで平文は一様分布していていることに注意しておこう。そうすると
左辺は次のように求めることができる。

&mimetex("Pr \( M = \(m_{1},m_{2}\) \)");~
&mimetex("=Pr \( M = m_{1},M=m_{2} \)");~
&mimetex("= \frac{1}{2^n} \cdot \frac{1}{2^n}");

 一方、右辺は(2)より次が成り立つことはすでに判明している。

&mimetex("Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)\) = \frac{1}{2^n} \cdot \frac{1}{2^n}");

 よって確率が等しくなったので、情報理論的に安全であることが示せた。

 次に(4)を考える。ESUB{k};は置換でctr+1≠ctr+2なので、ESUB{k};(ctr+1)≠ESUB{k};(ctr+2)となる。これは置換の性質から明らかである。置換の性質上、違う値を入れて置換すると、その結果も異なることになる。ESUB{k};(ctr+1)≠ESUB{k};(ctr+2)ということは、(1)から右
辺と左辺を書き換えることができて、cSUB{1};+mSUB{1};≠cSUB{2};+mSUB{2};になる。

&mimetex("Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)\)");~
&mimetex("=Pr \( E_{k} \( ctr+1\) = c_{1} \oplus \m_{1} , E_{k} \( ctr+2 \) = c_{2} \oplus \m_{2} \)");

 ESUB{K};は置換だから、(2)のようにPrの中を単純に分解できない。

 Pr[S]=(Sに属する場合の数)/(すべての場合の数)だから、次が成り立つ。

&mimetex("Pr \( E_{k} \( ctr+1\) = c_{1} \oplus \m_{1} , E_{k} \( ctr+2 \) = c_{2} \oplus \m_{2} \)");~
&mimetex("= \frac{ # \{E|E_{k} \( ctr+1\) = c_{1} \oplus \m_{1} , E_{k} \( ctr+2 \) = c_{2} \oplus \m_{2} \} }{# \{ E| E\in P_n \} }");

 分母は(2SUP{n};)!である。~
 一方、分子は2箇所行き先がfixされているから、次のようになる。

-&mimetex("c_{1} \oplus \m_{1} \not{=} c_{2} \oplus \m_{2}");のとき
--&mimetex("(2^n -2)!");
-&mimetex("c_{1} \oplus \m_{1} = c_{2} \oplus \m_{2}");のとき
--&mimetex("0");
---与えられているのはcSUB{1};,mSUB{1};,cSUB{2};,mSUB{2};だから、「cSUB{1};+mSUB{1};≠cSUB{2};+mSUB{2};」のときも考えなければならない。

 よって、次のように2つに場合分けができる。

[1]cSUB{1};+mSUB{1};=cSUB{2};+mSUB{2};のとき

&mimetex("Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)\)");~
&mimetex("= \frac{1}{2^{n}} \cdot \frac{1}{2^{n}-1}");

[補講]次の図のように考えてもよい。前半部で総パターンの2SUP{n};通りのうちからひとつが決定したので、後半部では総パターンから1を引いたもの総パターンになる。図にすると次のようになる。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ctr_keisan.jpg)
#img(,clear)

[2]cSUB{1};+mSUB{1};≠cSUB{2};+mSUB{2};のとき

&mimetex("Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)\)");~
&mimetex("=0");

 最後に(5)を考える。今度は(3)のようにランダム関数族ではなく、ラン
ダム置換族を使う場合である。本当の暗号ではこんなことはしないが、あくまで理解を確かめるためにあえてランダム置換族にするということである。このように条件を若干変更して、結果がどう変わってくるのかを自分で確かめるということは非常にためになる。暗号の仕様だけを追いかけていても力はなかなかつかないのだ。

 この暗号が情報理論的に安全であるには次が成り立たなければならない。

&mimetex("\forall c \in C , \forall m \in M ; Pr \( M=\(m_{1},m_{2}\)|C=(ctr,c_{1},c_{2}\)\) = Pr \( M=\(m_{1},m_{2}\) \)");

 しかし、(4)から必ずしも成り立たないので(場合分けの結果が異なっている
ので明らか)、情報理論的に安全でないことになる。

 少し解説が長くなってしまったが、どうだっただろうか? それほど難しい数学などは使っていない。あくまで「情報理論的に安全」「関数と置換の違い」「ビット列がある特定のビット列に一致するときの確率の求め方」の3つをしっかり理解しておけば、類似問題は完璧に解けることになるだろう。


***暗号文ブロックをビット反転すると、対応する平文ブロックがビット反転する [#m37df485]


**CTRモードの特徴 [#m58ae3fa]

-特徴
--現在ではCRCモードと同様によく使われる。
-メリット
--パディングがいらない。
--暗号化・復号の事前計算ができる。
--ブロックを任意の順番で暗号化・復号できる。つまり、暗号化・復号の両方において、並列処理ができる。
---並列処理による暗号化・復号が可能。つまり事前に計算しておける。
--復号アルゴリズムは暗号化アルゴリズムをそのまま利用するので、プログラムでの実装が楽。
--復号アルゴリズムとして、暗号化アルゴリズムをそのまま利用するので、プログラムの実装が楽。
---これはOFBモードと同じストリーム暗号の特徴である。
--ビット単位のエラーがある暗号文を復号すると、平文の対応するビットのみがエラーになる。
-デメリット
--能動的アドバーサリーが暗号文ブロックをビット反転すると、対応する平文ブロックがビット反転する。


*CBCモード [#zf8b3843]

 ''CBC(Cipher Block Chaining:暗号ブロック連鎖)モード''とは、次の仕様にしたがい各mSUB{i};を暗号化する方式である。

[1]暗号化

 平文M=(mSUB{1};,…,mSUB{t};)に対して、nビットの初期化ベクトルIV(Initial Value)をランダムに選び、cSUB{1};=ESUB{k};(IV+mSUB{1};),cSUB{2};=ESUB{k};(cSUB{1};+mSUB{2};),…,cSUB{t};=ESUB{k};(cSUB{t-1};+mSUB{t};)を計算して、暗号文をC=(c_1,…,c_t)とする。

[2]復号

 暗号文C=(IV,cSUB{1};,…,cSUB{t};)に対して、mSUB{1};=DSUB{k};(cSUB{1};)+IV,mSUB{2};=DSUB{k};(cSUB{2};)+cSUB{1};,…,m
SUB{t};=DSUB{k};(cSUB{t};)+cSUB{t-1};を計算して、平文をM=(mSUB{1};,…,mSUB{t};)とする。

#img(http://s-akademeia.sakura.ne.jp/main/image9/cbc.jpg)
#img(,clear)

 mとcでESUB{k};を挟んだような仕組みになっています。このESUB{k};がなければ一種の関数と見れる。


**CBCモードに対するアタック [#b861dc34]

***IVを定数にすると脆弱 [#g2f2c089]

 IVを定数(ブロック暗号の処理を施す度に)とすると安全でなくな
る。IVを定数にしてしまうと、ある平文を決まった鍵で暗号化したときと同
じになってしまい、いつも暗号文が同じになってしまう。例えばアタッカー
がターゲットの通信路をずっと監視していたとする。そのとき同じ暗号文が1週
間ごとの決まった時間に傍受したとする。通常規則性のある時間に同じ暗号文
が流れてくる確率はほとんどない。それにも関わらずそのような規則性が
あるということは、同じ平文を通信していて、しかもそれに対応する暗号文が同
じになってしまうという欠陥のある暗号を利用していると推測できる。後はこ
の情報からどんどん情報が漏れていく可能性がある。


***IVをカウンターモードにすると脆弱 [#qdfbd852]

***指定した平文ブロックのビットを反転できる [#x4ebbd13]

***エラーに弱い [#x34831ec]

 1ビット分のエラーがある暗号文を復号すると、2ブロックにその影響が広がってしまう。エラー率は最大n+1倍、平均&mimetex("\frac{n}{2}+1");倍になる。


**CBCモードの特徴 [#f1513dbb]

-特徴
--CTRモードと同様によく使われる。
-メリット
--復号のときだけ、並列処理できる。
--任意の暗号文ブロックを復号できる。
-デメリット
--暗号化のときは、並列処理できない。
--ビット単位のエラーがあると暗号文を復号すると、1ブロック全体と次のブロックの対応するビットがエラーになる。


*CFBモード [#pdc05fdd]

 ''CFB(Cipher Feed Back:暗号フィードバック)モード''とは、次の仕様にしたがい各mSUB{i};を暗号化する方式である。

[1]暗号化

 平文M=(mSUB{1};,…,mSUB{t};)に対して、nビットの初期化ベクトルIV(Initial Value)をランダムに選び、cSUB{1};=mSUB{1};+ESUB{k};(IV),cSUB{2};=mSUB{2};+ESUB{k};(cSUB{1};),…,cSUB{t};=mSUB{t};+ESUB{k};(cSUB{t-1};)を計算して、暗号文をC=(cSUB{1};,…,cSUB{t};)とする。

[2]復号

 暗号文C=(IV,cSUB{1};,…,cSUB{t};)に対して、mSUB{1};=cSUB{1};+ESUB{k};(IV),mSUB{2};=cSUB{2};+ESUB{k};(cSUB{1};),…,mSUB{t};=cSUB{t};+ESUB{k};(cSUB{t-1};)を計算して、平文をM=(mSUB{1};,…,mSUB{t};)とする。復号アルゴリズムDSUB{k};ではないことに注意。

#img(http://s-akademeia.sakura.ne.jp/main/image9/cfb.jpg)
#img(,clear)

 図から平文ブロックは暗号アルゴリズムによって直接暗号化されないというこ
とがわかる。

 CFBモードで暗号アルゴリズムが生成するビット列のことを''鍵ストリーム''と呼ぶ。CFBモードでは鍵ストリームを生成するための擬似乱数生成器として暗号ア
ルゴリズムを用いている。IVは擬似乱数生成器の種に相当する。なおESUB{k};は置換である必要がありません。

 またIVをカウンターモードにおけるctrのようにインクリメントするような設計
にしてもならない。


**1ビットCFBモード [#ma71d539]

 1ビットCFBモードは、非同期式(自己同期式)暗号となる。

 伝送中でエラーが起きたり同期がはずれたりして、シフトレジスタの内容が暗号側と復号側でずれても、少なくともnクロック経過すれば、再びシフトレジスタの内容が一致して、正常動作に戻る。



**CFBモードに対するアタック [#fb323f3f]

***再生攻撃 [#qcd39787]


***エラーに弱い [#lf20098a]

 伝送中のエラーは、エラーが復号側のシフトレジスタに残っている間影響を受け続ける。よって、エラー率は最大&mimetex("\lfloor \frac{(n-1+k)}{k} \rfloor  k+1");倍になり、平均&mimetex("\lfloor \frac{(n-1+k)}{k} \rfloor \frac{k}{2} +1");倍になる。

 特に、1ビットCFBモードの場合は、エラー率は最大n+1倍、平均&mimetex("\frac{n}{2}+1");倍に拡大される。k=1のときは、同期を取る必要はないが、処理速度は小さくなる。そのため、k=nのときと比べると、n分の1になるのである。


**CFBモードの特徴 [#gf3f8596]

-特徴
--平文ブロックは暗号化アルゴリズムで直接暗号化されない。
--CTRモードを使うほうがよい。
-メリット
--パディングがいらない。
--復号のときだけ並列処理できる。
--任意の暗号文ブロックを復号できる。
-デメリット
--暗号化のときは並列処理できない。
--再生攻撃に弱い。
--ビット単位のエラーがあると暗号文を復号すると、1ブロック全体と次のブロックの対応するビットがエラーになる。


*OFBモード [#h6981c04]

 ''OFB(Output Feed Back:暗号フィードバック)モード''とは、次の仕様にしたがい各mSUB{i};を暗号化する方式である。

[1]暗号化

 平文M=(mSUB{1};,…,mSUB{t};)に対して、nビットの初期化ベクトルIV(Initial Value)
をランダムに選び、~
zSUB{1};=ESUB{k};(IV),zSUB{2};=ESUB{k};(zSUB{1};),…,zSUB{t};=ESUB{k};(zSUB{t-1};)~
cSUB{1};=mSUB{1};+zSUB{1};,cSUB{2};=mSUB{2};+zSUB{2};,…cSUB{t};=mSUB{t};+zSUB{t};~
を計算して、暗号文をC=(cSUB{1};,…,cSUB{t};)とする。

[2]復号

 暗号文C=(IV,cSUB{1};,…,cSUB{t};)に対して、~
zSUB{1};=ESUB{k};(IV),zSUB{2};=ESUB{k};(zSUB{1};),…,zSUB{t};=ESUB{k};(zSUB{t-1};)~
mSUB{1};=cSUB{1};+zSUB{1};,mSUB{2};=cSUB{2};+zSUB{2};,…,mSUB{t};=cSUB{t};+zSUB{t};~
を計算して、平文をM=(mSUB{1};,…,mSUB{t};)とする。復号アルゴリズムDSUB{k};ではないことに注意。

#img(http://s-akademeia.sakura.ne.jp/main/image9/ofb.jpg)
#img(,clear)

 図から平文ブロックは暗号アルゴリズムによって直接暗号化されないというこ
とがわかる。平文ブロックと暗号アルゴリズムの出力とをXOR演算して、暗号
ブロックを作り出す。OFBモードはこの点でCFBモードに似ている。

 IVは暗号化の度ごとに異なるランダムビット列を用いるのが普通である。なおESUB{k};は置換である必要はない。


**OFBモードとCFBモードの比較 [#aab0b2ab]


**OFBモードに対するアタック [#uc4196e0]

***IVが固定なら脆弱 [#pb83187f]

***IVがctrでも脆弱でない [#wca1cfe7]

 ESUB{K};はランダム関数なので、IVがカウンターであっても大丈夫である。つまり脆弱でない。

***IVが書き換わってしまうと、すべて暗号文ブロックの復号に失敗する [#aee4410d]

***事前計算結果を盗まれたら、平文すべてを知られてしまう [#kdd16b39]

***暗号文ブロックをビット反転すると対応する平文ブロックがビット反転する [#ga85c156]


**OFBモードの特徴 [#x4ba3816]

-特徴
--平文ブロックは暗号化アルゴリズムで直接暗号化されない。
---平文ブロックと暗号化アルゴリズムの出力とをXOR演算して、暗号文ブロックを作り出す。OFBモードはこの点でCFBモードに似ている。
-メリット
--パディングがいらない。
--復号アルゴリズムとして、暗号化アルゴリズムをそのまま利用するので、プログラムの実装が楽。
--暗号化と復号の事前計算が可能。
--ビット単位のエラーがある暗号文を復号すると、平文の対応するビットのみがエラーになる。つまり、ビット反転に強い。
-デメリット
--並列処理ができない。
--能動的アドバーサリーが暗号文ブロックをビット反転すると対応する平文ブロックがビット反転する。


*各種利用モードの比較 [#f47013f8]

 以上でブロック暗号の主要な利用モードのすべての解説が終った。実際にブロック暗号を設計するときはCBCモード・CTRモードの使用が推奨され
ている。実際にインターネットではCBCモードがよく登場している。

 最後に関連する定理を少しだけ紹介する。

[定理]~
ECBモード以外の各モードは、{ESUB{k};}が擬似ランダム置換族であると仮定すると、選択平文攻撃に対して安全である。

[定理]~
CTRモードが最も安全である。


*参考文献 [#u171d77c]

-ゼミノート
-『現代暗号の基礎数理』
-『暗号理論入門』
-『暗号技術入門-秘密の国のアリス』