A New Modified Cryptosystem Based on Menezes

Vanstone Elliptic Curve Cryptography Algorithm that

Uses Characters' Hexadecimal Values

MeltemKURT Tank YERLiKAYA

Computer Engineering Department Computer Engineering Department
Kocaeli University Trakya University
Kocaeli, Turkey Edirne, Turkey
[email protected] [email protected]

Abstract-This paper proposes a new approach to encrypt This paper gives a brief review of the ECC algorithm's
data (message) with new modified version of Menezes Vanstone cryptosystem and Menezes Vanstone elliptic curve
cryptosystem based on elliptic curve. This new version basically cryptosystem, it also describes how to encrypt message using
utilizes the original Menezes Vanstone cryptosystem but we hexadecimal values of characters. Second section gives
added additional features to cryptosystem's encryption method. information about ECC algorithm. In the third section is
According to our encryption method, firstly the message is
mentioned about Menezes Vanstone ECC algorithm and this
divided into blocks that contain only one character, and then
cryptosystem. The fourth section examines modified
each character is converted to hexadecimal format. Hexadecimal
cryptosystem and its implementation in C++. Finally
values of each character have two digits. These two digits allow
conclusion is given the fifth section.
us to express the message as a point. Thus knowledge of each
character's point does not have to be sent to recipient. The paper
explains in detail its implementation in C++. II. BRIEF REVIEW ON THE ECC ALGORITHM

An elliptic curve E takes the general form as:

Keywords-Menezes Vanstone Elliptic Curve Cryptosystem,
Elliptic Curve Cryptography, Cryptology, Encryption, Decryption, E: l = x3 + ax + b [p] (1)
Elliptic Curves, Security
Where a, b are in the appropriate set (rational numbers, real
numbers, integers mod p, etc. ) and x, y are elements of the
I. INTRODUCTION
finite field GF (p), satisfying 4a3 + 27b2 i- 0 (mod p) and p is
Cryptology comes from Greek word "kryptos logos", which known as modular prime integer making the elliptic curve
means "hidden word". It aims to secure communication finite field.
between sender and recipient in the insecure communication
medium like internet. Cryptology is divided into two general There are two basic group operations on elliptic curve
fields, cryptography, the art of secret writing (encryption) and which are point addition and point doubling.
cryptanalysis, the art of deciphering encrypted message
(decryption). A. Point Addition
Addition means that given two points on E and their
In the mid-1980s Miller [I] and Koblitz [2] introduced
coordinates, P = (Xb Yl ) andQ = (X2' Y2) I E (GF (p)), we have
elliptic curves into cryptography. After Lenstra [3] showed to compute the coordinates of a third point R such that:
how to use elliptic curves to factor integers, elliptic curves
played an increasingly important role in many cryptographic P +Q = R
situations are required security and privacy.
(x], Yl ) + (X2' Y2) = (X3, Y3 )
Another reason of using elliptic curves in cryptography is
This is the case where we compute R = P +Q and P i-Q. Point
that they seem to offer a level security needs comparable to
R's coordinates (X3, Y3 ) also L E (GF (p)).
classical cryptosystems that use much larger key sizes. Using
of smaller key sizes is important in the environments where
resources like processing power, storage bandwidth and power
Ie= (yP- yq) /(xp - Xq) (2)
consumption are limited.
Xr = [ Ie 2 - xp - Xq] mod p (3)
Elliptic curve cryptography (ECC) algorithm is an
encryption algorithm. We use its mechanism which is Menezes Yr = [- YP + Ie (xp - xr)] mod p (4)
Vanstone cryptosystem [4] in our study.

ISBN: 978-1-4673-5613-8©2013 IEEE 449

B. Point Doubling Yo = k· a
Point doubling is the addition of a point P on E to itself to (c), Cl ) = k . �
obtain another point R. This is the case where we compute P +
Q but P =Q. Hence we can write R = P + P = 2P.
Yl = Cl . Xl mod p
Yl= Cl . Xl mod p
After calculating these equations, sends plaintext as a point
l (Yo, Yl, Yl) called ciphertext.
Ie = (3x p + a) /2yp (5)
Xr = [A? - 2xp] mod p (6)
C. Decryption
Yr = [- YP + Ie (xp - xr)] mod p (7) Recipient B uses whose secret key a calculating:

