Machine Translated by Google

See discussions, statistics, and author profiles for this publication at: https://www.researchgate.net/publication/265838050

ECC encryption and decryption with a data sequence

Article · January 2012

CITATIONS READS

18 2,369

2 authors:

Fatima Amounas El Kinani El Hassan

Université Moulay Ismail Université Moulay Ismail, Faculty of Sciences

33 PUBLICATIONS 127 CITATIONS 88 PUBLICATIONS 575 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by El Kinani El Hassan on 13 June 2016.

The user has requested enhancement of the downloaded file.

Machine Translated by Google

Applied Mathematical Sciences, Vol. 6, 2012, no. 101, 5039 - 5047

ECC Encryption and Decryption with

a Data Sequence
F. Amounas1 and EH El Kinani2

1
ROI Group, Moulay Isma¨ÿl University Informatics Department
Faculty of Sciences and Technics
Box 509 Errachidia, Morocco
2A.A Group, Moulay Isma¨ÿl University Mathematics Department
Faculty of Sciences and Technics
Box 509 Errachidia, Morocco

Abstract

The paper describes the basic idea of elliptic curve cryptography

(ECC) and its implementation by applying a data sequence on ECC
encrypted message over the finite field GF(p). We also propose an
algorithm to generate a data sequence and use it to the output of our
cryptosystem. In ECC, we normally start with an affine point noted Pm.
This point lies on the elliptic curve. Here, we will illustrate encryption/
decryption involving the embedding system m ÿ Pm, which imbeds the
characters constituting the message and then subjects it to a proposed
algorithm. Thus by using a data sequence, the present algorithm provides
sufficient strength against crypto analysis and whose performance can
be compared with standard algorithms such as the Rivest-Shamir-
Adleman algorithm (RSA).

Keywords: Elliptic Curve Cryptography, Discrete Logarithm, Cryptosys-

tem, Public Key, Data Sequence, Encryption, Decryption

1 Introduction
The idea of using ECC was introduced by Victor Miller [1] and Neal Kolbitz as
an alternative to established public key systems such as RSA [2]. In 1985, they
proposed a public key cryptosystems analogue of ElGamel encryption scheme
witch used Elliptic Curve Discrete Logarithm Problem (ECDLP) [3].
The application of elliptic curves to the field of cryptography has been relatively
recent. In the paper [4], the authors presented the implementation of ECC by
first transforming the message into an affine point on the elliptic
Machine Translated by Google

5040 F. Amounas and EH El Kinani

curve(EC), and then applying the knapsack algorithm on ECC encrypted message
over the finite field GF(p). The knapsack problem is not secure in the
present standards and more over in the work of the authors in their description
process used elliptic curve discrete logarithm to get back the plain text. This
may form a computationally infeasible problem if the values are large enough
in generating the plain text. In our previous work [5], we provide an examination of the
public-key cryptosystems based on ECC mechanism. In fact, the
transformation of the message into an affine point is explained. A transformed
character is encrypted by ECC technique. In the present work, the output of
ECC algorithm is provided with a values of the sequence generated by the proposed
algorithm. More precisely, this paper presents an algorithm to generate
a data sequence and its application to the output of our cryptosystem. We
illustrates also the implementation of our cryptosystem based into an elliptic
2
curve characterized by the following equation: y 3 = x ÿ x + 16[29].

2 Overview of Elliptic curve Cryptosystem

Elliptic curve cryptosystems (ECCs) include key distribution, encryption algorithm.
The key distribution algorithm is used to share a secret key and the
encryption algorithm enables confidential communication. ECCs are based on
the addition of rational points on a chosen elliptic curve. An elliptic curve
E over the finite field GF(p) where p is a prime, is the set of points (x, y)
satisfying the following equation:

2
E: y 3=x + ax + b, (1)

3
where a, b are integers modulo p, satisfying: 4a + 27b = 0 mod p, and include
an point ÿ called point at infinity.
It is known that rational points form an additive group in addition over the
Elliptic curve shown in the following figure:

Figure.1 Addition rule over an elliptic curve

Machine Translated by Google

ECC encryption and decryption with a data sequence 5041

When points P and Q on the elliptic curve E shown in Figure.1 are added, the result is defined
as the point S obtained by inverting the sign of the y-coordinate of point R, where R is the
intersection of E and the line passing through P and Q. If P and Q are at the same position,
the line is the tangent of E at P. Moreover, the sum of the point at infinity and a point P is
defined as point P itself.

3 Proposed Method Description

The proposed algorithm requires that we generate a series of vectors called Si .
The procedure is shown in algorithm (1). Then, the result of this procedure is applied to the
output of ECC.

3.1 Algorithm (1) for generating the sequence

1. Let P is a point generator and n is order of P

2. Consider the sequence for i=0 to n values

3. Convert each element of the sequence in base 3, and let m be a number

of digits: For example: n =34 =ÿ we obtain m=4

0000
0001
0002
..
.
1021

4. Represent above form in (n+1)×m matrix ( M)

ÿ a0,0 a0,1 · · · a0,mÿ1 a1,0 ÿ

