Open access peer-reviewed chapter - ONLINE FIRST

Elliptic Curve over a Local Finite Ring Rn

By Abdelhakim Chillali and Lhoussain El Fadil

Submitted: March 8th 2020Reviewed: July 25th 2020Published: September 10th 2020

DOI: 10.5772/intechopen.93476

Abstract

The goal of this chapter is to study some arithmetic proprieties of an elliptic curve defined by a Weierstrass equation on the local ring Rn=FqX/Xn, where n≥1 is an integer. It consists of, an introduction, four sections, and a conclusion. In the first section, we review some fundamental arithmetic proprieties of finite local rings Rn, which will be used in the remainder of the chapter. The second section is devoted to a study the above mentioned elliptic curve on these finite local rings for arbitrary characteristics. A restriction to some specific characteristic cases will then be considered in the third section. Using these studies, we give in the fourth section some cryptography applications, and we give in the conclusion some current research perspectives concerning the use of this kind of curves in cryptography. We can see in the conclusion of research in perspectives on these types of curves.

Keywords

• elliptic curve
• finite ring
• cryptography

1. Introduction

Elliptic curves are especially important in number theory and constitute a major area of current research; for example, they were used in Andrew Wiles’s proof of Fermat’s Last Theorem. They also find applications in elliptic curve cryptography (ECC), integer factorization, classical mechanics in the description of the movement of spinning tops, to produce efficient codes… For these reasons, the subject is well known, presented, and worth exploring.

The purpose of cryptography is to ensure the security of communications and data stored in the presence of adversaries [1, 2, 3]. It offers a set of techniques for providing confidentiality, authenticity, and integrity services. Cryptology, also known as the science of secrecy, combines cryptography and cryptanalysis. While the role of cryptographers is to design, build, and prove cryptosystems, among other things, the goal of cryptanalysis is to “break” these systems. The history of cryptography has long been the history of secret codes and along all previous times, this has affected the fate of men and nations [4]. In fact, until 1970, the main goal of cryptography was to build a signature encryption systems [5, 6], but thanks to cryptanalysis, the army and the black cabinets of diplomats were able to wage their wars in the shadows controlling the communication networks, especially of their enemies [7, 8]. The internet revolution and the increasingly massive use of information in digital form facilitated communications but in counterparty it weakened the security level of information. Indeed, “open” networks create security holes, which allow access to the information. Cryptography, or the art of encrypting messages, a science that sites today in the crossroads of mathematics, computer sciences, and some applied physics, has then become a necessity for today’s civilization to keep its secrets from adversaries. Confusion is often made between cryptography and cryptology, but the difference exists. Cryptology is the “science of secrecy,” and combines two branches on the one hand, cryptography, which makes it possible to encrypt messages, and on the other hand, cryptanalysis, which serves to decrypt them. Our focus in this chapter is to show how some elliptic curves, mathematical objects studied particularly in algebraic geometry [9, 10, 11, 12]. You can give several definitions depending on the person you are talking to. Cryptography indeed used elliptic curves for more than 40 years the appearance of the Diffie-Hellman key exchange protocol and the ElGamal cryptogram [13, 14, 15]. These cryptographic protocols use in particular group structures, for by applying these methods to groups defined by elliptic curves, a new speciality was born at the end of the 1980: ECC, Elliptic Curve Cryptography. Recall that Diffie-Hellman key exchange which is based on the difficulty of the discrete logarithm problem (DLP) [16, 17, 18]. The success of elliptic curves in public key cryptographic systems has then created a new interest in the study of the arithmetic of these geometric objects. The group of points on an elliptical curve is an interesting group in cryptography because there is no known sub-exponential algorithm for sound (DLP) [19, 20, 21]. In general, the DLP is difficult to be solved, but not as much as in a generic group as in the case of finite field. We know sub-exponential algorithms to solve it depending on the size of the group to use, which impose criteria for the PLD to be infeasible. The prime number p which is the characteristic of our base ring must then have at least 1024 bits, which offers a security level similar to the one given by a generic order group of 160 bits. Recall that a generic group for the DLP is a group for which there is no a specific algorithm to solve the DLP [22], so that the only available algorithms are those for all groups.

In [23], Elhassani et al. have built an encryption method based on DLP and Lattice. Boulbot et al. in [24] have studied elliptic curves on a non-local ring to compare these curves on local and non-local rings, while in [25], Sahmoudi et al. have studied these types of curves on a family of finite rings in the authors have introduced a cryptosystem on these types of curves, see [26].

In this chapter, dand nare a positive integers and q=pdis a power of a prime natural number p.

2. The ring Rn=FqX/Xn

Let Rn=FqX/Xnbe a Fq-algebra of dimension n, with 1ϵϵn1as a Fq-basis, where ϵ=X¯, ϵn=0, Fqis the finite field of order q=pr, and pbeing a prime integer [27, 28, 29].

2.1 Internal laws in Rn

Recall that the two laws “+” and “.” are naturally defined on Rn[30, 31]: for every two elements X=i=0n1xiϵiand Y=i=0n1yiϵiin Rn, with x1,,xn,y1,,ynin Fq,

X+Y=i=0n1ziϵi,wherezj=xj+yjinFqE1
X.Y=i=0n1ziϵi,wherezj=i=0jxiyjiThe  cauchy  productE2

