東海大学理学部情報数理学科暗号理論と整数論(その１)

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

2006/04/24

2006.4.24
東海大学情報数理学科志村真帆呂

暗号理論の技術的な話をする前に、実際に世の中で暗号がどのような場面で使われているのか、あるいはどのような使われ方が考えられているのかを、ほんの一部ですが簡単に見てみましょう。

機密文書 盗難などにより第三者の手に渡っても情報が漏れてはいけない文書。企業秘密、外交文書など。

認証重要な手続きなどを行う際に、本人であることを確認する仕組み。たとえばキャッシュカードでは、暗証番号を用いた認証をしています。

パケット(ブロック)通信 情報を一定のサイズに分割(その一つ一つをパケットといいます)して送る通信。
電子メールなど。

ストリーム通信 連続する情報を次々に送る通信。画像、音声などの通信

電子投票投票の集計の高速化や、遠隔地からの投票が簡単になるといった利点がある投票システム。電子端末から投票を行います。

暗号の仕組みは基本的にはとても簡単です。

やることはこれだけですが、状況によってどのような暗号の方式を使ったらいいかなどの問題を考える必要があります。

暗号を使う一番の目的は、秘密を安全に伝えるということです。しかしながら、使う状況や目的によって求められることは違ってきます。

暗号はしばしばインターネット上で使われますが、インターネットの情報はどのような経路を通るかわからないので第三者に見られてしまう可能性があります。

暗号化、復号化の速度 暗号文にしたり、元の文に戻す作業に時間がかかりすぎてはいけない。たとえば、ストリーム通信を暗号化するのにリアルタイムで処理できないと生中継に使えない。

暗号の安全性 鍵を用いた正規の手順以外の方法で、簡単に暗号が解かれてはいけない。

鍵をどうやって渡すか 通信が第三者に見られる状況で、一番最初にどうやって鍵を渡したらいいか。あるいは、鍵を見られても安全な暗号が作れるか。

上記の問題を解決する方法の一つとして、整数論と呼ばれる数学の理論が用いられます。
すると、次のようなことができます。

暗号を作る鍵と元の文に戻す鍵を分けることにより、暗号を作る鍵を第三者に見られても(確率的に)安全な暗号が作れる。この暗号を公開鍵暗号といいます。
暗号を作る鍵と元の文に戻す鍵が同じ暗号を共通鍵暗号といいますが、先に述べたように鍵をどうやって送るかという問題があります。
公開鍵暗号の安全性は、鍵なしで暗号を解読しようとすると計算量(計算の手間)が膨大になるという事実に依存しています。

この理論的な裏付けに整数論が用いられます。様々な暗号の仕組みや、問題点、攻撃法に関する研究などは次回に説明します。