Medical, Pharma, Engineering, Science, Technology and Business

**Kumar M ^{*} and Gupta P**

Department of mathematics and Statistics, Gurukula Kangri Vishwavidyalaya, Uttrakhand, 249404, India

- *Corresponding Author:
- Kumar M

Department of mathematics and Statistics

Gurukula Kangri Vishwavidyalaya

Uttrakhand, 249404, India

**Tel:**01334690011

**E-mail:**[email protected]

**Received Date:** January 19, 2016; **Accepted Date:** February 03, 2016; **Published Date:** February 05, 2016

**Citation:** Kumar M, Gupta P (2016) Cryptographic Schemes based on Elliptic Curves over the Ring Zp[i]. J Appl Computat Math 5:288. doi:10.4172/2168-9679.1000288

**Copyright:** © 2016 Kumar M, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited..

**Visit for more related articles at** Journal of Applied & Computational Mathematics

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 Ea,b and Ea,-b defined over the ring Zp[i] where i2 = -1. After showing isomorphism between Ea,b and Ea,-b. 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 E = Ea,b∪Ea,-b. 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 scheme 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.

Elliptic curve; Ring; Finite field; Isomorphism; Cardinality; Encryption/Decryption.

Elliptic curve cryptography has been an active area of research since 1985 when Koblitz [1] and Miller [2] independently suggested using elliptic curves for public-key cryptography. Because **elliptic curve cryptography**** **offers the same level of security than, for example, 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 publickey 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 elliptic curve cryptography. The principal attraction of elliptic curve cryptography compared to RSA is that it offers equal security for a smaller key-size.

In this section we mention some **auxiliary results **which are necessary to prove the main result.

For a prime number p, Let Zp[i] = {a + bi: a,b∈Z_{p} where i^{2} = -1} be a ring having p^{2} elements. We have the following assertion:

**Lemma 1: **An element a + ib is invertible in Zp[i] if only if a^{2} + b^{2}≠0(mod p) [3].

**Proof: **Let a + ib be invertible then there exists an element c + id in Zp[i] such that

(a+ ib)(c + id) =1 (1)

which implies (ac-bd) + i(bc + ad) = 1 i.e. ac-bd = 1and bc + ad = 0.

In (1) take the conjugate (a-ib)(c-id) = 1 (2)

Multiply (1) and (2), we get

(a+ ib)(a− ib)(c + id)(c− id) =1

We deduce a^{2} + b^{2} ≠ 0(mod p) , so a^{2} + b^{2} ≠ 0(mod p).

**Lemma 2:** Let p be a prime number. Then Zp[i] is field iff p≡3 (mod 4) [4].

**Proof:** Assume that Zp[i] is not field if p≡3(mod 4) then ∃ an element a + bi∈Zp[i], which is not invertible. By Lemma 1 we have a^{2} + b^{2} = 0(mod p). So a^{2} + b^{2} = k, where k∈Z. We can write a = ta_{1}, b = tb_{1} with g.c.d (a_{1},b_{1}) = 1. Suppose a is not divisible by p then p does not divide t but p divides a_{1}^{2} + b_{1}^{2}. Using proposition 1 [5], we obtain a_{1}^{2} + b_{1}^{2}= kp. We have p≠3 (mod 4). Suppose p = 2, we can write 1^{2} + 1^{2} = 0(mod 2) then 1 + i is not invertible. Assume p = 1, then ∃ an element c∈Zp[i] such that because cp-1 = 1 this implies that and hence (c^{k})^{2} = c^{2k} = -1. So 12 + (c^{k})^{2} = 1-1 = 0. We deduce that c^{k} + I is not invertible. This completes the proof of the result.

**Theorem 1:** For two isomorphic abelian groups (G_{1},*) an(G_{2},°)d with the same unit element e, let E = G_{1}∪ G_{2} and also let ⊕: E × E → E be a mapping defined by

(x,y)→x⊕y

such that

where f is the isomorphism** **between G_{1} and G_{2}. Then ⊕ is an internal composition law, commutative with identity element e and all elements in E are invertible [6].

**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 x∈G_{1} then x⊕e = x*e = e*x = e⊕x = x,

Because x∈G_{1} and e is the unit element of (G_{1},*).

Else x∈G_{2}, then

Because x∈G_{2},f(e) = e and e is unit element of (G_{2},°).

**⊕ is commutative: **We have (G_{1},*) and (G_{2},°) two abelian groups with the same unit element e [7-10].

Let x,y∈E. If x,y∈G_{1} then x⊕ y = x * y = y * x = y⊕ x

