Download paper :

SAM5912 A NOVEL AND EFFICIENT ALGORITHM TO

ENHANCE THE COMPLEXITY OF ELLIPTIC CURVE

CRYPTOGRAPHY

INTRODUCTION

In 1976 Diffie and Hellman[7] introduced the concept of Public key cryptography. They revolutionized the world of cryptography by developing key exchange system popularly known as Diffie Hellman Key Exchange which introduces applicability of discrete log in cryptography .The purpose of the algorithm is to enable two users to securely exchange a key. It depends for its effectiveness on the difficulty of computing discrete logarithms. The discrete logarithm problem employed was defined explicitly as the problem of finding logarithms with respect to a generator in the multiplicative group of the integers modulo a prime. But this idea can be extended to other groups. Elliptic curves were introduced in cryptography in 1985 independently by Koblitz[5] and Miller[6], who proposed to use Elliptic curve as groups over which all calculations are performed. This generated more complex discrete log problems .

Other public key cryptographic systems like RSA relies on the difficulty of integers factorization. In [1] the authors discusses the issues with RSA .The 1024 bit keys may be breakable in near future. The key length for secure RSA use has increased over years due to the development of fast computing processors which provide aid for brute force computation. Now larger key length has put heavier processing load on applications using RSA.[1] also discusses the advantages of ECC over RSA . There is a sub exponential attack already developed for RSA whereas ECC has attacks developed only for few classes of the curve.

Jurisic and Menezes[2] make a comparison based study between RSA and ECC. They compared the security achieved by both methods verses the key length used .The results showed that ECC outperforms RSA .[1]Table 1 shows the comparison between RSA and ECC methods on the basis of key size used and complexity achieved.

RSA ECC MIPS years

key size(bits) key size

512 106 10^4

768 132 10^8

1024 160 10^11

2048 210 10^20

Here key sizes are in bits and MIPS year represents computation power of a computer executing a million instructions per second,when used for one year.

[3] describes that the advantages that elliptic curve systems have over systems based on the multiplicative group of a finite field (and also over systems based on the intractability of integer factorization) is the absence of a sub exponential-time algorithm (such as those of “index-calculus” type) that could find discrete logs in these groups ECC compared to RSA offers equal security for smaller key sizes. The result is smaller key sizes, bandwidth savings, and faster implementations, features which are especially attractive for security applications where computational power and integrated circuit space is limited, such as smart cards, PC (personal computer) cards, and wireless devices.[4] also discusses various motivating factors which describes the advantages of ECC over other cryptosystems.

**ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM [ECDLP]**

Diffie and Hellman [7] used the discrete logarithm problem in their key exchange protocol .They defines the problem as finding logarithms with respect to a generator in the multiplicative group of the integers modulo a prime. But the problem of finding discrete logarithms can be extended to other groups ,especially when it is used over elliptic curves defined as curves its computational complexity increases many folds .[3] explains he discrete logarithm problem as, let G be a finite group of order n, and let α be an element of G. The discrete logarithm problem for G is the following: given an element β ∈ G, find an integer x, 0 ≤ x ≤ n − 1, such that α x = β,.Various groups have been proposed over the years for cryptographic purposes

like Agnew et al purposed multiplicative groups of characteristic two finite field .Koblitz[5] and Miller[6] used the group of points on an elliptic curve defined over a finite field.

**BASES OF ECC **

An elliptic curve used for cryptographic purposes is defined as follows:

y ^2 mod p = (x^ 3 + ax + b) mod p -(1)

where a and b are integer constants. The set of points E (a, b) is a set ( x, y ) of all x and y satisfying the above equation.

For an elliptic curve over a finite field Z p , we use the above cubic equation in which the variables and coefficients all take on values in the set of integers from 0 and p − 1 for some prime p,in which calculations are performed modulo p .

Assume first that Fq has characteristic greater than 3. An elliptic curve E over Fq is the set of all solutions (x, y) ∈ Fq × Fq to an equation

y 2 = x 3 + ax + b,

where a, b ∈ Fq and 4a + 27b = 0, together with a special point ∞ called the point at infinity.

Addition Formulas for the Curve (1). Let P = (x1 , y1 ) ∈ E; then −P = (x1 , −y1 ). If Q = (x 2 , y2 ) ∈ E, Q = −P, then P + Q = (x3 , y3 ), where

x3 = λ^2 − x1 − x2

y3 = λ(x1 − x3 ) − y1 ,

and

λ= y2-y1 / x2-x1 if P!=Q

3×1^2+a / 2y1 if P=Q

**Procedure**

Let us assume that both the user of the system agreed on a generating point G on the curve .Both will select their private keys and keep is as secret.Let the private key of user A is nA and that of user B is nB. Their respective public keys are pA and pB will be calculated in the following manner

pA=nA*G

pB=nB*G

