Abstract
We present a new hardware architecture to compute scalar multiplications in the group of rational points of elliptic curves defined over a prime field. We have made an implementation on Altera FPGA family for some elliptic curves defined over randomly chosen ground fields offering classic cryptographic security level. Our implementations show that our architecture is the fastest among the public designs to compute scalar multiplication for elliptic curves defined over a general prime ground field. Our design is based upon the Residue Number System, guaranteeing carry-free arithmetic and easy parallelism. It is SPA resistant and DPA capable.
Chapter PDF
Similar content being viewed by others
References
Bajard, J.-C., Didier, L.-S., Kornerup, P.: An rns montgomery modular multiplication algorithm. IEEE Transactions on Computers 47(7), 766–776 (1998)
Bajard, J.-C., Imbert, L., Liardet, P.-Y., Teglia, Y.: Leak resistant arithmetic. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 116–145. Springer, Heidelberg (2004)
Chen, L., Yanpu, C., Zhengzhong, B.: An implementation of fast algorithm for elliptic curve cryptosystem over GF(p). Journal of Electronics (China) 21(4), 346–352 (2004)
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Edwards, H.: A normal form for elliptic curves. Bull. Amer. Math. Soc. 44 (2007)
Fouque, P.-A., Valette, F.: The doubling attack – why upwards is better than downwards. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 269–280. Springer, Heidelberg (2003)
Güneysu, T., Paar, C.: Ultra high performance ecc over nist primes on commercial fpgas. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 62–78. Springer, Heidelberg (2008)
Jarvinen, K.U., Skytta, J.O.: High-speed elliptic curve cryptography accelerator for koblitz curves. In: Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 109–118 (2008)
Joye, M., Sung-Min-Yen: The montgomery powering ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Kawamura, S., Koike, M., Sano, F., Shimbo, A.: Cox-rower architecture for fast parallel montgomery multiplication. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 523–538. Springer, Heidelberg (2000)
Mentens, N.: Secure and Efficient Coprocessor Design for Cryptographic Applications on FPGAs. PhD thesis, Ruhr-University Bochum (2007)
Messerges, T.S., Dabbish, E.A., Sloan, R.H.: Power analysis attacks of modular exponentiation in smartcards. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 144–157. Springer, Heidelberg (1999)
de Dormale, G.M., Quisquater, J.-J.: High-speed hardware implementations of elliptic curve cryptography: A survey. J. Syst. Archit. 53(2-3), 72–84 (2007)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Montgomery, P.L.: Modular multiplication without trial division. Mathematics of Computation 44, 519–521 (1985)
Nozaki, H., Motoyama, M., Shimbo, A., Kawamura, S.-i.: Implementation of rsa algorithm based on rns montgomery multiplication. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 364–376. Springer, Heidelberg (2001)
National Institute of Science and Technology. The digital signature standard. Technical report, http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf
White Paper. Stratix vs. virtex-ii pro fpga performance analysis. Technical report, http://www.altera.com/literature/wp/wpstxvrtxII.pdf
Posch, K.C., Posch, R.: Modulo reduction in residue number systems. IEEE Trans. Parallel Distrib. Syst. 6(5), 449–454 (1995)
Ecegovac, M., Duquesne, S., Bajard, J.C.: Combining leak-resistant arithmetic for elliptic curves define over \(\mathbb{F}_p\) and rns representation
Sakiyama, K., Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: Reconfigurable modular arithmetic logic unit for high-performance public-key cryptosystems. In: Bertels, K., Cardoso, J.M.P., Vassiliadis, S. (eds.) ARC 2006. LNCS, vol. 3985, pp. 347–357. Springer, Heidelberg (2006)
Satoh, A., Takano, K.: A scalable dual-field elliptic curve cryptographic processor. IEEE Transactions on Computers 52, 449–460 (2003)
Schinianakis, D.M., Fournaris, A.P., Michail, H.E., Kakarountas, A.P., Stouraitis, T.: An rns implementation of an fpelliptic curve point multiplier. Trans. Cir. Sys. Part I 56(6), 1202–1213 (2009)
Shenoy, P.P., Kumaresan, R.: Fast base extension using a redundant modulus in rns. IEEE Trans. Comput. 38(2), 292–297 (1989)
Szerwinski, R., Gayneysu, T.: Exploiting the power of GPUs for asymmetric cryptography. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 79–99. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guillermin, N. (2010). A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over \(\mathbb{F}_p\) . In: Mangard, S., Standaert, FX. (eds) Cryptographic Hardware and Embedded Systems, CHES 2010. CHES 2010. Lecture Notes in Computer Science, vol 6225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15031-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-15031-9_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15030-2
Online ISBN: 978-3-642-15031-9
eBook Packages: Computer ScienceComputer Science (R0)