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

Downloaded: 12

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 charRn2,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

    admits an inverse application

    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

    Link to this chapter Copy to clipboard

    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:

    chapter statistics

    12total chapter downloads

    More statistics for editors and authors

    Login to your personal dashboard for more detailed statistics on your publications.

    Access personal reporting

    We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

    More About Us