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 6 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 six unknown variables. We prove that the computational complexity of verifying two variables should not be lower than the computational complexity of verifying any intermediate unknown variable whose number of possible values is exponentially to the length of the key, thus proving that the computational complexity of verifying two variables can't be polynomial. Due to the computational complexity satisfying the condition of ``complexity of cracking the key = complexity of solving six variables $\geq$ complexity of solving two variables $\geq$ complexity of verifying two variables", thus the computational complexity of cracking the key can't be polynomial, So the decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", thus 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 are no algebraic solutions 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 a completely randomly generated random number, while the other small part is calculated using plaintext, algorithms, and random numbers, and its distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.