If x, y∈G_{2} then x⊕ y = f (x) ° y = y ° f (x) = y⊕ x

If then

If , then .

**Elliptic curve over the Field Z _{p}[i]**

Let E_{a,b},E_{a,-b} be two elliptic curve over the field Z_{p}[i], where p is a prime number such that p = 3(mod 4), defined by and Where O is the point at infinity [11-14].

**Corollary 1:** If b≠0 then

**Proof:** Let (x,y)∈E_{a,b}∩E_{a,-b}, then y^{2} = x^{3} + ax + b and y^{2} = x^{3} + ax-b this implies that b = -b i.e. b = 0 which is a contradiction. Hence E_{a,b}∩E_{a,-b} = {O}.

**Theorem 2**

Let f be a mapping from E_{a,b}∩E_{a,-b} defined by

F(x,y) = (-x,iy) and f(O) = 0

Then f is a bijection.

**Proof: **First we show that f is well defined.

Let (x,y)∈E_{a,b} then y^{2} = x^{3} + ax + b, then -y^{2} = -x^{3}-ax-b i.e.

(iy)^{2} = (-x)^{3} + a(-x)-b therefore (-x,iy)∈E_{a,b}

Hence f is well defined.

f is one-one: Let (x_{1},y_{1}),(x_{2},y_{2})∈E_{a,b} such that

f (x_{1},y_{1}) = f (x_{2},y_{2})

(−x_{0} ,i y_{0}) = (−x_{1},i y_{1} )

This implies that x_{1} = x_{2} and iy_{1} = iy_{2} i.e. x_{1} = x_{2} and y_{1} = y_{2}

So, (x_{1},y_{1}) = (x_{2},y_{2})

Hence, f is one-one.

f is onto: Let (x,y)∈E_{a,-b}. Then y^{2} = x^{3} + ax-b or –y^{2} = -x^{3}-ax + b

This implies that (-x,iy)∈E_{a,-b} because (iy)^{2} = (-x)^{3} + a(-x)-b and f(- x,iy) = (x,y)

Thus, f is onto.

f is **homomorphism**: Let (x_{1},y_{1}),(x_{2},y_{2})∈E_{a,b} there is three cases arises:

**Case 1: **When x_{1}≠x_{2}

We have

where and

again

where and

It is obvious that this implies that and

Therefore

**Case 2:** When x_{1} = x_{2} and y_{1} = y_{2}

where and

again

where and

It is evident that then, and x_{3} = -x_{4}.

Therefore,

**Case 3:** When x_{1} = x_{2} and y_{1} = -y_{2}

We have

and

Thus

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

**Corollary 2: **For two isomorphic abelian groups E_{a,b} and E_{a,-b} with the same unit element O, let E = E_{a,b}∪E_{a,-b} and also let ⊕: E×E→E be a mapping defined by

(P,Q)→P⊕Q

such that

where f is the isomorphism between E_{a,b} and E_{a,-b}. 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 1, corollary 1, and theorem 2, it is evident that ⊕ is an internal composition law, commutative with identity element O and all elements in E are invertible.

**Corollary 3:** If E_{a,b} and E_{a,-b} are isomorphic groups i.e. they are both abstractly identical of groups then Card(E) = 2Card(E_{a,b})-1.

**Proof: **Since Ea,b is isomorphic to E_{a,-b} this implies Card(E_{a,b}) = Card(E_{a,-b})

Now, E = E_{a,b}∪E_{a,-b}

This implies that Card(E) = Card(E_{a,b}) + Card(E_{a,-b})-Card(E_{a,b}∩E_{a,-b})

Therefore, Card(E) = 2Card(E_{a,b})-1.

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.

**Coding of element on elliptic curve**

It is described with the help of illustration-1 and illustration-2.

**Illustration 1: **For p = 3, a = 1 and b = 1, Then codes of elements of E = E_{a,b}∪E_{a,-b} are given by E = {00100,00101,00201,10001,10101,102 01,20001,01101,01201,11001,11101,11201,21001,02101,02201,12001,1 2101,12201,22001}

Since, 2 3 and

Therefore E1,1 = {(0,1), (0,2), (1,0), (i,1), (i,2), (1 + i,0), (2i,1), (2i,2), (1 + 2i,0)}{O}.

and E1,-1 = {(1,1), (1,2), (2,0), (1 + i,1), (1 + i,2), (2 + i,0), (1 + 2i,1), (1 + 2i,2), (2 + i,0)}∪{O}.

Coding of element E = E_{1,1}∪E_{1,-1} are described as follow