(c), Cl ) = a . Yo
-1 -l
x = (y 1 . Cl mod p, Yl . mod p)
Cl
III. MENEZES VANSTONE CRYPTOSYSTEM
The point (Yl . -1 . 1
CI mod p, Yl cz- mod p) represents the
In our study, we used Menezes Vanstone elliptic curve plaintext x.
cryptosystem that is a variant of EIGamal's [5] encryption
system. These systems basically use elliptic curves. However,
IV. THE M ODIFIED CRYPTOSYSTEM
there is one main difference between these two cryptosystem.
This difference is that, in Menezes Vanstone cryptosystem, the In the modified cryptosystem can encrypt not only point but
message to be encrypted is masked instead of embed over E also message according to request of sender. If sender wants to
elliptic curve. This situation indicates that the message must be encrypt the message, the plaintext dimension d is calculated
expression as a point on E elliptic curve when EIGamal's than divided into blocks as the size of plaintext and each block
cryptosystem is used but this is a limiting factor. The message is encrypted by an identical key set K' = {(E', a', a', P'): P' = a' .
is independent from the points on elliptic curve which is a'} that has exactly the same characteristic of the original
Menezes Vanstone ECC cryptosystem. Every block has only
important in terms of security because person who is trying to
one character. After that this character's equivalent of
obtain secret message can guess this situation. In Reference [6]
hexadecimal (base-16) number system is calculated. Every
the authors describe Menezes Vanstone cryptosystem is fast
character's equivalent of hexadecimal value is given in Fig. l.
and simple. Therefore we choose to use Menezes Vanstone
cryptosystem. (')(') nul (')1 soh (')2 stx (')3 etx (')Ii eot (')5 enq (')6 aek (')7 bel

Encryption and decryption methods are for Menezes (')8 bs (')9 ht (,)A nl (')8 vt (,)C np (')0 er (,)E so (,)F Sl
Vanstone elliptic curve cryptosystem as:
1(') d I e 11 del 12 de2 13 de3 111 deli 15 nak 16 syn 17 etb
E is an elliptic curve defined on Zp , P > 3, p is a prime
number or for n > 1 is defined on finite field GF (pTI). E also 18 can 19 em lA sub 18 esc lC fs 10 9s lE rs 1F us
contains a cyclic group H in which the discrete log problem is "
2(') sp 21 ! 22 23 II 21i $ 25 % 26 & 27
impossible.
28 ( 29 ) 2A " 28 + 2C 20 - 2E 2F /
P = Zp* x Zp* and C = E x Zp* x Zp* and define key set K =
{(E, a, a, �): � = a . a} where a I E, the values a and � are 3(') (') 31 1 32 2 33 3 31i Ii 35 5 36 6 37 7
public and, a is secret. k is randomly selected integer, k � ZIHI
38 8 39 9 3A : 38 ; 3C < 30 =
3E > 3F ?
and x L Zp* x Zp*.
Ii(') @ lil A 1i2 8 1i3 C IiIi 0 1i5 E 1i6 F 1i7 G
The process of encryption and decryption has two entities
sender (A) and recipient (B). Both the entities agree upon a, b, 1i8 H 1i9 I IiA J 1i8 K IiC L 1i0 M liE N IiF 0
p, a, n which are called domain parameters.
5(') P 51 a 52 R 53 S 51i T 55 U 56 U 57 W

A. Key Generation 58 X 59 Y 5A Z 58 [ 5C \ 50 I 5E
�
5F -
Recipient B selects a random number a L [1, n-l] and it is ,
6(') 61 a 62 b 63 e 61i d 65 e 66 f 67 9
private key, a is the generator point and n is the order of a,
computes � public key as follows: 68 h 69 i 6A j 68 k 6C I 60 m 6E n 6F 0

�= a· a 7(') P 71 q 72 r 73 s 7Ii t 75 u 76 v 77 w

-
78 x 79 Y 7A z 78 { 7C I 70 } 7E 7F del
B. Encryption
Sender A gets 8's public key �, selects a random number k Fig. I. Hexadecimal values of each character
�[1, n-l], selects the message (plaintext) x = (x], Xl) that
wants to encrypt it then computes: According to Fig. 1, that can be easily shown, each
character's hexadecimal value, is located to the left of

ISBN: 978-1-4673-5613-8©2013 IEEE 450

character's in Fig. 1, has two digits whose units digit indicates Using this equation (Xi = Xli . 16 + X2i) that represents
X2i and tens digit indicates Xli for that reason the character plaintext x' = {(XlX2 . . .,Xn): i = 1, 2, 3... n}.
represented as a point (Xli, x2D, subscript i symbolizes block
number, it is an integer and I <:: i <:: d. However X2i can be one D. An implementation Example
of these letters A, B, C, D, E, and F, in this case hexadecimal For example sender A wants to sent the plaintext "Menezes
value is converted to decimal. These are A--->10, B--->II, Vanstone Elliptic Curve Cryptosystem" to recipient B.
C--->12, D--->13, E--->14, and F--->15.
Every character of plaintext "Menezes Vanstone Elliptic
In Ref. [7] the authors describes how to encrypt the data Curve Cryptosystem" is represented by a point. These values
using Tifinagh alphabet. Although this method is helpful can be shown Fig. 1.
information of transformation of the Tifinagh Characters into
the point of EC, must be sent to recipient information of M:4D---> (4, 13), e:65---> (6, 5), n:6E---> (6, 14), e:65---> (6, 5),
character which has been referred to which point on elliptic z:7A---> (7, 10), e:65---> (6, 5), s:73---> (7, 3), SP:20---> (2, 0),
curve. Consequently, this is security vulnerability. V:76---> (7, 6), a:61---> (6, 1), n:6E---> (6, 14), s:73---> (7, 3),
t:74---> (7, 4), o:6F--->(6, 15), n:6E---> (6, 14), e:65---> (6, 5),
As mentioned before, the key structure is the same with SP:20---> (2, 0), £:45--->(4, 5), 1:6C---> (6, 12), 1:6C---> (6, 12),
Menezes Vanstone ECC. i:69---> (6, 9), p:70--->(7, 0), t:74---> (7, 4), i:69---> (6, 9), c:63--->
(6, 3), SP:20---> (2, 0), C:43---> (4, 3), u: 75---> (7, 5), r:72---> (7,
A. Key Generation 2), v:76---> (7, 6), e:65---> (6, 5), SP:20---> (2, 0), C:43---> (4, 3),
Recipient B selects a random number a' L [1, n'-I] and it is r:72---> (7, 2), y:79---> (7, 9), ), p:70--->(7, 0), t:74---> (7, 4),
private key, a' is the generator point and n' is the order of a', o:6F--->(6, 15), s:73---> (7, 3), y:79--->(7, 9), s:73---> (7, 3), t:74--->
computes � public key as follows: (7, 4), e:65---> (6, 5), m: 6D---> (6, 13)
p' = a'· a' E: l = x3 + 17x + 33 mod 107,
As 4(l7 i + 27(33)2"* 0 mod 107, E is an elliptic curve.
B. Encryption
Sender A gets B's public key W, selects a random number a = 27, a = (5, 55), �= a' a = 27· (5, 55) = (45, 63), k=19,
k' L [1, n'-I], selects the plaintext x'. Then x' sent to the d = 44;
ConverttoPoint function, as shown in Table 1.
As mentioned before, a is generator point on E, we use it
while finding � . It is clear that � must be on E elliptic curve as
TABLE I. CONVERTTOPOINT FUNCTION'S STEPS
given Section II-B, they are bold in Table 2 which gives
Steps Pseudo Code of ConverttoPoint Function information about calculated points on E: l = x3 + 17x + 33
1 d = sizeof (plaintext) IICaleulate d,d is dimension of plaintext mod 107 elliptic curve.
2 for i =1 to d
3 key+- A[i] 2
TABLE II. POINTS ON E: y = x3 + 17x + 33 MOD 107 ELLIPTIC CURVE
4 e[i] = int (key)
Points Points on Elliptic Curve
5 b[i] = e[i]/16 II X2i
1-5 (0,51) (0, 56) (2, 17) (2,90) (3,2)
6 II if b[i] is a letter A--+ 10, B--+ I I, C--+ 12, D--+ 13, E--+ 14, and
6-10 (3,105) (5,52) (5,55) (6,43) (6,64)
F--+15
11-15 (8,50) (8,57) (11,38) (11,69) (12,50)
7 o[i] = e[i]%16 II Xli 16-20 (12,57) (14,33) (14,74) (15,5) (15,102)
8 A[i] - (b[i] , o[iD 21-25 (16,11) (16,96) (17,45) (17,62) (20,53)
26-30 (20,54) (22,26) (22,81) (24,26) (24,81)
This function converts to plaintext's value as x' = (Xli, X2i) than 31-35 (25,51) (25,56) (26,17) (26,90) (30,30)
36-40 (30,77) (33,30) (33,77) (34,2) (34,105)
computes:
41-45 (35,32) (35,75) (37,13) (37,94) (40,37)
46-50 (40,70) (41,23) (41,84) (42,16) (42,91)
y'o = k'· a' 51-55 (44,30) (44,77) (45,44) (45,63) (47,3)
(C'l' C'2) = k' . W 56-60 (47,104) (53,15) (53,92) (55,40) (55,67)
61-65 (58,0) (59,36) (59,71) (60,48) (60,59)
y'li = c\ . Xli mod p 66-70 (61,26) (61,81) (62,22) (62,85) (69,35)
71-75 (69,72) (70,2) (70,105) (73,13) (73,94)
Y'2i= C'2 . X2i mod p
76-80 (75,31) (75,76) (79,17) (79,90) (82,51)
After calculating these equations, every character of the 81-85 (82,56) (84,23) (84,84) (87,50) (87,57)
plaintext as a point (y'o, Y'li' Y'2D is sent n' times. 86-90 (89,23) (89,84) (91,42) (91,65) (92,24)
91-95 (92,83) (93,49) (93,58) (94,41) (94,66)
C. Decryption 96- (95,53) (95,54) (96,21) (96,86) (97,19)
100
Recipient B uses whose secret key a' calculating: 101- (97,88) (99,53) (99,54) (101,6) (101,
(C'l' C'2) = a' . y'o 105 101)
106- (102,12) (102,95) (104,13) (104,94)
Xi = (Y'li . Cl-l mod p, Y'2i . C2-l mod p) 109

ISBN: 978-1-4673-5613-8©2013 IEEE 451

 Encryption; The encoding and decoding time varies processor to
i = {l, 2, 3..., 44}, processor. The observations are recorded on a machine with 8
GB RAM and 2.20 GHz processor speed, on XP platform. In
Yo = k . a = 19 . (5, 55) = (73, 13), Fig. 2, CPU times are calculated for encryption and decryption
(c), Cl) = k· � = 19· (45, 63) = (60, 48), for each 44 blocks of the plaintext "Menezes Vanstone Elliptic
Curve Cryptosystem".
The plaintext is divided forty-four blocks and every block is
sent to B. First character "M" is encrypted and the others are The steps to be followed during encryption and decryption
found the same method. The value of Yo does not change are given the following flowchart in Fig. 3. In our
therefore we use it only first character. The plaintext IS implementation, encryption and decryption processes are the
converted to ciphertext that can be seen in Table 3. same with Menezes Vanstone ECC algorithm's while sending
only point.
Character "M" is encrypted as: (73, 13, 26, 89)

YII = CI . Xll mod p = 60· 4 mod 107= 26,

Yll = Cl . Xli mod p = 48 . 13 mod 107= 89,

TABLE III. TABLE OF CIPHER TEXT

Points Points of ciphertext y N

1-4 (73,13,26,89) (39,26) (39,30) (39,26)
5- 8 (99,52) (39,26) (99,37) (13,0)
9-12 (86,74) (39,48) (39,30) (99,37)
13-16 (99,85) (39,78) (39,30) (39,26)
17-20 (13,0) (26,26) (39,41) (39,41)
21-24 (39,4) (99,0) (99,85) (39,4)
25-28 (39,37) (13,0) (26,37) (99,26)
29-32 (99,96) (99,74) (39,26) (13,0)
33-36 (26,37) (99,96) (99,4) (99,0)
37-40 (99,85) (39,78) (99,37) (99,4)
41-44 (99,37) (99,85) (39,26) (39,89)
DecryptIOn;

(c), Cl) = a' Yo = 27· (73, 13) = (60, 48),

For i =1---> (Yh, YlD = (Yl), Y21) = (26, 89),
Xi = (Yli . Cl-1 mod p, Yli . Cl-1 mod p ) = (26 . 60-1 mod 107,
89 . 48-1 mod 107) = (4, 13) ---> (4, D ) which corresponds to N
the character "M" in the Fig. 1. The ciphertext is decrypted
with this method. At the end of these operations plaintext is Encrypt every
obtained successfully with our implementation. character's
hexadecimal values of
plaintext as a point

Encryption and Decryption Times

0.5 r----=----:--,--�--�-�---,--�-�

0.4 5
f------'-'---'
0.4

0.35

� 0.3

I 0.25
E
i= 0.2

015

0.1

0.05
Fig.3. Flowchart of encryption and decryption

Divided plaintext Menezes Vanstone Elliptic Curve Cryptosystem into44 blocks

Fig.2. Encryption and decryption times for every block

ISBN: 978-1-4673-5613-8©2013 IEEE 452

 V. CONCLUSIONS

Elliptic curve cryptosystem provides an efficient alternative

to other cryptosystems. In this study we explain how to encrypt
characters with their hexadecimal values that provides security
communication media without the necessity of code table
which is agreed by communication parties with modified
version of Menezes Vanstone cryptosystem based on elliptic
curve.
In future, we want to integrate this cryptosystem to mobile
phone for secure communication.

REFERENCES

[1] V. S. Miller, "Use of elliptic curves in cryptography", Advanced in

Cryptology, Proceedings of Crypto85, Lecture note in Computer Science,
v. 218, Springer Verlag,pp. 417-426,1986.
[2] N. Koblitz, "Elliptic curve cryptosystem"', Mathematics of Computation,
48: pp. 203-209,1987.
[3] H.W. Lenstra, "Factoring integers with elliptic curves"', Annals of
Mathematics 126,pp. 649-673,1987.
[4] A. Menezes , S. Vanstone, "Elliptic curve cryptosystem and their
implementation"',Journal of Cryptography 6 (4), pp. 209-224,1993.
[5] T. EI Gamal, "A public key cryptosystem and a signature scheme based
on discrete logarithms"', Advanced in Cryptology, Proceedings of
Crypto84, Springer Verlag,pp. 10-18,1988.
[6] L. Ertaul, W. Lu, "ECC based threshold cryptography for secure data
forwarding and secure key exchange in MANEr', IFIP, NETWORKING
2005,LNCS 3462,pp. 102-113,2005.
[7] F. Amounas , E. H. El Kinani, "Cryptography with elliptic curve using
Tifinagh characters", Journal of Mathematics and System Science 2, pp.
139-144,2012.

ISBN: 978-1-4673-5613-8©2013 IEEE 453