An Improved Public Key Cryptographic Algorithm Based on Chebyshev Polynomials and RSA

Abstract

Due to its very desirable properties, Chebyshev polynomials are often used in the design of public key cryptographic systems. This paper discretizes the Chebyshev mapping, generalizes the properties of Chebyshev polynomials, and proposes an improved public key encryption algorithm based on Chebyshev chaotic mapping and RSA, i.e., $CRPKC-K_i$. This algorithm introduces alternative multiplication coefficients $K_i$, the selection of which is determined by the size of $T_r\left(T_d\left(x\right)\right)mod N=T_d\left(T_r\left(x\right)\right)mod N$, and the specific value selection rules are shared secrets among participants, overcoming the shortcomings of previous schemes. In the key generation and encryption/decryption stages, more complex intermediate processes are used to achieve higher algorithm complexity, making the algorithm more robust against ordinary attacks. The algorithm is also compared with other RSA-based algorithms to demonstrate its effectiveness in terms of performance and security.

1. Introduction

At its essence, cryptography design and analysis is a mathematical technique for ensuring secure communication over insecure channels, closely related to computer technology and electronic communication technology. Although traditional symmetric encryption systems are highly efficient, the security of the ciphertext is entirely dependent on the secrecy of the key in the process of key distribution and management, and once the key is leaked, the confidentiality is lost [1]. When the sending and receiving ends are far apart and the key needs to be changed frequently, it is difficult to pass the key between each other. The concept of public-key cryptography was first proposed by Diffie and Hellman in their 1976 paper “New Directions in Cryptography” [2], which addresses the confidentiality problems in symmetric encryption systems, particularly in multi-user communication networks.

In 1977, Rivest, Shamir, and Adleman proposed the first relatively complete public-key cryptographic algorithm, the RSA algorithm [3]. Since then, a large number of public-key cryptographic algorithms have been proposed based on different computational problems, such as the Mer–Hellman knapsack algorithm, McEliece algorithm, ElGamal algorithm, elliptic curve cryptography, lattice-based cryptography, and password-based public-key cryptography.

The RSA public-key cryptographic system is still recognized as a well-performing cryptographic system. It is the first algorithm that can be used for both digital encryption and digital signatures. Its security is based on integer factorization, and the construction of the system is based on Euler’s theorem, which has an extremely important position in modern cryptography. With the rapid development of computer technology, many encryption methods for RSA have become relatively easy to crack [4,5,6,7,8]. Traditional public-key cryptographic algorithms are constantly facing various challenges, so it is necessary to study new practical public-key cryptographic algorithms as supplements or replacements for current public-key cryptographic algorithms.

According to relevant methods, the author conducted a systematic search for research articles on standard or modified RSA algorithms and their various applications, and a total of approximately 84 related articles were found [9]. These articles were then divided into several domains or categories, such as cloud security [10,11], image cryptography [12,13], wireless security, and others. In recent years, lightweight cryptographic systems using hybrid variants of RSA have been proposed, showing effective results in smart devices and IoT devices [14,15]. Based on the literature [9], we also analyzed the literature from the past two years [16,17]. Figure 1 categorizes the progress of all RSA variants based on different categories of publications each year. We can see that enhancements to the RSA algorithm have always been a popular research direction, which is also the goal pursued in this paper.

In

Table 1. Algorithm analysis-and-evaluation of the recent related enhanced models.

Algorithm Model	Total Modulus	Intermediate Variables as of Standard RSA	Encryption Scheme	Key Generation	Decryption Scheme	Shortcomings/Comments
Rivest, R.L. et al. [3]	$1,\mathrm{i}.\mathrm{e}.,\mathrm{N}$	Not Any	$C=M^e\mathit{mod}N$	$ed=1\mathit{mod}\phi \left(N\right)$	$M=C^d\mathit{mod}N$	Security is not efficient
Minni et al. [18]	$1,\mathrm{i}.\mathrm{e}.,\mathrm{N}$	$X(\leftrightarrow N)$	$C=M^e\mathit{mod}X$	$ed=1\mathit{mod}\phi \left(X\right)$	$M=C^d\mathit{mod}X$	Higher time Complexity [19]
Thangavel et al. [19]	$3,\mathrm{i}.\mathrm{e}.,\mathrm{n},$$\mathrm{m},\mathrm{N}$	$e_1,e_2,e={e_1}^{e_2}$	$C=M^e\mathit{mod}N$	$ed=1\mathit{mod}(\phi \left(N\right)\cdot e_1)$	$M=C^d\mathit{mod}N$	Same security level as RSA [20]
Mathur et al. [21]	$1,\mathrm{i}.\mathrm{e}.,\mathrm{N},$$\mathrm{L}\to \mathrm{N}$	$P,Q,O,N,s.t.,$ $Q=P\cdot e$	$C=M^e\mathit{mod}N$	$ed=1\mathit{mod}\phi \left(N\right)$	$M=C^d\mathit{mod}N$	Slower, i.e., higher time [22]
Panda and Chattopadhyay [23]	$1,\mathrm{i}.\mathrm{e}.,\mathrm{N}$	$P_1,W$	$C=M^e\mathit{mod}W$	$ed=1\mathit{mod}(\phi \left(N\right)\cdot P_1)$	$M=C^d\mathit{mod}W$	Security is not efficient [24]
Raza Imam et al. [17]	$3,\mathrm{i}.\mathrm{e}.,\mathrm{N}$	$e_1,e_2=e XOR N$	$C=M^{e_2}\mathit{mod}N$	$e_1{d}_1=1\mathit{mod}\phi \left(N\right)$	$M=C^{d_2}\mathit{mod}N$	Lack of proof

