Public Release: 

An MSU-based researcher developed an algorithm to improve information security tools

Lomonosov Moscow State University


IMAGE: Elliptical curves. view more 

Credit: Courtesy of Denis Khleborodov.

Cryptography is a science of data encryption providing its confidentiality and integrity. After cryptographic transformations (the basis of encryption algorithms) are applied, only the users that possess a relevant key can have access to the initial text.

Transformations based on elliptical curves have been widely used for data protection recently. They are able to provide the same security levels as other types of cryptographic algorithms but require substantially shorter keys.

Transformations based on elliptical curves are in high demand due to the fact that modern technologies aim at the reduction of memory and computational power consumption. Until recently people used desktop devices connected to power sources, and this issue was not a burning one. However, today mobile devices, sim cards, portable devices, and sensors became widely spread. They usually have small dimensions and are limited in accumulator capacity and computational power. At the same time, mobile devices, blockchain technologies, and the Internet of things require additional safety measures, causing the demand for new algorithms of cryptographic transformations with lower computational power consumption to increase. The Internet of things is a concept according to which devices communicate not only with the users, but also with each other. For example, a door and a lighting system may communicate as follows: when someone opens a door to enter the room, lights turn on, and when the door is opened and someone leaves the room, the lights go off. Blockchain technologies also cover the Internet of things and personal mobile devices and are based on the digital signature technology.

The main mathematical operation in transformations based on elliptical curves is scalar multiplication. In the course of it a point on an elliptical curve is multiplied by a parameter (scalar). The main disadvantage of scalar multiplication is its high calculational complexity which may be reduced by using new efficient algorithms with lower complexity and therefore lower computational power consumption.

"In the course of the study we found an algorithm and identified different parameters of its operation. When these parameters are used, and depending on available memory volumes and the value of the scalar, the algorithm allows us to perform scalar multiplication - the main operation on the elliptical curve - with minimum computational power consumption," said Denis Khleborodov, the author of the article, PhD, CCIE Security, and a researcher at MSU.

The new algorithm is based on window non-adjacent form of scalar representation that is classified as an algorithm with a precomputation step. Precomputations are single-time calculations that are performed before the main part of the work, and their results are saved in the memory. The main advantage of algorithms with precomputations is the division of calculation into two parts: the precomputations themselves followed by the new calculations reusing their results. Therefore, the computational complexity of consecutive scalar multiplication operations is reduced.

The author also performed comparative analysis of the obtained result with another effective algorithm based on the same method. The scientist managed to reduce the average computational complexity of the precomputation stage by 5% to 46%, and of the main stage - by 4% to 22% depending on the input data.

The new algorithm may be used on blockchain platforms for digital signing of transactions and authentication, as well as on the Internet of things for the authentication of its devices, in session keys development protocols for the encryption of transferred data, and to secure the integrity of transmitted information.

"We expect to develop an improved algorithm based on the sliding window non-adjacent form of scalar representation, i.e. with changeable parameters of precomputations. We also want to adapt the algorithms for simultaneous calculations. The results may be used in security features of the Internet of things and blockchain platforms," concluded the scientist.


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.