# An Improved Multi-Chaotic Public Key Algorithm Based on Chebyshev Polynomials
## 5 Implementation Results and Analysis
### Security Analysis  
Since we use Chebyshev polynomials based on finite fields, with the domain and range extended to \(Z_{N}\), it effectively avoids the breaking method mentioned in Section 2.2 that utilizes inverse trigonometric functions. In this paper, the selection coefficient \(k_{i}\) is chosen based on the value of \(T_{cd}(x)(modN)\), which can only be obtained through calculations by the communicating parties. It is impossible for any third party to know \(T_{cd}(x)(modN)\), thus ensuring the security of the selection of \(k_{i}\). In the calculation process, the computational complexity of \(k_{i}\) is equivalent to that of the ElGamal public key cryptosystem and does not add an additional computational load. However, it is computationally infeasible to determine \(d\) from \((x,\ T_{d}(x)(modN))\). However, the resonant characteristics of Chebyshev polynomial points in finite fields still exist. That is, given the public key \((x,\ T_{d}(x))\), by calculating \(x_{i}=T_{i}(x)\) and \(y_{i}=T_{d}(x_{i})=T_{d}(T_{i}(x))\), enough points \((x_{i},\ y_{i})\) can be obtained on the Chebyshev polynomial curve, allowing for curve fitting to derive the key \(d\). The autocorrelation function of \(T_{d}(x)\) exhibits binary characteristics, and the normalized autocorrelation function \(R_{d}(\eta)\) for \(T_{d}(x)\) is given by:  
\[R_{d}(\eta)=\frac{\sum_{x=0}^{N-1}{(T_{d}(x)modN)(T_{d}(x+\eta)modN)}}{\sum_{x =0}^{N-1}{(T_{s}(x)modN)^{2}}}. \tag{26}\]  
In the formula, when \(N\) is sufficiently large, it can be shown that:  
Figure 11: Encryption Time Comparison. Figure 12: Decryption Time Comparison. \[R_{d}(\eta)= \begin{cases}1,\ \eta=0,\\ \varepsilon,\ \eta\
eq 0.\end{cases}  \tag{27}\]  
where \(\varepsilon\) is a constant, such that \(0<\varepsilon<1\). In other words, when \(N\) is sufficiently large, \(R_{d}(\eta)\) exhibits binary characteristics. In practical public key encryption systems, the field values are extremely large. Therefore, it can be assumed that the points on the \(T_{d}(x)\) curve are difficult to predict and count during the effective lifespan of the key. Even if an attacker gains access to many points on the curve, they cannot fit the curve and deduce the private key \(d\) within the limited lifespan of the key. Furthermore, considering the range of values for \(k_{i}\), as long as the maximum value of \(k_{i}\), \(k_{n}<N\), and given that \(N\) can be theoretically arbitrarily large, the values of \(k_{n}\) and \(n\) can also be arbitrarily large. This means that in practical applications, the selection of the coefficient \(k_{i}\) is highly random, further ensuring the security of the algorithm. In Section 2.5, we have observed four shortcomings of previous algorithms. By replacing the corresponding linear transformations with finite field Chebyshev polynomials, we can overcome shortcomings 1 and 2. For shortcoming 3, we use chaotic hash functions and logistic mappings to generate pseudorandom sequences. By analyzing the properties of multi-chaos systems, we hypothesized that attackers can calculate \(x_{i_{1},\ i_{1},\ \cdots,\ j_{\widetilde{m}}}=f_{1}^{i+i_{0}}f_{2}^{i+i_{1}} \cdots f_{\widetilde{m}}^{i+i_{m}-1}(x_{0})\), where \(i\in\left\{1,\ 2,\ \cdots,\left\lfloor n_{A}/\widetilde{m}\right\rfloor\right\}\) and \(i_{k}\in\left\{0,\ 1\right\}(k=1,\ 2,\ \cdots,\left\lceil\sqrt{N}\right\rceil)\). However, in our proposed new algorithm, \(f_{1}(x),f_{2}(x),\cdots,f_{n}(x)\) have been replaced with \(f_{k_{a}}(x),f_{k_{g}}(x),\cdots,f_{k_{n}}(x)\), where \(k_{a}\), \(k_{b}\), \(\cdots,k_{n}\in k_{i}\), with sufficiently large ranges and good randomness. This makes it impossible for attackers to effectively attack the algorithm based on the assumptions. Regarding shortcoming 4, the performance test of the algorithm shows that the improved algorithm has stronger resistance to brute force attacks compared to previous algorithms. Table 6 represents the comparison of brute force attack times from 4-bit prime numbers to 7-bit prime numbers.