This paper investigates the issues of strengthening business security during digital transformation. The authors demonstrate that the expansion of digitalization processes necessitates a reevaluation of the economic security concept. It is substantiated that in order to strengthen business resilience to risks and threats to digital security, it is necessary to implement a number of measures aimed at protecting the confidentiality, integrity and availability of information. A study of cyber threats to national economic entities and citizens was conducted, including with the use of artificial intelligence tools. This made it possible to identify a priority area of data protection improving the RSA cryptosystem. This research details the development of efficient information processing strategies for reducing the latency of RSA cryptographic functions. To accelerate RSA cryptographic transformations, this study introduces methods for high-speed information processing. The core of suggested method involves the realization of a cyclic shift mechanism utilizing modular arithmetic, entirely implemented by the residue number system (RNS). The application of RNS demonstrates its effectiveness in structuring the process of implementing modular integer arithmetic operations for accelerating public-key cryptographic transformations.
The concept of ensuring economic security of Ukrainian business in active digital transformation has undergone a significant rethinking. Despite the unprecedented challenges and threats posed by Russia's military invasion, government regulatory measures to support all sectors of the national economy [1] continued with a new vector to increase business resilience by accelerating digital transformation. Digitalization has become a key tool in overcoming war risks and ensuring the adaptability of business entities in the face of uncertainty. At the same time, the digital economy is raising the issue of countering digital security threats [2].
Ukrainian business remains particularly vulnerable to digital security risks in the constant growth of cyberattacks from the aggressor country. Digital security incidents have significant economic and social consequences, including damage to reputation, financial losses, recovery costs, etc. [3]. Cyber incidents threaten the availability, integrity, and confidentiality of information and systems. In this context, the need to improve the level of digital security of business is undeniable.
One of the most relevant areas is the improvement of cryptographic information security systems.
Contemporary public-key cryptosystems commonly employ transformations based on algebraic curves, including elliptic curves (EC), hyperelliptic curves (HEC) [4, 5], Picard curves (PC), and superelliptic curves (SEC) [6], alongside traditional RSA systems. A prevailing direction in cryptographic information processing research focuses on extending key lengths. However, this approach inherently leads to a reduction in the processing speed of public-key cryptosystems [7, 8]. This slowdown is particularly problematic when implementing EC-based cryptosystems in resource-constrained environments, such as specialized systems and devices where the use of highperformance, multi-precision computers is not feasible [9]. Consequently, there is a pressing need for the development of techniques that enhance the efficiency, reliability, and security of cryptographic transformations [10]. The proposed approach, which leverages the residue number system (RNS), offers a significant advantage over existing hardware implementations of RSA by fundamentally altering the arithmetic operation paradigm. Unlike traditional positional number systems that rely on sequential digit processing and suffer from inter-digit carry propagation; RNS enables highly parallel execution of modular arithmetic operations. This inherent parallelism, particularly for modular multiplication and squaring which dominate RSA computations, allows for a substantial reduction in latency and an increase in throughput, making it a promising solution for high-speed crypto accelerators in real-time applications. For a comprehensive evaluation of novel cryptographic acceleration methods, comparative performance indicators against established techniques are essential for objectively assessing their practical utility and superiority.
Since the beginning of Russia's full-scale invasion, the number of cyberattacks against Ukraine has been steadily increasing [11]. According to official data from Forbes Ukraine, the losses caused by cybercrime to Ukrainian businesses in 2022 increased by 96% compared to 2021. Their absolute value amounted to UAH 1 billion (EUR 24 million) [12]. Average losses per cyberattack increased by 49% to UAH 7,900 (EUR 190). According to the Ministry of Digital Transformation of Ukraine, the problem of information security increased by 14% in 2021-2023. In 2022, 60% of the adult population and every 8 out of 10 adolescents experienced a data security breach [13]. Unfortunately, official data on the frequency and type of digital security incidents after the fullscale Russian invasion are not available. However, data collected prior to this period shows an increase in the vulnerability of Ukrainian businesses to digital security threats.
During the war, cybercriminals scaled up their criminal business using artificial intelligence [14, 15]. One of the most common types of crimes is the issuance of loans for missing military personnel and citizens who have traveled abroad [16], including through the forgery of an electronic digital signature. Accordingly, the issue of cryptographic protection of information to strengthen the security of business and citizens is relevant and supported by existing research and development.
A comprehensive examination of techniques aimed at enhancing the efficiency of scalar multiplication (SC) within the Jacobian of hyperelliptic curves (HEC) provides both theoretical and empirical justification for the dependence of SC operation performance on several key factors. These factors include: the implementation modality of cryptographic transformations (software, hardware, or hybrid); the specific algorithm employed for HEC divisors; the underlying base field over which the curve is defined; the curve's type and coefficient values; the chosen coordinate system for representing Jacobian divisors (affine, projective, weighted, or hybrid); and the selected arithmetic transformation method within the Jacobian.
Existing methodologies for implementing scalar multiplication algorithms, such as the Kantor divisor addition method, the Koblitz method, various arithmetic transformation methods for HEC Jacobian divisors, weighted divisor addition techniques, the Karatsuba method for modular multiplication and polynomial function field reduction, and methods leveraging aspects of the Chinese Remainder Theorem, often fail to meet the stringent efficiency requirements of modern cryptographic applications. Conversely, the literature [17, 18] highlights the substantial advantages of modular arithmetic codes, specifically the RNS, for accelerating digital information processing tasks, including digital filtering, Fast Fourier Transform (FFT), and Discrete Fourier Transform (DFT) implementations.
This context underscores the critical importance and timeliness of developing novel approaches to improve the performance of cryptographic transformations, particularly RSA, through the utilization of RNS. The RSA system, initially proposed in 1977, remains the most prevalent publickey cryptosystem in use today [19-21].
The primary goal of the studies documented in [22, 23] is to formulate a method for rapid execution of public-key cryptographic transformations and to design a structural model for the operating unit (OU) of a high-speed cryptographic coprocessor, leveraging the capabilities of RNS. The research [24] presents a modified stream cipher cryptographic processor equipped with specialized instructions based on the VLIW architecture. The proposed system utilizes a distributed (clustered) memory structure and is designed for efficient execution of stream cipher operations. Such architecture ensures high performance in processing stream cryptographic algorithms.
Research in [25] investigates the impact of fundamental properties of the modular number system (MNS), such as remainder independence, equality, and the presence of low-order digits, on the architecture and operational principles of crypto accelerator systems utilizing MNS. Specifically, it highlights that the presence of low-order digits in modular representations allows for a wide array of system and technical design choices when implementing integer modular arithmetic operations.
There are four primary methodologies for performing arithmetic operations within RNS: the summation method (utilizing low-order bits of binary adders modulo RNS); the table lookup method (employing read-only memory); the direct logical method, which involves defining and implementing modular operations at the switching function level to generate result values (systolic arrays, programmable logic matrices, and programmable logic devices (PLDs) are suitable hardware platforms for this approach) [26]; and the ring shift mechanism (RSM), which leverages cyclic shift arrays (CSA).
A significant and highly advantageous characteristic of RNS, when based on modular multiplication algorithms, is the absence of inter-remainder carry propagation during cryptographic transformations within the cryptographic coprocessors employing the ring shift mechanism (RSM). While intra-remainder carries exist between binary digits within each modulus pn , the elimination of carry propagation between remainders during modular operations [27] presents a key benefit.
In a positional number system (PNS), arithmetic operations necessitate sequential digit processing due to operation-specific rules, preventing completion until all intermediate results, reflecting inter-digit dependencies, are determined. Consequently, PNS, prevalent in contemporary highspeed crypto accelerators (HSCA), suffers from inherent inter-digit connections that complicate arithmetic operation implementation, demand complex hardware, compromise computational reliability, and limit cryptographic transformation speed [28]. Therefore, a number system devoid of inter-digit dependencies is desirable. The RNS offers this advantage, possessing a unique property: the independence of remainders based on the chosen base [29]. This independence facilitates the development of novel machine arithmetic and fundamentally new HSCA architectures, thereby expanding the applicability of machine arithmetic. Numerous studies [30-32] suggest that adopting non-traditional data representation and parallel processing in digital systems enhances computational efficiency, particularly in modular arithmetic, which exhibit maximum internal parallelism during information processing. RNS falls within this category.
Several factors support the effective utilization of RNS in HSCA: HSCA, like RNS, processes only integer data; HSCA primarily performs modular arithmetic operations; RNS excels in executing modular multiplication and squaring operations, which constitute over 95% of RSA cryptosystem operations, particularly in modulus pn ; as the word length (W ) of HSCA processors increases, a trend in modern RSA system development, RNS application efficiency improves; the widespread use of CSA in HSCA for RSA transformations; the limitations of PNS in achieving significant HSCA efficiency and reliability gains; and promising preliminary results demonstrating RNS's effectiveness in enhancing real-time HSCA performance and reliability [33].
Research presented in [34] elucidates the operational principle of integer residual arithmetic, specifically the ring shift mechanism (RSM). This mechanism is distinguished by its ability to determine the result of arithmetic operations, such as ( yn un ) mod pn , for any modulus pn within the RNS base set { pn} (n = 1, q) , without necessitating the computation of partial sums Sn or carry values Cn from binary adders in PNS. Instead, the result is derived through cyclic shifts of a predefined digital structure. This approach is grounded in Cayley's theorem, which establishes an isomorphism between the elements of a finite abelian group and those of a permutation group [35].
From Cayley's theorem, it can be inferred that the action of abelian group elements on the group of integers is homomorphic [36]. This property enables the organization of arithmetic operation result determination in RNS through the application of RSM. Thus, an operand in RNS is represented as a set of q remainders {yn} (n = 1, q) , obtained by successively dividing an initial number Y by n pairwise prime numbers { pn} . In this context, the collection of remainders {yn} directly corresponds to the sum of q simple Galois fields GF ( pn ) [37].
An algebraic system ( A) consists of a plural (P) and a set of operations (F ) defined on this set. This system is denoted as A = ( P,F ), where P is a non-empty plural of integers (Z ) ; F is a set of binary operations (specifically, in RNS implementation, the operations executed in a single clock cycle are the arithmetic operations: +, −, ) [38]. That is, F is the set of operations addition (+), subtraction ( − ), multiplication ( ) for any yn , un Z , yn + un , yn – un , yn un also belong to Z . It is important that the operations be closed on the plural P, that is, the result of the operation on elements from P also belongs to P . Therefore, it is very important that the range of q representation of numbers in the MSN D = pn overlaps the set P , that is, that the elements a n=1 and b themselves, and the result of the arithmetic operations +, −, , lie in this range. In cryptography, where information security is a key aspect, the use of large numbers becomes necessary to ensure the reliability and robustness of cryptographic systems. The larger the number of bits, the more difficult it is to break a cryptographic algorithm, as the number of possible combinations grows exponentially. Asymmetric cryptography algorithms, such as RSA, DSA, and ECC, are based on the use of large prime numbers to generate cryptographic keys [39]. The key operations in these algorithms are modular multiplication and exponentiation, which are performed on large-bit numbers. Given the increasing requirements for the speed of cryptographic systems, the optimization of these operations is a relevant area of research. In this context, the goal of our research is to develop and analyze a method for ultrafast execution of the modular addition operation in RNS, which can serve as an effective replacement for the modular multiplication and exponentiation operations, ensuring increased performance of cryptographic transformations [40].
Algebraic systems A is a plural P with operations F forming an algebraic system, for example, a group, ring, or field. Groups, rings, and fields are fundamental structures in abstract algebra, each defined by a set of axioms that specify the properties of operations. These structures are used to model a variety of mathematical objects and processes, from simple arithmetic operations to complex cryptographic algorithms.
One of the important directions in the study of algebraic systems is the study of factor structures, which allow us to build new algebraic objects based on existing ones. In particular, in the case of rings, we can construct a ring of subtraction classes, or a factor ring, which is a powerful tool for analyzing the structure of rings and their properties.
Let us consider in more detail the process of constructing a ring of subtraction classes. Let R be a ring with the operations of addition (+) and multiplication ( ) defined on it, and J be an ideal of the ring R . The ideal J is a subset of R that satisfies certain conditions that allow us to partition R into subtraction classes. The subtraction class containing an element yn R is defined as the set yn + J = yn + j | j J . The set of all subtraction classes forms a new ring, called the subtraction class ring or factor ring, and is denoted by R / J . The operations of addition and multiplication in R / J are defined in terms of the operations in R , allowing us to inherit many properties from the original ring.
Subtraction class rings are an important tool for studying the structure of rings and their applications in various fields of mathematics and computer science, including cryptography, number theory, and algebraic geometry.
The factor ring R / J can be expressed as Z /pn , where V represents the set of integers. When pn , the base of the RNS, is a prime number, Z /pn forms a finite field. Given the methodology for performing arithmetic operations within the RNS, it is advantageous to focus on an arbitrary finite Galois field GF ( pn ) , where n remains constant, corresponding to a specific defined residue system. Leveraging the aforementioned properties, modular addition and subtraction operations in RNS can be implemented without inter-digit carry propagation using the RSM through q CSAs with a range of with a range of elements representation D , effectively achieved through ring shifts of digit representations utilizing bit shift registers [41].
Based on the RSM proposed in the research, a method for performing arithmetic operations within the RNS is introduced, namely the binary remainder representation technique (BRRT). This approach, grounded in the principles of RNS, which originates from the Chinese remainder theorem [42], facilitates efficient execution of arithmetic operations, including addition, subtraction, and multiplication, on large-bit numbers. A key feature of BRRT is the utilization of binary representations for remainders [43], which allows for the substitution of complex multiplication and exponentiation operations with simpler shift and addition operations. This significantly enhances the speed of arithmetic computations, a critical factor for cryptographic algorithms where computational efficiency is paramount. Furthermore, BRRT enables parallel processing, further accelerating operation execution. These advantages render the proposed method highly promising for cryptographic systems that demand high performance and reliability [44]. Utilizing this approach, the primary (foundational) digital structure of the CSA for each modulus pn of RNS is represented by the initial row (column) of the Cayley addition table, specifically ( yn + un ) mod pn , as illustrated in Fig. 1.
The primary digital structure of the CSA content for each modulus pn can be expressed as:
B_ pn = ( B_ y0 || B_ y1 || ... || B_ y pn −1 ), where symbol || denotes the concatenation operation (combining, merging); B_ y j is a m-bit binary representation of the number y j (while y j iterates from 0 to pn −1 ) for modulus pn .
The bit width m of the binary code of the primary digital structure of the CSA is determined by: mn = log2 ( pn −1) + 1, where square brackets [x] denotes the integer part of x, discarding the fractional part.
Given a specific modulus pn = 7 , the primary digital structure of the CSA content, derived from
mathematical expression (
B _ 7 = (000 || 001|| 010 || 011||100 ||101||110).
Therefore, leveraging CSA, which are prevalent in binary PNS, especially within cryptography,
facilitates the straightforward implementation of addition operations in the RNS. The degree k of
cyclic displacements (shift) is established through the following expression, as per structure (
k = B_ yk || B_ yk +1 || ... || B_ y0 || ... || B_ y pn −1 ,
−k B_ y0 || B_ y1 || ... || B_ y pn −1 = = B_ y pn −1−k || B_ y pn −k || ... || B_ y0 || B_ y1 || ... || B_ y pn −k −2 .
p n , implying that when k = pn , all elements
It is noteworthy that B_ y0 || B_ y1 || ... || B_ y pn −1 of the ordered set {B_ y j } remain in their original positions.
For the practical realization of this approach, the first term yn indicates the quantity of CSA
digit positions that hold the result of the modular operation ( yn + un ) mod pn , while the second
term un indicates the number k shifts CSA applied to the primary CSA content (
Building upon prior research [45], the processing time for the modular addition of remainders yn and un , specifically ( yn + un ) mod pn , within the RNS can be expressed by the ensuing expression:
= 3 t,
RNS = Vn mn ,
RNS _ max = ( pn −1)log2 ( pn −1) + 1 3 t.
(
Thus, based on expressions (
RNS = Vn log2 ( pn −1) + 1 3 t.
In this case, the maximum possible value of expression (
RNS, the maximum addition time of two numbers Y = ( y1 || y2 || ... || yn || ... || yq ) and U = (u1 || u2 || ... || un || ... || uq ) is determined by the maximum value of modulus pq :
RNS _ max = ( pq −1) log2 ( pq −1) + 1 3 t.
In general, the addition time of two numbers
Y = ( y1 || y2 || ... || yn || ... || yq )
and
U = (u1 || u2 || ... || un || ... || uq ) in RNS is determined by the time (
Previous studies [29, 45], focused on the optimization of the RSA cryptographic algorithm through the utilization of the RNS, have thoroughly examined the implementation of modular addition for one- and two-byte digit numbers. A simplified OD scheme for a one-byte HSCA processor in RNS is presented in Fig. 3.
However, given the substantial range of number representation required for ensuring the robustness of the RSA cryptographic algorithm, there arises a necessity to investigate the effectiveness of RNS in processing large data arrays. A comprehensive analysis and illustrative examples demonstrating the advantages of employing RNS for modular addition of large-digit numbers will be presented.
Cases where operand sizes reach values typical for contemporary cryptographic applications will be considered, and results will be compared with conventional computational methods. This will enable the evaluation of the practical value of RNS for enhancing the performance of cryptographic systems.
Concrete example of implementing the addition operation for two numbers within the RNS are
presented, utilizing the following set of moduli: p1 = 11 , p2 = 13 , p3 = 15 , and p4 = pq = 19 ,
q
which provides a number representation range from 0 to D = pn = 1113 15 19 = 40755 in the
n=1
RNS. According to equation (
Example 1. If the second number (U10 = 95) is equal to U RNS = (111||100 ||101|| 000)2 = = (7 || 4 || 5 || 0)10 , then it is necessary to find the APU with the largest product value Vn mn , therefore:
In the APU1 with modulus p1 = 11 , the following values are obtained: V1 = 7 , m1 = log2 ( p1 −1) + 1 = log2 (11 −1) + 1 = 4 and V1 m1 = 7 4 = 28. with
p2 = 13 , the following values are obtained: V2 = 4 , m2 = log2 ( p2 −1) + 1 = log2 (13 −1) + 1 = 4 and V2 m2 = 4 4 = 16. with
p3 = 15 , the following values are obtained: V3 = 5 , m3 = log2 ( p3 −1) + 1 = log2 (15 −1) + 1 = 4 and V3 m3 = 5 4 = 20.
with modulus
p4 = 19 , the following values are obtained: V4 = 0 , m4 = log2 ( p4 −1) + 1 = log2 (19 −1) + 1 = 5 and V4 m4 = 0 5 = 0.
It is evident that the maximum binary digit shift, amounting to 28, is observed within the first arithmetic processing unit (APU1). Consequently, the execution time for the addition of two numbers Y and U, represented in the RNS utilizing the ring shift mechanism, is determined by the value of the second term U and is equivalent to:
RNS = V1 log2 ( p1 −1) + 1 3 t = 7 4 3 t = 84 t.
Example 2. If the second number (U10 = 78) is equal to U RNS = (001|| 000 || 011|| 010)2 = = (1|| 0 || 3 || 2)10 , then it is necessary to find the APU with the largest product value Vn mn , therefore:
In the
APU1 with modulus
p1 = 11 , the following values are obtained: V1 = 1 , with
p2 = 13 , the following values are obtained: V2 = 0 , m2 = log2 ( p2 −1) + 1 = log2 (13 −1) + 1 = 4 and V2 m2 = 0 4 = 0.
with modulus
p3 = 15 , the following values are obtained: V3 = 3 , m3 = log2 ( p3 −1) + 1 = log2 (15 −1) + 1 = 4 and V3 m3 = 3 4 =12.
with modulus
p4 = 19 , the following values are obtained: V4 = 2 , m4 = log2 ( p4 −1) + 1 = log2 (19 −1) + 1 = 5 and V4 m4 = 2 5 =10.
It is evident that the maximum binary digit shift, amounting to 12, is observed within the third arithmetic processing unit (APU3). The execution time for the addition of two numbers Y and U, represented in the RNS utilizing the RSM, is equivalent to:
RNS = V3 log2 ( p3 −1) + 1 3 t = 3 4 3 t = 36 t.
An analysis comparing the time required to perform the addition of two numbers Y and U
between PNS and RNS is provided. The addition time of numbers Y and U in PNS is:
(
Recognizing that an existing method achieves a two-fold shortening of the maximum operation time for modular addition in RNS, the following applies to RSM:
The ratio of addition operation execution times in PNS and RNS will be represented by a coefficient, namely:
RNS _ max = RNS _ max / 2. = = PNS / RNS _ max =
(16 l −1) 3 2 ( pq −1) log2 ( pq −1) + 1 3 =
2 (16 l −1) ( pq −1) log2 ( pq −1) + 1 .
=
The computational assessment and comparative evaluation of arithmetic operation execution times during cryptographic transformations demonstrated the significant effectiveness of the BRRT method, which utilizes the RSM within the RNS, when contrasted with a method employed in PNS (see Table 1).
It is important to note that Table 1 specifically presents a comparative analysis of the modular addition operation within the RNS versus the PNS. While these results highlight the efficiency gains at the fundamental arithmetic level, a direct comparative analysis of the overall RSA cryptosystem's performance using the proposed RNS-based acceleration against other established RSA acceleration methods (e.g., Montgomery multiplication, Karatsuba algorithm, or dedicated hardware implementations) is a complex task that requires specific experimental setups and is beyond the scope of this initial theoretical and methodological paper.
The presented data are derived without the inclusion of supplementary algorithms, which, if
implemented, could expedite the execution of modular arithmetic operations. The resulting
mathematical expressions (
Economic security of businesses undergoing digital transformation necessitates a paradigm shift in our conceptual approach. In the face of martial law threats, Ukraine's national economy has demonstrated a commendable level of cyber resilience. However, to bolster business resilience against evolving digital security risks, the current approach requires augmentation. Specifically, enhancing the RSA cryptosystem is crucial.
This paper introduced a novel method for accelerating cryptographic transformations within Galois fields, focusing on improving the efficiency of RSA cryptosystems with public keys. The proposed method leverages the RNS. By exploiting the fundamental theoretical properties of RNS, we have effectively streamlined the execution of modular operations essential for cryptographic tasks.
Furthermore, we have presented a practical method for realizing arithmetic operations in RNS based on a ring shift mechanism, namely the binary remainder representation technique. The efficiency analysis and concrete technical implementation examples of modular arithmetic operations substantiate the practical feasibility of this approach. This method of information processing is highly recommended for crypto accelerators enabling real-time security surveillance and secure authentication.
The application of the proposed method significantly reduces the execution time of operations, which is critical for ensuring real-time security. The obtained results confirm the practical value of RNS in enhancing the performance of cryptographic systems, particularly when processing large data arrays, which is typical for modern cryptographic applications.
The research findings offer significant potential for application in systems and devices designed for high-throughput, real-time digital information processing. Practical examples confirm its feasibility for real-time applications, strengthening digital security infrastructure, especially in dynamic environments. The implementation of this method not only improves the speed of critical cryptographic processes, but also enhances the overall security posture of digital systems. Moreover, while this study specifically focuses on RSA, the core principles of RNS-based modular arithmetic and the cyclic shift mechanism are inherently adaptable to other cryptographic algorithms that heavily rely on modular exponentiation and multiplication, such as ElGamal, Diffie-Hellman, and various elliptic curve cryptography (ECC) schemes. The parallel processing capabilities offered by RNS make it a versatile foundation for accelerating a broad spectrum of public-key cryptographic operations beyond RSA. As such, it represents a substantial advancement in the field of secure computation. By enhancing the speed and efficiency of cryptographic operations, this method contributes to strengthening the digital security infrastructure, particularly critical in dynamic and challenging environments.
Future work will focus on a comprehensive experimental evaluation of the proposed RNS-based RSA acceleration method against state-of-the-art hardware and software implementations of RSA, including detailed comparative performance indicators such as throughput, latency, and resource utilization. This will provide a more objective and complete assessment of its practical advantages and potential for real-world deployment.
The authors have not employed any Generative AI tools.