s Algorithms for the exchange of information between subscribers are proposed, based on surjective mappings of finite associative-commutative rings with unity and systems of linear equations over such rings. The paper presents algorithms for constructing finite rings, generating surjective mappings of these rings, as well as the information exchange protocol and computational features of the protocol's implementation. The main motivation for the development of such a cryptosystem is that almost all established cryptosystems require computations involving either large prime numbers or the construction of finite fields of large order. These constructions also necessitate the use of rather complex algorithms. In contrast, the proposed system does not require complex calculations, nor the construction of operation tables for rings. Its security relies on the combinatorial complexity of the set of surjective mappings and isomorphisms between finite rings of relatively small order. The algorithms for solving systems of linear equations, which are integral to the information exchange protocols over such rings, exhibit polynomial-time complexity. The operation of the cryptosystem is demonstrated through examples.
In cryptographic applications, finite fields and Diophantine equations, as well as systems of such equations, are frequently employed [1, 2]. This is primarily due to the fact that a finite field possesses a cyclic multiplicative group, which enables the efficient use of the discrete logarithm function, while algorithms for solving Diophantine equations and systems of such equations over the set of natural numbers exhibit high computational complexity [3]. Cryptosystems constructed on the basis of these structures require the generation of large prime numbers, the construction of finite fields of high order, or significant memory resources and computational time for preparatory operations [4].
The motivation for this work is to develop a cryptosystem based on objects of relatively small size that still provides the necessary level of cryptographic strength. A system of this type was proposed in [5], and the present work represents a further development of that approach. The foundation of the cryptosystem is the use of surjective mappings of finite rings and their isomorphisms, utilizing systems of linear equations over residue rings. The security of such a system is based on the combinatorial complexity of the set of mappings between rings of relatively small order.
Let denote the finite residue ring modulo , that is, – is an associative-commutative ring (ACring) with unity. Elements , ∈ ∖ {0} are called additive inverses if + ≡ 0 (mod ), and are called zero divisors if ⋅ ≡ 0 (mod ). Since the ring has a multiplicative identity, elements , ∈ such, that ⋅ ≡ 1 (mod ) are called units. The set of units in forms an abelian group [6].
Let denote a finite AC-ring with unity, isomorphic to the ring , constructed according to a given defining sequence for addition with unity. This sequence is referred to as the defining sequence and based on the laws satisfied by the addition and multiplication operations of the ring, the operation tables for are constructed (algorithms for constructing the operation tables of can be found in [5]). This sequence also specifies the isomorphism between the rings and , which allows one to avoid constructing the operation tables for , since operations can be performed in and, via the isomorphism, the results can be mapped to , where operations in are more efficient.
In the general case, the defining sequence of the ring = (1, 1, 2, … , −2, 0) is specified by
the mapping (0) = 0 + 1 = 1, (
The defining sequence of the ring is generated by the following algorithm.
GEN-G(, , , ) Input: Order and coefficients of the expression () = ⋅ + , where = , gcd(, )= gcd(, )=1. Output: The addition table row with unity as a one-dimensional array = (1, 2, … , ) of length . Method: 1. for = 0 to − 1 do [ + 1] ∶= ⋅ + (mod ) od 2. According to common rules, transform the array bb and fix its values (creation of the common defining sequence). 3. for = 1 to do if ( = 0 ∧ ≠ ) then change and ; if ( = 1 ∧ ≠ 1) then change and 1; od (* This defines the isomorphism () = , where = 1, 2, … , *) 4. Using the array = (1, 2, … , ) construct the array [1 × ] (from which, if necessary, the operation tables of the ring can be constructed): [0] ∶= 1; for = 1 to − 2 do [] ∶= +1 od [−1] ∶= 0.
The correctness of the algorithm follows from the fact that if gcd(, )=1 and runs through a complete residue system, then ⋅ + also runs through a complete residue system [6].
The time complexity of the GEN- algorithm is ( log2 ), since integer multiplication has complexity (log2 ), and there are at most such multiplications.
It should be noted that operator 1) of the GEN- algorithm can generate no more than ( − 2)() initial sequences, where – is Euler’s totient function. For cryptographic applications, this number is insufficient. Therefore, by agreement between the parties, the initial sequence generated by the algorithm is transformed in the same way by operator 2), which defines the cryptosystem as symmetric.
Example1. Generate the defining sequence for = 6 and () = + 4.
The first loop of the algorithm (operator 1) generates the following initial sequence: 1. 1 = 4; 2 = 5; 3 = 0; 4 = 1; 5 = 2; 6 = 3. 2. The second operator performs a transformation: it swaps pairs of adjacent elements and performs a single cyclic permutation of all elements. The resulting sequence is 2, 5, 4, 1, 0, 3. 3. The second loop (operator 3) places 0 and 1 in their correct positions and produces the defining sequence and isomorphism: () = , = 1, 2, … , 6, where 1 = 1; 2 = 5; 3 = 4; 4 = 2; 5 = 3; 6 = 0. 4. The third loop (operator 4) generates, from the array 1 = 1, 2 = 5, 3 = 3, 4 = 0, 5 = 2, 6 = 4 the sequence = (1, 5, 3, 0, 2, 4 from which the operation tables of the ring 6 are constructed. ♠1
Thus, the isomorphism between the rings and is determined by the defining sequence generated by the GEN- algorithm. Specifically, we have the following correspondence: 1 2 3 4 … −
1
,
1 2 3 4 … −1 0
where the isomorphic mapping g is defined as: () = 0, (
The design of the cryptosystem is based on the following scheme:
In this scheme, the mappings (see Fig. 1) are defined as follows: – is an isomorphism between the rings and , – is a surjective mapping from the ring onto the ring
, – is a surjective mapping from the ring onto the ring
, – 1 is a bijection between the factor set / and the ring
, – 1 is a bijection between the factor set / and the ring
.
The message exchange between Alice and Bob is performed according to the following protocol.
Initially, Alice and Bob exchange, via a secure channel, a quadruple (, , , ), whose elements are parameters of the algorithm GEN-G(, , , ). Using the expression () = ⋅ + , where gcd(, )= gcd(, )=1, they generate the initial sequences of the rings and and, by agreement, construct the defining sequences = (1 = 1, 2, … , −1, = 0) and = (1 = 1, 2, … , = 0) for the rings and respectively, in the same manner.
After this, Alice and Bob proceed as follows:
Step 1. а) Alice constructs a system of expressions in the ring : 1 The symbols ♠ and ■ denote the end of the example and the end of the proof, respectively.
() = + = (−1(… 2(1(() + ) + 1) … + −1) + ) + +1, where are non-singular matrices of dimension × , , – are vectors of dimension 1 × , = 1, 2, … , , = 1, 2, … , + 1. The result of this transformation is a system
c) She replaces the coefficients in () and () with their counterparts from the factor set /1: and Alice then transmits the expressions () and () via a public channel or publishes them on a website.
Step 2.
a) Bob, using the expressions () and () and the mappings 1−1 and −1 , finds the expressions () and () in the ring , and selects an arbitrary vector of dimension 1 × .
b) Bob wishes to send Alice a message . To do this, he solves the system () = , finds the solution and computes the vectors () = and ( + ) = 1 in the ring .
c) Bob keeps the vector secret, replaces the values and 1 with their counterparts from one of the factors sets / or / and sends Alice the pair of vectors (, ! ) via a public channel. Step 3.
a) Alice computes the inverse matrices to the matrices in the ring (these computations are performed in the ring via the isomorphism ).
b) She recovers the value , since she possesses all the necessary data.
Proposition 1. The message exchange according to the protocol is performed correctly. Proof. This follows directly from the properties of linear operators, the bijection 1, and the isomorphism . Indeed, let us denote the product of matrices −1 … 1 = , then 1 = (( + ) + 1) = (( + ) + 1) + + +1 = (( + ) + 1) + , where = + +1, and is the vector of values obtained by multiplying the matrices 1, 2, … , by the vectors 1, 2, … , . Then
−1 −1 −1 −1 ((1 − +1)) − = ((( + ) + 1) + ) − = ( + ) + 1.
Thus, ( + ) + 1 − [1 + ] = (). ■
From Figure 1, it follows that there are at least three paths for ciphertext generation in the system: 1)
/ → → → . Here, the expressions () and () are explicitly represented in the factor set /, which, via the bijections and 1, are mapped to the ring , where computations are performed and the ciphertext is constructed in the ring .
2)
/ → → → /. Here, the expressions () and () are explicitly represented in the factor set /, and via the bijections 1 and , these expressions are mapped to the ring , where computations are performed and the ciphertext is constructed via the bijections and 1 in the factor set /. This path corresponds to the protocol described above.
3)
/ → → → /. Here, the expressions () and () are explicitly represented in the factor set /, and via the bijections 1 and , these expressions are mapped to the ring , where computations are performed and the ciphertext is constructed in the factor set /.
Example 2. Consider the preparatory steps of the protocol.
Suppose Alice and Bob choose the first path for ciphertext generation, exchange the tuple (
= (
Operator 3) of the GEN-(
Using this isomorphism, operator 4) of the GEN-G algorithm constructs the array [1 × 25] (for convenience, it is presented as a substitution row).
Let the letters of the English alphabet be naturally enumerated, and the defining sequence of the ring 50, generated by the GEN-G algorithm is as follows
1,5,49,7,10,17,2,34,11,20,39,33,48,3,45,4,37,6,41,13,43,15,36,8,38,9, 35,12,40,14,44,19,46,16,47,21,31,24,27,42,29,22,32,23,30,25,28,18,26,0.
for = 1, 2, … , 50, we obtain the ordinal number j of the class of the element . This concludes the preparatory steps. ♠ 3.1. Cryptanalysis of the Protocol Let us consider possible cryptanalysis scenarios for the protocol. The cryptanalyst has access to the following data: a) The system (), from which the block length of the message can be determined by the number of congruences in the system; b) The ciphertext length, which can be determined by the number of unknowns in the congruences; c) Possibly, the orders of the rings and .
Unknowns include the isomorphism , the bijections 1, 1 and the surjections and .
Suppose in case (a), the cryptanalyst has no further information. Then, the only feasible method to recover the plaintext is exhaustive search. The complexity of such a search is determined by the number of possible ways to encrypt a message, which is composed of: 1. The number of possible isomorphisms (bijections) – (( − 2)!), where is the order of the ring , 2. The number of bijections 1 and 1: (!) each, 3. The number of surjections and : !!(!!)! , where = .
!
The total complexity, even for such a simple cryptosystem as in the example above, is If we assume that one combination is generated in 10−14 seconds, then to enumerate all combinations would require
1031 ⋅ 10-14 = 1017 seconds, which is more than 107 years.
Clearly, if the orders and are chosen to be larger, the brute-force method becomes infeasible. b) Suppose in case (b), the cryptanalyst has access to several encrypted messages, i.e., the texts 2 As 50, you can take any set of power 25 ⋅ , and Alice and Bob must equally order the elements of this set and construct a bijection 1.
1 = (11, 12), 2 = (21, 22), 3 = (31, 32),
Since there are ( − 2)! bijections of type and the vectors 1, 2, … belong to different sets, this information requires knowledge of the bijection , i.e., the defining sequence of . However, these objects are not available to the cryptanalyst, and searching for them by brute force requires generating ( − 2)! combinations. Moreover, for these combinations, one must also find the symbolic equivalents (which is also ! combinations), so this information does not allow the plaintext to be found in a reasonable time.
(c) Suppose in case (c), the cryptanalyst has access to both encrypted and decrypted messages, i.e., the data
1, 2, 3, … і 1 = −1(−1(1)), 2 = −1(−1(2)), 3 = −1(−1(3)), … where −1 maps the numeric text to the symbolic text.
Since the mappings , , and the system () are unknown to the cryptanalyst, it is not possible to recover the defining sequence from this data.
From the above example, it is evident that, in computational terms, the most complex step is the construction of inverse matrices in the ring . To simplify these computations, it is preferable to use the isomorphism ∶ → and perform calculations in the residue ring . Once the inverse matrices are found, the reverse substitutions can be performed to obtain the corresponding matrices in the ring .
It is known that the multiplicative group of units of the ring is an abelian group [6]. In order to apply the discrete logarithm function in this group, it must be cyclic, i.e., possess a generator. Thus, the question arises: under what conditions is the group of units of the ring cyclic? The answer is provided by Theorem 1. The multiplicative group of the ring is cyclic if and only if k is equal to 2, 4, or 2, where ≥ 1 and p is an odd prime [6]. 4. Message Formation From the above, it follows that Alice and Bob must exchange, via a secure channel, the tuple (, , , ), where , , , are the parameters of the GEN-G(, , , ) algorithm. If the order of the ring k is chosen to be a multiple of the order of the ring , i.e., = ⋅ , then, based on the coprimality of , , and , the methods for constructing the rings will be known, and the transformations for constructing the defining sequences of the rings can be taken identically for and . Furthermore, from the protocol and the example provided, it follows that, in order to transmit the desired message = (1, 2, … , ) it is necessary that the system of equations has a solution for arbitrary values of 1, 2, … , . The isomorphism between the rings and allows us to consider only the residue ring . The compatibility criterion for a system of linear congruences ≡ (mod ) of size × , ( < ) over the ring requires the existence of a solution to the congruence
11 + 22 + … + ≡ 1 (mod ), where 1, 2, … , are the values of the last coordinates in the solutions of the homogeneous system − 0 = 0 [7]. This condition is satisfied for any if the equations of the system are linearly independent and the determinant of the subsystem matrix 1 ≡ (mod ) of size × , formed by the linearly independent columns 1, 2, … , of the system ≡ (mod ), is coprime with the modulus . Then, for the subsystem matrix, there exists an inverse matrix, i.e., from 1 = (mod ) it follows that −11 1 = ≡ −11 (mod ) for any . A vector = (1, 2, … , ), whose coordinate indices 1, 2, … , coincide with those of the vector ≡ −11 (mod ), and the remaining coordinates are zero, will be a solution to the system.
Thus, Alice needs to construct a system of linear equations in which the equations are linearly independent and contain a subsystem whose matrix determinant is coprime with the modulus mm. To verify the linear independence of the expressions, Alice must solve the system ≡ 0 (mod ) and ensure that this system has only the trivial solution. She then constructs a subsystem with the described determinant properties.
Example 3. Let the letters of the English alphabet be naturally enumerated (see Table 1).
Step 1.
a) Suppose Alice constructs the following expressions in the ring 25 (expressions with negative coefficients are shown in parentheses, where negative coefficients are replaced by their additive inverses): and transforms them into the form where the matrix
b) Alice replaces the coefficients in the constructed expressions (), () and the matrix 1 with their counterparts from the factor set 50/ and obtaining the expressions which she sends to Bob via a public channel or publishes on her website.
Step 2. a) Bob, using the bijections and 1 finds the corresponding expressions () and () in the ring 25:
It is easy to verify that in the system of expressions (), the second and third columns form a subsystem whose determinant is 7, and 7 is coprime with the modulus 25 in the ring 25 (the compatibility conditions for the system () are satisfied).
Bob wishes to send Alice the message
tara tara tarara. b) Bob divides the message into blocks of two symbols per block (spaces between message symbols, corresponding to element 49, are omitted for simplicity in this example), and replaces them with their numeric equivalents from Table 1: ta ra ta ra ta ra ra 18,0 16,0 18,0 16,0 18,0 16,0 16,0 .
c) He solves the system of equations in the ring 25
and finds the solution ̄ = (
d) The value 1 = (18, 0) is kept secret. He selects the vector = (
Alice, using the received counterparts, finds the values and 1, and performs the following
computations:
a) She computes the inverse matrix to 1−1 in the ring 25:
b) She computes 1−1(1 − (
1−1 (
а) Bob solves the system of equations and finds the solution ̄ = (0, 18, 12, 0).
b) The value 2 = (16, 0) is kept secret. He selects the vector ̄ = (
c) Bob sends Alice the counterparts of the values і 1 in the ring .
Step 3. Alice, using the received counterparts, finds the values , 1 and performs the following
computations:
a) She finds the inverse matrix to 1−1 in the ring 25:
b) She computes 1−1 (1 − (
1−1 (21, 9) − (14, 11) = (
a) Bob solves the system of equations in the ring 25
and finds the solution ̄ = (
Alice computes
1−1(1 − (
(23, 0) − (
Since the next block is the same as the second, i.e 4 = (16, 0), Bob selects a new vector ̄ = (
= () = (21, 14), ̄ + ̄ = (
In the given example, the same ring was used throughout, but it is possible to change the ring for each transmission session or at certain intervals between transmissions. The vectors and ̄, which affect the values () and (̄ + ), can also be varied
The presented protocol can be made more complex by using different rings or different parameter
values—matrices and vectors—for each encrypted block. Furthermore, if the ciphertext is represented
by its counterparts in the ring 50
(
Given that computations in the ring are not standard in practice, the efficiency of encryption and decryption can be improved by utilizing the isomorphism between the rings and . Indeed, finding the additive inverse of an element in the ring reduces to computing − , and finding the multiplicative inverse of aa is performed using the extended Euclidean algorithm to solve the equation + = 1 (the extended Euclidean algorithm computes the decomposition + = , where d = gcd(, )). The result of this algorithm is the value = −1.
An obvious drawback of the described protocol is that the ciphertext is twice as long as the plaintext message.
During the preparation of this work, the authors used AI program Chat GPT 4.1 for correction of text grammar. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content.