Corollary 2.1 LetX=i=0n1xiϵiRn, thenX2=i=0n1xiϵiwhere

k0,x2k=xk2+2i=0k1xix2kix2k+1=2i=0kxix2k+1iE3

Proof.

By formula (2), we have

j0,xj=i=0jxixji.E4
Forj=2k,x2k=i=02kxix2ki,E5
so,x2k=xk2+2i=0k1xix2ki.E6
Similarly,forj=2k+1,x2k+1=i=02k+1xix2k+1i,E7
then,x2k+1=2i=0kxix2k+1i.E8

Under the same hypotheses of the corollary (2.1) and by an analogous proof, we have the following corollary:

Corollary 2.2X3=i=0n1xiϵi, where

k0,x2k=x2kx0+l=0k1x2lx2k2l+x2l+1x2k12lx2k+1=l=0kx2lx2k+12l+x2l+1x2k2lE9

Lemma 2.3 LetY=i=0n1yiϵithe inverse ofX=i=0n1xiϵi. Then

y0=x01yj=x01i=0j1yixji,j>0E10

Proof.

Let Y=i=0n1yiϵibe the inverse of X=i=0n1xiϵi. Then XY=1,by formula (2), we have

XY=i=0n1ziϵi,wherezj=i=0jxiyji.E11

So,

z0=1and j>0,zj=0,E12

which means that,

y0=x01yj=x01i=0j1yixji,j>0E13

Lemma 2.4 The non inverse elements inRnare the elements of the formi=1n1xiϵiwherexiFqn1for all1in1.

Proof.

Let X=i=0n1xiϵiRn. By lemma (2.3), Xis invertible in Rnif and only if x0is invertible in Fq.As Fqis a field, this means x00.

Corollary 2.5 The ringRnis local, with maximal idealIn=ϵRn.

Notation.

Let k2, we denote:

1. πk:RkRk1i=0k1xiϵii=0k2xiδi

the projection of Rkon Rk1.

• kπ:RkR1i=0k1xiϵix0

• the canonical projection of Rkon R1=Fq.

Corollary 2.6πketkπare two ring homomorphisms.

Proof.

We have,

πki=0k1xiϵi+i=0k1yiϵi=πki=0k1xi+yiϵi=i=0k2xi+yiδi=πki=0k1xiϵi+πki=0k1yiϵiE14

and

i=0k1xiϵii=0k1yiϵi=i=0k1ziϵi,wherezj=i=0jxiyji.πki=0k1ziϵi=i=0k2ziδiπki=0k1xiϵiπki=0k1yiϵi=i=0k2ziδiE15

Note that in addition, for every k1,

kπ=π2π3π4πkE16

So, πkand kπare tow rings morphisms.

Theorem 2.7 Letn2be an integer,

a=a˜+an1ϵn1, b=b˜+bn1ϵn1, X=X˜+xn1ϵn1, Y=Y˜+yn1ϵn1andZ=Z˜+zn1ϵn1be elements ofRnwith:

Y2Z=X3+aXZ2+bZ3.E17

Then

Y˜2Z˜=X˜3+a˜X˜Z˜2+b˜Z˜3+DAyn1+Bzn1+Cxn1ϵn1E18

where,

A=2y0z0,E19
B=y023z02b02z0a0x0,E20
C=3x02+a0z02E21

and

D=bn1z03+an1x0z02.E22

Proof.

We have:

Y2Z=Y˜+yn1ϵn12Z˜+zn1ϵn1=Y˜2Z˜+y02zn1+2y0z0yn1ϵn1X3=X˜+xn1ϵn13=X˜3+3x02xn1ϵn1aXZ2=a˜X˜Z˜2+2zn1z0a0x0+a0xn1z02+an1x0z02ϵn1bZ3=b˜Z˜3+bn1z03+3z02zn1b0ϵn1E23

If

Y2Z=X3+aXZ2+bZ3,E24

then, Y˜2Z˜=X˜3+a˜X˜Z˜2+b˜Z˜3+(3x02xn1+2zn1z0a0x0+a0xn1z02+an1x0z023z02zn1b0y02zn12y0z0yn1)ϵn1and therefore,

Y˜2Z˜=X˜3+a˜X˜Z˜2+b˜Z˜3+DAyn1+Bzn1+Cxn1ϵn1E25

where,

A=2y0z0,E26
B=y023z02b02z0a0x0,E27
C=3x02+a0z02E28

and

D=bn1z03+an1x0z02.E29

2.2 Primitive triples

Definition 2.8 LetRbe a ring. We say that an elementxyzR3is primitive if:xR+yR+zR=R. The set of these primitive triplets will be denotedPR.

Remark 2.9 The equalityxR+yR+zR=Rmeans that there existsαβλR3such that1R=αx+βy+λz.

Proposition 2.10 LetRbe a local ring, thenxyzR3is a primitive triple if and only if at least one of the elementsx,y, andzis invertible inR.

Proof.

Suppose that x,yand zare not invertible in R, then:

xyzM3where Mis the unique maximal ideal of R, hence

xR+yR+zRMR,E30

which contradicts that xyzis a primitive triple.

Conversely, suppose, for example, that xis invertible in R, then xR=R, so xR+yR+zR=R.

