BN128 curve in C implementation

Doc Github Repo

Definition:

BN

Elliptic Curve

Packages

ate-pairing

Pairing

Algorithm

Frobenius

Miller’s Loop

Parameters

BN_P

BN_ZETA

 Enter Elliptic Curve Parameters i.e. a,b and p
 Enter Choice of Operation

 Enter 1 For Point Addition Operation

 Enter 2 For Scalar Multiplication Operation
1

 Enter Points P(x,y) and/or Q(x,y) to beAdded

 Resultant Point is 53245742458311851613963450768604695125869175507241963909214915539587838403999,86019658436333621282556383871045654836888327576374321095942401925234007301028

 Enter Elliptic Curve Parameters i.e. a,b and p
 Enter Choice of Operation

 Enter 1 For Point Addition Operation

 Enter 2 For Scalar Multiplication Operation
2

 Enter Points P(x,y) and/or Q(x,y) to beAdded

 Enter m to Find mP
1

 Resultant Point is 55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424

#include<stdio.h>
#include<stdlib.h>
#include<gmp.h>
 
struct Elliptic_Curve
{
	mpz_t a;
	mpz_t b;
	mpz_t p;
};
struct Point
{
	mpz_t x;
	mpz_t y;
};
 
struct Elliptic_Curve EC;
 
void Select_EC();
void Point_Addition(struct Point P,struct Point Q,struct Point* R);
void Point_Doubling(struct Point P,struct Point *R);
void Scalar_Multiplication(struct Point P,struct Point* R, mpz_t m);
 
int main(void)
{
	int choice;
	mpz_init(EC.a); mpz_init(EC.b); mpz_init(EC.p);
	Select_EC();
	printf("\n Enter Choice of Operation\n");
	printf("\n Enter 1 For Point Addition Operation\n");
	printf("\n Enter 2 For Scalar Multiplication Operation\n");
	scanf("%d",&choice);
	struct Point P,R;
	mpz_init(P.x); 
	mpz_init(P.y);
	mpz_init_set_ui(R.x,0);
	mpz_init_set_ui(R.y,0);
	printf("\n Enter Points P(x,y) and/or Q(x,y) to beAdded\n");
	mpz_init_set_str (P.x, "55066263022277343669578718895168534326250603453777594175500187360389116729240", 10);
	mpz_init_set_str (P.y, "32670510020758816978083085130507043184471273380659243275938904335757337482424", 10);

	//gmp_scanf("%Zd",&P.x);
	//gmp_scanf("%Zd",&P.y);
	if(choice==1)
	{
		struct Point Q;
		mpz_init(Q.x);
		mpz_init(Q.y);
		mpz_init_set_str (Q.x, "48840125481190545212233038815866595080052446190700286140915905752173158787212", 10);
		mpz_init_set_str (Q.y, "55258565891714835096390285893857201264507235115974921462591453996678450950230", 10);
		// gmp_scanf("%Zd",&Q.x);
		// gmp_scanf("%Zd",&Q.y);
		Point_Addition(P,Q,&R);
	}
	else
	{
		printf("\n Enter m to Find mP\n");
		mpz_t m;
		mpz_init(m);
		gmp_scanf("%Zd",&m);
		Scalar_Multiplication(P,&R,m);
	}
	gmp_printf("\n Resultant Point is %Zd,%Zd",R.x,R.y);
}
 
void Select_EC()
{
	printf("\n Enter Elliptic Curve Parameters i.e. a,b and p");
	mpz_init_set_str (EC.a, "0", 10);
	mpz_init_set_str (EC.b, "7", 10);
	mpz_init_set_str (EC.p, "115792089237316195423570985008687907853269984665640564039457584007908834671663", 10);
	//gmp_scanf("%Zd",&EC.a);
	//gmp_scanf("%Zd",&EC.b);
	//gmp_scanf("%Zd",&EC.p);
}
 
 
void Point_Addition(struct Point P,struct Point Q,struct Point* R)
{
	mpz_mod(P.x,P.x,EC.p);
	mpz_mod(P.y,P.y,EC.p);
	mpz_mod(Q.x,Q.x,EC.p);
	mpz_mod(Q.y,Q.y,EC.p);
	mpz_t temp,slope;
	mpz_init(temp);
	mpz_init_set_ui(slope,0);
	if(mpz_cmp_ui(P.x,0)==0 && mpz_cmp_ui(P.y,0)==0)
		{ mpz_set(R->x,Q.x); mpz_set(R->y,Q.y); return;}
	if(mpz_cmp_ui(Q.x,0)==0 && mpz_cmp_ui(Q.y,0)==0)
		{ mpz_set(R->x,P.x); mpz_set(R->y,P.y); return;}
	if(mpz_cmp_ui(Q.y,0)!=0)
		{mpz_sub(temp,EC.p,Q.y);mpz_mod(temp,temp,EC
			.p);}
	else
		mpz_set_ui(temp,0);
// gmp_printf("\n temp=%Zd\n",temp);
	if(mpz_cmp(P.y,temp)==0 &&
		mpz_cmp(P.x,Q.x)==0)
		{ mpz_set_ui(R->x,0); mpz_set_ui(R->y,0); return;}
	if(mpz_cmp(P.x,Q.x)==0 &&
		mpz_cmp(P.y,Q.y)==0)
	{
		Point_Doubling(P,R);
		return;
	}
	else
	{
		mpz_sub(temp,P.x,Q.x);
		mpz_mod(temp,temp,EC.p);
		mpz_invert(temp,temp,EC.p);
		mpz_sub(slope,P.y,Q.y);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,Q.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
		return;
	}
}
void Point_Doubling(struct Point P,struct Point *R)
{
	mpz_t slope,temp;
	mpz_init(temp);
	mpz_init(slope);
	if(mpz_cmp_ui(P.y,0)!=0)
	{
		mpz_mul_ui(temp,P.y,2);
		mpz_invert(temp,temp,EC.p);
		mpz_mul(slope,P.x,P.x);
		mpz_mul_ui(slope,slope,3);
		mpz_add(slope,slope,EC.a);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,P.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
	}
	else
	{
		mpz_set_ui(R->x,0);
		mpz_set_ui(R->y,0);
	}
}
void Scalar_Multiplication(struct Point P,struct Point* R, mpz_t m)
{
	struct Point Q,T;
	mpz_init(Q.x); mpz_init(Q.y);
	mpz_init(T.x); mpz_init(T.y);
	long no_of_bits,loop;
	no_of_bits=mpz_sizeinbase(m,2);
	mpz_set_ui(R->x,0);mpz_set_ui(R->y,0);
	if(mpz_cmp_ui(m,0)==0)
		return;
	mpz_set(Q.x,P.x);
	mpz_set(Q.y,P.y);
	if(mpz_tstbit(m,0)==1)
		{mpz_set(R->x,P.x);mpz_set(R->y,P.y);}
	for(loop=1;loop<no_of_bits;loop++)
	{
		mpz_set_ui(T.x,0);
		mpz_set_ui(T.y,0);
		Point_Doubling(Q,&T);
		gmp_printf("\n %Zd %Zd %Zd %Zd ",Q.x,Q.y,T.x,T.y);
		mpz_set(Q.x,T.x);
		mpz_set(Q.y,T.y);
		mpz_set(T.x,R->x);
		mpz_set(T.y,R->y);
		if(mpz_tstbit(m,loop))
			Point_Addition(T,Q,R);
	}
}

