Skip to content

Latest commit

 

History

History
674 lines (518 loc) · 19.3 KB

note.md

File metadata and controls

674 lines (518 loc) · 19.3 KB
Raw

ecpy notes

hackmd: https://hackmd.io/JwZgJsAMDswGYFoCsBDAHAYwQFhfBARtpJAtAGxJwBMVY1AjJEkA#

C++クラス設計

C++側で書くクラスの設計について

ある対象を構造と値にそれぞれ分離して考える。有限体なら有限体の演算・素数を構造、実際の整数値は値として扱う。

構造クラス

  • FF
  • EF
  • EC

→ 値クラスに対する操作(演算)や共通保持すべきデータを保持するクラス。

値クラス

  • FF_elem
  • EF_elem
  • EC_elem

→ 値の保持を主目的とするクラス。

構造・値クラスが共通に持つメンバ関数

構造/値クラス T が必ず持つべきメンバ関数を定義する。

struct T {
  T* clone(void) const;
  std::string to_string(void) const;
};

構造クラスの持つメンバ関数

構造クラス T が必ず持つべきメンバ関数を定義する。 E は対応する値クラス。

template <class E>
struct T {
  void add(E& ret, const E& a, const E& b) const;
  void sub(E& ret, const E& a, const E& b) const;
  void mul(E& ret, const E& a, const E& b) const;
  void div(E& ret, const E& a, const E& b) const;
  void pow(E& ret, const E& a, const mpz_class& b) const;
  bool equals(const E& a, const E& b) const;
};

特殊メンバ関数について

これらの関数では例外は一切投げない。

struct T {
  T();
  ~T();
  T(const T&);
  T(T&&);
  T& operator=(const T&);
  T& operator=(T&&);
};

Pythonクラス設計

Python側でのC++ラッパクラスの設計。

以下、基本的な事柄として lib はecpy_nativeライブラリのctypes.CDLLインスタンスで、 ctypes は from ctypes import * でインポートされているとする。

構造クラスのラッパクラスの設計

基本となるクラスは以下のようにする。 構造クラスを T 、対応する値クラスを E とする。

class T(object):
  def __init__(s, params): # paramsは適宜パラメータを入れる。複数でも構わない。
    s.ptr = lib.T_create(params)

  def __to_string(s, bufsize): # to_stringのラッパ, バッファのサイズは可変
    b = create_string_buffer(bufsize)
    lib.T_to_string(s.ptr, b, bufsize)
    b = b.value
	if len(b) == 0: # not enough buffer size
	  return s.__to_string(2*bufsize)
	return b

  def __str__(s):
    return s.__to_string(1024)

  def add(s, ret, a, b):
    assert isinstance(ret, E) and isinstance(a, E) and isinstance(b, E)
    lib.T_add(s.ptr, ret.ptr, a.ptr, b.ptr)

  def sub(s, ret, a, b):
    assert isinstance(ret, E) and isinstance(a, E) and isinstance(b, E)
    lib.T_sub(s.ptr, ret.ptr, a.ptr, b.ptr)

  def mul(s, ret, a, b):
    assert isinstance(ret, E) and isinstance(a, E) and isinstance(b, E)
    lib.T_mul(s.ptr, ret.ptr, a.ptr, b.ptr)

  def div(s, ret, a, b):
    assert isinstance(ret, E) and isinstance(a, E) and isinstance(b, E)
    lib.T_div(s.ptr, ret.ptr, a.ptr, b.ptr)

  def pow(s, ret, a, b):
    assert isinstance(ret, E) and isinstance(a, E)
    lib.T_pow(s.ptr, ret.ptr, a.ptr, str(b))
	
  def equ(s, a, b):
    assert isinstance(a, E) and isinstance(b, E)
	return lib.T_equ(s.ptr, a.ptr, b.ptr) != 0

  def __del__(s): # GC deleter
    lib.T_delete(s.ptr)

値クラスのラッパクラスの設計

構造クラスと大方同じだが、こちらは値の保持が目的なのでそちらを優先する。

class E(object):
  def __init__(s, params): # paramsは適宜パラメータを入れる。複数でも構わない。
    s.ptr = lib.E_create(params)

  def __to_string(s, bufsize): # to_stringのラッパ, バッファのサイズは可変
    b = create_string_buffer(bufsize)
    lib.E_to_string(s.ptr, b, bufsize)
    b = b.value
	if len(b) == 0: # not enough buffer size
	  return s.__to_string(2*bufsize)
	return b

  def __str__(s):
    return s.__to_string(1024)

  def __del__(s): # GC deleter
    lib.E_delete(s.ptr)

  def to_python(s):
    # Pythonのオブジェクトに変換する。FFなら数値、EFならタプル等で、これは明確に規定する必要がある。

