User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Iterative modular division over GF(2(m)): Novel algorithm and implementations on FPGA

Primary tabs

de Dormale, Guerric Meurice Quisquater, Jean-Jacques [UCL]

Public key cryptography is a concept used by many useful functionalities such as digital signature, encryption, key agreements, For those needs, elliptic curve cryptography is an attractive solution. Cryptosystems based on elliptic curve need a costly modular division. Depending on the choice of coordinates, this operation is requested at each step of algorithms, during a precomputation phase or at the end of the whole computation. As a result, efficient modular division implementations are useful for both area constrained designs working in affine coordinates and high-speed processors. For that purpose, this work highlights the most efficient iterative modular, division algorithm and explores different time and area tradeoffs on FPGA. First, thanks to a novel algorithm, the computational time is divided by two with an area increase of one half. Second, using the Single-Instruction Multiple-Data feature of the selected algorithm, the area is divided by two with a doubling of the computational time. To the best of our knowledge, it is the first report about an iterative digit-serial modular division algorithm, the first area and time tradeoff analysis of an iterative algorithm and the best result among the very few implementations on FPGA.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2006
Language Anglais
Conference "2nd International Workshop on Reconfigurable Computing", Delft Univ Technol, Delft (Netherlands) (Mar 01-03, 2006)
Journal information "Lecture Notes in Computer Science" - Vol. 3985, p. 370-382 (2006)
Peer reviewed yes
issn 0302-9743
e-issn 1611-3349
Publisher Springer-verlag Berlin (Berlin)
Affiliation UCL - FSA/ELEC - Département d'électricité
Links
  1. Aigner Harald, Bock Holger, Hütter Markus, Wolkerstorfer Johannes, A Low-Cost ECC Coprocessor for Smartcards, Lecture Notes in Computer Science (2004) ISBN:9783540226666 p.107-118, 10.1007/978-3-540-28632-5_8
  2. Brunner H., Curiger A., Hofstetter M., On computing multiplicative inverses in GF(2/sup m/), 10.1109/12.238496
  3. Brent Richard P., Kung H. T., Systolic VLSI Arrays for Polynomial GCD Computation, 10.1109/tc.1984.5009358
  4. Blake I., Seroussi G., Smart N., Elliptic Curves in Cryptography, ISBN:9781107360211, 10.1017/cbo9781107360211
  5. Certicom Research, SEC 2: Recommended Elliptic Curve Domain Parameters, v1.0 (2000)
  6. Daneshbeh A.K., Hasan M.A., A class of unidirectional bit serial systolic architectures for multiplicative inversion and division over GF(2/sup m/), 10.1109/tc.2005.35
  7. Kim Chang Hoon, Kwon Soonhak, Kim Jong Jin, Hong Chun Pyo, A Compact and Fast Division Architecture for a Finite Field GF(2m), Computational Science and Its Applications — ICCSA 2003 (2003) ISBN:9783540401551 p.855-864, 10.1007/3-540-44839-x_90
  8. Fong K., Hankerson D., Lopez J., Menezes A., Field inversion and point halving revisited, 10.1109/tc.2004.43
  9. Guo, J.-H., Wang, C.-L.: Novel digit-serial systolic array implementation of Euclid’s algorithm for division in GF(2m). In: ISCAS 1998, pp. 478–481 (1998)
  10. Gura Nils, Chang Shantz Sheueling, Eberle Hans, Gupta Sumit, Gupta Vipul, Finchelstein Daniel, Goupy Edouard, Stebila Douglas, An End-to-End Systems Approach to Elliptic Curve Cryptography, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.349-365, 10.1007/3-540-36400-5_26
  11. Gutub, A.A.-A.: New Hardware Algorithms and Designs for Montgomery Modular Inverse Computation in Galois Fields GF(p) and GF(2n), Ph.D. Thesis (2002)
  12. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Professional computing. Springer, Heidelberg (2004)
  13. Hasan M.A., Bhargava V.K., Bit-serial systolic divider and multiplier for finite fields GF(2/sup m/), 10.1109/12.156540
  14. Itoh Toshiya, Tsujii Shigeo, A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, 10.1016/0890-5401(88)90024-7
  15. Koblitz Neal, Elliptic curve cryptosystems, 10.1090/s0025-5718-1987-0866109-5
  16. Miller Victor S., Use of Elliptic Curves in Cryptography, Lecture Notes in Computer Science ISBN:9783540164630 p.417-426, 10.1007/3-540-39799-x_31
  17. U.S. Department of Commerce/National Institute of Standards and Technology (NIST), Digital Signature Standard (DSS), FIPS PUB 182-2change1 (2000)
  18. Okeya Katsuyuki, Sakurai Kouichi, Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.564-578, 10.1007/3-540-36400-5_41
  19. Stein J, Computational problems associated with Racah algebra, 10.1016/0021-9991(67)90047-2
  20. Chien-Hsing Wu, Chien-Ming Wu, Ming-Der Shieh, Yin-Tsung Hwang, High-speed, low-complexity systolic designs of novel iterative division algorithms in GF(2/sup m/), 10.1109/tc.2004.1261843
Bibliographic reference de Dormale, Guerric Meurice ; Quisquater, Jean-Jacques. Iterative modular division over GF(2(m)): Novel algorithm and implementations on FPGA.2nd International Workshop on Reconfigurable Computing (Delft Univ Technol, Delft (Netherlands), Mar 01-03, 2006). In: Lecture Notes in Computer Science, Vol. 3985, p. 370-382 (2006)
Permanent URL http://hdl.handle.net/2078.1/59957