Summer Study Technical Report

Rahman Mohammad Shahriar

Summer Study, 2007

1 Signed Binary Representations Revisited

1.1 Introduction

In this paper a new signed representation of integers named Mutual Opposite Form(MOF) is proposed. It satisfies two conditions: 1. Adjacent non-zero bits habe different signs. 2. The most and least nonzero bits are 1and ¯1 respectively given that not all bits are zero. Any n-bit binary string can be uniquely represented by (n − 1)-bit MOF. Converting Binary String to MOF: The n-bit binary string d can be converted to a signed binary string μ which computes a bitwise subtraction of d. To be precise, μ_{i} = d_{i−1} − d_{i} for i = 1, 2, ..., n − 1 and μ_{0} = −d_{0}, μ_{n} = d_{n−1}. So this method operates from the MSB i.e. left-to-right.

1.2 Window methods on MOF

Right-to-Left case:wNAF: To generate the complete table for width w, all the conversions for of length l=2,3,...,w are considered.

The window is filled with leading zeros if l < w. A carry free wNAF can be generated beginning from the LSB. Left-to-Right case:wMOF:

This the proposed scheme of this paper.To generate the complete table for width w, all convertions

of length l = 2, 3, ...w are considered. But when l < w holds, the window is filled with closing zeros. wMOF must have some properties:

1. Most significant non-zero bit should be positive.

2. Except the right most non-zero bit x, all are adjoined by w − 1 zeros. If 2^{k−1} < |x| < 2^{k} for 2 ≤ k ≤ w − 1 then the pattern is 0...0x0..0 where the leading zeros=k,closing zeros=w − k − 1. If |x| = 1, the pattern is either x0...0 or 0x0..0. In this case, the next lower non-zero digit has the opposite and equal signs respectively. Ofcourse the last non-zero digit cannot be following any other non-zero digit.

3. Each non-zero digit is odd and less than 2^{w−1}.

1.3 Implementation details for the proposed scheme, w > 2

The conversion method uses table look-ups. Entries starting with 0,0 or 1,1 are not converted. c is the decimal representation of μ of the form c = γ × 2^{ξ} Initially ξ is assigned zero and c is divided until it is odd.If c is even, ξ inincremented by 1. At the end c is assigned to γ . So the resulting table has 2^{w} rows with ξ in (0, 1, ..., w − 1) and γ is in (±1, ±3, .., ±(2^{w−1} − 1)). So the pre-computed table is created in this step. For the scalar multiplication, this pre-computed table is used. After getting γ and ξ , w ECDBL and one ECADD operations have to be done. Here, ξ features the number of doublings before addition. If the doubling result is stated as Q, the pre-computed input value of point P is then added. In the last step, if the result Q has its last bit zero, P is subtracted from Q;hence getting the final result.

2 Efficient Elliptic Curve Exponentiations using mixed coordinates

2.1 Introduction

In this paper, a new idea for elliptic curve exponentiations is proposed. A new coordinate system named Modified Jacobian coordinate has also been introduced. The existing coordinate systems i.e. affine, projective, Jacobian, Chudnovsky jacobian along with the newly introduced one cannot guarantee best performance both for addition and doubling. The mixed use of these can show a significant improvement by dividing the elliptic curve exponentiations into three parts and choosing the optimal solutions for each of them. Modified Jacobian coordinates This system represents a point into a quad (X, Y, Z, aZ^{4}) and is denoted by J^{m}. And if P = (X_{1}, Y_{1}, Z_{1}, aZ_{1}^{2}), Q = (X_{2}, Y_{2}, Z_{2}, aZ_{2}^{4}) then P + Q = R = (X_{3}, Y_{3}, Z_{3}, aZ_{3}^{2}). ⋄ Curve addition formula (P ≠ ±Q) (X_{3} = −H^{3} − 2U_{1}H^{2} + r^{2}, Y_{3} = −S_{1}H^{3} + r(U_{1}H^{2} − X_{3}), Z_{3} = Z_{1}Z_{2}H, aZ_{3}^{4} = aZ_{3}^{4}) where (U_{1} = X_{1}Z_{2}^{2}, U_{2} = X_{2}Z_{1}^{2}, S_{1} = Y_{1}Z_{2}^{3}, S_{2} = Y_{2}Z_{!}^{3}, H = U_{2} − U_{1}, r = S_{2} − S_{1}) ⋄ Curve doubling formula (R = 2P) (X_{3} = T, Y_{3} = M(S − T) − U, Z_{3} = 2Y_{1}Z_{1}, aZ_{3}^{4} = 2U(aZ_{1}^{4})) where (S = 4X_{1}Y_{1}^{2}, U = 8Y_{1}^{4}, M = 3X_{1}^{2} + (aZ_{1}^{4}), T = −2S + M^{2}) And this system is faster than the earlier systems in case of doublings.

