本記事で学べること

・RSA 暗号
・楕円曲線暗号

はじめに

前回は共通鍵暗号について紹介しました。そこで今回は、共通鍵暗号の対となる、公開鍵暗号の詳細について紹介したいと思います。

 
(暗号入門1, 2 をまだ見ていない方はこちらもチェック↓)

暗号入門 1（暗号の基本編）

暗号入門 2 （共通鍵編）

公開鍵暗号方式とは

公開鍵暗号方式とは、暗号化と復号に異なる鍵を使用する暗号方式です。暗号化に使用する鍵を公開鍵、復号に使用する鍵を秘密鍵と呼びます。公開鍵は誰でも知ることができますが、秘密鍵は知っている人のみが復号を行うことができます。

代表的な暗号

公開鍵暗号方式の代表的な暗号には、RSA　暗号と楕円曲線暗号があります。以下ではこれら2つの暗号について説明していきます。
 

RSA 暗号

RSA 暗号は、1977年にRon Rivest、Adi Shamir、Leonard Adlemanの3人の暗号学者によって提案されました。
RSA暗号の仕組みについて説明します。はじめに使うのは、オイラーの定理です。
オイラーの定理とは、素数 p, q に対し、p, q を約数に持たない整数 a に対し、N = pq とするとき、

a(p-1)(q-1) ≡ 1 (mod N)

が成り立つという定理です。この両辺を k 乗してから両辺に a をかければ、

ak(p-1)(q-1) ≡ a (mod N)

となります。ここで、

ed = k(p-1)(q-1) + 1

となるような e, d を選ぶことができれば、e と N のペアと d と N のペアができます。(e, N) は閉める鍵（公開鍵）で、(d, N) は開ける鍵（秘密鍵）です。メッセージ M に対し、(e, N) を用いると、

C ≡ Me (mod N)

という暗号文ができあがります。次に、(d, N) を用いて、この C を d 乗すれば、

Cd ≡ (Me)d ≡ Med ≡ Mk(p-1)(q-1) + 1 ≡ M (mod N)

となり、元のメッセージ M が復号されます。

楕円曲線暗号

楕円曲線暗号は、y2 = (x の3次式) で表される楕円曲線上の離散対数問題の困難性を利用して情報を暗号化・復号化する技術です。楕円曲線上の離散対数問題とは、有限体上において、楕円曲線上のある点 P からの接線と交わる楕円曲線上の点を P + P = 2P と定義したときに、ある点 P と Q が与えられれば、Q = mP となるスカラー m が求められるのか、というものです。
ここでは楕円曲線上の離散対数問題を応用した楕円曲線エルガマル暗号の仕組みについて説明します。
まず、メッセージの受け手の秘密鍵を dB、ベースポイントを G とし、公開鍵を

PB = dBG

とします。メッセージの送り手はメッセージ M に対し、乱数 r を選んで、

C1 = rG
C2 = M + rPB

とします。ここで、M は元々のメッセージ M を楕円曲線上の点として表現した点です。その後、送り手は、暗号文 (C1, C2) を受け手に送ります。C1 は G を乱数倍したものであり、楕円曲線上の離散対数問題が困難ならば、r が知られることはありません。C2 はM に公開鍵を乱数倍した点を足しているため、ランダムにしか見えないでしょう。
暗号文を受け取った受け手は、自身の秘密鍵を用いて、

C2 – dBC1 = M + rPB – dB rG = M + rPB – rPB = M

として、メッセージ M を復元できます。

RSA 暗号と楕円曲線暗号はどちらが主流か

RSA 暗号を実際に応用するには、多数の素数を用意しなければならないことや、電子署名の処理速度が遅い点などが問題になります。一方で、楕円曲線暗号は、近年、処理が高速化され、使い勝手がよくなってきました。実際、米国の NIST は、電子署名アルゴリズムとして RSA 暗号ではなく、楕円曲線暗号を推奨しています。

まとめ

本記事では、公開鍵暗号方式の詳細について紹介しました。公開鍵暗号の原理を理解し、これからの仕事に役立てていただければ幸いです。