楕円曲線暗号の（比較的理解しやすい）入門書

楕円曲線暗号（ECC）は、今日広く使用されている暗号の中でも最も強力で、最も理解されていないタイプの1つです。Cloudflareでは、お客様のHTTPS接続からデータセンター間のデータの送信方法まで、ECCを幅広く活用しています。

基本的には、セキュリティシステムの背後にある技術を理解し、信頼できることが重要であると信じています。そのために、ユーザーと共有するために、ECCに関する優れた、比較的分かりやすい入門書を探しました。しかし、みつけることができなかったので、入門書を自分たちで作ることにしました。それが、この入門書です。

注意：これは、複雑な主題でブログ記事一つに要約することはできません。つまり、カバーすることがたくさんあるため長くなりますので、腰を据えて読んでみてください。要点だけが必要な方のために、要約は「ECCは次世代の公開鍵暗号であり、現在理解されている数学に基づいて、RSAのような第1世代の公開鍵暗号システムよりも大幅に安全な基盤を提供する」ということになります。パフォーマンスを維持しながら最高レベルのセキュリティを確保することが心配な場合は、ECCを採用することは理にかなっています。詳細に興味がある場合は以下を続けてお読みください。

公開鍵暗号の幕開け

暗号の歴史は、古典時代と近代の2つの時代に分けることができます。両者の転機は1977年にやってきました。RSAアルゴリズムとディフィー・ヘルマンキー交換アルゴリズムが導入されたときのことです。これらの新しいアルゴリズムは革新的でした。その理由は、これらのアルゴリズムが数字の理論に基づくセキュリティに関する、最初の実行可能な暗号方式を示したためです。共有秘密なしで2つの当事者間の安全な通信を可能にしたのは、はじめてのことでした。暗号は、世界中の秘密のコードブックを安全に送信していたことから、鍵交換をのぞき見る誰かを心配することなく、任意の2つの当事者間の信頼できる通信を持つことができるまでになりました。

ホイットフィールド・ディフィーとマーティン・ヘルマン

最新の暗号化は、データの暗号化に使用するキーを公開し、データの復号化に使用されるキーを非公開にできるという考えに基づいて作成されています。そのため、これらのシステムは公開鍵暗号システムとして知られています。これらのシステムの中で、最初にそして最も広く使われたきたのが、RSAと呼ばれるシステムです。RSAは、アルゴリズムを最初に公に記述した3人の男性の名前（Ron Rivest、Adi Shamir、Leonard Adleman）のイニシャルにちなんで命名されました。

公開鍵暗号システムが機能するために必要なのは、一方向に処理するのは簡単なのに、元に戻すのは難しい一連のアルゴリズムです。RSAの場合、アルゴリズムは簡単で、2つの素数を乗算します。乗算が簡単なアルゴリズムである場合、その対になる難しいアルゴリズムは乗算の積を2つの素数に素因数分解します。この特性（一方向は簡単で、もう一方は難しい）を持つアルゴリズムは、トラップドア機能として知られています。優れたトラップドア関数を見つけることは、安全な公開鍵暗号システムを作るために重要です。単純に、トラップ機能の片側から反対他方に行くまでの難易度が大きければ大きいほど、それに基づく暗号システムはより安全になります。

簡単すぎるRSAアルゴリズム

RSAアルゴリズムは、最も一般的で最もよく理解されている公開鍵暗号システムです。そのセキュリティは、因数分解は遅く、乗算は速いという事実に基づき作られています。次に、小規模なRSAシステムがどのように見えるかとその仕組みについて簡単に説明します。

一般的に、公開鍵暗号化システムには、パブリックキーとプライベートキーの 2 つのコンポーネントがあります。暗号化は、メッセージを受け取り、それに数学演算を適用してランダムに見える数を取得することによって機能します。復号化では、ランダムにみえる番号を取得し、別の操作を適用して元の番号に戻します。パブリックキーによる暗号化は、プライベートキーで復号化することによってのみ元に戻すことができます。

コンピューターはでたらめに大きい数字ではうまく機能しません。最大数値をあらかじめ決めておき、最大数値よりも小さい数値を扱うようにすることで、扱う数字が大きくなりすぎないようにすることができます。数字は、アナログ時計の数字のように扱うことができます。最大値を超える数値になる計算は、有効な範囲内の数値へとラップアラウンドされます。