2.2 Use of mixed coordinates

In this method, the whole exponentiation part is divided into three; namely C^{1}, C^{2}, C^{3}. C^{1} is used for repeated main doublings, C^{2} for the result of final doubling and C^{3} for the pre-computed points. As J^{m} is the fastest of all doublings, this is assigned to C^{1}. When the inversion(I) is faster than multiplication(M), affine coordinate is used as C^{3}, else Chudnovsky jacobian is used. When Affine coordinate is used, C^{2} is determined given that t(2J^{m} = C^{2}) + t(C^{2} + A = J^{m}) is the smallest possible and in this case, J is the suitable one. Montgomery’s trick is a good option used here to compute ((2P), (3P, 4P), ..., ((2^{w−2} + 1)P, .., (2^{w−2} − 1)P, 2^{w−1}P)) and so on. In the final doubling stage t(2J^{m} = J) is used. When Chudnovsky Jacobian is used, C^{2} is determined given that t(2J^{m} = C^{2}) + t(C^{2} + J^{c} = J^{m}) is the smallest and J is chosen as C^{2}. In the final stage of addition, (t(J + J^{c} = J)) is used when k_{0} = 0; (t = (2J^{m} = J)) is used otherwise. Finally, time comparisions depending on the I/M ratio is being showed for k=160, 192 and 224 bits.

3 Signed Binary Representations Revisited

3.1 Introduction

Here we try to develop an algorithm that uses Left-to-Right window method under the mixed coordinate. For the main doubling: modified-Jacobian (J^{m}), final doubling: Jacobian (J) and for the precomputed table: Affine (A) coordinate systems are used.

3.2 Algorithm

At first, we get the precomputed table for a width w. This table computes γ and ξ which are needed for the equation c = γ ∗ 2^{ξ} where c is the decimal representation of the MOF (μ).

Algorithm 1. Table computation with Width w input width w output arrays γ_{0...tw} and ξ_{0...tw} where tw = 2^{w} − 1. 1: For d ← 2^{w−1} to 3 ∗ 2^{w−1} − 1 do the following 1.1 c ← (d&(2^{w} − 1)) − (d 1) 1.2 ξ_{d−2^{w−1}} ← 0 1.3 While (c&1) = 0 do the following 1.3.1 ξ_{d−2^{w−1}} ← ξ_{d−2^{w−1}} + 1 1.3.2 c ← c 1 1.4 γ_{d−2^{w−1}} ← c 2: return γ_{0...tw} and ξ_{0...tw} Now we use the mixed coordinate system in scalar multiplication. The values of γ_{0...tw} and ξ_{0...tw} that we got from Algorithm1 is used here as input along with the non-zero n-bit binary string d and a point P in affine coordinate.

Algorithm 2. Scalar multiplication algorithm with width w using mixed coordinate input a non-zero n-bit binary string d, a point P in affine coordinate and the multiple of the point P, γ_{0...tw} and ξ_{0...tw}, the precomputed table. output scalar multiplication dP. 1: i ← n 2: Q ← 0 3: While i ≥ 1 do the following 3.1 if (d_{i}XORd_{i−1}) = 0, then do the following 3.1.1 Q ← ECDBL(Q) 3.1.2 i ← i − 1 3.2 else do the following 3.2.1 index ← ((d (i − w))&(2^{w+1} − 1)) − 2^{w−1} 3.2.2 For j = 1 to w − ξ_{index−1} do the following

1. Q ← ECDBL(Q)