Remark 2.11 IfRis a field, then an elementxyzR3is primitive if and only ifxyz0,0,0.

2.3 The projective plane on a finite ring

Let Ris a ring. The projective plane on Ris the set of equivalence classes of PRmodulo; the equivalence relation Rdefined by:

x1y1z1Rx2y2z2λR×:x2y2z2=λx1y1z1.E31

We denote the projective plane on Rby P2R, it is the quotient set PRR, and we write x:y:zfor the equivalence class of xyzPR. Thus, we have:

x1:y1:z1=x2:y2:z2λR×:x2=λx1,y2=λy1andz2=λz1.E32

Example 2.12 We Consider the finite ringF2e=α+βe/αF2andβF2,whereeis an indeterminate satisfyinge2=0. The group of units for this ring isF2e×=11+e.

As this ring is local with maximal idealeF2e, then an elementxyzofF2e3is non primitive if and only ifxyz0e3.As one can see, there are eight elements which are not primitive, and therefore the setPF2econtains648=56primitive triples as given below:

PF2e= 0,0,10,1,1+e0,1,00,1,101e0,1,1+e0e10e1+e,01+e0,01+e1,01+ee,01+e1+e,1,0,0,1,0,1,10e,1,0,1+e,1,1,0,1,1,1,11e,1,1,1+e,1e0,1e1,1ee,1e1+e,11+e0,11+e1,11+ee,11+e1+e,e,0,1,e,0,1+e,e,1,0,e,1,1,e1e,e,1,1+e,ee1,ee1+e,e1+e0,e1+e1,e1+ee,e1+e1+e,1+e,0,0,1+e,0,1,1+e0e,1+e,0,1+e,1+e,1,0,1+e,1,1,1+e1e,1+e,1,1+e,1+ee0,1+ee1,1+eee,1+ee1+e,1+e1+e0,1+e1+e11+e1+ee1+e1+e1+e.E33

Letxyzandxyzbe two elements inPF2e, then:

x:y:z=x:y:zxyz=xyzorxyz=x+xey+yez+ze

so every class inP2F2econtains two representatives, that is, the projective planeP2F2econtains exactly the following 28 elements:

P2F2e=0:1:00:0:10:1:10:1:e0:1:1+e0:e:11:0:01:0:1,1:0:e,1:0:1+e,1:1:0,1:1:1,1:1:e,1:1:1+e,1:e:0,1:e:1,1:e:e,1:e:1+e,1:1+e:0,1:1+e:1,1:1+e:e,1:1+e:1+e,e:0:1,e:1:0,e:1:1,e:1:e,e:1:1+ee:e:1.E34

3. Elliptic curve over Rn

In this section, we study the elliptic curves defined on finite local rings Rnof characteristic a prime number p;

1. A projective Weierstrass equation on Rnis an equation of the form:

E:Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4X+a6Z3E35

• A affine Weierstrass equation on Rnis an equation of the form:

E:Y2+a1XY+a3Y=X3+a2X2+a4X+a6E36

• where a1a2a3a4a6Rn5.

3.1 Elliptic curve form

To an affine (or projective) Weierstrass Eqs. (3) and (4), we associate the following quantities:

b2=a12+4a2b4=2a4+a1a3b6=a32+4a6b8=a12a6+4a2a6a1a3a4+a2a32a42c4=b2224b4Δ=b22b88b4327b62+9b2b4b6j=c43ΔifΔ0E37

Δis called the discriminant of Eand jits j– invariant.

Remark 3.1 On the fieldR1=Fq, we denote the discriminant byΔ0and the j-invariant byj0, while on the ringRn,n>1we denote the discriminant byΔε,nand the j-invariant byjε,n.

We havenπΔε,n=Δ0andnπjε,n=j0.

Definition 3.2 LetRbe a finite ring and leta=a1a2a3a4a6R5.An elliptic curve onRcorresponding to a, which we writeEaR, is the set of zeros in the projective planeP2Rof the WeierstrassEq. (3), for which the discriminantΔis invertible inR.

Remark 3.3 According to the characteristic of the ringR;chraRwe have the following cases:

1. 1. If charR2and charR3,then:

Ea,bR=X:Y:ZP2R/Y2Z=X3+aXZ2+bZ3E38

forabR×R, withΔ=Δa,b=164a3+27b2R×.

1. 2. If charR=2,then Ea,bRhas one of the following forms:

Ea,bR=X:Y:ZP2R/Y2Z+XYZ=X3+aX2Z+bZ3E39

for abR2, with Δ=Δa,b=bR×.

Or:

EaR=X:Y:ZP2R/Y2Z+a1XYZ+a3YZ2=X3+a4XZ2+a6Z3E40

for a=a1a3a4a6R4,with a1non invertible and

Δ=Δa=a13a13a6+a12a3a4+a1a42+a33+a34R×.E41

1. 3. If charR=3,then Ea,bRhas one of the following forms:

Ea,bR=X:Y:ZP2R/Y2Z=X3+aX2Z+bZ3E42

forabR2, withΔ=Δa,b=a3bR×.

Or:

Ea,bR=X:Y:ZP2R/Y2Z=X3+aXZ2+bZ3E43

for abR2, with Δ=Δa,b=a3R×.

Remark 3.4 A projective elliptic curve on a fieldKhas one of the following normal forms (Table 1):