Now we will use MAP2 Group method to map a message to a point on the elliptic group .Now message

m is converted to point P. Now let a secret parameter k. User A calculates k*pB and k*G(where G is the generating point).

Cm={kG,P+k*pB}

The adversary can access G and pB as they are in public domain. Given G and and kG is computational hard to kind k.

To decrypt it User B will multiply his private key with the hint provided as kG and subtract it from the second argument.

P=(P+k*pB)-(kG*nB)

The total time taken is

1. Time taken to map message to group Map2Group algorithm maps message M to Fp^m as (x,y).Its most expensive operation is Square root operation. Time needed is O(m^3). If m=1 ie Fp is the desired field as in our case, then the time taken is O(1).

- Time taken to add two points over the elliptic curve is also a constant ie O(1).
- Time taken in finding the cipher text is O(k),where k is the security parameter .So total time taken is O(k)+Θ(1)

**Security of ECC**

The basis for the security of elliptic curve cryptosystems such as the ECDSA is the apparent intractability of the following elliptic curve discrete logarithm problem (ECDLP): given an elliptic curve E defined over Fq , a point P ∈ E(Fq ) of order n, and a point Q ∈ E(Fq ), determine the integer l, 0 ≤ l ≤ n − 1, such that Q = l P, provided that such an integer

exists.[3] have made a good discussion on various kind of possible methods developed to solve the ECDLP .Pohlig–Hellman[9] developed a algorithm that reduces the determination of l to the determination of l modulo each of the prime factors of n .Pollard ρ-method[10] is one of the best known algorithm developed to counter the ECDLP .Gallant, Lambert and Vanstone [11] developed made the previous method more efficient which takes about √( π n)/2 elliptic curve additions.

Semaev[12]–Smart[13]–Satoh–Araki[14] designed which efficiently computes isomorphism between E(F p ), where E is a prime-field-anomalous curve, and the additive group of F p . This gives a polynomial-time algorithm for the ECDLP in E(F p ) .Menezes, Okamoto and Vanstone [15] developed the famous MOV attack ,it uses the concept of weil pairing to transform the elliptic curve group to a multiplicative group,defined over field Fq k for some integer k .Due to this transformation the Elliptic curve discrete logarithm problem got reduced to finding discrete logarithm problem (DLP) in Fq k. In [16] Miller discussed the implementation of index calculus method in elliptic curve groups.

**Proposed method to Increase the complexity of elliptic curve crypto system **

In this paper we are proposing a new idea of enhancing the security of elliptic curve crypto system by producing two discrete log problems,each one of them has to be independently solved. In ECC the curve on which computation is to be performed is in public domain since its beneficial to keep the algorithm and components in public domain to avoid overhead .After doing some computation on this base curve ie the curve available in the public domain we are rotating it along its axis to some appropriate value. Now this curve is hidden from the adversary. To know this curve curve the adversary has to solve a Elliptic Curve Discrete Logarithm Problem(ECDLP) .After rotating this curve we map the public keys and generating point(G) from base curve to the rotated curve. This can be performed by developing a mapping function,that performs a one-one mapping between the two curves. Now all the desired group arithmetic as performed conventionally is performed on the rotated curve. The user receiving the encrypted message has to use his/her private key with a given hint provided along with encrypted message in the cipher text to find the position of the curve .

We are increasing the security by producing two discrete log problems using keys of same size as used earlier .Thereby enhancing the security level .Now the adversary using any of the above explained sub exponential time algorithm,have to apply them to two separate ECDLP problems. In the next section we are explaining the proposed technique .

**MUTAROTATION**

An elliptic curve E over Fq is the set of all solutions (x, y) ∈ Fq × Fq to an equation

y 2 = x 3 + ax + b, (1)

where a, b ∈ Fq and 4a + 27b = 0, together with a special point ∞ called the point at infinity. Let there be two users Alice and Bob having private key and public key as (nA,pA) and (nB,pB) respectively.Suppose that E is an elliptic curve over Fq , and G(generating point) is an agreed upon (and publicly known) point on the curve .

STEP 1

Alice will take a secret number k1 and multiply the generating point G with it as per the group laws defined above.

Q=k1*G

Since Q lies on the curve let its coordinates be (x’,y’ ).

STEP 2

θ=tan-1(y/x)

STEP 3

Rotate the axis of the curve by θ .

STEP 4

Alice will map public keys pA ,pB and generating point G to the rotated elliptic curve,using the mapping function F . Let us assume that the mapped images are pA’,pB’and G’.

Step 5

Now Alice will select another secret parameter k2 and compute k2*G’ and k2*pB’. Here * depicts group multiplication operation.

Step 6

Alice will map the plain text to Pm,using the Map2Group algorithm .

**Cipher text generation **

Now Alice sends cipher text Pm to Bob as

