Elliptic curve form on a field.
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.
- elliptic curve
- finite ring
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 . 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 , so that the only available algorithms are those for all groups.
In , Elhassani et al. have built an encryption method based on DLP and Lattice. Boulbot et al. in  have studied elliptic curves on a non-local ring to compare these curves on local and non-local rings, while in , 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 .
In this chapter, and are a positive integers and is a power of a prime natural number .
2. The ring
2.1 Internal laws in
Corollary 2.1 Let , then where
By formula (2), we have
Under the same hypotheses of the corollary (2.1) and by an analogous proof, we have the following corollary:
Corollary 2.2 , where
Lemma 2.3 Let the inverse of . Then
Let be the inverse of . Then by formula (2), we have
which means that,
Lemma 2.4 The non inverse elements in are the elements of the form where for all
Let . By lemma (2.3), is invertible in if and only if is invertible in As is a field, this means .
Corollary 2.5 The ring is local, with maximal ideal .
Let , we denote:
Corollary 2.6 et are two ring homomorphisms.
Note that in addition, for every ,
So, and are tow rings morphisms.
Theorem 2.7 Let be an integer,
, , , and be elements of with:
then, and therefore,
2.2 Primitive triples
Definition 2.8 Let be a ring. We say that an element is primitive if: . The set of these primitive triplets will be denoted .
Remark 2.9 The equality means that there exists such that .
Proposition 2.10 Let be a local ring, then is a primitive triple if and only if at least one of the elements , , and is invertible in .
Suppose that and are not invertible in , then:
where is the unique maximal ideal of , hence
which contradicts that is a primitive triple.
Conversely, suppose, for example, that is invertible in , then , so .
Remark 2.11 If is a field, then an element is primitive if and only if .
2.3 The projective plane on a finite ring
Let is a ring. The projective plane on is the set of equivalence classes of modulo; the equivalence relation defined by:
We denote the projective plane on by , it is the quotient set , and we write for the equivalence class of . Thus, we have:
Example 2.12 We Consider the finite ring where is an indeterminate satisfying . The group of units for this ring is .
As this ring is local with maximal ideal , then an element of is non primitive if and only if As one can see, there are eight elements which are not primitive, and therefore the set contains primitive triples as given below:
Let and be two elements in , then:
so every class in contains two representatives, that is, the projective plane contains exactly the following 28 elements:
3. Elliptic curve over
In this section, we study the elliptic curves defined on finite local rings of characteristic a prime number p;
A projective Weierstrass equation on is an equation of the form:
A affine Weierstrass equation on is an equation of the form:
3.1 Elliptic curve form
is called the discriminant of and its – invariant.
Remark 3.1 On the field , we denote the discriminant by and the j-invariant by , while on the ring , we denote the discriminant by and the j-invariant by .
We have and .
Definition 3.2 Let be a finite ring and let An elliptic curve on corresponding to a, which we write , is the set of zeros in the projective plane of the Weierstrass Eq. (3), for which the discriminant is invertible in .
Remark 3.3 According to the characteristic of the ring ; we have the following cases:
If and then:
for , with .
If then has one of the following forms:
for , with .
for with non invertible and
If then has one of the following forms:
for , with .
for , with .
Remark 3.4 A projective elliptic curve on a field has one of the following normal forms (Table 1):
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 , according to the normal form.
Using Bosma and Lenstra’s theorem see , we can deduce the explicit formulas for the commutative additive law of the group . The results are given in the next theorems following the values of the characteristic of ring [33, 34, 35, 36]. Let
Theorem 3.5 [Characteristic two case]:
Theorem 3.6 [Characteristic three case]:
Theorem 3.7 [The case where the characteristic is different from two and from three]:
4. Elliptic curve on where
The objective of this chapter is to study elliptic curves defined by a Weierstrass equation with coefficients in a ring such that . We denote it by Let
4.1 The morphisms et
Lemma 4.1 The application
is a surjective group homomorphism.
is well defined because is a morphism of rings. According to theorem (2.7), we have , with
The coefficients , and are the partial derivatives of the function
calculated starting from which are not all equal to zero and deducing the existence of . Hence, est surjectif.
Using corollary (2.6), we deduce that is a group homomorphism.
Lemma 4.2 For all
As , we have
This yields .
Lemma 4.3 The application
is an injective group homomorphism.
The application is injective by construction.
Let and be two elements in , then:
so, using theorem (3.7),
Thus, is an injective group homomorphism.
4.2 Main applications
In this subsection, we consider a prime which does not divide , where
Corollary 4.4 Let , then
We deduce that where which proves that
Lemma 4.6 If do not divide , then there exists a unique homomorphism
for which the following diagram is commutative; (named Diagram(d)).
Let we have
Hence, there is a unique homomorphism
which makes the diagram(d) commutative.
Theorem 4.7 If do not divide , then there exists a unique homomorphism
Let as it exists checking Then,
According to Lemma (4.6), there is a unique homomorphism
which makes the following diagram commutative; (named Diagram(d’)):
Let , then there exists such that So,
Theorem 4.8 If do not divide , then .
admits an inverse application
As, , then we have
Corollary 4.9 If do not divide , then
Corollary 4.10 If do not divide , then
Corollary 4.11 If do not divide , then
According to Haas’ theorem, we have:
In this section, we are interested in ECC using elliptic curves over the ring .
5.1 The discrete logarithm on
The discrete logarithm problem that we denote DLP, (Discrete logarithm problem), is a generally difficult problem which depends on the considered group . 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 be a finite cyclic group of order and two elements of . We call discrete logarithm of base of the only element in such that The discrete logarithm for elliptic curves is defined in an analogous way to be, the only element in such that , where are two points of an additive subgroup of
By using the isomorphism proved given in theorem (4.8), we get the results gathered in the next theorem:
Theorem 5.2 If does not divide , then.
The problem of the discrete logarithm on the elliptic curve is equivalent to that of
If the problem of the discrete logarithm on is trivial, then it is also trivial on the elliptic curve
5.2 Cryptography based on elliptic curves
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 , where 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 where 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 . 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 a large integer, and The discrete elliptical logarithm problem (DLEP) consists in finding , where
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).
They choose on a large integer ,
Alice chooses and calculates
Bob chooses and calculates
Alice let public and keep private
Bob let public and keep private
Then, Alice and Bob build their common secret key
Unlike the classic Diffie-Hellman algorithm, we do not ask that be a generator of The analogue of the subgroup of order is the cyclic subgroup of generated by the point
As soon as we have a group and an element of finite order we can consider a Diffie-Hellman system on which is cyclic. For this construction to have a cryptographic interest, must be not easy to calculate.
is not always cyclical.
If, Oscar (program) is giving , then it is able to solve the discrete elliptical logarithm problem and find
5.4 Elliptical ElGamal cryptosystem
Let be the point representing the message m, to encrypt
Key generation algorithm
Bob chooses the private key known only to him.
Alice Randomly chooses
She also calculates
Then, he makes public or
To decrypt received message Bob calculates:
Now, Oscar encounters the discrete elliptic logarithm problem, because to decipher the message he must know (i.e.; calculate such that ).
5.5 Coding example
Let be a positive integer, we consider the quotient ring where is the finite field of order .
Then the ring is identified with the ring , where , i.e.,
We consider the elliptic curve on the ring given by the equation:
where in and is invertible in Each element of is of the form; or with . Write:
Let be the elliptic curve over and consider the irreducible polynomial in Let be such that in then is a vector space base of over
We have: Consider of order and consider the subgroup , generated by to encrypt and decrypt our messages.
Coding of elements of
We will give a code to each element where defined as follows:
If where for and then we set:
where is the primitive root of the irreducible polynomial and .
So, we code as follows:
Example: with the same
The elliptic curve contains elements to know:
We consider: then is of order 28. We attach to each point a letter of the alphabet and a code. We collect the results in the following Table 2:
|mP||Code for mP||Symbol|
5.6 Encryption and decryption procedures
The encryption of our message “for the elliptical curve”, is;
Decryption of this message:
is: hello to abdelhakim.
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:
The generalization of Hass’s theorem, corollary 4.9.
The result of the corollary 4.11, then in , we have the result of the Proposition 3.12.
The authors thank professor Karim Mounirh for his correcting typographical, grammatical, spelling, and punctuation errors to ensure the clear and accurate communication.