Python<=>C++インターフェース

基本的には不透明ポインタをハンドルのように扱うことで実現する。

多倍長整数について

Python側での多倍長整数(C APIでのPyLong型)をC++へ渡す際は文字列として渡した後C++側でmpz_classへ変換する。

Python:

# lib.cpp_func(1<<256) # <= long型なので直接渡せない
lib.cpp_func(str(1<<256)) # <= OK

C++:

// __EXPORT__ void cpp_func(const mpz_class& x); <= 直接の変換は不可能
__EXPORT__ void cpp_func(const char *x); // <= OK, 内部でmpz_classへ変換される

文字列を戻り値とする関数について

文字列を戻り値に持つ関数(現在の設計ではto_string)についてはPython ctypes APIのctypes.create_string_bufferを用いて文字列バッファを用意、そこにコピーするようにする

C++側では次の関数 (ecpy_native.h に用意されている)を用いてバッファに文字列をコピーする。

template <class T>
void write_to_python_string(const T *x, char *ptr, int len) {
  std::stringstream ss;
  ss << x->to_string();
  std::string r = ss.str();
  if (r.size() < len) {
    strcpy(ptr, r.c_str());
  }
}

Python側は上のクラス設計の際のものと同じ。

  def __to_string(s, bufsize): # to_stringのラッパ, バッファのサイズは可変
    b = create_string_buffer(bufsize)
    lib.E_to_string(s.ptr, b, bufsize)
    b = b.value
	if len(b) == 0: # not enough buffer size
	  return s.__to_string(2*bufsize)
	return b

  def __str__(s):
    return s.__to_string(1024)

構造クラスのインターフェース関数

構造クラスを T とし、値クラスを E とする

__EXPORT__ {
  // create T instance
  T *T_create(〜);
  // delete T instance
  void T_delete(const T*);
  // ret = a + b
  void T_add(const T *obj, E *ret, const E *a, const E *b);
  // ret = a - b
  void T_sub(const T *obj, E *ret, const E *a, const E *b);
  // ret = a * b
  void T_mul(const T *obj, E *ret, const E *a, const E *b);
  // ret = a / b
  void T_div(const T *obj, E *ret, const E *a, const E *b);
  // ret = a ^ b
  void T_pow(const T *obj, E *ret, const E *a, const char *b);
  // a == b
  int T_equ(const T *obj, const E *a, const E *b);
  // to python __str__ function
  void T_to_string(const T *obj, char *ptr, int len);
};

値クラスのインターフェース関数

構造クラスを T とし、値クラスを E とする

__EXPORT__ {
  // create E instance
  E *E_create(〜);
  // delete E instance
  void E_delete(const E*);
  // to python __str__ function
  void E_to_string(const E *obj, char *ptr, int len);
};

FF/FF_elem

FF

struct FF {
  mpz_class p;

  FF() = default;
  ~FF() = default;
  FF(const mpz_class& p) : p(p) {}
  FF(const FF& t) : p(t.p) {}
  FF(FF&& t) : p(std::move(t.p)) {};

  FF& operator=(const FF&);
  FF& operator=(FF&&);

  // common functions
  FF* clone(void) const;
  std::string to_string(void) const;

  // structure class member functions
  void add(FF_elem& ret, const FF_elem& a, const FF_elem& b) const;
  void sub(FF_elem& ret, const FF_elem& a, const FF_elem& b) const;
  void mul(FF_elem& ret, const FF_elem& a, const FF_elem& b) const;
  void div(FF_elem& ret, const FF_elem& a, const FF_elem& b) const;
  void pow(FF_elem& ret, const FF_elem& a, const mpz_class& b) const;
  bool equ(const FF_elem& a, const FF_elem& b) const;
};

FF_elem

struct FF_elem {
  mpz_class v;

  FF_elem(const mpz_class& v) : v(v) {};

  FF_elem() = default;
  ~FF_elem() = default;
  FF_elem(const FF_elem& t) : v(t.v) {};
  FF_elem(FF_elem&& t) : v(std::move(t.v)) {};

  FF_elem& operator=(const FF_elem&);
  FF_elem& operator=(FF_elem&&);

