2022/02/05 by Ming Gao, Gao Ming, Ming, Gao
Computer Science · Mathematics · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Data Security #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2203.05022
openalex publication_date 2022/02/05 · openalex created_date 2025/10/10 · arxiv created 2026/07/29 · arxiv updated 2026/07/30 · openalex updated_date 2026/07/31
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 ≠ 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. The computational complexity of verifying two variables should not be lower than the computational complexity of enumerating 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 is exponential. Due to the computational complexity satisfying the condition of ``complexity of cracking the key = complexity of solving the six variables ≥ complexity of solving the two variables ≥ complexity of verifying the two variables", thus the computational complexity of cracking the key is at least exponential, So the decryption is a one-way function, and according to ``the existence of one-way function means P ≠ NP", thus solving the unsolved problem of P vs NP.