Abstract
The Montgomery kP-algorithm using Lopez-Dahab projective coordinates is a well-known method for performing the scalar multiplication in elliptic curve crypto-systems (ECC). It is considered resistant against simple power analysis (SPA) since each key bit is processed by the same type, amount and sequence of operations, independently of the key bit’s value. Nevertheless, its initialization phase affects this algorithm’s robustness against side channel analysis (SCA) attacks. We describe how the first iteration of the kP processing loop reveals information about the key bit being processed, i.e. bit \(k_{l-2}\). We explain how the value of this bit can be extracted with SPA and how the power profile of its processing can reveal details about the implementation of the algorithm. We propose a modification of the algorithm’s initialization phase and of the processing of bit \(k_{l-2}\), in order to hinder the extraction of its value using SPA. Our proposed modifications increase the algorithm’s robustness against SCA and even reduce the time needed for the initialization phase and for processing \(k_{l-2}\). Compared to the original design, our new implementation needs only 0.12 % additional area, while its energy consumption is almost the same, i.e. we improved the security of the design at no cost.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For example if the product \(X_1 X_2 T Z_2\) in line 4 is calculated as \(X_1 X_2 T Z_2= (X_1 Z_2) \cdot (X_2 T)\), this calculation corresponds to only one multiplication since the products \(X_1 \cdot Z_2\) and \(X_2 \cdot T\) are already calculated.
- 2.
Here, 1 is the integer value.
- 3.
\(k1= cd \ ea65f6dd \ 7a75b8b5 \ 133a70d1 \ f27a4d95 \ 06ecfb6a \ 50ea526e \ b3d426ed\)
\(k2= 93 \ 919255fd \ 4359f4c2 \ b67dea45 \ 6ef70a54 \ 5a9c44d4 \ 6f7f409f \ 96cb52cc\).
References
López, J., Dahab, R.: Fast multiplication on elliptic curves over \(GF\)(2\(^{\rm m}\)) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 316–327. Springer, Heidelberg (1999)
Hankerson, D., Lopez Hernandez, J., Menezes, A.: Software implementation of elliptic curve cryptography over binary fields. In: Koç, Ç.K., Paar, C. (eds.) CHES 2000. LNCS, vol. 1965, pp. 1–24. Springer, Heidelberg (2000). doi:10.1007/3-540-44499-8_1
Joye, M., Yen, S.-M.: The montgomery powering ladder. In: Kaliski, B.S., Koç, K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2002). doi:10.1007/3-540-36400-5_22
Mahdizadeh, H., Masoumi, M.: Novel architecture for efficient FPGA implementation of elliptic curve cryptographic processor over \(GF(2^{163})\). IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21(12), 2330–2333 (2013)
Liu, S., Ju, L., Cai, X., Jia, Z., Zhang, Z.: High performance FPGA implementation of elliptic curve cryptography over binary fields. In: 13th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 148–155. IEEE (2014)
Li, L., Li, S.: High-performance pipelined architecture of elliptic curve scalar multiplication over \(GF(2^m)\). IEEE Trans. Very Large Scale Integr. (VLSI) Syst. PP(99), 1–10 (2015)
Ansari, B., Hasan, A.: High-performance architecture of elliptic curve scalar multiplication. IEEE Trans. Comput. 57(11), 1443–1453 (2008)
Alpirez Bock, E.: SCA resistent implementation of the montgomery \(kP\)-algorithm. Master thesis, BTU Cottbus-Senftenberg (2015)
Fan, J., Verbauwhede, I.: An update survey on secure ECC implementations: attacks, countermeasures and cost, cryptography and security. In: Naccache, D. (ed.) From Theory to Applications, pp. 265–282. Springer, Heidelberg (2012)
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). doi:10.1007/3-540-48059-5_25
Synopsis, PrimeTime. http://www.synopsys.com/Tools/Implementation/SignOff/Pages/PrimeTime.aspx
Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 46–61. Springer, Heidelberg (1999). doi:10.1007/978-3-642-17650-0_5
Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski, B.S., Koç, K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2002). doi:10.1007/3-540-36400-5_3
Acknowledgements
The research leading to these results has received funding from the European Commissions Horizon 2020 under grant agreement from project myAirCoach No. 643607.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Alpirez Bock, E., Dyka, Z., Langendoerfer, P. (2016). Increasing the Robustness of the Montgomery kP-Algorithm Against SCA by Modifying Its Initialization. In: Bica, I., Reyhanitabar, R. (eds) Innovative Security Solutions for Information Technology and Communications. SECITC 2016. Lecture Notes in Computer Science(), vol 10006. Springer, Cham. https://doi.org/10.1007/978-3-319-47238-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-47238-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-47237-9
Online ISBN: 978-3-319-47238-6
eBook Packages: Computer ScienceComputer Science (R0)