Cipher text Cm={k1G, k2G’,Pm+k2*pB’}

Here k1 is the parameter which Alice choses for rotation of the curve ,G is the generating point to be used on the initially given curve E1 to find E2,k2 is the number of times the addition is performed,G’ is the mapped generating point ,Pm is the plain text.

**Decryption **

Bob will multiply his private key nB with the first hint to discover the new curve

nB*k1G=k1(nB*G)=k1*pB={x’,y’}

From this data Bob will calculate the angle by which curve is rotated .Now all the calculations will be performed on the rotated curve. Bob will multiply his private key with the second argument ie k2*G’ and subtract the result form the third argument of cipher text.

{Pm+k2*pB’} -{k2G’*nB}={Pm+k2*pB’} -{k2*(G’*nB)}={Pm+k2*pB’}-{k2*pB’}=Pm

**ISOMORPHISM BETWEEN THE TWO CURVES**

The two curves obtained will be isomorphic images of each other

<E1>——><E2>

eg

P1=αG1

P2=ø{P1}

αG1=α ø(G1)=αG2

**Development of a one-one function**

Let F be a one to one function mapping points form E1 to E2 ie F:E1->E2. Let there be a point (x,y) on E1.After the rotating the curve by θ we obtained the curve E2.Let there be another point having abscissa x’ and ordinate y’ on E2,which is the image of the point (x,y) on E1. F will find a mapping scheme between the two groups as

x’=x cosθ – y sin θ

y’=x sin θ +y cos θ

**Enhancement in Security **

Now the adversary has to solve two elliptic curve discrete log problems instead of one .First it is necessary for the adversary to find the rotated curve then only he can perform the desired computation on it. We are enhancing the security without increasing the key length .We can make the analysis of the security verses key length. If we keep the key length same,the security is increased two folds eg the index calculus algorithm takes sub exponential running time

exp((c + o(1))(log q k )1/3 (log log q k )2/3 )

here we assume that the elliptic curve is defined over the field F_{q}^{k }

Now we have to apply the index calculus algorithm twice to solve the two ECDLP. In this way security will be increased by twofolds.

Majority of the algorithms solving the ECDLP exploit the field properties and size on which the elliptic curve is defined .As an example, we will show the security level reached by incorporating the above proposed method in comparison to the conventionally used ECC algorithm .One of the best known algorithm to solve ECDLP is Pollard p method[10]. Let us assume that over curve E is defined over the field F2^k. We will depict the field size parameter 2^k by n. Pollard p method will take √( π n)/2 steps,here a step represents elliptic curve addition. Let us denote the computing power of the computers solving the EDCLP by Pollard p algorithm in MIPS ie million instructions per second. Here MIPS year defines the computational power of a computer executing a million instruction per second utilized for one year.

Size of n √( π n)/2 MIPS year MIPS year (when proposed method is used)

(in bits) 160 2^80 8.5 * 10^11 1.7 * 10^12

186 2^93 7 * 10^15 1.4 * 10^16

234 2^117 1.2 *10^23 2.4* 10^23

Since our proposed method generates two separate ECDLP problems , the Pollard p method will have to be applied to both the problems independently.

**Implementation efficiency **

ECC has major application in wireless communication. The wireless devices run on battery power,so the limited energy provided by battery acts as a constraint on the processing capabilities .If we use methods like RSA ,yet they provide high level of security but they will consume the power of the wireless devices

at both ends as both encryption and decryption processes will take enough time and energy . ECC overtook RSA in this respect ,as we can use keys of lower size with respect to RSA,and still provide same level of security. ECC takes less time to implement as arithmetic performed ie point addition and point doubling over the elliptic curve are relatively fast when compared to arithmetic performed over other fields.

[3] made a comparison between the time taken by ECC arithmetic performed over by elliptic curve defined over field Fq,whose order is 160 bits with DSA arithmetic performed over field Fp where calculations are performed with a 1024 bit modulus p .Since they both provide same level of security we are comparing the time taken to implement them. Multiplying two n bit numbers takes n^2 bit operation ,so modular multiplication is (1024/160)^2 ≈ 41 times longer than a field multiplication.

- To calculate kP ,where P∈ E(Fq ) and k is a 160 bit integer, we have to do repeated doubling and addition which on average requires 160 elliptic curve doubling and 80 elliptic curve additions

.The time taken to perform Elliptic curve addition or doubling requires one field inversion and two field multiplication[17].Also [18] and [19] showed that one field inversion is equivalent to three field multiplications .[3] showed that computing k P requires the equivalent of 1200 field multiplications, or 1200/41 ≈ 29 1024-bit modular multiplications.

- To calculate a^k mod p ,where k is 160 bit random number and p is 1024 bit prime (as perfomed in DSA) by repeated squaring and multiplying requires an average of 240 1024-bit modular multiplications