RSAでは、この最大値（_max_と呼ばれます) は、2つのランダムな素数を乗算することで得られます。パブリックキーとプライベートキーは、ゼロより大きく、最大値より小さい2つの特別に選択された数字で、_pub_と_priv_と呼ばれます。数字を暗号化するには、それ自体を_pub_回乗算します。最大値になったら、ラップアラウンドしていることを確認します。メッセージを復号化するには、それ自体を_priv_回乗算すると、元の番号に戻ります。意外に思われるかもしれませんが、これが実際に機能します。発見されたとき、このプロパティは大きなブレークスルーでした。

RSAキーペアを作成するには、まず2つの素数をランダムに選んで最大値_(max)_を得ます。次に、パブリックキー_pub_の数字を選びます。2つの素数がわかっている限り、対になるプライベートキー_priv_を、このパブリックキーから計算することができます。このようにして、因数分解はRSAの解読に関わっています。最大数を素因数分解することで素数が得られ、パブリックキーから誰かのプライベートキーを計算し、その秘密メッセージを復号化することができます。

例を挙げて、これをより具体的に考えてみましょう。素数13と7を例に考えてみます。この2つを掛け合わせると、91になり、最大値が得られます。公開暗号化鍵の数字は5にしましょう。そして、7と13が91の素因数であることを知っているという事実を使って、拡張ユークリッドアルゴリズムと呼ばれるアルゴリズムを適用します。すると、プライベートキーは数字の29であることがわかります。

これらのパラメーター（max:91、pub:5、priv: 29）を使うと、完全に機能するRSAシステムを定義することができます。暗号化するには、数字を5乗し、算出された数を29乗すると元の数字を取り出すことができます。

これらの値を使って、「CLOUD」というメッセージを暗号化してみましょう。

メッセージを数学的に表現するためには、文字を数字に変える必要があります。ラテンアルファベットでよく使われる文字コードはUTF-8です。各文字が数字に対応しています。

このエンコーディングでは、CLOUDは67、76、79、85、68です。これらの数字はそれぞれ最大値「91」よりも小さいので、個別に暗号化できます。最初の文字から始めましょう。

暗号化された値を取得するには、その数字自体を5回掛け合わせる（5乗する）必要があります。

67×67 = 4489 = 30 *

*4489は最大値より大きいので、ラップアラウンドしなければなりません。ラップアラウンドは91で割った余りを使います。

4489 = 91×41 + 30

30×67 = 2010 = 8

8×67 = 536 = 81

81×67 = 5427 = 58

これは、67を暗号化すると58になることを意味します。

文字のそれぞれについてこのプロセスを繰り返すと、暗号化されたメッセージCLOUDは次のようになります。

58, 20, 53, 50, 87

このスクランブルメッセージを復号化するためには、各数字を29乗します。

58×58 = 3364 = 88 （思い出してください。数字が最大値 _max_を超える場合は、ラップアラウンドします）>

88×58 = 5104 = 8

…

9×58 = 522 = 67

出来上がり、67に戻りました。これは残りの数字でも機能し、元のメッセージになります。

まとめると、数字を選び、その数字を累乗（同じ数字を順次に掛け合わせる）することで、ランダムに見える数字を取得できます。そしてその数字を秘密の数字の回数分累乗することで、元の数字に戻ります。

完璧なトラップドアではない

RSAとディフィー・ヘルマンは、厳格なセキュリティ証明があるため非常に強力でした。著者たちは、システムに侵入することは、解読が難しいとされている数学的問題を解決することと同じくらい難しいことを証明しました。因数分解は非常によく知られている問題であり、古代から研究されています（エラトステネスのふるい)。どんな発見も大きなニュースになり、発見者は予期せぬ多額の利益を得ることになります。

"Find factors, get money" - Notorious T.K.G. (Reuters)

つまり、因数分解は、ビット対ビットベースでは最も難しい問題ではありません。Quadratic Sieve やGeneral Number Field Sieveなどの特別なアルゴリズムは、素因数分解の問題を解くためにつくられていて、ほどほどの成功を収めているといえるでしょう。これらのアルゴリズムは、既知の素数のペアを推測するという単純なアプローチよりも、高速で計算負荷も低くなります。

