楕円曲線暗号を拡張しようとして

昨日、今日と台風がすごいらしいですね。

伝聞形式なのは、基本的に北陸地方ではよほどの進路でない限り台風の影響があまりないので、メディアを通した情報から判断しているからです。

それでも秋雨前線による雨はすごいので気象的に荒れているな～というのがわかります。いろいろな影響には気をつけるようにしましょう。

それはそれとして、楕円曲線暗号系のちょっとした拡張を考えようとしていた人の問題です。

wikipediaでも楕円曲線暗号の記事ではあまり詳しい情報が書いていないですし、日本語のページで楕円曲線暗号の理論が詳しく書いてあるものも多くないので探し回ってみました。

英語の会報記事であればいいのが見つかった

「Theory and Implementation of Elliptic Curve Cryptography」という文章です。Googleあたりで英語文章で検索すればPDF形式のやつがヒットすると思います。

これには楕円曲線暗号を実装するために必要な理論部分がかなり詳細に書いてあります。特に楕円曲線を絡めた暗号・署名形式であるECDH、ElGamal for EC、ECRSA、ECDSAといったアルゴリズムの計算方法が数式で示されているため、英語の文章が多少読めれば理論を知る上でものすごい参考になる資料だと思います。それ以外にも楕円曲線の基礎知識やら楕円曲線暗号の成り立ちについてなどかなりいろんな情報が詰まった文章だと思います。

勉強してみたい方はまず一読するのがいいと思います。PDFの品質自体は、おそらく紙データをスキャンしただけなのでカラーページの部分だけ恐ろしく品質が悪いですが、一度紙に印刷さえすれば普通に読めるレベルのものです。

で、やりたいことは「公開鍵暗号のうち＜秘密鍵で暗号化、公開鍵で復号＞の処理」だったのですが

それを求めて四苦八苦して文章を読んでいました。ちなみに、

ECDH	楕円曲線を使って鍵交換を行う方法
ElGamal for EC	楕円曲線を使ってElGamal暗号を成立させる方法
ECRSA	楕円曲線を使ってRSA暗号を成立させるための方法
ECDSA	楕円曲線を使ってデジタル署名を行う方法

ですね。

なお、前に楕円曲線暗号を組み込んだときに、ECDHとECDSAについては理論と実装を行っていますので難しいものではないです。ほとんど素のままの楕円曲線の計算だけでこの処理が成立できます。

今回着目したのはElGamal for ECとECRSAです。

ElGamal for ECでの計算方法

こんな感じですね。

通信を行う人物(A)および(B)は、楕円曲線E( $y^2 = x^3 + ax + b ￥quad mod ￥quad q ￥quad (order ￥quad n)$ )、合意点 $G$ が合意できているものとする。

受信者(B)は $1 ￥le k_B ￥le n - 2$ となる秘密鍵 $k_B$ を作成する。また、公開鍵として $B=k_BG$ を作成する。これにより、

送信作業

送信者(A)は送信したい文章mからこれに関連づけられる座標Mを生成する

送信者(A)は $1 ￥le k_A ￥le n - 2$ となる任意の数 $k_A$ を生成し、 $A=k_AG$ と $C=M+k_AB$ を計算する。

送信者(A)は $(A,C)$ を送信する

受信作業

受信者(B)は受信した $(A,C)$ より $M’=C-k_BA=(M+k_Ak_BG)-k_Bk_AG=M$ を計算する。

受信者(B)は座標Mより関連づけられる文章mを取得する

となります。

面倒な点は以下の二つですね。

ElGamal for ECで公開鍵暗号系としてできるのは「公開鍵で暗号化、秘密鍵で復号」の動作のみ

そもそも「送信したい文章mからこれに関連づけられる座標Mを生成する」ってどうやるの？

一応後者についてはこの文章中にやり方が書いてあります。簡単に翻訳するなら

文章mから座標Mを生成するのは些細なことではない。座標MのX座標として文章mを選択するのは不可能である。

それは、50%位の確率でX座標として文章m(この場合は文章mを整数として扱ったもの)を受け入れることができないからである。

この問題については、文章mにいくつかのビットを付け足すことにより受け入れ可能なX座標を検索することになり、それからY座標を計算することになる。

らしいです。これさえクリアできれば一応公開鍵暗号による「特定の受信者のみが受け付ける」送受信ができるわけですね。

しかし、私の狙いとは全く違うので、理解はしましたが今は無視ということで・・・。

ECRSAは「条件が特殊すぎてほとんど使えないのでは？」

というのも、確かに楕円曲線暗号の仲間であることには間違いないのですが、成立させるための条件が厳しすぎるな～と思いました。

これもどうせなので一応翻訳したやり方を書いておきます。これについては微妙に誤訳があると思いますので原文を参考にして理解してください。

通信を行う人物(A)および(B)がいるものとする。

受信者(B)は2つの異なった素数p,q(ただし、 $p ￥equiv q ￥equiv 2 ￥quad mod ￥quad 3$ )を生成し、 $n=pq$ を計算する。

また、整数 $e_B$ , $d_B$ を $e_Bd_B ￥equiv 1 ￥quad mod (p+1)(q+1)$ (本来は $lcm(p+1)(q+1)$ だが、簡単になるように)として、 $e_B$ を公開鍵、 $d_B$ を秘密鍵とする。

(正確には、公開鍵は $￥left[ n,e_B ￥right$ である)

送信処理

送信者(A)は文章mを $(m_1,m_2)$ とし、これを楕円曲線上の点Mとする。このとき、楕円曲線Eは( $y^2 = x^3 + ax + b ￥quad mod ￥quad n$ )とみなし、 $b=m_2{}^2-m_1{}^2$ とする。

送信者(A)は楕円曲線Eのパラメータaを計算する。 $(a = ￥frac{m_2{}^2-m_1{}^3-b}{m_1} ￥quad mod ￥quad n = -m_1{}^2+m_1 ￥quad mod ￥quad n)$

送信者(A)は公開鍵 $e_B$ を用いて $C=e_BM$ を計算する。

送信者(A)は $C$ を送信する。(このとき、記述されてはいないが楕円曲線のパラメータaも同時に送信する)

受信処理

受信者(B)は受信した $C(,a)$ より $M’=d_BC ￥quad mod ￥quad n = M$ を計算する。

受信者(B)は座標Mより関連づけられる文章mを取得する