Zot-Binary: A New Number System And Its Application On Number Theory Based Public-Key Cryptography
Loading...
Date
2016-01
Authors
Jahani, Shahram
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
Public-key cryptosystems are widely used in protocols such as key agreement, authentication, encryption; etc. Number theory based Public-key cryptosystems are one of the main branches in public-key cryptosystems. The two main operations in number theory based public-key cryptography are large number multiplication and exponentiation. For RSA encryption and decryption, ElGamal digital signature and Diffie-Hellman key exchange are some of the well-known example of these cryptosystems which benefit from these operations. The performance of these cryptographic primitives is highly dependent on the efficiency of these operations. Improving the efficiency of multiplication and exponentiation through the use of a recoding method or utilizing a number system which can decrease the Hamming weight of numbers is very common. ZOT recoding method is one of the latest recoding methods used to decrease the Hamming weight of numbers. However, since it is not positional number systems its cost is high. The focus of this study is to devise an efficient ZOT-base positional number system capable of improving the performance of multiplication and exponentiation-based algorithms. One of the proposed positional number systems in this study is ZOT-Binary with the result of a significant reduction in the Hamming weight. LZOT-Binary is another proposed positional number system with a reduced size look-up table compared to ZOT-Binary. To evaluate the efficiency of the proposed number systems and their respective enhanced multiplication, squaring and exponentiation algorithms, an environment that can handle large numbers was designed. The enhanced operations were compared to the original ones. Based on the results of this study, the Hamming weights of ZOT-Binary and LZOT-Binary are 22 and 23 percent respectively. The results show that classical multiplication algorithm based on ZOT-Binary, ZOTB-CLM, is approximately 20 times faster than the original, for numbers within the range of 128 bits to 8 Kbits. For the same 128-bit to 8-Kbit numbers, the proposed multiplication, ZOTB-CLM, is 25 to 5 times faster than the Karatsuba-classical multiplication algorithm. The results on the enhanced squaring, ZOTB-SQ, indicate that ZOTB-SQ is also significantly faster, that is 53 to 41 times faster for the 128-bit to 8-Kbit numbers, than the classical squaring algorithm. The findings also show that the exponentiation algorithm based on LZOT-Binary is about 36 times faster than the popular exponentiation algorithm for 128-bits numbers and decreases to 9.6 times faster for 8-Kbits numbers. To show the impact of the proposed number systems and the enhanced operations on the efficiency of number theory based public-key cryptosystems, RSA was chosen as a case study. The total execution time for RSA algorithm that runs on LZOT-Binary number system is about is about 36 to 10 times faster than the original algorithm for numbers ranging from 128 bits to 8 Kbits. In summary, the findings from this research indicate that the proposed number system and the enhanced algorithms are highly suitable for existing number theory based public-key cryptosystems.
Description
Keywords
Public-key cryptosystems