数学が嫌いな人も、原理が分かれば面白くなります。また数学に造詣のある人は、今後ひょっとしたら画期的な理論を考案して、ITの世界に革新をもたらすかもしれません。例えば、スパースモデリングはCTスキャンや宇宙観測の領域に革命をもたらしました。暗号も言わば関数y=f(x)ととらえることができます。あるデータx(数値や文字)を入れると関数f(x)によって意味不明の値yに変換され、それを見ても真の意味は理解されませんが、別の関数x=g(y)で伝えたい情報データxが復元されるという仕組みです。

素因数分解と暗号の関係

前回に続いて暗号を特集してみたいと思います。私も公開鍵と秘密鍵の関係が中々分からなかったので、その点を重点的に書きたいと思います。私の場合、「公開鍵で暗号化されたものがどうして秘密鍵で再現できるのか?」というカラクリが全く理解できませんでした。Webを見ても、身近な文献を読んでも、概念的で具体的に書いてなかったからです。

【正解】2581の値は2となります。何故、2になるのかを考えてください

右記に非常に単純な暗号クイズがあります。頭のリフレッシュの意味でみなさんもチャレンジしてみてください。問題を見た時に、条件式の値が0から6までであることに着目した人は理科系の人かもしれません。私も最初はこれは7で割った余りなのかなと直感しましたが、全く違っていました。最終的には4桁が同じ「0000」「6666」「9999」は4なのに対して「1111」「2222」「3333」「5555」「7777」は0ということからやっと解けました。特に前者の3つの数値に共通するものを考えると簡単かもしれません。私の場合、それでも10分以上かかったので、我ながら頭が固いなあと思い知らされました。事ほど左様に暗号に潜むアルゴリズムを解析するのは難しいのです。この問題はコンピューターを使っても解けないかもしれません(視覚的解法といったところでしょうか)。

みなさんは素数を小学校の時に習いましたよね。素数の定義は、1とその数自身でしか割れない自然数(正の整数)です。従って2という数字の例外を除くと、奇数しか素数にはなりえません。1は素数に加えませんので小さい順に「2、3、5、7、11、13、17、19、23、……」といった感じになります。RSA暗号ではこの素数の持つある特性を利用しています。下図にあるように素数と素数の掛け算は電卓を叩けばすぐ答えが出ますが、ある数を素数に分解するのは困難(桁数が多いと実質不可能)という特性があります。2つの素数をP、Qとした時にA=P×Qの式を素因数分解と言います。

絞り込みなしで順次に演算をしていく場合、演算回数のべき数を推定すると最大10の80乗程度必要になる。一方CPUの1秒当たりの演算処理回数を10の10乗と仮定すると、必要な演算時間は10の70乗程度(秒)となる(注:Loop処理やディスクへの書き込み時間は無視)

このような天文学的な素数のマトリックスがあれば、値Aを検索して割り出すことができるのでしょうが、検索自体も恐ろしく時間がかかることでしょう

例えばA=34,579を素因数分解しようとすると、人力ではとても解く気になりません。凄く原始的ですが、Aを3で割ってみたり、7で割ってみたりと順番に素数で割っていき確かめるしかないのです。ちなみに34,579=151×229です。5桁の数値Aでこれくらいですから、10の160乗規模の数値になると、人力はおろかコンピューターと言えど、解くのに何カ月あるいは何年かかるか分かりません。現代の進化した数学の理論をもってしても、素因数分解を効率的に解析するアルゴリズムはまだ発見されていないのです。ちょうど半導体のように片方向には電流を通すけど、反対向きには電流を通さないというのと似ています。

では、こんな面倒くさい素因数分解を何に使うのという疑問が湧きますよね。そう、この素因数分解は暗号化における公開鍵に活用されるのです。それは2つの理由からです。

【理由1】
桁数の多い整数Aから素因数分解で素数P、Qを求めるのは極めて困難である。

この性質は暗号の世界では極めて有用なのです。仮に数年後に解読された時には情報の価値がなくなっているのです。

【理由2】
素数の積が持つ面白い特性が活用できるのです(詳細は後述)。

理由2を理解する上で最低限知っておいた方が良い決まりがあります。数学でいう法(ほう)について簡単にご説明しますので、頭に入れておいてください。決して難しい内容ではありませんので。

一言でいうと、全ての数を「割り算の余り」だけで表すという約束事です。ある整数Xを整数Yで割った余りをZ(整数)とします。当然余りZは0からY-1までの整数となります。この時に余りZを作り出すことをY(割る数)を法とする世界と言います。法の表現方法と定義は数学の世界の決め事なので、そのように覚えてください。

【法の例】
15を法とした時の21の値は21÷15=1…余り6ですから6を指します。15で割った余りで表すので、全ての値は0から14までになりますよね。