[3]. It proves that arithmetic operations performed on elliptic curve defined over Fq are nearly 8 times faster then operations performed in case 2.

Let us assume a random number k of 32 bits .As explained earlier in cipher text,

Cm={kG,P+k*pB}

In this mechanism we have to make three calculations

1.multiplication of G with k

2.multiplication of pB with k.

3.one addition operation

Both 1 and 2 , will require 240 field multiplications. So in total we have 480 field multiplications. As explained earlier one addition is equivalent to five field multiplications. So the total time taken in producing the cipher text is equivalent of doing 485 field multiplications.

Our proposed method may seem to be more time consuming at first look , but if we select the numbers k1 and k2 prudently then we can perform the above calculation in the same time .In our method cipher text,

Cm={k1G, k2G’,Pm+k2*pB’}

Let us assume that k1 and k2 are 32 bit and 16 bit numbers respectively .Now , the four operations performed are

1.multiplication of k1 with G.

2.multiplication of k2 with G’.

3.multiplication of k2 with pB’

4.addition between Pm and k2*pB’

Operation 1 is equivalent of doing 240 field multiplications. While operations 2 and 3 are equivalent of doing 120 field multiplications each. The fourth addition operation is equivalent of performing one field inversion and three field multiplication , which sums up to five field multiplications .In this way the total time taken is equivalent to 485 field multiplications ,which is exactly equal to the earlier case.

Thus our proposed method takes the same time in implementation as taken by previous method .We can still use it in wireless communication .On the other hand it provides more security than the conventional elliptic curve cryptographic system.

**Conclusion**

In this paper we have introduced a technique called Mutarotation and presented the algorithm to implement it. We also made a comparison on the basis of security achieved and implementation time between our proposed method and previously incorporated technique. We have proved that our proposed technique is more secure then the previously used method and it takes same time in implementation. This method can provide more security to wireless communication and can be implemented in same time as previous algorithm.

**References **

1.Elliptic Curve Cryptography by Vivek Kapoor and Vivek Sonny Abraham Department of Computer Engineering Delhi college of Engineering .

2.Elliptic curves and cryptography by Aleksandar Jurisic and Alfred J. Menezes . .Dr. Dobb’s Journal, 1997.

3.The State of Elliptic Curve Cryptography Neal koblitz Dept. of Mathematics, Box 354350, University of Washington, Seattle, WA 98195, USA.,ALFRED MENEZES Dept. of C&O, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1. SCOTT VANSTONE Dept. of C&O, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1.)

4.New Vistas in elliptic curve cryptography Brian A. LaMacchia, John L. Manferdelli Microsoft Corporation, One Microsoft Way, Redmond, WA, USA

5.N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, Vol. 48 (1987) pp. 203–209.

6.V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology—CRYPTO ’85, Lecture Notes in Computer Science, Springer-Verlag, 218 (1986) pp. 417–426.

7.W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol. 22 (1976) pp. 644–654.

8. G. Agnew, R. Mullin, I. Onyszchuk and S. Vanstone, An implementation for a fast public-key cryptosystem,

Journal of Cryptology, Vol. 3 (1991) pp. 63–79.

9. . Pohlig and M. Hellman, An improved algorithm for computing logarithms over G F( p) and its crypto-

graphic significance, IEEE Transactions on Information Theory, Vol. 24 (1978) pp. 106–110.

10. J. Pollard, Monte Carlo methods for index computation mod p, Mathematics of Computation, Vol. 32 (1978)

pp. 918–924.

11. R. Gallant, R. Lambert and S. Vanstone, Improving the parallelized Pollard lambda search on binary anoma-

lous curves, to appear in Mathematics of Computation.

12.I. Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic

p, Mathematics of Computation, Vol. 67 (1998) pp. 353–356.

13.N. Smart, The discrete logarithm problem on elliptic curves of trace one, to appear in Journal of Cryptology.

14.T. Satoh and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic

curves, Commentarii Mathematici Universitatis Sancti Pauli, Vol. 47 (1998) pp. 81–92.

15.A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field,

IEEE Transactions on Information Theory, Vol. 39 (1993) pp. 1639–1646.

- Miller, Uses of elliptic curves in cryptography, Advances in Cryptology—CRYPTO ’85, Lecture Notes in Computer Science, Springer-Verlag, 218 (1986) pp. 417–426.

17.G. Agnew, R. Mullin, I. Onyszchuk and S. Vanstone, An implementation for a fast public-key cryptosystem ,

Journal of Cryptology.

18.R. Schroeppel, H. Orman, S. O’Malley and O. Spatscheck, Fast key exchange with elliptic curve systems,

Advances in Cryptology—CRYPTO ’95

.

19.E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem and J. Vandewalle, A fast software implementation

for arithmetic operations in G F(2n ), Advances in Cryptology—ASIACRYPT ’96