traP Member's Blog

NP【新歓ブログリレー2017 16日目】

nari
このエントリーをはてなブックマークに追加

こんばんは。成です。

CTF・競プロ体験会、お疲れ様でした!大盛況で終わってホッとしています。

今回はCTFに関連して、セキュリティに関わるNPについて書きたいと思います。

NPとは

NPとは、Non-deterministic Polynomial timeのことで、日本語で「非決定性多項式時間」と言います。これに対して、Pというのがあって、これはPolynomial time(多項式時間)のことです。

多項式時間というのは、通常のコンピュータ上で計算量が多項式なものです。例えばソートアルゴリズムO(nlog_2n)や、最長共通部分列アルゴリズムO(nm)などがそうです。

逆に計算量が多項式でないものというのは、巡回セールスマン問題に対するHeld-KarpアルゴリズムO(n^22^n)や、0-1ナップザック問題O(2^n)などがあります。

こういったO(2^n)が入った問題はだいたいNPです(すごい大雑把)。

厳密には、「全ての可能性を探索できる」コンピュータ上では多項式時間で計算可能なYes/No問題をクラスNPの問題と呼びます。

全ての可能性を探索できる、というのは、ナップザック問題でいえば「アイテムを使う/使わない」という2つの可能性を同時に探索できる、というものです。量子のように全ての可能性を重ね合わせで表現するなどすると実現できるかもしれない仮想のコンピュータです。

また、Yes/No問題なので、部分和問題O(2^n)はYes/No問題なのでクラスNPですが、ナップザック問題は最適化問題のため厳密にはクラスNPではありません。ただし、ナップザック問題は例えば「価値の総和をある値以上にできるか?」というYes/No問題を用いて二分探索する方針にすると、クラスNPの問題を用いて解くことが可能となります。このようなナップザック問題のような問題はNP困難というクラスに属します。

NPの恐ろしさ

五十歩百歩ということわざがあります。

これは、50歩逃げても100歩逃げても、大体同じでしょ、という感じの意味のことわざです。

このように、たかが定数倍では特に大差無いように感じるわけです。これはコンピュータでもそうで、1000倍ぐらいだろうと定数倍なら脅威ではありません(スパコンを1000個用意すれば同じわけです)。

では、クラスNPはどうでしょう。量子コンピュータが無い場合、計算量はO(2^n)です。ここで「五十歩百歩」してみましょう。

X = 2^{50}Y = 2^{100}の差を見ると、なんとY = X^2なわけです。

指数を数倍するだけで、全体の数は大幅に増加します。これがクラスNPの怖いところで、もしn=512について解かれてしまっても、n=1024について解くには簡単に至らないわけです。

NPの解法

クラスNPに属する問題はどのように解けるのでしょうか?

有名なクラスNPの問題はナップザック問題です。これはよく動的計画法の説明で使われ、そこでは多項式時間で解けるように見えます。

しかし、このようなナップザック問題は、重さの総和が小さめに作られているために解けるわけで、重さに制限が無ければ動的計画法の手法は使えません。

クラスNPの問題は基本的に、全探索するしかありません。つまり、現実的な時間では計算不可能です。

ただし、問題の性質を良く見極めると計算量を若干ゃ下げることが可能です。

例えば、ナップザック問題や部分和問題は、半分全列挙を用いることでO(2^{n/2})程度に抑えられます。

また、グラフの最大独立集合問題も、枝刈りを適切に行うことで、指数関数の底を2未満に抑えることが可能です。

さらに、クラスNPの問題の多くは整数計画問題として容易に記述でき、整数計画問題はそれ専用の枝刈り探索アルゴリズムがあるため、ある程度速めに解を求めることが可能です。

ただし上記の手法はどれも指数関数の域を出ないため、クラスNPであることに変わりなく、恐ろしさはそのままです。

ちょっと優しいNP

ところで、巡回セールスマン問題やナップザック問題に関しては、厳密な最適解を求めずとも、十分良い解が求まれば工業的応用という意味では十分です。そのために、ヒューリスティック解法等も多く研究されています。

最適解で無ければ、指数関数的時間計算量でないアルゴリズムも多数あります。良さそうな選択肢を連続的に選ぶアルゴリズムなどもヒューリスティックになりますが、そこそこ良い解を高速に求めることが可能です。

このヒューリスティックジャンルは、最適解を求めることが目的ではなく、いかに高速に良質な解を求めるかが目的になります。

NPの使われ方

こんな難しい問題ですが、いったいどのようなことに使われるのでしょうか?

例えば、ナップザック問題はどうでしょう。ナップザック問題は「どれだけ効率よく詰められるか?」という応用的側面がそのまま問題になっています。

また、巡回セールスマン問題も、「どれだけ効率よく巡回できるか?」という応用があります。ドリルの穴開け問題に応用することで、いかに効率よく基盤に穴をあけて生産能率を上げるかにも直結します。

さらにグラフの最小頂点被覆問題は、一般的なネットワークと関わりがあります。