Let P = [x_{0} + x_{1}i;y_{0} + y_{1}i;z], where x_{j},y_{j}∈Z_{3 } for j = 0 or 1 and z = 0 or 1. Then coding method is given by x_{0}x_{1}y_{0}y_{1}

which produces the following codes

E={00100,00101,00201,10001,10101,10201,20001,01101,01201,110 01,11101,11201,21001,02101,02201,12001,12101,12201,22001}

**Illustration 2:** For p = 7,a = 2 + 3i and b = 1 + i. The coding of points of E_{a,b}∪E_{a,-b} can be described as

Let P = [x_{0} + x_{1}i; y_{0} + y_{1}i; z], where x_{j},y_{j}∈Z7 for j = 0 or 1 and z = 0 or 1. Then coding method is given by x_{0}x_{1}y_{0}y_{1}z, which produces the following codes

E={00100, 00131, 00361, 00411, 00641, 01021, 01051, 01351, 01421, 02111, 02661, 03141, 03631, 04311, 04461, 05161, 05161, 05611, 06201, 06231, 06501, 06541, 10121, 10241, 10531, 10651, 12251, 12521, 14031, 14041, 14111, 14661, 15021, 15051, 15351, 15421, 16201, 16231, 16501, 16541, 20011, 20061, 23141, 23631, 25251, 25521, 26311, 26461, 31141, 311631, 33001, 33321, 33451, 35301, 35401, 36341, 36431, 41331, 41441, 42031, 42041, 44001, 44241, 44531, 46311, 46461, 50101, 50601, 51141, 51631, 52221, 52551, 54311, 54461, 60261, 60321, 60451, 60511, 61021, 61051, 61351, 61421, 62201, 62231, 62501, 62541, 63161, 63301, 63401, 63611, 65221, 65551}

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

**Exchange of secret key**

1. For a publically integer p, and an elliptic curve E(Zp[i]) let P∈E(Z_{p}[i]) of order n.

2. By P generate a subgroup and denoted it by . 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 0≤N_{A}≤n-1, computes K = N_{A}P and sends it to Bob.

4. Bob chooses a random number 0≤N_{B}≤n-1, computes K = N_{B}P and sends it to Alice.

5. Alice computes N_{A}K′ = N_{A}.N_{B}P.

6. Bob computes N_{B}.K = N_{B}.N_{A}P.

7. Alice and Bob are agree with a point S = N_{A}.N_{B}P, choose the binary code** **of point S as a private key, which transformed on the decimal code <<S′>>.

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

**Illustration 3:** Let E_{3,45} = {(x,y): y^{2} = x^{3} + 3x + 45}∪{O} and E_{3,-45} = {(x,y): y^{2} = x^{3} + 3x-45}∪{O} are two elliptic curve defined over the same field Z_{8831}[i] having 8831^{2} element, where 8831 be a prime number such that 8831≡3(mod 4) and a point P = (4,11)∈Z_{8831}[i] of order 4427.

(1) Alice choose a random number N_{A} = 12, compute K = 12(4,11) = (814,5822) and sends it to Bob.

(2) Bob chooses a random number N_{B} = 23 and comput K′ = 23(4,11) = (3069,3265) and sends to it Alice.

(3) Alice computes N_{A}K′ = 12.(3069,3265) = (3076,265).

(4) Bob computes N_{B}.K = 23.(814,5822) = (3076,265).

(5) Alice and Bob are agree with a point S = (3076,265), choose the **binary** code of point S as a private key, which transformed on the decimal code <<30760000265000001>>.

**ECC key generation phase**

Now, exchange of secret key involves the following steps:

1. Encode the message m on the point P_{m}.

2. Choose a random number** **k, compute Q = k.P_{m} and calculate P_{b} = S′.Q.

3. Public key is (a,b,p,P,P_{b},Q).

4. Private key is (N_{A},N_{B},k,S).

**ECC encryption phase**

To encrypt P_{m}, a user choose an integer <<r>> at random and sends the point (r.Q,P_{m} + r.P_{b}). This operation is shown in **Figure 1**.

**ECC decryption phase**

Decryption of the message is done by multiplying the first component of the received point the secret key <<S′>> and subtract it from the second component: (P_{m} + r.P_{b})-S′.(r.Q) = P_{m} + r.S′Q-S′.r.Q = P_{m}

This operation is shown in **Figure 2**.

