IJCSNS International Journal of Computer Science and Network Security, VOL.9 No.1 , January 2009
413
Manuscript received January 5, 2009
Manuscript revised January 20, 2009
Elliptic Curve Cryptography Over Gaussian Integers
Elsayed Mohamed and Hassan Elkamchouchi
Alexandria University, Alexandria, Egypt
Summary
A new approach is used to implement elliptic curve cryptography
(ECC) over prime finite fields. The new approach uses Gaussian
integers instead of rational integers. It generates a much larger
number of points under the same curve equation and the same
prime p. The elliptic curve arithmetic is basically the same but
works on complex numbers. The security of the proposed
method is far higher. When compared to the original prime field,
the new method requires double the space to store cryptographic
keys represented by points but the security level, in terms of the
group order, is roughly squared.
Key words:
Elliptic Curve Cryptography, Gaussian Integers
1. Introduction
1.1 Elliptic Curves
Elliptic curves are known for their security. The common
fields used for encryption are prime fields and
characteristic 2 fields.
Elliptic curves over prime fields are on the form:
E: y2 = x3 + ax + b mod p
where a, b ∈ Fp and 4a3 + 27b2 ≠ 0 mod p
The addition of two points P(x1, y1) and Q(x2, y2) is
calculated by:
R (x3, y3) = P + Q where:
x3 = λ2 – x1 – x2,
y3 = λ(x1 – x3) – y1,
λ = (y2 – y1)/(x2 – x1) if P ≠ Q
λ = (3x12 + a)/2y1 if P = Q
The multiplication of points by a scalar is a series of
doublings and additions of points. The multiplication by –
1 converts P to –P by negating the y coordinate of P, i.e.,
the negative of P = (x, y) gives –P = (x, –y)
1.2 Gaussian Integers
Gaussian integers are complex numbers on the form a + bi
where a and b are integers and i =
1
−
. The norm N of a
Gaussian integer a + bi is a2 + b2. A Gaussian prime is a
Gaussian integer that cannot be expressed in the form of a
product of other Gaussian integers. The ring of Gaus