Efficient And Side-Channel Resistant RSA Implementation For 8-Bit AVR Microcontrollers

The RSA algorithm is the most widely used public-key cryptosystem today, but difficult to implement on embedded devices due to the computation-intense nature of its underlying arithmetic operations. Different techniques for efficient software im-plementation of the RSA algorithm have been proposed; these range from high-level approaches, such as exploiting the Chinese Remainder Theorem (CRT), down to smart optimizations of the low-level modular arithmetic (e.g. hybrid multiplication). In the present paper we introduce a new variant of the hybrid method for multiple-precision multiplication that optimizes both memory accesses and register allocation. The inner loop of our improved hybrid method saves about 7.8% in execution time compared to the original one of Gura et al. We combine our hybrid method with the Separated Operand Scanning (SOS) Montgomery multiplication into the HSOS method, a new technique to perform long-integer modular arithmetic. Our practical results, obtained on an ATmega128 microcontroller, show that the HSOS method outperforms other modular multiplication techniques for typical operand lengths used in RSA. A 1024-bit private-key operation can be carried out in less than 76·106 clock cycles when tak-ing advantage of the CRT and m-ary exponentiation method, which represents a new speed record for RSA on 8-bit controllers. We also protected our RSA implementation against power analysis attacks via the integration of low-cost countermeasures. These countermeasures increased the execution time of the private-key operation by just 12% compared to an unprotected version.Focusing on efficient implementation and Side-channel attack, the main contribu-tions and innovations of the thesis are as follows.1. We proposed three new inner loop algorithms of hybrid multiplications. When completing a 32-bit multiplication, Gura's method needs 141 clock cycles while our three improved methods just need 114 clock cycles (See Figure 4.3),108 clock cycles (See Figure 4.4) and 102 clock cycles (See Figure 4.5) respectively.2. Based on our new inner loop algorithms of hybrid multiplication, Our practical results, obtained on an ATmega128 microcontroller, show that the HSOS method outperforms other modular multiplication techniques for typical operand lengths used in RSA. A 1024-bit private-key operation can be carried out in less than 76·106 clock cycles when taking advantage of the CRT and m-ary exponentiation method, which represents a new speed record for RSA on 8-bit controllers (See Table 4.4).3. We also protected our RSA implementation against power analysis attacks via the integration of low-cost countermeasures. These countermeasures increased the execution time of the private-key operation by just 12% compared to an un-protected version.Efficient and safely implementation on embedded system is considered as basic blocks in cryptography. The research and design of algorithm for efficient implemen-tation and side-channel analysis has important theoretical significance and practical value. Thus, it will have a bright prospect.