Normal form
charK2,3Y2Z=X3+a4XZ2+a6Z3
Δ=164a43+27a62j=17284a434a43+27a62
charK=3j=0Y2Z=X3+a4XZ2+a6Z3
Δ=a43
j0Y2Z=X3+a2X2Z+a6Z3
Δ=a23a6j=a23a6
charK=2j=0Y2Z+a3YZ2=X3+a4XZ2+a6Z3
Δ=a34
j0Y2Z+XYZ=X3+a2X2Z+a6Z3
Δ=a6j=1a6

Table 1.

Elliptic curve form on a field.

3.2 Projective coordinates and group law

In this subsection, we give in projective coordinates the formulas for adding the points on an elliptic curve defined by Eq. (3) on the ring Rn, according to the normal form.

Using Bosma and Lenstra’s theorem see [32], we can deduce the explicit formulas for the commutative additive law of the group EaRn. The results are given in the next theorems following the values of the characteristic of ring Rn[33, 34, 35, 36]. Let

X1:Y1:Z1+X2:Y2:Z2=X3:Y3:Z3.E44

Theorem 3.5 [Characteristic two case]:

• IfnπX1:nπY1:nπZ1=nπX2:nπY2:nπZ2,then:

X3= X1Y1Y22+X2Y12Y2+X22Y12+X1X22Y1+aX12X2Y2+aX1X22Y1+aX12X22+bX1Y1Z22+bX2Y2Z12+bX12Z22+bY1Z22Z1+bY2Z12Z2+bX1Z22Z1.E45
Y3= Y12Y22+X2Y12Y2+aX1X22Y1+a2X12X22+bX12X2Z2+bX1X22Z1+bX1Y1Z22+bX12Z22+abX22Z12+abX12Z22+bY1Z1Z22+bX1Z1Z22+abX1Z1Z22+abX2Z12Z2+b2Z12Z22E46
Z3= X12X2Y2+X1X22Y1+Y12Y2Z2+Y1Y22Z1+X12X22+Y12X2Z2+X12Y2Z2+aX12Y2Z2+aX22Y1Z1+X12X2Z2+aX1X22Z1+bY1Z1Z22+bY2Z12Z2+bX1Z1Z22.E47

• IfnπX1:nπY1:nπZ1nπX2:nπY2:nπZ2,then:

X3= X1Y22Z1+X2Y12Z2+X12Y2Z2+X22Y1Z1+aX12X2Z2+aX1X22Z1+bX1Z1Z22+bX2Z12Z2.E48
Y3= X12X2Y2+X1X22Y1+Y12Y2Z2+Y1Y22Z1+X12Y2Z2+X22Y1Z1+aX12Y2Z2+aX22Y1Z1+aX12X2Z2+aX1X22Z1+bY1Z1Z22+bY2Z12Z2+bX1Z1Z22+bX2Z12Z2.E49
Z3=X12X2Z2+X1X22Z1+Y12Z22+Y22Z12+X1Y1Z22+X2Y2Z12+aX12Z22+aX22Z12.E50

Theorem 3.6 [Characteristic three case]:

• IfnπX1:nπY1:nπZ1=nπX2:nπY2:nπZ2,then:

X3=Y1Y22X1+Y12Y2X2+2aX12X2Y2+2aX1X22Y1+2Z1Z22abY1+2Z12Z2abY2.E51
Y3=Y12Y22+2a2X12X22+a2bX1Z1Z22+a2bX2Z12Z2.E52
Z3=aX1X2Y1Z2+Y2Z1+aX1Y2+X2Y1X1Z2+X2Z1+Y1Y2Y1Z2+Y2Z1.E53

• IfnπX1:nπY1:nπZ1nπX2:nπY2:nπZ2,then:

X3=2X1Y2Y1Z2+X1Y22Z1+2X2Y12Z2+X2Y1Y2Z1+2aX12X2Z2+aX1X22Z1.E54
Y3=2Y12Y2Z2+Y1Y22Z1+2aX1X2Y1Z2+aX1X2Y2Z1+2aX12Y2Z2+aX22Y1Z1.E55
Z3=2Y12Z22+Y22Z12+aX12Z22+2aX22Z12.E56

Theorem 3.7 [The case where the characteristic is different from two and from three]:

• IfnπX1:nπY1:nπZ1=nπX2:nπY2:nπZ2,then:

X3=Y12X2Z2Z1X1Y22aZ1X2+X1Z2Z1X2X1Z2+2Y1Y23bZ1Z2Z1X2X1Z2E57
Y3=Y1Y2Z2Y1Z1Y2aX1Y1Z22Z12X2Y2+2aZ1Z23X1X2X2Y1X1Y23bZ1Z2Z2Y1Z1Y2E58
Z3=Z1Y2+Z2Y1Z2Y1Z1Y2+3X1X2+aZ1Z2Z1X2X1Z2E59

• IfnπX1:nπY1:nπZ1nπX2:nπY2:nπZ2,then:

X3= Y1Y26bZ1Z2X2Y1+X1Y2+a2Z1Z22aX1X2Z1Y2+Z2Y13bX1Y1Z22+Z12X2Y2aY1Z1X22+X12Y2Z2E60
Y3= Y12Y22+3aX12X22+a39b2Z12Z22a2Z1X2+X1Z222a2Z1X1Z2X2+9bX1X23abZ1Z2Z1X2+X1Z2E61
Z3= Y1Y2+3bZ1Z2Z1Y2+Z2Y1+3X1X2+2aZ1Z2X2Y1+X1Y2+aX1Y1Z22+Z1X2Y2.E63

