Page 308 - Hardware Implementation of Finite-Field Arithmetic

288 Cha pte r T e n

2
Thus, the set {1, g, g , . . . , g n − 1 } is a cyclic subgroup of G. The private key
is a natural x belonging to the interval 0 < x < n, and the public key is
x
the element y of the cyclic subgroup defined by y = g . The message mes
must be represented under the form of an element of G. The encryption
algorithm is the following: Randomly choose a natural k belonging to
k
0 < k < n, compute c = g and c = mes · y . The ciphered text is made up
k
1 2
x − 1
of c and c . In order to decrypt the message, compute c · (c ) . Observe
1 2 2 1
that knowing the public key y, the computation of the private key x
amounts to calculating log y, presumably a very hard problem. In the
g
basic version of the discrete logarithm scheme [ElG85] G is the set of
natural {1, 2, . . . , p − 1}, where p is a prime, so that all operations are
performed modulo p. Nevertheless, other groups can be used. Consider
m
for example, an elliptic curve E over the binary extension field GF(2 )
defined as being the set of elements (x,y) of GF(2 ) × GF(2 ) so that
m
m
2
3
m
y + xy = x + ax + b, where a and b are elements of GF(2 ). It can be
demonstrated that the set of points of E, plus the so-called point at
infinity ∞, is a group (E, + , ∞) whose basic operation (under additive
notation with neutral element ∞) will be defined in Sec. 10.2. A discrete
logarithm scheme can then be defined by choosing a point P of E whose
order is equal to n so that the set {∞, P, 2P, . . . , (n − 1)P} is a cyclic
subgroup of E. The private key is a natural d belonging to the interval
0 < d < n, and the public key is the element Q of the cyclic subgroup
defined by Q = dP. A simple encryption/decryption algorithm would
be the following: Given a message mes represented by a point M of E,
randomly choose a natural number k belonging to 0 < k < n, and
compute C = kP and C = M + kQ. The ciphered text is made up of C
1 2 1
and C . In order to decrypt the message, compute C − dC . Actually,
2 2 1
other encryption/decryption schemes are used, avoiding among others
the embedding of mes within E. Nevertheless, the operations to be
performed are similar. Observe that knowing the public key Q, the
computation of the private key amounts to looking for a natural d such
as dP = Q, presumably a very hard problem. Nowadays, this problem
is intractable for key sizes greater than 160 bits.
10.2 Elliptic Curve over a Finite Field
Given a finite field K, an elliptic curve E over K is defined by a
Weierstrass equation ([HMV04], [BSS99])
3
2
2
y + a xy + a y = x + a x + a x + a (10.1)
1 3 2 4 6
where a , a , a , a , and a belong to K and satisfy some additional
1 2 3 4 6
conditions [HMV04, Chap. 3]. Given an extension field L of K, the
corresponding elliptic curve E(L) is defined by the following relation:
E(L) = {(x,y) ∈ L x L: y + a xy + a y = x + a x + a x + a } ∪ {∞} (10.2)
3
2
2
1 3 2 4 6
∞ being an additional point called point at infinity.