コーディング初心者が楕円曲線暗号をPythonで実装した話

1 何か作りたい

大学に入ってから結構経ったけれども、なにかアプリを作るわけでもなく、なにかイベントに参加するわけもなく、時間が過ぎていた。なんとなく数学が好きなので、数学を交えたプログラミングができないか考えた結果、暗号をライブラリ使わず計算のみで実装できないかということを思い立った。そこで今回注目したのが楕円曲線暗号だ。

※今回は数学的な証明には深入りせず、楕円曲線暗号の基本的な仕組みとPythonによる実装を中心に書いた。

2 楕円曲線暗号とは?

私の調べによると、RSA暗号と同じ公開鍵暗号に分類され、楕円曲線という曲線を利用した暗号である。楕円曲線は以下の式によってあらわされるものだそう。
$y^2 = x^3 + Ax + B\ (A,Bは任意の定数)$
たとえば$A=-3,B=10$のとき、以下のような概形になる。

ここで、$A,B$ は定数であり、曲線が特異点を持たないために、次の条件を満たすものとする。

$$
4A^3+27B^2\neq 0
$$

暗号化を行うときは法を$p$とする有限体上で行われるため、上記の条件式が法$p$で成り立ってなければならない。

2.1 有限体とは

ChatGPTにきいたところ「限られた種類の数字だけで、四則演算ができる世界」とのこと。これをどう、楕円曲線に組み込むかというと、例えば、$p$を素数として、有限体$\mathbb F_p$上の楕円曲線の傾きを
$m = \left(y_2 - y_1\right)\left(x_2 - x_1\right)^{-1}\ \left(mod \ p\right)$
と計算する。ここで有限体$\mathbb F_p$上では割り算を乗法逆元というものを使って表す。例えば、有限体 $\mathbb F_p$ 上では、3で割る操作は、3を掛けると法 $p$ で1になる数を掛ける操作に置き換えられる。このような数を3の乗法逆元という

2.2 楕円曲線における"足し算"

楕円曲線上の点には、通常の座標の足し算とは異なる特別な点の加算が定義される。
楕円曲線上の2点を

$$
P=(x_1,y_1),\quad Q=(x_2,y_2)
$$

とする。

このとき、点の和 $R=P+Q$ を以下のように定義する。

2.3 異なる2点の加算

$x_1\neq x_2$ の場合、2点を結ぶ直線の傾き $\lambda$ は、

$$
\lambda=\frac{y_2-y_1}{x_2-x_1}
$$

となる。ここで有限体$\mathbb{F}_p$上においては割り算を乗法逆元を用いた掛け算として計算する。

点の和 $R=(x_3,y_3)$ は次の式で定義される。

$$
\boxed{
\begin{aligned}
x_3=\lambda^2-x_1-x_2,\ \ \ y_3=\lambda(x_1-x_3)-y_1
\end{aligned}
}
$$

幾何学的には、次の手順で求められる。

1. 点 $P,Q$ を通る直線を引く。
2. その直線と楕円曲線の3つ目の交点を求める。
3. その交点を $x$ 軸について反転させる。
4. 得られた点を $P+Q$ とする。

ただし、2点のx座標が等しく、y座標が互いに加法逆元の関係にある場合、2点を結ぶ直線は垂直になる。

このとき、傾き$\lambda$は定義できないため、点の和を無限遠点$O$とする。

有限体$\mathbb{F}_p$上では、

$$
x_1=x_2,\qquad y_1+y_2\equiv0\pmod p
$$

を満たす場合、

$$
\boxed{P+Q=O}
$$

となる。

なお、この処理は後述する無限遠点と逆元の性質に対応している。

2.4 同じ点の加算（Point Doubling）

$P=Q$ の場合、2点を通る直線の代わりに、点 $P$ における接線を使用する。接線の傾きは、陰関数微分から、