この手の因数分解アルゴリズムは、因数分解する数字のサイズが大きくなるにつれて、より効率的になります。大きな数を因数分解することと大きな数を掛けることの間にある難易度のギャップは、数値（つまりキーのビットの長さ）が大きくなるにつれて小さくなります。数字の復号化に使用できるリソースが増加すると、キーのサイズをそれよりも高速で大きくする必要があります。これは、計算能力が限られているモバイルおよび低消費電力デバイスにとって、持続可能な状況ではありません。因数分解と乗算のギャップは、長期的には持続可能ではないのです。

このことからわかるのは、RSAが暗号の将来にとって理想的なシステムではないということです。理想的なトラップドア関数では、簡単な方法と難しい方法が、当該の数のサイズに関して、同じ速度で難しくなります。そこで、より優れたトラップドアに基づく公開鍵システムが必要となるのです。

楕円曲線：よりよいトラップドアのための基本要素

RSAとディフィー・ヘルマンの導入後、リサーチャーは他の数学ベースの暗号ソリューションを探求し、トラップドア関数としてよく機能する因数分解を超える他のアルゴリズムを探しました。1985年、楕円曲線と呼ばれる数学の難解な分岐に基づく暗号化アルゴリズムが提案されました。

しかし、楕円曲線は一体どういうもので、トラップドア関数はどのように機能するのでしょうか？残念ながら、因数分解とは違って（中学校のはじめで全員が学習しなければなりませんでした）、ほとんどの人は楕円曲線についてよく知りません。数学はそんなに簡単ではないですし、それを説明するのも簡単ではないのですが、次のいくつかのセクションで説明してみようと思います。（退屈で、ぼーっとしてきた方は、ずっと先の「これは一体何を意味するのか」まで飛ばしてください）

楕円曲線は、特定の数式を満たす点の集合です。楕円曲線の方程式は、次のようになります。

y² = x³ + ax + b

このグラフは、Lululemonのロゴを横にしたようにもみえますね。

楕円曲線を表現する方法は他にもありますが、専門的な言葉で説明すると、楕円曲線は２つの変数をもち、片方の変数が2次、もう片方の変数が3次である方程式を満たす点の集合です。楕円曲線は単なる美しい画像ではなく、暗号化の設定に適したいくつかの特性があります。

奇妙な対称性

上で示された楕円曲線について詳しく見てみましょう。興味深い特性をいくつか持っています。

特性の1つは、水平対称であることです。曲線のどのポイントもX軸を軸として反転させることができ、同じ曲線が保たれています。より興味深い特性は、任意の非垂直の線が、最大3か所で曲線と交差することです。

この曲線を使って、ビリヤードの不思議なゲームを行うことを想定してみましょう。曲線の上で任意の2つの点を選び、その2点を通過する直線を引くと、この直線は曲線とちょうど別の1か所で交差します。このビリヤードゲームでは、あなたはＡポイントに玉を置いて、Ｂポイントに向かって玉を突きます。曲線に玉が当たると、玉の進路は曲線の反対側に向かって次のように動きます：上にはね返る（x軸よりも下の場合）、もしくは下にはね返る（x軸よりも上の場合）。

この2ポイントのビリヤードの動きを「dot」と呼びます。曲線上の任意の2ポイントを「dot」させると、新しいポイントに到達します。

A dot B = C

また、同じポイント同士で何度でも「dot」させることができます。

A dot A = B

A dot B = C

A dot C = D

...

2ポイントあって、最初のポイント同士でn回「dot」すると、最後のポイントに到達しますが、最初のポイントと最後のポイントだけがわかっている状態で「n」が何を指すのか判断することは困難です。この不思議なビリヤードの例を続けて、ある人が一人で部屋のなかでこのゲームを任意の時間行うとします。彼が上記のルールに従って、何度も玉を突くことは簡単です。誰かが後で部屋に入り、玉が最後に到達した場所を見たとき、ゲームの全ルールと玉をつき始めた場所が分かったとしても、玉が同じポイントに到達するまで再びゲーム全体をリプレイすることなく、玉が最終地点に到達するために打った回数が何回だったかを割り出すことはできません。簡単にできるが、元に戻すのは難しい。これがとても優れたトラップドア関数の基盤になるのです。

さらにオタクな話になりますが

