Open access peer-reviewed chapter

Elliptic Curve over a Local Finite Ring Rn

Written By

Abdelhakim Chillali and Lhoussain El Fadil

Reviewed: 25 July 2020 Published: 10 September 2020

DOI: 10.5772/intechopen.93476

From the Edited Volume

Number Theory and Its Applications

Edited by Cheon Seoung Ryoo

Chapter metrics overview

547 Chapter Downloads

View Full Metrics

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, d and n are a positive integers and q=pd is a power of a prime natural number p.

Advertisement

2. The ring Rn=FqX/Xn

Let Rn=FqX/Xn be a Fq-algebra of dimension n, with 1ϵϵn1 as a Fq-basis, where ϵ=X¯, ϵn=0, Fq is the finite field of order q=pr, and p being 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ϵi and Y=i=0n1yiϵi in Rn, with x1,,xn,y1,,yn in Fq,

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

Corollary 2.1 Let X=i=0n1xiϵiRn, then X2=i=0n1xiϵi where

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.2 X3=i=0n1xiϵi, where

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

Lemma 2.3 Let Y=i=0n1yiϵi the inverse of X=i=0n1xiϵi. Then

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

Proof.

Let Y=i=0n1yiϵi be 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 in Rn are the elements of the form i=1n1xiϵi where xiFqn1 for all 1in1.

Proof.

Let X=i=0n1xiϵiRn. By lemma (2.3), X is invertible in Rn if and only if x0 is invertible in Fq. As Fq is a field, this means x00.

Corollary 2.5 The ring Rn is local, with maximal ideal In=ϵRn.

Notation.

Let k2, we denote:

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

the projection of Rk on Rk1.
  1. kπ:RkR1i=0k1xiϵix0

the canonical projection of Rk on R1=Fq.

Corollary 2.6 πk et kπ 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, πk and kπ are tow rings morphisms.

Theorem 2.7 Let n2 be an integer,

a=a˜+an1ϵn1, b=b˜+bn1ϵn1, X=X˜+xn1ϵn1, Y=Y˜+yn1ϵn1 and Z=Z˜+zn1ϵn1 be elements of Rn with:

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)ϵn1 and 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 Let R be a ring. We say that an element xyzR3 is primitive if: xR+yR+zR=R. The set of these primitive triplets will be denoted PR.

Remark 2.9 The equality xR+yR+zR=R means that there exists αβλR3 such that 1R=αx+βy+λz.

Proposition 2.10 Let R be a local ring, then xyzR3 is a primitive triple if and only if at least one of the elements x, y, and z is invertible in R.

Proof.

Suppose that x,y and z are not invertible in R, then:

xyzM3 where M is the unique maximal ideal of R, hence

xR+yR+zRMR,E30

which contradicts that xyz is a primitive triple.

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

Remark 2.11 If R is a field, then an element xyzR3 is primitive if and only if xyz0,0,0.

2.3 The projective plane on a finite ring

Let R is a ring. The projective plane on R is the set of equivalence classes of PR modulo; the equivalence relation R defined by:

x1y1z1Rx2y2z2λR×:x2y2z2=λx1y1z1.E31

We denote the projective plane on R by P2R, it is the quotient set PRR, and we write x:y:z for 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 ring F2e=α+βe/αF2andβF2, where e is an indeterminate satisfying e2=0. The group of units for this ring is F2e×=11+e.

As this ring is local with maximal ideal eF2e, then an element xyz of F2e3 is non primitive if and only if xyz0e3. As one can see, there are eight elements which are not primitive, and therefore the set PF2e contains 648=56 primitive 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

Let xyz and xyz be two elements in PF2e, then:

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

so every class in P2F2e contains two representatives, that is, the projective plane P2F2e contains 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
Advertisement

3. Elliptic curve over Rn

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

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

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

  1. A affine Weierstrass equation on Rn is 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 E and j its j – invariant.

Remark 3.1 On the field R1=Fq, we denote the discriminant by Δ0 and the j-invariant by j0, while on the ring Rn, n>1 we denote the discriminant by Δε,n and the j-invariant by jε,n.

We have nπΔε,n=Δ0 and nπjε,n=j0.