4. Elliptic curve on Rnwhere charRn≠2,3

The objective of this chapter is to study elliptic curves defined by a Weierstrass equation with coefficients in a ring Rnsuch that charRn2,3. We denote it by Ea,bn.Let

kθ:Fqk1Ea,bkx1x2.xk1i=1k1xiϵi:1:i=3k1ziϵiE64

we denote, kG=kθFqk1.

4.1 The morphisms πket θk

Lemma 4.1 The application

πk:Ea,bkEπka,πkbk1X:Y:ZπkX:πkY:πkZE65

is a surjective group homomorphism.

Proof.

πkis well defined becauseπkis a morphism of rings. According to theorem (2.7), we haveAYk1+BZk1+CXk1=Dmodp, with

A=2y0z0,E66
B=y023z02b02z0a0x0,E67
C=3x02+a0z02E68

and

D=bn1z03+an1x0z02.E69

The coefficientsA,BandCare the partial derivatives of the function

FXYZ=Y2ZX3a0XZ2b0Z3E70

calculated starting from x0y0z0,which are not all equal to zero and deducing the existence of xk1:yk1:zk1. Hence, πkest surjectif.

Using corollary (2.6), we deduce thatπkis a group homomorphism.

Lemma 4.2 For allk2,

Kerπk=lϵk1:1:0lFq.E71

Proof.

We have:

Kerπk=PEa,bkπkP=0:1:0.E72

Then, P=xk1ϵk1:1+yk1ϵk1:zk1ϵk1=xk1ϵk1:1:zk1ϵk1..

As PEa,bk, we have

zk1ϵk1=xk1ϵk13+axk1ϵk1zk1ϵk12+bzk1ϵk13=0,E73

so, zk1=0.

This yields Kerπk=lϵk1:1:0lFq.

Lemma 4.3 The application

θk:FqEa,bkllϵk1:1:0E74

is an injective group homomorphism.

Proof.

The application θkis injective by construction.

Let lϵk1:1:0and hϵk1:1:0be two elements in Ea,bk, then:

kπlϵk1=kπhϵk1kπ1=kπ1kπ0=kπ0.E75

so, using theorem (3.7),

X3=l+hϵk1Y3=1Z3=0.E76

This yields

θkl+h=θkl+θkh.E77

Thus, θkis an injective group homomorphism.

4.2 Main applications

In this subsection, we consider a prime pwhich does not divide N, where N=Ekπa,kπb1.

Corollary 4.4 LetPEa,bk, then

NP=0:1:0PEkπa,kπb1.E78

Proof.

If PEkπa,kπb1,thenNP=0:1:0.

Let P=x0+X:y0+Y:z0+ZEa,bkandQ=x0:y0:z0Ekπa,kπb1.

If NP=0:1:0,thenNPQ=0:1:0.

So, PQ=kθl1l2.lk1.

We deduce that Nli0p,i=1,2,,k1,where pgcdNp=1,which proves that li=0etP=Q.

Corollary 4.5

PEa,bk,wehavepNP=0:1:0.E79

Proof.

PEa,bk,NPkG,so pNP=0:1:0..

Lemma 4.6 Ifpdo not divideN, then there exists a unique homomorphism

vk:Ea0,b01Ea,bkE80

for which the following diagram is commutative; (named Diagram(d)).

Proof.

Let PkG,we have pP=0:1:0.

Then

kGkerp.E81

Hence, there is a unique homomorphism

vk:Ea0,b01Ea,bkE82

which makes the diagram(d) commutative.

Theorem 4.7 Ifpdo not divideN, then there exists a unique homomorphism

sk:Ea0,b01Ea,bkE83

such that πkosk=idEa0,b01.

Proof.

Let Nas it exists tchecking 1NN=tp.Then,

1NN=top.E84

According to Lemma (4.6), there is a unique homomorphism

sk:Ea0,b01Ea,bkE85

which makes the following diagram commutative; (named Diagram(d’)):

Let PEa0,b01, then there exists PEa,bksuch that πkP=P.So,

πkoskP=πkoskoπkP=πk1NNP=πkPNNP=PNNP=P.E86

Theorem 4.8 Ifpdo not divideN, thenEa,bkEa0,b01×kG.

Proof.

The isomorphism

fk:Ea0,b01×kGEa,bkPQskP+QE87

Fk:Ea,bkEa0,b01×kGPπkPNNP.E88

Indeed,

fkoFkP=fkπkPNNP=skoπkP+NNP=1NNP+NNP=P.E89

Likewise,

FkofkPQ=FkskP+Q=πkskP+QNNskP+Q.E90

So,

πkskP+Q=πkskP+πkQ=P+0:1:0=P.NN'skP+Q=NNskP+NNQ=NN1NNP+NNQ=NtpNP+NNQ=0:1:0+NNQ=NNQ.E91

As, pQ=0:1:0, then we have

NNQ=1tpQ=QtpQ=Q.E92

We conclude,

FkofkPQ=PQ.E93

