The national PKI regulates the use of a qualified electronic signature according to the algorithms of DSTU 4145-2002, ECDSA, DSA and RSA. Operations of creating and verifying electronic signature are based on various mathematical methods: transformation in a ring of integers, field of integers and polynomials, in a group of points of an elliptic curve. All these transformations are impossible without arithmetic operations on integers. In this work authors presented experimental results for implementation previously proposed methods of integers representation with delayed carry form and methods of arithmetic operations on numbers in this representation for ES cryptographic transformations according to the ECDSA scheme. To test the proposed methods of ECDSA cryptosystem operations over a prime GF (p) field, two software collections were prepared - using 32-bit machine words, and using 64-bit machine words. To compare the obtained results, operations without the use of the proposed methods were used as a reference. The comparison was made by comparing the average execution time of 1 million iterations of operations in the software implementation. Based on the analysis results it can be concluded that the proposed methods are more effective than classical.
Information technologies playing an increasingly important role in modern human
and business relations. They can improve the efficiency of information exchange, the
speed of decision-making, quality of goods and services, expand business areas,
develop new markets and compete. As a result of information exchange, there is a need
to ensure the security of this information. Traditionally to build information security
systems consider a standard model of information security [
To automate different activities, there is a need to build an electronic document management system, for which the categories of integrity, authenticity and irrefutability are represented greatest interest. These categories are successfully implemented using an electronic signature (ES). ES application areas are quite diverse – electronic document management systems for various purposes, reporting systems for regulatory authorities, Internet banking systems, public service portals, government registries, electronic bidding and public procurement systems, and others. This is dictated by the main property of ES – it can be used as an analogue of a handwritten signature or seal on a paper document.
With the ratification of the Association Agreement between Ukraine and the
European Union on September 16, 2014, our country has committed itself to harmonize its
own legislation with EU legislation. In particular, to bring the Law of Ukraine “About
Electronic Digital Signature” in line with EU Regulation № 910/2014 “About
electronic identification and trust services for electronic transactions in the internal market
and repealing Directive 1999/93/EC” (eIDAS) of 23 July 2014 year, which defines
the basic requirements for providers of electronic signature and electronic
identification services. Since the Law of Ukraine "On electronic digital signature" no longer
meet the requirements of modern technology and the needs of consumers of electronic
services, it was necessary to develop a new law, the purpose of which was to reform
the legislation in the field of electronic digital signature taking into account the
experience of the European Union, building a single area of trust based on a system of
electronic trust services, recognition in Ukraine of electronic trust services provided
by foreign providers of electronic trust services, which will ensure the active
development of cross-border cooperation and integration of Ukraine into the global
electronic information space. Such a law became the Law of Ukraine "On electronic trust
services", which was adopted on October 5, 2017 and entered into force on November
7, 2018 [
The Law of Ukraine "On Electronic Trust Services" has expanded the list of
services, which, in turn, opens more opportunities for the state, business and citizens:
website authentication, electronic identification, creating an electronic document,
imposition of a qualified electronic signature and seal, timestamp, storage of
electronic signatures and seals [
The international electronic signature algorithm ECDSA is approved for use and is
actively used in the national public key infrastructure of Ukraine. ECDSA is based on
transformations in a group of points of an elliptic curve over a binary field GF(2m) or
a prime field GF(p), as well as operations on prime field elements GF(p) [
Every year the number of services provided in electronic form increases, which in turn leads to growth of services that support ES and also ES user’s. In turn, this leads to an increase in the number of documents with one or more ES that should be checked, and processed in a short time. Therefore, the development of methods to ensure the efficiency of ES creation and verification by increasing the productivity of cryptographic transformations is an urgent scientific and practical task. 2
The productivity of cryptographic transformations can be increased by increasing the
speed of operations with integers. In turn, the speed of operations with integers can be
significantly increase by postponing the transfer operation from senior digits to junior,
and for a loan on the contrary – from junior digits to seniors [
An integer in a delayed carry form representation is a sequence of machine words of w-bit size, each of which contains a block of r bit length allocated for the accumulation of hyphenation, and a block of v bit length filled with bits of the number in binary form (where w r v ). Specificity of the proposed DCF representation of integers is the absence of need to take into account transfers and loans, that allows to get rid of unnecessary operations of assignment and checks at implementation in high-level programming languages, and also from the register analysis of flags on possible transfer. In turn, this leads to increased efficiency of software implementation on processors with superscalar architecture and the capabilities of modern compilers in predicting transitions, parallel execution of commands, deployment of cycles, etc. The exception is the hyphen adjustment operation, which is performed sequentially from the lower machine words to the older ones. The following methods of arithmetic transformations with numbers in DCF-representation are offered by authors in previous works: method of addition (terms and sum in DCF-representation) and mixed addition; subtraction method (decrement, subtractor and difference in DCF representation) and mixed subtraction; method of shift to the left (number and result in DCF-representation) and mixed shift to the left (number in binary form, and result in DCFrepresentation); the method of shift to the right (number and result in DCF-representation) and mixed right-shift (number in binary form, and result in DCFrepresentation); multiplication method based on the Comba method; the method of elevation to the square; modulation method based on the Barrett method; division method based on Barrett's method; comparison method.
The proposed arithmetic operations were used in the implementation of cryptographic transformations of ES according to the ECDSA scheme. 3
Prime fields from NIST FIPS 186-3, namely P-192, P-224, P-256, P-384 and P-521
[
To evaluate the effectiveness of the proposed methods, a software implementation was performed using Microsoft Visual Studio 2015 in C ++ programming language without the use of assembly inserts for the platform with Intel Core-i7 4770 3.40 GHz processor running Microsoft Windows 10 (x64).
To test the proposed methods of ECDSA cryptosystem operations over a prime GF (p) field, two software collections were prepared – using 32-bit machine words, and using 64-bit machine words. To compare the obtained results, operations without the use of the proposed methods were used as a reference. The comparison was made by comparing the average execution time of 1 million iterations of operations in the software implementation: using classical methods of arithmetic operations (original); using the proposed methods of arithmetic operations without parallelization (with improvements).
The use of parallelization in 2 or more streams is not considered, because the effect of their use is achieved at larger values of field size than those used in the cryptosystem ECDSA.
Experimental studies were performed for the main operations of the ECDSA cryptosystem over a prime GF (p) field: private key generation – is operations in a prime field of integers, modulo the order of the group – a prime number of common form; public key generation – is scalar multiplication by a fixed point ES (group generator); digest sign – is scalar multiplication by a fixed point ES (group generator); digest verify sign – is scalar multiplication by an arbitrary (public key) and a fixed point ES (group generator).
When generating a public key and creating a signature, scalar multiplication of a fixed
(base) point is performed on the basis of the Lim-Lee algorithm using Chudnovsky
projective coordinates [
It should be noted that the operations in the base field are performed modulo the prime number of a special kind – pseudomersen, and the operations in the field of the order of the base point, is modulo the prime number of the general form.
The values of these operations speed for the cryptosystem ECDSA on a prime field GF (p) are given in milliseconds.
Table 1 shows the results of operations speed measuring for ECDSA cryptosystem
over a prime field GF (p) with and without the proposed methods using 32-bit
machine words [
To evaluate the effectiveness of the proposed methods using 32-bit machine words, the ratio of the results of measuring the operations of the ECDSA cryptosystem over a prime field GF (p) without using the proposed methods to the results using the proposed methods.
Table 2 shows the normalized results to demonstrate the effectiveness of the proposed methods. The effectiveness of the proposed methods for these operations: The private key generating operation is more efficient in 1.02-1.18 times for all fields under consideration. The public key generation operation is more efficient in 1.02-1.06 times efficient for all fields under consideration. The digest sign operation is more efficient in 1.01-1.03 times for all fields under consideration. The digest verify sign operation is more efficient in 1.01-1.03 times for all fields under consideration. To evaluate the effectiveness of the proposed methods using 64-bit machine words, the ratio of the results of measuring the operations of the cryptosystem ECDSA over a prime field GF (p) without using the proposed methods to the results using the proposed methods.
Table 4 shows the normalized results to demonstrate the effectiveness of the proposed methods. The effectiveness of the proposed methods for these operations: The private key generating operation is more efficient in 1,02-1,08 times for all fields under consideration. The public key generation operation is more efficient in 1,01-1,04 times for all fields under consideration. The digest sign operation is more efficient in 1,02-1,05 times for all fields under consideration. The digest verify sign operation is more efficient in 1,01-1,04 times for all fields under consideration. Based on the analysis results it can be concluded that the proposed methods are more effective than classical.
Private Key Generation 1,2 1,15 1,1 1,05 1 p192 p224 p256 p384
p521
Public Key Generation p192 p224
Digest Sign p192 p224 p384
p521
Digest Verify Sign 1,05 1,04 1,03 1,02 1,01 1 p192 p224 p256 p384
p521 In general, according to Table 5, cryptographic operations of the ECDSA cryptosystem using the proposed methods of arithmetic operations in the group of ES points over a prime field are more efficient:
Due to the slight difference in the binary lengths of integers - elements of a prime field, their binary length has virtually no effect on the effectiveness of the proposed methods.
In addition, it should be noted that modern processors are built on a 64-bit architecture, which shows a much higher efficiency of 64-bit implementations of both classical and proposed methods.