a1,1 · · · a1,mÿ1
M= .. ..
. .
ÿÿÿÿÿ ÿÿÿÿÿ

an,0 an,1 · · · an,mÿ1

5. Circularly shifting each row of M by one element to the right [ai,0 ai,1 ai,2
ai,mÿ1] =ÿ [ai,mÿ1 ai,0 ai,1 ai,2 ai,m ÿ2]

6. The sequence formed is:

S : [S0 = [a0,mÿ1 a0,0 a0,1 a0,2 · · · a0,mÿ2], S1 = [a1,mÿ1 a1,0 a1,1 a1,2 · · · a1,mÿ2], · · · , Sn =
[an,mÿ1 an,0 an,1 an,2 · · · an,mÿ2]]
Machine Translated by Google

5042 F. Amounas and EH El Kinani

3.2 Algorithm (2) ECC by using a generated sequence

Suppose that we have some elliptic curve E defined over a finite field GF(p) and that E and
a point P ÿ E are publicly known, as is the embedding system m ÿ Pm ; which imbed plain
text on an elliptic curve E. Then, when Alice wants to communicate secretly with Bob, they
proceed in the following way: -Encryption Step 1. Bob chooses a random integer a, and
publishes the
point aP (while a remains secret ).

Step 2. Alice chooses her own random integer l and computes the pair of points:

P1(x1, y1) = lP
P2(x2, y2) = Pi + l(aP)

Step 3. Read the sequence generated from algorithm (1).

Step 4. Calculate S(x1, y1) and S(x2, y2) with S is a corresponding sequence value in step3.
Then, the ciphertext is as follows:

Cm = (S(x1, y1), S(x2, y2))

Step 5. Alice converts Cm to binary form with: 0 =ÿ 00, 1=ÿ 01 and sends to Bob , 2 =ÿ 10
a series of bits.
- Decryption To
, a, the base point P,a, b,
decrypt the message, Bob knows the sequence of Si his own secret
p values of the ECC. Bob receives the encrypted message Cm = (S(x1, y1), S(x2, y2))

Step 1. Converts a binary form to series of digits as well as: 00 =ÿ0, 01 =ÿ1, 10 =ÿ2
Step 2. Transforms
Cm into groups of 2m.
Step 3. Extract a group of m digits in sequence of step2.
Step 4. Circularly shifting this sequence of m digits by one element to the left Step 5.
Convert
a sequence to decimal form, and store a value in k For example: 0100 will in the
3 +1ÿ3 2 +0ÿ3 1 +0ÿ3 0
form: 0 ÿ 3 = 9 =ÿ k= 9

Step 6. Obtain (k+1)P from pre-computed and stored point (k+1)P=(x1, y1).
Step 7. The procedure is repeated for the next element of the sequence of step 3 for the
recovery of S(x2, y2).
Step 8. The procedure is repeated for the next group of step 2, which was not visited
earlier.
Recall that lP is represented by (x1, y1) and Pi + l(aP) is represented by S(x2, y2). In
order to pull out Pi from Pi + l(aP), Bob applies his secret key a
Machine Translated by Google

ECC encryption and decryption with a data sequence 5043

and calculates a(lP) from the first part of the pair, then subtracts it from the
second part to obtain: Pi + l(aP) ÿ a(lP) = Pi + laP ÿ laP = Pi , and then
reverses the embedding to get back the message.

4 Implementation of the proposed algorithm

The elliptic curve using here is given by the following equation:
2
y 3=x ÿ x + 16[29]. (2)

The base point P is selected as (5, 7). The table below represents a set of all
points in the curve:

(5, 7) (28, 4) (18, 1) (22, 12)

(6, 20) (13, 5) (2, 14) (21, 11)
(23, 3) (10, 7) (14, 22) (16, 23)
(7, 27) (1, 4) (0, 4) (0, 25)
(1, 25) (7, 2) (16, 6] (14, 7)
(10, 22) (23, 26) (21, 18] (2, 15)
(13, 24) (6, 9) (22, 17] (18, 28)
(28, 25) (5, 22) ÿ

Table.1. A set of all points on EC.

Here the choosing curve contains 31 points with P is the point generator. It
is the point witch represents the letter 'a', as well as 2P represents the letter
'b',..., 31P represents space.
In our case we use the letters 'a' to 'z' with some of the other symbols like ';',
',', '.' '?' ,and space for illustration purposes only.

Suppose that Alice wants to encrypt and transmit a message "hello" to Bob,
she does the following:
Step 1. Generating sequence data
- P is a point generator with order n=31. Then m=4.
- Convert a sequence 0 to n to the form:

0000
0001
0002
0011
..
.
1011

- Represent the above form in (32*4) matrix:

Machine Translated by Google

5044 F. Amounas and EH El Kinani

- Circularly shifting each row of M by one element to the right:

Machine Translated by Google

ECC encryption and decryption with a data sequence 5045

- The sequence formed is:

