RSA CRYPTOSYSTEM FOR RINGS WITH COMMUTING

IDEALS
arXiv:2206.14775v1 [math.RA] 29 Jun 2022

NASRUTDINOV M.F., TRONIN S.N.

Abstract. This article presents a generalization of the RSA cryptosystem for

rings with commuting ideals. An analogue of the Euler function for ideals and
the concept of an RSA-ideal are defined. An analog of a cryptosystem for the
ring with commuting ideals is formulated and a description of the RSA-ideals
for which this is possible is obtained.

1. Introduction
In [1] the authors generalized the well-known RSA cryptographic algorithm
to Dedekind rings. They replaced natural numbers with ideals of commutative
Dedekind rings. After some time it became clear that a similar idea could be real-
ized for rings that are not necessarily commutative or Dedekind ring. This paper
describes the initial stage of the implementation of this idea.
RSA is a public-key cryptosystem that is widely used for secure data transmis-
sion. Ron Rivest, Adi Shamir and Leonard Adleman described the algorithm in
1977 [2]. This cryptosystem is the object of intense study up to the present time.
Recall the idea of the original RSA [2]. The receiver of a message publishes the
number n, where n = pq is the product of two different secret large primes and the
encryption exponent e satisfying the condition that the greatest common divisor
gcd(e, ϕ(n)) = 1. Here ϕ(n) is the Euler’s function.
Let m be a bit string which we want to encrypt. Let’s represent m as a natural
number from 0 to n. The sender of the letter computes the ciphertext represented
by the number (or bit string) c = me (mod n), which is the encrypted message. The
receiver of the message selects 1 < d < ϕ(n) from the condition ed = 1 + ϕ(n)t.
Then the receiver recovers the original message by raising the ciphertext to the
power of d. Because med = m (mod n).
The secret key is a triple p, q, ϕ(n) = (p − 1)(q − 1). Without knowing p and q
it is very difficult to calculate ϕ(n), without ϕ(n) it is very difficult to calculate d,
i.e. to decrypt the message. The security of the RSA cryptosystem is based on the
factorization complexity n. Details can be found in the [3] book.
The security of the RSA cryptosystem is based on two mathematical problems:
the problem of factoring large numbers and the RSA problem. But the rise of
quantum computing becomes the threat to modern cryptography. Shor’s quantum
algorithm [9], in particular, provides a large theoretical speedup to the brute-forcing
capabilities of attackers targeting many public-key cryptosystems such as RSA (see
also [3]). Therefore, there is a practical need to find new cryptographic algorithms,
attacks on which will be difficult even for quantum computers. We investigate

Key words and phrases. Algebraic cryptography, rings with commuting ideals, RSA cryptosys-
tem, Euler’s function for ideals.
1
2 NASRUTDINOV M.F., TRONIN S.N.

the possibility of using commutative rings that are not principal ideal rings or non-
commutative rings to generalize the RSA cryptosystem. We show that a meaningful
generalization of RSA is possible for a fairly wide class of associative rings with
identity.
Let us briefly describe the content of the paper. In section 2 we consider the
special class of rings, namely rings witch commuting ideals (CI-rings). These rings
are quite convenient for generalizing the RSA cryptosystem. In section 3 we gen-
eralize Euler’s function for ideals of CI-rings. In section 4 we construct an analog
of the RSA algorithm for CI-rings and we define the concept of an RSA-ideal. The
main result of this paper is a description of the RSA-ideals. In fact, to generalize
the RSA cryptosystem we should use only intersection of maximal ideals.
The results of this research were announced in [11].

2. Rings with commuting ideals

All rings are assumed to be associative and with nonzero identity element. We
will consider rings with commuting ideals. As will be shown below, this class of rings
allows generalization of the RSA cryptoscheme and contains both commutative and
non-commutative rings.
Definition 1. A ring R is said to be a CI-ring (ring with commuting ideals) if
AB = BA for all ideals A, B of R.
As usual the product AB of two ideals A and B is the set of all finite sums of
elements of the form ab with a ∈ A and b ∈ B.
CI-rings have the following easily proved properties:
Theorem 1. [4]
(1) A homomorphic image of a CI-ring is a CI-ring.
(2) A finite direct product of CI-rings with unity is a CI-ring.
(3) If R is a CI-ring with unity, then for each positive integer n, the ring of
n × n matrices over R is also a CI-ring.
(4) Let R be a CI-ring and e = e2 ∈ R is the idempotent. Then eRe is a
CI-ring.
Proof The first two statements are obvious.
To prove the third statement, note that every ideal of Mn (R) is of the form
Mn (A) where A is an ideal of R.
To prove the last statement we use the fact that RR = R. Suppose A, B are
ideals of eRe. We have
AB = eReAeReeReBeRe = e(ReAeR)(ReeReBeR)e = e(ReeReBeR)(ReAeR)e = BA.
CI-rings were introduced by Armendariz and Heatherly in short proceedings
thesis [4]. At the moment, we do not know the literature where the theory of such
rings would develop. There are some examples of such rings in [5] and [6]. In [10,
Chapter 4] modules over CI-rings are considered.