2. i ← i − 1

3.2.3 while j = w − ξ_{index}

1. Q ← ECDBL(Q) 3.2.4 Q ← ECADD(Q, γ_{i}ndexP) 4: return Q Step 1 initializes the loop variable i to the bit-length n. The second step initializes the result variable Q to 0 to avoid the special case in first digit. While i is greater or equal to 1, the loop is executed. The condition in step 3.1 checks whether the two adjacent bits equals or not. If they have the same value, Q is doubled and i is decreased. This doubling is done in J^{m} coordinate. If the else part in step 3.2 is executed, a table index is created first. After this we get the γ and ξ. In the whole else part, wECDBL and one ECADD is being done. In step 3.2.2, Q is doubled w − ξ_{index−1} times. This doubling loop is done in J^{m} coordinate system. In the last step of doubling i.e. 3.2.3 Jacobian coordinate system J is used. In the next step ECADD is done with the Q and precomputed multiple of the point P which is the input in affine coordinate. Step 4 returns the result Q

4 Addition and doubling in Jacobian coordinate system

4.1 Introduction

Here we make addition and multiplication in Jacobian coordinate system using java. The program can calculate addition and doubling for any arbitrarily large integer. The resultant we get is also in Jacobian coordinate. We also calculate the execution time.

4.2 Formulae

Jacobian coordinate addition Now we consider the formula for point addition. We assume the ponits are P (X_{1}, Y_{1}, Z_{1}) and

Q(X_{2}, Y_{2}, Z_{2}) and P ≠ ±Q. So, we get P + Q = R = (X_{3}, Y_{3}, Z_{3}).

X_{3} = −H^{3} − 2U_{1}H^{2} + r^{2}, Y_{3} = −S_{1}H^{3} + r(U_{1}H^{2} − X_{3}), Z_{3} = Z_{1}Z_{2}H where U_{1} = X_{1}Z_{2}^{2}, U_{2} = X_{2}Z_{1}^{2}, S_{1} = Y_{1}Z_{2}^{3}, S_{2} = Y_{2}Z_{1}^{3}, H = U_{2} − U_{1}, r = S_{2} − S_{1};

Jacobian coordinate doubling This is the point doubling formula where R = 2P.

X_{3} = T, Y_{3} = −8Y_{1}^{4} + M(S − T), Z_{3} = 2Y_{1}Z_{1} where S = 4X_{1}Y_{1}^{2}, M = 3X_{1}^{2} + aZ_{1}^{4}, T = −2S + M^{2}.

4.3 Code

Addition in Jacobian coordinate

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger;

public class ecadd { public static void main(String[] args) throws IOException {

String str,str1;

System.out.println(”———————start—————”);

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));//input string

BigInteger U1 = new BigInteger(”1”); BigInteger U2 = new BigInteger(”1”); BigInteger S1 = new BigInteger(”1”); BigInteger S2 = new BigInteger(”1”); BigInteger H = new BigInteger(”1”); BigInteger r = new BigInteger(”1”); BigInteger S = new BigInteger(”1”); BigInteger M = new BigInteger(”1”); BigInteger T = new BigInteger(”1”);

BigInteger X3 = new BigInteger(”1”); BigInteger Y3 = new BigInteger(”1”); BigInteger Z3 = new BigInteger(”1”);

long start=1; long end=2; long time=0;

System.out.println(”Press enter after each Coordinate.”);

System.out.print(”Point P: X1= ”); String strX1 = bf.readLine();

System.out.print(”Point P: Y1= ”); String strY1 = bf.readLine();

System.out.print(”Point P: Z1= ”); String strZ1 = bf.readLine(); System.out.print(” Point Q: X2= ”); String strX2 = bf.readLine();

System.out.print(”Point Q: Y2= ”); String strY2 = bf.readLine();

System.out.print(”Point Q: Z2= ”); String strZ2 = bf.readLine();

//—————STARTING TIMER——————————- start = System.nanoTime();

BigInteger X1 = new BigInteger(strX1); BigInteger Y1 = new BigInteger(strY1); BigInteger Z1 = new BigInteger(strZ1); BigInteger X2 = new BigInteger(strX2); BigInteger Y2 = new BigInteger(strY2); BigInteger Z2 = new BigInteger(strZ2);

