はじめに
以前（といっても1年以上前ですが……）、Kotlinでも代数学という記事を書きました。
そこでは種々の代数構造をプログラミングしてきたわけですけども、ちょっと遊び足りないな〜と思っていました。そこで、なにかいい応用はないかといろいろ思案していたところ、わたしの専門分野（にとても近いところ）にあるではないですか。
ということで、こんかいは楕円曲線暗号を作ってみようと思います。
先に挙げた前シリーズではみんなだいすきKotlinを使っていましたが、ここさいきんはTypeScriptにハマっておりまして、その習作も兼ねてTypeScriptでやります。
数学的な参考文献は記事の最後にまとめてありますので、興味のあるかたはぜひ一度手にとってみてください（手軽なお値段とは言いがたいですが……）。
注意
この記事に掲載されているコードはあくまでデモです。これらのコード（片）の利用は自由に行っていただいて構いませんが、これらをそのまま製品に組み込んだり、機密情報の保護のために使ったりすることは安全上の観点から、絶対におやめくださいね。
数学的なはなし
まずは簡単に数学っぽい話からしましょう。コードだけみたいっていう方はどうぞしたーの方までスクロールしてください。
楕円曲線暗号
まず、楕円曲線暗号についてですが、ひとくちに「楕円曲線暗号」といってもいろんなものがあります。これは楕円曲線の上に構成された様々な暗号技術（暗号化・復号や署名など）をひとまとめにしてそう呼んでいるからで、そのままズバリ楕円曲線暗号という名前の暗号手法があるわけではありません。
ホントウにいろいろあるのですが、ここではもっともシンプル（と思われる）楕円ElGamal暗号というものを実装したいと思います。
すごく簡単にでも数学的な知識が必要だ、というかたは冒頭でも挙げたKotlinでも代数学シリーズ、あるいはその元記事のSwiftで代数学入門シリーズなどでおさらいしておいてください。
ElGamal暗号
さっそく楕円ElGamal……の前に、まずはベースとなっているElGamal（公開鍵）暗号を導入します。
「楕円」ElGamalというからには、とうぜん、「楕円でない」ElGamal暗号があるわけです。
（楕円でない）ElGamal暗号は以下のように構成されます。
定義: ある大きな素数\( p \)について、\( p \)を法とする乗法群\( \mathbb{Z}^{*}_{p} \)に対して、以下のアルゴリズムの組をElGamal暗号といいます。
Key Generation
受信者アリスは以下の手順で秘密鍵・公開鍵のペアを生成します。
- \( \mathbb{Z}^{*}_{p} \)の生成元\( \alpha \)をランダムに生成する。
- \( 1 \le a \le p – 2 \)なる整数\( a \)をランダムに生成し、\( \alpha ^ {a} \)を計算する。
- \( a \)を秘密鍵として秘密裏に保管し、\( \left(p, \alpha, \alpha ^ {a} \right)\)を公開鍵として公開する。
Encryption
送信者ボブは、アリスの公開鍵\( \left(p, \alpha, \alpha ^ {a} \right)\)を用いて以下の手順でメッセージを暗号化し、アリスに送信します。
- 送信するメッセージ\( m \)を\( \left[ 0, p-1\right]\)の整数で表す。
- \( 1 \le k \le p – 2 \)なる整数\( k \)をランダムに生成する。
- \( \gamma = \alpha ^ {k} \bmod p\)と\(\delta = m \cdot \left( \alpha ^ {a} \right) ^ {k} \bmod p\)をそれぞれ計算する。
- \(C = \left(\gamma, \delta\right)\)を暗号文とし、アリスに送信する。
Decryption
メッセージを受け取った受信者アリスは、受信した暗号文\(C\)と自身の秘密鍵\(a\)を用いて以下の手順でメッセージを復号します。
- 秘密鍵\( a \)を使って\(t = \gamma^{p – 1 – a} \bmod p\)を計算する。
- メッセージ\(m\)は\(m = t \cdot \delta \bmod p \)として得られる。
最後のものに関して、念のため確認しておきましょう。
\(\begin{eqnarray*}t \cdot \delta &\equiv& \gamma ^ { p – 1 -a} \cdot \delta \bmod p \\ &\equiv& \gamma ^ {p – 1} \cdot \gamma ^ {-a} \cdot \delta \bmod p \\ &\equiv& \gamma^{-a} \cdot \delta \bmod p \\ &\equiv& \alpha ^ {-ak} \cdot m \cdot \alpha ^ {ak} \bmod p \\ &\equiv& m \bmod p \end{eqnarray*}\)
となって、たしかにもともと送信されたメッセージ\( m \)が得られることがわかると思います。
楕円ElGamal暗号
さて、このElGamal暗号ですが、ここで使っていた乗法群\(\mathbb{Z} ^ {*} _ {p}\)は、任意の有限巡回群\(G\)によっても構成することができます。といっても一般の場合では暗号化して、復号できる、程度のもので、そうやって構成された系が安全かどうかは\(G\)上のDLP（離散対数問題）の困難さに帰着します。
どのような\( G \)が安全に使えるか……というのはちゃんとあるのですが、ここでは割愛することにして、ともかく、楕円曲線（上の有限群）が使えるというわけです（もちろん、楕円曲線ならばなんでもよい、というわけでもないですが）。
有限体上楕円曲線の有理点と無限遠点、そして点どうしの加算において、これらは加法群をなします。詳細についてはここでは割愛します。ゴメンナサイ！！そのうち補足の記事を書くかもしれません。
というわけで、楕円曲線上の群とその演算でもって乗法群\(\mathbb{Z} ^ {*} _ {p}\)をすげかえることで楕円ElGamal暗号を構成することができます。
定義: ある有限体\( \mathbb{F}_q \)上の楕円曲線を\(E/\mathbb{F}_q: y^2 = x^3 + ax + b\)（ただし\( q \)は素数で\(a, b \in K\)）とし、\( E/\mathbb{F}_q \)のすべての有理点がなす集合に無限遠点\( \mathcal{O} \)を加えた集合を\( E\left( \mathbb{F}_q \right)\)とします。このとき\(E\left( \mathbb{F}_q \right)\)に対して以下のアルゴリズムの組を楕円ElGamal暗号といいます。
Key Generation
受信者アリスは以下の手順で秘密鍵・公開鍵のペアを生成します。
- \( E\left(\mathbb{F}_q \right)\)の生成元\( \alpha \)をランダムに生成する。
- \( 1 \le a \le n – 1\)なる整数\( a \)をランダムに生成し、\(a \cdot \alpha \)を計算する。
- \( a \)を秘密鍵として秘密裏に保管し、\( \left( \alpha, a \cdot \alpha \right)\)を公開鍵として公開する。
Encryption
送信者ボブは、アリスの公開鍵\( \left( \alpha, a \cdot \alpha \right) \)を用いて以下の手順でメッセージを暗号化し、アリスに送信します。
- 送信するメッセージ\( m \)を\( E\left(\mathbb{F}_q\right) \)の元として表す。
- \(1 \le k \le n – 1\)なる整数\( k \)をランダムに生成する。
- \(\gamma = k \cdot \alpha\)と\(\delta = m + k \cdot \left(a \cdot \alpha \right) \)をそれぞれ計算する。
- \( C = \left(\gamma, \delta\right) \)を暗号文とし、アリスに送信する。
Decryption
メッセージを受け取った受信者アリスは、受信した暗号文\( C \)と自身の秘密鍵\( a \)を用いて以下の手順でメッセージを復号します。
- 秘密鍵\( a \)を使って\(t = \left(-a\right) \cdot \gamma\)を計算する。
- メッセージ\( m \)は\(m = t + \delta\)として得られる。
例によって確認しておきます。
\( \begin{eqnarray*}t + \delta &=& \left( -a \right) \cdot \gamma + \left(m + k \cdot \left(a \cdot \alpha \right)\right) \\ &=& \left(-ak\right) \cdot \alpha + m + \left(ak\right) \cdot \alpha \\ &=& m \end{eqnarray*} \)
ですね。
実装する
とてもつらい
で、これをTypeScriptで実装していくわけなのですが、これが元記事の元記事、swiftによるものと比べてとてもつらいものとなっております（それでもKotlinよりは楽かもしれない……）。
主なつらいところ
- interface のメソッドにデフォルト実装を持たせられないので抽象化が効きづらい。
- minus() はplus() とunaryMinus() から決まりますが、これを表現する方法がないのでけっきょく手で書かないといけません。
- operator overloadもinfix function/operatorもないのでメソッドチェーンが地獄。
- x*y+z のように書くことができずx.times(y).plus(z) のように書かなければならないので可読性は宇宙の彼方です。
- 型アサーションマシマシ
- メソッド呼び出しのたびに、もともと定義されているinterface として型推論されてしまうのでいちいち型アサーションを書いて型を明示しないといけない。
- Self 型とかないです。
- polymorphic this 型で行けそうな気はしたけどそんなことはなかったです。
- メソッドチェーン地獄と合わさると……(phi.times(phi) as T).minus(this.x).minus(other.x) as T;
- うまいやりかた知ってる方がおられたらぜひ教えてください。
- static なフィールドも持たせられない
- class のstatic なフィールドをinterface で強制できないので、identity などはインスタンスメソッドとして実装しないといけません。当然どのインスタンスから取得しても同じです……
- TypeScriptの、というかJavaScriptのnumber が浮動小数点数である
- しかもそのうちのsafeInteger なサイズが52ビットしかない
- なので今回のような素朴な実装だと気をつけないとビットサイズが全然足りず、このままでは実用は難しそう？です。
- たとえば体\( \mathbb{F}_p \)の元を32ビットにもできない（乗算で64ビット必要になります）。
- 除算で死ぬ。
- 考えなしに除算すると小数点数になって死にます。
- なので(n / m) >> 0 のようなわりと気持ちの悪いイディオムが現れます。
- しかもそのうちのsafeInteger なサイズが52ビットしかない
……となかなかなかなかですが、まぁなんとかなります（なりました）。
パラメータ
では、こんかい実装していく楕円曲線のパラメータを列挙しておきます。
- 楕円曲線 \( E / \mathbb{F}_p: y^2 = x^3 +17 \)
- つまり上で説明したパラメータを\(a = 0, b = 17\)としたものです
- \(p = 13\_040\_959\) (24ビット素数);
- ベースポイント \(g = \left(-2, 3\right) \in E / \mathbb{F}_p\)
です。このパラメータで\(g\)が生成元となるかは未確認……
今度こそ実装
上で説明したとおりに、楕円曲線上の加法群を実装していきます。
……が、Group だのField だのはここでは紙幅の都合上省略しますので、Kotlinでも代数学シリーズを参考にしてください（ご意見ご感想マサカリそのたお待ちしています）。
というわけで、もっとも大事な有限体上楕円曲線（の有理点がなす群）のクラスは以下のとおりです。
export class PointOnEllipticCurve<T extends Field> implements AdditiveGroup {
constructor(readonly x: T,
readonly y: T,
readonly curve: EllipticCurve<T>,
readonly isFinite: boolean = false) {
// 省略
}
get zero(): PointOnEllipticCurve<T> { /* ... */ }
plus(other: PointOnEllipticCurve<T>): PointOnEllipticCurve<T> { /* ... */ }
double(): PointOnEllipticCurve<T> { /* ... */ }
unaryMinus(): PointOnEllipticCurve<T> { /* ... */ }
minus(other: PointOnEllipticCurve<T>): PointOnEllipticCurve<T> { /* ... */ }
scalarMulti(d: Z|number): PointOnEllipticCurve<T> { /* ... */ }
equals(other: PointOnEllipticCurve<T>): boolean { /* ... */ }
toString(): string { /* ... */ }
}
\(E\left(\mathbb{F}_q\right)\)は加法群をなすのでAdditiveGroup を実装します。その他、継承されるメソッド・プロパティを実装してあります。具体的なコードは省略しますが……
plus() やdouble() についてはいろいろなところで加算公式、倍算公式として紹介されているので、そういうのをあたってみるのもよいかもしれません。
動作確認
さて、この楕円曲線（上の点）クラスを使って実際に暗号化・復号するのが次のコードです。
#!/usr/bin/env yarn run ts-node
import { Fp } from './fp';
import { Z } from './z';
import { EllipticCurve } from './ellipticCurve';
import { PointOnEllipticCurve } from './pointOnField';
const mod = 13_040_959;
const bitLength = mod.toString(2).length;
console.log(`bit length of ${mod} = ${bitLength}`);
const a = new Fp(0, mod);
const b = new Fp(17, mod);
console.log(`(a, b) = (${a.toString()}, ${b.toString()})`);
const x = new Fp(-2, mod);
const y = new Fp(3, mod);
console.log(`(x, y) = (${x.toString()}, ${y.toString()})`);
const curve = new EllipticCurve<Fp>(a, b);
console.log(`E/Fp: ${curve.toString()}`);
const g = new PointOnEllipticCurve<Fp>(x, y, curve);
const privateKeyReceiver = new Z(4_518_997);
const publicKeyReceiver = {
group: curve,
base_point: g,
modulo: mod,
kp: g.scalarMulti(privateKeyReceiver),
};
console.log(`base point: ${g.toString()}`);
console.log(`Kp: ${publicKeyReceiver.kp}`);
mod を型情報に含められないのが悲しい……
8行目-23行目で共有するパラメータの設定をします。これらは公開情報です。
続いて24行目で受信者の秘密鍵（これはその名の通り秘密裏に保管する）を、25行目から30行目で公開鍵を作ります。曲線のパラメータ、ベースポイントなどなども含めての公開鍵です。
出力結果は
bit length of 13040959 = 24
(a, b) = (0 mod 13040959, 17 mod 13040959)
(x, y) = (13040957 mod 13040959, 3 mod 13040959)
E/Fp: y^3 = x^3 +17 mod 13040959
base point: (13040957 mod 13040959, 3 mod 13040959) y^3 = x^3 +17 mod 13040959
Kp: (3574499 mod 13040959, 12409557 mod 13040959) y^3 = x^3 +17 mod 13040959です。
では、いよいよ暗号化しましょう！
const r = new Z(Math.floor(Math.random() * mod));
console.log(`random number: ${r}`);
const message = new PointOnEllipticCurve<Fp>(
new Fp(1_366_161, mod), new Fp(562_609, mod), curve);
console.log(`message text = ${message.toString()}`);
const c = [
publicKeyReceiver.base_point.scalarMulti(r),
message.plus(publicKeyReceiver.kp.scalarMulti(r)),
];
console.log(`encrypted text = ${c[0].toString()}, ${c[1].toString()}`);
上で説明したとおりですが……
暗号化すべき平文は楕円曲線上の点です。ここではm = (1_366_161, 562_609) です。
受信者の公開鍵のベースポイントに適当な乱数r を乗算し（8行目）、
受信者の公開鍵のkp にこれまた適当な乱数r （↑と同じもの）を乗算したものと平文を加算します（9行目）。
この2つの値（やっぱりこれらも点です）の組が暗号文となります。
さて、この暗号文を受信したとき、正しく復号できるかどうか、試してみましょう。
const decrypted = c[1].minus(c[0].scalarMulti(privateKeyReceiver));
console.log(`decrypted text = ${decrypted.toString()}`);
console.log(`m == Dec(Enc(m))? : ${decrypted.equals(message)}`);復号するには、暗号文の2つめの点から、1つめの点に秘密鍵を乗算したものを引くことで得られます。
random number: 6978818
message text = (1366161 mod 13040959, 562609 mod 13040959) y^3 = x^3 +17 mod 13040959
encrypted text = (5488406 mod 13040959, 9147684 mod 13040959) y^3 = x^3 +17 mod 13040959, (2644073 mod 13040959, 786394 mod 13040959) y^3 = x^3+17 mod 13040959
decrypted text = (1366161 mod 13040959, 562609 mod 13040959) y^3 = x^3 +17 mod 13040959
m == Dec(Enc(m))? : true確かにちゃんと復号できていますね！
おわりに
いかがだったでしょうか。速度、メッセージ空間、暗号文空間どれをとっても実用とは程遠いですが、なんとな〜く楕円曲線暗号というものがわかりましたか？
みなさんも代数構造をプログラミングしていろいろ応用してみてはいかがでしょうか。
ではまた。
参考文献
[1] HANDBOOK of APPLIED CRYPTOGRAPHY, Alfred J. Menezes, et al., 1996, ISBN: 978-0-8493-8523-0
[2] 代数学から学ぶ暗号理論, 宮地充子, 2012, ISBN: 978-4-535-78679-0
[3] 情報セキュリティ, 宮地充子, 菊池浩明, 2006, ISBN: 4-274-13284-6