Порівняльний аналіз функцій обчислення модульної експоненти

Abstract

Обчислення модульної експоненти для великих чисел широко використовується для знаходження дискретного логарифму, в теоретико-числових перетвореннях та в криптографічних алгоритмах. Для ефективного обчислення модульної експоненти проводяться дослідження нових методів, алгоритмів та засобів їх реалізації. Виділяють три напрями методів модульного піднесення до степеня: загальне модульне піднесення до степеня, та обчислення модульної експоненти з фіксованим показником або з фіксованою основою. Розроблено спеціальні функції для виконання піднесення до степені за модулем у математичних і криптографічних програмних бібліотеках. У роботі проведено порівняльний аналіз вільнодоступних функцій обчислення модульної експоненти з бібліотек Crypto++, OpenSSL, Pari/GP та MPIR та розроблених трьох функцій на основі алгоритму бінарного зсуву справа на ліво. Для роботи з великими числами у розроблених функціях використовується окремий тип числових даних з бібліотеки MPIR. Розроблені функції реалізують бінарний ітераційний алгоритм в одному основному потоці, у двох потоках та одному потоці з використанням передобчислення. За основу порівняння вибрано усереднений тривалість виконання обчислення модульної експоненти для псевдовипадкових даних розрядністю 1К і 2К біт, що відповідає розрядності біля 300 і 600 десяткових знаків. Результати часу виконання, що зведені у таблицю, показують, що найшвидше обчислюється модульна експонента функцією з бібліотеки OpenSSL в універсальних комп'ютерних системах. Реалізації математичними та криптографічними програмними бібліотеками функції обчислення модульної експоненти використовує більш оптимальний алгоритм множення за модулем, так зване множення Монтгомері. У розроблених трьох функціях використовуються операції множення за модулем для множників менших за значення модуля. Окремо проаналізовано функцію з використанням передобчислення залишків для фіксованої основи та модуля, що може ефективно використовуватись для обчислення дискретного логарифму.

The computation of the modular exponentiation for big numbers is widely used to find the discrete logarithm, in number-theoretic transforms and in cryptographic algorithms. To efficient compute the modular exponent, new methods, algorithms and means of their implementation are being developed. There are three directions of computational method of modular exponentiation: general modular exponentiation, and computation of the modular exponentiation with a fixed exponent or with a fixed base. Special functions have been developed to perform modular exponentiation in mathematical and cryptographic software libraries. The paper compares the freely available functions of computing the modular exponentiation from the Crypto ++, OpenSSL, Pari / GP and MPIR libraries and developed three functions based on the right-to-left binary shift algorithm. A separate type of numeric data from the MPIR library is used to work with big numbers in the developed functions. The developed functions implement a binary iterative algorithm in one main stream, in two streams and one stream using precomputation. The comparison is based on the average time of execution of the modular exponentiation for pseudo-random data with 1K and 2K bits, which corresponds to the size of about 300 and 600 decimal signs. The runtime results summarized in the table show that the modular exponentiation is computed the fastest by a function from the OpenSSL library, which is almost twice smaller than the function from the Crypto ++ library and three times smaller than the MPIR function in universal computer systems. The implementation of the function of computing the modular exponentiation by mathematical and cryptographic software libraries uses a more optimal modulus multiplication algorithm, the so-called Montgomery multiplication. The developed three functions use multiplication by modulo operations for factors smaller than the module value. The function using precomputation of the remainders for the fixed basis and the module is analyzed separately. After all, in the testing process, the time of precomputation and determination of the periodicity of residues for this function is not taken into account. Further parallelization of the computation of parts of a multi-bit exponent and the use of the Montgomery multiplication algorithm will allow efficient use of the developed function with precomputation for the calculation of the discrete logarithm.