$$
2y\frac{dy}{dx}=3x^2+A
$$
より、
$$
\boxed{\lambda=\frac{3x_1^2+A}{2y_1}}
$$
となる。
したがって、

$$
\begin{aligned}
x_3&=\lambda^2-2x_1\
y_3&=\lambda(x_1-x_3)-y_1
\end{aligned}
$$

で $2P$ を計算できる。

ただし、$y_1=0$ の場合は $2P=O$ となる。

2.5 無限遠点と逆元

楕円曲線では、特別な点として無限遠点 $O$ を導入する。

無限遠点は通常の足し算における $0$ に相当し、

$$
P+O=O+P=P
$$

が成立する。

また、点 $P=(x,y)$ の逆元を

$$
-P=(x,-y)
$$

と定義する。

これにより、

$$
P+(-P)=O
$$

となる。

つまり、$x$ 座標が等しく、$y$ 座標が反対の2点を加算すると無限遠点になる。

2.6 スカラー倍（Scalar Multiplication）

楕円曲線上の点 $P$ に対して、正の整数 $k$ によるスカラー倍を次のように定義する。

$$
\boxed{kP=\underbrace{P+P+\cdots+P}_{k\text{ 個}}}
$$

さらに、

$$
0P=O,\qquad (-k)P=-(kP)
$$

と定義することで、整数全体に拡張できる。

2.7 より早くスカラー倍するために

スカラー倍を単純に計算すると、多数の点の加算が必要になる。

そこで、整数を2進数に分解し、点の2倍算と加算を組み合わせて計算する。

例えば、

$$
13=8+4+1
$$

より、

$$
13P=8P+4P+P
$$

と計算できる。

この方法を Double-and-Add法 と呼び、計算量を $O(k)$ から $O(\log k)$ に削減できる。

なお、今回の実装では有限体 $\mathbb F_p$ 上で計算を行うため、点の座標や点の加算における演算は法 $p$ で行う。ただし、スカラー倍の整数 $k$ については、点の位数を $n$ とすると、$kP=(k\bmod n)P $が成立する。

3 楕円曲線暗号との関係

楕円曲線暗号では、スカラー倍が重要な役割を果たす。

あらかじめ決められた基準点 $G$ に対して、秘密鍵を整数 $d$ とすると、公開鍵 $Q$ は、

$$
\boxed{Q=dG}
$$

によって生成される。

• 秘密鍵：整数 $d$
• 公開鍵：楕円曲線上の点 $Q$
• 基準点：楕円曲線上の点 $G$

$d$ と $G$ が分かっていれば、$Q=dG$ は効率的に計算できる。

しかし、$G,Q$ のみから $d$ を求める問題は、適切なパラメータを用いた場合、計算上非常に困難である。

この問題を**楕円曲線離散対数問題（ECDLP）**と呼ぶ。

この計算の非対称性が、楕円曲線暗号の安全性を支えている。

4 EC-ElGamal暗号の仕組み

今回は、楕円曲線を利用した公開鍵暗号の一つである EC-ElGamal暗号 を実装する。

EC-ElGamal暗号では、楕円曲線上の点の加算とスカラー倍を利用して、暗号化と復号を行う。

4.1 鍵の生成

まず、暗号化に必要な鍵を生成する。

あらかじめ楕円曲線上の基準点 $G$ を決め、秘密鍵となる整数 $d$ を選ぶ。

このとき、公開鍵 $Q$ は次の式によって求められる。

$$
\boxed{Q=dG}
$$

ここで、$d$ は秘密にするが、$G$ と $Q$ は公開してよい。

4.2 暗号化

暗号化する平文を楕円曲線上の点 $M$ とする。

暗号化には、受信者の公開鍵 $Q$ と、その暗号化のために新しく選んだ乱数 $k$ を使用する。

まず、次の2つの点を計算する。

$$
\boxed{
\begin{aligned}
C_1 &= kG\
C_2 &= M+kQ
\end{aligned}
}
$$

