Securing RSA against power analysis attacks through non-uniform exponent partitioning with randomisation

Securing RSA against power analysis attacks through non-uniform exponent partitioning with randomisation

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

This study presents an approach to compute randomised modular exponentiation through non-uniform exponent partitioning. The exponent has been first partitioned into multiple parts and then shuffled by Fisher Yates method. Thereafter, every partition randomly computes modular exponentiation followed by a final modulo operation to generate the desired result. The shuffling has been introduced to randomise the execution order of individual modular exponentiation. This work is implemented in Rivest-Shamir-Adleman (RSA) and Chinese remainder theorem RSA as they are modular exponentiation based public key cryptosystems. The results have been analysed during decryption with different key sizes. The results indicate that the proposed work can generate non-uniform partitions of the exponent which could not be easily anticipated even in multiple iterations. Also, the shuffling method could completely randomise the execution order of modular exponentiation operations. With non-uniform exponent partitions and randomised modular exponentiation, the proposed work could challenge all the variances of power analysis attacks.


    1. 1)
      • 1. Kocher, P., Jaffe, J., Jun, B.: ‘Differential power analysis’. CRYPTO 1999, 1999 (LNCS, 1666), pp. 388397.
    2. 2)
      • 2. Mangard, S., Oswald, E., Popp, T.: ‘Power analysis attacks: revealing the secrets of smart cards’ (Springer Science and Business Media, 2008), vol. 31.
    3. 3)
      • 3. Jaffe, J.: ‘A first-order DPA attack against AES in counter mode with unknown initial counter’. Cryptographic Hardware and Embedded Systems – CHES 2011, 2007, pp. 113.
    4. 4)
      • 4. Oswald, E., Mather, L., Whitnall, C.: ‘Choosing distinguishers for differential power analysis attacks’. Non-Invasive Attack Testing Workshop, Nara, Japan, 2011.
    5. 5)
      • 5. Kamoun, N. M., Bossuet, L., Ghazel, A.: ‘Experimental implementation of 2ODPA attacks on AES design with flash-based FPGA technology’. Proc. IEEE Int. Conf. on Microelectronics, Cairo, Egypt, 2010, pp. 407410.
    6. 6)
      • 6. Tang, M., Qiu, Z., Gao, S., et al: ‘Polar differential power attacks and evaluation’, Sci. China Inf. Sci., 2012, 55, (7), pp. 15881604.
    7. 7)
      • 7. Messerges, T. S., Dabdish, E. A., Sloan, R. H.: ‘Power analysis attacks of modular exponentiation in smartcards’. Cryptographic Hardware and Embedded Systems – CHES 1999, 1999, pp. 144157.
    8. 8)
      • 8. Boer, B., Lemke, K., Wicke, G.: ‘A DPA attack against the modular reduction within a CRT implementation of RSA’. Cryptographic Hardware and Embedded Systems – CHES 2002, 2002, pp. 228243.
    9. 9)
      • 9. Novak, R.: ‘SPA-based adaptive chosen-ciphertext attack on RSA implementation’. Proc. Int. Workshop on Public Key Cryptography, 2002, pp. 252262.
    10. 10)
      • 10. Fouque, P., Martinet, G., Poupard, G.: ‘Attacking unbalanced RSA-CRT using SPA’. Cryptographic Hardware and Embedded Systems – CHES 2003, 2003, pp. 254268.
    11. 11)
      • 11. Amiel, F., Feix, B., Villegas, K.: ‘Power analysis for secret recovering and reverse engineering of public key algorithms’. Selected Areas in Cryptography, 2007, pp. 110125.
    12. 12)
      • 12. Sarkar, S.: ‘Partial key exposure: generalized framework to attack RSA’. Proc. Int. Conf. on Cryptology in India, 2011, pp. 7692.
    13. 13)
      • 13. Vuillaume, C., Endo, T., Wooderson, P.: ‘RSA key generation: new attacks’. Constructive Side-Channel Analysis and Secure Design – COSADE 2012, 2012, pp. 105119.
    14. 14)
      • 14. Brier, E., Clavier, C., Olivier, F.: ‘Correlation power analysis with a leakage model’. Cryptographic Hardware and Embedded Systems – CHES 2004, 2004, pp. 1629.
    15. 15)
      • 15. Bauer, A., Jaulmes, E.: ‘Correlation analysis against protected SFM implementations of RSA’. Proc. Int. Conf. on Cryptology in India, 2013, pp. 98115.
    16. 16)
      • 16. Kuzu, E. A., Soysal, B., Sahinoglu, M., et al: ‘New cross correlation attack methods on the montgomery ladder implementation of RSA’. Proc. IEEE 3rd Int. Conf. on Advance Computing Conf., Ghaziabad, India, 2013, pp. 138142.
    17. 17)
      • 17. Kuzu, E. A., Tangel, A.: ‘A new style CPA attack on the ML implementation of RSA’. Proc. IEEE Int. Computer Science and Engineering Conf., Chiangmai, Thailand, 2014, pp. 323328.
    18. 18)
      • 18. Jia, F., Xie, D.: ‘A unified method based on SPA and timing attacks on the improved RSA’, China. Commun., 2016, 13, (4), pp. 8996.
    19. 19)
      • 19. Itoh, K., Yajima, J., Takenaka, M., et al: ‘DPA countermeasures by improving the window method’. Cryptographic Hardware and Embedded Systems – CHES 2002, 2002, pp. 303317.
    20. 20)
      • 20. Mamiya, H., Miyaji, A., Morimoto, H.: ‘Efficient countermeasures against RPA, DPA, and SPA’. Cryptographic Hardware and Embedded Systems – CHES 2004, 2004, pp. 343356.
    21. 21)
      • 21. Kim, C., Ha, J., Kim, S., et al: ‘A secure and practical CRT-based RSA to resist side channel attacks’. Proc. Int. Conf. on Computational Science and Its Applications, Springer Berlin Heidelberg, Assisi, Italy, 2004, pp. 150158.
    22. 22)
      • 22. Kim, C., Ha, J., Moon, S., et al: ‘An improved and efficient countermeasure against power analysis attacks’, IACR Cryptology ePrint Archive, 22, 2005.
    23. 23)
      • 23. Wang, Y., Leiwo, J., Srikanthan, T., et al: ‘An efficient algorithm for DPA-resistant RSA’. Proc. IEEE Asia Pacific Conf. on Circuits and Systems, Singapore, 2006, pp. 16591662.
    24. 24)
      • 24. Kaminaga, M., Watanabe, T., Endo, T., et al: ‘Power analysis and countermeasure of RSA cryptosystem’, Electron. Commun. Jpn. III, Fundam. Electron. Sci., 2006, 89, (8), pp. 1020.
    25. 25)
      • 25. Zhang, Y., Zheng, X., Peng, B.: ‘A side-channel attack countermeasure based on segmented modular exponent randomizing in RSA cryptosystem’. Proc. 11th IEEE Singapore Int. Conf. on Communication Systems, 2008, pp. 148151.
    26. 26)
      • 26. Ha, J., Jun, C., Park, J., et al: ‘A new CRT-RSA scheme resistant to power analysis and fault attacks’. Proc. 3rd Int. Conf. on Convergence and Hybrid Information Technology, Busan, South Korea, vol. 2, 2008, pp. 351356.
    27. 27)
      • 27. Fournaris, A. P., Koufopavlou, O.: ‘Protecting CRT RSA against fault and power side channel attacks’. Proc. IEEE Computer Society Annual Symp. on VLSI, MA, USA, 2012, pp. 159164.
    28. 28)
      • 28. Liang, Y., Bai, G.: ‘A new FA and SPA resistant implementation of RSA’, Proc. 3rd Int. Conf. on Computer Science and Network Technology, China, 2013, pp. 893897.
    29. 29)
      • 29. Liang, Y., Bai, G.: ‘A randomized window-scanning RSA scheme resistant to power analysis’, Proc. IEEE/ACIS 13th Int. Conf. on Computer and Information Science, Taiyuan, China, 2014, pp. 217221.
    30. 30)
      • 30. Witteman, M. F., Woudenberg, J., Menarini, F.: ‘Defeating RSA multiply-always and message blinding countermeasures’. Topics in Cryptology – CT-RSA 2011, 2011, pp. 7788.
    31. 31)
      • 31. Bauer, S.: ‘Attacking exponent blinding in RSA without CRT’. Constructive Side-Channel Analysis and Secure Design – COSADE 2012, 2012, pp. 8288.
    32. 32)
      • 32. Kaminaga, M., Yoshikawa, H., Suzuki, T.: ‘Double counting in 2t-ary RSA precomputation reveals the secret exponent’, IEEE Trans. Inf. Forensics Sec., 2015, 10, (7), pp. 13941401.
    33. 33)
      • 33. Wan, W., Yang, W., Chen, J.: ‘An optimized cross correlation power attack of message blinding exponentiation algorithms’, China Commun., 2015, 12, (6), pp. 2232.
    34. 34)
      • 34. Ade-Ibijola,  A.O.: ‘A simulated enhancement of Fisher-Yates algorithm for shuffling in virtual card games using domain-specific data structures’, Int. J. Comput. Appl., 2012, 54, (11), pp. 2428.
    35. 35)
      • 35. Black, P. E.: ‘Fisher–Yates shuffle’, in Black, P.E. (Ed.): ‘Dictionary of algorithms and data structures’ (NIST, 2005).

Related content

This is a required field
Please enter a valid email address