Abstract
Modern Graphics Processing Units (GPU) have reached a dimension with respect to performance and gate count exceeding conventional Central Processing Units (CPU) by far. Many modern computer systems include – beside a CPU – such a powerful GPU which runs idle most of the time and might be used as cheap and instantly available co-processor for general purpose applications.
In this contribution, we focus on the efficient realisation of the computationally expensive operations in asymmetric cryptosystems on such off-the-shelf GPUs. More precisely, we present improved and novel implementations employing GPUs as accelerator for RSA and DSA cryptosystems as well as for Elliptic Curve Cryptography (ECC). Using a recent Nvidia 8800GTS graphics card, we are able to compute 813 modular exponentiations per second for RSA or DSA-based systems with 1024 bit integers. Moreover, our design for ECC over the prime field P-224 even achieves the throughput of 1412 point multiplications per second.
Chapter PDF
Similar content being viewed by others
References
Advanced Micro Devices, Inc. (AMD), Sunnyvale, CA, USA. ATI CTM Guide, Release 1.01 (2006)
American National Standards Institute (ANSI). Public key cryptography for the financial services industry: The elliptic curve digital signature algorithm (ECDSA) (ANSI X9.62:2005) (2005)
Bajard, J.-C., Didier, L.-S., Kornerup, P.: Modular multiplication and base extension in residue number systems. In: Burgess, N. (ed.) Proceedings ARITH15, the 15th IEEE Symposium on Computer Arithmetic, Vail, Colorado, USA, pp. 59–65 (June 2001)
Bajard, J.-C., Meloni, N., Plantard, T.: Efficient RNS bases for cryptography. In: Proceedings of IMACS 2005 World Congress, Paris, France (July 2005)
Bajard, J.-C., Plantard, T.: RNS bases and conversions. Advanced Signal Processing Algorithms, Architectures, and Implementations XIV 5559(1), 60–69 (2004)
Koç, Ç.K., Acar, T., Kaliski Jr., B.S.: Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16(3), 26–33 (1996)
Koç, Ç.K., Naccache, D., Paar, C. (eds.): CHES 2001. LNCS, vol. 2162. Springer, Heidelberg (2001)
Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. Chapman & Hall/CRC Press, Boca Raton (2005)
Cook, D.L., Ioannidis, J., Keromytis, A.D., Luck, J.: CryptoGraphics: Secret key cryptography using graphics cards. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376. Springer, Heidelberg (2005)
Costigan, N., Scott, M.: Accelerating SSL using the vector processors in IBM’s Cell broadband engine for Sony’s Playstation 3. In: SPEED 2007 Workshop Record [12] (2007), http://www.hyperelliptic.org/SPEED/
ECRYPT. eBATS: ECRYPT benchmarking of asymmetric systems. Technical report (2007), http://www.ecrypt.eu.org/ebats/
ECRYPT European Network of Excellence in Cryptography. Software Performance Enhancement for Encryption and Decryption (SPEED), 2007 Workshop Record, Amsterdam, The Netherlands (June 2007), http://www.hyperelliptic.org/SPEED/
Fan, J., Skiyama, K., Verbauwhede, I.: Montgomery modular multiplication algorithm for multi-core systems. In: SPEED 2007 Workshop Record [12] (2007), http://www.hyperelliptic.org/SPEED/
Fleissner, S.: GPU-accelerated Montgomery exponentiation. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2007. LNCS, vol. 4487, pp. 213–220. Springer, Heidelberg (2007)
Gaudry, P., Thomé, E.: The \(\mbox{mpF}_q\) library and implementing curve-based key exchanges. In: SPEED 2007 Workshop Record [12], pp. 49–64 (2007), http://www.hyperelliptic.org/SPEED/
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2003)
Harris, M.: Optimizing CUDA. In: Supercomputing 2007 Tutorial, Reno, NV, USA (November 2007)
Harrison, O., Waldron, J.: AES encryption implementation and analysis on commodity graphics processing unit. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 209–226. Springer, Heidelberg (2007)
Hisil, H., Carter, G., Dawson, E.: Faster group operations on special elliptic curves. Cryptology ePrint Archive, Report 2007/441 (2007), http://eprint.iacr.org/
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)
Manavski, S.A.: CUDA compatible GPU as an efficient hardware accelerator for AES cryptography. In: Proceedings of IEEE’s International Conference on Signal Processing and Communication ICSPC 2007, pp. 65–68 (November 2007)
Mentens, N.: Secure and Efficient Coprocessor Design for Cryptographic Applications on FPGAs. PhD thesis, Katholieke Universiteit Leuven, Leuven-Heverlee, Belgium (June 2007)
Montgomery, P.L.: Modular multiplication without trial division. Mathematics of Computation 44(170), 519–521 (1985)
Moss, A., Page, D., Smart, N.: Toward acceleration of RSA using 3d graphics hardware. In: Galbraith, S.D. (ed.) Cryptography and Coding 2007. LNCS, vol. 4887, pp. 369–388. Springer, Heidelberg (2007)
National Institute of Standards and Technology (NIST). Digital signature standard (DSS) (FIPS 186-2) (January 2000)
Nozaki, H., Motoyama, M., Shimbo, A., Kawamura, S.: 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)
Nvidia Corporation, Santa Clara, CA, USA. Compute Unified Device Architecture (CUDA) Programming Guide, Version 1.0 (June 2007)
Nvidia Corporation, Santa Clara, CA, USA. Parallel Thread Execution (PTX) ISA Version 1.0, Release 1.0 (June 2007)
Poettering, B.: seccure – SECCURE elliptic curve crypto utility for reliable encryption, version 0.3 (August 2006), http://point-at-infinity.org/seccure/
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public key cryptosystems. In: Communications of the ACM, vol. 21, pp. 120–126 (February 1978)
Rosenberg, U.: Using graphic processing unit in block cipher calculations. Master’s thesis, University of Tartu, Tartu, Estonia (2007)
Schinianakis, D.M., Kakarountas, A.P., Stouraitis, T.: A new approach to elliptic curve cryptography: an RNS architecture. In: Proceedings of IEEE’s 14th Mediterranian Electrotechnical Conference (MELECON 2006), pp. 1241–1245 (May 2006)
Shenoy, A.P., Kumaresan, R.: Fast base extension using a redundant modulus in RNS. In: IEEE Transactions on Computers, vol. 38, pp. 292–297 (February 1989)
Smart, N.P.: The Hessian form of an elliptic curve. In: Koç, Ç.K., et al. (eds.) [7], pp. 118–125
Stinson, D.R.: Cryptography. Theory and Practice, 3rd edn. Taylor & Francis, Abington (2005)
Suzuki, D.: How to maximize the potential of FPGA resources for modular exponentiation. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 272–288. Springer, Heidelberg (2007)
Szabó, N.S., Tanaka, R.I.: Residue Arithmetic and its Applications to Computer Technology. McGraw-Hill Inc., USA (1967)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Szerwinski, R., Güneysu, T. (2008). Exploiting the Power of GPUs for Asymmetric Cryptography. In: Oswald, E., Rohatgi, P. (eds) Cryptographic Hardware and Embedded Systems – CHES 2008. CHES 2008. Lecture Notes in Computer Science, vol 5154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85053-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-85053-3_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85052-6
Online ISBN: 978-3-540-85053-3
eBook Packages: Computer ScienceComputer Science (R0)