このとき、暗号文は

$$
\boxed{C=(C_1,C_2)}
$$

となる。

つまり、平文 $M$ に対して、乱数 $k$ と公開鍵 $Q$ から計算した点 $kQ$ を加えることで暗号化している。

4.3 復号

復号では、暗号文 $(C_1,C_2)$ と秘密鍵 $d$ を使用する。

まず、秘密鍵 $d$ と暗号文の一部である $C_1$ を用いて、次の点を計算する。

$$
S=dC_1
$$

そして、$C_2$ から $S$ を引くことで元の平文を復元する。

$$
\boxed{M=C_2-dC_1}
$$

実際に、暗号化の式を代入すると、

\begin{align}
C_2-dC_1
&=(M+kQ)-d(kG)\\
&=M+k(dG)-dkG\\
&=M+dkG-dkG\\
&=M
\end{align}

となる。

このように、暗号化の際に加えた点 $kQ$ と、復号時に計算した点 $dC_1$ が等しいため、元の平文を取り出すことができる。

なお、ここでいう点の引き算は、前述した逆元を使って

$$
P-Q=P+(-Q)
$$

と計算する。

4.4 今回の実装について

今回のプログラムでは、平文を文字列ではなく、楕円曲線上の点 $M=(3,33)$ として扱う。

また、秘密鍵を $d=114$、暗号化に用いる整数を $k=60$ として、暗号化と復号が正しく行われるかを確認する。

ただし、今回は計算の仕組みを理解するために小さな有限体と固定値を使用している。実際の暗号化では、十分に安全なパラメータを選び、暗号化ごとに適切な乱数 $k$ を生成する必要がある。

以上の仕組みをPythonで実装していく。

5 Pythonで実装してみた

ここからは、これまでに説明した楕円曲線上の計算とEC-ElGamal暗号をPythonで実装していく。

今回は暗号ライブラリを使用せず、Pythonの基本的な演算機能だけを用いて実装した。

また、処理を分かりやすくするため、プログラムを次の4つのファイルに分割した。

ファイル名	役割
ecc_cal.py	楕円曲線上の点の計算
gen_key.py	公開鍵の生成
EC_ElGamal.py	暗号化と復号
main.py	各処理の実行

5.1 楕円曲線上の計算（ecc_cal.py）

まず、楕円曲線上の点の加算やスカラー倍を計算するために、ECCクラスを作成した。

このクラスでは、主に次の3つのメソッドを定義した。

• add(p,q)：楕円曲線上の2点を加算する。
• negate(point)：点の逆元を求める。
• scalar_mul(k,point)：点を整数倍する。

点の加算では、2点が異なる場合と同じ場合で傾きの計算方法が変わるため、条件分岐を行っている。

また、有限体上での割り算には、Pythonのpow(den,-1,self.P)を使用した。これはdenの法self.Pにおける乗法逆元を求めるものである。

スカラー倍には、前述したDouble-and-Add法を採用した。

ここでは、整数kを2進数として扱い、最下位ビットが1である場合に点を加算する。さらに、点を2倍しながらkを右に1ビットずつシフトすることで、効率的に計算できるようにしている。

なお、無限遠点はPythonのNoneで表現した。
以下では

O=None

と定義している。

点の和を再現する関数

ecc_cal.py

    def add(self,p,q):
        if p == O :
            return q
        elif q == O :
            return p
        x1,y1 = p
        x2,y2 = q
        if x1 == x2 and (y1 + y2)%self.P == 0 :
            return O
        
        if x1 != x2 :
            num ,den= (y2-y1) , (x2-x1)
        elif p == q :
            num ,den= (3*x1**2+self.A),(2*y1)
        m = (num*pow(den,-1,self.P))%self.P
        x3 = (m**2-x1-x2)%self.P
        y3 = (m*(x1-x3)-y1)%self.P
        P_new = (x3,y3)
        return P_new

