Method for speed up modular exponent calculation by using precomputations
DOI №________________
Abstract
The article proposes a method to speed up modular exponentiation AE mod M – the base operation of network data protection protocols. The proposed method is solving this issue by using precomputation that allows to cut down by half the numbers of operation of modular multiplications on retention of numbers modular quadrate operations. Elaborated method envisages to separate the exponent code E into m-bit length fragments. In context of precomputation all q =2m-1 possible values of A2 mod M, A3 mod M,…, Aq mod M are calculated. In contrast to existing modular exponentiation method, the proposed one allows to process the whole fragment of exponent code. The article includes mathematical background of the proposed approach. It proves existence of the optimal value for length m fragments of exponent code. The mathematical way to determinate the optimal value of m is presented. Obtained results can be used for optimization of structure modular exponentiation calculation. The results derived by theoretical way have been confirmed by the results of experimental researches that are presented in the article. The proposed procedure of modular exponent calculation with precomputations are described in details and illustrated by numerical example. A recommendation has been worked out for choosing the optimal parameters of software for implementation of the proposed method. A comparative analysis of the proposed methods of modular exponent calculation has been executed. In theoretical and experimental way it is proved that the proposed method provides an acceleration of modular exponentiation by approximately 50%.
Keywords: computer arithmetic, modular multiplication, modular exponentiation, precomputation, network data protection protocols.
References
1. Harin J. S., Berdnic V. I., Matveev G. V. "Mathematical basics of cryptology." Мinsk. BGU (1999): 319.
2. Samofavov K. G., Luckyi G. M., Markovskyi O. P. "Effectiveness organization of multiplicative modular arithmetic operation in data protection systems." Proceeding of International scientific conference UNITECH-09. Gabrovo (November 20-21, 2009): 435-437.
3. Bardis N. G., Drigas A., Markovskyі A. P., Vrettaros I. "Accelerated Modular Multiplication Algorithm of Large Word Length Numbers with a Fixed Module." Communications in computer and information science 111, knowledge management, information systems, e-learning, and sustainability research. Third world summit on the knowledge society, WSKS 2010, Corfu, Greece (September 10-14, 2010): 573-581.
4. Stirenko S. G., Markovskyi O. P., Zahariydakis L., Michenko L. D. "Methor for speed up modular exponentiation calculate." Proceeding of National Technical University of Ukraine "КPI". Informatica, control and computer technic 65 (2017): 110-115.
5. Samofalov K. G. Ramzi Anvar Syliba Sunna. "Accelerated implementation of modular exponentiation on low bit microprocessors, embedded microcontrollers." Problems of informatics and control 4(15), (2005):144-153.
6. Can Xiang. "Verifiable and secure outsourcing schemes of modular exponentiations using one untrusted cloud server and their application." IACR Cryptology ePrint Archive (2014): 500-508.
7. Bardis N. G, Markovskyi O. P. "Secure implementation of modular exponentiation on cloud computing resources". Proceeding of International conference applied mathematics, computational science and systems engineering, Athens, Greece (October 6-8, 2017): 90-96.
8. Kostenko J. V., Markovskyi A. P., Rusanova O. V. "Method for protected modular exponentiation on remote systems." Proceeding of National Technical University of Ukraine “КPI” Informatica, control and computer technic 64 (2016): 51-54.
9. Markovskyi О. Р., Badis N., Doukas N., Kirilenko S. "Secure modular exponentiation in cloud systems." Proceedings of The congress on information technology, computational and experimental physics (CITCEP 2015), Krakow, Poland (18-20 December 2015): 266-269.