Corollary 4.9 Ifpdo not divideN, thenEa,bkEa0,b01×Fqk1.

Proof.

We have, kGFqk1,see [27, 30, 33].

Corollary 4.10 Ifpdo not divideN, then

Ea,bkCN×Fqk1,withCNcyclicorEa,bkZ/n1Z×Z/n2Z×Fqk1,wheren2n1p1.E94

Proof.

We have

Ea0,b01CN,withCNcyclicorEa0,b01Z/n1Z×Z/n2Z,wheren2n1p1.E95

And

Ea,bkEa0,b01×Fqk1.E96

Corollary 4.11 Ifpdo not divideN, thenq12qk1Ea,bkq+12qk1.

Proof.

According to Haas’ theorem, we have:

q+1N2qE97

so

q12qk1Ea,bkq+12qk1.E98

5. Applications

In this section, we are interested in ECC using elliptic curves over the ring Rn.

5.1 The discrete logarithm on Ea,bn

The discrete logarithm problem that we denote DLP, (Discrete logarithm problem), is a generally difficult problem which depends on the considered group G. In many situations, due to the asymmetry existing between problems concerning the calculation of logarithms and calculation of powers which is more easier and so of great interest in cryptograph, the above mentioned makes Diffie and Hellman were the first to build a cryptosystem from this situation [37, 38].

Definition 5.1 LetGbe a finite cyclic group of orderρands,rtwo elements ofG. We call discrete logarithm of basesofr,the only elementmin0ρ1such thatsm=r.The discrete logarithm for elliptic curves is defined in an analogous way to be, the only elementmin0ρ1such thatmP=Q, whereP,andQare two points of an additive subgroupGofEa,bn.

By using the isomorphism proved given in theorem (4.8), we get the results gathered in the next theorem:

Theorem 5.2 Ifpdoes not divideN, then.

• #Ea,bn=pdn1×N.

• The problem of the discrete logarithm on the elliptic curve Ea,bnis equivalent to that of Ea0,b01.

• If the problem of the discrete logarithm on Ea,bnis trivial, then it is also trivial on the elliptic curve Ea0,b01.

5.2 Cryptography based on elliptic curves Ea,bn

Elliptic curve cryptography (ECC) is public key cryptography, which relies on the use of curves over finite fields. Essentially, there are two families of these curves which are used in cryptography. The first uses elliptic curves on a finite field Fpd, where pis a large prime number. This family is the best choice for a high software level when implementing ECC. The second family uses elliptic curves on a binary field F2dwhere dis a large positive integer, this family is more appropriate at the material level point of view when implementing ECC. Another family which is also interesting in ECC implementations is the family of elliptic curves on the previously seen rings Rn. The most important advantage presented by the use of elliptic curves in cryptography (ECC) consists in the high security they provide for wireless applications compared to other asymmetric key cryptosystems, also their small key size. Indeed, a 160-bit key for (ECC) can replace a 1024-bit key for (RSA). Given d;a large integer, PEa,bnand QGEa,bn.The discrete elliptical logarithm problem (DLEP) consists in finding kZsuchthatQ=kP, where

kP=P+P+Pktimes=kP.E99

This is in fact a difficult problem, whose resolution is exponential.

5.3 Elliptical Diffie-Hellman cryptosystem

Recall that Alice and Bob can publicly agree on a common secret (that we describe below).

1. They choose on a large integer d, Ea,bnandPEa,bn.

2. Alice chooses tZand calculates tP.

3. Bob chooses sZand calculates sP.

4. Alice let public tPand keep private t.

5. Bob let public sPand keep private s.

6. Then, Alice and Bob build their common secret key K=tsP=stP.

Remark 5.3

1. Unlike the classic Diffie-Hellman algorithm, we do not ask that Pbe a generator of Ea,bn.The analogue of the subgroup Fpof order p1,is the cyclic subgroup of Ea,bn,generated by the point P.

2. As soon as we have a group Ea,bn,and an element PEa,bnof finite order we can consider a Diffie-Hellman system on G=<P>which is cyclic. For this construction to have a cryptographic interest, logPtP=tmust be not easy to calculate.

3. Ea,bn,is not always cyclical.

4. If, Oscar (program) is giving d,Ea,bn,tPandsP, then it is able to solve the discrete elliptical logarithm problem and find tors.

5.4 Elliptical ElGamal cryptosystem

Let PmEa,bnbe the point representing the message m, to encrypt Pm:

1. Key generation algorithm

• Bob chooses the private key tZknown only to him.

• d,PEa,bnandR=tPare public.

2. Encryption algorithm

• Alice Randomly chooses kZ;

• She calculates c1=kPEa,bn;

• She also calculates c2=Pm+kR;

• Then, he makes public c1,c2,or C=c1c2.

3. To decrypt received message c1c2,Bob calculates:

Pm=c2kR=c2ktP=c2tc1.E100

Now, Oscar encounters the discrete elliptic logarithm problem, because to decipher the message Pmhe must know t(i.e.; calculate tsuch that R=tP).

5.5 Coding example

Let dbe a positive integer, we consider the quotient ring R2=F2dXX2,where F2dis the finite field of order 2d.

Then the ring R2is identified with the ring F2dε, where ε2=0, i.e.,

R2=a0+a1εa0a1F2d.E101