点の逆元を求める関数

ecc_cal.py

    def negate(self, point):
        if point is None:
            return None

        x, y = point
        return (x, (-y) % self.P)

Double-and-add法を用いたスカラー倍する関数

ecc_cal.py

    def scalar_mul(self, k, point):
        if k < 0:
            return self.scalar_mul(-k, self.negate(point))
        result = None
        addend = point
        while k > 0:
            if k & 1:
                result = self.add(result, addend)
            addend = self.add(addend, addend)
            k >>= 1
        return result

5.2 公開鍵の生成（gen_key.py）

次に、秘密鍵から公開鍵を生成するGenKeyクラスを作成した。

公開鍵は、秘密鍵dと基準点Gから、

$$
Q=dG
$$

によって生成される。

今回の実装では、先ほど作成したscalar_mul()を呼び出すことで公開鍵を求めている。

5.3 暗号化と復号（EC_ElGamal.py）

EC_ElGamal.py

class EC_ElGamal:
    def __init__ (self,M,public_key,private_key,k,ecc):
        self.M = M
        self.public_key = public_key
        self.private_key = private_key
        self.k = k
        self.ecc = ecc
    
    def encryption(self):
        C1 = self.ecc.scalar_mul(self.k,self.ecc.G)
        C2 = self.ecc.add(self.M,self.ecc.scalar_mul(self.k,self.public_key))
        return C1,C2

    def decryption(self,C1,C2):
        shared = self.ecc.scalar_mul(self.private_key,C1)
        dec_M = self.ecc.add(C2,self.ecc.negate(shared))
        return dec_M

続いて、EC-ElGamal暗号による暗号化と復号を実装した。

EC_ElGamalクラスには、次の2つのメソッドを定義した。

• encryption()：公開鍵と整数kを用いて暗号文を生成する。
• decryption(C1,C2)：秘密鍵を用いて元の平文を復元する。

暗号化では、

$$
C_1=kG,\quad C_2=M+kQ
$$

を計算する。

復号では、

$$
M=C_2-dC_1
$$

を計算することで、元の平文を取り出す。

このように、暗号化と復号の処理は、どちらもECCクラスで実装した点の加算とスカラー倍によって実現できる。

5.4 メイン処理（main.py）

最後に、これらのクラスを呼び出すmain.pyを作成した。

main.py

from ecc_cal import ECC
from gen_key import GenKey
from EC_ElGamal import EC_ElGamal


def main():
    P = 1009
    A = 1
    B = 50
    G = (0, 177)
    private_key = 114
    M = (3, 33)
    k = 60  # 1~999

    ecc = ECC(P, A, B, G)
    key_generator = GenKey(private_key, ecc)
    public_key = key_generator.gen_public_key()
    ec_elgamal = EC_ElGamal(M, public_key, private_key, k, ecc)

    C1, C2 = ec_elgamal.encryption()
    restored = ec_elgamal.decryption(C1, C2)
    print("平文: ", M)
    print("暗号化: ", (C1, C2))
    print("復号: ", restored)
    print("一致: ", restored == M)
    if restored != M:
        raise AssertionError("復号結果が元の平文と一致しません")


if __name__ == "__main__":
    main()

ここでは楕円曲線のパラメータ、基準点、秘密鍵、平文、暗号化用の整数kを設定している。

その後、公開鍵の生成、暗号化、復号を順番に実行し、元の平文と復号結果が一致するかを確認する。

今回は動作を確認しやすくするため、各パラメータを固定して実行した。

6 実行結果と検証

6.1 パラメータの設定

今回は次の楕円曲線を使用した。

$$
\boxed{y^2\equiv x^3+x+50\pmod{1009}}
$$

この曲線は、無限遠点を含めて1000個の点を持つ。

また、基準点として$G=(0,177)$を選んだ。この点の位数は1000であり、