  // common functions
  FF_elem* clone(void) const;
  std::string to_string(void) const;
};

FF/FF_elem のPythonインターフェース

struct FF;
struct FF_elem;
// FF
__EXPORT__ {
  // create FF instance
  FF *FF_create(const char *p);
  // delete FF instance
  void FF_delete(const FF*);
  // ret = a + b
  void FF_add(const FF *obj, FF_elem *ret, const FF_elem *a, const FF_elem *b);
  // ret = a - b
  void FF_sub(const FF *obj, FF_elem *ret, const FF_elem *a, const FF_elem *b);
  // ret = a * b
  void FF_mul(const FF *obj, FF_elem *ret, const FF_elem *a, const FF_elem *b);
  // ret = a / b
  void FF_div(const FF *obj, FF_elem *ret, const FF_elem *a, const FF_elem *b);
  // ret = a ^ b
  void FF_pow(const FF *obj, FF_elem *ret, const FF_elem *a, const char *b);
  // a == b
  int FF_equ(const FF *obj, const FF_elem *a, const FF_elem *b);
  // to python __str__ function
  void FF_to_string(const FF *obj, char *ptr, int len);
};

// FF_elem
__EXPORT__ {
  // create FF_elem instance
  FF_elem *FF_elem_create(const char *v);
  // delete FF_elem instance
  void FF_elem_delete(const FF_elem*);
  // to python __str__ function
  void FF_elem_to_string(const FF_elem *obj, char *ptr, int len);
};

to_pythonの返り値: FF_elem

int(str(s))

つまり保持している数値をそのまま返す。

EF/EF_elem

既約多項式が2種類($x^2+1$, $x^2+x+1$)あるので、これはenumにしておく

enumeration declaration - cppreference.com

the keywords class and struct are exactly equivalent

enum class IrreduciblePolynomialType : int {
  X2_1, // x^2+1
  X2_X_1, // x^2+x+1
};

EF

struct EF {
  const FF& base;
  IrreduciblePolynomialType poly;

  EF(const FF& ff, IrreduciblePolynomialType pol) : base(ff), poly(pol) {}

  EF(const mpz_class& p, IrreduciblePolynomialType pol) : base(p), poly(pol) {}


  EF() = default;
  ~EF() = default;
  EF(const EF& ef) : base(ef.base), poly(ef.poly) {}
  EF(EF&& ef) : base(std::move(ef.base)), poly(ef.poly) {}

  EF& operator=(const EF& ef);
  EF& operator=(EF&& ef);

  // structure class member functions
  void add(EF_elem& ret, const EF_elem& a, const EF_elem& b) const;
  void sub(EF_elem& ret, const EF_elem& a, const EF_elem& b) const;
  void mul(EF_elem& ret, const EF_elem& a, const EF_elem& b) const;
  void div(EF_elem& ret, const EF_elem& a, const EF_elem& b) const;
  void pow(EF_elem& ret, const EF_elem& a, const mpz_class& b) const;
  bool equ(const EF_elem& a, const EF_elem& b) const;

  // common functions
  EF* clone(void) const;
  std::string to_string(void) const;
};

EF_elem

struct EF_elem {
  FF_elem u, v;

  EF_elem(const FF_elem& u, const FF_elem& v = 0) : u(u), v(v) {}

  EF_elem(const mpz_class& u, const mpz_class& v = 0) : u(u), v(v) {}


  EF_elem() = default;
  ~EF_elem() = default;
  EF_elem(const EF_elem& ee) : u(ee.u), v(ee.v) {};
  EF_elem(EF_elem&& ee) : u(std::move(ee.u)), v(std::move(ee.v)) {};

  EF_elem& operator=(const EF_elem& ee);
  EF_elem& operator=(EF_elem&& ee);

  // common functions
  EF_elem* clone(void) const;
  std::string to_string(void) const;
};

EF/EF_elemのPythonインターフェース

struct EF;
struct EF_elem;