Examples of CI-rings

1) Commutative rings.
2) Principal ideal domains. Recall that R is a principal ideal domain if R is a
domain of integrity and every one-sided ideal (right or left) is a principal one-sided
 RSA CRYPTOSYSTEM FOR RINGS WITH COMMUTING IDEALS 3

ideal (right or left respectively). These rings are considered in the third chapter of
[5].
Obviously, the rings of integers is a principal ideal domain. There are other
examples of this ring:
2.1) The subring of Hamilton’s quaternion algebra consisting of quaternions α0 +
iα1 + jα2 + kα3 , where the ai are either all rational integers or all halves of odd
integers. This subring is called the ring of Hurwitz quaternions.
2.2) Let K be any skew field with an endomorphism α and an α-derivation δ.
Then the skew polynomial ring K[x; α, δ] is a principal ideal domain whenever α is
an automorphism [6, Theorem 1.3.2].
3) Leavitt path algebras of directed graphs [7, Theorem 4.2].
For arbitrary rings the famous Chinese remainder theorem holds.
Theorem 2. [8, Theorem 18.30] If A1 , . . . , An are finitely many ideals of a ring
R, then the following conditions are equivalent:
n
T Qn
(1) The canonical map h : R/ Ai → R/Ai with h(r) = (r + A1 , r +
i=1 i=1
A2 , . . . , r + An ) is an isomorphism.
(2) For any set x1 , x2 , . . . , xn of elements of R the system of congruences X =
xi ( (mod A)i ) has a solution x ∈ R.
(3) The ideals A1 , . . . , An are comaximal in pairs, that is, Ai +Aj = R whenever
i 6= j.
For CI-rings we can prove additionally.
Corollary 1. Let R is a CI-ring and A1 , . . . , An are comaximal in pairs. Then
n
\ n
Y
Ai = Ai .
i=1 i=1

Proof We use induction on n.

Let n
T= 2. Suppose A, B are comaximal ideal and AB = BA. We shall prove
that A B = AB. It is sufficient to show that A ∩ B ⊂ AB. From R = A + B
we have 1 = a + b for some a ∈ A and b ∈ B. Then for all x ∈ A ∩ B we have
x = x(a + b) ∈ AB + BA = AB.
Now, suppose that n > 2 and that the result has been proved for smaller values
of n. For pairwise comaximal ideals A1 , . . . , An , An+1 of R we denote by B =
n
T n
Q
Ai = Ai . We claim that
i=1 i=1

n+1
Y \ n+1
\
Ai = BAn+1 = B An+1 = Ai .
i=1 i=1

By the Chinese remainder theorem there is x ∈ R such that x = 0 (mod Ai ) for

n
T
all i = 1, . . . , n and x = 1 (mod An+1 ). Then x ∈ Ai = B and 1 − x ∈ An+1 .
i=1
Thus, for any r ∈ R we have
r = rx + r(1 − x) ∈ B + An+1 .
Therefore B, An+1 are comaximal ideals and BAn+1 = B ∩ An+1 .
4 NASRUTDINOV M.F., TRONIN S.N.

Note. Corollary 1 will allow us to decompose RSA ideals of CI-rings into prod-
uct of maximal ideals and to introduce the Euler function for ideals with suitable
properties.

3. Euler’s function for ideals

In [1] the Euler’s function analog was defined for ideals of Dedekind rings. Note
that RSA cryptosystems with Dedekind rings were also considered in [12]. We
define the Euler’s function in the same way.
Definition 2. Let A be the ideal of a ring R and |U (R/A)| < ∞ where U (R/A) is
a group of units of R/A. The function
ϕ(A) = |U (R/A)|.
is called the Euler’s function of the ideal A.
Example 1: If R = Z then A = (n) = Zn and ϕ(A) = ϕ(n) in the usual sense.
Example 2: If R is the ring of Gaussian integers . Then
Y 1