**Illustration 4:** The E_{3,45} = {(x,y): y^{2} = x^{3} + 3x + 45}∪{O} and E_{3,-45} = {(x,y): y^{2} = x^{3} + 3x-45}∪{O} are two elliptic curve defined over the same field Z_{8831}[i] having 88312 element where 8831 be a prime number such that 8831≡3(mod 4) and a point P = (4,11)∈Z_{8831}[i] of order 4427.

Alice’s message is point P_{m} = (5,1743).

Bob has chosen his secret random number k = 3 and computed Q = k.P_{m} = 3.(5,1743) = (445,3115) and calculated Pb = S.Q = 30760000265000001(445,3115) = (7093,2868) Bob publish the point. Alice chooses the random number r = 8 and compute r.Q = 8.(445,3115) = (7966,6354) and Pm + r.P_{b} = (5,1743) + 8.(7093,2868) = (5011,2629) Alice sends (7966,6354) and (5011,2629) to Bob, who multiplies the first of these point by S′.(r.Q) = 30650000265000001.(7966,6354) = (6317,6201). Bob then subtracts the result from the last point Alice sends him. Note that he subtracts by adding the point with the second coordinate negated:

Bob has therefore received Alice’s message.

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

- Koblitz AH, Koblitz N, Menezes A (2011) Elliptic curve cryptography: The serpentine course of a paradigm shift. Journal of Number Theory 131: 781-814.
- Miller V (1985) Use of elliptic curves in cryptography. Advances in Cryptology-CRYPTO 85 (LNCS 218) pp: 417-426.
- Gilbert WJ (2004) Modern algebra with application. Willey-Interscience.
- Gallian JA (1998) Contemporary abstract algebra.Narosa publishing house.
- Chillali A (2011) Elliptic curve over ring. International Mathematical Forum 6: 1501-1505.
- Hankerson D, Menezes JA, Vanstone S (2004) Guide to Elliptic Curve Cryptography. Springer-Verlag.
- Hardy GH, Wright EM (1938)An introduction to the theory of numbers.Oxford university press.
- Koblitz N (1987) Elliptic Curve Cryptosystem. Journal of mathematics computation 48:203-209.
- Kumar S, Suneetha C, Chandrasekh A (2012) Encryption of data using elliptic curve over finite fields. International Journal of Distributed and Parallel Systems (IJDPS).
- Schoof R (1985) Elliptic curves over finite fields and the computation of square roots mod p. Math Comp 44: 483-494.
- Silverman J (1986)The Arithmetic of Elliptic Curves. Springer.
- Srivastava K, Nand G (2015) Elliptic Curves for Data Provenance.Procedia Computer Science 45: 470-476.
- Stinson DR (2006) Cryptography theory and practice. Chapman and Hall/CRC.
- Washington LC (2008) Elliptic curves number theory and cryptography. Chapman and Hall/CRC.

Select your language of interest to view the total content in your interested language

- Adomian Decomposition Method
- Algebraic Geometry
- Analytical Geometry
- Applied Mathematics
- Axioms
- Balance Law
- Behaviometrics
- Big Data Analytics
- Binary and Non-normal Continuous Data
- Binomial Regression
- Biometrics
- Biostatistics methods
- Clinical Trail
- Complex Analysis
- Computational Model
- Convection Diffusion Equations
- Cross-Covariance and Cross-Correlation
- Differential Equations
- Differential Transform Method
- Fourier Analysis
- Fuzzy Boundary Value
- Fuzzy Environments
- Fuzzy Quasi-Metric Space
- Genetic Linkage
- Hamilton Mechanics
- Hypothesis Testing
- Integrated Analysis
- Integration
- Large-scale Survey Data
- Matrix
- Microarray Studies
- Mixed Initial-boundary Value
- Molecular Modelling
- Multivariate-Normal Model
- Noether's theorem
- Non rigid Image Registration
- Nonlinear Differential Equations
- Number Theory
- Numerical Solutions
- Physical Mathematics
- Quantum Mechanics
- Quantum electrodynamics
- Quasilinear Hyperbolic Systems
- Regressions
- Relativity
- Riemannian Geometry
- Robust Method
- Semi Analytical-Solution
- Sensitivity Analysis
- Smooth Complexities
- Soft biometrics
- Spatial Gaussian Markov Random Fields
- Statistical Methods
- Theoretical Physics
- Theory of Mathematical Modeling
- Three Dimensional Steady State
- Topology
- mirror symmetry
- vector bundle

- Total views:
**8180** - [From(publication date):

March-2016 - Aug 18, 2018] - Breakdown by view type
- HTML page views :
**8095** - PDF downloads :
**85**

Peer Reviewed Journals

International Conferences 2018-19