[0000], [1000], [2000], [0001], [1001], [2001], [0002], [1002], [2002], [0010], [1010], [2010],
[0011], [1011], [2011], [0012], [1012], [2012], [0020], [1020], [2020], [0021], [1021], [2021 ],
[0022], [1022], [2022], [0100], [1100], [2100], [0101], [1101]
Step.2. Crypting / Decrypting Hence
we shall assume that l = 13, and a = 24. Plaintext is 'h', Therefore: PB = aP = 24(5, 7) = (2,

15)

Pi= (21, 11)

lPB = 13(2, 15) = (28, 4)

Pi + lPB = (10, 7) lP =

13(5, 7) = (7, 27).

Encrypted version of the message is: Cm= (S(7, 27), S(10, 7)), where x1 = 7, y1 = 27, x2 =
10, and y2= 7.
Apply algorithm (1) for generating the sequence S: S(7, 27) =

0011 and S(10, 7) =0010 Hence, the

message is transformed into the message : 00110010 Then, the transmitted
message is : 0000010100000100

The recovery of cipher text is done as follows:

- extract four digits on the cipher text: 0011

- Circularly shifting this sequence by one digit to the left: 0110

- Convert a sequence to decimal form, and store a value in k

3 ie 0110 will form: 0 ÿ 3 2 + 1 ÿ 3 1 + 1 ÿ 3 0 + 0 ÿ 3 = 12 =ÿ k=12

- Obtain (k+1)P from pre-computed and stored point (k+1)P=(x1, y1).

Therefore (x1, y1) = (7, 27) represents kP.
Similarly, other point is recovered by applying a data sequence algorithm1.
Thus we are able to recover the encrypted version: ((7, 27), (10, 7))
From this Pi should be retrieved using Bobs private key:

24(7, 27) = (28, 4)

Pi= (10, 7) - (28, 4) = (21, 11)

Now reverse the embedding to get back the message. Thus we retrieve the character 'h'.

The table below shows the results for the message "hello". Encryption with sequence data
incorporated is shown in Table.2 and decryption is shown in Table.3.
Machine Translated by Google

5046 F. Amounas and EH El Kinani

Character Point Pi Encryption before EncryptionAfter

sequence data applied sequence data applied
Cm = (lP, Pi + lPB) Cm = (S(x1, y1), S(x2, y2))
h (21, 11) ((7, 27),(10, 7)) 00110010
e (6, 20) ((7, 27),(2, 14)) 00110002
l (16, 23) ((7, 27),(1, 4)) 00111011
l (16, 23) ((7, 27),(1, 4 )) 00111011
o (0, 4) ((7, 27),(1, 25)) 00111012

Table.2. Encryption before and after applying sequence data

Hence the message "hello" is transformed into the message:

0011001000110002001110110011101100111012
So, Alice sends to Bob a series of bits as follows:
00000101000001000000010100000010000001010100010100000101010001010000010101000110

When Bob received the above series of bits, he transforms it into series of
digits: 00 =ÿ 0, 01=ÿ 1, 10=ÿ 2. Then, Bob separates the series of digits in
groups of eight digits and reverses the procedure to recover the coordinates of
points.

Decryption of each group is shown in Table.3:

Sequence Reversal of sequence Decryption Symbol

((7, 27), ((7, 27),(10, 7)) (21, 11) 00110010 h
(16, 23)(2, 14)) (6, 20) 00110002 ((7, 27),(1, 4) ) e
00111011 00111011 ((7, 27),(1, 4)) (16, 23) l
((7, 27),(1, 25)) (0, 4) l
00111012 o

Table.3. Decryption with reversal of sequence

After decrypting the received message, we obtain the plain text "hello".

5 Conclusions
In this work based on the idea of the ECC, we provide a new method to secure
the output of ECC . More precisely, we establish an algorithm to generate a
sequence data and use it to the output of our cryptosystem.
Here we apply a data sequence generated by the proposed algorithm to the
output of ECC, witch is new to our knowledge. Finally, we like to point out
that the use of sequence data will provide better performance in this regard.
Machine Translated by Google

ECC encryption and decryption with a data sequence 5047

References
[1] VS Miller. Use of Elliptic Curves in Cryptography. Advances in Cryptology
CRYPTO'85, LNCS.218, New York, Springer-Verlag, pp. 417-426,
1986.

[2] N. Demytko. A New Elliptic Curve Based Analogue of RSA. in T. Helle-seth,

editor, Advances in CryptologyEurocrypt'93, Springer-Verlag, New
York, pp. 40-49, 1994.

[3] Dahab, R., and J. Lopez, An Over-view of Elliptic Curve Cryptography,

Institute of Computing State University of Campinas Brazil, Brazil, 2000

[4] R. Rajaram Ramasamy, M. Amutha Prabakar, M. Indra Devi, and M.

Suguna, Knapsack based ECC Encryption and Decryption, International
Journal of Network Security, vol. 9, no. 3, pp. 218-226, Nov. 2009.

[5] F. Amounas, EH El Kinani and A. Chillali, An application of discrete

algorithms in asymmetric cryptography, International Mathematical Forum, Vol.
6, no. 49, pp. 2409 - 2418, 2011

Received: January, 2012

View publication statistics