// int contract_main(int argc, char **argv){
// 	mpz_init(EC.a); mpz_init(EC.b); mpz_init(EC.p);
// 	mpz_init_set_str (EC.a, "0", 10);
// 	mpz_init_set_str (EC.b, "7", 10);
// 	mpz_init_set_str (EC.p, "115792089237316195423570985008687907853269984665640564039457584007908834671663", 10);
// 	struct Point P,R;
// 	mpz_init(P.x); 
// 	mpz_init(P.y);
// 	mpz_init_set_ui(R.x,0);
// 	mpz_init_set_ui(R.y,0);
// 	mpz_init_set_str (P.x, "55066263022277343669578718895168534326250603453777594175500187360389116729240", 10);
// 	mpz_init_set_str (P.y, "32670510020758816978083085130507043184471273380659243275938904335757337482424", 10);

// 	//gmp_scanf("%Zd",&P.x);
// 	//gmp_scanf("%Zd",&P.y);

// 	struct Point Q;
// 	mpz_init(Q.x);
// 	mpz_init(Q.y);
// 	mpz_init_set_str (Q.x, "48840125481190545212233038815866595080052446190700286140915905752173158787212", 10);
// 	mpz_init_set_str (Q.y, "55258565891714835096390285893857201264507235115974921462591453996678450950230", 10);
// 	//gmp_scanf("%Zd",&Q.x);
// 	//gmp_scanf("%Zd",&Q.y);
// 	Point_Addition(P,Q,&R);
// 	gmp_printf("\n Resultant Point is %Zd,%Zd",R.x,R.y);
// 	//printf("%d, %d",R.x,R.y);

// 	return 0;
// }

<gmp> on linux

  1. download from gmplib
  2. download lzip:
    sudo apt install lzip
  3. Conver gmp-6.1.2.tar.lz to gmp-6.1.2.tar
    sudo lzip -d gmp-6.1.2.tar.lz
  4. Unzip gmp-6.1.2.tar
    tar -xvf gmp-6.1.2.tar
  5. Install GMP
    cd gmp-6.1.2/
sudo ./configure
sudo make
sudo make check
sudo make install

    <gmp> tutorial

    Headers and Libraries

    • header: #include <gmp.h>
    • C compile: gcc code.c -lgmp
    • C++ compile g++ code.cc -lgmpxx -lgmp
    • 若GMP被安裝在非標準的地方，則用-I及-L使編譯時指向正確的資料夾

      Nomenclature and Types

    • mpz_t: 一般整數(Integers)
    • 函數開頭為 mpz_ - mpq_t: 有理數(Rational number)
    • 函數開頭為 mpq_ - mpf_t: 浮點數(Floating point number)
    • 函數開頭為 mpf_

      Variable Conventions

      - input和output可以吃相同的變數
    • 如整數乘法mpz_mul，若想要對x平方 則用mpz_mul(x,x,x); - 在assign到一個GMP變數前，必須呼叫一個初始化函數 在用完該變數後，要呼叫清除函數
    • 範例：
       mpz_t n;
 mpz_init(n); // Initializing
 mpz_mul(n,...);
 mpz_clear(n); //clearing

      Parameter Conventions

      - 是call-by-reference
- 函數呼叫只返回座標，所以用法是將回傳結果`result`放入函數參數中
- 範例： ```cpp= void foo(mpz_t result, const mpz_t param, unsigned long n){  mpz_mul_ui(result, param, n); } int main(void){  mpz_t r,n;  // init  mpz_init(r);  mpz_init_set_str (n,"123456",0);  // call function foo  foo(r,n,20L);  // print  gmp_printf("%Zd\n",r);  return 0; } ``` #### Demonstration programs
  6. demos/ 資料夾中有範例程式
    cd demos/
  7. make
    sudo make pexpr
  8. 執行
    ./pexpr 68^975+10

Integer functions