2013年12月29日日曜日

C++11のlvalueとrvalueで引っかかるところ

lvalueとrvalueについて、僕が引っかかったところをメモしておく。

とりあえずひと通りは江添氏の本の虫で読めば分かる。

本の虫

ここから先は本の虫の記事を読んでもイマイチ腑に落ちない人向けである。以下の様なコードを考える。


#include <iostream>

void f(int&& i){
    std::cout << "rvalue" << std::endl;
}

void f(int& i){
    std::cout << "lvalue" << std::endl;
}

void g(int&& i){
    f(i);
}

int main(){
    int i = 0;
    g(std::move(i));
}

さて、ここで出力はどうなるだろうか? Wandboxで確かめてみよう。

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

出力が「lvalue」であることが確認できただろうか。

なぜか?

関数gの仮引数iがlvalueだからである。

言い換えると、iはrvalueリファレンス型のlvalueだからである。

つまり、「rvalueリファレンス型のインスタンスである」ということと、「rvalueである」こと、すなわち「rvalueリファレンスでキャプチャされる」ということは本質的に無関係である。

C++におけるvalueカテゴリと型システムはまったく無関係なのだ。

2013年12月15日日曜日

RSA暗号の特徴と原理

この文章では非対称鍵暗号の一種であるRSA暗号についてその特徴と原理を説明する。

対称鍵暗号と非対称鍵暗号

暗号には対称鍵暗号と非対称鍵暗号の二つの種類がある。暗号化の鍵と復号化の鍵が同一であれば称鍵暗号で、そうでなければ非対称鍵暗号である。

対称鍵暗号は非対称鍵暗号よりも一般的に頑強であり、かつ高速に暗号化と復号化の処理ができるが、鍵をいかにして安全に配送するかという問題(鍵の配送問題)が生じる。鍵の配送問題とは次のようなものである。ここでは、暗号化には対称鍵暗号を用いるとする。

ある秘密のメッセージを安全に送るには送信者はその秘密のメッセージを暗号化する必要があるが、受信者が暗号化された秘密のメッセージを復号化するには鍵が必要であるため、その鍵も安全に送る必要がある。すなわち、その鍵を安全に送るためにその鍵を暗号化する必要があるが、今度は暗号化された鍵を復号化するための鍵を安全に配送しなければならないという問題が生じる。

この、鍵を安全に送る問題には終わりがないため、対称鍵暗号では安全なメッセージをやり取りすることは本質的にできないことが分かる。

これに対して非対称鍵暗号は対称鍵暗号に比べれば一般的に脆弱であり、かつ暗号化と復号化の処理に時間がかかるが、鍵の配送問題を回避することができる。非対称鍵暗号がいかにして鍵の配送問題を回避するかを以下に手順として示す。ここでは、アリスがボブに秘密のメッセージを送ることを考える。

  1. ボブは暗号化用の鍵と復号化用の鍵のペアを生成する。
  2. ボブは暗号化用の鍵を公開する。公開された鍵はアリスはもちろん、世界中の誰に知られても構わない。
  3. アリスはボブが公開した暗号化用の鍵を用いて秘密のメッセージを暗号化し、その暗号化した秘密のメッセージをボブに送信する。
  4. ボブはアリスから暗号化された秘密のメッセージを受け取り、復号化用の鍵を用いて復号化して秘密のメッセージを得る。

このように非対称鍵暗号は鍵の配送問題を回避することができる。

現実の暗号システムの多くは対称鍵暗号と非対称鍵暗号を組み合わせて利用している。すなわちメッセージの暗号化には対称鍵暗号を用い、対称鍵暗号で用いた鍵を非対称鍵暗号でやり取りする。普通、メッセージに対して鍵ははるかに小さい。ゆえに、こうすることでメッセージ全体に非対称鍵暗号を適用した場合よりも高速にメッセージをやり取りすることができる。

非対称鍵暗号の鍵のペアが持つべき性質とRSA暗号

非対称鍵暗号で使われる暗号化用の鍵と復号化用の鍵のペアは上述したやり取りを安全に行うために、次の性質を満たさなければならない。

  • 暗号化用の鍵と暗号化されたメッセージから、復号化用の鍵を推測することが困難である。
  • 暗号化されたメッセージは復号化用の鍵で容易に復号化できる。

ところで、ある大きな数を分解して素因数を導出することは困難であるが、逆にその素因数からその大きな数を導出することは容易である。RSA暗号はこの事実を利用して上述の性質を満たす鍵を構成する。

RSA暗号の手順

