Paper 2025/445

A proof of P≠NP (New symmetric encryption algorithm against any linear attacks and differential attacks)

Abstract

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 10 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about ten unknown variables $(w_{1}, w_{2}, ..., w_{9}, w_{10})$ together with some implicit variables which are generated by the encryption process. In this paper, we will prove that there is no universal algorithm without brute-force searching at least one variable during the process of verifying four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ whose computational complexity is not greater than solving the ten variables. After performing elimination the implicit variables, the problem of verifying the four variables will be equivalently transformed into a series of general quintic equations about one variable $w_{9} \oplus w_{10}$ with coefficient given by other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$, according to the conclusion that ``there is no algebraic solution to quintic equations", we can't establish a system of algebraic equations only containing the other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$. Without solving the other four variables, the problem of verifying the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ is equivalent to solve the slope and intercept of a line given the x-coordinates or y-coordinates of several points on it (points with x-coordinates known cannot have their y-coordinates known, and vice versa), this implies that there is no universal algorithm without brute-force searching at least one variable to verify the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$. Since the computational complexity of brute-force searching any single variable is exponential, thus the complexity of cracking the key is exponential. Thus decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there is no algebraic solution to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of two parts, one part is completely random, while the other small part is calculated using plaintexts, keys, and random numbers, and their distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.