// EF
__EXPORT__ {
  // create EF instance
  // polynomial is string of irreducible polynomial. 
  // e.g. x^2+x+1, x^2+1, X^2+1, x^2+ x +1 (ignore spaces and case insensitive)
  EF *EF_create(const char *p, const char *polynomial);
  // delete EF instance
  void EF_delete(const EF *ef);

  // r = a + b
  void EF_add(const EF *obj, EF_elem *ret, const EF_elem *a, const EF_elem *b);
  // r = a - b
  void EF_sub(const EF *obj, EF_elem *ret, const EF_elem *a, const EF_elem *b);
  // r = a * b
  void EF_mul(const EF *obj, EF_elem *ret, const EF_elem *a, const EF_elem *b);
  // r = a / b
  void EF_div(const EF *obj, EF_elem *ret, const EF_elem *a, const EF_elem *b);
  // r = a ^ b
  void EF_pow(const EF *obj, EF_elem *ret, const EF_elem *a, const char *b);
  // a == b
  int EF_equ(const EF *obj, const EF_elem *a, const EF_elem *b);
  void EF_to_string(const EF *obj, char *ptr, int len);
};

// EF_elem
__EXPORT__ {
  EF_elem *EF_elem_create(const char *u, const char *v);
  void EF_elem_delete(const EF_elem *obj);
  void EF_elem_to_string(const EF_elem *obj, char *ptr, int len);
};

to_pythonの返り値: EF_elem

ast.literal_eval(str(s).lstrip("EF_elem")))

二次拡大体なので2つの要素が返らなければならない。そのため返り値はタプルで内容は要素を a+b*v (vは基底) とした時 (a, b)。

EC/EC_elem

楕円曲線クラス

べき乗・除算は数式上ありえないので除外する。除外するにはdelete代入を利用する。

テンプレート型引数の T は FF/EF 等構造クラスを表し、 E は対応する値クラスを表す。

EC

template <class T>
struct EC {
  const T& base;
  mpz_class a, b;
  
  EC(const T& base, const mpz_class& a, const mpz_class& b) : base(base), a(a), b(b) {}
  
  EC() = default;
  ~EC() = default;
  EC(const EC<T>& ec) : base(ec.base), a(ec.a), b(ec.b) {};
  EC(EC<T>&& ec) : base(std::move(ec.base)), a(std::move(ec.a)), b(std::move(ec.b)) {};
  EC<T>& operator=(const EC<T>& ec);
  EC<T>& operator=(EC<T>&& ec);
  
  template <class E>
  void add(EC_elem<E>& ret, const EC_elem<E>& a, const EC_elem<E>& b) const;
  template <class E>
  void sub(EC_elem<E>& ret, const EC_elem<E>& a, const EC_elem<E>& b) const;
  template <class E>
  void mul(EC_elem<E>& ret, const EC_elem<E>& a, const mpz_class& b) const;
  template <class E>
  bool equ(const EC_elem<E>	& a, const EC_elem<E>& b) const;
  
  // ----------------- UNDEFINED(DELETED) -----------------
  template <class E>
  void mul(EC_elem<E>& ret, const EC_elem<E>& a, const EC_elem<E>& b) const = delete;
  template <class E>
  void div(EC_elem<E>& ret, const EC_elem<E>& a, const EC_elem<E>& b) const = delete;
  template <class E>
  void pow(EC_elem<E>& ret, const EC_elem<E>& a, const mpz_class& b) const = delete;
  // ------------------------------------------------------

  template <class E>
  EC_elem<E> to_affine(const EC_elem<E>& elem) const;
  template <class E>
  E line_coeff(const EC_elem<E>& P, const EC_elem<E>& Q) const;
  template <class E>
  bool is_on_curve(const EC_elem<E>& elem) const;
  template <class E>
  bool is_infinity(const EC_elem<E>& P) const;
  EC<T>* clone(void) const;
  std::string to_string(void) const;
};

追加した関数については以下の通り:

to_affine

あるEC_elemについて通常の射影座標からアフィン座標(xy座標)に変換して返す(z座標を1にして実質アフィン座標になるようにする)

line_coeff

楕円曲線の点P、点Qを通る直線 $ax + b$ の係数 $a$ を求める。もし $P=Q$ だったならば接線の係数を返す。

is_on_curve

ある点Pが楕円曲線上の点かどうかを判定する。

is_infinity

ある点Pが無限遠点かどうかを判定する。

EC_elem

template <class T>
struct EC_elem {
  T x, y, z;
  
  EC_elem(const mpz_class& x, const mpz_class& y, const mpz_class& z) : x(x), y(y), z(z) {}
  
  EC_elem() = default;
  ~EC_elem() = default;
  EC_elem(const EC_elem<T>& ee) : x(ee.x), y(ee.y), z(ee.z) {};
  EC_elem(EC_elem<T>&& ee) : x(std::move(ee.x)), y(std::move(ee.y)), z(std::move(ee.z)) {};
  EC_elem<T>& operator=(const EC_elem<T>&);
  EC_elem<T>& operator=(EC_elem<T>&&);
  