ここでは、上述したアリスがボブに秘密のメッセージを送ることを考え、具体的にどのような手順を二人が行うかを示す。

  1. ボブは無作為に素数pとqを選び、その二つの積nを求める。

    さらに次の条件を満たす自然数eを選ぶ。 \[1<e<(p-1)(q-1)\,かつ\,eと(p-1)(q-1)の最大公約数が1である。\]

    そして、次の条件を満たす自然数dを求める。このようなdはeが満たす条件から必ず存在する。 \[1<d<(p-1)(q-1)\,かつ\,ed\equiv1\mod{(p-1)(q-1)}\]

    暗号化用の鍵は(n, e)、復号化用の鍵は(n, d)である。

  2. ボブは暗号化用の鍵(n, e)を公開する。

  3. アリスはボブが公開した暗号化用の鍵(n, e)と秘密のメッセージmから次の式を使って暗号化されたメッセージcを求める。 \[c\equiv m^{e}\mod{n}\]

  4. ボブは自分しか知らない復号化用の鍵(n, d)とアリスから受け取った暗号化されたメッセージcから、次の式を使って秘密のメッセージmを求める。 \[m\equiv c^d\mod{n}\]

RSA暗号が正しく復号化できる証明

RSA暗号の復号化は次の定理に依っている。 \[(m^{e})^{d}\mod{n}=m\]

この定理は次のように証明される

dが満たす条件\[ed\equiv 1\mod{(p-1)(q-1)}\]より、\[ed=1+l(p-1)(q-1)\]となるlが存在する。 よって\[(m^{e})^{d}=m^{ed}=m^{1+l(p-1)(q-1)}=m(m^{(p-1)(q-1)})^{l}\]が成立し、 ゆえに\[(m^{e})^d\equiv m(m^{(p-1)})^{(q-1)l}\mod{p}\]である。

ところでフェルマーの小定理を次に示す。

nが素数であれば、nとの最大公約数が1である全ての整数aについて、\[a^{n-1}\equiv 1\mod{n}\]が成立する。

今、pがmの約数ではないと仮定すると、pは素数でありpとmの最大公約数は1なので、フェルマーの小定理より次の等式が成立する。 \[m^{(p-1)}\equiv 1\mod{p}\] よって、\[(m^{e})^d\equiv m(m^{(p-1)})^{(q-1)l}\equiv m(1)^{(q-1)l}\equiv m\mod{p}\]である。 また、pがmの約数であると仮定しても、両辺は\[0\mod{p}\]となるので同様に等式が成立する。 よって、pがmの約数かどうかに関わらず、\[(m^{e})^{d}\equiv m\mod{p}\]が成立する。

pとqの対称性より、qについても同様に\[(m^{e})^{d}\equiv m\mod{q}\]が成立する。 pとqは異なった素数であるから、pとqの積であるnについて\[(m^{e})^{d}\equiv m\mod{n}\]が成立する。よって示された。

RSA暗号の安全性

RSA暗号を破るには任意の自然数を高速に素因数分解できなければならないと考えられている。そして今のところ、数十年にもわたる多くの優秀な数学者たちの努力にも関わらず、大きな自然数の素因数分解を高速に実行するアルゴリズムは発見されていない。また、そのようなアルゴリズムが存在することも証明されていない。このことから、今のところRSA暗号は正しく運用されれば安全であると考えられている。

ただしRSA暗号を破るには自然数を高速に素因数分解することが必須であるとは証明されておらず、未解決問題の一つとなっている。

また、量子コンピュータを用いれば任意の自然数を高速に素因数分解できる可能性が示唆されており、そういった計算機の著しい能力の向上によってRSA暗号の安全性が脅かされることは有りうる。

任意の自然数を高速に素因数分解する能力を持つ攻撃者オスカーが存在すると仮定する。上述したRSA暗号についてのアリスとボブの例において、オスカーは以下の手順で秘密のメッセージを傍受することができる。

  1. ボブが公開した暗号化用の鍵(n, e)を受け取り、nとeを取り出す。

  2. nを素因数分解してpとqを得る。

  3. eとp、qを用いて上述した条件を満たすdを求める。

  4. オスカーはnとdを用いて暗号化された秘密のメッセージcを復号化して秘密のメッセージmを得る。

このように、RSA暗号は任意の自然数を高速に素因数分解する能力を持つ攻撃者に対して無力である。

参考:暗号理論入門(J.A.ブーフマン著 林 芳樹訳)

2013年11月12日火曜日

QtはMinGWのgcc4.8.1ではコンパイルできない

参考:https://qt-project.org/forums/viewthread/33370/
参考:http://stackoverflow.com/questions/18739688/compile-time-error-from-a-qt-file-expected-unqualified-id-before-token

ひとつはMinGWのバグのせい。io.hのoff64_t_を_off64_tに置換すれば解決する。
もうひとつはQtのバグのせい。MemoryBarrierという名前がWindowsのものとQtのものとで競合するため。Qt5.1.2とQt5.2では修正される予定。

しょうがないのでQt5.1.2か5.2がリリースされるまではQtをソースからビルドする場合にはQt4.8.5を使おう。
やり方は以下に以前書いた。
http://wirelessia-liberation.blogspot.jp/2012/12/windows764bitmingw-gcc47-qtsdk484.html

Qt4.8.5も無理でした。MinGWのバグのようです。
結局バイナリインストーラを使うしかないのか……

既にあるMinGW+Msys環境からMsysGitを使うシンプルなやり方