We consider the elliptic curve on the ring R2given by the equation:

Y2Z+XYZ=X3+aX2Z+bZ3.E102

where a,bin R2and bis invertible in R2.Each element of Ea,b2is of the form; X:Y:1or :1:0,with xF2d. Write:

Ea,b2=X:Y:1P22Y2+XY=X3+aX2+b:1:0xF2d.E103

Let Ea,b2be the elliptic curve over R2and consider the irreducible polynomial TX=1+X+X3in F2X.Let αbe such that Tα=0in F8=F2XTX,then 1αα2is a vector space base of F8over F2.

F8=01αα2α+1α2+αα2+1α2+α+1E104

Put:

a=1+α;E105
b=1+α2ε.E106

We have: R2=F8εandEa,b2:Y2+XY=X3+1+αX2+1+α2ε.Consider PEa,b2of order l,and consider the subgroup G=<P>, generated by P,to encrypt and decrypt our messages.

1. 1. Coding of elements of G

We will give a code to each element Q=mP,where m12..l,defined as follows:

If Q=x0+x1ε:y0+y1ε:Z,where xi,yiF8for i=0,1,and Z=0or1,then we set:

xi=c0i+c1iα+c2iα2;E107
yi=d0i+d1iα+d2iα2,E108

where αis the primitive root of the irreducible polynomial TX=1+X+X3,and cij,dijF2.

So, we code Qas follows:

If Z=1: Q=c00c10c20c01c11c21d00d10d20d01d11d211.

If Z=0: Q=00c01c11c21d01d11d2110000.

1. 2. Example: with the same aandb;

a=1+α;E109
b=1+α2ε.E110

The elliptic curve Ea,b2contains 112elements to know:

Ea,bA2={α2+α+1ε:1:0,α2+1ε:1:0,[1+αε:1:0],α2+αε:1:0,α2ε:1:0,αε:1:0,[ε+α2+1:αε+α:1],α2+α:α2+α+1ε:1,α2ε:ε+1:1,[α2+1ε+α2+1:α2+αε+α:1],1+αε+α2:α2+α+1ε+α2+1:1,[α2+αε+1+α:α2+α+1ε+α2:1],1+αε+α2+1:α:1,[α2ε+α2+α+1:ε+1:1],1+α:α2+1ε+α2+α+1:1,[α2+α+1ε+α:α2+1ε+α2+α:1],αε+α2:α2+1ε+α2+1:1,[1+αε+α2+α+1:1+αε+1:1],α2ε:1+αε+1:1,α2ε+1+α:α2ε+α2+α+1:1,[αε+α2+1:ε+α:1],1+αε+α2+α:α2+1ε+α2+α:1,[α2ε+α2+α+1:α2+1ε+α2+α:1],α2+1ε+1+α:α2+αε+α2:1,[αε+α2+α:E111
0:1],α2+1:1+αε+α2+α+1:1,[ε+α2+1:1+αε+α2+α+1:1],α2+α+1ε+α2+1:1+αε+α2+α+1:1,[α2+α+1ε+α2:1+αε+1:1],α2ε+α2+1:α2+α+1ε+α:1,[1+αε+α2+α:α2+αε:1],α2+α+1ε+1+α:ε+α2:1,[α2+αε+α2+1:1+αε+α2+α+1:1],α2+1ε+α2+1:1+αε+α2+α+1:1,[α2+1ε+1+α:1+αε+α2+α+1:1],ε+α2:αε+1:1,[α2+1ε+α2+α+1:αε+1:1],α2ε:αε+1:1,ε+α2+α:ε:1,[1+αε+α2+1:1+αε+α2+α+1:1],α2ε+α2+1:1+αε+α2+α+1:1,[αε+α2+1:1+αε+α2+α+1:1],α2+α+1ε+α2+α+1:α2ε+1:1,1+αε+α2:α2ε+1:1,[α2ε:α2ε+1:1],α2+α+1:α2+αε+α2+α:1,α2ε:1:1,[α2+αε+α2:1:1],ε+α1+αε+α2+α:1,[α2+α+1ε+α2+α+1:1+αε+α2+α:1],α2+αε+α2+α:1+αε+α2+α:1,[α2+αε+1+α:ε+α2+α+1:1],α2+α+1ε+α2+α:1+αε:1,[ε+α2+α+1:α2ε+α2+α:1],ε+1+α:αε+α2+α+1:1,α:αε+α2+α:1,[αε+α2+α+1:αε+α2+α:1],αε+α2+α+1:1:1,[α2+α+1ε+α2+α:α2ε+α2+α:1],α2:ε+α2+1:1,[1+αε+1+α:α2+α+1ε+α2+α+1:1],α2+α:α2+α+1ε+α2+α:1,ε+α2+α:α2+α:1,[αε+1+α:α2+α+1:1],α2:ε+1:1,[α2+αε+α2+α+1:α2+α+1ε+1:1],α2ε:α2+α+1ε+1:1,α2+αε+α2+1:α2+1ε+α:1,[ε+α2:1+αε+α2+1:1],ε+1+α:1+αε+α2:1,[α2+αε+α2:α2+αε+α2+1:1],α2+αε+α2+α:α2+1ε:1,[ε+α2+α+1:α2+1ε+1:1],α2+α+1ε+α2+1:α2ε+α:1,[α2ε+α2+α:αε:1],α2+αε+α:α2ε+α2+α:1,[α2+αε+α:αε+α2:1],α2+1ε+α:αε+α2:1,1+αε+α:αε+α2:1,[1+αε+α:ε+α2+α:1],1+αε+α2+α+1:α2+α:1,[α2+α+1:α2+αε+1:1],α2ε:α2+αε+1:1,[α2ε+α:αε+α2:1],αε+1+α:αε+α2:1,αε+α:αε+α2:1,[α2+1ε+α2:α2+1:1],αε+α:α2+α:1,1+αε+1+α:α2ε+α2:1,[α2+1ε+α2+α:ε+α2+α:1],αε+α2+α:αε+α2+α:1,[α2ε+α2:αε+α2+1:1],α2+1ε+α2+α+1:α2+α+1ε+α2+α:1,[α2+1ε+α:α2+α+1ε+α2+α:1],α2+α+1ε+α2:α2ε+α2+1:1,[α2ε:E112
α2+1ε+1:1],α2ε+α:α2+αε+α2+α:1,[1+α:α2+1ε+α2:1],α2+α+1ε+1+α:α2+αε+α2+α+1:1,[α2ε+α2:α2+αε+1:1],α2+1:1+αε+α:1,α2+1ε+α2+α:α2ε:1,[α2ε+1+α:α2:1],0:1:0,α:αε+α2:1,ε+α:αε+α2:1,[α2+α+1ε+α:αε+α2:1],α2+αε+α2+α+1:ε+α2+α:1,[α2ε+α2+α:α2+αε+α2+α:1],αε+α2:α2+α+1ε+1:1,ε:1:0,α2+1ε+α2:α2+1ε+1:1}E114

