Page 180 - Hardware Implementation of Finite-Field Arithmetic

162 Cha pte r S i x

6.5 FPGA Implementations
Several dividers over GF(239 ) have been implemented within
17
Spartan3 (speed-5) programmable devices, namely: pseudo Euclidean
algorithm (Algorithm 6.3), binary algorithm (Algorithm 6.5), reduction
to multiplications (Algorithm 6.6) with either LSE-first or MSE-first
multipliers, optimal extension field (Algorithm 6.8) with either LSE-
first or MSE-first multipliers. Their costs and delays are shown in
Table 6.1.
As noted previously, the times (period, total time) are expressed
in ns, and the parameters FFs, LUTs, Mult and RAM represent the
numbers of flip-flops, look-up tables, embedded 18-bit-by-18-bit
multipliers, and RAM blocks, respectively. All the source files are
available at www.arithmetic-circuits.org.

6.6 Comments and Conclusions
The binary algorithm is a good option as it gives the fastest circuit,
with a number of slices similar to that of other options, and furthermore
does not need RAM blocks for storing the inverses mod 239. Another
advantage is that it can be used for any extension field, not necessarily
an optimal one. If the delay is not an issue, then the reduction to
multiplications can also be considered.

6.7 References
[DCW00] J. Domingo-Ferrer, D. Chan, and A. Watson, eds. Smart Card Research and
Advanced Applications. Kluwer, Dordredit, Netherlands, 2000.
[DS06] J.-P. Deschamps and G. Sutter. “Hardware Implementation of Finite-Field
Division.” Acta Applicandae Mathematicae, vol. 93, pp. 119–147, September 2006.
[HMV04] D. Hankerson, A. Menezes, and S. Vanstone. Guide to Elliptic Curve
Cryptography. Springer, New York, 2004.
[Kob94] N. Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag,
New York, 1994.
[MOV96] A. J. Menezes, P. C. van Oorschot, and S. Vanstone. Handbook of Applied
Cryptography. CRC Press, Boca Raton, Florida, 1996.
[WBP00] A. D. Woodbury, D. V. Bailey, and C. Paar. “Elliptic curve cryptography on
smart cards without coprocessors,” in [DCW00], pp. 71–92, 2000.
[WWSH02] Ch.-H. Wu, Ch.-M. Wu, M.-D. Shieh, and Y.-T. Hwang. “Novel Algorithm
and VLSI Design for Division over GF(2 ).” IEICE Transactions Fundamentals,
m
vol. E85-A, no. 5, pp.1129–1139, May 2002.