Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

ed25519のpython実装を紐解く その1数学編

ed25519のpythonによるリファレンス実装を解説してみます。
pythonのリファレンス実装はこちらです。
https://ed25519.cr.yp.to/python/ed25519.py

数学的な関数の解説のみ簡単に行います。
詳しくはこのブログの他の記事に記載があります。
使う楕円曲線はed25519と呼ばれる、Twisted Edward曲線です。

q = 2**255 - 19
L = 2**252 + 27742317777372353535851937790883648493

素数2255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949
=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
は10進数で77桁の素数です。
曲線の方程式は - {x}^{2} + {y}^{2} = 1 - \frac {121665} {121666}  {x}^{2} {y}^{2} という形をしており、xが一つ決まるとyが一つ決まりますが、x,yは共に整数しか取りません。
そして、 - \frac {121655} {121666}は分数ではなく整数であり、
 - \frac {121655} {121666} = 37095705934669439343138083508754565189542113879843219016388785533085940283555 という10進数で77桁の整数です。
この方程式は素数qを法とし成り立つものとして考えます。
なぜ割り算で表現してあるかというと、その方が77桁の整数を全てを書くよりも紙面が節約できるからです。
なぜ割り算がこうなるのかというと、素数を法とした演算を使うと体を成すことが知られているためです。
これを素体といいます。
整数の範囲内での演算なので、割り算は掛け算を使って表現します。

LはこちらのRFC8032
RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
に書かれている通り、 ed255199曲線の有理点の数(#Eと表現します。)の約数である素数であり、
 L = {2}^{252}  + 27742317777372353535851937790883648493
= 7237005577332262213973186563042994240857116359379907606001950938285454250989
= 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
という10進で76桁の整数です。
なお、 8 L = \#E です。
Hasse-Weilの定理を考えると、有理点の数がこのくらいあることは納得感があります。
つまり有理点の数は10進で77桁くらいあるということです。(※1)
また、このLはある条件を満たしますが、これは後で説明します。

def expmod(b,e,m):
  if e == 0: return 1
  t = expmod(b,e/2,m)**2 % m
  if e & 1: t = (t*b) % m
  return t

expmod関数では高速指数計算法で法mにおいてbのe乗を計算する関数です。

def inv(x):
  return expmod(x,q-2,q)

inv関数では法qにおけるxの逆数を計算する関数です。
なぜq-2乗すると逆数になるのかはオイラーの小定理を考えると理解できます。

d = -121665 * inv(121666)

そのままですね。

I = expmod(2,(q-1)/4,q)

これは、ここで平方剰余を計算するときのケースAのときの係数です。

mod pでの平方剰余を計算する(p mod 8 = 5の場合)を実装する - Pebble Coding

def xrecover(y):
  xx = (y*y-1) * inv(d*y*y+1)
  x = expmod(xx,(q+3)/8,q)
  if (x*x - xx) % q != 0: x = (x*I) % q
  if x % 2 != 0: x = q-x
  return x

xrecovery関数は、曲線上のyの値が与えられたときにxの値を求める関数です。
単純にed25519の方程式をxについてまとめると最初の式になり、 {x}^{2} = aを解く形になります。
この解き方は先ほどのリンクで説明しています。
xが奇数になったときは、奇素数qを使って反転して、q(奇数)-x(奇数) = 偶数に変換しています。
xが解であるとき、q-xが解であることは、
 {(q-x)}^{2} = {q}^{2} - 2qx + {x}^{2} =  {x}^{2} \mod qであることから分かります。

By = 4 * inv(5)
Bx = xrecover(By)
B = [Bx % q,By % q]

これもRFCに記載されていますが、ベースポイントの座標です。 実際の値は次のような値です。
Bx = 15112221349535400772501151409588531511454012693041857206046113283949847762202
77桁の10進数

By = 46316835694926478169428394003475163141307993866256225615783033603165251855960
77桁の10進数

ベースポイントBとは点のスカラー倍を計算していくときの最初の点です。
点BをLスカラー倍したときにゼロ点(x=0, y=1)になります。
通常の楕円曲線ではゼロ点は無限遠点ですが、この曲線ではこのような有限の値の点になるので、
コンピュータでの計算が分かりやすくなっています。
Lは最初の方で出てきた値です。
つまり  L B = 0と表現できます。 点Bの位数はLであるともいいます。

これらの条件は、楕円曲線暗号において知られている攻撃方法を回避するように設定されています。
新たな攻撃方法が発見されない限り、安全だと言えます。

def edwards(P,Q):
  x1 = P[0]
  y1 = P[1]
  x2 = Q[0]
  y2 = Q[1]
  x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)
  y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2)
  return [x3 % q,y3 % q]

edwards関数では点Pと点Qを加算した点の座標を求めています。

def scalarmult(P,e):
  if e == 0: return [0,1]
  Q = scalarmult(P,e/2)
  Q = edwards(Q,Q)
  if e & 1: Q = edwards(Q,P)
  return Q

scalarmult関数では点Pをe倍した点の座標を求めます。
これは、倍数を高速に計算する方法を再帰で実装したものです。 このリンク
高速指数計算法アルゴリズム - Pebble Coding
ではべき乗の場合ですが、倍数の場合も同じようなロジックになります。

def isoncurve(P):
  x = P[0]
  y = P[1]
  return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0

isoncurve関数は点Pが楕円曲線上にあるかどうかを返す関数です。

ここでみたように楕円曲線暗号は初等整数論、楕円関数論を活用して作られていることが分かります。
大学の数学科4年生レベルの数学知識が求められ、理解するのに一筋縄ではいきません。

※1 この有理点の数を求めるのにどのくらい時間がかかるのか想像できていません。
mac book proでは数分レベルでないことは分かっていますが、誰か調べて欲しい。。

ed25519のpython実装を紐解く その2 暗号編キーペア生成からベリファイまで - Pebble Coding