(EC)Elgamal暗号の数的構造

# はじめに
以前、[電子署名DSA/ECDSAの数的構造](/angel_p_57/items/f2350f2ba729dc2c1d2e)という記事を書きましたが、同じ**離散対数問題**をベースにした、Elgamal暗号についても軽く調べなおしたので、記事にすることにしました。

前回のサンプルコードに付け足す形で、暗号処理のデモも実装しています。

# 事前知識
同じ離散対数問題ベースの話なので、上の記事の大部分で説明がかぶります。具体的には、以下の部分は事前知識として把握しておくか、あるいは必要に応じて参照してください。

* [事前知識](/angel_p_57/items/f2350f2ba729dc2c1d2e#事前知識)  
  主に mod n の世界の話についてです
* [有限群とべき乗](/angel_p_57/items/f2350f2ba729dc2c1d2e#有限群とべき乗), [べき乗の性質](/angel_p_57/items/f2350f2ba729dc2c1d2e#べき乗の性質), [離散対数問題](/angel_p_57/items/f2350f2ba729dc2c1d2e#離散対数問題)  
  離散対数問題の概要です
* [有限群での演算の内容](/angel_p_57/items/f2350f2ba729dc2c1d2e#有限群での演算の内容)  
  楕円曲線も含め、群の演算の実際の内容についてです

あ。以降、説明の中で**群の要素を区別するために**ギリシア文字を使いますが、読み方が分からなくてイメージし辛いという人も出るかもしれません。(昔の自分がそうでした)
一応、使う文字の読み方を挙げておきます。

* $\gamma$ … ガンマ (べき乗のベースとなる要素に使ってます)
* $\epsilon$ … イプシロン (群の演算の単位元です)
* $\zeta$ … ゼータ (暗号文を表す要素に使ってます)
* $\kappa$ … カッパ (秘密情報を表す要素に使ってます)
* $\mu$ … ミュー (メッセージに対応する要素に使ってます)
* $\chi$ … カイ (公開鍵を表す要素に使ってます)

# Elgamal暗号とは
## 概要
さてでは本題ですが、先にElgamal暗号についてです。

これは、1984年にElgamal氏が発表した**(狭義)公開鍵暗号**の1種です。つまり、**暗号化と復号**の機能を持ちます。
※公開鍵暗号の分類については、[2つの公開鍵暗号(公開鍵暗号の基礎知識)](/angel_p_57/items/897bf94160be8d637585#分類)をご覧ください。

なお、同時にElgamal署名という電子署名も(同じ論文で)発表しており、**以前の記事で紹介したDSAはこのElgamal署名の改良版**という位置づけになります。

Elgamal暗号、Elgamal署名とも離散対数問題をベースにした方式ですが、処理内容が共通化されているRSA暗号、RSA署名と違って、計算している内容は同じではありません。

なお、オリジナルのElgamal暗号は、mod p上のべき乗(乗法群)を利用した方式ですが、これは一般の有限群にも(条件付きで)応用可能であり、楕円曲線を使えばEC-Elgamalとなります。
※とはいえ、実際に活用されている事例は、私は知らないのですが

## 理論
### 身も蓋もない説明
さて、それではElgamal暗号の理論的な裏付けですが、これは**DHの鍵交換**( 事前知識で挙げた[べき乗の性質](/angel_p_57/items/f2350f2ba729dc2c1d2e#べき乗の性質)にもあります )を応用したものになっています。

DHの鍵交換とは、

* 群$(G,\circ,\epsilon)$と、その要素$\gamma$があるとき、
* 2者が秘密鍵・公開鍵のペア、$(x_1,\chi_1=\gamma^{x_1}),~(x_2,\chi_2=\gamma^{x_2})$ を作成し、
* 両者で公開鍵 $\chi_1,\chi_2$ を交換し、$\chi_2^{x_1},~\chi_1^{x_2}$ を計算することで、
* 秘密情報 $\kappa=\chi_2^{x_1}=\chi_1^{x_2}=\gamma^{x_1\times x_2}$ が共有できる

という方式でした。

であれば、この共有した秘密情報$\kappa$を使って、**当事者しか行えない変換・逆変換を行えば暗号になるだろう**というのが基本アイデアです。

つまりこういうことです。

* 暗号化  
  メッセージに対応した$G$の要素 $\mu$ に対し、$\zeta=\mu\circ\kappa$ を暗号文とする
* 復号  
  暗号文 $\zeta$ に対し、$\mu'=\zeta\circ\kappa^{-1}$を計算する  
  $\mu'=\zeta\circ\kappa^{-1}=\mu\circ\kappa\circ\kappa^{-1}=\mu\circ(\kappa\circ\kappa^{-1})=\mu\circ\epsilon=\mu$ であるため、確かに元のメッセージに対応する要素が得られる

なお、ここで$\kappa^{-1}$と出てきたのは、群の演算$\circ$に関する逆元です。
つまり$\kappa\circ\kappa^{-1}=\kappa^{-1}\circ\kappa=\epsilon$となるもの ( $\epsilon$は単位元であることに注意 ) です。
(EC)DSAの話では使わないため触れませんでしたが、**群はこのような逆元が存在するという性質も持っています**。
 
…え? それだけかって? **鍵交換で得られた鍵で共通鍵暗号の処理するの**とどう違うの、と?
…いやあの…。まあその…ええと。

### 取り繕った説明
先ほどの説明だと、**単なる鍵交換にしか見えない**ので、ちょっと説明をやり直します。

* 鍵ペア生成
  * 暗号を受け取る側が、鍵ペア$(x,\chi=\gamma^x)$を作成し、$\chi$ を公開鍵として公開します。$x$ は秘密鍵です。
* 暗号化
  * 暗号を送る側が、**秘密の乱数** $r$ を用意します。
  * 暗号文の半分として $\zeta_1=\gamma^r$ を計算します。
  * メッセージに対応した $G$ の要素 $\mu$ に対し、公開鍵も用いて暗号文のもう半分 $\zeta_2=\mu\circ\chi^r$ を計算します
  * $(\zeta_1,\zeta_2)$ を暗号文として送信します
* 復号
  * 秘密鍵を用いて $\mu'=\zeta_2\circ(\zeta_1^x)^{-1}$ を計算します
  * $\mu'=\mu$ となるため、元のメッセージに対応する要素が得られています
  * これは、次の計算で確かめることができます  
    $\mu'=\mu\circ\chi^r \circ(\zeta_1^x)^{-1}=\mu\circ(\gamma^x)^r\circ((\gamma^r)^x)^{-1}=\mu\circ\gamma^{r\times x}\circ(\gamma^{r\times x})^{-1}=\mu\circ\epsilon=\mu$

**ほら、なんか乱択な暗号っぽい説明になった。**

### 残りの重要な補足
さて、これまでに説明してないけれど、結構重要な点が残っているので補足します。

* $\gamma$の要件  
  [電子署名DSA/ECDSAの数的構造](/angel_p_57/items/f2350f2ba729dc2c1d2e)で説明したときは、十分大きな素数 $q$ に対して$\gamma^q=\epsilon$という要件でした。  
  しかし、(EC)Elgamalでは、**$\gamma$ は「原始元」**ということになっています。  
  これは、$\gamma^0(=\epsilon), \gamma^1(=\gamma), \gamma^2, \gamma^3, \cdots$ で、$G$ の全ての要素を表すことができるという要件です。このとき、$G$ の全要素数 $n$ に対してはじめて、$\gamma^n=\epsilon$ となります。  
  とはいえ、別に原始元でなくても、$\gamma^q=\epsilon$ な $\gamma$ であっても(暗号としての強度も含め)本質的に大きく変わることはありません。ただ、$x, r$ に使える値が $q$ までか $n$ までなのか、という違いはあります。
* メッセージに対応した要素  
  Elgamalでは、暗号化のメインの演算の対象は、メッセージそのものではなく$G$の要素$\mu$です。  
  つまり、メッセージ・要素間の変換・逆変換 $\mu=f_t(m),~m=f_t^{-1}(\mu)$ が必要になるということです。  
  いや、**ある要素が$\gamma$の何乗か(離散対数)を求めるのが困難なのに、そんな都合のいい変換・逆変換あるの?**というのは気になるところですが、オリジナルのElgamalでは非常に都合のいい ( 変換に見えない ) 変換があります。ECElgamalの場合も決まったやり方があるわけではありませんが、一応やりようはあります。  
  ※この点はサンプルコードでの実装例で説明します

# サンプルコード
## 概要
サンプルコードは、[電子署名DSA/ECDSAの数的構造(2/2)](/angel_p_57/items/355eec5b5547ac122607#_reference-e58908695fdb38c3ee87)の時の、以下のソースツリーに追加する形で作りました。
https://github.com/angel-p57/qiita-sample/tree/master/dsa

今回関係するファイルは次の通りです。

* base.rb
  基本部分のライブラリの流用です。今回ECElgamalでのメッセージ⇔要素変換のために、mod pでの平方根sqrtを追加しています。
* fg_m.rb, fg_ec.rb  
  DSAの時の有限群の実装の流用で、前者が mod p での乗算の群用、後者が$GF(p)$での楕円曲線用です。  
  Elgamalの処理のため、それぞれ群の逆演算invを追加しています。
* elgamal.rb  
  Elgamal暗号の実装です。
* test_elgamal_m.rb, test_elgamal_ec.rb  
  対応する有限群を使ったElgamal暗号のデモです。

## ElgamalEncryptionEngineクラス
では、まず[elgamal.rb](https://github.com/angel-p57/qiita-sample/blob/master/dsa/elgamal.rb)で実装した、Elgamal暗号の処理を行うElgamalEncryptionEngineクラスです。

### コンストラクタinitialize
DSAの時と同様、各処理を行うためのオブジェクトを生成します。
違いとしては、パラメータが $\gamma,n,f_t,f_t^{-1}$ となっていることです。
$n$ は $\gamma^n=\epsilon$ となる指数ということで、DSAの時の $q$ と同様ですが、素数かどうかまではチェックしません。
※オリジナルの方式では $n$ は群の要素数になるべきですが、ここではそこまで厳密にはやっていません。

$f_t,f_t^{-1}$ は、メッセージと群の要素の変換・逆変換を行うための関数 ( ラムダ ) です。

### 鍵ペア生成 create_key_pair
これはDSAの時と同様、単純に乱数として秘密鍵 `x` を生成し、計算した公開鍵 `chi` ( $\chi=\gamma^x$ ) とのペアを返す実装です。
ちなみにこの機能は、暗号化の時にも ( 鍵交換用の鍵ペアに相当するデータの生成のため ) 使用します。

### 暗号化 encrypt
メッセージ `msg` と、前項で生成した公開鍵 `chi`を用いて署名を生成する処理です。

身も蓋もないですが、乱数$r$および、そこから導出される$\zeta_1=\gamma^r$ は、もう1つの鍵ペア生成として計算しています。
後は、$f_t$ によってメッセージ `msg` を変換した `mu` ( $\mu$ ) に、DH鍵交換による秘密情報 `kappa` ( $\kappa=\chi^r$ ) を作用させるだけです。

```ruby:encrypt実装抜粋
    def encrypt(msg,chi,rval=nil)
      mu = @ft[msg]

      r,zeta1 = create_key_pair(rval)
      kappa = chi**r

      zeta2 = mu*kappa

      [zeta1,zeta2]
end
```

### 復号 decrypt
暗号文`[zeta1,zeta2]` ( $(\zeta_1,\zeta_2)$ ) と、秘密鍵 `x` をもとに復号します。
`zeta1` は、鍵交換用の公開鍵に相当するわけなので、`kappa` ( $\kappa=\zeta_1^x$ ) を復号側でも計算してあげて、`zeta2` に逆演算してあげれば、メッセージに対応する要素 `mu` が得られます。( $\mu=\zeta_2\circ\kappa^{-1}$ )

最後に逆変換 $f_t^{-1}$ をかければ元のメッセージが得られる、ということです。

```ruby:decrypt実装抜粋
    def decrypt(zeta1,zeta2,x)
      kappa = zeta1**x

      kinv = kappa.inv
      mu = zeta2*kinv

      msg = @ftinv[mu]
    end
```

## デモ実行
続いて、`elgamal.rb`を組み込んだ簡単なデモです。

### 素のElgamalのデモ
ファイルとしては[`test_elgamal_m.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/test_elgamal_m.rb)が該当します。

群のパラメータは、前回のDSAの時と同様、$\gamma=2937, n=679733~( \gamma^n=1~mod~464937373 )$ です。
※q が n と名前を変えただけです。

さて、説明を保留していた、メッセージ⇔群の要素間の変換関数 $f_t, f_t^{-1}$ ですが、これは単に $1\sim p-1$ の数値をメッセージとみなし、それをそのまま群の要素にするだけです。ぶっちゃけ何か計算をするわけではありません。
※だから、あえて「変換」と言わないと、変換関数のことを意識できないかもしれません。

```ruby:test_dsa_m.rb抜粋
# Elgamal parameters
p_=464937373
n=679733
FG_M=MyExample::FiniteGroup::Multiplicative.generate(p_)

myelgamal=MyExample::ElgamalEncryptionEngine.new(
  FG_M.new(2937),
  n,
  ->msg{
    raise "msg #{msg} is not in range 1..#{p_-1}" unless (1...p_)===msg
    FG_M.new(msg)
  },
  ->mu{
    mu.to_i
  }
)
```

以下、コードの内容は特に示しませんが、鍵とメッセージを生成して暗号化・復号を試し、元のメッセージに戻ることを試した例です。

```text:test_elgamal_m.rb実行結果
$ ruby test_elgamal_m.rb
  ** debug: initialize
    Elgamal Encryption engine initialized with;
    gamma=2937, n=679733

  ** debug: create_key_pair
    created private key x: 539294,
            public key chi=gamma**x: 99209203

  ** debug: encrypt
    translate msg = 136113 to mu = 136113,
    created random number (private key) r = 210686,
    generated cipher #1 (public key) zeta1 = 88674550,
    using DH shared value kappa = 134912847,
    generated cipher #2 (main value) zeta2 = 225859703

encrypted the message 136113 to ( 88674550,225859703 )

  ** debug: decrypt
    cipher 1 / DH public key zeta1 = 88674550,
    cipher 2 / main value zeta2 = 225859703,
    DH shared value kappa = 134912847, and its inverse value = 105540414,
    inverse to mu = 136113,
    translate inverse to decrypted message = 136113

decrypted the cipher data to 136113, and succeeded in restoring the original message.
```

### ECElgamalのデモ
ファイルとしては[`test_elgamal_ec.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/test_elgamal_ec.rb)が該当します。

ECDSAの時と同様、素のElgamalのデモを楕円曲線ベースのものに変えています。
パラメータもECDSAの時と同様、以下を利用しています。

* 楕円曲線: $y^2\equiv x^3+54079150x+64993959~mod~89334649$
* 基準点 ( ベースカーブ ): $\gamma=(81994458,7695874)~~(\gamma^{1624057}=\epsilon)$  
  ※$\epsilon$は楕円曲線における無限遠点

肝心の、メッセージ⇔群の要素の変換についてですが、流石に群の要素を簡単に作ることはできないので、**楕円曲線上の点のx座標を指定して方程式を解いてy座標を求める**ということをしています。
この時、mod p での平方根、sqrt を計算するわけですが、必ず平方根が存在するわけではない ( というか、半分くらいは計算できない ) ので、**一定の幅の範囲で x座標の候補を定め、平方根が計算できるものを順番に探す**ようにしています。
今回は幅16としていて、なので例えばメッセージが100なら、x座標 1600～1615の範囲で探す感じになります。
なお、逆変換は単にx座標を取ってきて、その「幅」で割るだけなので単純です。

```ruby:test_elgamal_ec.rbより抜粋
# Elgamal parameters
p_,a,b=89334649,54079150, 64993959
n=1624057
GF=MyExample::GaloisField.generate(p_)
EC=MyExample::FiniteGroup::EllipticCurve.generate(GF,a,b)
search_width=16

myelgamal=MyExample::ElgamalEncryptionEngine.new(
  EC.element(81994458,7695874),
  n,
  ->msg{
    raise "msg #{msg} is not in range 0..#{p_/search_width-1}" unless (0...p_/search_width)===msg
    search_width.times{|i|
      x=GF.new(msg*search_width+i)
      y=(x*x*x+x*a+b).sqrt and return EC.element(x,y)
    }
    raise "failed to search an element on EC for #{msg}"
  },
  ->mu{
    mu.x.to_i/search_width
  }
)
```

ところで、mod p での sqrt については、
[よしいずの雑記帳-奇素数を法とする平方根を計算するCプログラムの例](http://yoshiiz.blog129.fc2.com/blog-entry-415.html)にある、M.Cipollaのアルゴリズムを参考にさせてもらいました。
実装の詳細に興味があれば、[base.rb](https://github.com/angel-p57/qiita-sample/blob/master/dsa/base.rb)の中をご覧ください。

では以下実行結果例です。やっていることは素のElgamalの時と同じです。

```text:test_elgamal_ec.rb実行結果
$ ruby test_elgamal_ec.rb
  ** debug: initialize
    Elgamal Encryption engine initialized with;
    gamma=(81994458,7695874), n=1624057

  ** debug: create_key_pair
    created private key x: 636197,
            public key chi=gamma**x: (4425197,80197370)

  ** debug: encrypt
    translate msg = 3628805 to mu = (58060880,72462770),
    created random number (private key) r = 1588174,
    generated cipher #1 (public key) zeta1 = (49144368,9527163),
    using DH shared value kappa = (15272535,85899800),
    generated cipher #2 (main value) zeta2 = (54046410,72983264)

encrypted the message 3628805 to ( (49144368,9527163),(54046410,72983264) )

  ** debug: decrypt
    cipher 1 / DH public key zeta1 = (49144368,9527163),
    cipher 2 / main value zeta2 = (54046410,72983264),
    DH shared value kappa = (15272535,85899800), and its inverse value = (15272535,3434849),
    inverse to mu = (58060880,72462770),
    translate inverse to decrypted message = 3628805

decrypted the cipher data to 3628805, and succeeded in restoring the original message.
```

# 終わりに
ということで、Elgamal暗号でした。**DHの鍵交換でええやん**と思わなくもないですが、仕組み的に分かり易いので、公開鍵暗号のデモ的にはやりやすいかな、という感じです。