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カテゴリと型システムはまったく無関係なのだ。

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.ブーフマン著 林 芳樹訳)