|
 |
 |
|
講師： 織田孝幸（おだ・たかゆき）
日時： 2006年７月２７日 |
|
| 数学カフェ 「素数」 |
|
 |
|
 |
三井： 後半を始めます。ご質問の中に多かった素数と暗号との関係を話題にしたいと思います。
これは数学の問題ですけれど、コンピュータ関係で詳しい方がおられるかもしれませんね。
では、始めに、寺杣さんにお話して頂きます。
寺杣： 科学技術に関する財団法人（情報処理推進機構という独立行政法人？）
がありまして、そこでは、国家的プロジェクトとして、素数の生成プログラムとか判定法についての研究がなされています。
素数は暗号に利用されますので、素数をどうやって生成するかというのは大問題で、機密を守るという意味で、
非常に重要なものになっています。
ここで言う暗号というのは、Ａという人とBという人が、お互いに他人には見破られない暗号を使って通信するというような暗号
ではありません。公開鍵暗号という特殊なものです。たとえば、インターネットで、あるサイトに入ってモノを買うときに、
クレジットカードの番号を入力して送信します。そのとき、お客さんの側は、サイトを経営している人から、ある情報、つまり、
公開鍵を得て、クレジットカードの番号を暗号化して送っているわけです。そして、その暗号を元に戻すための鍵を秘密鍵といいます。
暗号化するときの鍵（公開鍵）と元に戻すときの鍵（秘密鍵）が異なるというところがミソです。
その原理は、素因数分解がすごく難しいということが一つと、もう一つは、素数の判定は簡単であるということです。
ある数が素数かどうかというのは、素因数分解をしなくても判定できる。ただし、今のところは、
確率的に判定するという方法をとっています。
何億回に１回くらいは素数じゃないかもしれないという確率を含んでいるけれども素数らしいという素数を使っています。
そうした二つの素数を掛け合わせて合成数にすると、とてもじゃないけど、もう因数分解はできないという上手い仕組みです。
これは、素因数分解の良いアルゴリズムがないということを前提にしていますから、その前提が破られますと、
暗号は直ちに読まれてしまいます。例えば、同じくらいの大きさの素数を掛けて作った合成数は、
簡単なアルゴリズムで因数分解されますから、そういうものは避けるようにするわけです。
織田： 先ず、暗号には2種類あります。英語でいうと、"code"と"cipher"です。
Codeは、"code book"というのがあって、ある小説の何ページの何行目に対応するというようなものですが、今、
このcodeは問題にしません。
Cipherというのは、換字式といって、最も古い（紀元前1世紀頃）暗号の一つであるシーザー暗号（Caesar cipher）では、
文字単位で換えていきます。アルファベットの文字を何文字かずらして書く方法です。もっと古く（紀元前500年頃）には、
棒に細い紙を巻きつけて、それに字を書いて、その紙を解くと、文字の並び方が変わるというのもあります（スキュタレー方式）。
クレジットカードの番号を暗号化する場合には、ある一定のやり方で、その番号から別の数をつくりだすんです。
掛け算と割り算でつくりだす。それが換字式暗号です。問題は、掛け算と割り算をやる手続きですね。
こういう方法でやるという手続きを鍵として指定するわけです。普通、そのやり方、すなわち、鍵は、両方とも秘密にしているんです。
一般的に、商用暗号はそうなっています。アメリカには、有名なDES（Deta Encryption Standard）と呼ばれる商用暗号がありますし、
日本だと、NTTが開発したFEAL（Fast Data Encipherment Algorithm）というのがあります。これは商用なので、
特定の人どうしで暗号を遣り取りするときに使います。銀行などが、本店と支店との間で遣り取りする情報に使っていると思います。
寺杣さんが言われたのは、そういうものと違って、一方が不特定他者の場合です。普通は、情報を出すほうが不特定他者で、
受け取るほうが特定の人です。入力した情報を暗号にするほうの手続きは、もう世界中に公開している。
解くときに必要なキーは隠している。そういう一方的な方法です。発見されたのは、1970年代の後半で、 そんなに昔じゃない。
割合新しいやり方です。時代の必要があると新しい発明ができるという例ですけど、RSAという三人の発見者
（Rivest、Shamir、Adleman）の頭文字を冠したRSA暗号という公開鍵暗号です。そのおかげで、インターネットを使ったサービスも、
絶対安全かどうか知りませんけど、ある程度安全にできるようになったということです。
その中で一番大事なのは、落とし戸関数（trapdoor function）というもので、ある合成数があったときに、
それを素数の積に分解するのは難しいけど、素数そのものをつくるのは簡単にできるという、そういう差を使ってやっている。
でも、合成した数を素因数に分解するのは、本当に時間がかかるのかどうか、証明されたわけじゃない。ただ、今のところは、
どうやっても速い方法が見つからないから、難しいと信じている。誰かが新しい方法を考えついたら、
秘密が皆バレてしまうという可能性は、先ずないと思いますけど、絶対ゼロとは言えない。そういう仕掛けを利用しています。
三井： 数学というのは、もっと厳密なものだと思っていたら、
けっこういい加減なところがあるようなお話ですけど、実用的だということですか。
織田： 世の中複雑になったせいだと思うんですけど、いろんなところで、
数学で最近発見されたことがすぐ使われるということがあります。割に有名なのは、ソリトン（soliton）と言われるもので、
運河の表面にできる波、浅水波というんですけど、この波が何百メートルも形を崩さずにいくというのがある。
これをソリトン波というんですけど、解が発見されて20年ぐらいで、通信に利用された。光ファイバーの中でそういう波を作ると、
なかなか弱まらないんです。これは非常に速く応用された例です。
三井： 皆さん、暗号のお話は、分かって下さいましたか。
|
|
|
|
|
|
|