BigInteger temp1 = new BigInteger(”1”); BigInteger temp2 = new BigInteger(”1”); BigInteger temp3 = new BigInteger(”1”);

U1=X1.multiply(Z2.pow(2)); U2=X2.multiply(Z1.pow(2)); S1=Y1.multiply(Z2.pow(3)); S2=Y2.multiply(Z1.pow(3)); H=U2.subtract(U1); r=S2.subtract(S1);

//———X3—— temp1=(H.pow(3)).negate();

temp2=U1.multiply(BigInteger.valueOf(2)).multiply(H.pow(2));

X3=(temp1.subtract(temp2)).add(r.pow(2));

//———-Y3—–

temp1=(S1.multiply(H.pow(3))).negate();

temp2= r.multiply(U1.multiply(H.pow(2)).subtract(X3)); Y3=temp1.add(temp2);

//———-Z3—–

Z3=Z1.multiply(Z2.multiply(H));

//——————–ENDING TIMER—————————- end = System.nanoTime();

time=end-start;

System.out.println(” X3=” + X3.toString() ); System.out.println(”Y3=” + Y3.toString() ); System.out.println(” Z3=” + Z3.toString() );

System.out.println(” Time: Start (nanoseconds) =” + start); System.out.println(” End (nanoseconds) =” + end);

System.out.println(” Start-end=” + time); }

}

Doubling in Jacobian coordinate

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger;

public class ecdbl {

public static void main(String[] args) throws IOException {

String str,str1;

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

BigInteger S = new BigInteger(”1”); BigInteger M = new BigInteger(”1”); BigInteger T = new BigInteger(”1”);

BigInteger X3 = new BigInteger(”1”); BigInteger Y3 = new BigInteger(”1”); BigInteger Z3 = new BigInteger(”1”);

System.out.println(”Press enter after each Coordinate.”);

System.out.print(”Point P: X1= ”); String strX1 = bf.readLine();

System.out.print(”Point P: Y1= ”); String strY1 = bf.readLine();

System.out.print(”Point P: Z1= ”); String strZ1 = bf.readLine();

System.out.print(” a= ”); String stra = bf.readLine();

BigInteger X1 = new BigInteger(strX1); BigInteger Y1 = new BigInteger(strY1); BigInteger Z1 = new BigInteger(strZ1); BigInteger a = new BigInteger(stra);

BigInteger temp1 = new BigInteger(”1”); BigInteger temp2 = new BigInteger(”1”); long start=1; long end=2; long time=0;

//————STARTING TIMER——————————- start = System.nanoTime();

S=X1.multiply(BigInteger.valueOf(4)).multiply(Y1.pow(2));

temp1=(X1.pow(2)).multiply(BigInteger.valueOf(3)); temp2=(Z1.pow(4)).multiply(a);

M=temp1.add(temp2);

temp1= (S.multiply(BigInteger.valueOf(2))).negate(); T=temp1.add(M.pow(2));

X3=T;

temp1=((Y1.pow(4)).multiply(BigInteger.valueOf(8))).negate(); temp2=(S.subtract(T)).multiply(M); Y3=temp1.add(temp2);

Z3=(Y1.multiply(Z1)).multiply(BigInteger.valueOf(2));

//————ENDING TIMER—————————- end = System.nanoTime(); time=end-start;

System.out.println(”X3=” + X3.toString() ); System.out.println(”Y3=” + Y3.toString() ); System.out.println(”Z3=” + Z3.toString() );

System.out.println(”Time: Start (nanoseconds) =” + start); System.out.println(” End (nanoseconds) =” + end);

System.out.println(” Start-end=” + time);

}

}

4.4 Discussion

We run both the code segments in a DELL workstation having Intel(R) Xeon CPU 2.40GHz and 1GB RAM. The operating time was measured in nanoseconds. We run the programs for P = (1,2,1) and Q = (2,3,1). The resultant R came as correct which were cross-checked by the similar programs in Mathematica. As BigInteger class has been used, the input points can have any number of digits.

