# An Improved Multi-Chaotic Public Key Algorithm Based on Chebyshev Polynomials
## 2 Preliminary
### Improved Algorithm (Cmpkc-ki)  
The improved public key encryption system adopts the coefficient selection \(k_{i}\) based on the equality \(T_{r}(T_{d}(x))modN=T_{d}(T_{r}(x))modN\), where the size of \(k_{i}\ (i=1,\ 2\cdot\cdot\cdot n)\) is determined, and \(T(x)\) is the Chebyshev polynomial. The specific value selection rule of \(k_{i}\) and the size of \(n\) are shared secrets among participants. A pseudo-random sequence \(\{0,\ 1\}\) is generated using chaotic hash functions and logistic mapping. The initial value \(x_{0}\) is iterated \(n_{A}\) and \(n_{B}\) times based on the sequence content to obtain \(x_{nA}\) and \(x_{nB}\), and then iterated \(n_{B}\) and \(n_{A}\) times again to obtain \(x_{nB+nA}\) and \(x_{nA+nB}\).  
The key exchange process of this improved multi-chaos public key system is illustrated in Figure 8.  
The algorithm is described as follows (assuming [PERSON] wants to communicate with [PERSON]):  
Let \(N\) be a large positive number, and the chaotic system is of m levels.  
Step 1. [PERSON] and [PERSON] choose coefficients \(k_{i}\) through public negotiation and calculation and determine the initial value \(x_{0}\) and \(\widetilde{m}\) selection functions \(f_{1}(x),f_{2}(x),\cdots,f_{\widetilde{m}}(x)\), where \(f_{1}(x),f_{2}(x),\cdots,f_{\widetilde{m}}(x)\) are Chebyshev polynomials.  
Step 2. [PERSON] randomly selects a key seed \(s_{A}\) and a large number \(n_{A}\in[0,\ N]\), inputs these parameters into a pseudo-random sequence generator, and outputs a \(\{0,1\}\) sequence \(r_{A}\) of length \(n_{A}\). Select \(k_{\alpha},k_{\beta}\) by the selectivity coefficient \(k_{i}\), select functions \(f_{k_{\alpha}}\) and \(f_{k_{\beta}}\) based on \(k_{\alpha}\) and \(k_{\beta}\). Iterating \(f_{k_{\alpha}}(x_{0}),f_{k_{\beta}}(x_{0})\) over \(n_{A1},\ \ n_{A2}\) times according to the content of \(\{0,1\}\) in \(r_{A}\) to obtain \(x_{nA}\), and pass \(x_{nA}\) as the public key to [PERSON].  
\[x_{i}=h(x_{i-1},\ k_{i})\] \[h_{\widetilde{m}}(x,\ k)= \begin{cases}f_{1}(x)(modN)&if\ k=1,\\ f_{2}(x)(modN)&if\ k=2,\\ \vdots\\ f_{m}(x)(modN)&if\ k=\widetilde{m}.\end{cases} \tag{21}\]  
Figure 8: Key exchange process of the improved multi-chaos system.  
Step 3. Similarly, [PERSON] randomly selects a key seed \(s_{B}\) and a large number \(n_{B}\in[0,\ N]\), inputs these parameters into a pseudo-random sequence generator, and outputs a \(\{0,1\}\) sequence \(r_{B}\) of length \(n_{B}\). Select \(k_{a},k_{B}\) by the selectivity coefficient \(k_{i}\), select functions \(f_{k_{a}}\) and \(f_{k_{B}}\) based on \(k_{a}\) and \(k_{B}\). Iterating \(f_{k_{a}}(x_{0}),f_{k_{B}}(x_{0})\) over \(n_{B1},\ n_{B2}\) times according to the content of \(\{0,1\}\) in \(r_{B}\) to obtain \(x_{nB}\), and pass \(x_{nB}\) as the public key to [PERSON].  
Step 4. [PERSON] iterates \(x_{nB}\) over \(n_{A}\) times according to \(r_{A}\) to obtain \(x_{nB+nA}\).  
Step 5. [PERSON] iterates \(x_{nA}\) over \(n_{B}\) times according to \(r_{B}\) to obtain \(x_{nA+nB}\).  
Since \(f_{1}(x),f_{2}(x),\cdots,f_{m}(x)\) are Chebyshev polynomials, it is known from preliminary knowledge that Chebyshev polynomials satisfy the semi-group property on \((-\infty,+\infty)\). Therefore, we have \(f_{k_{a}}\circ f_{k_{B}}=f_{k_{B}}\circ f_{k_{a}}(k_{a},\ k_{B}\in[1,\ \widetilde{m}])\), that is  
\[x_{nB+nA}=f_{k_{a}}^{n_{A1}}f_{k_{B}}^{n_{A2}}(x_{nB})=f_{k_{a}}^{n_{A1}}f_{k_ {B}}^{n_{A2}}f_{k_{a}}^{n_{B1}}f_{k_{B}}^{n_{B2}}(x_{0})=f_{k_{a}}^{n_{A1}+n_{ B1}}f_{k_{B}}^{n_{A2}+n_{B2}}(x_{0}), \tag{22}\]  
where \(n_{A1},\ n_{A2},\ n_{B1},\ n_{B2}\) are the numbers of 0s and 1s in \(r_{A}\) and \(r_{B}\), respectively. Similarly, it can be proven that  
\[x_{nA+nB}=f_{k_{a}}^{n_{A1}+n_{B1}}f_{k_{B}}^{n_{A2}+n_{B2}}(x_{0}), \tag{23}\]  
therefore, we have \(x_{nA+nB}=x_{nB+nA}\).  
Combined with the process in Figure 8, this improved algorithm can be used for both encryption and decryption, and can be combined with the AES algorithm for further applications.