ORGANIZATION OF PARALLEL EXECUTION OF MODULAR MULTIPLICATION TO SPEED UP THE COMPUTATIONAL IMPLEMENTATION OF PUBLIC-KEY CRYPTOGRAPHY

Abstract

The object of research to which the article is devoted are the processes of calculating multiplicative operations of modular arithmetic, which are performed on numbers, the length of which is orders of magnitude greater than the bit capacity of processors.

The target of the research is to speed up the execution of the modular multiplication operation on numbers, which is important for cryptographic tasks, the bit count of which significantly exceeds the bit count of the processor, due to the organization of parallel calculation of fragments of the modular product on multi-core computers.  

As the main way to achieve the goal, in the research presented in the article, parallelization at the level of processing bits of the multiplier and the application of Montgomery group reduction using recalculations that depend only on the module, which for cryptographic applications is part of the public key, which allows it to be considered constant, were used.

The article theoretically substantiates, develops and investigates the method of parallel execution of the basic operation of cryptography with a public key - modular multiplication of large numbers. It is based on a special organization of dividing the components of modular multiplication by independent computational processes in order to ensure the possibility of effective group reduction of the product. The proposed organization ensures high independence of partial computing processes, which simplifies the organization of interaction between them. To implement the Montgomery group reduction, the results of recalculations are used, which depend only on the module and, accordingly, are performed only once. The presentation is illustrated by numerical examples. It is theoretically and experimentally proven that the proposed approach to the parallelization of the computational process of modular multiplication using Montgomery group reduction when using s processor cores allows to speed up this important for cryptographic applications operation by 0.57⋅s.