5 Elliptic curve Addition, Doubling and Scalar Multiplications in Jacobian coordinate system

5.1 Introduction

Here we make 192-bit Elliptic curve addition and multiplication in Jacobian coordinate system in java. We also make an Elliptic curve scalar multiplication using binary method. The programs can calculate addition, doubling and multiplication for a maximum of 192-bit Elliptic curve. The resultant we get is also in Jacobian coordinate. We also calculate the total execution time of addition, doubling and average time of scalar multiplication for 1000 and 5000 times.

5.2 Formulae

Jacobian coordinate addition Now we consider the formula for point addition. We assume the ponits are P (X_{1}, Y_{1}, Z_{1}) and

Q(X_{2}, Y_{2}, Z_{2}) and P ≠ ±Q. So, we get P + Q = R = (X_{3}, Y_{3}, Z_{3}).

Calculation Operation
H^{2} Sq
H ∗ H Mul, Mod
U_{1}H^{2} Mul, Mod
r^{2} Sq
X_{3} = −H^{3} − 2U_{1}H^{2} + r^{2} Mod
S_{1}H^{3} Mul, Mod
r(U_{1}H^{2} − X_{3}) Mul
Y_{3} = −S_{1}H^{3} + r(U_{1}H^{2} − X_{3}) Mod
Z_{3} = Z_{1}Z_{2}H Mod

X_{3} = −H^{3} − 2U_{1}H^{2} + r^{2}, Y_{3} = −S_{1}H^{3} + r(U_{1}H^{2} − X_{3}), Z_{3} = Z_{1}Z_{2}H

where U_{1} = X_{1}Z_{2}^{2}, U_{2} = X_{2}Z_{1}^{2}, S_{1} = Y_{1}Z_{2}^{3}, S_{2} = Y_{2}Z_{1}^{3}, H = U_{2} − U_{1}, r = S_{2} − S_{1};

The table above shows the steps where Multiplication, Squaring and Mod are done.

Jacobian coordinate doubling This is the point doubling formula where R = 2P.

X_{3} = T, Y_{3} = −8Y_{1}^{4} + M(S − T), Z_{3} = 2Y_{1}Z_{1} where S = 4X_{1}Y_{1}^{2}, M = 3X_{1}^{2} + aZ_{1}^{4}, T = −2S + M^{2}.

The table below shows the steps where Multiplication, Squaring and Mod are done.

Calculation Operation
Y_{1}^{2} Sq
X_{1}Y_{1}^{2} Mul
4X_{1}Y_{1}^{2} Mod
X_{1}^{2} Sq
Z_{1}^{4} Mul, Sq
3X_{1}^{2} + aZ_{1}^{4} Mod
M^{2} Sq
X_{3} = T Mod
M(S − T) Mul
Y_{1}^{4} Mul
Y_{3} = −8Y_{1}^{4} + M(S − T) Mod
2Y_{1}Z_{1} Mul
Z_{3} = 2Y_{1}Z_{1} Mod

Scalar multiplication The process of scalar multiplication is as follows:

kP = ∑_{j=0}^{l_{1}−1} c_{j}2^{j} (P)

= 2(...(2(2(c_{l_{1}−1}P) + c_{l_{1}−2}P))... + c_{1}P) + c_{0}P

5.3 Code

Java Mul operation

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger; public class testM { public static void main(String[] args)throws IOException { BufferedReader bf = new BufferedReader(newInputStreamReader(System.in)); BigInteger out; long start=0; long end=0; long time=0; long count; System.out.print(”Number of Loops = ”); String strcount = bf.readLine(); / /——————–MULTIPLICATION——————- BigInteger A=new BigInteger(”fff82347293847234872346293847239487234872394873f”,16); BigInteger B=new BigInteger(”163987239238749827349872498732498732488479283478”,16); for (count=1000000;count!=0;count− − ) { start = System.currentTimeMillis(); out=A.multiply(B); end = System.currentTimeMillis(); time=time+end-start; } System.out.println(”Mul execution time (milisecond) =” + time); } }