  EC_elem<T>* clone(void) const;
  std::string to_string(void) const;
};

ECのPythonインターフェース

template <class T>
struct EC;
template <class E>
struct EC_elem;

__EXPORT__ {
  // create EC<FF> instance
  EC<FF> *EC_FF_create(const char *a, const char *b, const FF *base);
  // delete EC<FF> instance
  void EC_FF_delete(const EC<FF>* obj);
  // ret = a + b
  void EC_FF_add(const EC<FF> *obj, EC_elem<FF_elem> *ret, const EC_elem<FF_elem> *a, const EC_elem<FF_elem> *b);
  // ret = a - b
  void EC_FF_sub(const EC<FF> *obj, EC_elem<FF_elem> *ret, const EC_elem<FF_elem> *a, const EC_elem<FF_elem> *b);
  // ret = a * b
  void EC_FF_mul(const EC<FF> *obj, EC_elem<FF_elem> *ret, const EC_elem<FF_elem> *a, const char *b);
  // a == b
  int EC_FF_equ(const EC<FF> *obj, const EC_elem<FF_elem> *a, const EC_elem<FF_elem> *b);
  // to python __str__ function
  void EC_FF_to_string(const EC<FF> *obj, char *ptr, int len);
};

__EXPORT__ {
  // create EC<EF> instance
  EC<FF> *EC_EF_create(const char *a, const char *b, const EF *base);
  // delete EC<EF> instance
  void EC_EF_delete(const EC<EF>* obj);
  // ret = a + b
  void EC_EF_add(const EC<EF> *obj, EC_elem<EF_elem> *ret, const EC_elem<EF_elem> *a, const EC_elem<EF_elem> *b);
  // ret = a - b
  void EC_EF_sub(const EC<EF> *obj, EC_elem<EF_elem> *ret, const EC_elem<EF_elem> *a, const EC_elem<EF_elem> *b);
  // ret = a * b
  void EC_EF_mul(const EC<EF> *obj, EC_elem<EF_elem> *ret, const EC_elem<EF_elem> *a, const char *b);
  // a == b
  int EC_EF_equ(const EC<EF> *obj, const EC_elem<EF_elem> *a, const EC_elem<EF_elem> *b);
  // to python __str__ function
  void EC_EF_to_string(const EC<EF> *obj, char *ptr, int len);
};

EC_elemのPythonインターフェース

template <class T>
struct EC;
template <class E>
struct EC_elem;

__EXPORT__ {
  // create EC_elem<FF_elem> instance
  EC_elem<FF_elem> *EC_elem_FF_create(const FF_elem *x, const FF_elem *y, const FF_elem *z);
  // delete E instance
  void EC_elem_FF_delete(const EC_elem<FF_elem>* obj);
  // to python __str__ function
  void EC_elem_FF_to_string(const EC_elem<FF_elem> *obj, char *ptr, int len);
};

__EXPORT__ {
  // create EC_elem<EF_elem> instance
  EC_elem<EF_elem> *EC_elem_EF_create(const EF_elem *x, const EF_elem *y, const EF_elem *z);
  // delete E instance
  void EC_elem_EF_delete(const EC_elem<EF_elem>* obj);
  // to python __str__ function
  void EC_elem_EF_to_string(const EC_elem<EF_elem> *obj, char *ptr, int len);
};

ペアリング関数群

ペアリングのために必要な関数の設計

  • miller
  • weil_pairing
  • tate_pairing

miller関数

Miller algorithmの実装, 中にラムダ式でh関数を持つ 返り値は第一引数const E& retに返り、その値は因子$m(P) - m(O)$を持つ関数$f_P$に$Q$を適用した$f_P(Q)$の値。

template <class T>
template <class E>
void miller(const E& ret, const EC<T> curve const EC_elem<E> P, const EC_elem<E> Q, const int& m);

weil_pairing関数

Weil Pairingの計算をする関数。

template <class T>
template <class E>
void weil_pairing(const E& ret, const EC<T> curve const EC_elem<E> P, const EC_elem<E> Q, const int& m);

weil_pairing関数

Tate-Lichtenbaum Pairingの計算をする関数。

template <class T>
template <class E>
void tate_pairing(const E& ret, const EC<T> curve const EC_elem<E> P, const EC_elem<E> Q, const int& m, const int& embedding_degree);

References