WindowsでGitを使おうとするとたいていMsysGitを使うことになるのだけれど、MsysGitにはMinGWが付属していて、既にMinGW環境がある場合にはちょっとややこしいことになる。
できれば既にあるMinGW環境でGitを使えるようにしたい。
mingw-getで入ればいいのだけれど、少なくともこの記事を書いている現在はできない。

参考:http://sourceforge.net/p/mingw/feature-requests/127/

上のリンクにすべて書いてあるけれど、改めてきちんと書き出してみる。

MsysGitをインストールする。Msysからしか使わない場合は最小構成でOK。
Program Files/MsysGit/bin/の中にあるmsys-1.0.dllを削除する。(削除しなかった場合は後述)
Windowsシステムの環境変数のPATHの末尾(というかMinGW/binより後)にProgram Files/MsysGit/binを突っ込む。

これで既にあるMinGW環境からgitコマンドが使えるようになる。
ただしgit commitでvimが起動しないのでgit commit -mで使うしかないようだ……
msys-1.0.dllを削除しないでおくとvimが起動しないままストップし、削除しておくとプロシージャエントリポイントが云々のエラーが出る。

2013年10月16日水曜日

C++11の高速フーリエ変換ライブラリ「Fftk」

をつくりました。
あまり最適化はしていないので他のFFTライブラリのほうがおそらく高速ですが、実装はシンプルだと思います。
以下にMITライセンスで公開します。
Fftk:https://github.com/okdshin/Fftk

参考:nursの日記:http://d.hatena.ne.jp/nurs/20130617/1371483633

2013年10月8日火曜日

OpenCVのVideoCaptureのバグ?

cv::VideoCaptureである特定のAVIファイルを再生しようとするとSIGSEGVエラーが起こる。
この場合は、cv::VideoCapture::setメソッドで以下のように開始フレームを0にしてからフレームを取得するようにすると解決することがある。
cap.set(CV_CAP_PROP_POS_FRAMES, 0);

参考:http://code.opencv.org/issues/3030

2013年9月5日木曜日

OpenCV2.4 + Windows7 + MinGW + msys で staticライブラリの自前ビルドとアプリケーションへのリンク


staticライブラリの自前ビルド
 まずMinGW用のMakefileをつくる。
  • cmakeを本家(http://www.cmake.org/)からダウンロードする。(windows用のバイナリインストーラでさくっとインストールするのが楽)
  • OpenCV2.4のソースファイルを本家(http://opencv.org/)からダウンロードしてきてCドライブ直下に展開する。
  • cmake-guiを起動する。
  • BrouseSourceボタンで展開したOpenCV2.4のディレクトリ(デフォルトだとc\:opencv)をセットする。
  • BrouseBuildボタンでビルド先のディレクトリ(ここではc\:OpenCV2.4MinGWとする)をセットする。
  • 今回はstaticライブラリをビルドしたいのでBUILD_SHARED_LIBSのチェックを外す。(Searchでsharedと入力するとすぐ出てくる)
  • Configureボタンを押す。
  • "MSYS Makefiles"を選択して"Specify native compilers"にチェックをつける。
  • Nextボタンを押して、CにはMinGW/bin/gcc.exeをセットし、C++にはMinGW/bin/g++.exeをセットする。(Fortranは何もセットしなくてOK)
  • Finishボタンを押す。
  • 再度Configureボタンを押す。
  • Generateボタンを押す。

 これでc\:OpenCV2.4MinGWにMinGW用のMakefileがつくられる。

 次にMinGWでMakeしてライブラリをビルドする。

  • MinGWのShellを起動する。
  • 起動したShellで以下のコマンドを入力する。
cd c\:OpenCV2.4MinGW && mingw32-make && mingw32-make install

 これでビルドが開始される。ビルドにはしばらく時間がかかるので終わるまで待つ。(makeするときに-j2とか-j4とかしてもよいかもしれない)

アプリケーションへのリンク
 mingw32-g++でコンパイルするときは、C:/OpenCV2.4MinGW/libとC:\OpenCV2.4MinGW\3rdparty\libが参照できるようにし、必要なライブラリをリンクする。

 リンクするライブラリの順番によってはundefinedエラーが起こるので、そこらへんは試行錯誤するか、調べるかして解決する。ちなみに以下のコンパイルオプションだとうまくコンパイルできた。

-LC:/OpenCV2.4MinGW/lib -lopencv_imgproc246 -lopencv_core246 -lopencv_highgui246 -LC:/OpenCV2.4MinGW/3rdparty/lib -llibjpeg -llibtiff -llibpng -llibjasper -lIlmImf 
 アプリケーションの利用するOpenCVのライブラリによっては他のライブラリ(libopencv_video246.aなど)が必要になることがあるので、その場合は適宜調べて追加すること。


インクルードパスにOpenCV2.4MinGW中のinstallディレクトリを追加しておくこと。

2013年8月2日金曜日

C++11向けパックラットパーサジェネレータライブラリ「Parsia」

C++11用のパックラットパーサジェネレータライブラリを書きました。
「Parsia」https://github.com/okdshin/Parsia

PEGがあれば構文解析器を簡単につくることができます。