We consider: P=α:α+α2+αε:1=0100000110101,then G=<P>is of order 28. We attach to each point QGa letter of the alphabet and a code. We collect the results in the following Table 2:

mPCode for mPSymbol
1α:α+α2+αε:10100000110101a
21+α+ε:α2+1+αε:11101000011101b
3α2+αε:1+α2+α2+1ε:10010101011011c
41+α+α2+1+αε:α+α2:11111100110001d
5α+α2+1+α+α2ε:1+αε:10111110001101e
61+α2+1+α+α2ε:α+α2ε:11011110100011f
7α2ε:1+1+α2ε:10000011001011g
81+α2+1+α2ε:1+α+α2+1+αε:11011011111101h
9α+α2+αε:α+α2+αε:10110100110101i
101+α+α2+αε:1:11110101000001j
11α2+α2ε:1+α+α2ε:10010011000111k
121+α+α+α2ε:1+α+α2+ε:11100111111001l
13α+1+αε:α2+αε:10101100010101m
14α2ε:1:00000100010000n
15α+1+αε:α+α2+ε:10101100111001o
161+α+α+α2ε:α2+1+α+α2ε:11100110011111p
17α2+α2ε:1+α2+αε:10010011010101q
181+α+α2+αε:α+α2+αε:11110100110101r
19α+α2+αε:0:10110100000001s
201+α2+1+α2ε:α+α+α2ε:11011010100111t
21α2ε:1+ε:10000011001001u
221+α2+1+α+α2ε:1+α+α2+1+αε:11011111111101v
23α+α2+1+α+α2ε:α+α2+α2ε:10111110110011w
241+αα2+1+αε:1+1+αε:11111101001101x
25α2+αε:1+1+α+α2ε:10010101001111y
261+α+ε:1+α+α2+αε:11101001110101z
27α:α2+αε:10100000010101space
280:1:00000000010000,

Table 2.

Points coding.

5.6 Encryption and decryption procedures

• The encryption of our message “for the elliptical curve”, is;

01111101100110111110001101010000001010100000110010010110100000001011111000110101000000101011011010100111101101111110101111100011010100000010101011111000110111001111110011100111111001011010011010111001100111111011010100111011010011010100101010110110100000010101001010101101100000110010011110100110101101111111110101111100011010000000010000E115

• Decryption of this message:

010000011010111010000111011111100110001011111000110111001111110011011011111101010000011010101011000101010110100110101111110011000101000000101011011010100111010000011010111111001100010101100010101010110011100111101001101010110100110101E116

is: hello to abdelhakim.

6. Conclusion

The results obtained are very important from theoretical points of view because to study an elliptic curve on a finite local ring it suffices to study these curves on finite fields, for the applications of these curves they can be applied in cryptography to reinforce security and we can use them in cryptanalysis to solve the PDL on special curves. This results are very imploring and give applications in different fields such as classical mechanics, number theory, cryptology, information theory … and we can quote here:

1. The generalization of Hass’s theorem, corollary 4.9.

2. The result of the corollary 4.11, then in [24], we have the result of the Proposition 3.12.

Acknowledgments

The authors thank professor Karim Mounirh for his correcting typographical, grammatical, spelling, and punctuation errors to ensure the clear and accurate communication.

How to cite and reference

Cite this chapter Copy to clipboard

Abdelhakim Chillali and Lhoussain El Fadil (September 10th 2020). Elliptic Curve over a Local Finite Ring <em>R<sub>n</sub></em> [Online First], IntechOpen, DOI: 10.5772/intechopen.93476. Available from: