Cryptographic Schemes Based on Elliptic Curves over the Ring Zp[i]

Manoj Kumar, Pratik Gupta

Department of Mathematics and Statistics, Gurukula Kangri Vishwavidyalaya, Haridwar (Uttrakhand), India.

DOI: 10.4236/am.2016.73027                

Abstract

Elliptic Curve Cryptography recently gained a lot of attention in industry. The principal attraction of ECC compared to RSA is that it offers equal security for a smaller key size. The present paper includes the study of two elliptic curve and defined over the ring where . After showing isomorphism between and , we define a composition operation (in the form of a mapping) on their union set. Then we have discussed our proposed cryptographic schemes based on the elliptic curve . We also illustrate the coding of points over E, secret key exchange and encryption/decryption methods based on above said elliptic curve. Since our proposed schemes are based on elliptic curve of the particular type, therefore the proposed schemes provides a highest strength-per-bit of any cryptosystem known today with smaller key size resulting in faster computations, lower power assumption and memory. Another advantage is that authentication protocols based on ECC are secure enough even if a small key size is used.

Keywords

Elliptic Curve, Ring, Finite Field, Isomorphism, Cardinality, Encryption/Decryption

Received 9 January 2016; accepted 26 February 2016; published 29 February 2016

1. Introduction

Elliptic curve cryptography has been an active area of research since 1985 when Koblitz (Ref. [1] ) and Miller (Ref. [2] ) independently suggested using elliptic curves for public-key cryptography. A lot of work has been done on elliptic curve cryptography (Ref. [3] -[7] ). Because elliptic curve cryptography offers the same level of security as compared to RSA with considerably shorter keys, it has replaced traditional public key cryptosystems, especially, in environments where short keys are important. Public-key cryptosystems are computationally demanding and, hence, the fact that elliptic curve cryptography has been shown to be faster than traditional public-key cryptosystems is of great importance. Elliptic Curve Cryptographic (ECC) schemes are public-key mechanisms that provide the same functionality as RSA schemes. However, their security is based on the hardness of a different problem, namely the Elliptic Curve Discrete Logarithmic Problem (ECDLP). Most of the products and standards that use public-key cryptography for encryption and digital signatures use RSA schemes. The competing system to RSA is an elliptic curve cryptography. The principal attraction of elliptic curve cryptography compared to RSA is that it offers equal security for a smaller key-size.

2. Auxiliary Result

In this section first we discuss some essential arithmetic of elliptic curves, and then we mention some auxiliary results which are necessary to prove the main result. Although a lot of literature exist on arithmetic of elliptic curves (Ref. [8] -[11] ), a simple and easier arithmetic of elliptic curves are given by the following (Ref. [10] ):

An elliptic curve over a finite field is defined by the parameters (a and b satisfy the relation), consists of the set of points, satisfying the equation. The set of points on also include point O, which is the point at infinity and which is the identity element under addition. Actually elliptic curve are not ellipse. They are so called because they are described by cubic equation similar to those are used for calculating the circumference of an ellipse.

The Addition operation is defined over and it can be seen that forms an abelian group under addition.

Ÿ .

Ÿ If, then. (The point and is called the negative of P and is denoted).

Ÿ If and and, then, where

, and.

Ÿ Let. Then the point,

where, and.

Now we discuss the auxiliary result of this section. For a prime number p, let where, be a ring having elements. Then we have the following assertion:

Lemma 2.1. (Ref. [12] ) An element is invertible in if only if.

Proof. Let be invertible then there exists an element in such that

(1)

which implies i.e. and.

In (1) take the conjugate

(2)

Multiply (1) and (2), we get

We deduce

, so.

Lemma 2.2. (Ref. [13] [14] ) Let p be a prime number. Then is field iff.

Proof. Assume that is not field if then an element, which is not

invertible. By Lemma 2.1, we have. So, where. We can write,

with. Suppose a is not divisible by p then p does not divide t but p divides. Using proposition 1.2 [3] , we obtain. We have. Supposing, we can write then is not invertible. Assume, then an element such that

because this implies that and hence. So.

We deduce that is not invertible. This completes the proof of the result.

Theorem 2.3. For two isomorphic abelian groups and with the same unit element e, let and also let be a mapping defined by

such that

where f is the isomorphism between and. Then is an internal composition law, commutative with

identity element e and all elements in E are invertible.

Proof. It is clear that is an internal composition law over E.

To show that e is the identity element with respect to binary operation.

Let x in E. If then

because and e is the unit element of.

Else, then

because and e is unit element of.

is commutative

We have and two abelian groups with the same unit element e.

Let. If then

If then

If then

If then

.

3. Elliptic Curve over the Field

Let be two elliptic curve over the field, where p is a prime number such that, defined by

and

where O is the point at infinity.

Corollary 3.1. If then.

Proof. Let, then

and

This implies that

i.e.

which is a contradiction.

Hence

.

4. Main Result

Theorem 4.1. Let f be a mapping from to defined by

and

Then f is a bijection.

Proof. First we show that f is well defined.

Let then, then i.e. therefore

Hence f is well defined.

f is one-one. Let such that

This implies that i.e.

So,

Hence, f is one-one.

f is onto. Let. Then or

This implies that because and

Thus, f is onto.

f is homomorphism. Let there is three cases arise:

Case I. When

As we know that addition of two different points and on elliptic curve is given by

where and

So we have

where and

Again

where and.

It is obvious that this implies that and.

Therefore

.

Case II. When and

where and.

Again

where and.

It is evident that then, and.

Therefore,

Case III. When and

We have

and

Thus

Therefore, in either case f is an homomorphism. Hence f is a bijection.