上記の単純化された曲線は、楕円曲線の一般的な概念を実際にお見せしながら説明するのに最適ですが、暗号化に使用される曲線とは外観が異なります。

暗号化のためには、RSAで行ったように、使用できる数字の大きさの範囲を固定する必要があります。曲線上でポイントを決めるときに、どの数値も許容するのではなく、固定範囲の中で整数を使う必要があります。楕円曲線の公式（y² = x³ + ax + b）を計算する場合にも、最大値に到達したときに、数の繰り越しに使うトリックと同じものを使います。最大値に素数を選んだ場合、楕円曲線は「prime曲線」と呼ばれ、優れた暗号特性を持ちます。

下の図は、すべての数字を使った場合の数式（y² = x³ - x + 1）を曲線で表した例です。

下の図は、同じ曲線を表す数式で、整数だけを使い、最大値を97に設定した場合です。

これは普通に見るだけでは、曲線のようには見えませんが、実際は曲線です。元々の曲線がエッジで囲まれているように見えますが、曲線上でも整数を使ったものだけが色付けしてあります。この図でもまだ水平対称が保たれていることがわかります。

実は、この曲線でもまだビリヤードゲームを行って、ポイントを「dot」させることができます。曲線で表される線の計算式は、同じ属性をもっています。さらに、「dot」の演算を効率的に行うことができます。2つのポイントを結ぶ線は、ポイントに当たるまで境界でラップアラウンドする線として視覚化することができます。それは先ほど取り上げた不思議なビリヤードゲームのようです。玉がボードの端（最大値）に当たると、魔法のようにテーブルの反対側に転がり、ポイントに到達するまで転がり続けます。アステロイドというゲームにも似ています。

この新しい曲線を使うと、メッセージを曲線上のポイントとして表現することができます。メッセージをx座標として設定し、yに何が来るのかを計算して、曲線上のポイントを特定することを想像してみてください。実際はこれよりもさらに複雑ですが、考え方としてはこんな感じです。

以下のポイントがあります。

(70,6), (76,48), -, (82,6), (69,22)

*x値に65の座標はありません。これは現実世界では回避できます。

楕円曲線暗号は、素数を最大値とし、曲線方程式と曲線上のpublic pointを選ぶことによって定義することができます。プライベートキーは数字の_priv_、パブリックキーはpublic pointであらわされ、それ自体を_priv_回「dot」したものです。この種の暗号を使って、パブリックキーからプライベートキーを計算することは、楕円曲線上の離散対数関数と呼ばれます。これこそ、我々が探していたトラップドア関数であることが判明しました。

これは一体何を意味するか

楕円曲線上の離算対数は、楕円曲線暗号の基礎となる難しい問題です。約30年に渡り、研究が行われているにも関わらず、数学者はこの問題を解決する（単純なアプローチを改善する）アルゴリズムの発見には至っていません。つまり、因数分解とは違って、現在理解されている数学に基づいて考えると、トラップドア関数のギャップを狭める近道は、楕円曲線上の離算対数にはないようです。これは、同じ大きさの数の場合、楕円曲線上の離算対数を解くことは、因数分解よりもかなり難しいことを意味します。大量の計算が必要な難しい問題は、より強力な暗号化システムになるため、楕円曲線暗号は、RSAやディフィー・ヘルマンを解くよりも難しいということになります。

これらの暗号を解読するのがどれだけ難しいかを視覚化するために、Lenstraは最近、Global Securityという概念を紹介しました。「暗号アルゴリズムを解読するために、どれだけの量のエネルギーが必要かということを計算でき、そのエネルギーを使ってどれだけの水を沸騰させることができるかがわかります。これは、暗号のカーボンフットプリントのようなものです。228ビットのRSAキーを解読するのは、ティースプーン1杯の水を沸かすよりも少ないエネルギーで行うことができます。それに比べて、228ビットの楕円曲線キーは、地球にあるすべての水を沸騰させるレベルのエネルギーが必要となります。同じレベルのセキュリティをRSAを使って得ようとする場合、2,380ビットのキーが必要です。」