Definition 3.2 Let R be a finite ring and let a=a1a2a3a4a6R5. An elliptic curve on R corresponding to a, which we write EaR, is the set of zeros in the projective plane P2R of the Weierstrass Eq. (3), for which the discriminant Δ is invertible in R.

Remark 3.3 According to the characteristic of the ring R; chraR we have the following cases:

  1. If charR2 and charR3, then:

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

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

  1. If charR=2, then Ea,bR has 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 a1 non invertible and

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

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

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

for abR2, 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 field K has 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]:

  • If nπ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

  • If nπ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]:

  • If nπ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

  • If nπ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]:

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

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

  • If nπ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.E62
Advertisement

4. Elliptic curve on Rn where charRn2,3

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

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

we denote, kG=kθFqk1.

4.1 The morphisms πk et θk

Lemma 4.1 The application

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

is a surjective group homomorphism.

Proof.

πk is well defined because πk is a morphism of rings. According to theorem (2.7), we have AYk1+BZk1+CXk1=Dmodp, with

A=2y0z0,E65
B=y023z02b02z0a0x0,E66
C=3x02+a0z02E67

and

D=bn1z03+an1x0z02.E68

The coefficients A, B and C are the partial derivatives of the function

FXYZ=Y2ZX3a0XZ2b0Z3E69

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

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

Lemma 4.2 For all k2,

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

Proof.

We have:

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

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

so, zk1=0.

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

Lemma 4.3 The application

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

is an injective group homomorphism.

Proof.

The application θk is injective by construction.

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

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

so, using theorem (3.7),

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

This yields

θkl+h=θkl+θkh.E76

Thus, θk is an injective group homomorphism.

4.2 Main applications

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

Corollary 4.4 Let PEa,bk, then

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

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

Proof.

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

Lemma 4.6 If p do not divide N, then there exists a unique homomorphism

vk:Ea0,b01Ea,bkE79

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

Proof.

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

Then

kGkerp.E80

Hence, there is a unique homomorphism

vk:Ea0,b01Ea,bkE81

which makes the diagram(d) commutative.

Theorem 4.7 If p do not divide N, then there exists a unique homomorphism

sk:Ea0,b01Ea,bkE82

such that πkosk=idEa0,b01.

Proof.

Let N as it exists t checking 1NN=tp. Then,

1NN=top.E83

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

sk:Ea0,b01Ea,bkE84

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

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

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

Theorem 4.8 If p do not divide N, then Ea,bkEa0,b01×kG.

Proof.

The isomorphism

fk:Ea0,b01×kGEa,bkPQskP+QE86

admits an inverse application

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

Indeed,

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

Likewise,

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

So,

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

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

NNQ=1tpQ=QtpQ=Q.E91

We conclude,

FkofkPQ=PQ.E92

Corollary 4.9 If p do not divide N, then Ea,bkEa0,b01×Fqk1.

Proof.

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

Corollary 4.10 If p do not divide N, then

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

Proof.

We have

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

And

Ea,bkEa0,b01×Fqk1.E95

Corollary 4.11 If p do not divide N, then q12qk1Ea,bkq+12qk1.

Proof.

According to Haas’ theorem, we have:

q+1N2qE96

so

q12qk1Ea,bkq+12qk1.E97
Advertisement

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 Let G be a finite cyclic group of order ρ and s,r two elements of G. We call discrete logarithm of base s of r, the only element m in 0ρ1 such that sm=r. The discrete logarithm for elliptic curves is defined in an analogous way to be, the only element m in 0ρ1 such that mP=Q, where P,andQ are two points of an additive subgroup G of Ea,bn.

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

Theorem 5.2 If p does not divide N, then.

  • #Ea,bn=pdn1×N.

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

  • If the problem of the discrete logarithm on Ea,bn is 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 p is 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 F2d where d is 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,bn and QGEa,bn. The discrete elliptical logarithm problem (DLEP) consists in finding kZsuchthatQ=kP, where

kP=P+P+Pktimes=kP.E98

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 tZ and calculates tP.

  3. Bob chooses sZ and calculates sP.

  4. Alice let public tP and keep private t.

  5. Bob let public sP and 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 P be a generator of Ea,bn. The analogue of the subgroup Fp of 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,bn of finite order we can consider a Diffie-Hellman system on G=<P> which is cyclic. For this construction to have a cryptographic interest, logPtP=t must 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,bn be the point representing the message m, to encrypt Pm:

  1. Key generation algorithm

    • Bob chooses the private key tZ known only to him.

    • d,PEa,bnandR=tP are 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.E99

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

