Efficient modulo 2ⁿ+1 multiplication for the idea block cipher

ABSTRACT

International Data Encryption Algorithm (IDEA) is a popular and secure cryptography algorithm, suitable for hardware implementation. IDEA comprises of modulo 2¹⁶ additions, bitwise exclusive-OR operations and modulo 2¹⁶⁺¹ multiplications of 16-bit words. Among them, modulo 2¹⁶⁺¹ multiplication is the most time, space and power consuming operation. In this work, we propose an efficient modulo 2ⁿ⁺¹ modified Booth multiplication algorithm which is adapted to operands used in the IDEA. The IDEA multiplier based on the proposed modulo 2ⁿ⁺¹ multiplication algorithm yields area and power advantages of up to 12% and 14% respectively, compared to the already proposed modulo 2ⁿ⁺¹ multiplier designs. The implementation of a single round of the IDEA block cipher based on the proposed multiplier verifies the area and power advantages over the implementations based on existing modulo 2ⁿ⁺¹ multipliers.

References

1. X. Lai, "On the design and security of block ciphers", ETH Series in Information Processing, Hartung-Gorre Verlang Konstantz, 1992.
2. A. V. Curiger, H. Bonnenberg, and H. Kaeslin, "Regular VLSI architecture for multiplication modulo (2n+1)", IEEE Journal of Solid-State Circuits, vol. 26, no. 7, pp. 990--994, July 1991.
3. M. Bahrami and B. Sadeghiyan, "Efficient modulo 2n+1 multiplication schemes for IDEA", in Proc. of IEEE International Symposiums on Circuits and Systems (ISCAS), pp. 653--656, 2000.
4. C. Efstathiou, I. Voyiatzis, N. Sklavos, "On the modulo 2n+1 multiplication for diminished-1 operands", in Proc. of the 2nd IEEE Int. Conference on Signals Circuits and Systems (SCS), 2008.
5. J. W. Chen, R. H. Yao, "Efficient modulo 2n+1 multipliers for diminished-1 representation", IET Circuits, Devices, Systems, vol. 4, no. 4, pp. 291--300, July 2010.
6. S. Mukherjee, B. Sahoo, "A novel modulo (2n+1) multiplication approach for IDEA cipher", International Journal of Programmable Devices, Circuits and Systems, vol. 2, no. 11, Nov. 2010.
7. R. Zimmermann, "Efficient VLSI implementation of modulo (2n+1) addition and multiplication", Proc. of IEEE Symp. on Computer Arithmetic, pp. 158--167, April 1999.
8. Y.-J. Chen, D.-R. Duh, Y. S. Han, "Improved modulo (2n+1) Multiplier for IDEA", Journal of Information Science and Engineering, vol. 23, no. 3, pp. 907--919, 2007.
9. H. T. Vergos, C. Efstathiou, "Design of efficient modulo 2n+1 multipliers", IET Computers & Digital Techniques, vol. 1, no. 1, pp. 49--57, Jan. 2007.
10. {C. Efstathiou, N. Axelos, K. Pekmestzi, "On the design of modulo 2n+1 multipliers", in Proc. of 14th Euromicro Conference on Digital System Design (DSD), pp. 453--459, 2011.
11. J. Sklansky, "Conditional sum addition logic", IRE Trans. Electronic Computers, vol. 9, no. 6, pp. 226--231, June 1960.
12. W. Hong, R. Modugu, and M. Choi, "Efficient Online Self-Checking Modulo 2n+1 Multiplier Design", IEEE Trans. on Computers, vol. 60, no. 9, pp. 1354--1365.
13. H. T. Vergos, C. Efstathiou, "Efficient Modulo 2n+1 Adder Architectures", Integration, the VLSI Journal, vol. 42, no. 2, pp. 149--157, Feb. 2009.

Index Terms

• Hardware

  • Integrated circuits

    • Logic circuits

      • Combinational circuits

  • Very large scale integration design

    • Application-specific VLSI designs

      • Application specific processors