このような工業的な応用も多いですが、現代で最も活躍しているのは、やはり暗号的分野でしょう。

NPと暗号

突然ですが、15を素因数分解してみてください。

簡単ですね。素因数は3と5です。

では、6319はどうでしょう。

これは、71と89です。暗算は難しいですね。

では、1000000016000000063は?

これは1000000007と1000000009です。人間には難しいでしょう。

このような素因数分解は、桁数nに対して計算量が指数になり、NP困難であると予想されています(クラスPとなるようなアルゴリズムが見つかっていない)。

では、また突然ですが、3\times 5を計算してみてください。

15ですね。

71 \times 89は?

6319です。

1000000007 \times 1000000009は?

1000000016000000063。

これらはただの掛け算で、筆算すれば比較的簡単に求まります。

このように、素因数分解と掛け算には、逆操作の計算量が圧倒的に違うという性質があります。

すると、例えばある人が秘密の素数p,qを生成して、その積n=pqを公開しても、秘密の素数p,qはバレない、という一方向的な性質ができ、これとフェルマーの小定理(オイラーの定理)を組み合わせることで、有名なRSA暗号が構成できます。

RSA暗号は素因数分解の計算困難性に基づいた公開鍵暗号で、世界的に利用されています。

公開鍵暗号が存在することで、インターネット上で初対面の相手とも安全に暗号化された通信が可能となります。

この他にも、離散対数問題の計算困難性に基づいたDiffie-Hellman鍵交換、楕円曲線上の離散対数問題の計算困難性に基づいた楕円曲線暗号など、NP困難を基として様々な公開鍵暗号が構成されています。

この情報化社会はNP困難によって守られていると言っても過言ではありません。

NPの危機

しかし、安心してはいけません。

量子コンピュータが実現されれば、素因数分解が多項式時間で完了するような量子アルゴリズムがすでに作られています。

このため、近い将来にRSA暗号は崩壊するかもしれないということが危惧されています。

また、RSA暗号の内、偶然にも性質が悪くなってしまった場合には容易に素因数分解されたり、複号できてしまったりすることもあります。

NP困難と適切に付き合うことで、セキュリティを上げる必要があります。

終わりに

以上、NPについてでした。情報科学科や情報工学科に進む人にとっては避けては通れないジャンルだと思います。

NPはP≠NP予想などに言われるように未解決問題が多くあり、NP問題の解を求めるアルゴリズムやヒューリスティックは現代でも盛んに研究されているジャンルです。

特にスーパーコンピュータの性能が上がり、気軽に利用できる昨今では、計算リソースで無理やり解くなどということもできるため、RSA暗号等がどれだけ安全でいられるかなども注目されるでしょう。

セキュリティを保つためにも、どこまで解かれてしまうかのラインを知ることは重要で、CTFでもRSA暗号を攻撃する問題が多数存在します。

この機会に是非NP問題に興味を持っていただければと思います。最適解が基本的に出ないので、いくら遊んでも終わりがありません。楽しいですよ(白目)。

明日はhihumiさんとCulMenさんの記事です。

このエントリーをはてなブックマークに追加

記事へのコメント

CargoCarrier
2017年4月23日 03:52

RSA暗号は鍵方式とは言え、素因数分解の一意性に準じた
暗号論的安全性にありますから、これまでも、これからも、
強固ですが、脆弱です。鍵盗難が伴うからです
(例え量子観測事象を利用したとしても)。
証明があるか、反証に覆されるかです。体制か、反体制か。

この有様では、仮にDTMがNP問題のための解法を持つとしても、
DTMはこれまでのような戦争から抜け出せません
(例えばクラッカー同士による暗号論的戦争)。
もしそんなDTMがもっと難しい問題の解法を持っていたら?

しらみ潰し以上に難しい問題を瞬く間に解いてしまう賢者でも、
やるかやられるか、椅子取りゲームから逃げられません。
数学、文化、社会、常識は、これまでも、これからも大して変わらない事に。

しかしもっと救いようがないのは、PvsNP予想が解決されないまま、
量子コンピューティングがかつての古典コンピューティングのように
アイドル扱いされ、研究者や門外の想像力がこれまで以上に削がれる事態です。

計算可能性理論は哲学をも内包し、幅広い分野に一石を投じる
強力な分野です。しかし課題となっているPvsNP予想の難しさは、
神託機械が保証するほど難しく、PとNPの関係も示さねばなりません。

SPACEやTIMEと言った、具体性を伴う概念の専門分化が、
核心を突くかも不明です。解決までにあと100年必要かも
しれない一方で、明日には誰かが解くかもしれません。

なぜなら、解決によって多くの概念が刷新されるならば、
思いがけない形で解決が提示され得るからです。
例えば「問題」「難しい」「方程式」「代数学」に関する
現代の常識に誤謬があれば、有り得ない事も起こり得ます。

PvsNP予想は未解決問題の中でも、際立って異質で重大な問題です。

コメントを残す

メールアドレスが公開されることはありません。