都内で働くSEの技術的なひとりごと

都内でサラリーマンやってます。マイクロソフト系(たまに、OSS系などマイクロソフト以外の技術も...)の技術的なことについて書いています。日々の仕事の中で、気になったことを技術要素関係なく気まぐれに選んでいるので記事内容は開発言語、インフラ等ばらばらです。なお、当ブログで発信、発言は私個人のものであり、所属する組織、企業、団体等とは何のかかわりもございません。ブログの内容もきちんと検証して使用してください。よろしくお願いします♪

数学の勉強がてら、RSA 暗号についても少し勉強してみた

 もともと、私理系なんですが、数学が苦手でした.....統計とか色々と学ばなくてはいけなくなり、数学のお勉強をしています。けど、どれも専門的すぎて中々手がでません。(理系なのに....) 

 最近、Nexus 7 を買って、kindle の利用を再開しました。そこでたまたま出会ったのが、『世界を読み解く 数学入門』です。

 内容はまったく専門的ではなく、数学書といった感じをまったく受けません。具体的な事象を題材に、軽快に書かれています。その中でも、RSA 暗号についての内容に興味を惹かれました。

 RSA 暗号とは、

1977年に発明され、発明者であるロナルド・リベスト (Ron Rivest) 、アディ・シャミア (Adi Shamir) 、レオナルド・エーデルマン (Len Adleman) の頭文字をつなげてこのように呼ばれる。当時、ディフィーヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年チューリング賞を受賞した。

RSA暗号は次のような方式である: 鍵ペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な正整数 e(通常は小さな数。(65537 =216+1) がよく使われる)を選択する。また、大きな2つの素数 {p ,q } を生成し、それらの積 n (=pq) を求めて、{en } を平文の暗号化に使用する鍵(公開鍵)とする。2つの素数 {p ,q } は、暗号文の復号に使用する鍵(秘密鍵)d の生成にも使用し (d=e^{-1} \pmod{(p-1)(q-1)}) 、秘密に保管する。

  • 暗号化(平文 m から暗号文 c を作成する): c = m^e \mod n
  • 復号(暗号文 c から元の平文 m を得る): m = c^d \mod n

ここで、暗号化(e 乗)は、{en } があれば容易に計算できるのに対して、復号(e 乗根)は、「n の素因数を知らないと難しい(大きい合成数の素因数分解も難しい)」と考えられている。つまり秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。

RSA暗号のアルゴリズムは、1983年9月20日アメリカ合衆国特許(4,405,829号)を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。

暗号の用語については、暗号の用語暗号理論の用語を参照。

 上記の説明だけみると非常に難解ですが、この本では具体的かつ分かりやすく説明されています。その他にも数学の基礎に多く触れられていますし、コンピューターの基礎としても最適な本だと思います。情報処理試験などの対策にも非常に役立つと思われます。

 この著者は、それ以外にも数学に関する著書がいくつかあるようですね。以下の本もついついポチってしまいました。

完全独習 統計学入門

完全独習 統計学入門

 

 さぁ、数学の勉強、少しまじめにやることにします。