arXiv:2203.05022 · v13

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

首次提交 2022-02-05 21:11

版本更新 2026-10-26 20:36

雷达观测 2026-10-29 00:36

摘要

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 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 of the ten variables 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 with coefficient given by other four variables, 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......