ECCでは、より小さなキーを使用して同じレベルのセキュリティを実現できます。特に携帯電話のようなあまり強力ではないデバイス上でますます多くの暗号化が行われるような世界では、小さなキーが重要です。2つの素数を掛け合わせることは、2つの素数を掛け合わせて得られたものから、因数分解して元の数を取り出すよりは簡単ですが、素数がとても長くなると、掛け算でさえも、電力供給量の少ないデバイスではしばらく時間がかかることがあります。キーの長さを長くすることで、RSAのセキュリティを維持し続けることは可能ですが、クライアント側で暗号化のパフォーマンスが低下することになってしまいます。ECCは、短くて速いキーを使った高いセキュリティという優れたトレードオフを提供しているようです。

楕円曲線の活用

最初はゆっくりとしたスタートでしたが、楕円曲線に基づくアルゴリズムは人気を集め、採用されるペースも加速しています。楕円曲線暗号は、現在さまざまなアプリケーションで使用されています。たとえば、米国政府は、内部通信を保護するために使用しています。Torプロジェクトは匿名性を保証するために使用しています。さらに、ビットコインの所有権を証明するためのメカニズムとして使用されています。AppleのiMessage serviceでは署名を発行します。さらに、DNSCurveでDNS情報を暗号化するために、使用されています。そして、同アルゴリズムは、SSL/TLSを介したセキュアなブラウジングのための認証方法としても適しています。Cloudflareでは楕円曲線暗号化をオンラインプライバシーに不可欠な perfect forward secrecyを提供するために使用しています。RSAやディフィー・ヘルマンなどの暗号化の第一世代は、ほとんどの領域ではまだ標準ですが、楕円曲線暗号は、はやくもオンラインプライバシーとセキュリティを保護するための、頼りになるソリューションになりつつあります。

今、ChromeやFirefoxの比較的新しいバージョンからこのブログのHTTPSバージョン（https://blog.cloudflare.com）にアクセスしている場合、ブラウザは楕円曲線暗号を使用しています。ご自分で確認することもできます。Chromeの場合、アドレスバーの鍵をクリックして、コネクションタブに進むと、安全な接続にどの暗号化アルゴリズムが使用されているのかを確認することができます。Chrome 30で鍵をクリックした場合、以下のような画像が表示されます。

ここで表示されている文字データの中で本稿と関連する部分は、ECDHE_RSAです。ECDHEは、Elliptic Curve Diffie Hellman Ephemeral（楕円曲線ディフィー・ヘルマンEphemeral）の略で（Ephemeralは「短命の」を意味し、鍵を使い捨てるの意）、楕円曲線に基づく鍵交換メカニズムのことです。このアルゴリズムはCloudflareがSSLでperfect forward secrecyを提供するのに使用しています。RSAの部分は、RSAがサーバーのIDを証明するのに使われていることを意味します。

CloudflareがRSAを使う理由は、CloudflareのSSL証明書がRSAキーペアに結びつけられているためです。最新のブラウザでは、楕円曲線に基づく証明書もサポートしています。CloudflareのSSL証明書が楕円曲線証明書の場合、ページのこの部分にECDHE_ECDSAと表示されます。サーバーのID証明は、楕円曲線デジタル署名アルゴリズムであるECDSAを使用して行われます。

CloudflareのECDHEのECC曲線（これはGoogle.comで使用されているのと同じ曲線です）：

RSAと比較すると、ECDSAのパフォーマンスの向上には目を見張るものがあります。アセンブリ最適化楕円曲線コードを持たない古いバージョンの OpenSSLでも、256ビットキーを持つECDSA署名は、2,048ビットのキーを持つRSA署名よりも20倍も高速です。

MacBook ProのOpenSSL 0.9.8では、「スピード」ベンチマークは以下を返します。

これは、RSAのECDSAの署名と比べると23倍にもなります。

Cloudflareは常にSSLパフォーマンスを向上させようとしています。ちょうど今週、CloudflareではECDHEの速度を2倍以上にするアセンブリ最適化バージョンのECCを使用し始めました。楕円曲線暗号を使用すると、サーバーとブラウザの両方のために、時間、電力、計算リソースを節約することができ、Webをより速く、より安全なものにするのに役立ちます。

欠点

楕円曲線が、そのすべてにおいて、すばらしいわけではありません。業界で広く受け入れられるようになりましたが、疑念や不確かな点がいくつか懸念されています。

