alexa Cryptographic Schemes Based on Elliptic Curves over the Ring Zp[i] | OMICS International
ISSN: 2168-9679
Journal of Applied & Computational Mathematics
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

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

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

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 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.

Keywords

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

Introduction

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.

Auxiliary Result

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∈Zp where i2 = -1} be a ring having p2 elements. We have the following assertion:

Lemma 1: An element a + ib is invertible in Zp[i] if only if a2 + b2≠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 a2 + b2 ≠ 0(mod p) , so a2 + b2 ≠ 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 a2 + b2 = 0(mod p). So a2 + b2 = k, where k∈Z. We can write a = ta1, b = tb1 with g.c.d (a1,b1) = 1. Suppose a is not divisible by p then p does not divide t but p divides a12 + b12. Using proposition 1 [5], we obtain a12 + b12= kp. We have p≠3 (mod 4). Suppose p = 2, we can write 12 + 12 = 0(mod 2) then 1 + i is not invertible. Assume p = 1, then ∃ an element c∈Zp[i] such that Equationbecause cp-1 = 1 this implies that Equation and hence (ck)2 = c2k = -1. So 12 + (ck)2 = 1-1 = 0. We deduce that ck + I is not invertible. This completes the proof of the result.

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

(x,y)→x⊕y

such that Equation

where f is the isomorphism between G1 and G2. 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∈G1 then x⊕e = x*e = e*x = e⊕x = x,

Because x∈G1 and e is the unit element of (G1,*).

Equation

Else x∈G2, then

Because x∈G2,f(e) = e and e is unit element of (G2,°).

⊕ is commutative: We have (G1,*) and (G2,°) two abelian groups with the same unit element e [7-10].

Let x,y∈E. If x,y∈G1 then x⊕ y = x * y = y * x = y⊕ x

If x, y∈G2 then x⊕ y = f (x) ° y = y ° f (x) = y⊕ x

If Equationthen Equation

If Equation, then Equation .

Elliptic curve over the Field Zp[i]

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

Corollary 1: If b≠0 then Equation

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

Main Result

Theorem 2

Let f be a mapping from Ea,b∩Ea,-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)∈Ea,b then y2 = x3 + ax + b, then -y2 = -x3-ax-b i.e.

(iy)2 = (-x)3 + a(-x)-b therefore (-x,iy)∈Ea,b

Hence f is well defined.

f is one-one: Let (x1,y1),(x2,y2)∈Ea,b such that

f (x1,y1) = f (x2,y2)

(−x0 ,i y0) = (−x1,i y1 )

This implies that x1 = x2 and iy1 = iy2 i.e. x1 = x2 and y1 = y2

So, (x1,y1) = (x2,y2)

Hence, f is one-one.

f is onto: Let (x,y)∈Ea,-b. Then y2 = x3 + ax-b or –y2 = -x3-ax + b

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

Thus, f is onto.

f is homomorphism: Let (x1,y1),(x2,y2)∈Ea,b there is three cases arises:

Case 1: When x1≠x2

We have Equation

Equation

where Equation and Equation

again Equation

Equation

where Equation and Equation

It is obvious that Equation this implies that Equation and Equation

Therefore Equation

Case 2: When x1 = x2 and y1 = y2

Equation

Equation

where Equation and Equation

again Equation

Equation

where Equation and Equation

It is evident that Equation then, Equation and x3 = -x4.

Therefore, Equation

Case 3: When x1 = x2 and y1 = -y2

We have

Equation

and

Equation

Thus

Equation

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

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

(P,Q)→P⊕Q

such that Equation

where f is the isomorphism between Ea,b and Ea,-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 Ea,b and Ea,-b are isomorphic groups i.e. they are both abstractly identical of groups then Card(E) = 2Card(Ea,b)-1.

Proof: Since Ea,b is isomorphic to Ea,-b this implies Card(Ea,b) = Card(Ea,-b)

Now, E = Ea,b∪Ea,-b

This implies that Card(E) = Card(Ea,b) + Card(Ea,-b)-Card(Ea,b∩Ea,-b)

Therefore, Card(E) = 2Card(Ea,b)-1.

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.

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 = Ea,b∪Ea,-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 Equation and Equation

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 = E1,1∪E1,-1 are described as follow

Let P = [x0 + x1i;y0 + y1i;z], where xj,yj∈Z3 for j = 0 or 1 and z = 0 or 1. Then coding method is given by x0x1y0y1

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 Ea,b∪Ea,-b can be described as Equation

Equation

Let P = [x0 + x1i; y0 + y1i; z], where xj,yj∈Z7 for j = 0 or 1 and z = 0 or 1. Then coding method is given by x0x1y0y1z, 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(Zp[i]) of order n.

2. By P generate a subgroup and denoted it by Equation. 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≤NA≤n-1, computes K = NAP and sends it to Bob.

4. Bob chooses a random number 0≤NB≤n-1, computes K = NBP and sends it to Alice.

5. Alice computes NAK′ = NA.NBP.

6. Bob computes NB.K = NB.NAP.

7. Alice and Bob are agree with a point S = NA.NBP, 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 E3,45 = {(x,y): y2 = x3 + 3x + 45}∪{O} and E3,-45 = {(x,y): y2 = x3 + 3x-45}∪{O} are two elliptic curve defined over the same field Z8831[i] having 88312 element, where 8831 be a prime number such that 8831≡3(mod 4) and a point P = (4,11)∈Z8831[i] of order 4427.

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

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

(3) Alice computes NAK′ = 12.(3069,3265) = (3076,265).

(4) Bob computes NB.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 Pm.

2. Choose a random number k, compute Q = k.Pm and calculate Pb = S′.Q.

3. Public key is (a,b,p,P,Pb,Q).

4. Private key is (NA,NB,k,S).

ECC encryption phase

To encrypt Pm, a user choose an integer <<r>> at random and sends the point (r.Q,Pm + r.Pb). This operation is shown in Figure 1.

applied-computational-mathematics-the-encryption

Figure 1: The encryption operation.

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: (Pm + r.Pb)-S′.(r.Q) = Pm + r.S′Q-S′.r.Q = Pm

This operation is shown in Figure 2.

applied-computational-mathematics-the-decryption

Figure 2: The decryption operation.

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

Alice’s message is point Pm = (5,1743).

Bob has chosen his secret random number k = 3 and computed Q = k.Pm = 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.Pb = (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:

Equation

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.

References

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

Share This Article

Article Usage

  • Total views: 8180
  • [From(publication date):
    March-2016 - Aug 18, 2018]
  • Breakdown by view type
  • HTML page views : 8095
  • PDF downloads : 85
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2018-19
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

kactakapaniyor.com

[email protected]

+1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

Taktube

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

porn sex

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

Gaziantep Escort

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

sikiş

[email protected]

1-702-714-7001Extn: 9037

instafollowers

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

mp3 indir

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

putlockers

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

seks

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2018 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version