2
ϕ(m) = |m| 1− 2 .
p|m
|p|
√
Example 3: If R = Z[ k] is a ring of the quadratic integers. Then
Y 1

ϕ(m) = |ν(m)| 1− ,
N (m)
p|m
√ √
where N (a + b k) = a2 − kb2 is norm of element of m = a + b k ∈ R and
ν(m) = |R/(m)|.
Example 4: If R is a polynomial ring over Galua field GF (q) then
Y
ϕ(m) = q deg(m) (1 − q −deg(p) ).
p|m

Theorem 3. Let R be a CI-ring. For finite set of pairwise comaximal ideals

A1 , . . . , An of the ring R we have
ϕ(A1 A2 . . . An ) = ϕ(A1 )ϕ(A2 ) . . . ϕ(A1 ).
Proof By the Chinese remainder theorem and Corollary 1 we have
Yn n
Y
R/ Ai = R/Ai .
i=1 i=1
n
Y n
Y n
Y n
Y
ϕR ( Ai ) = |U (R/ Ai )| = U ( R/Ai ) = |U (R/Ai )| = ϕ(A1 )ϕ(A2 ) . . . ϕ(A1 ).
i=1 i=1 i=1 i=1

4. RSA Cryptosystem for CI-rings and RSA-ideals

The RSA algorithm uses natural numbers.The security of RSA relies on the
practical difficulty of factoring the product of two large prime numbers. We replace
the ring Z in the scheme by some CI-ring R and the integers by ideals of the ring
R. Additionally, we assume that the Euler’s function for the ideals must exist and
be difficult to compute.
Suppose 2 < |R/A| < ∞. If gcd(e, ϕ(A)) = 1 and ed = 1 + ϕ(A)t for some
natural numbers e, d then we need med ≡ m (mod A) holds for all m ∈ R. The
 RSA CRYPTOSYSTEM FOR RINGS WITH COMMUTING IDEALS 5

encryption and decryption algorithm in case of the RSA cryptosystem for CI-rings
is similar to the classical case. Let’s describe it.
Suppose Bob wants to send messages to Alice that only she can decrypt. Alice
chooses two ideals M1 6= M2 ⊂ R. Then she calculates the ideal A = M1 · M2 . Also
Alice chooses an encryption exponent e that satisfies the condition gcd(e, ϕ(A)) = 1.
So, Alice’s public key is the pair (A, e) and she can keep it in the public domain.
After that, Alice calculates the decryption exponent d from conditions ed = 1 +
ϕ(A)t. Alice’s secret key is the triple (d, M1 , M2 ), which she keeps secret.
Suppose Bob wants to encrypt a message for Alice. He represents the message
as an element m ∈ W . The ciphertext c is obtained by raising the message to a
power equal to the open encryption exponent and taking the remainder modulo A
c = me (mod A).
Alice can decrypt the ciphertest c and get the original message as follows:
m = cd (mod A).
The message m = cd is represented by an element from the set W . W is a
complete system of remainders modulo A. Thus |(r + A) ∩ W | = 1 for each r ∈ R.
There is a bijection φ : W ↔ R/A. At the same time elements from W should be
convenient for encoding into a bit string.
In order for the cryptoscheme would work we need the condition med = m
(mod A) holds. We introduce the following definition.
Definition 3. Suppose A be a ideal of CI-ring R, R/A is a finite ring, ϕ(A) > 2,
e, d are natural numbers such that 1 < e, d < ϕ(A) and gcd(e, ϕ(A)) = 1, ed ≡
1 + ϕ(A)t.
We shall say that ideal A is said the RSA-ideal if xed ≡ x (mod A) for all x ∈ R.
The following theorem is a direct consequence of Jacobson’s theorem [13, Theo-
rem 3.1.2] on the commutativity of rings with the property xn(x) = x.
Theorem 4. Let A be an ideal of a CI-ring R then R/A is a commutative ring.
Our main result is the following.
Theorem 5. Let A be an ideal of a CI-ring R. The ideal A is RSA-ideal if and
only if A = M1 M2 . . . Mk where Mi is maximal ideal for any i = 1, . . . , k.
Proof
(⇒) Consider the factor ring R/A. Denote by s = ed = 1 (mod ϕ(A)). Then
for any x ∈ R/A we have xs = x.
Let us show that the quotient ring R/A has no nilpotent elements. Assuming
the converse, let x 6= 0 and n be the smallest number for which xn = 0.
If n < s then x = xs = xs−n xn = 0 and this contradicts to the choice of x.
If n > s then we divide n with remainder n = qs + r, q > 0, 0 ≤ r < s. Then
0 = xn = xqs+r = xsq xr = xq+r and we have a contradiction with the minimality
of n.
By the Wedderburn-Artin theorem, R/A is isomorphic to a direct sum of fields.
Indeed, R/A is a finite commutative ring without nilpotent elements. Hence its
Jacobson radical is equal to zero [13, Theorem 1.3.1] and R/A is the Artinian
semisimple ring. Thus, R/A is isomorphic to the direct sum of matrix rings over
division rings [13, Theorem 1.4.4 and Theorem 2.1.6].
6 NASRUTDINOV M.F., TRONIN S.N.