$$
1000G=O
$$

が成立する。

今回使用したパラメータを以下にまとめる。

パラメータ	設定値
素数 $p$	1009
曲線の係数 $A$	1
曲線の係数 $B$	50
基準点 $G$	$(0,177)$
秘密鍵 $d$	114
平文 $M$	$(3,33)$
暗号化用の整数 $k$	60

なお、平文として使用した$(3,33)$は、

$$
33^2\equiv3^3+3+50\pmod{1009}
$$

を満たしており、今回の楕円曲線上の点である。

6.2 実行結果

main.pyを実行した結果、次の出力が得られた。

平文:  (3, 33)
暗号化:  ((80, 604), (726, 130))
復号:  (3, 33)
一致:  True

暗号化によって、元の平文$(3,33)$は2つの点

$$
C_1=(80,604),\quad C_2=(726,130)
$$

に変換された。

また、復号結果は元の平文と一致し、Trueが出力された。

6.3 計算結果の確認

実際に暗号化と復号の計算を確認してみる。

まず、秘密鍵$d=114$から公開鍵を生成すると、

$$
Q=114G=(5,455)
$$

となる。

次に、$k=60$を用いて暗号化を行う。

$$
\begin{aligned}
C_1&=60G=(80,604)\
C_2&=M+60Q=(726,130)
\end{aligned}
$$

復号では、秘密鍵を用いて、

$$
dC_1=114C_1=(285,229)
$$

を計算する。

これは、暗号化時に計算した$60Q$と一致している。

したがって、

\begin{aligned}
M&=C_2-dC_1\\
&=C_2+(-dC_1)\\
&=(726,130)+(285,780)\\
&=(3,33)
\end{aligned}

となり、元の平文を復元できた。

以上より、今回設定したパラメータに対して、EC-ElGamal暗号による暗号化と復号が正しく動作することを確認できた。

ただし、この結果だけで、あらゆる入力に対する動作や暗号としての安全性が保証されるわけではない。

7 まとめと今後の課題

今回は、数学を利用したプログラミングに挑戦するため、楕円曲線暗号の基本的な計算機構をPythonで実装した。

特に、有限体上での演算や楕円曲線上の点の加算など、数学的な操作を実際のプログラムに落とし込む過程がとても面白かった。

また、これらの計算を組み合わせることで、公開鍵の生成から暗号化、復号までを実現できた。

一方で、今回のプログラムにはいくつかの課題が残っている。

まず、今回使用した楕円曲線は学習用の小さなものであり、実際の暗号として使用するには安全性が不十分である。加えて、秘密鍵や暗号化用の整数を固定しているため、実用的な暗号方式とは異なる。

また、今回の実装では平文を楕円曲線上の点として扱っているため、文字列などの一般的なデータをそのまま暗号化することはできない。

今後は、以下のようなことにも挑戦してみたい。

• 文字列などのデータを暗号化できる仕組みの実装
• ECDHによる鍵共有の実装
• より大きな有限体上での計算
• 入力検証や鍵生成処理の改善
• 他の公開鍵暗号の実装

今回の実装を通じて、数学的な理論がプログラムとして実際に機能することを確認できた。

まだまだ改善の余地はあるが、今後も数学とプログラミングを組み合わせたものを作っていきたい。

なお、今回作成したコードはGitHubに公開している。

※本プログラムは学習・検証を目的としたものであり、実際の機密情報の暗号化には使用しないでください。

8 参考文献

• SSLサポートチーム，「楕円曲線暗号 (ECC) とは何ですか?」，SSL.com，2024年10月8日，https://www.ssl.com/ja/記事/楕円曲線暗号とは/
• 奥秋清次，「楕円ElGamal暗号の実装」，千葉職業能力開発短期大学校紀要，第21号，2016年12月，https://www3.jeed.go.jp/chiba/college/media/20240422-142956-344.pdf