, we focus on introducing popular RSA algorithms that are relevant to this research and have improved the performance and security of RSA to varying degrees. Some of these methods are borrowed and compared with the proposed method, while others are evaluated theoretically.

The natural relationship between the basic properties of chaos transformations, such as the mixture, sensitivity to parameters and initial values, and cryptography were mentioned in Shannon’s classic paper [25]. Research on chaotic public-key cryptography is still relatively weak compared to chaotic sequences and block cipher systems, and there are few practical and efficient encryption schemes based on chaos. Paying attention to the good properties of chaotic mappings and traditional cryptology criteria is still a new research field [26]. In [27], L. Kocarov and Z. Tasev proposed a public-key encryption method based on Chebyshev polynomials. Unfortunately, P. Bergamo pointed out its insecurity and inefficiency [28]. Zhao et al. proposed a new key agreement scheme based on chaotic mappings using the traditional RSA algorithm and discrete logarithm problems over finite fields. The scheme is based on the values of Chebyshev polynomials over finite fields, thereby avoiding various active attacks in the past and ensuring key agreement security. At the same time, the key agreement scheme can also achieve identity authentication functions [29]. Benasser et al. proposed an identity-based encryption scheme based on Chebyshev polynomials, but it has security flaws. Wang et al. proposed a corresponding identity authentication scheme, and the key exchange protocol based on Chebyshev polynomials is gradually being improved and perfected [30].

In recent years, there have been some new research advances in chaotic public-key cryptography [31,32,33,34]. In [35], Hsiao proposed an RSA encryption algorithm based on chaotic synchronization. However, RSA must use at least 1024 bits of digits to be considered secure under today’s computational capabilities. Ruzai, W.N.A. proposed a solution by giving examples to illustrate that near-square prime numbers could potentially lead to RSA being completely broken in [36]. Lawnik proposed two new cryptographic systems based on modified Chebyshev polynomials in the paper [37]. Gupta proposed a new lightweight image encryption algorithm based on session key using Chebyshev chaotic mapping and hybrid mix [38]. Patgiri proposed future solutions for RSA on traditional computers in the paper [39]. Ryu proposed an improved and secure Chebyshev chaotic mapping user authentication scheme in the paper [40].

This article discretizes the Chebyshev mapping, promotes the properties of Chebyshev polynomials, and designs an improved public key encryption algorithm based on the Chebyshev chaotic mapping and RSA, i.e., $CRPKC-K_i$. This algorithm overcomes the shortcomings of previous schemes and provides higher security. The analysis and experimental results show that this algorithm has strong robustness against ordinary attacks.

The article is organized as follows. Section 2 is the foundation of the rest of the article, as it includes the description of public key encryption algorithm, the extensive properties of Chebyshev mapping, and the Chebyshev-RSA public key cryptosystem. In Section 3, we propose an improved public key encryption algorithm based on Chebyshev polynomials and RSA. Section 4 describes the software implementation and provides examples. Section 5 presents some performance analyses. Finally, the conclusion and future scope is drawn in the last section.

2. Preliminaries

2.1. The General Public Key Cryptography Algorithm Can Be Described as Follows [1]

• Each user generates a key pair $k=(k_d,k_e)$, where $k_d$ represents the private key and $k_e$ represents the public key. The public key cryptography algorithm requires that $k_d$ can be derived theoretically from $k_e$, but in practice, it is not feasible due to the large computational complexity.
• The information sender encrypts the plaintext p using the publicly available key $k_e$ of the information receiver: $E(p,k_e)=C$, where $p$ represents the plaintext and $C$ represents the encrypted ciphertext.
• The information receiver decrypts using their privately held secret key $k_d$: $D(C,k_d)=p$.

2.2. Chebyshev Polynomials and Their Properties

Let $C[-\mathrm{1,1}]$ be a vector space consisting of all continuous real-valued functions on $[-\mathrm{1,1}]$, then $\left\{\mathit{cos}(n{\mathit{cos}}^{-1}(x\right)){\}}_{n=0}^{n=\infty }$ is a set of bases on $C[-\mathrm{1,1}]$. Let

$$T_n=\mathit{cos}(n{\mathit{cos}}^{-1}(x\left)\right),$$

(1)