Java Square operation

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger; public class testS { public static void main(String[] args) { int i=0; BigInteger out; long start=0; long end=0; long time=0; long count;

BigInteger A=new BigInteger(”fff82347293847234872346293847239487234872394873f”,16);

//——————–SQURE——————-

for (count=1000000;count!=0;count− −) {

start = System.currentTimeMillis(); out=A.pow(2); end = System.currentTimeMillis(); time=time+end-start;

} System.out.println(”Squre execution time (milisecond) =” + time);

}

}

Java MOD operation

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger;

public class testMOD {

public static void main(String[] args) {

BigInteger out;

long start=0; long end=0; long time=0; long count;

BigInteger A=new BigInteger(”fff82347293847234872346293847239487234872394873ffff82347293847234872346293847239487234872394873f”,16); BigInteger B=new BigInteger(”163987239238749827349872498732498732488479283478”,16);

//——————–MOD——————-

for (count=1000000;count!=0;count− −) { start = System.currentTimeMillis(); out=A.mod(B); end = System.currentTimeMillis(); time=time+end-start; } System.out.println(”Java mod execution time (milisecond) =” + time);

}

}

Elliptic curve Addition in Jacobian coordinate

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger;

public class ecadd252 {

public static void main(String[] args) throws IOException {

String str,str1;

BigInteger H ; BigInteger r ; BigInteger S ; BigInteger M ; BigInteger T ;

BigInteger X3 ; BigInteger Y3 ; BigInteger Z3 ;

BigInteger base = new BigInteger(”2”);

long start=1; long end=2; long time=0; long count;

BigInteger p2; BigInteger p1=new BigInteger(”163987239238749827349872498732498732488479283478”,16); p2 =(p1.subtract(base.pow(64))).subtract(BigInteger.valueOf(1)); / ∗ P = 2^{192} − 2^{64} − 1 ∗ /

BigInteger X1 = new BigInteger(”fff82347293847234872346293847239487234872394873f”,16); BigInteger Y1 = new BigInteger(”fffff7123687234687236487324cfb1231ffffffffffffff”,16); BigInteger Z1 = new BigInteger(”1”,16);

BigInteger X2 = new BigInteger(”ffffffffffff876871381391312313122311231fffffffff”,16); BigInteger Y2 = new BigInteger(”98173987139871398719837183319827391cdf123213fc12”,16); BigInteger Z2 = new BigInteger(”1”,16);

BigInteger temp1 ; BigInteger temp2 ; BigInteger temp3 ; BigInteger temp4 ; BigInteger tempH2; BigInteger tempH3; BigInteger tempH2U1;

//—————STARTING TIMER——————————-

start = System.currentTimeMillis();

for (count=1000000;count!=0;count− −) // loop runs for 10^{6} times {

H=X2.subtract(X1); r=Y2.subtract(Y1);

//———X3—— tempH2=H.pow(2); // tempH_{2} = H^{2} tempH3=tempH2.multiply(H); // tempH_{3} = H^{3} tempH3=tempH3.mod(p1); tempH2U1=tempH2.multiply(X1); //tempH_{2}U_{1} = U_{1} ∗ H^{2} tempH2U1=tempH2U1.mod(p1); temp1=tempH3.negate(); // temp1= −H^{3} temp2=tempH2U1.multiply(BigInteger.valueOf(2)); // temp2= 2 ∗ U_{1} ∗ H^{2} temp2=temp2.negate(); // temp2= −2 ∗ U_{1} ∗ H^{2} temp3=r.pow(2); //temp3= r^{2} X3=(temp1.add(temp2)).add(temp3).mod(p2); //X_{3}= temp1+temp2+temp3= −H^{3}−2∗U_{1}∗H^{2}+r^{2} //———-Y3—– temp1=tempH2U1.subtract(X3); //temp1=U_{1} ∗ H^{2} − X_{3} temp1=temp1.multiply(r); //temp1=r(U_{1} ∗ H^{2} − X_{3}) temp2=tempH3.multiply(Y1); // temp2=S_{1} ∗ H^{3} temp2=temp2.mod(p1); Y3=(temp1.subtract(temp2)).mod(p2); // Y_{3}= temp1-temp2= −S_{1} ∗ H^{3} + r(U_{1} ∗ H^{2} − X_{3}) Z3=H.mod(p2); X1=X3; Y1=Y3; Z1=BigInteger.ONE; // Taking Z_{1}=1 } // end for loop //——————–ENDING TIMER—————————- end = System.currentTimeMillis(); time=end-start; System.out.println(”Total time(milisecond)=” + time); } }

Elliptic curve Doubling in Jacobian coordinate

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.math.BigInteger; public class ecdbl82 { public static void main(String[] args) throws IOException { String str,str1; BigInteger S ; BigInteger M ; BigInteger T ; BigInteger X3 ; BigInteger Y3 ; BigInteger Z3 ; long start; long end; long time=0; long count; BigInteger X1 = new BigInteger(”fff82347293847234872346293847239487234872394873f”,16); BigInteger Y1 = new BigInteger(”ffffffff123472983429387498237498237492738492834f”,16); BigInteger Z1 = new BigInteger(”fffffffff28364283746827364872364872364234623ffff”,16); BigInteger a=new BigInteger(”-3”); BigInteger temp1; BigInteger temp2; BigInteger tempY2; BigInteger p2; BigInteger p1=new BigInteger(”163987239238749827349872498732498732488479283478”,16); p2 =(p1.subtract(base.pow(64))).subtract(BigInteger.valueOf(1)); //P = 2^{192} − 2^{64} − 1 //————STARTING TIMER——————————- start = System.currentTimeMillis(); for (count=1000000;count!=0;count− −) { tempY2=Y1.pow(2); //tempY_{2} = Y^{2} S=((tempY2.multiply(X1)).multiply(BigInteger.valueOf(4))).mod(p1); // S= 4 ∗ X_{1} ∗ Y_{1}^{2} temp1=(X1.pow(2)).multiply(BigInteger.valueOf(3)); // temp1=3 ∗ X_{1}^{2} temp2=Z1.pow(2); temp2=(a.multiply(temp2)).multiply(temp2); // temp2=a ∗ Z_{1}^{4} M=(temp1.add(temp2)).mod(p1); // M= temp1+temp2=3 ∗ X_{1}^{2} + a ∗ Z_{1}^{4} temp2=S.multiply(BigInteger.valueOf(2)); // temp2=2 ∗ S T=(M.pow(2)).subtract(temp2); // T= temp1-temp2= −2 ∗ S + M^{2} //——————–X3———- X3=T.mod(p2); //———————Y3———- temp1=M.multiply(S.subtract(T)); //temp1=M(S − T) temp2=(tempY2.multiply(tempY2)).multiply(BigInteger.valueOf(8)); //temp2=8 ∗ Y_{1}^{4} Y3=(temp1.subtract(temp2)).mod(p2); // Y3= temp1-temp2= −8 ∗ Y_{1}^{4} + M(S − T) //———————-Z3————- Z3=((Y1.multiply(Z1)).multiply(BigInteger.valueOf(2))).mod(p2); // Z3=2 ∗ Y_{1} ∗ Z_{1} X1=X3; Y1=Y3; Z1=Z3;

} //end for loop

//————ENDING TIMER—————————-

end = System.currentTimeMillis(); time=end-start;

System.out.println(”Total time for whole program (milisecond)=” + time);

}

}

5.4 Discussion

We consider the Elliptic Curve as follows: E_{p} : y^{2} = x^{3} − 3x + b where P = 2^{192} − 2^{64} − 1 As BigInteger class has been used, the input points can have any number of digits. We computed for 192 digits. For all the inner multiplications, modulus of 2^{1}92 were taken. And for the final result, we took the modulus of 2^{192} − 2^{64} − 1. We use P = (1, 2, 1), Q = (2, 3, 1) as the points in Elliptic Curve and a = −3 in the experiments. In case of Scalar Multiplication, we set Seed=13 to get the random values of K (192bit). But to make sure getting the random numbers precisely, we add the systemtime with the seed value. We run all the code segments in a DELL workstation having Intel(R) Xeon CPU 2.40GHz and 1GB RAM. The operating time was measured in milliseconds.

Results of Scalar Multiplication We make the scalar multiplication under Binary Method. We execute the method for 1000 times to get the values. So, random k has different values after each loop. In other word, we use 1000 different random values of k.

To set the random values of k, we use the following code:

randomizer.setSeed(randvalue.longV alue() + randomizer.nextInt() + System.currentT imeMillis());

Where, ranodom (class) → (object) randomizer → (method) nextInt()

randomizer.nextInt() returns random integer value one after one according to seed Seed and random class can be long at maximum. So, we add three random values inside the randomizer to get a better random value.

Table 1: Scalar Multiplication

Input Total time  Average time
P (192bit), k(192bit rand) 25968 millisec 25.97millisec (ms)

Results of Addition For the addition to be done 10^{6} times, we keep it inside a forloop. After every loop, P_{i}

gets the value of R_{i−1}, where P_{i} + Q = R_{i}

Table 2: Implementation Time

Sq Mul  Mod
0.002078 msec 0.001671 msec 0.004546 msec

Table 3: ECADD

Operations Theoritical Time Actual Time
4M +2S+6Mod 0.040188msec  0.050343msec

So, the computation time is t(A + J) = 6M + 5S + 9Mo where J means Jacobian and A means Affine.

Results of Doubling For the doubling to be done 10^{6} times, we keep it inside a forloop. After every loop, P_{i}

gets the value of R_{i−1}, where 2P_{i} = R_{i}

Table 4: ECDBL

Operations Theoritical Time Actual Time
5M+4S+5Mod 0.039397msec  0.064718msec

So, the computation time is t(2J) = 5M + 4S + 5Mo where J means Jacobian.

5.5 Classes and methods used

Method : nanoTime public static long nanoTime() Returns the current value of the most precise available system timer, in nanoseconds. This method can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time. The value returned represents nanoseconds since some fixed but arbitrary time (perhaps in the future, so values may be negative). This method provides nanosecond precision, but not necessarily nanosecond accuracy. No guarantees are made about how frequently values change. Differences in successive calls that span greater than approximately 292 years (263 nanoseconds) will not accurately compute elapsed time due to numerical overflow. Returns: The current value of the system timer, in nanoseconds.

Class : BigInteger public class BigInteger extends Number implements Comparable Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two’scomplement notation (like Java’s primitive integer types). BigInteger provides analogues to all of Java’s primitive integer operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations.

BigInteger : add public BigInteger add(BigInteger val) Returns a BigInteger whose value is (this + val).

Parameters: val - value to be added to this BigInteger. Returns: this + val

BigInteger : subtract public BigInteger subtract(BigInteger val) Returns a BigInteger whose value is (this - val).

Parameters: val - value to be subtracted from this BigInteger. Returns: this - val

BigInteger : multiply public BigInteger multiply(BigInteger val) Returns a BigInteger whose value is (this * val).

Parameters: val - value to be multiplied by this BigInteger. Returns: this * val

BigInteger : pow public BigInteger pow(int exponent) Returns a BigInteger whose value is (thisexponent). Note that exponent is an integer rather than a BigInteger.

Parameters: exponent - exponent to which this BigInteger is to be raised. Returns: thisexponent Throws: ArithmeticException - exponent is negative. (This would cause the operation to yield a non-integer value.)

BigInteger : negate public BigInteger negate() Returns a BigInteger whose value is (-this).

Returns: -this

BigInteger : toString public String toString() Returns the decimal String representation of this BigInteger. The digit-to-character mapping provided by Character.forDigit is used, and a minus sign is prepended if appropriate. (This representation is compatible with the (String) constructor, and allows for String concatenation with Java’s + operator.)

Overrides: toString in class Object Returns: decimal String representation of this BigInteger.

BigInteger : modPow public BigInteger modPow(BigInteger exponent, BigInteger m) Returns a BigInteger whose value is (thisexponent mod m). (Unlike pow, this method permits negative exponents.)

Parameters: exponent - the exponent. m - the modulus.

BigInteger : valueOf public static BigInteger valueOf(long val) Returns a BigInteger whose value is equal to that of the specified long. This ”static factory method” is provided in preference to a (long) constructor because it allows for reuse of frequently used BigIntegers.

Parameters: val - value of the BigInteger to return.