暗号理論と整数論(その2)

2006/05/22

2006.5.22
東海大学 情報数理学科 講師 志村 真帆呂

RSA暗号系

RSA暗号系は、素因数分解の困難さを安全性の根拠にした公開鍵暗号系です。
たとえば、
3921727133=17443*224831
という等式が成り立つのは掛け算を実行して確認できます。しかし、3921727133という数から右辺の素因数分解を求めるのはとても大変です。ここでは正確な手順は説明しませんが、この数字を例にしてRSA暗号系の要点を書いてみます。

  1. 情報を暗号で受け取りたい人(Aさん)は、17443*224831を計算した答の 3921727133を公開鍵として公開する。
  2. 情報を暗号で送りたい人(Bさん)は、 公開鍵3921727133を用いて送りたい文を暗号にする。
  3. 17443*224831を知っているAさんは、それを用いると非常に速く暗号を解読できる。
  4. 公開鍵3921727133だけを知っている第三者(Cさん)が暗号を解読しようとしても 素因数分解がわからないと非常に長い時間がかかってしまい、 実際には解読できない。ただし、時間を気にしなければ理論的には解読はできます。

このように、暗号を作る鍵と解く鍵を別々にすることで安全な情報のやりとりが できるわけです。

実際には3921727133は非常に小さいので、これで暗号を作ってはいけない。 また、素因数分解もコンピュータを用いれば簡単にできてしまいます。
しかし、とても長い桁の数を用いても原理は同じなので、 あえて小さい数を使いました。

代数曲線暗号

公開鍵暗号は、RSA暗号以外にもあります。その一つが代数曲線暗号です。代数曲線暗号で有名なものには、楕円曲線暗号や 超楕円曲線暗号があります。

代数曲線暗号は、曲線のヤコビ多様体の上の点同士の足し算ができることを利用した 暗号です。足し算があると、n回足す操作、つまりn倍があります。

ヤコビ多様体の上の点P,Qの間に
Q=nP
という関係があったとします。n,PからQを計算するのは簡単です。 しかし、P,Qだけからnを求めるのは非常に大変になります。これを利用すると、RSA暗号と同様に公開鍵暗号ができるわけです。

どの公開鍵暗号がよいか

暗号の優劣は、次のような様々な要因で判定されます。

  • 暗号化、複号化の処理速度が速いか。
  • 性能が低いコンピュータの上でも動くか。
  • 安全な暗号を簡単かつ、大量に作れるか。

たとえば、私が研究している超楕円曲線暗号のメリットの一つは、同じ安全性を持つ 暗号を作ろうとしたときに必要なメモリのサイズが最も小さくなることです。デメリットの一つは、数学的に構造が複雑なので様々な攻撃法が考えられ、 その全てに対して安全な暗号を作らないといけないことです。私の研究テーマの一つは、暗号に対する攻撃法を検証し、どのような曲線ならば 安全かを判定することです。

暗号と整数論の関わり

整数論は、上で述べたような問題を理論的に解決するためにも欠かせないものです。暗号への応用がすぐに見つかるかどうかに関係なく、整数論の研究は大事です。最後に、私の行っている研究を中心に暗号と整数論に関連したトピックスを列挙しておきます。

  • 素数判定、素因数分解アルゴリズム
  • 素数のより深い性質を知るための、ゼータ関数やディリクレ関数の研究
  • 楕円曲線を統制しているモジュラー曲線の研究
  • 楕円曲線暗号、超楕円曲線暗号に対する攻撃法、特にヴェイユ降下攻撃と呼ばれる攻撃法の研究

見慣れない言葉ばかりで尻込みしてしまいそうですが、 実際には数値実験を大量に行う研究が多く、大量のデータを処理する 技術を研究に役立てながら覚えられるといったメリットもあります。その応用として、数学関連の教材を効率的に作成するといったこともできます。