Since the matrix ring of order ≥ 2 is not commutative it follows that R/A ∼
=
F1 ⊕ F2 ⊕ Fk where Fi is a field for each i.
Consider an epimorphism θ : R → R/A and projections πj : R/A → Fj . Then
k
T
Mj = ker πj θ are maximal ideals. By the Chinese remainder theorem R/ Mj =
j=1
n
Q
R/Ai . Therefore,
i=1
k
\ k
\
ker πj θ = Mj = M1 M2 . . . Mk .
j=1 j=1
k
T k
T
We claim that A = ker πj θ. Clearly, A = ker θ ⊂ ker πj θ. Conversely, if
j=1 j=1
k
T
r ∈ R 6∈ A and r ∈ ker πj θ then θ(r) = r+A 6= 0 but (π1 θ(r), π2 θ(r), . . . , πk θ(r)) =
j=1
n
Q
(0, 0, . . . , 0). It is impossible because R/A and R/Mj are isomorphic.
j=1
(⇐) Let A = M1 M2 . . . Mk be the product of maximal ideals, s = ed = 1 +
t · ϕ(A) = 1 + t · ϕ(M1 )ϕ(M2 ) . . . ϕ(Mk ). Then Fj = R/Mj are finite skew fields
(fields, due to the commutativity of finite skew fields) and by the Chinese remainder
theorem R/A ∼ = F1 ⊕ F2 ⊕ . . . ⊕ Fk .
Then U (R/A) = U (F1∗ ) × U (F2∗ ) × . . . × U (Fk∗ ) where F ∗ = F \ {0}. If x ∈ A
then xs ∈ A and xs = x (mod A).
If x 6∈ A then the image of x in R/A can be represented as
x = (x1 , x2 , . . . , xk ) ∈ F1 ⊕ F2 ⊕ . . . ⊕ Fk .
It suffices to show that xsj = xj .
If xj = 0 then the assertion is trivial. If xj 6= 0, then xj ∈ Fj∗ = U (Fj ) and by
ϕ(Mj )
the Lagrange theorem on the element orders in the group xj = 1. Recall that
ϕ(Mj ) = |U (Fj )|. Thus,
1+t·ϕ(M1 )ϕ(M2 )...ϕ(Mk )
xsj = xj = xj .
Corollary 2. In the definition of the RSA-ideal A of ring R any number e coprime
to ϕ(A) is allowed.

5. Conclusions and open problems

From a practical point of view, the ring for building an RSA cryptosystem should
not be complicated. This means that the elements of this ring can be quite conve-
niently represented in the computer’s memory, and operations with such elements
are easily computable.
At the same time, to implement the RSA analogue protocol, it is necessary that
the task of finding the secret key d from public keys be a computationally difficult
task.
It follows from the description of RSA ideals given in the theorem that the
security of a hypothetical encryption protocol will depend both on the complexity
of calculating ϕ(A) and on the complexity of the problem of decomposing this ideal
into a product of maximal ideals. The uniqueness of such a decomposition is not
assumed. The RSA ideal in this scheme will play the role of one of the public keys.
 RSA CRYPTOSYSTEM FOR RINGS WITH COMMUTING IDEALS 7

