国密SM 9アルゴリズムC++実現の三:楕円曲線インタフェース、パラメータ初期化

35922 ワード

SM 9アルゴリズムC++実装シリーズ目次:
  • JPBCのSM 9アルゴリズムに基づくjava実装とテスト
  • 国密SM 9アルゴリズムC++実現の0:ソースコードダウンロードアドレス
  • 国密SM 9アルゴリズムC++実現の一つ:アルゴリズム概要
  • 国密SM 9アルゴリズムC++実現その2:テストツール
  • 国密SM 9アルゴリズムC++実現の3:楕円曲線インタフェース、パラメータ初期化
  • 国密SM 9アルゴリズムC++実現の4:基本機能関数とKGCインタフェースの実現
  • 国密SM 9アルゴリズムC++実現の5:署名チェックアルゴリズム
  • 国密SM 9アルゴリズムC++実現の6:鍵パッケージ解封アルゴリズム
  • 国密SM 9アルゴリズムC++実現の7:暗号解読アルゴリズム
  • 国密SM 9アルゴリズムC++実現の8:鍵交換アルゴリズム
  • 国密SM 9アルゴリズムC++実現の九:アルゴリズム機能とテスト例
  • 国密SM 9アルゴリズムC++実現の三:曲線インタフェース、パラメータ初期化
    文書ディレクトリ
  • 国密SM 9アルゴリズムC++実現の3:曲線インタフェース、パラメータ初期化
  • @[toc]
  • エラー異常処理
  • 数学機能
  • 群G 1倍点計算
  • 群G 2倍点計算
  • GT群上点の数学演算とR-ate双線形対計算
  • パラメータ初期化
  • Parameters.h
  • Parameters.cpp
  • 双線形対計算
  • zzn12.h
  • zzn12.cpp

  • 以下のいくつかの記事では、miraclベースのSM 9アルゴリズムの各部分の実装について説明する.
    まず、実装時に、下位層の数学機能はmiraclライブラリによって提供され、さらにZZN 12クラスが二重線形ペアの計算を処理するためにパッケージされている.上位のアルゴリズムフローはC++で書かれています.次に、全体のコードは大きく3つのモジュールに分けられ、1つ目のモジュールは数学機能関数の実現、パラメータの初期化と解放であり、この部分はmiraclライブラリの中のいくつかのオブジェクト、例えば大数オブジェクト、曲線点オブジェクトなどに関連するため、それを下層実装として遮蔽し、SM 9アルゴリズム機能を使用する人には関心を持たない.この部分はParametersとZZN 12クラスで実現される.第2のモジュールはKGC機能の実現であり、主に主鍵対とユーザー秘密鍵の生成であり、KGCクラスに含まれる.第3のモジュールはアルゴリズム機能実装であり、署名チェック、鍵パッケージの解封、暗号解読、鍵交換を含み、SM 9クラスに含まれる.後者の2つのモジュールは上位層で使用されるモジュールであり,すべてのSM 9のデータはstd::stringで格納され,下位層の大数オブジェクト,曲線点オブジェクトなどには関与しない.また,アルゴリズムで設計された複数のデータ部分を含む結果は,いずれも単純に1つのクラスオブジェクトにカプセル化される.同時に、すべてのインタフェースはstaticです.最後に、すべてのエラーまたは例外はstd::exceptionで投げ出され、インタフェースを呼び出すときにキャプチャする必要があります.
    この論文では,最初のモジュールの実装とエラー処理について論じる.
    エラー例外処理
    SM 9ドキュメントで発生したエラー処理として必要な箇所について,それを抽出し,アルゴリズム実装においてstd::exceptionで投げ出すのに便利なErrorsクラスを書いた.
    // Errors.h
    #ifndef YY_SM9_ERROR_INCLUDE_H__
    #define YY_SM9_ERROR_INCLUDE_H__
    
    #pragma once
    
    #include 
    using namespace std;
    
    #define SM9_OK									0x00000000
    #define SM9_ERROR_NOT_INIT						0x00000001
    #define SM9_ERROR_INIT_G1BASEPOINT				0x00000002
    #define SM9_ERROR_INIT_G2BASEPOINT				0x00000003
    #define SM9_ERROR_CALC_RATE						0x00000004
    #define SM9_ERROR_KGC_GENPRIKEY_T1_IS_ZERO		0x00000005
    #define SM9_ERROR_KGC_WRONG_PRIKEY_TYPE			0x00000006
    #define SM9_ERROR_VERIFY_H_OUTRANGE				0x00000007
    #define SM9_ERROR_VERIFY_S_NOT_ON_G1			0x00000008
    #define SM9_ERROR_VERIFY_H_VERIFY_FAILED		0x00000009
    #define SM9_ERROR_DECAP_C_NOT_ON_G1				0x0000000A
    #define SM9_ERROR_DECAP_K_IS_ZERO				0x0000000B
    #define SM9_ERROR_DECRYPT_C1_NOT_ON_G1			0x0000000C
    #define SM9_ERROR_DECRYPT_K1_IS_ZERO			0x0000000D
    #define SM9_ERROR_DECRYPT_C3_VERIFY_FAILED		0x0000000E
    #define SM9_ERROR_KEYEXCHANGE_R_NOT_ON_G1		0x0000000F
    
    
    
    /**
    *     .
    * @author YaoYuan
    */
    class Errors {
    private:
    	Errors() {}
    	~Errors() {}
    
    public:
    	static string getErrorMsg(int errnum) {
    		string msg = "Unknown error";
    		switch( errnum )
    		{
    			case SM9_OK:
    				msg = "Success";
    				break;
    			case SM9_ERROR_NOT_INIT:
    				msg = "Not init";
    				break;
    			case SM9_ERROR_INIT_G1BASEPOINT:
    				msg = "G1 init error";
    				break;
    			case SM9_ERROR_INIT_G2BASEPOINT:
    				msg = "G2 init error";
    				break;
    			case SM9_ERROR_CALC_RATE:
    				msg = "R-ate result is not of order q";
    				break;
    			case SM9_ERROR_VERIFY_H_OUTRANGE:
    				msg = "Verify : h is out range";
    				break;
    			case SM9_ERROR_VERIFY_S_NOT_ON_G1:
    				msg = "Verify : s is not on G1";
    				break;
    			case SM9_ERROR_VERIFY_H_VERIFY_FAILED:
    				msg = "Verify failed, h verify failed";
    				break;
    			case SM9_ERROR_DECAP_C_NOT_ON_G1:
    				msg = "Decapsulate : C is not on G1";
    				break;
    			case SM9_ERROR_DECAP_K_IS_ZERO:
    				msg = "Decapsulate : K is zero";
    				break;
    			case SM9_ERROR_DECRYPT_C1_NOT_ON_G1:
    				msg = "Decrypt : C1 is not on G1";
    				break;
    			case SM9_ERROR_DECRYPT_K1_IS_ZERO:
    				msg = "Decrypt : K is zero";
    				break;
    			case SM9_ERROR_DECRYPT_C3_VERIFY_FAILED:
    				msg = "Decrypt : C3 verify failed";
    				break;
    			case SM9_ERROR_KEYEXCHANGE_R_NOT_ON_G1:
    				msg = "Key Exchange : R not on G1";
    				break;
    			case SM9_ERROR_KGC_GENPRIKEY_T1_IS_ZERO:
    				msg = "t1 is zero while KGC generate private key";
    				break;
    			case SM9_ERROR_KGC_WRONG_PRIKEY_TYPE:
    				msg = "Wrong private key type for generate private key";
    				break;
    			default:
    				break;
    		}
    
    		return msg;
    	}
    };
    
    
    #endif
    

    数学の機能
    SM 9アルゴリズムを実現するには,群G 1/G 2上の倍点計算,GT群上点の数学演算,R−ate二重線形対計算といういくつかの数学的機能が先に実現される必要がある.
    群G 1倍点算出
    miraclライブラリで「ecurve_」先頭の関数は,SM 9における素地上のG 1群の数学的機能を提供する.
    群G 2倍点計算
    miracleライブラリで「ecn 2_」先頭の関数は、SM 9におけるG 1の2次拡散領域G 2群の数学的機能を提供する.
    GT群上点の数学演算とR-ate双線形対計算
    miralclライブラリのソースコードの「curve/pairing」ディレクトリの下には、12回の拡張ドメイン群の数学的機能と、二重線形ペアの実装があります.この例では、私がネットからダウンロードしたソースコードを参考にして、この機能をZZN 12クラスにパッケージします.
    パラメータ初期化
    パラメータ初期化関連セクションは、次のパラメータクラスに配置されます.
  • は、SM 9パラメータの初期化にinit()関数を提供し、パラメータ解放にrelease()関数を提供する.
  • コード実装では、内部にmiraclライブラリのbig、zzn 2、zzn 4、ecn 2、epointなどの構造体オブジェクトが含まれているため、Parametersクラスでは「init_」が提供されると「release_」先頭の関数を使用して、これらのオブジェクトを初期化および解放します.
  • コード実装では、内部の構造体オブジェクトとstringとの間で変換する必要があるため、いくつかの「cin_」が提供される.と「cout_」冒頭の関数でこの機能を実現します.
  • SM 9アルゴリズムでは、ある点がG 1上にあるか否かを判断する必要がある場合があり、G 1上の点はepointで表され、下位オブジェクトであるため、この関数をParametersに置き、isPointOnG 1(epoint*var)という.
  • には、ZZN 12計算に関連する1つまたは2つの関数があり、Parametersにも置かれています.
  • init()関数では,c++の乱数機能を用いてmiraclの乱数生成器を初期化した.

  • Parametersクラスの内容は次のとおりです.
    Parameters.h
    // Parameters.h
    #ifndef YY_SM9_Parameters_INCLUDE_H__
    #define YY_SM9_Parameters_INCLUDE_H__
    
    #pragma once
    
    #include 
    using namespace std;
    
    #ifdef __cplusplus
    extern "C" {
    #include "miracl/miracl.h"
    }
    #endif
    
    
    #define BIG_LEN 2000
    #define SELF_CHECK 1
    
    class Parameters {
    private:
    	Parameters();
    	~Parameters();
    
    public:
    	static bool init();
    	static void release();
    
    	static void init_big(big& var);
    	static void release_big(big& var);
    
    	static void init_zzn2(zzn2& var);
    	static void release_zzn2(zzn2& var);
    
    	static void init_zzn4(zzn4& var);
    	static void release_zzn4(zzn4& var);
    
    	static void init_ecn2(ecn2& var);
    	static void release_ecn2(ecn2& var);
    
    	static void init_epoint(epoint*& var);
    	static void release_epoint(epoint* var);
    
    public:
    	static string cout_big(big& var);
    	static void cin_big(big& var, const unsigned char* buf, int length);
    	static void cin_big(big& var, const char* buf, int length) { cin_big(var, (const unsigned char*)buf, length); }
    
    	static string cout_ecn2(ecn2& var);
    	static bool cin_ecn2_byte128(ecn2& var, const char* buf);
    
    	static string cout_epoint(epoint* var);
    	static void cin_epoint(epoint* var, const char* buf);
    
    public:
    	static bool isPointOnG1(epoint* var);
    
    private:
    	static void setFrobeniusNormCconstant();
    	static void zzn2_pow(zzn2& x, big& k, zzn2& r); // r=x^k
    	static string cout_ecn2_big(big& var);
    
    public:
    	static int getErrorNum() noexcept { return mErrorNum; }
    
    private:
    	static int mErrorNum;
    public:
    	static const int BNLEN;
    
    public:
    	static big param_a;
    	static big param_b;
    	static big param_N;
    	static big param_q;
    	static big param_t;
    	static epoint* param_P1;
    	static ecn2 param_P2;
    	static zzn2 norm_X; //Frobenius norm constant
    	static miracl* mMip;
    };
    
    #endif
    

    Parameters.cpp
    // Parameters.cpp
    #include "Parameters.h"
    #include "Errors.h"
    #include 
    
    #ifdef _WIN32
    #ifdef _DEBUG
    #pragma comment(lib, "miracld.lib")
    #else
    #pragma comment(lib, "miracl.lib")
    #endif
    #endif
    
    unsigned char SM9_q[32] = {
    	0xB6,0x40,0x00,0x00,0x02,0xA3,0xA6,0xF1,0xD6,0x03,0xAB,0x4F,0xF5,0x8E,0xC7,0x45,
    	0x21,0xF2,0x93,0x4B,0x1A,0x7A,0xEE,0xDB,0xE5,0x6F,0x9B,0x27,0xE3,0x51,0x45,0x7D
    };
    
    unsigned char SM9_N[32] = {
    	0xB6,0x40,0x00,0x00,0x02,0xA3,0xA6,0xF1,0xD6,0x03,0xAB,0x4F,0xF5,0x8E,0xC7,0x44,
    	0x49,0xF2,0x93,0x4B,0x18,0xEA,0x8B,0xEE,0xE5,0x6E,0xE1,0x9C,0xD6,0x9E,0xCF,0x25
    };
    
    unsigned char SM9_P1x[32] = {
    	0x93,0xDE,0x05,0x1D,0x62,0xBF,0x71,0x8F,0xF5,0xED,0x07,0x04,0x48,0x7D,0x01,0xD6,
    	0xE1,0xE4,0x08,0x69,0x09,0xDC,0x32,0x80,0xE8,0xC4,0xE4,0x81,0x7C,0x66,0xDD,0xDD
    };
    
    unsigned char SM9_P1y[32] = {
    	0x21,0xFE,0x8D,0xDA,0x4F,0x21,0xE6,0x07,0x63,0x10,0x65,0x12,0x5C,0x39,0x5B,0xBC,
    	0x1C,0x1C,0x00,0xCB,0xFA,0x60,0x24,0x35,0x0C,0x46,0x4C,0xD7,0x0A,0x3E,0xA6,0x16
    };
    
    unsigned char SM9_P2[128] = {
    	0x85,0xAE,0xF3,0xD0,0x78,0x64,0x0C,0x98,0x59,0x7B,0x60,0x27,0xB4,0x41,0xA0,0x1F,
    	0xF1,0xDD,0x2C,0x19,0x0F,0x5E,0x93,0xC4,0x54,0x80,0x6C,0x11,0xD8,0x80,0x61,0x41,
    	0x37,0x22,0x75,0x52,0x92,0x13,0x0B,0x08,0xD2,0xAA,0xB9,0x7F,0xD3,0x4E,0xC1,0x20,
    	0xEE,0x26,0x59,0x48,0xD1,0x9C,0x17,0xAB,0xF9,0xB7,0x21,0x3B,0xAF,0x82,0xD6,0x5B,
    	0x17,0x50,0x9B,0x09,0x2E,0x84,0x5C,0x12,0x66,0xBA,0x0D,0x26,0x2C,0xBE,0xE6,0xED,
    	0x07,0x36,0xA9,0x6F,0xA3,0x47,0xC8,0xBD,0x85,0x6D,0xC7,0x6B,0x84,0xEB,0xEB,0x96,
    	0xA7,0xCF,0x28,0xD5,0x19,0xBE,0x3D,0xA6,0x5F,0x31,0x70,0x15,0x3D,0x27,0x8F,0xF2,
    	0x47,0xEF,0xBA,0x98,0xA7,0x1A,0x08,0x11,0x62,0x15,0xBB,0xA5,0xC9,0x99,0xA7,0xC7
    };
    
    unsigned char SM9_t[32] = {
    	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x60,0x00,0x00,0x00,0x00,0x58,0xF9,0x8A
    };
    
    unsigned char SM9_a[32] = {
    	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
    };
    
    unsigned char SM9_b[32] = {
    	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x05
    };
    
    int Parameters::mErrorNum = SM9_OK;
    const int Parameters::BNLEN = 32;
    big Parameters::param_N = NULL;
    big Parameters::param_a = NULL;
    big Parameters::param_b = NULL;
    big Parameters::param_q = NULL;
    big Parameters::param_t = NULL;
    epoint* Parameters::param_P1 = NULL;
    ecn2 Parameters::param_P2;
    zzn2 Parameters::norm_X;
    miracl* Parameters::mMip = NULL;
    
    Parameters::Parameters()
    {
    	
    }
    
    Parameters::~Parameters()
    {
    
    }
    
    void Parameters::setFrobeniusNormCconstant()
    {
    	big p, zero, one, two;
    	zzn2 tmp_norm_X;
    
    	init_big(p);
    	init_big(zero);
    	init_big(one);
    	init_big(two);
    	init_zzn2(tmp_norm_X);
    
    	convert(0, zero);
    	convert(1, one);
    	convert(2, two);
    	copy(mMip->modulus, p);
    	switch( get_mip()->pmod8 )
    	{
    		case 5:
    			zzn2_from_bigs(zero, one, &tmp_norm_X);// = (sqrt(-2)^(p-1)/2
    			break;
    		case 3:
    			zzn2_from_bigs(one, one, &tmp_norm_X); // = (1+sqrt(-1))^(p-1)/2
    			break;
    		case 7:
    			zzn2_from_bigs(two, one, &tmp_norm_X);// = (2+sqrt(-1))^(p-1)/2
    		default: break;
    	}
    	decr(p, 1, p);
    	subdiv(p, 6, p);
    	zzn2_pow(tmp_norm_X, p, norm_X);
    
    	release_big(p);
    	release_big(zero);
    	release_big(one);
    	release_big(two);
    	release_zzn2(tmp_norm_X);
    }
    
    bool Parameters::init()
    {
    	bool result = false;
    	big P1_x = NULL;
    	big P1_y = NULL; 
    	BOOL br = FALSE;
    
    	mMip = mirsys(BIG_LEN, 16);
    	mMip->IOBASE = 16;
    	mMip->TWIST = MR_SEXTIC_M;
    
    	// Initialize random seed
    	std::random_device rd;
    	std::default_random_engine mGenerator;
    	std::uniform_int_distribution mDistribute(0, UINT_MAX);
    	mGenerator.seed(rd());
    	irand(mDistribute(mGenerator));
    
    	init_big(P1_x); 
    	init_big(P1_y);
    
    	init_big(param_N);
    	init_big(param_a);
    	init_big(param_b);
    	init_big(param_q);
    	init_big(param_t);
    	init_epoint(param_P1);
    	init_ecn2(param_P2);
    	init_zzn2(norm_X);
    
    	cin_big(param_N, (char*)SM9_N, sizeof(SM9_N));
    	cin_big(param_a, (char*)SM9_a, sizeof(SM9_a));
    	cin_big(param_b, (char*)SM9_b, sizeof(SM9_b));
    	cin_big(param_q, (char*)SM9_q, sizeof(SM9_q));
    	cin_big(param_t, (char*)SM9_t, sizeof(SM9_t));
    
    	//Initialize GF(q) elliptic curve, MR_PROJECTIVE specifying projective coordinates
    	ecurve_init(param_a, param_b, param_q, MR_PROJECTIVE); 
    
    	cin_big(P1_x, (char*)SM9_P1x, sizeof(SM9_P1x));
    	cin_big(P1_y, (char*)SM9_P1y, sizeof(SM9_P1y));
    
    	br = epoint_set(P1_x, P1_y, 0, param_P1);
    	result = br ? true : false;
    	if( result ) {
    		result = cin_ecn2_byte128(param_P2, (const char*)SM9_P2);
    		if( !result ) {
    			mErrorNum = SM9_ERROR_INIT_G2BASEPOINT;
    			goto END;
    		}
    	} else {
    		mErrorNum = SM9_ERROR_INIT_G1BASEPOINT;
    		goto END;
    	}
    
    	setFrobeniusNormCconstant();
    
    	result = true;
    
    END:
    	release_big(P1_x);
    	release_big(P1_y);
    
    	if( !result ) {
    		release();
    	}
    
    	return result;
    }
    
    void Parameters::release()
    {
    	mirkill(param_N);
    	mirkill(param_a);
    	mirkill(param_b);
    	mirkill(param_q);
    	mirkill(param_t);
    	release_epoint(param_P1);
    	release_ecn2(param_P2);
    	release_zzn2(norm_X);
    	mirexit();
    	mErrorNum = SM9_OK;
    }
    
    void Parameters::init_big(big& var)
    {
    	var = mirvar(0);
    }
    
    void Parameters::release_big(big& var)
    {
    	mirkill(var);
    }
    
    void Parameters::init_zzn2(zzn2& var)
    {
    	var.a = mirvar(0);
    	var.b = mirvar(0);
    }
    
    void Parameters::release_zzn2(zzn2& var)
    {
    	mirkill(var.a);
    	mirkill(var.b);
    }
    
    void Parameters::init_zzn4(zzn4& var)
    {
    	var.a.a = mirvar(0);
    	var.a.b = mirvar(0);
    	var.b.a = mirvar(0);
    	var.b.b = mirvar(0);
    	var.unitary = FALSE;
    }
    
    void Parameters::release_zzn4(zzn4& var)
    {
    	mirkill(var.a.a);
    	mirkill(var.a.b);
    	mirkill(var.b.a);
    	mirkill(var.b.b);
    }
    
    void Parameters::init_ecn2(ecn2& var)
    {
    	var.x.a = mirvar(0); var.x.b = mirvar(0); 
    	var.y.a = mirvar(0); var.y.b = mirvar(0);
    	var.z.a = mirvar(0); var.z.b = mirvar(0); 
    	var.marker = MR_EPOINT_INFINITY;
    }
    
    void Parameters::release_ecn2(ecn2& var)
    {
    	mirkill(var.x.a); mirkill(var.x.b);
    	mirkill(var.y.a); mirkill(var.y.b);
    	mirkill(var.z.a); mirkill(var.z.b);
    }
    
    void Parameters::init_epoint(epoint*& var)
    {
    	var = epoint_init();
    }
    
    void Parameters::release_epoint(epoint* var)
    {
    	epoint_free(var);
    }
    
    bool Parameters::cin_ecn2_byte128(ecn2& var, const char* buf)
    {
    	ecn2 r;
    	zzn2 x, y;
    	big a=NULL, b=NULL;
    	
    	init_ecn2(r);
    	init_zzn2(x);
    	init_zzn2(y);
    	init_big(a);
    	init_big(b);
    
    	bytes_to_big(BNLEN, (char*)buf, b);
    	bytes_to_big(BNLEN, (char*)buf + BNLEN, a);
    	zzn2_from_bigs(a, b, &x);
    	bytes_to_big(BNLEN, (char*)buf + BNLEN * 2, b);
    	bytes_to_big(BNLEN, (char*)buf + BNLEN * 3, a);
    	zzn2_from_bigs(a, b, &y);
    	BOOL ret = ecn2_set(&x, &y, &r);
    	if(ret) ecn2_copy(&r, &var);
    
    	release_ecn2(r);
    	release_zzn2(x);
    	release_zzn2(y);
    	release_big(a);
    	release_big(b);
    
    	return ret ? true : false;
    }
    
    string Parameters::cout_ecn2_big(big& var)
    {
    	big tmp = NULL;
    	init_big(tmp);
    	redc(var, tmp);
    
    	int length = tmp->len * sizeof(tmp->w);
    	char *buffer = new char[length];
    	int ret = big_to_bytes(length, tmp, buffer, TRUE);
    	string result(buffer, ret);
    
    	delete[] buffer;
    	release_big(tmp);
    	return result;
    }
    
    string Parameters::cout_ecn2(ecn2& var)
    {
    	string result;
    	result.append(cout_ecn2_big(var.x.b));
    	result.append(cout_ecn2_big(var.x.a));
    	result.append(cout_ecn2_big(var.y.b));
    	result.append(cout_ecn2_big(var.y.a));
    	return result;
    }
    
    void Parameters::cin_big(big& var, const unsigned char* buf, int length)
    {
    	bytes_to_big(length, (const char*)buf, var);
    }
    
    std::string Parameters::cout_epoint(epoint* var)
    {
    	big x = NULL;
    	big y = NULL;
    	string result;
    
    	init_big(x);
    	init_big(y);
    
    	epoint_get(var, x, y);
    
    	result.append(cout_big(x));
    	result.append(cout_big(y));
    
    	release_big(x);
    	release_big(y);
    	return result;
    }
    
    void Parameters::cin_epoint(epoint* var, const char* buf)
    {
    	big x = NULL;
    	big y = NULL;
    
    	init_big(x);
    	init_big(y);
    
    	cin_big(x, buf, BNLEN);
    	cin_big(y, buf+BNLEN, BNLEN);
    	epoint_set(x, y, 0, var);
    
    	release_big(x);
    	release_big(y);
    }
    
    string Parameters::cout_big(big& var)
    {
    	int length = var->len * sizeof(var->w);
    	char *buffer = new char[length];
    	int ret = big_to_bytes(length, var, buffer, FALSE);
    	string result(buffer, ret);
    
    	delete[] buffer;
    	return result;
    }
    
    bool Parameters::isPointOnG1(epoint* var)
    {
    	bool result = false;
    	big x = NULL;
    	big y = NULL;
    	big x_3 = NULL;
    	big tmp = NULL;
    	epoint* buf = NULL;
    
    	init_big(x);
    	init_big(y);
    	init_big(x_3);
    	init_big(tmp);
    	init_epoint(buf);
    
    	//check y^2=x^3+b
    	epoint_get(var, x, y);
    	power(x, 3, param_q, x_3); //x_3=x^3 mod p
    	multiply(x, param_a, x);
    	divide(x, param_q, tmp);
    	add(x_3, x, x); //x=x^3+ax+b
    	add(x, param_b, x);
    	divide(x, param_q, tmp); //x=x^3+ax+b mod p
    	power(y, 2, param_q, y); //y=y^2 mod p
    	if( mr_compare(x, y) != 0 )
    		return 1;
    
    	//check infinity
    	ecurve_mult(param_N, var, buf);
    	if( point_at_infinity(buf) == TRUE )
    		result = true;
    
    	release_big(x);
    	release_big(y);
    	release_big(x_3);
    	release_big(tmp);
    	release_epoint(buf);
    
    	return result;
    }
    
    void Parameters::zzn2_pow(zzn2& x, big& k, zzn2& r)
    {
    	int i, j, nb, n, nbw, nzs;
    	big zero;
    	zzn2 u2, t[16];
    
    	init_big(zero);
    	init_zzn2(u2);	
    	for( i = 0; i < 16; i++ )
    	{
    		init_zzn2(t[i]);
    	}
    
    	if( zzn2_iszero(&x) )
    	{
    		zzn2_zero(&r);
    		goto END;
    	}
    	if( size(k) == 0 )
    	{
    		zzn2_from_int(1, &r);
    		goto END;
    	}
    	if( size(k) == 1 ) {
    		zzn2_copy(&x, &r);
    		goto END;
    	}
    
    	// Prepare table for windowing
    	zzn2_mul(&x, &x, &u2);
    	zzn2_copy(&x, &t[0]);
    	for( i = 1; i < 16; i++ )
    	{
    		zzn2_mul(&t[i - 1], &u2, &t[i]);
    	}
    	// Left to right method - with windows
    	zzn2_copy(&x, &r);
    	nb = logb2(k);
    	if( nb > 1 ) for( i = nb - 2; i >= 0;)
    	{
    		//Note new parameter of window_size=5. Default to 5, but reduce to 4 (or even 3) to save RAM
    		n = mr_window(k, i, &nbw, &nzs, 5);
    		for( j = 0; j < nbw; j++ ) zzn2_mul(&r, &r, &r);
    		if( n > 0 ) zzn2_mul(&r, &t[n / 2], &r);
    		i -= nbw;
    		if( nzs )
    		{
    			for( j = 0; j < nzs; j++ ) zzn2_mul(&r, &r, &r);
    			i -= nzs;
    		}
    	}
    
    END:
    	release_big(zero);
    	release_zzn2(u2);
    	for( i = 0; i < 16; i++ ) {
    		release_zzn2(t[i]);
    	}
    }
    

    にせんけいついけいさん
    二重線形対の計算およびGT要素のオブジェクトはZZN 12クラスでSM 9アルゴリズム部分で使用され,KGC部分では使用されない.
    zzn12.h
    
    #ifndef YY_SM9_ZZN12_INCLUDE_H__
    #define YY_SM9_ZZN12_INCLUDE_H__
    
    #pragma once 
    
    #include 
    using namespace std;
    
    #ifdef __cplusplus
    extern "C" {
    #include "miracl/miracl.h"
    }
    #endif
    
    
    class ZZN12 {
    public:
    	ZZN12();
    	ZZN12(const ZZN12& var);
    	ZZN12& operator=(const ZZN12& var);
    	~ZZN12();
    
    public:
    	string toByteArray();
    
    public:
    	ZZN12 mul(ZZN12& var); // return this*var
    	ZZN12 conj();
    	ZZN12 inverse();
    	ZZN12 powq(zzn2& var);
    	ZZN12 div(ZZN12& var); // return this/y
    	ZZN12 pow(big k); // return this^k
    	bool isOrderQ(); 
    
    // pairing
    public:
    	static void q_power_frobenius(ecn2 A, zzn2 F);
    	static ZZN12 line(ecn2 A, ecn2 *C, ecn2 *B, zzn2 slope, zzn2 extra, BOOL Doubling, big Qx, big Qy);
    	static ZZN12 g(ecn2 *A, ecn2 *B, big Qx, big Qy);
    	static bool fast_pairing(ZZN12& ret, ecn2 P, big Qx, big Qy, big x, zzn2 X);
    	static bool calcRatePairing(ZZN12& ret, ecn2 P, epoint *Q, big x, zzn2 X);
    	
    
    private:
    	void init();
    	void release();
    	string cout_zzn12_big(big& var);
    
    private:
    	zzn4 a, b, c;
    	BOOL unitary; // "unitary property means that fast squaring can be used, and inversions are just conjugates
    	BOOL miller;  // "miller" property means that arithmetic on this instance can ignore multiplications
    				 // or divisions by constants - as instance will eventually be raised to (p-1).
    };
    
    #endif
    

    zzn12.cpp
    
    #include "zzn12.h"
    #include "Parameters.h"
    
    
    ZZN12::ZZN12()
    {
    	init();
    }
    
    ZZN12::ZZN12(const ZZN12& var)
    {
    	init();
    	zzn4_copy((zzn4*)&var.a, &a); 
    	zzn4_copy((zzn4*)&var.b, &b); 
    	zzn4_copy((zzn4*)&var.c, &c);
    	miller = var.miller;
    	unitary = var.unitary;
    }
    
    ZZN12& ZZN12::operator=(const ZZN12& var)
    {
    	zzn4_copy((zzn4*)&var.a, &a);
    	zzn4_copy((zzn4*)&var.b, &b);
    	zzn4_copy((zzn4*)&var.c, &c);
    	miller = var.miller;
    	unitary = var.unitary;
    	return *this;
    }
    
    ZZN12::~ZZN12()
    {
    	release();
    }
    
    
    void ZZN12::init()
    {
    	a.a.a = mirvar(0); a.a.b = mirvar(0);
    	a.b.a = mirvar(0); a.b.b = mirvar(0); a.unitary = FALSE;
    	b.a.a = mirvar(0); b.a.b = mirvar(0);
    	b.b.a = mirvar(0); b.b.b = mirvar(0); b.unitary = FALSE;
    	c.a.a = mirvar(0); c.a.b = mirvar(0);
    	c.b.a = mirvar(0); c.b.b = mirvar(0); c.unitary = FALSE;
    	unitary = FALSE; miller = FALSE;
    }
    
    void ZZN12::release()
    {
    	mirkill(a.a.a); mirkill(a.a.b);
    	mirkill(a.b.a); mirkill(a.b.b);
    	mirkill(b.a.a); mirkill(b.a.b);
    	mirkill(b.b.a); mirkill(b.b.b);
    	mirkill(c.a.a); mirkill(c.a.b);
    	mirkill(c.b.a); mirkill(c.b.b);
    }
    
    std::string ZZN12::toByteArray()
    {
    	string result;
    	result.append(cout_zzn12_big(c.b.b));
    	result.append(cout_zzn12_big(c.b.a));
    	result.append(cout_zzn12_big(c.a.b));
    	result.append(cout_zzn12_big(c.a.a));
    	result.append(cout_zzn12_big(b.b.b));
    	result.append(cout_zzn12_big(b.b.a));
    	result.append(cout_zzn12_big(b.a.b));
    	result.append(cout_zzn12_big(b.a.a));
    	result.append(cout_zzn12_big(a.b.b));
    	result.append(cout_zzn12_big(a.b.a));
    	result.append(cout_zzn12_big(a.a.b));
    	result.append(cout_zzn12_big(a.a.a));
    	return result;
    }
    
    string ZZN12::cout_zzn12_big(big& var)
    {
    	big tmp = NULL;
    	tmp = mirvar(0);
    	redc(var, tmp);
    
    	int length = tmp->len * sizeof(tmp->w);
    	char *buffer = new char[length];
    	int ret = big_to_bytes(length, tmp, buffer, TRUE);
    	string result(buffer, ret);
    
    	delete[] buffer;
    	mirkill(tmp);
    	return result;
    }
    
    ZZN12 ZZN12::mul(ZZN12& var)
    {
    	// Karatsuba
    	zzn4 Z0, Z1, Z2, Z3, T0, T1;
    	ZZN12 ret(*this);
    	BOOL zero_c, zero_b;
    
    	Parameters::init_zzn4(Z0);
    	Parameters::init_zzn4(Z1);
    	Parameters::init_zzn4(Z2);
    	Parameters::init_zzn4(Z3);
    	Parameters::init_zzn4(T0);
    	Parameters::init_zzn4(T1);
    
    	if( zzn4_compare(&a, &var.a) && zzn4_compare(&a, &var.a) && zzn4_compare(&a, &var.a) )
    	{
    		if( unitary == TRUE )
    		{
    			zzn4_copy(&a, &Z0); zzn4_mul(&a, &a, &ret.a); zzn4_copy(&ret.a, &Z3); zzn4_add(&ret.a, &ret.a, &ret.a);
    			zzn4_add(&ret.a, &Z3, &ret.a); zzn4_conj(&Z0, &Z0); zzn4_add(&Z0, &Z0, &Z0); zzn4_sub(&ret.a, &Z0, &ret.a);
    			zzn4_copy(&c, &Z1); zzn4_mul(&Z1, &Z1, &Z1); zzn4_tx(&Z1);
    			zzn4_copy(&Z1, &Z3); zzn4_add(&Z1, &Z1, &Z1); zzn4_add(&Z1, &Z3, &Z1);
    			zzn4_copy(&b, &Z2); zzn4_mul(&Z2, &Z2, &Z2);
    			zzn4_copy(&Z2, &Z3); zzn4_add(&Z2, &Z2, &Z2); zzn4_add(&Z2, &Z3, &Z2);
    			zzn4_conj(&b, &ret.b); zzn4_add(&ret.b, &ret.b, &ret.b);
    			zzn4_conj(&c, &ret.c); zzn4_add(&ret.c, &ret.c, &ret.c); zzn4_negate(&ret.c, &ret.c);
    			zzn4_add(&ret.b, &Z1, &ret.b); zzn4_add(&ret.c, &Z2, &ret.c);
    		} else
    		{
    			if( !miller )
    			{// Chung-Hasan SQR2
    				zzn4_copy(&a, &Z0); zzn4_mul(&Z0, &Z0, &Z0);
    				zzn4_mul(&b, &c, &Z1); zzn4_add(&Z1, &Z1, &Z1);
    				zzn4_copy(&c, &Z2); zzn4_mul(&Z2, &Z2, &Z2);
    				zzn4_mul(&a, &b, &Z3); zzn4_add(&Z3, &Z3, &Z3);
    				zzn4_add(&a, &b, &ret.c); zzn4_add(&ret.c, &c, &ret.c); zzn4_mul(&ret.c, &ret.c, &ret.c);
    				zzn4_tx(&Z1); zzn4_add(&Z0, &Z1, &ret.a);
    				zzn4_tx(&Z2); zzn4_add(&Z3, &Z2, &ret.b);
    				zzn4_add(&Z0, &Z1, &T0); zzn4_add(&T0, &Z2, &T0);
    				zzn4_add(&T0, &Z3, &T0); zzn4_sub(&ret.c, &T0, &ret.c);
    			} else
    			{// Chung-Hasan SQR3 - actually calculate 2x^2 !
    			 // Slightly dangerous - but works as will be raised to p^{k/2}-1
    			 // which wipes out the 2.
    				zzn4_copy(&a, &Z0); zzn4_mul(&Z0, &Z0, &Z0);// a0^2 = S0
    				zzn4_copy(&c, &Z2); zzn4_mul(&Z2, &b, &Z2); zzn4_add(&Z2, &Z2, &Z2); // 2a1.a2 = S3
    				zzn4_copy(&c, &Z3); zzn4_mul(&Z3, &Z3, &Z3);; // a2^2 = S4
    				zzn4_add(&c, &a, &ret.c); // a0+a2
    				zzn4_copy(&b, &Z1); zzn4_add(&Z1, &ret.c, &Z1); zzn4_mul(&Z1, &Z1, &Z1);// (a0+a1+a2)^2 =S1
    				zzn4_sub(&ret.c, &b, &ret.c); zzn4_mul(&ret.c, &ret.c, &ret.c);// (a0-a1+a2)^2 =S2
    				zzn4_add(&Z2, &Z2, &Z2); zzn4_add(&Z0, &Z0, &Z0); zzn4_add(&Z3, &Z3, &Z3);
    				zzn4_sub(&Z1, &ret.c, &T0); zzn4_sub(&T0, &Z2, &T0);
    				zzn4_sub(&Z1, &Z0, &T1); zzn4_sub(&T1, &Z3, &T1); zzn4_add(&ret.c, &T1, &ret.c);
    				zzn4_tx(&Z3); zzn4_add(&T0, &Z3, &ret.b);
    				zzn4_tx(&Z2); zzn4_add(&Z0, &Z2, &ret.a);
    			}
    		}
    	} else
    	{
    		// Karatsuba
    		zero_b = zzn4_iszero(&var.b);
    		zero_c = zzn4_iszero(&var.c);
    		zzn4_mul(&a, &var.a, &Z0); //9
    		if( !zero_b ) zzn4_mul(&b, &var.b, &Z2); //+6
    		zzn4_add(&a, &b, &T0);
    		zzn4_add(&var.a, &var.b, &T1);
    		zzn4_mul(&T0, &T1, &Z1); //+9
    		zzn4_sub(&Z1, &Z0, &Z1);
    		if( !zero_b ) zzn4_sub(&Z1, &Z2, &Z1);
    		zzn4_add(&b, &c, &T0);
    		zzn4_add(&var.b, &var.c, &T1);
    		zzn4_mul(&T0, &T1, &Z3);//+6
    		if( !zero_b ) zzn4_sub(&Z3, &Z2, &Z3);
    		zzn4_add(&a, &c, &T0);
    		zzn4_add(&var.a, &var.c, &T1);
    		zzn4_mul(&T0, &T1, &T0);//+9=39 for "special case"
    		if( !zero_b ) zzn4_add(&Z2, &T0, &Z2);
    		else zzn4_copy(&T0, &Z2);
    		zzn4_sub(&Z2, &Z0, &Z2);
    		zzn4_copy(&Z1, &ret.b);
    		if( !zero_c )
    		{ // exploit special form of BN curve line function
    			zzn4_mul(&c, &var.c, &T0);
    			zzn4_sub(&Z2, &T0, &Z2);
    			zzn4_sub(&Z3, &T0, &Z3); zzn4_tx(&T0);
    			zzn4_add(&ret.b, &T0, &ret.b);
    		}
    		zzn4_tx(&Z3);
    		zzn4_add(&Z0, &Z3, &ret.a);
    		zzn4_copy(&Z2, &ret.c);
    		if( !var.unitary ) ret.unitary = FALSE;
    	}
    
    	Parameters::release_zzn4(Z0);
    	Parameters::release_zzn4(Z1);
    	Parameters::release_zzn4(Z2);
    	Parameters::release_zzn4(Z3);
    	Parameters::release_zzn4(T0);
    	Parameters::release_zzn4(T1);
    
    	return ret;
    }
    
    ZZN12 ZZN12::conj()
    {
    	ZZN12 ret;
    	zzn4_conj(&a, &ret.a);
    	zzn4_conj(&b, &ret.b);
    	zzn4_negate(&ret.b, &ret.b);
    	zzn4_conj(&c, &ret.c);
    	ret.miller = miller;
    	ret.unitary = unitary;
    	return ret;
    }
    
    ZZN12 ZZN12::inverse()
    {
    	zzn4 tmp1, tmp2;
    	ZZN12 ret;
    	Parameters::init_zzn4(tmp1);
    	Parameters::init_zzn4(tmp2);
    
    	if( unitary )
    	{
    		ret =conj();
    		goto END;
    	}
    	//ret.a=a*a-tx(b*c);
    	zzn4_mul(&a, &a, &ret.a);
    	zzn4_mul(&b, &c, &ret.b); zzn4_tx(&ret.b);
    	zzn4_sub(&ret.a, &ret.b, &ret.a);
    
    	//ret.b=tx(c*c)-a*b;
    	zzn4_mul(&c, &c, &ret.c); zzn4_tx(&ret.c);
    	zzn4_mul(&a, &b, &ret.b); zzn4_sub(&ret.c, &ret.b, &ret.b);
    
    	//ret.c=b*b-a*c;
    	zzn4_mul(&b, &b, &ret.c); zzn4_mul(&a, &c, &tmp1); zzn4_sub(&ret.c, &tmp1, &ret.c);
    
    	//tmp1=tx(b*ret.c)+a*ret.a+tx(c*ret.b);
    	zzn4_mul(&b, &ret.c, &tmp1); zzn4_tx(&tmp1);
    	zzn4_mul(&a, &ret.a, &tmp2); zzn4_add(&tmp1, &tmp2, &tmp1);
    	zzn4_mul(&c, &ret.b, &tmp2); zzn4_tx(&tmp2); zzn4_add(&tmp1, &tmp2, &tmp1);
    	zzn4_inv(&tmp1);
    	zzn4_mul(&ret.a, &tmp1, &ret.a);
    	zzn4_mul(&ret.b, &tmp1, &ret.b);
    	zzn4_mul(&ret.c, &tmp1, &ret.c);
    
    END:
    	Parameters::release_zzn4(tmp1);
    	Parameters::release_zzn4(tmp2);
    	return ret;
    }
    
    ZZN12 ZZN12::powq(zzn2& var)
    {
    	ZZN12 ret(*this);
    	zzn2 X2, X3;
    	
    	Parameters::init_zzn2(X2);
    	Parameters::init_zzn2(X3);
    
    	zzn2_mul(&var, &var, &X2);
    	zzn2_mul(&X2, &var, &X3);
    	zzn4_powq(&X3, &ret.a); zzn4_powq(&X3, &ret.b); zzn4_powq(&X3, &ret.c);
    	zzn4_smul(&ret.b, &Parameters::norm_X, &ret.b);
    	zzn4_smul(&ret.c, &X2, &ret.c);
    
    	Parameters::release_zzn2(X2);
    	Parameters::release_zzn2(X3);
    	return ret;
    }
    
    ZZN12 ZZN12::div(ZZN12& var)
    {
    	ZZN12 y = var.inverse();
    	return mul(y);
    }
    
    ZZN12 ZZN12::pow(big k)
    {
    	ZZN12 ret;
    	big zero, tmp, tmp1;
    	int nb, i;
    	BOOL invert_it;
    
    	Parameters::init_big(zero);
    	Parameters::init_big(tmp);
    	Parameters::init_big(tmp1);
    
    	copy(k, tmp1);
    	invert_it = FALSE;
    	if( mr_compare(tmp1, zero) == 0 )
    	{
    		tmp = get_mip()->one;
    		zzn4_from_big(tmp, &ret.a);
    		goto END;
    	}
    	if( mr_compare(tmp1, zero) < 0 )
    	{
    		negify(tmp1, tmp1); invert_it = TRUE;
    	}
    	nb = logb2(k);
    
    	ret = *this;
    	if( nb > 1 ) for( i = nb - 2; i >= 0; i-- )
    	{
    		ret = ret.mul(ret);
    		if( mr_testbit(k, i) ) ret = ret.mul(*this);
    	}
    	if( invert_it ) ret = ret.inverse();
    
    END:
    	Parameters::release_big(zero);
    	Parameters::release_big(tmp);
    	Parameters::release_big(tmp1);
    	return ret;
    }
    
    bool ZZN12::isOrderQ()
    {
    	bool result = false;
    	ZZN12 v(*this);
    	ZZN12 w(*this);
    	big six;
    
    	Parameters::init_big(six);
    
    	convert(6, six);
    
    	w = w.powq(Parameters::norm_X);
    	v = v.pow(Parameters::param_t);
    	v = v.pow(Parameters::param_t);
    	v = v.pow(six);
    
    	if( zzn4_compare(&w.a, &v.a) && zzn4_compare(&w.a, &v.a) && zzn4_compare(&w.a, &v.a) ) {
    		result = true;
    		goto END;
    	}
    
    END:
    	Parameters::release_big(six);
    
    	return result;
    }
    
    
    void ZZN12::q_power_frobenius(ecn2 A, zzn2 F)
    {
    	// Fast multiplication of A by q (for Trace-Zero group members only)
    	zzn2 x, y, z, w, r;
    
    	Parameters::init_zzn2(x);
    	Parameters::init_zzn2(y);
    	Parameters::init_zzn2(z);
    	Parameters::init_zzn2(w);
    	Parameters::init_zzn2(r);
    
    	ecn2_get(&A, &x, &y, &z);
    	zzn2_copy(&F, &r);//r=F
    	if( get_mip()->TWIST == MR_SEXTIC_M ) zzn2_inv(&r); // could be precalculated
    	zzn2_mul(&r, &r, &w);//w=r*r
    	zzn2_conj(&x, &x); zzn2_mul(&w, &x, &x);
    	zzn2_conj(&y, &y); zzn2_mul(&w, &r, &w); zzn2_mul(&w, &y, &y);
    	zzn2_conj(&z, &z);
    	ecn2_setxyz(&x, &y, &z, &A);
    
    	Parameters::release_zzn2(x);
    	Parameters::release_zzn2(y);
    	Parameters::release_zzn2(z);
    	Parameters::release_zzn2(w);
    	Parameters::release_zzn2(r);
    }
    
    
    
    ZZN12 ZZN12::line(ecn2 A, ecn2 *C, ecn2 *B, zzn2 slope, zzn2 extra, BOOL Doubling, big Qx, big Qy)
    {
    	ZZN12 ret;
    	zzn2 X, Y, Z, Z2, U, QY, CZ;
    	big QX;
    
    	Parameters::init_big(QX);
    	Parameters::init_zzn2(X);
    	Parameters::init_zzn2(Y);
    	Parameters::init_zzn2(Z);
    	Parameters::init_zzn2(Z2);
    	Parameters::init_zzn2(U);
    	Parameters::init_zzn2(QY);
    	Parameters::init_zzn2(CZ);
    
    	ecn2_getz(C, &CZ);
    	// Thanks to A. Menezes for pointing out this optimization...
    	if( Doubling )
    	{
    		ecn2_get(&A, &X, &Y, &Z);
    		zzn2_mul(&Z, &Z, &Z2); //Z2=Z*Z
    							   //X=slope*X-extra
    		zzn2_mul(&slope, &X, &X);
    		zzn2_sub(&X, &extra, &X);
    		zzn2_mul(&CZ, &Z2, &U);
    		//(-(Z*Z*slope)*Qx);
    		nres(Qx, QX);
    		zzn2_mul(&Z2, &slope, &Y);
    		zzn2_smul(&Y, QX, &Y);
    		zzn2_negate(&Y, &Y);
    		if( get_mip()->TWIST == MR_SEXTIC_M )
    		{ // "multiplied across" by i to simplify
    			zzn2_from_big(Qy, &QY);
    			zzn2_txx(&QY);
    			zzn2_mul(&U, &QY, &QY);
    			zzn4_from_zzn2s(&QY, &X, &ret.a);
    			zzn2_copy(&Y, &(ret.c.b));
    		}
    		if( get_mip()->TWIST == MR_SEXTIC_D )
    		{
    			zzn2_smul(&U, Qy, &QY);
    			zzn4_from_zzn2s(&QY, &X, &ret.a);
    			zzn2_copy(&Y, &(ret.b.b));
    		}
    	} else
    	{ //slope*X-Y*Z
    		ecn2_getxy(B, &X, &Y);
    		zzn2_mul(&slope, &X, &X);
    		zzn2_mul(&Y, &CZ, &Y);
    		zzn2_sub(&X, &Y, &X);
    		//(-slope*Qx)
    		nres(Qx, QX);
    		zzn2_smul(&slope, QX, &Z);
    		zzn2_negate(&Z, &Z);
    		if( get_mip()->TWIST == MR_SEXTIC_M )
    		{
    			zzn2_from_big(Qy, &QY);
    			zzn2_txx(&QY);
    			zzn2_mul(&CZ, &QY, &QY);
    			zzn4_from_zzn2s(&QY, &X, &ret.a);
    			zzn2_copy(&Z, &(ret.c.b));
    		}
    		if( get_mip()->TWIST == MR_SEXTIC_D )
    		{
    			zzn2_smul(&CZ, Qy, &QY);
    			zzn4_from_zzn2s(&QY, &X, &ret.a);
    			zzn2_copy(&Z, &(ret.b.b));
    		}
    	}
    
    	Parameters::release_big(QX);
    	Parameters::release_zzn2(X);
    	Parameters::release_zzn2(Y);
    	Parameters::release_zzn2(Z);
    	Parameters::release_zzn2(Z2);
    	Parameters::release_zzn2(U);
    	Parameters::release_zzn2(QY);
    	Parameters::release_zzn2(CZ);
    	return ret;
    }
    
    ZZN12 ZZN12::g(ecn2 *A, ecn2 *B, big Qx, big Qy)
    {
    	ZZN12 ret;
    	zzn2 lam, extra;
    	ecn2 P;
    	BOOL Doubling;
    
    	Parameters::init_zzn2(lam);
    	Parameters::init_zzn2(extra);
    	Parameters::init_ecn2(P);
    
    	ecn2_copy(A, &P);
    	Doubling = ecn2_add2(B, A, &lam, &extra);
    	if( A->marker == MR_EPOINT_INFINITY )
    	{
    		zzn4_from_int(1, &ret.a);
    		ret.miller = FALSE;
    		ret.unitary = TRUE;
    	} else {
    		ret = line(P, A, B, lam, extra, Doubling, Qx, Qy);
    	}
    
    	Parameters::release_zzn2(lam);
    	Parameters::release_zzn2(extra);
    	Parameters::release_ecn2(P);
    	return ret;
    }
    
    bool ZZN12::fast_pairing(ZZN12& ret, ecn2 P, big Qx, big Qy, big x, zzn2 X)
    {
    	bool result = false;
    	int i, nb;
    	big n, zero, negify_x;
    	ecn2 A, KA;
    	ZZN12 t0, x0, x1, x2, x3, x4, x5, res, tmp;
    
    	Parameters::init_big(n);
    	Parameters::init_big(zero);
    	Parameters::init_big(negify_x);
    	Parameters::init_ecn2(A);
    	Parameters::init_ecn2(KA);
    
    	premult(x, 6, n); incr(n, 2, n);//n=(6*x+2);
    	if( mr_compare(x, zero) < 0 ) //x<0
    		negify(n, n); //n=-(6*x+2);
    	ecn2_copy(&P, &A);
    	nb = logb2(n);
    	zzn4_from_int(1, &res.a);
    	res.unitary = TRUE; //res=1
    	res.miller = TRUE; //Short Miller loop
    
    	for( i = nb - 2; i >= 0; i-- )
    	{
    		res = res.mul(res);
    		tmp = g(&A, &A, Qx, Qy);
    		res = res.mul(tmp);
    		if( mr_testbit(n, i) ) {
    			tmp = g(&A, &P, Qx, Qy);
    			res = res.mul(tmp);
    		}
    	}
    	// Combining ideas due to Longa, Aranha et al. and Naehrig
    	ecn2_copy(&P, &KA);
    	q_power_frobenius(KA, X);
    	if( mr_compare(x, zero) < 0 )
    	{
    		ecn2_negate(&A, &A);
    		res = res.conj();
    	}
    	tmp = g(&A, &KA, Qx, Qy);
    	res = res.mul(tmp);
    
    	q_power_frobenius(KA, X);
    	ecn2_negate(&KA, &KA);
    	tmp = g(&A, &KA, Qx, Qy);
    	res = res.mul(tmp);
    
    	if( zzn4_iszero(&res.a) && zzn4_iszero(&res.b) && zzn4_iszero(&res.c) )
    		goto END;
    
    	// The final exponentiation
    	res = res.conj().div(res);
    	res.miller = FALSE; res.unitary = FALSE;
    
    	res = res.powq(X).powq(X).mul(res);
    	res.miller = FALSE; res.unitary = TRUE;
    
    	// Newer new idea...
    	// See "On the final exponentiation for calculating pairings on ordinary elliptic curves"
    	// Michael Scott and Naomi Benger and Manuel Charlemagne and Luis J. Dominguez Perez and Ezekiel J. Kachisa
    	t0 = res.powq(X);
    	x0 = t0.powq(X);
    	x1 = res.mul(t0);
    
    	x0 = x0.mul(x1).powq(X);
    	x1 = res.inverse();
    
    	negify(x, negify_x); 
    	x4 = res.pow(negify_x);
    	x3 = x4.powq(X);
    	x2 = x4.pow(negify_x);
    
    	x5 = x2.inverse();
    	t0 = x2.pow(negify_x);
    
    	x2 = x2.powq(X);
    	x4 = x4.div(x2);
    	x2 = x2.powq(X);
    
    	res = t0.powq(X);
    	t0 = t0.mul(res);
    
    	t0 = t0.mul(t0).mul(x4).mul(x5);
    	res = x3.mul(x5).mul(t0);
    
    	t0 = t0.mul(x2);
    	res = res.mul(res).mul(t0);
    
    	res = res.mul(res);
    	t0 = res.mul(x1);
    
    	res = res.mul(x0);
    	t0 = t0.mul(t0).mul(res);
    
    	ret = t0;
    	result = true;
    
    END:
    	Parameters::release_big(n);
    	Parameters::release_big(zero);
    	Parameters::release_big(negify_x);
    	Parameters::release_ecn2(A);
    	Parameters::release_ecn2(KA);
    	return result;
    }
    
    bool ZZN12::calcRatePairing(ZZN12& ret, ecn2 P, epoint *Q, big x, zzn2 X)
    {
    	bool result = false;
    	big Qx, Qy;
    
    	Parameters::init_big(Qx);
    	Parameters::init_big(Qy);
    
    	ecn2_norm(&P);
    	epoint_get(Q, Qx, Qy);
    	result = fast_pairing(ret, P, Qx, Qy, x, X);
    	if(result) result = ret.isOrderQ();
    
    	Parameters::release_big(Qx);
    	Parameters::release_big(Qy);
    	return result;
    }