Department of Mathematics
1Sidi Mohamed Ben Abdellah University, Faculty of Science Dhar El Mahraz
2Sidi Mohamed Ben Abdellah University, FP, LSI, Taza
Atlas, Fez, postcode 1796, Fez, Morocco
MOROCCO
Abstract: Let Fqbe the nite eld of qelements, where qis a prime power. In this paper, we study the
Montgomery curves over the ring Fq[X]
hX2−Xi, denoted by MA,B(Fq[X]
hX2−Xi);(A,B)∈(Fq[X]
hX2−Xi)2.
Using the Montgomery equation, we dene the Montgomery curves MA,B(Fq[X]
hX2−Xi)and we give a bijection
between this curve and product of two Montgomery curves dened on Fq. Furthermore, we study the
addition law of Montgomery curves over the ring Fq[X]
hX2−Xi. We close this paper by introducing a public key
cryptosystem which is a variant of the ElGamal cryptosystem on a Montgomery curves over the same ring.
Key-Words: Montgomery curves, Finite ring, Cryptography, ElGamal.
1 Introduction
Let Fqbe the nite eld of order q=pnwhere
nis a positive integer and pis a prime number.
The ring Fq[X]
hX2−Xican be identied to the nite ring
Fq[e],e2=e. The objective of this article is the
search for new groups of points of a Montgomery
curve on a nite ring, for use in cryptography. In
[10], Montgomery introduced a new elliptic curve
model what became known as Montgomery curves
and the Montgomery scale as way to speed up
Lenstra’s elliptic-curve factorization method [8].
Boulbot et al. study the arithmetic of the ring
Fq[e], in particular they show that this ring is
not a local [2]. In section 3, we dene the
Montgomery curves MA,B(Fq[e]) over this ring, we
study Montgomery equation which allows us to de-
ne two Montgomery curves: M
π
0(A),
π
0(B)(Fq)and
M
π
1(A),
π
1(B)(Fq)dened over the nite eld Fq. In
the next of this section, we classify the elements
of MA,B(Fq[e]) and we give a bijection between
the two sets: MA,B(Fq[e]) and M
π
0(A),
π
0(B)(Fq)×
M
π
1(A),
π
1(B)(Fq), where
π
0and
π
1are two surjec-
tive morphisms of rings dened by:
π
0:Fq[e]→Fq
x0+x1e7→ x0
and
π
1:Fq[e]→Fq
x0+x1e7→ x0+x1.
We study the addition law of Montgomery curves
over the ring Fq[e]. We nish this paper by in-
troducing a new public key cryptosystem which is
a variant of the ElGamal cryptosystem [3] on a
Montgomery curves over the ring Fq[e]. For more
works in this direction we refer the reader to [1].
2 The ring Fq[e],e2=e
An element in Fq[e]is represented by x0+x1e
where (x0,x1)∈Fq.
The arithmetic operations in Fq[e]can be decom-
posed into operations in Fqand they are computed
as follows:
X+Y= (x0+y0)+(x1+y1)e
X.Y= (x0y0)+(x0y1+x1y0+x1y1)e,
where X=x0+x1eand Y=y0+y1e. Let us recall
the following results [1, 2]:
•(Fq[e],+,.)is a nite unitary commutative
ring.
•Fq[e]is an Fq-vector space of dimension 2with
Fq-basis {1,e}.
•X.Y= (x0y0) + ((x0+x1)(y0+y1)−x0y0)e.
•X2=x2
0+ ((x0+x1)2−x2
0)e.
•X3=x3
0+ ((x0+x1)3−x3
0)e.
El Gamal Cryptosystem on a Montgomery
Curves Over Non Local Ring
1MOHA BEN TALEB ELHAMAM, 1ABDELALI GRINI, 2ABDELHAKIM CHILLALI,
1LHOUSSAIN EL FADIL
Received: May 10, 2021. Revised: January 13, 2022. Accepted: February 8, 2022. Published: March 2, 2022.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.13
Moha Ben Taleb Elhamam, Abdelali Grini,
Abdelhakim Chillali, Lhoussain El Fadil
E-ISSN: 2224-2880
85
Volume 21, 2022
• Let X=x0+x1e∈Fq[e], then X∈(Fq[e])×(the
multiplicative group of Fq[e]) if and only if
x06=0and x0+x16=0. The inverse is given
by:
X−1=x−1
0+ ((x0+x1)−1−x−1
0)e.
• Let X∈Fq[e], then Xis not invertible if and
only if X=xe or X=x−xe, such that x∈Fq.
•Fq[e]is a non local ring.
•
π
0and
π
1are two surjective morphisms of
rings.
3 Montgomery curves over the ring
Fq[e],e2=e
In this section, the elements X,Y,Z,Aand Bare in
the ring Fq[e]such that X=x0+x1e,Y=y0+y1e,
Z=z0+z1e,A=A0+A1eand B=B0+B1ewhere
x0,x1,y0,y1,z0,z1,A0,A1,B0and B1are in Fq. We
dene a Montgomery curve over the ring Fq[e], as
a curve in the projective space P2(Fq[e]), which is
given by the equation:
BY 2Z=X3+AX2Z+XZ2,
where Aand Bare parameters satisfying the con-
dition that ∆=B(A2−4)is invertible in Fq[e].
We denote this curves by: MA,B(Fq[e]), and we
write:
MA,B(Fq[e]) = {[X:Y:Z]∈P2(Fq)|BY 2Z=X3+
AX2Z+XZ2},
there is a unique point O= [0:1:0]at infnity in
MA,B: it is the only point on MA,Bwhere Z=0.
Proposition 1. Let ∆0=B0(A2
0−4)and ∆1= (B0+
B1)((A0+A1)2−4). Then,
∆=∆0+ (∆1−∆0)e.
Proof. We have:
∆=B(A2−4)
= (B0+B1e)[(A0+A1e)2−4]
=∆0+ (∆1−∆0)e.
Corollary 1. ∆is invertible in Fq[e]if and only if
∆06=0and ∆16=0.
Using Corollary 1, if ∆is invertible in Fq[e],
then M
π
0(A),
π
0(B)(Fq)and M
π
1(A),
π
1(B)(Fq)are two
projective Montgomery curves over the nite eld
Fq, and we notice:
M
π
0(A),
π
0(B)(Fq) = {[x:y:z]∈P2(Fq)|B0y2z=x3
+A0x2z+xz2}
M
π
1(A),
π
1(B)(Fq) = {[x:y:z]∈P2(Fq)|(B0+B1)
y2z=x3+ (A0+A1)x2z+xz2}
In [2] Boulbot et al. have showed the following
proposition:
Proposition 2. Let X,Yand Zin Fq[e], then [X:Y:
Z]∈P2(Fq[e]) if and only if [
π
i(X):
π
i(Y):
π
i(Z)] ∈
P2(Fq), where i∈ {0,1}.
Theorem 2. Let X,Yand Zbe in Fq[e], then
[X:Y:Z]∈MA,B(Fq[e]) if and only if [
π
i(X):
π
i(Y):
π
i(Z)] ∈M
π
i(A),
π
i(B)(Fq), for i∈ {0,1}.
Proof. We have:
BY 2Z= (B0+B1e)(y0+y1e)2(z0+z1e)
=B0y2
0z0+ [(B0+B1)(y0+y1)2(z0+z1)−B0
y2
0z0]e
X3= (x0+x1e)3
=x3
0+ [(x0+x1)3−x3
0]e
AX2Z= (A0+A1e)(x0+x1e)2(z0+z1e)
=A0x2
0z0+ [(A0+B1)(x0+x1)2(z0+z1)−A0
x2
0z0]e
XZ2= (x0+x1e)(z0+z1e)2
=x0z2
0+ [(x0+x1)(z0+z1)2−x0z2
0]e.
As {1,e}is an Fq-basis of the vector space
Fq[e],
then: BY 2Z=X3+AX2Z+XZ2if and only if
B0y2
0z0=x3
0+A0x2
0z0+x0z2
0
and
(B0+B0)(y0+y1)2(z0+z1)=(x0+x1)3+ (A0+
A1)(x0+x1)2(z0+z1)+(x0+x1)(z0+z1)2,
so the point [X:Y:Z]is a solution of the
Montgomery equation in MA,B(Fq[e]) if and only
if [
π
i(X):
π
i(Y):
π
i(Z)] is a solution of the same
equation in M
π
i(A),
π
i(B)(Fq)where i∈ {0,1}.
From the Corollary 1 and Proposition 2 we deduce
the result.
Corollary 3. The mappings ˜
π
0and ˜
π
1are well de-
ned, where ˜
π
ifor i∈ {0,1}is given by:
˜
π
i:MA,B(Fq[e]) →M
π
i(A),
π
i(B)(Fq)
[X:Y:Z]7→ [
π
i(X):
π
i(Y):
π
i(Z)]
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.13
Moha Ben Taleb Elhamam, Abdelali Grini,
Abdelhakim Chillali, Lhoussain El Fadil
E-ISSN: 2224-2880
86
Volume 21, 2022
Proof. From the previous theorem, we have
[
π
i(X):
π
i(Y):
π
i(Z)] ∈M
π
i(A),
π
i(B)(Fq)
If [X1:Y1:Z1] = [X2:Y2:Z2], then there exist
γ
∈
(Fq)×such that: X2=
γ
X1,Y2=
γ
Y1and Z2=
γ
Z1,
then:
˜
π
i([X2:Y2:Z2]) = [
π
i(X2):
π
i(Y2):
π
i(Z2)]
= [
π
i(
γ
)
π
i(X1):
π
i(
γ
)
π
i(Y1):
π
i(
γ
)
π
i(Z1)]
= [
π
i(X1):
π
i(Y1):
π
i(Z1)]
=˜
π
i([X1:Y1:Z1]).
4 The classication of elements in
MA,B(Fq[e])
Let MA,B(Fq[e]) be the Montgomery curve BY 2Z=
X3+AX2Z+XZ2over the ring Fq[e]. In this sec-
tion we will classify the elements of the Mont-
gomery curves, into three types, depending on
whether the projective coordinate Zis invertible
or not. The result is in the following proposition.
Proposition 3. The set MA,B(Fq[e]) has the follow-
ing form:
MA,B(Fq[e]) = {[X:Y: 1]|BY 2=X3+AX2+X}
∪ {[0:1:0]}
∪ {[xe :1:ze]|[x:1:z]∈M
π
1(A),
π
1(B)
(Fq)} ∪ {[xe :y−ye :e]|[x:0:1]∈
M
π
1(A),
π
1(B)(Fq)} ∪ {[x−xe :1:z−ze]|
[x:1:z]∈M
π
0(A),
π
0(B)(Fq)} ∪ {[x−xe :
ye : 1 −e]|[x:0:1]∈M
π
0(A),
π
0(B)(Fq)}.
Proof. Let P= [X:Y:Z]∈MA,B(Fq[e])), where
X=x0+x1e,Y=y0+y1eand Z=z0+z1e.
We have two cases of the projective coordinate Z:
1) First case: Zis invertible, then: [X:Y:Z]∼
[X:Y: 1], where ∼is the equivalence relation of
the projective space P2(Fq[e]) [9, p.6] (see also [1,
4, 6, 5, 7]).
2) Second case: Zis no invertible, in this case we
have:
i) Z=ze, where z∈Fq, then:
•If z=0then [X:Y:Z]=[0:1:0], else z6=0:
We have:
π
0([x0+x1e:y0+y1e:ze]) = [x0:y0: 0]∈
M
π
0(A),
π
0(B), then x0=0and y06=0, i.e:
[X:Y:Z]=[xe : 1 +ye :ze]
there are two sub-cases of y∈Fq:
a) y6=−1, then 1+ye is invertible in Fq[e], so we
have: [X:Y:Z]∼[xe :1:ze], where [x:1:z]∈
M
π
1(A),
π
1(B)(Fq).
b) y=1then 1−eis not invertible in Fq[e], so
we have: [X:Y:Z] = [xe : 1 −e:ze], where [x:1:
z]∈M
π
1(A),
π
1(B)(Fq)then necessary z6=0according
to Montgomery equation, hence [X:Y:Z]∼[xe :
y−ye :e],where [x:0:1]∈M
π
1(A),
π
1(B)(Fq)
ii) Z=z−ze, where z∈Fq.
•If z=0then [X:Y:Z]=[0:1:0], else z6=0,
we have
π
1([x0+x1e:y0+y1e:z−ze]) = [x0+x1:
y0+y1: 0]∈M
π
1(A),
π
1(B)then: x0+x1=0and y0+
y16=0, i.e:
[X:Y:Z]=[x−xe :y0+y1e:z−ze]
there are two sub-cases of y0∈Fq:
a) y06=0then y0+y1eis invertible in Fq[e], so we
have:
[X:Y:Z]∼[x−xe :1:z−ze]
b) y0=0then y0+y1eis not invertible in Fq[e],
so we have: [X:Y:Z]=[x−xe :ye :z−ze],
where [x: 0 : z]∈M
π
0(A),
π
0(B)(Fq)then necessary
z6=0according to Montgomery equation, hence
[X:Y:Z]∼[x−xe :ye : 1 −e],where [x: 0 : 1]∈
M
π
0(A),
π
0(B)(Fq)
Corollary 4. ˜
π
0is a surjective mapping.
Proof. Let [x:y:z]∈M
π
0(A),
π
0(B)(Fq), then:
•if y=0then z6=0so [x:y:z]∼[x: 0 : 1]; hence
[x−xe :e: 1 −e]is an antecedent of [x:0:z]
•if y6=0, then [x:y:z]∼[x:1:z]; hence [x−xe :
1 : z−ze]is an antecedent of [x:1:z].
Corollary 5. ˜
π
1is a surjective mapping.
Proof. Let [x:y:z]∈M
π
1(A),
π
1(B)(Fq), then:
•if y=0then z6=0so [x:y:z]∼[x: 0 : 1]; hence
[xe : 1 −e:e]is an antecedent of [x:0:1]
•if y6=0, then [x:y:z]∼[x:1:z]; hence [xe :1:ze]
is an antecedent of [x:1:z].
The next proposition gives a bijection between
the two sets MA,B(Fq[e]) and M
π
0(A),
π
0(B)(Fq)×
M
π
1(A),
π
1(B)(Fq).
Proposition 4. The ˜
π
mapping dened by:
˜
π
:MA,B(Fq[e]) →M
π
0(A),
π
0(B)(Fq)×
M
π
1(A),
π
1(B)(Fq)
[X:Y:Z]7→ ([
π
0(X):
π
0(Y):
π
0(Z)],
[
π
1(X):
π
1(Y):
π
1(Z)])
is a bijection.
Proof. •As ˜
π
0and ˜
π
1are well dened, then ˜
π
is well dened.
•Let ([x0:y0:z0],[x1:y1:z1]) ∈M
π
0(A),
π
0(B)(Fq)×
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.13
Moha Ben Taleb Elhamam, Abdelali Grini,
Abdelhakim Chillali, Lhoussain El Fadil
E-ISSN: 2224-2880
87
Volume 21, 2022
M
π
1(A),
π
1(B)(Fq)), clearly:
˜
π
([x0+(x1−x0)e:y0+(y1−y0)e:z0+(z1−z0)e]) =
([x0:y0:z0],[x1:y1:z1]), hence ˜
π
is a surjective
mapping.
•Let [X:Y:Z]and [X0:Y0:Z0]are elements of
MA,B(Fq[e]), where X=x0+x1e,Y=y0+y1e,Z=
z0+z1e,X0=x0
0+x0
1e,Y0=y0
0+y0
1eand Z0=z0
0+
z0
1e,
such that: ˜
π
([X:Y:Z]) = ˜
π
([X0:Y0:Z0]),
then:
[x0:y0:z0]=[x0
0:y0
0:z0
0]
and
[x0+x1:y0+y1:z0+z1]=[x0
0+x0
1:y0
0+y0
1:z0
0+z0
1],
then there exist (k,l)∈(F∗
q)2such that:
(x0
0=kx0
y0
0=ky0
z0
0=kz0
and (x0
0+x0
1=l(x0+x1)
y0
0+y0
1=l(y0+y1)
z0
0+z0
1=l(z0+z1)
So (x0
1= (l−k)x0+x1
y0
1= (l−k)y0+y1
z0
1= (l−k)z0+z1
Then:
(X0=kx0+ ((l−k)x0+x1)e= (k+ (l−k)e)X
Y0=ky0+ ((l−k)y0+y1)e= (k+ (l−k)e)Y
Z0=kz0+ ((l−k)z0+z1)e= (k+ (l−k)e)Z
As k+ (l−k)eis invertible in Fq[e], so
[X0:Y0:Z0]=[X:Y:Z], hence ˜
π
is an injective
mapping.
We can easily show that the mapping ˜
π
−1dened
by:
˜
π
−1([x0:y0:z0],[x1:y1:z1]) = [x0+(x1−x0)e:y0+
(y1−y0)e:z0+ (z1−z0)e]
is the inverse of ˜
π
.
Corollary 6. The cardinal of MA,B(Fq[e]) is equal to
the cardinal of M
π
0(A),
π
0(B)(Fq)×M
π
1(A),
π
1(B)(Fq).
5 The group law
Let P= (X1:Y1:Z1)be a point on MA,B(Fq[e])
and [n]P= (Xn:Yn:Zn). By [10], the sum [n+
m]P= [n]P⊕[m]Pis given by the following formu-
las where Ynnever appears.
Addition: n6=m
Xm+n=Zm−n((Xm−Zm)(Xn+Zn) + (Xm+Zm)
(Xn−Zn))2,
Zm+n=Xm−n((Xm−Zm)(Xn+Zn)−(Xm+Zm)
(Xn−Zn))2.
Doubling: n=m
4XnZn= (Xn+Zn)2−(Xn−Zn)2,
X2n= (Xn+Zn)2(Xn−Zn)2,
Z2n=4XnZn((Xn−Zn)2+ ((A+2)/4)(4XnZn)).
6 Cryptography applications
6.1 Cryptography results
From the proposition 4, we have:
•If card(MA;B(Fq[e])) :=nis an odd num-
ber, then n=s×tis the factorization of
n, where s:=card(M
π
0(A);
π
0(B)(Fq)) and t:=
card(M
π
1(A);
π
1(B)(Fq)), hence the cardinal of
MA;B(Fq[e]) is not a prime number.
•The discrete logarithm problem in MA,B(Fq[e])
is equivalent to the discrete logarithm problem in
M
π
0(A);
π
0(B)(Fq)×M
π
1(A);
π
1(B)(Fq).
6.2 ElGamal cryptosystem on a
Montgomery curves over this ring
ElGamal cryptosystem for MA,B(Fq[e]) consists es-
sentially in mapping the operations customarily
carried out in the multiplicative group Zpto the
set of points of a Montgomery curve MA,B(Fq[e]),
endowed with an additive group operation. An
entity chooses and publishes a prime number p
(large), a Montgomery curve MA,B(Fq[e]) and a
point P in MA,B(Fq[e]).
6.2.1 Key creation:
• Choose a secret integer sA.
• Compute QA=sAPin MA,B(Fq[e]).
• Publish the public key QA.
6.2.2 Encryption:
• Choose the plain text P
min MA,B(Fq[e]).
• Choose an ephemeral key k.
• Use Alice’s public key QAto calculate u=kP
in MA,B(Fq[e]) and v=P
m+kQAin MA,B(Fq[e]).
• Send the cipher text (u, v)
6.2.3 Decryption:
Calculate v−sAuin MA,B(Fq[e]). This value is
equal to P
m.
ElGamal cryptosystem is directly based on the
diculty of solving the discrete logarithm prob-
lem over (E,+) of base P. This problem requires to
nd nwhere Q=nP and points P,Qbelong to a set
of points Eof a Montgomery curve MA,B(Fq[e]). It
is known to be computationally dicult and thus
can be utilized to accomplish a more elevated level
of security in cryptosystem.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.13
Moha Ben Taleb Elhamam, Abdelali Grini,
Abdelhakim Chillali, Lhoussain El Fadil
E-ISSN: 2224-2880
88
Volume 21, 2022
References:
[1] Ben Taleb, E.M., Chillali, A., El Fadil,
L., Twisted Hessian curves over the Ring
Fq[e],e2=e, Bol. Soc. Paran, (3s.) v.(40),
doi:10.52699/bspm.15867, (2022).
[2] Boulbot, A., Chillali, A., Mouhib, A., ”Elliptic
Curves Over the Ring R”, Bol. Soc. Paran.,
Vol.38, No.3, 2020, 193-201.
[3] ElGamal, T., A Public Key Cryptosystem and
a Signature Scheme Based on Discrete Log-
arithms, In Proceedings of CRYPTO 84 on
Advances in cryptology. Springer-Verlag New
York, Inc, 1985, pp. 10-18.
[4] Grini, A., Chillali, A., Mouanis, H., The Bi-
nary Operations Calculus in H2
a,d. Bol. Soc.
Paran, Vol.40, 2020, 1-6.
[5] Grini, A., Chillali, A., Mouanis, H., Cryptog-
raphy over twisted Hessian curves of the ring
Fq[
ε
],
ε
2=0. Adv. Math.: Sci. J., vol.10 , no.1,
2021, 235-243.
[6] Grini, A., Chillali, A. &Mouanis, H. A new
cryptosystem based on a twisted Hessian curve
H4
a,d. J. Appl. Math. Comput., 2021.
[7] Grini A., Chillali A., Mouanis H. Cryptogra-
phy Over the Twisted Hessian Curve H3
a,d. In:
Ben Ahmed M., Teodorescu HN.L., Mazri T.,
Subashini P., Boudhir A.A. (eds) Networking,
Intelligent Systems and Security. Smart Inno-
vation, Systems and Technologies, vol. 237.
Springer, Singapore, 2022.
[8] Hendrik, W., Lenstra Jr., Factoring integers
with elliptic curves. Annals of mathe-matics,
1987, pp. 649-673.
[9] Lenstra, H. W., Eliptic Curves and Number-
Theoretic Algorithms. Processing Int.
Congress Math., USA, 1986.
[10] Peter L., Montgomery, Speeding the Pollard
and Elliptic Curve Methods of Facorization,
Mathematics of Computation., vol. 48, 1987,
243-264.
Creative Commons Attribution
License 4.0 (Attribution 4.0
International , CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/li-
censes/by/4.0/deed.en_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.13
Moha Ben Taleb Elhamam, Abdelali Grini,
Abdelhakim Chillali, Lhoussain El Fadil
E-ISSN: 2224-2880
89
Volume 21, 2022