The results of our research give a hint in which direction we can look for non-
commutative rings suitable for application in practical cryptography. An open
problem is if there are good rings apart from Z.
The ring of Hurwitz quaternions if we replace of natural numbers by ideals does
not provide any advantages compared to Z. This follows from the description
of the ideals of this ring [14, Theorem 211]. However, in this case, there is a
fairly meaningful description of simple elements which are not directly related to
the structure of ideals [15, Chapter 5]. So it is not worth completely excluding
Hurwitzian quaternions from consideration yet.
The next candidates for research may be non-commutative principal ideal do-
mains. They are considered fairly simple. In [5] it shows that the ideals of a
non-commutative principal ideal ring commute.
Another well-studied class of rings with commuting ideals are the skew poly-
nomial rings [16]. Finally, it is of interest to find out which of the finite non-
commutative rings may be suitable for use in the ring analogs of the RSA cryp-
tosystem. To begin with, we can pose the question of characterizing finite non-
commutative rings with commuting ideals.
Another interesting question from the point of view of ring theory is the following:
Whether it is possible to weaken the conditions in the definition of RSA-ideals, for
example, to weaken the condition that the quotient ring is finite.

References
[1] Petukhova, K.A., Tronin, S.N. “RSA Cryptosystem for Dedekind Rings ”Lobachevskii Jour-
nal of Mathematics, 37(3), 284-287 (2016). https://doi.org/10.1134/S1995080216030197
[2] Rivest R.L., Shamir A. and Adleman L. “A method for obtainig digital signatures and public-
key cryptosystems ”Communications of the ACM 21(2), 120-126 (1978).
[3] Song Y. Yan Cryptanalytic attacks on RSA (Springer 2008)
[4] Armendariz E.P. “Rings with commuting ideals ”In Report 91th Annual Meeting Texas
section of the MAA, (2011).
[5] Jacobson N. The Theory of Rings (Mathematical Surveys and Monographs Volume: 2; 1943)
[6] P.M. Cohn Free Ideal Rings and Localization in General Rings (Cambridge University Press,
2009) https://doi.org/10.1017/CBO9780511542794
[7] Rangaswamy, K.M. “The Multiplicative Ideal Theory of Leavitt Path Algebras of Directed
Graphs - A Survey ”In: Facchini, A., Fontana, M., Geroldinger, A., Olberding, B. (eds) Ad-
vances in Rings, Modules and Factorizations. Rings and Factorizations 2018. Springer Pro-
ceedings in Mathematics & Statistics, vol 321. Springer, Cham. https://doi.org/10.1007/978-
3-030-43416-8 16
Rangaswamy, K.M. “The Multiplicative Ideal Theory of Leavitt Path Algebras of Directed
Graphs - A Survey ”In: Facchini, A., Fontana, M., Geroldinger, A., Olberding, B. (eds) Ad-
vances in Rings, Modules and Factorizations. Rings and Factorizations 2018. Springer Pro-
ceedings in Mathematics & Statistics, vol 321. Springer, Cham. https://doi.org/10.1007/978-
3-030-43416-8 16
[8] C. Faith Algebra II, Ring Theory (Springer, Berlin, 1976) https://doi.org/10.1007/978-3-642-
65321-6
[9] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring ”In
Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134,
doi: 10.1109/SFCS.1994.365700.
[10] A.A. Tuganbaev “Multiplication Modules ”Journal of Mathematical Sciences 123, 3839 - 3905
(2004). https://doi.org/10.1023/B:JOTH.0000036653.76231.05
[11] M.F. Nasrutdinov, S.N. Tronin, “Extension of RSA Cryptosystems to Rings with Commuting
Ideals ”In Proceedings of the XVII International Conference dedicated to the 100th anniver-
sary of the birth of Professor N.I. Feldman and the 90th anniversary of the birth of Professors
A.I. Vinogradov, A.V. Malyshev and B.F. Skubenko. 2019, Tula, p. 93-95. Russian.
8 NASRUTDINOV M.F., TRONIN S.N.

[12] N. V. Kondratyonok, “Analysis of the RSA-cryptosystem in abstract number rings ”Jour-

nal of the Belarusian State University. Mathematics and Informatics, 1 (2020), 13-21,
https://doi.org/10.33581/2520-6508-2020-1-13-21. Russian.
[13] I. N. Herstein Noncommutative Rings (University of Chicago, Publication: Carus Mathemat-
ical Monographs 1994, Volume 15) DOI: https://doi.org/10.5948/UPO9781614440154
[14] L. Redei Algebra. Vol. 1. (Pergamon Press Ltd., Oxford, 1967). .
[15] John H. Conway, Derek A. Smith On Quaternions and Octonions. Their Geometry, Arith-
metic, and Symmetry (New York, 2003). https://doi.org/10.1201/9781439864180
[16] K. R. Goodearl, E. S. Letzter Prime Ideals in Skew and q-Skew Polynomoal Rings (Memoirs
of the AMS, 521, 1994).