5.5 Coding example

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

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

R2=a0+a1εa0a1F2d.E100

We consider the elliptic curve on the ring R2 given by the equation:

Y2Z+XYZ=X3+aX2Z+bZ3.E101

where a,b in R2 and b is invertible in R2. Each element of Ea,b2 is of the form; X:Y:1 or :1:0, with xF2d. Write:

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

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

F8=01αα2α+1α2+αα2+1α2+α+1E103

Put:

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

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

  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,yiF8 for i=0,1, and Z=0or1, then we set:

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

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

So, we code Q as follows:

If Z=1: Q=c00c10c20c01c11c21d00d10d20d01d11d211.

If Z=0: Q=00c01c11c21d01d11d2110000.

  1. Example: with the same aandb;

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

The elliptic curve Ea,b2 contains 112 elements 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+α:E110
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ε:E111
α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}E112

We consider: P=α:α+α2+αε:1=0100000110101, then G=<P> is of order 28. We attach to each point QG a 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;

01111101100110111110001101010000001010100000110010010110100000001011111000110101000000101011011010100111101101111110101111100011010100000010101011111000110111001111110011100111111001011010011010111001100111111011010100111011010011010100101010110110100000010101001010101101100000110010011110100110101101111111110101111100011010000000010000E113

  • Decryption of this message:

010000011010111010000111011111100110001011111000110111001111110011011011111101010000011010101011000101010110100110101111110011000101000000101011011010100111010000011010111111001100010101100010101010110011100111101001101010110100110101E114

is: hello to abdelhakim.

Advertisement

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.

Advertisement

Acknowledgments

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