最近ニュースになったのは、the Dual Elliptic Curve Deterministic Random Bit Generator（Dual_EC_DRBG）です。これは、米国国立標準技術研究所 (NIST) によって標準化され、NSAが推進した乱数ジェネレーターです。Dual_EC_DRBG は、楕円曲線の数学を使用して、ランダムにみえる数値を生成します。アルゴリズム自体は、曲線上の点を取り、楕円曲線で「dot」操作を繰り返します。公開後、バックドアが設計に組み込まれていた可能性が報告されました。つまり、リターンされる数列が、正しい秘密番号を持つ何者かによって完全に予測できる可能性があることがわかったのです。最近、RSA社は自社製品のいくつかをリコールしました。その理由は、この乱数ジェネレーターが各社のセキュリティ製品のデフォルトのPRNG として設定されていたためです。この乱数ジェネレーターがバックドアと共に書かれたかどうかは、楕円曲線技術自体の強さには影響を与えません。しかし、これは楕円曲線の標準化プロセスに疑問を投げかける問題です。すでに述べたように、私たちはシステム自体が正確に乱数を使用していることを確認することに注意を払う必要があります。今後のブログ記事では、バックドアをこのアルゴリズムの仕様にどのように組み込むことができるかについて説明します。

より懐疑的な暗号学者の中には、NIST自体とNSAによってサポートされ公開されている標準に対して、不信感をもっている学者もいます。広く実装されている楕円曲線のほとんどすべてがこのカテゴリーに分類されます。効率的な算術のために選択されたこれらの特殊曲線には既知の攻撃はありませんが、悪い曲線は存在し、後で後悔するよりも安全なものを選んでおく方が良いと考える人もいます。NIST以外でも、効率的な計算を用いた曲線の開発が進んでおり、Curve25519はダニエル・バーンスタイン (djb) によって作成されました。さらに最近では、computed curvesが、Paulo Barettoと共同研究者によって発表されていますが、これらの曲線が広く採用されるようになるのは、数年先になるでしょう。こうした従来とは異なる新しい曲線が、ブラウザによって実装されるまで、Web上の暗号送信を保護するために使用することはできません。

楕円曲線暗号に関する別の不確実性は、特許に関連しています。BlackBerryが所有する楕円曲線の特定の用途をカバーする特許が130以上あります（Certicomの2009年の買収を通じて）。これらの特許の多くは、民間組織やNSAが使用を許可しています。このため、ECCの実装がこの特許ポートフォリオを侵害することがあるかもしれないとの懸念から、一部の開発者は一時的に開発をやめています。2007年に、Certicomは楕円曲線の一部の使用をめぐって、ソニーに対して訴訟を提起しましたが、2009年にその訴訟は棄却されています。現在、楕円曲線暗号の中でも、これらの特許を侵害していないと考えられるものは多くあり、実装され、広く使用されています。

ECDSAデジタル署名をRSAと比較したときの前者の欠点は、それが大量のエントロピーを必要とすることです。適切なランダム性がなければ、プライベートキーが明らかになる可能性があります。Android上の乱数ジェネレーターの欠陥により、2013年初頭にビットコインウォレットを保護するために使用される何人かのECDSAのプライベートキーがハッカーに知られることになります。ソニーのプレイステーションが使用していたECDSAにも同様の脆弱性が見つかりました。署名を生成する機械では、質の良い乱数がたくさん必要です。Dual_EC_DRBG はお勧めしません。

将来を見据える

上記の注意事項があっても、従来のRSAよりも楕円曲線暗号の利点は広く受け入れられています。多くの専門家は、RSAとディフィー・ヘルマンで使用している数学のアルゴリズムは5年以内に破られる可能性があると憂慮しており、ECCを唯一の合理的な代替手段として残しています。

楕円曲線は、最新のブラウザすべてでサポートされており、ほとんどの証明機関は楕円曲線証明書を提供しています。Cloudflareの保護サイトのすべてのSSL接続は、最新のブラウザではデフォルトでECCに設定されます。近い将来Cloudflareでは、お客様が独自の楕円曲線証明書をアップロードできるようになる見込みです。これにより、ECCをID検証に使用し、基になるメッセージを保護し、HTTPS セッションを全面的に高速化することが可能になります。この機能が使用できるようになったときに、さらに詳しくご案内します。

Cloudflare ブログ