then $T_n$ is called the $n$ order Chebyshev polynomial of the first kind. It has the following properties:

•

First,

$$T_0=1, T_1=x, \mathrm{and} T_{n+2}\left(x\right)=2x{T}_{n+1}\left(x\right)-T_n\left(x\right);$$

(2)

•

Second, define the mapping ${\rho }_n:x\to T_n$ on $[-\mathrm{1,1}]$, then the following semi-group property holds:

$${\rho }_{mn}\left(x\right)={\rho }_m\left({\rho }_n\right(x\left)\right)={\rho }_n\left({\rho }_m\right(x\left)\right).$$

(3)

To clearly state the design idea of the chaotic key scheme, we need to extend its properties.

Theorem 1.

The semi-group property of Chebyshev polynomials holds on the interval  $(-\infty ,+\infty )$;

Theorem 2.

If  $x$ is a positive integer and  $p$ is an odd prime number, then

$$T_p\left(x\right)\equiv x\left(\mathit{mod}p\right);$$

(4)

Theorem 3.

Let $p$ and  $q$  be relatively prime, and  $x$  and  $e$  be positive integers. If  $T_e\left(x\right)\equiv x\left(\mathit{mod}p\right)$  and  $T_e\left(x\right)\equiv x\left(\mathit{mod}q\right)$, then

$$T_e\left(x\right)\equiv x\left(\mathit{mod}pq\right).$$

(5)

Proof. 

Since $(p,q)=1$, there exist integers $s$ and $t$ such that $sp+tq=1$, therefore, $T_e\left(x\right)=sp{T}_e\left(x\right)+tq{T}_e\left(x\right)\equiv spx+tqx\equiv x\left(\mathit{mod}pq\right)$. □

Corollary 1.

If $T_{\phi }\left(x\right)\equiv 1$ for all  $x$  and there exist positive integers  $e$  and  $d$  satisfying  $ed\equiv 1\left(\mathit{mod}\phi \right)$, then

$$T_{ed}\left(x\right)\equiv x\left(\mathit{mod}pq\right),$$

(6)

where  $p$  and  $q$  are coprime primes.

2.3. Rivest–Shamir–Adleman

The security of RSA is based on the difficulty of factoring large numbers. Its public key and private key consist of a pair of large primes. The difficulty of recovering plaintext from a public key and ciphertext is equivalent to factoring the product of two large primes.

A detailed description of the RSA algorithm is as follows:

• Select two random large primes $p$ and $q$, each with at least 512 bits, ensuring that the difference between them is not too large or too small;
• Calculate the modulus $n=pq$ and the Euler’s totient function value $\phi \left(n\right)$;
• Select a number $e$ and use the extended Euclidean algorithm to find $d$ that satisfies $ed=1\left(\mathit{mod}\phi \right(n\left)\right)$;
• The information receiver publishes the public key $(e,n)$, with $d$ as the private key;
• The information sender divides the plaintext into blocks, such that each block is a positive integer $m$ less than $n$, and encrypts it using $c=m^e\left(\mathit{mod}n\right)$;
• The information receiver decrypts using the privately saved key $d$ according to the equation $m=c^d\left(\mathit{mod}n\right)$.

From the above algorithm, it can be observed that:

$$m=c^d=(m^e{)}^d=m^{ed}=m$$

Usually, attacks on RSA target the protocols rather than the specific algorithm itself, but that discussion is beyond the scope of this explanation.

2.4. Chebyshev-RSA Public Key Cryptosystem

Kocarev et al. [41] proposed a Chebyshev-based RSA-type public key cryptography algorithm (Chebyshev-RSA Public Key Cryptosystem, CRPKC) based on the periodicity of $T_n\left(x\right)$, as shown below.

Assuming that Alice is the sender and Bob is the receiver, the communication process is as follows.

• Key generation. Bob randomly generates two different large prime numbers $p$ and $q$, calculates $N=pq$ and $\phi =(p^2-1)(q^2-1)$, chooses a random number $e$ such that $1<e<\phi$ and $\mathit{gcd}(e,\phi )=1$, and calculates the integer $d$ such that $1<d<\phi$ and $ed\equiv 1\mathit{mod}\phi$; Bob’s public key is $(N,e)$ and the private key is $d$;
• Message encryption. Alice converts the message to be encrypted into an integer $m(0\le m<N)$, calculates the ciphertext $c=T_e\left(m\right)\left(\mathit{mod}N\right)$ based on Bob’s public key $(N,e)$, and sends it to Bob;
• Message decryption. Bob receives the ciphertext $c$ and uses the private key $d$ to obtain the plaintext $m=T_d\left(c\right)\left(\mathit{mod}N\right)$.

Although CRPKC has its unique characteristics, due to the lack of widespread application and research, it has certain uncertainties in terms of security, such as man-in-the-middle attacks and tampering attacks. Additionally, it does not provide identity authentication.

3. Improved Public Key Encryption Algorithm

