[-]=======================================================================[-] Wizard Bible vol.28 (2006,9,6) [-]=======================================================================[-] x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第0章：目次 --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○第1章：マニアックJavaプログラミング第四回 金床 著 ○第2章：ニューラルネットワーク　ひとつのニューロンの学習 Defolos 著 ○第3章：Windows File Protection Hacking Kenji Aiko 著 ○第4章：基礎暗号学講座 〜 第3回 〜 IPUSIRON 著 ○第5章：お知らせ ○第6章：著者プロフィール x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第1章: マニアックJavaプログラミング第四回: 〜 実用速度で使うXMLEncoder/Decoder 〜 --- 著者：金床 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　筆者はXMLが大嫌いである。XMLはおそらくHTMLのウェブでの成功を受けて出て きたものであるが、HTMLはいわゆるデザイナー系の人に受け入れられはしたもの の、プログラマー系の人にはそれほど高くは評価されていないのではないか。 　XMLをデータの保存形式として使うのは、場合によっては悪くない。特に階層構 造を保存する場合には適しており、筆者もNoFTP@JUMPERZ.NETというFTPクライア ントを開発した際に、階層構造を持つブックマークの保存形式としてXMLを選択し た。 　うんざりするのは、サーバーなどの設定ファイルがXML形式である場合だ。特に オープンソースのJavaプロダクトにはこの傾向が顕著で、Tomcatを初め数多くの プロダクトが設定ファイルをXML形式としている。ここで一つ、筆者を凍り付かせ た設定ファイルの一部を紹介しよう。 ----- abs audio/x-mpeg ai application/postscript aif audio/x-aiff aifc audio/x-aiff aiff audio/x-aiff aim application/x-aim art image/x-jg …以下えんえんと続く ----- 　これはTomcatの設定ファイルであるweb.xmlの一部である。ごちゃごちゃしてい て分かりにくいので、タグ部分を全部消してみよう。すると次のようになる。 ----- abs audio/x-mpeg ai application/postscript aif audio/x-aiff aifc audio/x-aiff aiff audio/x-aiff aim application/x-aim art image/x-jg ----- 　すっきりして、何が行われているか分かるようになる。Apacheなどの設定を行 った経験があればピンとくるだろう。これはファイルの拡張子とそれに対応する MIMEタイプの一覧の一部である。Apacheではmime.typesというファイル名で次の ように記述される。この方がはるかにわかりやすい。 ----- image/x-cmu-raster ras image/x-portable-anymap pnm image/x-portable-bitmap pbm image/x-portable-graymap pgm image/x-portable-pixmap ppm image/x-rgb rgb image/x-xbitmap xbm image/x-xpixmap xpm image/x-xwindowdump xwd ----- 　このように、階層構造でもない大量のデータが並ぶ場合、XMLの使用はあまりに も冗長であり、無駄や重複を嫌うプログラマの神経を逆撫でするのである。また、 XML形式というのはプログラムにとっては読み書きしやすい形式だが、人間が直接 テキストエディタで読み書きするのには向いていない。特に、一部のタグの対応 がずれてしまった場合にファイル全体に影響が出してしまう点などは非常にいた だけない。 　XMLを人間が編集する必要がある場合、専用の使いやすいエディタなどがあれば 良いが、サーバーの設定ファイルというのはターミナルしか使えないなどの不便 な環境で編集する必要がでてくるものなので、XML形式ではなく、例えばviのよう なシンプルなエディタでも問題なく扱える形式が好ましい。 ■0x02.) オブジェクトの保存 　さてJavaでは、オブジェクトをファイルに保存するための手軽な方法が2つ用意 されている。ひとつはシリアライゼーション、もうひとつがXMLエンコード（とデ コード）である。どちらもストリームに対してオブジェクトを読み書きできるよ うに設計されているため、ファイルストリームを指定すればファイルへの読み書 き、つまりデータとしての保存が可能になる。また、ソケットストリームなどを 指定すればネットワーク越しにオブジェクトをやりとりすることが可能だ。 　シリアライゼーションはJDK1.1の頃から存在する、古くよく知られた手法だ。 具体的にはObjectInputStreamクラスとObjectOutputStreamクラスを使う。この方 法の欠点は読み書きの対象となるクラスの定義の変更に弱いことだ。ある時点で オブジェクトをファイルに書き出したとする。その後ソフトウェアがアップデー トされ、クラスの定義が変更されてしまうと、もはや過去に保存したファイルか らは正しくオブジェクトを再構築することができないのである。 　この欠点に対処する方法は存在するものの、手間がかかる上に本質的でないた め、オブジェクトの保存にシリアライゼーションを使うことは推奨できない。 　もう一方のオブジェクトの保存方法であるXMLエンコードは、JDK1.4で登場した、 比較的新しい方法である。シリアライゼーションでの失敗の経験を元に、クラス の変更に強い作りになっている。 　シリアライゼーションがバイナリ形式の出力を行っていたのに対し、XMLエンコ ードはその名の通りオブジェクトをXML形式として出力する。例えば次のようなコ ードを見てみよう。 ----- XMLEncoder e = new XMLEncoder( System.out ); e.writeObject( new JButton( "hoge" ) ); e.close(); ----- 　このコードの出力は次のようになる。 ----- hoge ----- 　このようにオブジェクトをXML形式で吐き出すことが可能になる。逆にこのXML をXMLDecoderで読み込めば、オブジェクトを復元できる。 ■0x03.) XMLEncoder/Decoderの特徴 　XML形式でオブジェクトを読み書きするためには、 ・クラスがデフォルトコンストラクタをもつ ・保存したいプロパティ（フィールド）について、ゲッターとセッターを持つ 　という条件を満たせば、とりあえずはよい（厳密な定義についてはXMLEncoder のjavadocを参照）。いわゆるJavaBeansと呼ばれるスタイルだ。この条件は簡単 に満たせるだろう。 　エンコードとデコードはこのゲッターとセッターによって行われるため、実際 には内部に存在しないプロパティ（のようなもの）を読み書きすることもできる。 つまりオブジェクト指向プログラミングらしく、外部に公開するインターフェー ス（ゲッターとセッター）と、内部の実装を完全に分離できるのだ。このため非 常に柔軟なプログラミングが可能となる。 ■0x04.) 書き出しは遅い 　ある程度のボリュームのあるクラスのインスタンスをいくつか連続で書き出し てみると分かるが、XMLEncoderのエンコード処理は非常に遅い。特に悲劇的なの がbyte型の配列などを書き出すときだ。 　なぜ遅いのかというと、配列の要素全てを次のようにXMLとして書き出している からである。 　例えば配列が次のようなものだったとすると ----- byte[]{ ( byte )0x01, ( byte )0x02, ( byte )0x03, ( byte )0x04 } ----- 　次のようにXMLにエンコードされるのだ。 ----- 1 2 3 4 ----- 　めまいを覚える読者もいるのではないだろうか。 　たった4byteのデータを保存するために、なんと285byteも使っているのだ。つ まり処理速度が遅いばかりでなく、吐き出されたデータが非常にスペースを取る という、2重にデメリットを持つ構造になっているのである。もちろんいちおうメ リットもあって、保存されたデータをテキストファイルやプログラムなどで変更 しやすいという面も持つ。 ■0x05.) パフォーマンスチューニング 　さてここからがマニアックプログラミングとなる。このbyte配列の書き出しは あまりにも遅いため、100byteや1000byte単位のデータを扱うプログラムでは、X MLEncoderの使用は実用的ではない。しかし、オブジェクトのファイルへの保存の ために、クラスごとにいちいちエンコーダーとデコーダーを書くのも面倒だ。ま た、パフォーマンスの問題を抜かせば、変更に対する強さなど、XMLEncoder/Dec oderの動きは非常に魅力がある。そこで、次のようにする。 　まず、ここでは読み書き対象のクラスの例として、byte配列のプロパティbuff erを持つMHogeクラスを考える。このクラスの定義は以下のようなものだ。 ----- public class MHoge { private byte[] buffer = new byte[]{}; //-------------------------- public byte[] getBuffer() { return buffer; } //-------------------------- public void setBuffer( byte[] b ) { buffer = b; } //-------------------------- } ----- 　問題となるのはbyte配列の書き出しなので、これを避けることにする。しかし byte配列に対するゲッター・セッターは定義されており、それらは様々なプログ ラムの中で使われているため、当然ながら削除することはできない。そして、XM LEncoderは必ずゲッターを呼び出してしまう。ではどうすればよいだろうか。 　XMLEncoderから呼び出される場合、つまりオブジェクトを書き出す場合のみ、 空の配列を返すようにするのである。具体的にはクラスにフラグを一つ持たせ、 そのフラグがonの間はXMLEncode/Decodeが行われると考え、byte配列のプロパテ ィに関するゲッター・セッターは何もしない。変更後のMHogeクラスのコードは次 のようになる。 ----- public class MHoge { boolean xmlFlag = true; private byte[] buffer = new byte[]{}; //-------------------------- public void setXmlFlag( boolean b ) { xmlFlag = b; } //-------------------------- public byte[] getBuffer() { if( xmlFlag ) { return new byte[]{}; } else { return buffer; } } //-------------------------- public void setBuffer( byte[] b ) { if( !xmlFlag ) { buffer = b; } } //-------------------------- } 　xmlFlagがtrueの場合はgetBuffer()は空のbyte配列を返すため、処理はすぐに 終わる。 　しかし、この状態では当然ながら、肝心のbufferの内容がXMLとして吐き出され ない。オブジェクトの状態を保存・復元するという本来の目的が達成されないの である。 　問題はbyte配列の要素ひとつひとつをいちいちタグで囲んで出力するという点 にあった。そこで、これを、一つのデータの固まりとしてまとめて出力・入力す るようにしてしまえばよい。そこでbyte配列であるbufferをStringクラスとして 出力・入力するためのgetBufferString()及びsetBufferString()メソッドを定義 する。 ----- public class MHoge { boolean xmlFlag = true; private byte[] buffer = new byte[]{}; //-------------------------- public void setXmlFlag( boolean b ) { xmlFlag = b; } //-------------------------- public byte[] getBuffer() { if( xmlFlag ) { return new byte[]{}; } else { return buffer; } } //-------------------------- public void setBuffer( byte[] b ) { if( !xmlFlag ) { buffer = b; } } //-------------------------- public String getBufferString() { return MStringUtil.byteToHexString( buffer ); } //-------------------------- public void setBufferString( String s ) { buffer = MStringUtil.hexStringToByteArray( s ); } //-------------------------- } ----- 　ここでMStringUtilクラスにはbyte配列とStringクラス型のオブジェクトの変換 を行うメソッドが定義されているものだ。中身は次のようになっている。 ----- public static final String byteToHexString( byte[] data ) { StringBuffer strBuf = new StringBuffer( data.length * 2 ); int length = data.length; for( int i = 0; i < length; ++i ) { int j = data[ i ]; if( j < 0 ) { j += 256; } String tmpStr = Integer.toHexString( j ); if( tmpStr.length() == 1 ) { strBuf.append( "0" ); } strBuf.append( tmpStr ); } return strBuf.toString(); } //----------------------- public static final byte[] hexStringToByteArray( String s ) { byte[] array = new byte[ s.length()/2 ]; for( int i = 0, j = 0; ( i + 1 ) < s.length(); i+=2, j++ ) { int k = Integer.parseInt( s.substring( i, i + 2 ), 16 ); array[ j ] = ( byte )k; } return array; } ----- 　次のようなコードでMHogeクラスのオブジェクトをエンコードする。エンコード の前後でフラグを変化させている。 ----- MHoge hoge = new MHoge(); hoge.setXmlFlag(false); hoge.setBuffer( new byte[]{ ( byte )0x01, ( byte )0x02, ( byte )0x03, ( byte )0x04 } ); hoge.setXmlFlag(true); XMLEncoder e = new XMLEncoder( System.out ); e.writeObject( hoge ); e.close(); hoge.setXmlFlag(false); ----- 　出力は次のようになる。 ----- 01020304 ----- 　bufferStringとして「01020304」というデータが出力されており、byte配列が まとめてひとつのデータとして読み書きされることが確認できる。 　1000byte単位のデータになると、この方法によってパフォーマンス的には何倍 ・何十倍も速く処理が行われることになり、byte配列のプロパティを持つクラス に対してXMLEncoder/Decoderを実用するための解としてこのような方法もあると いうことがわかる。 ■0x06.) まとめ 　この方法のメリットは、XMLEncoder/Decoderを利用することで、クラスごとに エンコーダー・デコーダーを作ることを避けることができる点にある。デメリッ トとしては、クラスに少し変更を加える必要がある点があげられる。しかしこの 変更は決まり切ったパターンに沿って行えばよいものなので、一度理解してしま えばバグを入れ込む可能性は殆どない。 　かなり急ごしらえで考えた仕組みなので、他にも良い解決方法があるはずだ。 例えばXMLEncoder/Decoderのような働きをし、かつ高速なものを作るという解な どもあるだろう。 　筆者は現在開発中のDoorman@JUMPERZ.NETというソフトウェアで、HTTPセッショ ンのデータのエンコード・デコードにこの方法を利用している。また、XMLだとど うしてもファイルのサイズが大きくなってしまうので、gzip圧縮を併用している。 　XMLは嫌いなのだが、XMLEncoder/Decoderはとても便利でおすすめできる機能だ。 ただし処理速度は非常に遅いので、環境によっては（たとえこの方法を使っても） 実用が難しいかもしれない。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第2章: ニューラルネットワーク　ひとつのニューロンの学習 --- 著者：Defolos x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　こんにちは、Defolosです。今回はニューラルネットワークについてまとめてみ たいと思います。 　ニューラルネットワークはパーセプトロンとバックプロパゲーションがひとつ の区切りとなるように思えるのですが、今回はそのパーセプトロンやバックプロ パゲーションの部分の解説を読むのに必要と思われる前提知識的な部分をまとめ てみました。 　私自身が現在勉強中の分野ですので、間違いや不適切な表現などは多いと思い ますが、雰囲気をつかむ、間違いを指摘して学習するなどに役立てば幸いです。 間違いをみつけてくださったらDefolos宛（defolos@ruffnex.oc.to）にメールし ていただければ嬉しいです。 ■0x02.) ニューラルネットワークとは 　ニューラルネットワークとは、生物の脳に見られるような神経回路のことです。 情報技術では、この生物の神経回路を手本にした人工ニューラルネットワークが 様々なところで応用されています。このレポートでは生物ニューラルネットワー クいついても言及しますが、人工ニューラルネットワークを主に解説して行きま すので、以降は特に注意がない限り人工ニューラルネットワークをニューラルネ ットワークと略します。 　ニューラルネットワークは人工知能へのアプローチとして応用されており、パ ターン認識や制御を得意とし、組み合わせ最適化の解である非線形関数を近似す る手段のひとつとして位置付けられるようになりました。また、学習できるとい う特性によって応用範囲は広範囲に広がっています。 ■0x03.) 生体ニューロンの仕組み 　ニューラルネットワークは先述の通り、生物の脳をモデルにした情報処理シス テムです。それゆえに、ニューラルネットワークを理解していくには、まず生体 のニューロンの仕組みを理解することからはじめるべきでしょう。 ●脳の構成要素 　生体の脳は数百億のニューロンと多数のグリア細胞から成り立っており、ニュ ーロンは層状に規則的に並んでいます。ニューロンは電気信号を発し、処理し、 伝達して認知や推論など複雑な仕事をこなしています。ニューロンは次の図のよ うな構造をしています。以降の説明は図を参照しながら閲覧ください。 （図）http://ruffnex.oc.to/defolos/text1/figure/neuron.jpg（※1） 　ニューロンは樹状突起、細胞体、軸索と呼ばれる部分に大別することができま す。軸索は細胞体から一本だけ伸びており、末端で枝分かれして他の樹状突起と 結びつきます。この結び目のことをシナプスと呼びます。これらのニューロンの 周りを取り囲むように無数のグリア細胞が存在しています。 ・細胞体（Soma） 　ニューロンの本体といえる部分。その内部には核やミトコンドリアなどを持ち、 通常の細胞と構造自体は変わらない。ニューラルネットワークにおいては信号を 他のニューロンに出力するかどうかの処理装置となる。 ・樹状突起（Dendrite） 　細胞体から伸びだした多数の枝のような部分で、ニューロンの入力端子にあた る。 ・軸索（Axon） 　細胞体から伸びだしている太い軸のようなもので、先端で枝分かれして他のニ ューロンと結びついている。ニューロンの出力端子にあたる。先端は樹状突起と 結びつき、シナプスを形成する。 ・シナプス（Synapse） 　他のニューロンをつなげる役割をする。樹状突起はシナプスを通して軸索と接 続され、他のニューロンから入力信号を受け取っている。また、シナプスの伝達 効率はそれぞれ異なっている。 ●グリア細胞の役割 　グリア細胞はニューロンの10倍以上存在しています。ニューロンの情報伝達機 能とは直接的な関係はありませんが、ニューロンがネットワークを広げていく過 程、またはニューロンの存続において大きな役割を果たします。言うならばグリ ア細胞はニューロンを縁の下からサポートする役割を持っていると言ってよいで しょう。最近の研究で脳の情報伝達において無視できない役割を果たすことがわ かってきたようです。 　グリア細胞のグリアとはギリシャ語で「膠：にかわ」を意味する言葉です。ニ ューロンにまとわりつくように存在しているため、このような名称となったと思 われます。グリア細胞は性質の異なるいくつかの細胞を総括して使われる名称で す。グリア細胞には次のような種類があります。 （図）http://ruffnex.oc.to/defolos/text1/figure/glia.jpg（※2） ・星状グリア細胞（Astroglia） 　無数の突起を持った星型の形をしており、ニューロンと毛細血管の間に存在す る。血管から養分や酸素などをニューロンに供給する役割を持つ。脳神経系で最 も多い。 ・稀突起グリア細胞（Oligodendroglia） 　突起は少なく、軸索に巻きついて髄鞘（ミエリン鞘）を形成する。髄鞘は絶縁 体の鞘であり軸索を保護する役割を持っている。この髄鞘のおかげで他の軸索の 電気信号が混ざらないようになっている。電気信号の伝達速度を向上させる。 ・ミクログリア（Microglia） 　血管の近くに存在する。詳しい性質は不明な点が多いが、脳におけるマクロフ ァージであると考えられている。防御機能をもつ。 　ニューロンのネットワークを、あるニューロンが他の決まった標的となるニュ ーロンと結合した構造の集まりであると考えると、ネットワークが作り出される ためにはニューロンの細胞体から軸策が伸びていくことと、この過程が正しい標 的のニューロンに向かうことが必要となります。 　ニューロンはグリア細胞から分泌される神経栄養因子やニューロンの表面にあ る細胞接着分子のガイドにより、軸索を伸ばし、正しい相手に到達して結合しま す。このときニューロンと周囲のグリア細胞との間で情報のやり取がおこなわれ ます。ニューロン内では新しい遺伝子が発現し、特定の酵素が働いてニューロン の骨格が変化します。このように生体のニューラルネットワークにおいてグリア 細胞は大きな役割を持っています。 ●信号とその伝達 　生体の脳は電気信号を伝達し、複雑な処理を行っています。コンピュータと動 作原理は同じですが、その性質は大きく異なります。コンピュータは高速な処理 素子を使い直列処理に長けていますが、一方生体の脳は処理素子の速度は非常に 低速ですが超並列化された構造を持っています。これがよく言われるようなコン ピュータの高速正確、脳の創造曖昧の違いを生み出していると言ってよいでしょ う。 　コンピュータはトランジスタなどが信号を流す流さないというスイッチング処 理を行っています。生体のニューロンにも、トランジスタのようなスイッチング を行う仕組みがあります。 ○膜電位 　動物の細胞は細胞膜で覆われています。ニューロンの構造も通常の細胞と同じ く、細胞膜を持っています。細胞は細胞膜で外部と細胞内が仕切られているので、 外部と内部では電圧が異なります。細胞内部から見た外部との電圧の差（電位） を膜電位と呼び、膜電位は-70〜-90mvです。つまり通常の場合、細胞内は細胞の 外側より70〜90mv電圧が低くなっています。この電位の差を静止電位（Resting Potential）と呼びます。 　他のニューロンからの出力信号を樹状突起を通して受信すると膜電位に変化が おきます。膜電位が静止電位（-70mv前後）から0のほうへ変化する脱分極（Depo larization）がおきます。脱分極があまり大きくならないうちに入力信号がスト ップすると元の電圧に戻ってしまい、軸索には何も出力されません。しかし、あ る一定の大きさを超えると100mvほどのパルスが1m秒ほど発生し、軸索を通して他 のニューロンに出力信号として伝えられます。このパルスは活動電位（Action P otential）やインパルス（Impulus）、スパイク（Spike）と呼ばれます。活動電 位が発生することをニューロンが発火すると表現します。 　一定の大きさを閾値電位（Threshold Potential）と呼び、ニューロンの場合は 15〜20vmに設定されています。シナプスには興奮性のものと抑制性のものとがあ ります。興奮性のものは膜電位を上昇させ、抑制性のものは逆に膜電位を低下さ せます。まとめると、膜電位が他のニューロンからの入力信号によって15〜20mv ほど高くなると、100mvほどの活動電位が発生し他のニューロンへの出力信号とな ります。 ○髄鞘における電気信号の伝達 　髄鞘は前述の通り、稀突起グリア細胞によって形成される絶縁体で、軸索を保 護しています。稀突起グリア細胞ひとつで髄鞘ひとつを形成していますが、グリ ア細胞から形成される髄鞘と髄鞘の間には小さな隙間があり軸索が露出していま す。この隙間をランビエ絞輪といい、ニューロンから発せられる電気信号は隙間 から隙間へ絶縁体である髄鞘を飛び越えて伝わります。 ○シナプスでの伝達 　シナプスはシナプス間隔という極小さい隙間が存在しており、電気信号はこの 隙間を飛び越えることはできません。ここで電気信号は一旦化学的信号に変換さ れます。 　電気信号がシナプスに到達すると、この電気信号によりシナプス小胞からアセ チールコリンやドーパミンなどの化学物質（神経伝達物質）がシナプス間隔へ放 出されます。シナプス後膜にあるチャネルや受容体がそれらの神経伝達物質を受 け取ることで細胞内のイオン濃度が変化し、電気信号が引き起こされます。つま り、信号は電気信号→化学的信号→電気信号のように伝達されます。これにより 100mvと高い電圧を持つ活動電位が流れても、他のニューロンに到達するときには 流れたのか流れてないのかの2値（デジタル）として取り扱われることになります。 ■0x04.) ニューロンモデル 　生体のニューロンの仕組みは非常に複雑ですので、そのまま忠実に再現して情 報の処理を行うのは不可能です。そこで生体ニューロンの仕組みを本質を取りこ ぼすことなく簡単に表現したものを利用します。このような本来複雑な仕組みを 簡単に表現したものをモデルと呼びます。 ●ニューロンのモデル化 　情報科学では、生体のニューロンを数理的なモデルとして単純に表現したもの を用います。このようなニューロンのモデルは1943年にマッカロック（McCulloc h）とピッツ（Pitts）によって最初に提案されました。ニューロンモデルは次の 図のように表されます。 （図）http://ruffnex.oc.to/defolos/text1/figure/n_model.jpg 　このモデルは次のような数式で表現することができ、その数式に基づいて動作 します。 net = w1・x1 + w2・x2 + … + wn・xn out = f( net - θ) 　xは他のニューロンからの入力信号を表しており、x1からxnまでのn個の入力信 号があることを意味しています。wは重み（結合荷重）を表しており、それぞれの 入力信号に対する伝達効率となります。netは重み付けられた入力信号を足し合わ せた値となります。このnet値が一定の値を超えることで出力信号を他のニューロ ンに送ります。生体のニューロンが一定の電圧にまで膜電位が高まるとインパル スを発する（発火する）のと同様の動作を行います。一定の値を閾値（しきいち） と呼び、この図ではθで表されています。 　f()は活性化関数と呼ばれ、入力されるnet値がある一定以上なら0を返し、ある 一定以下なら0を返す関数です。ニューロンが発火する、しないを判定する関数と いうことになります。 　マッカロックとピッツがニューロンモデルを提案した当初の活性化関数はヘビ サイド階段関数（Heaviside step function）または単にステップ関数と呼ばれる 関数を用いていました。ステップ関数は数式では次のように表現できます。 H(x) = {1(x>=0), 0(x<0)} 　ヘビサイド階段関数はH(x)で表される場合が多いです。これをグラフに書き表 すと次のようになります。 （図）http://ruffnex.oc.to/defolos/text1/figure/heaviside.jpg 　このグラフを見ていただければわかる通り、ヘビサイド階段関数は0より大きな 数が入力されたときは1を返し、0以下の値が入力されたときは0を返します。活性 化関数にはヘビサイド階段関数のほか、グラフの形がS字状になるシグモイド関数 も多用されます。 　活性化関数で発火すると判断された入力に対してはout値が1となり、他のユニ ットへの入力信号を送り出すことになります。 ●ニューロンモデルの計算練習 　それでは実際にニューロンモデルの動作を計算して求めてみましょう。次のよ うなモデルの場合に1が出力されるのか0が出力されるのかを計算してみましょう。 （図）http://ruffnex.oc.to/defolos/text1/figure/n_exam.jpg 　このモデルでは重みw1、w2はそれぞれ2.0と-1.0であり、閾値は1.0です。重み がマイナスになっているのは抑制性の結合係数を表しています。 　ここに入力信号x1=1.0、x2=1.0が入力されたとします。まずはじめにnet値を算 出します。net値は次の式のようにして算出できます。 net = w1・x1 + w2・x2 + … + wn・xn 　これは次のようにも書き表すことができます。 net = Σ[k=1;n]xk・wk 　x1が1.0、w1が2.0、x2が1.0、w2が-1.0ですので、上記の式に代入してnet値を 求めてみましょう。 net = 2.0・1.0 + -1.0・1.0 = 2.0 + (-1.0) = 1.0 　net値は1.0になりました。次にout値を求めてみましょう。活性化関数には前述 したヘビサイド階段関数を用います。活性化関数の引数にはnet - θを渡すこと になっていますので、引数を求めてみましょう。 net - θ = 1.0 - 1.0 = 0.0 　引数には0.0を渡すことがわかりました。それではヘビサイド階段関数に0.0を 渡してみましょう。ヘビサイド階段関数では0を含む0以上の値が渡されたときに は1を返します。よって0.0を引き渡した場合には1が返されます。 out = f( 0.0 ) = 1.0 　以上からw1が2.0でw2が-1.0、閾値が1.0のときにx1に1.0、x2に1.0を入力した ときは出力値として1.0が出力されることがわかりました。あとは各自で重みや閾 値、入力信号などを適当に変更して、どのような出力結果になるのか確認してく ださい。 ●ニューロンモデルの別表現 　ニューロンモデルは前述の表現の仕方以外にも、別の表現をすることもできま す。より単純に表現するために、入力信号に常に値が1.0となるx0とその重みw0 = -θを導入した表現法がよく用いられます。これを式に書き表すと次のようにな ります。 net = -θ・1.0 + w1・x1 + w2・x2 + … + wn・xn = w0・x0 + w1・x1 + w2・x2 + … + wn・xn = Σ[k=0;n]wk・xk out = f ( net ) 　このように閾値を重みと考えることで、「■0x06.) ニューロンの学習」で解説 するように学習によって重みだけでなく閾値を変化させることができるようにな ります。ニューロンの学習について学ぶ前に、必要な前提知識となる論理演算に ついて復習をしておきましょう。 ■0x05.) 論理演算の復習 　論理演算（Logical Operation）はブール演算（Boolean Operation）とも呼ば れ、真か偽かの2通りの元しか持たない集合における演算で、ひとつの値を出力し ます。演算結果も真か偽かの2通りになります。 　論理演算はコンピュータ内部での演算に使われ、コンピュータで表現する場合 は真に1、偽に0を使う場合が多いです。論理演算は論理和、論理積、否定、排他 的論理和がよく使われます。 　入力の全てのパターンに対する出力を表として表現したものを真理値表（Truth Table）と呼び、集合の領域を図として表現したものをベン図（Venn Diagram） またはオイラー図（Euler Diagram）と呼びます。 ●論理和（OR） 　論理和（Logical Disjunction）は入力された値のうち、どれかひとつでも真で あれば真を出力します。それ以外の場合、つまり全ての入力された値が偽であっ た場合に限り偽を出力します。「AまたはB」の関係を表します。 ○真理値表 +-----+-----+-----+ | A | B | X | +-----+-----+-----+ | 1 | 1 | 1 | +-----+-----+-----+ | 1 | 0 | 1 | +-----+-----+-----+ | 0 | 1 | 1 | +-----+-----+-----+ | 0 | 0 | 0 | +-----+-----+-----+ ○論理式 　論理式で表す場合、次のように書かれる場合が多いです。 ・A or B ・A＋B ・A∪B ・A∨B ○ベン図 （図）http://ruffnex.oc.to/defolos/text1/figure/ld.jpg ●論理積（AND） 　論理積（Logical Conjunction）は入力された値が全て真であるときに真を出力 します。それ以外であった場合には偽を出力します。「AかつB」の関係を表しま す。 ○真理値表 +-----+-----+-----+ | A | B | X | +-----+-----+-----+ | 1 | 1 | 1 | +-----+-----+-----+ | 1 | 0 | 0 | +-----+-----+-----+ | 0 | 1 | 0 | +-----+-----+-----+ | 0 | 0 | 0 | +-----+-----+-----+ ○論理式 　論理式で表す場合、次のように書かれる場合が多いです。 ・A and B ・A・B ・A×B ・A∩B ・A∧B ○ベン図 （図）http://ruffnex.oc.to/defolos/text1/figure/lc.jpg ●否定（NOT） 　否定（Logical Negation）は入力された値とは逆の値を出力します。入力値が 真であれば偽を出力し、入力値が偽であれば真を出力します。反転させると覚え るといいと思います。「Aではない」という関係を表します。 ○真理値表 +-----+-----+ | A | X | +-----+-----+ | 1 | 0 | +-----+-----+ | 0 | 1 | +-----+-----+ ○論理式 　論理式で表す場合、次のように書かれる場合が多いです。2番目の否定を表すA_ は本来Aの上に線を引くことで表されるのですが、フォントの関係上このように表 現しています。 ・A not B ・A_ ・¬A ○ベン図 （図）http://ruffnex.oc.to/defolos/text1/figure/not.jpg ●排他的論理和（XOR） 　排他的論理和（Exclusive Or）は入力された値が全て同じときは偽を出力し、 入力された値が異なる場合には真を出力します。 　排他的論理和は論理和、論理積と否定を組み合わせることで表現できますが、 使われる頻度が多いためここで取り上げました。 ○真理値表 +-----+-----+-----+ | A | B | X | +-----+-----+-----+ | 1 | 1 | 0 | +-----+-----+-----+ | 1 | 0 | 1 | +-----+-----+-----+ | 0 | 1 | 1 | +-----+-----+-----+ | 0 | 0 | 0 | +-----+-----+-----+ ○論理式 　論理式で表す場合、次のように書かれる場合が多いです。3番目のA_、B_は否定 を表していますが、本来はA、Bの上に線を引くことで表されます。フォントの関 係上、このように表現しています。 ・A eor B ・A xor B ・A_・B＋A・B_ ・（A∨B）∧¬（A∧B） ○ベン図 （図）http://ruffnex.oc.to/defolos/text1/figure/eo.jpg ■0x06.) ニューロンの学習 　ニューロンの重みや閾値を自動的に変更し、正しい解を導くことができるよう に修正することを学習といいます。生体の脳も入力に対する正しい出力が得られ るようにニューロンとニューロンの繋がり方や伝達効率などが変化しているよう です。例えば入力として犬という視覚情報が入力された場合、それを犬であると 認識するという正しい出力を得られるように、脳の中のニューロンの結びつきな どが変更されています。 　学習は1949年にDonald Hebbが書いた「行動の機構」という本の中で提唱された ようです。この本でHebbは生物学的に「シナプスを経て到着した入力が直ちにパ ルスを発生させる時、その結合係数の効率は少し増加する」と提唱したようです。 そこからHebbはニューラルネットワークの重みを変化させることで学習ができる という仮説を立てました。これがニューラルネットワークの学習の研究のはじま りだと言われています。 ●教師つき学習と教師なし学習 　入力に対する出力がこちらが定義した理想的な出力結果である教師信号通りに なるように重みを変更する学習方法のことを教師つき学習と呼びます。一方、教 師信号なしに学習を行う方法を教師なし学習と呼びます。ここでは教師つき学習 の誤り訂正学習法を使って論理演算を学習させてみることにしましょう。 　教師信号は次のように表現されます。 ・第p番目の入力信号（x1〜xnまで） 　　xp1, xp2, xp3 ... xpn ・第p番目の教師信号 　　yp 　x1からxnまでの入力信号をあわせてパターンひとつと考えます。パターンひと つにつき、そのパターンを入力して得られる理想的な出力結果である教師信号が ひとつ与えられます。例えば第3番目の入力パターンに対する教師信号はy3となり ます。 ●誤り訂正学習法 　誤り訂正学習法は、適当な初期値から学習を開始し徐々に訂正していくことで 学習を行います。誤り訂正学習法は入力信号に対する出力と教師信号との誤差が ある場合には重みの変更を行い、出力と教師信号が一致した場合には何も行いま せん。重みの変更は次の式に基づいて行われます。 wi[new] = wi[old] + η(yp - out) xpi ( 1≦ i ≦n ) 　wi[new]は修正後の重みを表しており、wi[old]は修正される前の重みを表して います。ηは学習率といって、1以下の小さな正の定数です。また、(yp - out)は 次の式に従って出力されることになります。 (yp - out) = {1(yp=1,out=0); -1(yp=0,out=1); 0(yp=out)} 　上記の式より出力と教師信号が一致していない場合に重みを修正することがわ かります。つまり、ypの値が1であるのにoutの値が0になる場合には、outが1にな るように重みをη・xiだけ増加させます。逆にypの値が0であるのにoutが1である 場合には、outが0になるように重みをη・xiだけ減少させます。これをp個すべて の入力信号に対して、重みwiが変化しなくなるまで繰り返します。 ●誤り訂正学習法の例 　それでは次の入力信号と教師信号に対して、誤り訂正学習法で学習を行う過程 を見ていきましょう。また、重みの初期値はすべて0の状態からスタートします。 +---------+----+----+----+----+ | | x0 | x1 | x2 | y | +---------+----+----+----+----+ |パターン1| 1 | 0 | 0 | 0 | +---------+----+----+----+----+ |パターン2| 1 | 1 | 0 | 1 | +---------+----+----+----+----+ |パターン3| 1 | 0 | 1 | 1 | +---------+----+----+----+----+ |パターン4| 1 | 1 | 1 | 1 | +---------+----+----+----+----+ 　x0は常に1となる入力です。「■0x04.) ニューロンモデル」のニューロンモデ ルの別表記を参照してください。上記の入力信号と教師信号の関係は論理積を表 しています。x1とx2を考えて、双方が1の場合にのみ1が出力されます。それにあ わせて教師信号yを設定しています。 　パターン1では0と0が入力され、その時の正しい出力結果は0です。パターン2で は1と0が入力され、出力は1になります。パターン3では0と1が入力され、出力は 1になります。パターン4では1と1が入力され、出力は1になります。この4つのパ ターンを順次入力して行き、前述の式に従って重みを修正して、すべてのパター ンにおいて出力と教師信号が同じになるようにします。 　重みの初期値はすべて0の状態から開始されます。ここにパターン1の入力信号 を入力します。x1・w1は0でありx2・w2、x3・w3も0になるのでx1・w1 + x2・w2 + x3・w3の値であるnet値は0となります。net値0をステップ関数に入力すると1が 出力されますので、out値は1となります。パターン1の教師信号は0ですのでyp - outの値は0 - 1で-1になります。yp - outは負の値ですので新しい重みはη・ xpi減少させます。ここでは学習率を1と置くこととしますので、その結果wi[new] = wi[old] + η(yp - out) xpiの式はwi[new] = wi[old] - xpiとすることがで き、重みの変更を行います。次のように修正されることになります。 w0 = 0 - 1 = -1 w1 = 0 - 0 = 0 w2 = 0 - 0 = 0 　重みは上記のように修正されました。次にパターン2を入力します。net値は-1 + 0 + 0 = -1となり、out値は0です。out値と教師信号が異なるため、重みの修 正を行います。yp - outは1 - 0であり1となりますのでxpi増加させます。 w0 = -1 + 1 = 0 w1 = 0 + 1 = 1 w2 = 0 + 0 = 0 　同様にパターン3を入力します。net値は0 + 0 + 0 = 0であるためout値は1とな り、教師信号と同じですので重みの修正はありません。パターン4を入力するとn et値は0 + 1 + 0 = 1となり、out値は1です。教師信号と一致するため、ここでも 重みの修正は行われません。現在の重みは(0, 1, 0)です。一通り入力信号のパタ ーンを入力し終わったため、第1回目の学習はこれで終わりです。 　 一通りすべてのパターンを入力しましたが、パターン2で重みを修正している ため、新しい重みの場合にパターン1が教師信号と同じ出力をするかどうかはわか りません。そのためもう一度パターン1を入力します。再度パターン1を入力する とnet値は0 + 0 + 0 = 0となり、out値は1です。教師信号とは一致せず、yp - o utの値は-1です。ですので重みは次のように修正されます。 w0 = 0 - 1 = -1 w1 = 1 - 0 = 1 w2 = 0 - 0 = 0 　修正が行われたので、続いてパターン2を入力してみます。net値は-1 + 1 + 0 = 0ですので、out値は1となります。教師信号と一致しますので重みの変更は行 わずに次のパターンを入力します。次のパターン3ではnet値は-1 + 0 + 0 = -1で ありout値は0です。教師信号とは一致しないため重みの修正が行われます。yp - out = 1 - 0 = 1で正の値ですのでxpi増加させます。 w0 = -1 + 1 = 0 w1 = 1 + 0 = 1 w2 = 0 + 1 = 1 　パターン4ではnet値は0 + 1 + 1 = 2でありout値は1です。教師信号と一致する ため重みの修正は行われません。ここまでで第2回目の学習は終了しました。 　パターン3で修正が行われたため、第3回目の学習を行います。パターン1を入力 するとnet値は0 + 0 + 0 = 0となりout値は1です。教師信号と違いますので修正 を行います。yp - out = 0 - 1 = -1で負の値ですので次のように修正されます。 w0 = 0 - 1 = -1 w1 = 1 - 0 = 1 w2 = 1 - 0 = 1 　ここで修正された重みは、この問題を解くための解となります。この後パター ン2から4までを入力しても重みの修正は行われることがなく、第3回目の学習は終 了します。第3回目の学習のパターン1で重みを修正しているため第4回目の学習を 行いますが、第4回目の学習ではパターン1から4まで重みの修正は行われることが ありません。このようにすべてのパターンで重みの修正が行われなくなったとき は学習できたことを意味しており、その重みで問題を解くことができます。当然、 問題を解くことのできる重みは無数に存在しており、ここで求めた重み以外でも 問題を解くことは可能です。 ■0x07.) 学習プログラム 　それでは「■0x06.) ニューロンの学習」で説明した誤り訂正法を使って、ひと つのユニットが論理演算を学習できるようにプログラムを組んでみます。大変お 見苦しいソースコードですが、次のようなプログラムを書きました。 -----neuron.c /***************************************************************/ /* 12:58 2006/06/28 Defolos neuron.c /* /* ニューラルネットワークのユニットひとつの学習 /* 誤り訂正学習法で論理和・論理積を学習させる /* /***************************************************************/ #include #define INPUT_PATTERN 4 //入力パターン #define INPUT_SIG_NUM 3 //入力信号数 /*-------------------------------------------------------------*/ /* 構造体の設定 */ /*-------------------------------------------------------------*/ struct NEURON_DATA { int input[INPUT_PATTERN][INPUT_SIG_NUM]; int weight[INPUT_SIG_NUM]; int magister[INPUT_PATTERN]; int net; int out; }; /*=============================================================*/ /* メイン関数始まり */ /*=============================================================*/ int main (void){ int i, j; int err; int count = 0; /*-------------------------------------------------------------*/ /* プロトタイプ宣言　main関数内でのみ利用する */ /*-------------------------------------------------------------*/ int step (int); /*-------------------------------------------------------------*/ /* 構造体へのデータ設定 */ /*-------------------------------------------------------------*/ struct NEURON_DATA unit; unit.input[0][0] = 1; unit.input[0][1] = 0; unit.input[0][2] = 0; unit.input[1][0] = 1; unit.input[1][1] = 1; unit.input[1][2] = 0; unit.input[2][0] = 1; unit.input[2][1] = 0; unit.input[2][2] = 1; unit.input[3][0] = 1; unit.input[3][1] = 1; unit.input[3][2] = 1; unit.weight[0] = 0; unit.weight[1] = 0; unit.weight[2] = 0; //論理和 unit.magister[0] = 0; unit.magister[1] = 1; unit.magister[2] = 1; unit.magister[3] = 1; unit.net = 0; unit.out = 0; //学習が完了するまで繰り返す while (1){ //エラーフラグのリセット err = 0; //カウントアップ count = count + 1; //パターン4まで繰り返し for (j=0; j= 100) ) break; } /*-------------------------------------------------------------*/ /* 結果の表示 */ /*-------------------------------------------------------------*/ printf("学習回数:%d\n", count); for (i=0; i= 0) return 1; else return 0; } ----- 　このソースコードをコンパイルし、実行すると次のような結果が得られます。 これは、4回の学習で重みが次のように変更されたことを意味しています。はじめ 無秩序であった重みが、学習によって論理和を行える重みに変更されました。こ れで論理和を学習できました。 学習回数:4 weight[0] = -1 weight[1] = 1 weight[2] = 1 　次に、ソースコード中の教師信号を論理積の結果にした場合を考えて見ます。 6回の学習で次のように重みが変更されました。これによって論理積も学習するこ とができました。 学習回数:6 weight[0] = -3 weight[1] = 1 weight[2] = 2 ●ひとつのユニットの限界 　ユニットがひとつの場合でも、先述のように論理和と論理積を学習することは できました。それでは排他的論理和を学習できるか試してみましょう。neuron.c の教師信号を排他的論理和の演算結果になるようにセットし、コンパイルして実 行しますと、次のような結果になります。 学習回数:100 weight[0] = 0 weight[1] = 0 weight[2] = -1 　このプログラムでは学習回数が100回の時は学習できなかったということを意味 していますので、排他的論理和を学習することはできませんでした。論理和、論 理積と排他的論理和には後述する線形分離性のある、ないで違いがあります。こ の違いがひとつのユニットで学習できる、できないの違いとなります。 ○線形分離性 　以前、「■0x04.) ニューロンモデル」で解説したニューロンの動作を表す式を 次に記述します。ここでf()はstep関数を表しています。 net = w0・x0 + w1・x1 + w2・x2 out = f( net ) 　活性化関数によってユニットはnet値が0より大きいときには1を出力し、net値 が0より小さいときには0を出力します。このことからユニットが0か1かのどちら の値を出力するかの境界線は次のように表現できます。 net = w0・x0 + w1・x1 + w2・x2 = 0 　この直線によって0を出力するべき点と1を出力するべき点を分離することがで きる問題を線形分離可能な問題と呼びます。次のグラフで確認できるように、AN DとORは線形分離可能な問題です。○は0を出力するべき点を表しており、●は1を 出力するべき点を表しています。 ・AND （図）http://ruffnex.oc.to/defolos/text1/figure/linia_dev_and.jpg ・OR （図）http://ruffnex.oc.to/defolos/text1/figure/linia_dev_or.jpg 　一方、XORのように一本の直線では分離できないような問題も存在しています。 このような問題は線形分離不可能な問題と呼びます。XORが線形分離不可能である のは次のグラフを参照することで確認してください。 ・XOR （図）http://ruffnex.oc.to/defolos/text1/figure/linia_dev_xor.jpg 　実は、XORなどの線形分離不可能問題はひとつだけのユニットあるいは中間層を 持たないニューラルネットワークでは学習不可能であることが数学的に証明され ています。1962年にFrank Rosenblattが提唱したニューラルネットワークのアル ゴリズムの中で最初に提唱されたパーセプトロンは一世を風靡し、多くの分野で 応用されました。パーセプトロンは1階層で表現されコスト関数によって学習しま すが、線形分離可能問題しか学習することができないことがMinskyによって証明 されました。これによってニューラルネットワークの研究は一時衰退傾向にあっ たようです。 　これを解決する方法としてニューロンに中間層を持たせて階層構造をとること が挙げられます。ニューラルネットワークの研究が盛り返したのは中間層をとる パーセプトロンとバックプロパゲーションという学習法の出現による部分が大き いとされています。 ■0x08.) 注釈 （※１） 東京医科歯科大学　教養部　生物化学C　ニューロン （http://www.tmd.ac.jp/artsci/biol/textlife/lifetop.htm）より引用 （※２） 東京医科歯科大学　教養部　生物化学C　ニューロン （http://www.tmd.ac.jp/artsci/biol/textlife/lifetop.htm）より引用 ■0x09.) 参考文献 ・「東京都神経化学総合研究所　ニューロンと情報処理」 http://www.tmin.ac.jp/neuro/neuron.html ・「東京医科歯科大学　教養部　生物化学C　ニューロン」 http://www.tmd.ac.jp/artsci/biol/textlife/neuron.htm ・「独立行政法人 理化学研究所 脳科学総合研究センター　ニューロン」 http://www.brain.riken.go.jp/japanese/g_braaw/g4.html ・「CyberLibrarian　参考資料　論理演算」 http://www.asahi-net.or.jp/~AX2S-KMTN/ref/logicope.html ・「愛媛大学 工学部 情報工学科　村上・泉田研究室　ニューラルネットワーク」 http://ipr20.cs.ehime-u.ac.jp/column/neural/index.html ・「MetalBrain」 http://metalbrain.piroo.com/index.html ■0x0A.) さいごに 　それではまたお会いしましょう。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第3章: Windows File Protection Hacking --- 著者：Kenji Aiko x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　システムファイルのリバースエンジニアリングを行っていると、Windows File Protection（WFP）の存在がとても面倒に感じます。セキュリティ的観点から見 ると、WFPはとても重要なシステムですが、プログラマや解析者からすると少しや っかいな存在です。よって私は、どうにかしてこのWFPを制御できないか、と考え ました。このテキストは、その方法を模索した結果を書き記したものです。 　私の環境は「WindowsXP SP2」であるため、このテキストは基本的にその環境に 従って書かれています。WFPはWindowsのバージョンによって多少の違いがあるた め、もしかしたら他の環境では勝手が違うかもしれません。あらかじめご了承く ださい。 ■0x02.) Windows File Protection（WFP）とは 　「Windows File Protection」とは、Windows2000にて新しく採用されたファイ ル保護機能のことであり、一般のアプリケーションに、Windowsのシステムファイ ルの変更を行わせない仕組みのことです。以後、Windows2000/XP/2003にて同様の 機能が実装されています。 　本来、WFPとは、アプリケーションソフトのインストール時に、システムファイ ルが上書きされ、Windowsが不安定になったり、これまで正常に動作していたアプ リケーションに問題が発生したり、といったこと（いわゆるDLL地獄）を防ぐため に実装されたものです。例えば、WINDOWSフォルダ（C:\WINDOWS）やsystem32フォ ルダ（C:\WINDOWS\system32）には、Windowsの根幹を担うシステムファイルが多 数存在します。これらのファイルを、一般のアプリケーションが容易に変更する ことができたならば、OS自体の動作に影響が出てしまいますし、また、ウイルス やスパイウェアが意図的にシステムファイルを都合のよいように改竄することも 可能となります。つまり、セキュリティ的観点から、システムファイルの変更は 好ましくありません。よって、マイクロソフトは、Windows2000にてWFPと呼ばれ るファイル保護機能を実装しました。 　WFPによって保護されているファイルは、変更や削除ができなくなり、基本的に 一般のアプリケーションからはアクセスできません。つまり、どのようなアプリ ケーションをインストールしても、どのような悪質なコンピュータウイルスに感 染しても、保護されているファイルだけは、OSインストール時のままというわけ です。そして、このシステムによって、Windowsはとても安定したシステムを維持 することができるようになりました（もちろんこれだけの理由ではありませんが）。 　ちなみに、Windows ME（Millennium Edition）にも、WFPに似たような機能が搭 載されていますが、こちらは「System File Protection」と呼ばれるものであり、 このテキストでは別物と解釈し、扱わないものとします（ただし、どちらもほぼ 同じ機能だと思われますが）。 ■0x03.) 保護機能の仕組み 　ファイル保護はさほど難しい仕組みで動作していません。保護対象のファイル に対して、何かしらの変更が行われた場合、まず「C:\WINDOWS\system32\dllcache」 フォルダ内に、同様のファイルが存在しないかを調べます。もし、同様のファイ ルが存在するなら「C:\WINDOWS\system32\dllcache」からファイルが復元される ことになります。 　試しに、「C:\WINDOWS」フォルダ内にある「notepad.exe」のファイル名を変更 してみてください。 （図1）http://ruffnex.oc.to/kenji/text/wfp/wfp1.png 　ファイル名を変更すると、実質「notepad.exe」というファイルは無くなったこ とになるため、ファイル保護機能が働きます。保護機能が働くと「C:\WINDOWS」 以下に、新たに「notepad.exe」が作成されます。ちなみに「C:\WINDOWS\system 32\dllcache」フォルダ以下に「notepad.exe」のバックアップファイルが無いと、 当然「notepad.exe」ファイルは復元されないため、ファイル名を変更する場合は、 必ず「C:\WINDOWS\system32\dllcache」フォルダ以下に「notepad.exe」のバック アップファイルが存在することを確認してから行ってください（といっても、ほ ぼ確実にありますので問題ないと思いますが）。 （図2）http://ruffnex.oc.to/kenji/text/wfp/wfp2.png 　さて、dllcacheフォルダからファイルが復元されるということは、もし、dllc aheフォルダ内に「notepad.exe」のバックアップファイルがない、もしくは偽物 （まったく異なったファイル）が保存されていた場合、ファイルが復元できない ことになります。すると、「システムファイルが変更され復元できないため、イ ンストールCDを挿入してください」という旨のメッセージボックスが表示されま す。 （図3）http://ruffnex.oc.to/kenji/text/wfp/wfp3.png 　ここで指示に従ってインストールCDを入れると、インストールCDからファイル の復元が行われますが、もし、インストールCDを入れずに「キャンセル」を選択 すると、復元されずに終わります。 　つまり、まとめると、WFPの保護機能は次の処理を行うことになります。 ・dllcacheフォルダ内にキャッシュがあれば、dllcacheフォルダから復元する ・dllcacheフォルダ内にキャッシュがなければ、警告のダイアログボックスを表 示する 　このような仕組みの元、システムファイルはあらゆるアプリケーションから保 護されています。 ■0x04.) WFPの無効化 　WFPを働かせないようにするためには、Windowsをセーフモードで起動する必要 があります。セーフモードで起動すると、WFPは起動時から無効になっているので、 システムファイルを任意に変更することが可能です。しかし、いちいちセーフモ ードで再起動するのも面倒くさいというわけで、便利なツールが公開されています。 Windows File Protection Switcher 1.0 http://fileforum.betanews.com/detail/Windows_File_Protection_Switcher/1106499902/1 　「Windows File Protection Switcher 1.0」はWFPの「有効」「無効」を切り替 えることができます。また、「セーフモードで実行してくれ」と書かれてありま すが、普通の状態でも問題なく動作します。ただし、インストールCDの挿入を求 めるダイアログボックスが表示されますので、それに「キャンセル」を選択する 必要があります。 　このツールが内部でどのような動作を行っているかは、解析してみなければ分 かりませんが、WFPの無効化は、Windowsのバージョンによって多少異なります。 以下にその詳細を示します。ちなみに、以下の解説に出てくる、レジストリの「 SFCDisable」キーとは、レジストリの「HKEY_LOCAL_MACHINE\SOFTWARE\Microsof t\Windows NT\CurrentVersion\Winlogon」以下にある「SFCDisable」キーのこと です。 ----- Windows 2000 SP2の場合 1. セーフモードで起動 2. C:\WINDOWS\system32\sfc.dllをバイナリエディタで開く 3. オフセット「0x6211」から2バイトの値を「8BC6」から「9090」へ変更 4. レジストリの「SFCDisable」キーの値を「0xffffff9d」へ変更 5. Windowsを再起動 ----- ----- Windows 2000 SP4の場合 3. オフセット「0x62DB」から2バイトの値を「8BC6」から「9090」へ変更 これ以外はWindows 2000 SP2の場合と同じ ----- ----- Windows XPの場合 1. セーフモードで起動 2. C:\WINDOWS\system32\sfc_os.dllをバイナリエディタで開く 3. オフセット「0xE2B8」から2バイトの値を「8BC6」から「9090」へ変更 4. レジストリの「SFCDisable」キーの値を「0xffffff9d」へ変更 5. Windowsを再起動 ----- ----- WindowsXP SP1の場合 3. オフセット「0xE3BB」から2バイトの値を「8BC6」から「9090」へ変更 これ以外はWindows XPの場合と同じ ----- ----- WindowsXP SP2の場合 3. オフセット「0xECE9」から3バイトの値を「33C040」から「909090」へ変更 これ以外はWindows XPの場合と同じ ----- 　上記の操作を手動で行うことで、WFPを解除することができます。ただし、いろ いろと面倒ですし、システムファイルを変更するので、万が一のことがあるかも しれません。なので、もし解除だけしたいならば、ツール（Windows File Prote ction Switcher 1.0）を使う方がよいでしょう。ただ、このツールにも「自己責 任で使用してください」と書いてあったりしますが…（笑）。 ■0x05.) WFP制御へのアプローチ 　WFP無効化へのアプローチとして、sfc.dll（もしくはsfc_os.dll）の上書きを 紹介しました。これは、もっともシンプルな方法です。しかし、これ以外にもWF Pを無効化する手段はいくつか存在します。例えば「C:\WINDOWS\system32\sfcfi les.dll」を変更する方法です。 　sfcfiles.dllファイルには、WFPの対象となるファイルパスがUNICODE形式で保 存されています。よって、それらのファイルパスを変更することで、任意のファ イルのWFPを無効化することができます。 （図4）http://ruffnex.oc.to/kenji/text/wfp/wfp4.png 　重要なAPIを提供しているuser32.dllも、もちろんWFPの対象となっています。 しかし、sfcfiles.dllファイルに記述されているuser32.dllのパスを変更するだ けで、user32.dllがWFPの対象から外されます。このように、システムファイルを バイナリレベルで操作することにより、WFPは簡単に無効化することができます。 　しかし、sfcfiles.dllファイルのWFP対象ファイルを見ていると、とても面白い ことに気づきます。それは、WFP対象ファイルに、sfc.dllも、sfc_os.dllも、sf cfiles.dll自身さえも含まれているということです。つまり、WFPを無効化するた めに編集しなければならないファイルがすべて、WFPの対象となっているわけです。 よって、仮に悪意あるプログラムがWFPを無効にしようと企んだとしても、必ず一 度はWFPに引っかかることになります。一度引っかかれば、警告ダイアログボック スによってユーザにその旨が知らされますので、十分にセキュアだと言えます。 いやー、Windowsは実によく考えて作られていますね(^^;。 　しかし、これは、非公開APIを利用することで簡単に突破できます。sfc_os.dl lがエクスポートしている、エクスポート序数が「5」の関数を呼び出すことで、 一時的に任意のファイルに対してのWFPを解除することができます。この関数は関 数名が存在しないため、とりあえずここでは、関数名をDisWfpとします。では、 DisWfp関数の定義を以下に示します。 ----- DisWfp関数の定義 DWORD WINAPI DisWfp( // 戻り値は成功時0、失敗時1 DWORD dwA, // 0固定（詳細不明） WCHAR *szFile, // WFPを無効にするファイルパス（UNICODE） DWORD dwB // -1固定（詳細不明） ); ----- 　この関数を呼び出すことで、szFileで指定したファイルへのWFPが「一時的に」 無効になります。「一時的に」というのは、この関数を呼び出して、約1分くらい だけWFPが無効になるからです。関数呼出し後、1分を経過するとまたWFPが有効に なりますので、その1分間に対象ファイルを変更する必要があります。 　では、以下のソースコードを見てください。 ----- dwfp1.cpp #define WIN32_LEAN_AND_MEAN #define STRICT #include #include #include typedef DWORD (WINAPI *PDISWFP)(DWORD dwA, WCHAR *szFile, DWORD dwB); int main(int argc, char *argv[]) { if(argc < 3){ printf("%s [src file] [dest file]\n", argv[0]); return 1; } char *srcfile = argv[1]; char *destfile = argv[2]; HMODULE hMod = NULL; // sfc_os.dll handle PDISWFP pWfp = NULL; // function ptr try{ if((hMod = LoadLibrary("sfc_os.dll")) == NULL) throw 1; if((pWfp = (PDISWFP)GetProcAddress(hMod, (LPCSTR)5)) == NULL) throw 2; WCHAR wdestfile[1024]; MultiByteToWideChar(CP_ACP, 0, destfile, -1, wdestfile, 1024 * sizeof(WCHAR)); if(pWfp(0, wdestfile, -1)) throw 3; CopyFile(srcfile, destfile, FALSE); printf("Copy \"%s\" to \"%s\" successed!\n", srcfile, destfile); }catch(int err){ printf("Error: %d\n", err); } FreeLibrary(hMod); return 0; } ----- ----- コマンドプロンプト C:\>bcc32 -w- dwfp1.cpp Borland C++ 5.6.4 for Win32 Copyright (c) 1993, 2002 Borland dwfp1.cpp: Turbo Incremental Link 5.65 Copyright (c) 1997-2002 Borland C:\> ----- 　「Borland C++ Compiler 5.6.4」にてコンパイルしています。引数にコピー元 とコピー先のファイルパスを指定します。通常ならば、WFPの対象となっているフ ァイルに対してCopyFile関数を実行すると、エラーとなりますが、DisWfp関数に てWFPを無効にしているので、問題なくファイルのコピーを行うことができます。 system32フォルダ以下にあるcalc.exeは、Windowsに標準で搭載されている電卓プ ログラムです。適当な実行ファイルの名前を「calc.exe」として、system32以下 の電卓プログラムcalc.exeと置換する例を以下に示します。 ----- コマンドプロンプト C:\>dwfp1.exe c:\calc.exe c:\WINDOWS\system32\calc.exe Copy "c:\calc.exe" to "c:\WINDOWS\system32\calc.exe" successed! C:\> ----- 　これで、system32以下のcalc.exeは、こちらが用意した偽物のcalc.exeに置換 されました。試しに電卓を起動してみてください。偽物のcalc.exeが起動するは ずです。このようにして、WFPは簡単に無効化することができます。 ■0x06.) 実用的なWFPの制御方法 　DisWfp関数を使うと任意のファイルに対してのみ、WFPを解除することができま すが、できるならば、すべてのファイルに対してのWFPを解除したいです。WFPを 解除するためには、sfc.dllやsfc_os.dllやsfcfiles.dllを変更することで行うこ とができますが、これらのファイルを変更しなくとも、WFPを解除することができ ます。 　WFPを行っているプロセスは、システムプロセスであるwinlogon.exeです。これ は、WFP対象ファイルを変更したときに表示される警告ダイアログボックスから割 り出すことができます。ちなみに、私は、警告ダイアログボックスが表示された ときにタスクマネージャを起動し、ダイアログボックスのウィンドウからプロセ スを調べました。 　そして、このwinlogon.exeプロセスの内部で、SfcTerminateWatcherThread関数 を呼び出すことで、WFPを無効化することができます。SfcTerminateWatcherThre ad関数とは、DisWfp関数同様に、名前のない関数であり、sfc.dllのエクスポート 序数「2」としてエクスポートされています。定義は以下のようになっています。 ----- SfcTerminateWatcherThread関数の定義 DWORD WINAPI SfcTerminateWatcherThread(void); // 戻り値は成功時0、失敗時1 ----- 　見ての通り引数はなく、戻り値は成功時に0が返ります。この関数をwinlogon. exe内部で呼び出すことで、WFPが無効になります。 　任意の関数を任意のプロセス内部で呼び出させる方法は多数あります。例えば DLLインジェクションやスレッドインジェクションです。これらについては、私の HPにある「常駐プログラム隠蔽テクニック」や「KeyLoggerとプロセス隠蔽につい てのまとめ」を参照してください。 常駐プログラム隠蔽テクニック http://ruffnex.oc.to/kenji/text/dll_inj/ KeyLoggerとプロセス隠蔽についてのまとめ http://ruffnex.oc.to/kenji/thekeylogger/KeyLogger.html 　このようなテクニックを使用することで、他プロセスへ任意のコードを注入で きますが、winlogon.exeはシステムプロセスですので、そのままOpenProcess関数 を使用したのでは、プロセスが開けません。よって、インジェクション処理を行 う前に、システムファイルを制御できるよう、OpenProcessToken関数、LookupPr ivilegeValue関数、AdjustTokenPrivileges関数を使用して、システムレベルのデ バッグ処理を行えるように、特権を取得します。この辺りについては、以下のサ イトが参考になるでしょう。 SeDebugPrivilegeを使用して任意のプロセスへのハンドルを取得する方法 http://support.microsoft.com/default.aspx?scid=kb;ja;131065 　これらの処理を行うことで、WFPを無効にすることができます。 　本当はこの後、実証コードをずらずらっと載せたかったのですが、ちょっと時 間がなかったので、実証コードは、私のサイトに公開するときに追加しておくこ とにします。すみません(^^;。 ■0x07.) さいごに 　さて、いかがだったでしょうか。今回は少しHackingっぽいネタを書かせていた だきました。WFPの無効化や、システムファイルの改竄などは、どちらかというと 悪意あるプログラムで使用されそうですが、個人的にはとても面白い内容だと思 ったので書いてみました。ただ、あまりこういうことに興味のある人は少ないか もしれないですが…(^^;。 　というわけで、今回のHackingネタ、楽しんでいただけたなら幸いです。最後に なりましたが、ここまで読んでくれて本当にありがとうございます。 　では、また会う日まで... ■0x08.) 参考サイト Hacking Windows File Protection http://www.bitsum.com/aboutwfp.asp More on disabling Windows File Protection http://www.jsifaq.com/SF/Tips/Tip.aspx?id=5392 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第4章: 基礎暗号学講座 〜 第3回 〜 --- 著者：IPUSIRON x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　前回はランダム置換・ランダム関数の概念について解説しました。今回はブロ ック暗号の利用モードの解説とそれが情報理論的に安全かどうかを証明するとこ ろまで解説したいと思います。ブロック暗号の利用モードは、ECBモード・CBCモ ード・CFBモード・OFBモード・CTRモードがあります。しかしたくさん紹介しても 消化しきれないと思いますので、今回はECBモードとCTRモードについてだけ触れ ることにします。なお、誤り伝搬（同期はずれ）やビット欠落・ビット破損とい ったネットワークに依存するような話は今回はしないことにします。あくまで暗 号に関連する点に重点を入れる予定です。 ■0x02.) 情報理論的安全性 　暗号の安全性を語るときは①アタッカー（アドバーサリーとも呼ぶ）の能力と ②どこまでの情報漏れを許容するかという2つの点に分けて考えます。 　まずアタッカーの能力としては無限の能力、有限の能力などがあります。後者 の有限の能力としては多項式時間・準指数的時間・指数的時間といったレベルで 考えられます。一般のコンピュータの能力は多項式時間の能力まで持っていると 議論されます。 　次にどこまでの情報漏れまでを許容するかということは、情報が完全に漏れた らアウトなのか、情報の一部分（1ビットなど）さえも漏れたらアウトなのかとい ったことです。 　細かい話は次回以降また解説しますので、まだわからなくても大丈夫です。こ こでは、情報理論的安全性だけをしっかり理解しておいてください。 　情報理論的安全性では、理想的である計算時間（無限の能力を持つCPUと考えて もらえればよい）と記憶領域（無限の領域を持つメモリと考えてもらえればよい） の能力を持つアタッカーを考えます。こうしたアタッカーに対してさえも安全で ある暗号のことが証明されたものを「情報理論的に安全」と呼びます。つまり、 「情報理論的に安全」ということは暗号における一番強力な安全性です。 　それに対して、アタッカーに無限の能力を考えない場合は、計算量的安全性と 呼ばれ、前述したようにアタッカーのレベルと許容するレベルの段階がいくつか に分かれているので、それの組合わせ分だけ安全性が存在するということになり ます。 　それでは、共通鍵暗号系の情報理論的安全性を定義してみます。 　まず平文m、鍵kに対して、暗号文cが暗号化アルゴリズムであるEを用いて、次 のように表される共通鍵暗号系を考えます。 c=E(k,m)　←(1) 　また平文は集合M={m_1,m_2,…}から、ある確率分布によって生起すると仮定し、 ~M（エムチルダ）によってその確率変数を表すとします。ただし、任意のm∈Mは 正の確率で生起すると仮定します。 　鍵は集合K={k_1,k_2,…}から、ある確率分布によって生起すると仮定し、~Kに よってその確率変数を表すとします。 　そして、暗号文は(1)によって定まる集合C={c_1,c_2,…}上のある確率分布によ って生起し、~Cによってその確率変数を表すとします。 　これで共通鍵暗号系の情報理論的安全性の定義の準備ができました。上記の記 号を使い、定義を表記することにします。 [定義] ∀c∈C、∀m∈M；Pr(~M=m|~C=c)=Pr(~M=m) が成り立つとき、暗号系（~K,~M,~C）は情報理論的に安全（完全秘匿）であると いう。 （図）http://s-akademeia.sakura.ne.jp/main/image9/jyouhou.jpg 　数学記号ばかりになってしまいましたが直観的にいうと、アタッカーが盗聴に よって暗号文を入手したとするとき、平文を解読するための情報がなんら含まれ ておらず役に立たないことを意味します。 　ただし、暗号が少しわかる人に言及しておくと、アタッカーはあくまで盗聴だ けでありランダムオラクルモデルは使えないという仮定をしています。 ■0x03.) 情報理論的安全性の例 　例えば、暗号化アルゴリズムD：c=m+kを考えてみます。 　また、M={0,…,9}とK={0,…,9}が各集合上でmとkが一様分布すると仮定します。 　このとき、Pr(~M=0)=Pr(~M=1)=…=Pr(~M=9)=1/10となります。 　ここでアタッカーが何らかの方法でc=1を入手したとします。これをDの式に代 入すると、1=m+kとなり、(m,k)の組み合わせは次の2通りのみになります。ここで +はXOR演算（排他的論理和）であることを忘れないように。 (m,k)=(1,0),(0,1) 　つまり、c=1のときはm=2となることはありえません。 　よって、Pr(~M=2|~c=1)=0となり、Pr(~M=2|~c=1)≠Pr(~M=2)がわかります。 　ゆえに、このDの暗号系は情報理論的に安全でないことが示されました（反例が ひとつ提示された）。 ■0x04.) 情報理論的に安全な暗号系の鍵長と平文長の関係 [定理] 「情報理論的に安全」⇔「|K|≧|M|」 　この絶対値は、長さを意味します。例えば、100ビットの平文を暗号化したい場 合は、鍵の長さは100ビット以上必要ということです。 [証明]背理法を用います。 　|K|≧|M|でない、すなわち|K|＜|M|と仮定します。 　すると、ある平文m∈Mと暗号文c∈Cが存在して、次がいえます。 D_k(c)≠m　（∀k∈K） 　これは、Pr(~C=c|~M=m)=0であることを意味しますが、これは定義に矛盾します。 　ゆえに、|K|≧|M|となります。　（Q.E.D.） ■0x05.) ECBモード 　ブロック暗号の欠点はnビット以上使えないということです。利用モードとはブ ロック長nのブロック暗号Eを用いて、nより長い平文M=(m_1,…,m_t)を暗号化する ための技術です。 　ここで、|m_i|によってm_iの長さ（ビット長）を表すことにします。特に断ら ない限り、|m_i|=n（ブロック長がn）とします。 　ECB（Electronic CodeBook：電子符号表）モードとは、次の仕様にしたがい各 m_iを単純に暗号化する方式です。 [1]暗号化 　平文M=(m_1,…,m_t)に対して、c_1=E_k(m_1),…,c_t=E_k(m_t)を計算して、暗 号文をC=(c_1,…,c_t)とします。 [2]復号 　暗号文C=(c_1,…,c_t)に対して、m_1=D_k(c_1),…,m_t=D_k(c_t)を計算して、 平文をM=(m_1,…,m_t)とします。 （図）http://s-akademeia.sakura.ne.jp/main/image9/ecb.jpg 　なお、最後の平文ブロックがブロック長に満たない場合には、パディングと呼 ばれるデータの詰め物を入れます。 　図を見てもらえればわかるように、m_i=m_jならc_i=c_jとなります。つまり平 文ブロックと暗号文ブロックが一対一対応の関係にあるわけです。これは安全性 の議論に直結します。 　直観的にも安全性に問題があることがわかります。例えば、平文の中に同じ値 を持つ平文ブロックが複数存在したとします。それらをブロック暗号のECBモード で暗号化しますと、同じ値を持つ平文ブロックは同じ値の暗号文ブロックに変換 されてしまいます。これでは、暗号文全体を見るだけで、平文の中に同じ値の繰 り返しがあることが推測されてしまいます。というのも、本来は暗号化の結果は あたかもランダム値に見えるのが理想的であり、同じビット長の繰り返しが何度 も登場する確率はほとんどありえないことです。それにもかかわらず登場してい るということは、アタッカーは暗号文だけを見ただけでECBモードのような脆弱な 方式などを採用していると推測できるわけです。さらに何らかのきっかけで暗号 文の一部分が判明した場合、それがきっかけとして暗号解読が行われてしまう危 険性もあるわけです。 　前回のWBで解説したランダム関数・擬似ランダム関数の概念を使えば、次の図 のようにもう少し数学的・暗号学的に議論できます。 （図）http://s-akademeia.sakura.ne.jp/main/image9/ecb2.jpg 　アドバーサリー（アタッカーと同意）のAは適当にmを作ります。そして、m=m_1 =m_2として、ペア(m_1,m_2)を暗号アルゴリズムM_ecb(E_k)に送信します。ここで M_ecbとはモードのMでECBを利用していることを明示する記号とします。そうする と、暗号文のペア(c_1,c_2)が送られてきます。そのときM_ecb(E_k)が本当のラン ダム関数ならばc_1=c_2になる確率はほとんどありません。しかしM_ecb(E_k)はE CBモードの暗号化アルゴリズムなので、c_1=c_2となります。そうするとAはDが本 当のランダム関数でなく、擬似ランダム関数であると認識できます。つまり、暗 号化アルゴリズムが認識できたということはECBの暗号化は安全でないことになり ます。 ■0x06.) CTRモード 　CTR（CounTR：カウンタ）モードとは、次の仕様にしたがい各m_iを暗号化する 方式です。カウンタの役割を果たす変数ctrを利用します。 [1]暗号化 　平文M=(m_1,…,m_t)に対して、c_1=m_1+E_k(ctr+1),…,c_t=m_t+E_k(ctr+t)を 計算して、暗号文をC=(c_1,…,c_t)とします。 [2]復号 　暗号文C=(ctr,c_1,…,c_t)に対して、m_1=c_1+E_k(ctr+1),…,m_t=c_t+E_k(ctr+t) を計算して、平文をM=(m_1,…,m_t)とします。ここで、DではなくEを使うことに 注意。 （図）http://s-akademeia.sakura.ne.jp/main/image9/ctr.jpg 　このCTRモードはECBモードから比べると若干複雑になっています。 　特徴としてまずブロックを任意の順番で暗号化・復号化できるということがい えます。これはECBモードでも同様でした。この特徴は実際に暗号をプログラムと して実装したときに各々の暗号化・復号の処理を並列処理させることができるこ とを意味します。 　また、暗号化と復号はまったく同じ構造をしています。まして復号アルゴリズ ムは必要なく暗号化アルゴリズムを復号処理でも利用しています。つまりプログ ラムとして実装するときはわざわざ復号アルゴリズムに対応する関数などを用意 する必要がないということです。これは次回以降紹介するOFBモードと同じストリ ーム暗号の特徴です。 　それではECBモードのときと同様に図で考えてみましょう。 （図）http://s-akademeia.sakura.ne.jp/main/image9/ctr2.jpg 　同じ平文のペア(m_1,m_2)をM_ctr(E_k)に投げてみます。すると暗号文(c_1,c_2) が返ってきますが、CTRモードの仕様によりc_1≠c_2となります。これだけ見ても ECBモードよりも安全性の意味で強くなっていることがわかります。 　実はAが2^nの計算能力があれば、CTRモードは安全でないことが証明されていま す。しかしながら一般のコンピュータはそれほどの能力は持たないので（多項式 時間しか計算できないから当たり前）、CTRモードは推奨されています。 ■0x07.) CTRモードと情報理論的な安全性について 　前回と今回のWBの内容がきちんと理解しているかどうかを確認するために、CT Rモードについての問題を解いてみましょう。答えは伏せておきますので、自力で 解いてみてください。前回のWBで置換や関数の総数の計算方法をしっかり理解し ておき、今回のWBで情報理論的な安全性の定義について理解しておけば、解ける はずです。解答は質問掲示板の暗号関係スレッド（次のURL）でお待ちしておりま す。また、ヒントが欲しいなども歓迎します。 http://ruffnex.oc.to/ipusiron/cgi/forum/patio.cgi?mode=view&no=1004 問：CTRモードについて、次の設問を解け。 （1）平文M=(m_1,m_2)に対する暗号文がC=(ctr,c_1,c_2)であった。このときの E_k(ctr+1)およびE_k(ctr+2)の値を求めよ。 （2）ランダム関数族をブロック暗号として用いるCTRモードを考える。アタッカ ーが暗号文C=(ctr,c_1,c_2)を入手した。このとき、平文が(m_1,m_2)である確率 を求めよ。 （3）ランダム関数族をブロック暗号として用いたCTRモードは、情報理論的に安 全であることを証明せよ。 （4）ランダム置換族をブロック暗号として用いるCTRモードを考える。アタッカ ーが暗号文C=(ctr,c_1,c_2)を入手した。このとき、平文が(m_1,m_2)である確率 を求めよ。 （5）ランダム置換族をブロック暗号として用いたCTRモードは、情報理論的に安 全でないことを証明せよ。 ■0x08.) おわりに 　今回はこれで終わりです。段々と数学的表記を用いているので難しく感じるか たもいらっしゃるかもしれません。初学者向けの暗号本だと単に暗号の仕様（例 えばDESやAESの原理）だけを記述してあるものがあります。それはそれで大事で すが、暗号を学問としてやる場合にはそれだけでは不十分です。仕様は単なる知 識であって、仕様から本当に安全かどうかを数学的に判断できる力こそが重要な のです。その力は一朝一夕で身に付くものではありません。またそういう力を付 けるための暗号本も少ないのが実情です（あったとしても敷居が高い）。そうい た状況を踏まえ、WBの皆さんには一歩ずつ着実にそういった力を身に付けてもら いたいと思って、暗号講座を続けていきたいと思います。まだまだ続きそうです が、諦めずに考えてみてください。考えて考えて考え抜いてください。それが遠 回りのように思えますが、実際は一番の近道なのです。 　それでは来月会いましょう。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第5章：お知らせ --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○Wizard Bible（http://s-akademeia.sakura.ne.jp/wizardbible/）では随時、 執筆ライターを募集しています。 　扱う内容のテーマは広義での「under ground」です。例えば、ハッキングから サリンガスの合成法などと幅広い内容を考えています。また、各種、特殊な職業 や趣味を持った方のレクチャーなども含まれます。 　一回きりでも構いません。また、必ず、毎回連載する義務もありませんのでで きる範囲で構いません。気軽に声をかけてください。もちろん一回書いたことが ある人も気軽に声をかけてください（全く気にしていない性格なので）。 ○Kenji AikoさんがQ&Aを作ってくれました。初めて参加する人でもわかりやすく 書かれていますので、参考にしてください。 http://s-akademeia.sakura.ne.jp/wizardbible/wbQandA.html ○支援者、参加希望者用のスレッドを立てました。 http://ruffnex.oc.to/ipusiron/cgi/forum/patio.cgi?mode=view&no=17 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第6章：著者プロフィール --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■金床 ●Job: プログラマー ●Web: http://guardian.jumperz.net/, http://www.jumperz.net/ ●Mail: anvil@jumperz.net ●この夏の目標: 　特に目標とか立てずにだらだら行くタイプなので、この夏も特に何も考えてな いですね。わはは。 　まぁ基本的に不健康な身体を何とかすることと、少し体の調子が良くなってき たので今まで溜めてたいろんなことを少しずつ消化するって感じでしょうか。 　WebAppSecをテーマに本を書くことにしたので、今はとりあえずそれを少しずつ きっちり進めるようにしてます。 よし、本を書くぞ →資料集め →色んなウェブアプリケーションの動きを研究しなきゃ →プロキシツールが必要だな →やっぱここは自前だろ →ツール作りにかまける →やっとツールが出来てきたので本格的に執筆開始　←いまここ 　とりあえず今年中に原稿完成が目標ですが、ぎりぎり難しそうな感じです。 「…オレのExploitを載せてくれ！」とかありましたら送ってください（ないか）。 ■Kenji Aiko ●Job: Student ●Web: http://ruffnex.oc.to/kenji/ ●Mail: kenji@ruffnex.oc.to ●Team（Group): N/A ●Comment: 　漫画の「MONSTER」を全巻読みました。いやー、これ面白いです。 ●この夏の目標: 　ゆっくりすること。とにかくゆっくりする。ぐったりする。だらける。うにゅ ーん。 ■Defolos ●Job: Student ●Web: http://ruffnex.oc.to/defolos/ ●Mail: defolos@ruffnex.oc.to ●Team（Group）: none ●Comment: 　こんにちは、Defolosです。 　前回のレポートで次回はHTMLについて詳しく書くと言っておきながら、全然関 係ないニューラルネットワークについて書いてしまいました。この分野は私も全 くの初学者で、自分の調べたことをまとめただけですので間違えが多いかもしれ ません。不完全なレポートとなってしまって申し訳ありません。 ●この夏の目標: 　この夏は嫌いで苦手な数学をもう少しマシにしたいと考えております。文型コ ースでしたので高校2年から数学の授業が消えました。ですので数2あたりからの 復習を中心に微積と線形代数、離散数学をやりたいと思ってます。 ■IPUSIRON ●Job: 学生・テクニカルライター・ごろごろ師 ●Web: http://akademeia.info/ ●Mail: ipusiron@ruffnex.oc.to ●Team（Group): ruffnex ●Comment: 　新刊の原稿執筆の追い込みなどと重なり、2ヶ月ぶりのリリースとなりました。 無事新刊の赤字校正も終わりつつあり、おそらく来月には発売されると思います。 本の内容はスパムメールですが、英語の論文を濫読してスパムメールを研究テー マにしている院生レベルまではがんばったつもりです。セキュリティの分野から するとスパムメールは地味かもしれませんが、結構知らないことばかりで目から 鱗の話題もあると思いますので興味ある方は是非読んでみてください。 ●この夏の目標: 　SAS2006第1回目は無事終えることができました。思った以上に参加者も集まり、 真面目に何かを学ぼうと思っている人はこんなにもいるんだと実感しました。随 時SASのメンバーは募集しておりますので、興味あるかたは是非メールください。 http://akademeia.info/index.php?SAS2006#tb7af9b1 　また暗号の研究のほうも順調に進んでおります。研究テーマ・研究課題も決定 し、それに関する論文を読み漁り模索しているところです。本当はM2までに結果 を出せれば十分なのですが、M1の段階である程度の新しい結果を残せるようにが んばりたいと思っています。