Corollary 4.2. For two isomorphic abelian groups and with the same unit element O, let and also let be a mapping defined by

such that

where f is the isomorphism between and. Then is an internal composition law, commutative with identity element O and all elements in E are invertible.

Proof. Keeping in view the result of theorem-2.3, corollary-2.4, and theorem-3.1, it is evident that is an internal composition law, commutative with identity element O and all elements in E are invertible.

Proof. Since is isomorphic to this implies

Now,

This implies that

Therefore,

.

5. Cryptographic Applications

In this section we shall illustrate our proposed methods for coding of points on Elliptic Curve, then exchange of secret key and finally use them for encryption/decryption.

5.1. Coding of Element on Elliptic Curve

It is described with the help of illustration 5.1 and illustration 5.2.

Illustration 5.1. For and, Then codes of elements of are given by

Since, and

Therefore

.

and

.

Coding of element are described as follow

Let, where for j = 0 or 1 and z = 0 or 1. Then coding method is given by which produces the following codes

Illustration 5.2. For and. The coding of points of can be described as

Let, where for j = 0 or 1 and z = 0 or 1. Then coding method is given by which produces the following codes

The above scheme helps us to encrypt and decrypt any message of any length.

5.2. Exchange of Secret Key

1) For a publically integer p, and an elliptic curve let of order n.

2) P generates a subgroup say which is used to encrypt the message m.

Now, key exchange between Alice and Bob can be described as follows

3) Alice chooses a random number, computes and sends it to Bob.

4) Bob chooses a random number, computes and sends it to Alice.

5) Alice computes.

6) Bob computes.

7) Alice and Bob are agree with a point,choose the binary code of point S as a private key, which transformed on the decimal code.

Remark. With the secret key such as the decimal code of point S Alice and Bob can encrypt and decrypt the message (m).

Illustration 5.3. Let and

are two elliptic curve defined over the same field having element, where 8831 be a prime number such that and a point of order 4427.

1) Alice chooses a random number, compute and sends it to Bob.

2) Bob chooses a random number and compute and sends to it Alice.

3) Alice computes.

4) Bob computes.

5) Alice and Bob are agree with a point, choose the binary code of point S as a private key, which transformed on the decimal code.

5.3. ECC Key Generation Phase

Now, exchange of secret key involves the following steps:

1) Encode the message m on the point.

2) Choose a random number k, compute and calculate.

3) Public key is.

4) Private key is.

5.4. ECC Encryption Phase

To encrypt, a user choose an integer at random and sends the point. This operation is shown in Figure 1.

5.5. ECC Decryption Phase

Decryption of the message is done by multiplying the first component of the received point and the secret key, and the result is subtracted from the second component i.e.:

This operation is shown in Figure 2.

Illustration 5.4. Theand

Figure 1. The encryption operation.

Figure 2. The decryption operation.

are two elliptic curves defined over the same field having element where 8831 be a prime number such that and a point of order 4427.

Alice’s message is the point.

Bob has chosen his secret random number and computed

and calculated

Bob publishes the point. Alice chooses the random number and computes

and

Alice sends (7966,6354) and (5011,2629) to Bob, who multiplies the first of these point by

.

Bob then subtracts the result from the last point that Alice sends him. Note that he subtracts by adding the point with the second coordinate negated:

Bob has therefore received Alice’s message.

Acknowledgements

This research work is supported by University Grant commission (UGC) New Delhi, India under the Junior Research Fellowship student scheme..

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Koblitz, A.H., Koblitz, N. and Menezes, A. (2011) Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift. Journal of Number Theory, 131, 781-814. http://dx.doi.org/10.1016/j.jnt.2009.01.006
[2]	Miller, V. (1985) Use of Elliptic Curves in Cryptography. Advances in Cryptology-CRYPTO, 85, 417-426.
[3]	Chillali, A. (2011) Elliptic Curve over Ring. International Mathematical Forum, 6, 1501-1505.
[4]	Koblitz, N. (1987) Elliptic Curve Cryptosystem. Journal of Mathematics Computation, 48, 203-209. http://dx.doi.org/10.1090/S0025-5718-1987-0866109-5
[5]	Kumar, S., Suneetha, C. and Chandrasekh, A. (2012) Encryption of Data Using Elliptic Curve over Finite Fields. International Journal of Distributed and Parallel Systems (IJDPS), 3, No. 1.
[6]	Schoof, R. (1985) Elliptic Curves over Finite Fields and the Computation of Square Roots Mod p. Mathematics of Computation, 44, 483-494.
[7]	Srivastava, K. and Nand, G. (2015) Elliptic Curves for Data Provenance. Procedia Computer Science, 45, 470-476. http://dx.doi.org/10.1016/j.procs.2015.03.082
[8]	Hankerson, D., Menezes, J.A. and Vanstone, S. (2004) Guide to Elliptic Curve Cryptography. Springer-Verlag, Germany.
[9]	Silverman, J. (1986) The Arithmetic of Elliptic Curves. Springer, New York. http://dx.doi.org/10.1007/978-1-4757-1920-8
[10]	Stinson, D.R. (2006) Cryptography Theory and Practice. Chapman and Hall/CRC, United Kingdom.
[11]	Washington, L.C. (2008) Elliptic Curves Number Theory and Cryptography. Chapman and Hall/CRC, United Kingdom. http://dx.doi.org/10.1201/9781420071474
[12]	Gilbert, W.J. (2004) Modern Algebra with Application. Willey-Interscience, New York.
[13]	Hardy, G.H. and Wright, E.M. (1938) An Introduction to the Theory of Numbers. Oxford University Press, United Kingdom.
[14]	Gallian, J.A. (1998) Contemporary Abstract Algebra. Narosa Publishing House, New Delhi.