Page 307 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 10

An Example of

Application—Elliptic

Curve Cryptography

his final chapter gives an example of finite-field application,
namely, the implementation of the scalar product (point multi-
Tplication) over an elliptic curve. It is the basic computation
primitive of elliptic curve cryptography. The definition of the corre-
sponding operations depends on the particular field, but they always
amount to combinations of arithmetic operations (add, subtract, mul-
tiply, square, and divide) over the chosen field, so that their hardware
implementation can be carried on using the VHDL models defined in
the preceding chapters. The definition of the elliptic curve opera-
tions follows the presentation of [HMV04].

10.1 Public-Key Cryptography
Public-key cryptography is a ciphering/deciphering method using
distinct keys for ciphering (public key) and deciphering (private key).
Among the most used are the RSA and the discrete logarithm systems.
In the first case [ARS78], two primes p and q are chosen. The
public key is a pair (n, e) of naturals where n = pq, e belongs to the
interval 0 < e < (p − 1)(q − 1) and e is relatively prime with (p − 1)(q − 1).
The private key is d = e mod (p − 1)(q − 1). It can be shown that x ≡
−1
ed
x mod n, for any natural x. The encryption/decryption algorithm
follows: Giving a message mes represented in the form of a natural
belonging to the interval 0 < mes < n, compute the ciphered text c =
d
e
mes mod n. In order to decrypt c, compute c mod n. Observe that
knowing the public key (n,e), the computation of the private key
amounts to decomposing n under the form n = pq and then calculating
− 1
d = e mod (p − 1)(q − 1). Nowadays, the factorization problem is
intractable for key sizes greater than 1024 bits.
In the second case (discrete logarithm), a finite group (G,*,1) is
defined and some element g of G is chosen. Let n be the order of g.
287