The improved public key encryption algorithm is based on the aforementioned CRPKC algorithm and uses alternative multiplication factors $K_i$. The selection of $K_i$ is determined by the magnitude of $T_r\left(T_d\right(x\left)\right)\mathit{mod}N=T_d\left(T_r\right(x\left)\right)\mathit{mod}N$, where $T\left(x\right)$ represents the Chebyshev polynomial, $i=\mathrm{1,2}\cdots n$. The specific rules for selecting $K_i$ values and the size of $n$ are secrets shared only among the participants. Therefore, this algorithm not only enhances computational complexity but also introduces digital signatures to prevent ciphertext from being subjected to man-in-the-middle attacks and tampering. The improved algorithm, $CRPKC-K_i$, inherits the advantages of the CRPKC algorithm while also taking into account the good properties of Chebyshev polynomials, resulting in better security and reliability.

The introduction of selective factors $K_i$ follows the following selection rules:

$$\left\{\begin{array}{c}{K}_1,0\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N=T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le \frac{N}{n} \\ K_2,\frac{N}{n}\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N=T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le \frac{2N}{n} \\ ⋮\\ { K}_i,\frac{(i-1)N}{n}\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N=T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le \frac{iN}{n} \\ ⋮\\ K_n,\frac{(n-1)N}{n}\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N=T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le N \end{array} .\right.$$

(7)

In the above equation, $N$ is a large prime number, and $n$ represents the number of $K_i$. It is easy to see from Chebyshev’s semigroup property that $T_r\left(T_d\right(x\left)\right)\mathit{mod}N=T_d\left(T_r\right(x\left)\right)\mathit{mod}N$.

$\left(A\mathit{mod}N\right)\left(\mathit{mod}p\right)=A\left(\mathit{mod}p\right)$, where $A$ represents Chebyshev polynomial, and $N=p\cdot q$, where $p$ and $q$ are two large prime numbers.

The algorithm is described as follows (assuming Alice wants to communicate with Bob):

3.1. Key Generation

• Alice randomly generates two distinct large prime numbers $p$ and $q$, with similar sizes, but $p-q$ is a large integer;
• Calculate $N=pq$ and $\phi =(p-1)(q-1)$;
• Randomly select an integer $e$, choose a random number $x\in Z_N$ such that $1<e<\phi$ and $\mathit{gcd}(e,\phi )=1$;
• Use the extended Euclidean algorithm to calculate $d$, such that $1<d<\phi$ and $ed\equiv 1\mathit{mod}\phi$, and calculate $A=T_d\left(x\right)\left(\mathit{mod}N\right)$;

At this point, the keys have been generated. Alice’s public key is $(N,A,e)$, and the private key is $d$.

3.2. Encryption

• Bob obtains Alice’s public key $(N,A,e)$;
• Randomly choose $r<N$, calculate $T_r\left(A\right)\left(\mathit{mod}N\right)=T_r\left(T_d\right(x\left)\right)\left(\mathit{mod}N\right)$, and select $K_{iB}$ based on Equation (6);
• Express the message to be encrypted as an integer $m$, calculate $M=K_{iB}m$, and satisfy $0\le M<N$;
• Use the public key to calculate $C=R_e\left(M\right)=M^e\left(\mathit{mod}N\right)$, and $B=T_r\left(x\right)\left(\mathit{mod}N\right)$. $Y_A=E_k\left(Si{g}_A\right(C,B\left)\right)$, where $E_k(\square )$ is a mature symmetric encryption system;
• Send the ciphertext $(C,B,Y_A)$ to Alice.

3.3. Decryption

• Alice receives the ciphertext $(C,B,Y_A)$, decrypts $Y_A$, and checks $Si{g}_A(C,B)$. If it is correct, continue; otherwise, stop;
• Calculate $M=R_{ed}(C)=C^d(\mathit{mod}N)$ using the private key $d$, $T_d\left(B\right)\left(\mathit{mod}N\right)=T_d\left(T_r\right(x\left)\right)\left(\mathit{mod}N\right)$, and select $K_{iA}$ based on Equation (7);
• Calculate $m=M/K_{iA}$.

4. Algorithm Implementation

4.1. Feasibility Analysis

Since the semigroup property of Chebyshev polynomials holds on the interval $(-\infty ,+\infty )$, the decryption calculation is feasible. It is an important problem to evaluate Chebyshev polynomials in order to reduce the calculation time of $T_n\left(x\right)$. There are two ways to implement a fast algorithm for Chebyshev polynomial $T_n\left(x\right)$.

The first method is to use the semigroup property of Chebyshev polynomials to implement a fast algorithm. The algorithm is described as follows:

Let the integer $s$ be decomposed as:

$$s=\underset{k_1}{\underbrace{s_1\cdots s_1}}\underset{k_2}{\underbrace{s_2\cdots s_2}}\cdots \underset{k_i}{\underbrace{s_i\cdots s_i}}=s_1^{k_1}{s}_2^{k_2}\cdots s_i^{k_i}$$

(8)

Then, due to the semigroup property of Chebyshev polynomials, it can be obtained that:

$$T_s(x)=T_{s_1}^{k_1}(T_{s_2}^{k_2}(\cdots T_{s_i}^{k_i}(x)))$$

(9)

To calculate $T_s\left(x\right)$, the number of iterations required is $k_1+k_2+\cdots k_i<<s$. And the efficiency is higher when the value of $s$ has more factors.

Although this algorithm is much faster than recursively calculating according to the definition, it is also composed of many loops and has high memory requirements for computers. Especially when $n$ is a large number, the amount of computation is quite large. Therefore, the second matrix-based calculation method, which has been experimentally proven to be more efficient, is introduced below.

From the definition of Chebyshev polynomials $T_{n+1}\left(x\right)=2x{T}_n\left(x\right)-T_{n-1}\left(x\right)$, $T_0=1, T_1=x$, if we transform the above equation into a matrix expression, it can be represented as follows:

Let the integer $s$ be decomposed as:

$$\left[\begin{array}{c}{T}_n\\ T_{n+1}\end{array}\right]=\left[\begin{array}{cc}0& 1\\ -1& 2x\end{array}\right]\left[\begin{array}{c}{T}_{n-1}\\ T_n\end{array}\right]={\left[\begin{array}{cc}0& 1\\ -1& 2x\end{array}\right]}^n\left[\begin{array}{c}{T}_0\\ T_1\end{array}\right]$$

(10)

From the above equation, it can be seen that the key to calculating $T_n\left(x\right)$ lies in finding the value of the matrix ${\left[\begin{array}{cc}0& 1\\ -1& 2x\end{array}\right]}^n$. The flowchart of the specific algorithm is shown in Figure 2.

4.2. An Example

Here we list a simple example to illustrate the algorithm and basic steps.

We now discuss the software implementation of the algorithm and provide a practical example. PYTHON is a popular and powerful programming software currently available for calculations. In our software implementation, we used an algorithm library in the Windows environment.

4.2.1. Generation of Secret Key

• Alice randomly generates two distinct large prime numbers, $p=127$ and $q=113$;
• Compute $N=pq=\mathrm{14,351}$ and ${\phi }_{\left(n\right)}=(p-1)(q-1)=\mathrm{14,112}$;
• Select a random integer $e=5$ and a random number $x=13\in Z_N$, where $\mathit{gcd}(e,\phi )=\mathit{gcd}(5, \mathrm{14,112})=1$;
• Use the extended Euclidean algorithm to calculate $d=5645$, satisfying $1<d<\phi$, and $ed\equiv 1\mathit{mod}\phi$. Calculate the Chebyshev polynomial $A=T_d\left(x\right)\left(\mathit{mod}N\right)=\mathrm{13,558}$;

At this point, Alice’s public key is $(N,A,e)=(\mathrm{14,351}, \mathrm{13,558}, 5)$, and the private key is $d=5645$.

4.2.2. Encryption

• Bob obtains Alice’s public key $(N,A,e)=(\mathrm{14,351}, \mathrm{13,558}, 5)$;
• Choose a random $r=15<N$ and calculate $T_r\left(A\right)\left(\mathit{mod}N\right)=T_r\left(T_d\right(x\left)\right)\left(\mathit{mod}N\right)=9257$. Select $K_{iB}$ according to Equation (7). For simplicity, take $n=5$ and $K_{iB}=2i+1$ as an arithmetic progression. In this case, calculate Equation (11) and select $K_{iB}=K_4=9$.

  $$K_i=\left\{\begin{array}{l}3,\hspace{1em}\hspace{1em}0\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N\le 2870.2 \\ 5,\hspace{1em}\hspace{1em}2870.2\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N\le 5740.4 \\ 7,\hspace{1em}\hspace{1em}5740.4\le T_r\left(T_d\left(x\right)\right)\mathit{mod}N\le 8610.6 \\ 9,\hspace{1em}\hspace{1em}8610.6\le T_r\left(T_d\right(x\left)\right)\mathit{mod}N\le \mathrm{11,480.8}\\ 11,\hspace{1em} \mathrm{11,480.8}\le T_r\left(T_d\right(x\left)\right)\mathit{mod}N\le \mathrm{14,351}\end{array}\right.$$

  (11)

In this example, $8610.6<T_r\left(A\right)\left(\mathit{mod}N\right)=9257<\mathrm{11,480.8}$; therefore, choose $K_{iB}=K_4=9$;

3.

Express the message to be encrypted as an integer $m=1234$ and calculate $M=K_{iB}m=\mathrm{11,106}$, satisfying $0\le M<\mathrm{14,351}$;

4.

Compute the ciphertext $C=R_e\left(M\right)=M^e\left(\mathit{mod}N\right)=8438$;

5.

$B=T_r\left(x\right)\left(\mathit{mod}N\right)=\mathrm{12,347}$.

Send the ciphertext $(C,B)=(8438, \mathrm{12,347})$ to Alice.

4.2.3. Decryption

• Alice receives the ciphertext $(C,B)=(8438, \mathrm{123,47})$;
• Calculate $M=R_{ed}(C)=C^d(\mathit{mod}N)=8438^{5456}(\mathit{mod}1\mathrm{4,351})=\mathrm{11,106}$ using the private key $d$. At this point, $8610.6<T_d\left(B\right)\left(\mathit{mod}N\right)=T_d\left(T_r\right(x\left)\right)\left(\mathit{mod}N\right)=9257<\mathrm{11,480.8}$. Similarly, calculate Equation (12) and select $K_{iA}=K_4=9$;

  $$K_i=\left\{\begin{array}{l} 3,\hspace{1em}\hspace{1em}0\le T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le 2870.2\\ 5,\hspace{1em}\hspace{1em}2870.2\le T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le 5740.4 \\ 7,\hspace{1em}\hspace{1em}5740.4\le T_d\left(T_r\left(x\right)\right)\mathit{mod}N\le 8610.6 \\ 9,\hspace{1em}\hspace{1em}8610.6\le T_d\left(T_r\right(x\left)\right)\mathit{mod}N\le \mathrm{11,480.8}\\ 11,\hspace{1em}\hspace{1em}\mathrm{11,480.8}\le T_d\left(T_r\right(x\left)\right)\mathit{mod}N\le \mathrm{14,351}\end{array}\right.$$

  (12)
• Calculate $m=M/K_{iA}=\mathrm{11,106}/9=1234$.

Then, send it to Alice. Finally, Alice recovers the message $m$.

In this example, $p,q$ should be set as large primes in practical applications to achieve higher security, and the selection of other integers follows a similar approach.

4.3. Mathematical Proof of The Proposed $CRPKC-K_i$ Algorithm

Mathematically, the proposed algorithm $\mathrm{C}\mathrm{R}\mathrm{P}\mathrm{K}\mathrm{C}-{\mathrm{K}}_{\mathrm{i}}$ is proven as follows.

The encrypted text C is calculated using:

$$C=R_e\left(M\right)=M^e\left(\mathit{mod}N\right)=(m\cdot K_{iB}{)}^e(\mathit{mod}N)$$

(13)

Plaintext message $m$ is calculated using:

$$m=M/K_{iA}=C^d(\mathit{mod}N)/K_{iA}$$

(14)

Now, the objective is to fetch back the message $M$ from $C^d(\mathit{mod}N)$, then calculate the original message $m=M/K_{iA}$.

Proof. 

Since Equations (13) and (14), we can say, $C^d\left(\mathit{mod}N\right)=M^{ed}\left(\mathit{mod}N\right)=(K_{iB}\cdot m{)}^{ed}\left(\mathit{mod}N\right)$, where, Bob calculates $K_{iB}=T_r\left(A\right)\left(\mathit{mod}N\right)=T_r\left(T_d\right(x\left)\right)\left(\mathit{mod}N\right)$, Furthermore, $ed=1\mathit{mod}\phi \left(N\right)$ such that $C^d\left(\mathit{mod}N\right)=(K_{iB}\cdot m{)}^{1+k\cdot \phi \left(N\right)}(\mathit{mod}N)=(K_{iB}\cdot m{)}^1(K_{iB}\cdot m{)}^{k\cdot \phi \left(N\right)}(\mathit{mod}N)=(K_{iB}\cdot m{)}^1\left(\mathit{mod}N\right)=K_{iB}\cdot m=M,$ Since $K_{iA}=T_d\left(T_r\left(x\right)\right)\left(\mathit{mod}N\right)=T_r\left(T_d\left(x\right)\right)\left(\mathit{mod}N\right)=K_{iB}$, using Equation (14), therefore, $m=M/K_{iA}={(K}_{iB}\cdot m)/K_{iA}=m$, which is the original plaintext.

5. Implementation Results and Analysis

This paper conducts a security analysis on the improved public key encryption algorithm. The theoretical analysis shows that the improved algorithm is a public key cryptographic algorithm based on polynomials and RSA, which takes into account the security advantages of both and can effectively resist common attacks.

We can list the following advantages:

• Attackers cannot use the periodicity of Chebyshev polynomials to break it, because the cosine representation of Chebyshev polynomials defined on the interval $(-\infty ,+\infty )$ is not valid.
• The three typical scenarios of RSA cipher attacks cannot be the same as the proposed scheme, because the following inequalities hold:

  $$R_n\left(m_1\right)R_n\left(m_2\right)\ne R_n\left(m_1{m}_2\right)$$

  (15)

  $$R_{n_1+n_2}\left(m\right)\left(\mathit{mod}n\right)\ne R_{n_1}\left(m\right)T_{n_2}\left(m\right)\left(\mathit{mod}n\right)\ne R_{n_1}\left(R_{n_2}\right(m\left)\right)\left(\mathit{mod}n\right)$$

  (16)

  where Equation (15) is an analogy to the multiplication property of RSA.
• It can resist common modular attacks.
• After encryption transformation, the linear independence between plaintexts cannot be maintained, which is immune to low exponent attacks.

The proposed CRPKC-Ki algorithm is implemented using SageMath’s Jupyter Notebook. SageMath (or simply Sage) is a free and open-source mathematical software system that integrates numerous functionalities of symmetric and asymmetric key encryption, providing a unified interface and API. SageMath is developed based on the Python programming language and supports various functionalities such as mathematical computation, data analysis, graph plotting, and programming, and it can run on various operating systems. In this paper, the implementation and analysis were conducted using an 11th Gen Intel^® Core™ i5-11320H @ 3.20 GHz processor, with 16.0 GB of RAM (15.8 GB available), and the operating system is Windows 10, 64-bit. The following two sections focus on the performance and security evaluation of CRPKC-Ki compared to RSA and its variants.

In reference [17], Raza Imam et al. performed a performance analysis of the XRSA algorithm, including key generation time, encryption time, and decryption time, and compared it with Rivest et al.’s standard RSA, as well as two other enhanced versions of RSA, namely ESRKGS [19] and MRSA [42]. The analysis results showed that the XRSA algorithm outperforms other similar algorithms in terms of performance, and the algorithm achieves higher algorithm complexity by introducing parameters in the key generation and encryption/decryption stages, which enhances the algorithm’s security. This is similar to the motivation for improving the algorithm in this paper; hence, we introduce this algorithm as a comparative algorithm for performance analysis.

5.1. Performance Analysis

5.1.1. Key Generation

The Miller–Rabin primality testing algorithm is used for generating primes and tested and analyzed on different bit sizes of initial primes, ranging from 64 to 128, 256, 512, 1024, and 2048.

Table 2. Analysis and comparison of CRPKC-Ki model with RSA, XRSA, and CRPKC models.

Model	Length of Primes (in bits)	Key Generation Time (in ms)	Encryption Time (in ms)	Decryption Time (in ms)	Total Execution Time (in ms)
RSA	64	20.27	0.26	0.22	20.75
	128	25.47	0.37	0.33	26.17
	256	40.50	0.97	0.85	42.32
	512	76.55	1.75	1.68	79.99
	1024	820.14	15.28	14.54	849.96
	2048	4575.03	52.26	37.39	4664.67
XRSA	64	32.00	0.57	0.54	33.11
	128	47.61	1.30	1.05	49.95
	256	93.54	2.02	2.01	97.56
	512	188.91	10.53	9.56	209.00
	1024	922.81	39.68	36.06	998.56
	2048	8706.22	185.98	221.41	9113.61
CRPKC	64	50.03	0.96	0.94	51.93
	128	76.33	1.46	1.42	79.21
	256	147.21	4.61	3.77	155.59
	512	228.62	11.81	12.14	252.57
	1024	1582.39	40.12	39.25	1661.76
	2048	14,203.75	198.01	232.38	14,634.14
CRPKC-Ki	64	35.02	0.65	0.64	36.32
	128	54.19	1.29	1.08	56.57
	256	105.99	3.12	3.09	112.19
	512	177.18	10.93	10.01	198.12
	1024	1250.09	39.87	39.24	1329.19
	2048	10,036.74	1896.98	235.31	12,169.03

shows the comparative analysis of CRPKC-Ki with RSA, XRSA, and CRPKC. Figure 3 shows the comparison of key generation time under different key sizes, and it is evident that CRPKC has the longest key generation time, while standard RSA has the shortest and the best key generation time. For ease of comparison, the vertical axis uses a logarithmic scale with a base of 10 when plotting. The proposed CRPKC-Ki algorithm is essentially similar to the XRSA algorithm and falls in the middle. Due to the addition of the selective coefficient Ki in the proposed algorithm, which adds an initial parameter compared to RSA, the increase in time is acceptable considering the enhanced security.

5.1.2. Encryption and Decryption

Considering the encryption and decryption time shown in Figure 4 and Figure 5, it can be observed that the standard RSA has the lowest execution time in both encryption and decryption, making it the best in terms of encryption and decryption time. Due to the additional steps involved in the encryption and decryption stages of the CRPKC-Ki algorithm, the overall complexity of the proposed algorithm is increased. The introduction of a selection coefficient in the final encryption and decryption steps prevents attackers from determining the private key or plaintext using the product of the public key and the prime numbers. Furthermore, until the typical size of 1024 bits, CRPKC-Ki achieves similar performance in terms of encryption and decryption time compared to XRSA. Compared to CRPKC, CRPKC-Ki has better efficiency in terms of encryption, decryption, and key generation time per bit. For higher sizes of 2048 bits, CRPKC-Ki is slightly behind XRSA in encryption and decryption time, but the recommended prime size is usually 1024 bits, and the proposed CRPKC-Ki is more efficient and performs better among all the discussed algorithms. From the overall performance evaluation, the CRPKC-Ki algorithm is equally efficient and performs at the same level as the XRSA algorithm discussed, making it the best algorithm after the standard RSA. CRPKC is the least efficient among the discussed variations. Compared to the standard RSA, the added key generation time in CRPKC-Ki is reasonable because the introduction of Ki increases the complexity, making it more time-consuming to crack the CRPKC-Ki system and, thus, improving security.

5.2. Security Analysis

5.2.1. Security Resistance to Man-in-the-Middle Attack Which Is Described Above

The man-in-the-middle attack refers to the ability of an attacker to intercept, replay, substitute, or modify the information exchanged between the communication parties. Malicious attackers can change ciphertext by hiding alternate multiplication coefficients $k$, and then calculate $m=m^{\prime }/k$ to obtain plaintext. However, during the encryption process, we cleverly apply alternative multiplication coefficients $K_i$, which are not only determined by the values of $T_r\left(A\right)\left(\mathit{mod}N\right)=T_r\left(T_d\right(x\left)\right)\left(\mathit{mod}N\right)$ and $T_d\left(B\right)\left(\mathit{mod}N\right)=T_d\left(T_r\right(x\left)\right)\left(\mathit{mod}N\right)$, but also only share specific value selection strategies with participants. For example, in the example given in this paper, $K_i$ is selected by an arithmetic sequence, which is just a simple example. In actual applications, we can adopt more complex rules, so we do not need to worry about the security of $K_i$ selection.

5.2.2. Security against Tampering Attacks and Identity Authentication

Since Alice will sign the ciphertext during the actual encryption process, $Y_A=E_k\left(Si{g}_A\right(C,B\left)\right)$, Bob can use this to check if the result has been tampered with or forged. Bob can easily verify Alice’s identity through her public key during the decryption process.

5.2.3. Practicability Analysis

Modulus $N$ is a large prime number, and $K_i\in Z_N$, providing a large selection space that can be systematically changed. Here, $i=\mathrm{1,2}\cdots n$ is an optional parameter, and we can choose $K_i$ as needed. Additionally, if the number of users increases, we can increase the quantity accordingly. In practical cryptographic applications, periodically changing the values of $K_i$ to enhance cryptographic security has the advantages of convenience, efficiency, and operability.

5.2.4. Comparison between Improved Algorithm and Original Algorithm

Both algorithms achieve encryption functionality, but the $\mathrm{CRPKC}-K_i$ algorithm has higher security and reliability. Its innovation lies in the clever use of alternative multiplication coefficients $K_i$ to prevent common ciphertext attacks. The use of digital signatures helps verify identity and avoid tampering attacks. The performance comparison analysis is shown in

Table 3. Performance comparisons.

Attacks/Functions	The Algorithm, CRPKC	$\mathbf{The} \mathbf{Improve} \mathbf{Algorithm}, \mathbf{CRPKC}-{\mathit{K}}_{\mathit{i}}$
Man-in-the-middle attack	Not safe	Safe
Tampering attack	Not safe	Safe
Authentication	Not given	Safe
Practicability	Ordinary	Better

.

From the process of the public key encryption algorithm, we can see that although its computational complexity is slightly higher than the former, the order of magnitude is basically the same. The application of digital signatures will adopt more mature solutions. Therefore, in practical applications, the improved algorithm is superior to the original algorithm.

6. Conclusions and Future Scope

Compared to the private key cryptographic system, the public key cryptographic system has unique advantages in key exchange, communication between unknown entities, secure services, and authentication services. This paper introduces the CRPKC public key encryption algorithm and proposes an improved public key cryptographic algorithm based on Chebyshev polynomials and RSA, named $\mathrm{CRPKC}-K_i$. The improved algorithm introduces an alternative multiplication coefficient $K_i$ to forge ciphertext and uses digital signatures to ensure Alice’s identity. These measures enable the system to resist chosen ciphertext attacks and tampering attacks while providing identity authentication functionality. In conclusion, after performance and security analysis, the proposed $\mathrm{CRPKC}-K_i$ algorithm based on an RSA variant shows better results with improved security.

The proposed algorithm is equivalent to encrypting the plaintext twice. Although it requires some extra computation time compared to other methods, we believe its advantage lies in the fact that even if an attacker guesses the private key in the same amount of time, they still need to decipher the true plaintext from the forged plaintext. This enhances the algorithm’s security. However, in the case of large prime bit sizes, the efficiency of the algorithm decreases significantly, especially beyond 2048 bits, and the multiplication coefficient cannot be set too large, otherwise it will have a negative impact on encryption/decryption time. This can be seen as a drawback. Therefore, as future work, we plan to extend this algorithm to parallel machines so that multiple related operations can be executed simultaneously on multi-core processors. We will also discuss the optimal values for the multiplication coefficient in detail to reduce computational costs. Additionally, combining the algorithm protocol with symmetric cryptography and ensuring its wide acceptability in IoT devices will be explored.