References

  1. 1. Boneh D, Franklin M. Identity-based encryption from the Weil pairing. SIAM Journal on Computing. 2003;32(3):586-615
  2. 2. Hoffstein J, Pipher J, Silverman JH. An Introduction to Mathematical Cryptography. Springer, New York, NJ, USA: Undergraduate Texts in Mathematics; 2008
  3. 3. Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation. 1987;48:203-209
  4. 4. Diffie W, Hellman ME. New directions in cryptography. In: IEEE Transactions on Information Theory. Vol. 22. IEEE Xplore; 1976. pp. 644-654
  5. 5. Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security. 2001;1(1):36-63
  6. 6. Tzer-Shyong C, Gwo-Shiuan H, Tzuoh-Pyng L, Yu-Fang C. Digital signature scheme resulted from identification protocol by elliptic curve cryptosystem. In: Tencon ‘02. Proceedings. 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering. Vol. 1. Beijing: IEEE; 2002. pp. 192-195
  7. 7. Shannon CE. Communication theory of secrecy systems. Bell System Technical Journal. 1949;28(4):656-715
  8. 8. Shannon CE. A mathematical theory of communication. Bell System Technical Journal. 1948;27(4):379-423
  9. 9. Beutelspacher A, Rosenbaum U. Projective Geometry: From Fondations to Application. Cambridge: Cambridge University Press; 1998
  10. 10. Hartshorne J. Algebraic Geometry. Vol. 52. Springer-Verlag, GTM; 1977
  11. 11. Lang S. Algebraic Number Theory. New York: Springer; 1986
  12. 12. Lenstra AK, Lenstra HW Jr, editors. The Development of the Number Field Sieve, Volume 1554 of Lecture Notes in Mathematics. Berlin: Springer-Verlag; 1993
  13. 13. Joux A. A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology. 2004;17(4):263-276
  14. 14. Joux A, Pierrot C. Improving the Polynomial Time Precomputation of Frobenius Representation Discrete Logarithm Algorithms Simplified Setting for Small Characteristic Finite Fields. Springer-Verlag; 2014
  15. 15. Joux A, Vitse V. Elliptic curve discrete logarithm problem over small degree extension fields application to the static Diffie-Hellman problem on EFq5. Journal of Cryptology. 2013;26(1):119-143
  16. 16. Maurer UM, Wolf S. Diffie Hellman oracles. In: Crypto, 96, LNCS. 1109. Springer-Verlag; 1996. pp. 268-282
  17. 17. Menezes AJ, Okamoto T, Vanstone SA. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory. 1993;39(5):1639-1646
  18. 18. Popescu C. An identification scheme based on the elliptic curve discrete logarithm problem. In: Proceedings of the Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region. Vol. 2. Beijing: IEEE; 2000. pp. 624-625
  19. 19. Fontein F. Elliptic Curves over Rings with a Point of View on Cryptography and Factoring. Vol. 28. Company, Reading, Massachusetts: Diplomarbeit, Carl von Ossietzky Universität Oldenburg Diplomstudiengang Mathematik; 2005
  20. 20. Silverman JH. Advanced topics in the arithmetic of elliptic curves. In: Volume 151 of Graduate Texts in Mathematics. Springer; 1994
  21. 21. Silverman JH. The arithmetic of elliptic curves. In: Graduate Texts in Mathematics. Vol. 106. Springer; 1986
  22. 22. Semaev I. New algorithm for the discrete logarithm problem on elliptic curves. Computer Science and Security. 2015; Cryptology ePrint Archive, Report 2015/310
  23. 23. Elhassani M, Chillali A, Mouhib A. Elliptic curve and lattice cryptosystem. In: Proceedings - 2019 International Conference on Intelligent Systems and Advanced Computing Sciences. ISACS; 2019
  24. 24. Boulbot A, Chillali A, Mouhib A. Elliptic curves over the ring R. Boletim da Sociedade Paranaense de Matematica (BSPM). 2020;38(3):193-201
  25. 25. Sahmoudi M, Chillali A. Elliptic curve on a family of finite ring. WSEAS Transactions on Mathematics. 2019;18:415-422
  26. 26. Sahmoudi M, Chillali A. SCC-cryptosystem on an algebraic closure ring. Journal of Discrete Mathematical Sciences and Cryptography. 2019. DOI: 10.1080/09720529.2019.1624338
  27. 27. Chillali A. Identification methods over. In: ICACM’11 Proceedings of the 2011 International Conference on Applied & Computational Mathematics, ACM Digital Library. Recent Researches in Applied and Computational Mathematics. 2011. pp. 133-138
  28. 28. Hassib MH, Chillali A, Elomary MA. Special ideal ring A3 and cryptography. In: Proceedings of the International Conference JNS3. IEEE; 2013. pp. 1-4
  29. 29. Tadmori A, Chillali A, Ziane M. The binary operations calculus in Ea,b,c. International Journal of Mathematical Models and Methods in Applied Sciences. 2015;9:171-175
  30. 30. Chillali A. The Jε,n-invariant of EA,Bn. In: Recent Advances in Computers, Communications, Applied Social Science and Mathematics -Proceedings of ICANCM’11, ICDCC’11, IC-ASSSE-DC’11. 2011
  31. 31. Tadmori A, Chillali A, Ziane M. Elliptic curve over ring A4=F2dε;ε4=0. Applied Mathematical Sciences. 2015;9(35):1721-1733
  32. 32. Bosma W, Lenstra H. Complete system of two addition laws for elliptic curved. Journal of Number Theory. 1995;53:229-240
  33. 33. Chillali A. Cryptography over elliptic curve of the ring Fqε,ε4=0. World Academy of Science, Engineering and Technology. 2011;5:917-919
  34. 34. Hassib MH, Chillali A, Elomary MA. Elliptic curves over a chain ring of characteristic 3. Journal of Taibah University for Science. 2014;9(3):276-287
  35. 35. Tadmori A, Chillali A, Ziane M. Normal form of the elliptic curve over the finite ring. Journal of Mathematics and System Science. 2014;4:194-196
  36. 36. Tadmori A, Chillali A, Ziane M. Elliptic curve over SPIR of characteristic two. In: Proceeding of the 2013 International Conference on Applied Mathematics and Computational Methodes. 2013. pp. 41-44
  37. 37. Okamoto T, Uchiyama S. A new pubic-key cryptosystem as secure as factoring. In: Eurocrypt, 98, LNCS. 1403. Springer-Verlag; 1998. pp. 308-318
  38. 38. Washington LC. Elliptic curves number theory and cryptography. In: Discrete Mathematics and its Applications. Chapman and Hall/CRC; 2003

Written By

Abdelhakim Chillali and Lhoussain El Fadil

Reviewed: 25 July 2020 Published: 10 September 2020