CN-121150971-B - Password security assessment method and system based on secondary Boolean equation variable segmentation

CN121150971BCN 121150971 BCN121150971 BCN 121150971BCN-121150971-B

Abstract

The invention discloses a password security assessment method and a system based on secondary Boolean equation variable segmentation, belonging to the technical field of password security assessment; the method comprises the steps of constructing a mixed integer linear programming model of a secondary Boolean equation set, solving the mixed integer linear programming model based on a set objective function to obtain an optimal segmentation result of an x variable in the secondary Boolean equation set, executing secondary Boolean equation set solving based on the segmentation result of the x variable to obtain a plurality of sets of candidate solutions, decrypting the ciphertext according to a key formed by the candidate solutions to obtain a security evaluation result of the cryptographic algorithm to be evaluated. The invention can provide the security evaluation efficiency of the cryptographic algorithm.

Inventors

SHI DANPING
GUO XU
HU LEI
GUO YI
CHEN ZHIRU

Assignees

中国科学院信息工程研究所

Dates

Publication Date: 20260508
Application Date: 20250828

Claims (8)

1. A cryptographic security assessment method based on quadratic boolean equation variable segmentation, the method comprising: constructing a secondary Boolean equation set related to a cryptographic algorithm to be evaluated, wherein the number of equations in the secondary Boolean equation set Determining based on bit length of ciphertext generated by the cryptographic algorithm to be evaluated, the method comprising the steps of Number of variables Determining based on a key bit length of the cryptographic algorithm to be evaluated; constructing a mixed integer linear programming model of the quadratic Boolean equation system, wherein the mixed integer linear programming model is used for using Variable(s) Variable substitution in a system of quadratic boolean equations A variable; Solving the mixed integer linear programming model based on a set objective function to obtain a secondary Boolean equation set An optimal segmentation result of the variable; Based on The segmentation result of the variables is solved by a secondary Boolean equation system to obtain candidate solutions of a plurality of groups; Decrypting the ciphertext according to the candidate solution composition key to obtain a security evaluation result of the to-be-evaluated cryptographic algorithm; The method for constructing the mixed integer linear programming model of the secondary Boolean equation set comprises the following steps: defining variables in a mixed integer linear programming model according to a secondary Boolean equation set; Adding constraints between variables; Generating a mixed integer linear programming model by combining the variables in the mixed integer linear programming model and the constraints among the variables; wherein defining variables in the mixed integer linear programming model according to the set of quadratic boolean equations comprises: defining variables of integer type For representing Number of variables; a binary variable d [ j ] is defined to represent the second order Boolean equation Personal (S) The variables are Variable or A variable; Defining binary variables For indicating the first Whether or not the second Boolean equation is related to Linear equation of the variables; Defining binary variables For indicating the first Quadratic term in the individual equations Whether or not to be about A quadratic term for the variable; Defining binary variables For indicating the first Whether there are quadratic terms in the equations for the y variables; defining variables of integer type For indicating the first In the equation The variable times the number of quadratic terms of the y variable; Defining an integer variable g_e for representing a gaussian elimination solution Complexity of the linear system of equations of the variables.
2. The method of claim 1, wherein constructing a set of quadratic boolean equations from the password to be evaluated comprises: Obtaining a plaintext and encrypting the plaintext by using the cryptographic algorithm to be evaluated to obtain a ciphertext; Constructing using the plaintext Each comprises A nonlinear polynomial of the variable; Converting each nonlinear polynomial based on the structure of the cryptographic algorithm to be evaluated to obtain a final nonlinear polynomial set; and enabling the final nonlinear polynomial set to be equal to the ciphertext so as to obtain a quadratic Boolean equation set.
3. The method of claim 1, wherein adding constraints between variables comprises: Adding variables Sum variable Constraint between The constraint is that Includes the required variable If and only if to With variations Otherwise variable ; Adding variables Sum variable Constraint between The constraint is that Comprises the following variables Is smaller than the variable Number of equations of =1; adding variable d [ j ] and variable Constraint between The constraint is that Comprising the following steps: For a pair of If dj=dk=0, then the variable is ; For a pair of If dj is not equal to dk, the variables are ; For a pair of If dj=dk=1, then the variable is ; Adding variable d [ j ] and variable Constraint between The constraint is that Comprising the following steps: For a pair of If d [ j ] =d [ k ] =0, then the variable q_y [ i ] =0; For a pair of If dj is not equal to dk, the variable q_y [ i ] =0; If it is So that d [ j ] =d [ k ] =1, then the variable q_y [ i ] =1; adding constraints between the variable d [ j ] and the variable z_yj ] The constraint is that Includes the following steps The value of the variable z_yj of the individual equations is equal to the number of quadratic terms of the y variable times the z variable; Adding variable g_e, variable Sum variable Constraint between The constraint is that Comprises the following variables , Representing the number of secondary boolean equations; adding variable d [ j ] and variable Constraint between The constraint is that Comprises the following variables 。
4. The method according to claim 1, wherein the generating of the objective function comprises: In variable quantity Statistical variables in the second-order boolean equation of (2) Equation number of (2) ; In variable quantity Statistical variables in the second-order boolean equation of (2) Equation number of (2) ; In variable quantity Counting the number of quadratic terms of the z variable times the y variable in the quadratic boolean equation of (2) ; Minimum MIN of Crossbred algorithm complexity for solving secondary Boolean equation set As an objective function.
5. The method according to claim 1, characterized in that it is based on And executing secondary Boolean equation system solution on the segmentation result of the variable to obtain a plurality of candidate solutions, wherein the method comprises the following steps: traversing the value space of the y variable to enable the variable to be The quadratic boolean equation of=1 constitutes a linear system of equations for the z-variable; using Gaussian elimination pairs for Solving a linear equation set of variables to obtain a linear equation set The value of the variable; involving the system of linear equations Values of variables and traversal of y variables The values of the variables are returned to the system of secondary boolean equations for verification, and after verification is successful, a set of candidate solutions is obtained.
6. A cryptographic security assessment system based on quadratic boolean equation variable segmentation, the system comprising: an equation set construction module for constructing a secondary Boolean equation set related to the cryptographic algorithm to be evaluated, wherein the number of equations in the secondary Boolean equation set Determining based on bit length of ciphertext generated by the cryptographic algorithm to be evaluated, the method comprising the steps of Number of variables Determining based on a key bit length of the cryptographic algorithm to be evaluated; The model construction module is used for constructing a mixed integer linear programming model of the secondary Boolean equation system, wherein the mixed integer linear programming model is used for using Variable(s) Variable substitution in a system of quadratic boolean equations A variable; the variable segmentation module is used for solving the mixed integer linear programming model based on a set objective function to obtain a secondary Boolean equation set An optimal segmentation result of the variable; a system of equations solving module for The segmentation result of the variables is solved by a secondary Boolean equation system to obtain candidate solutions of a plurality of groups; the password evaluation module is used for decrypting the ciphertext according to the candidate solution composition key to obtain a security evaluation result of the to-be-evaluated password algorithm; The method for constructing the mixed integer linear programming model of the secondary Boolean equation set comprises the following steps: defining variables in a mixed integer linear programming model according to a secondary Boolean equation set; Adding constraints between variables; Generating a mixed integer linear programming model by combining the variables in the mixed integer linear programming model and the constraints among the variables; wherein defining variables in the mixed integer linear programming model according to the set of quadratic boolean equations comprises: defining variables of integer type For representing Number of variables; a binary variable d [ j ] is defined to represent the second order Boolean equation Personal (S) The variables are Variable or A variable; Defining binary variables For indicating the first Whether or not the second Boolean equation is related to Linear equation of the variables; Defining binary variables For indicating the first Quadratic term in the individual equations Whether or not to be about A quadratic term for the variable; Defining binary variables For indicating the first Whether there are quadratic terms in the equations for the y variables; defining variables of integer type For indicating the first In the equation The variable times the number of quadratic terms of the y variable; Defining an integer variable g_e for representing a gaussian elimination solution Complexity of the linear system of equations of the variables.
7. An electronic device comprising a processor and a memory storing computer program instructions that when executed implement the method of cryptographic security assessment based on quadratic boolean equation variable segmentation according to any one of claims 1-5.
8. A computer readable storage medium, having stored thereon computer program instructions, which when executed by a processor, implement the method for cryptographic security assessment based on quadratic boolean equation variable segmentation according to any one of claims 1-5.

Description

Password security assessment method and system based on secondary Boolean equation variable segmentation Technical Field The invention relates to the technical field of password security assessment, in particular to a password security assessment method and system based on secondary Boolean equation variable segmentation. Background The password is a core technology and basic support for guaranteeing the security of networks and information, so that the security assessment of the password algorithm is also particularly important. Constructing a system of equations for key bits according to the structure of the cryptographic algorithm, and evaluating the cryptographic algorithm by solving the system of equations is a common cryptographic security evaluation method. Specifically, according to the characteristics of the cryptographic algorithm structure, a secondary boolean equation set about key bits can be constructed, and the corresponding solving algorithm is used for solving. The following is one existing algorithm for solving a system of quadratic boolean equations (Crossbred algorithm). For a variable comprising n variablesWhen the solution of the second-order boolean equation set E (x) =f 1(x)＝f2(x)＝…＝fm (x) =0 is performed using the Crossbred algorithm, n boolean variables are first divided into two partsThen each equation in the system of equations can be written asL i (y) is a linear expression of y, q (y) is a quadratic expression of y. Thus, equation set E (x) may be written as follows, ：A·(z1z2,z1z3,…,zu-1zu,z1,z2,…,zu)T＝B,ABefore (1)The elements of the columns are 0 or 1, the elements of the latter u columns are linear expressions of y, B is a vector containing m elements, and each element is a quadratic expression of y. Simplifying the augmentation matrix A|B into a descending row ladder matrix according to the back of the matrixLine, a linear system of equations a ' · (z 1,z2,…,zu)T =b ', a ' isWherein each element is a linear expression of y, and B' is a matrix containingA vector of elements, each element being a quadratic expression of y. TraversingThe values of the expressions of y in A 'and B' are calculated, and a linear system of equations for z is solved using Gaussian elimination in each pass to obtain a candidate solution, and the candidate solution is carried back to the original system of equations for verification. It can be seen that the algorithm can involve variable segmentation in the process of solving, the original algorithm for solving the secondary Boolean equation set is randomly segmented when the variable segmentation is carried out, and the relation of the variables in the equation is not considered, so that the solving complexity of the algorithm is not optimal. This can result in inefficient cryptographic security assessment. Disclosure of Invention The invention provides a password security assessment method and a password security assessment system based on secondary Boolean equation variable segmentation, which are used for carrying out variable segmentation through the relation of variables in equations, so that the complexity of Crossbred algorithm for solving a secondary Boolean equation set is effectively reduced, and the assessment efficiency of password security is improved. In order to achieve the above object, the technical scheme of the present invention includes the following. A cryptographic security assessment method based on quadratic boolean equation variable segmentation, the method comprising: Constructing a secondary Boolean equation set related to the to-be-evaluated cryptographic algorithm, wherein the equation number m in the secondary Boolean equation set is determined based on the bit length of a ciphertext generated by the to-be-evaluated cryptographic algorithm, and the variable number n in the secondary Boolean equation set is determined based on the key bit length of the to-be-evaluated cryptographic algorithm; the mixed integer linear programming model of the secondary Boolean equation set is constructed, wherein the mixed integer linear programming model is used for replacing an x variable in the secondary Boolean equation set by using a y variable and a z variable; Solving the mixed integer linear programming model based on a set objective function to obtain an optimal segmentation result of an x variable in a secondary Boolean equation set; performing secondary Boolean equation system solution based on the segmentation result of the x variable to obtain candidate solutions of a plurality of groups; and decrypting the ciphertext according to the candidate solution composition key to obtain a security evaluation result of the to-be-evaluated cryptographic algorithm. Further, constructing a secondary boolean equation set according to the password to be evaluated, including: Obtaining a plaintext and encrypting the plaintext by using the cryptographic algorithm to be evaluated to obtain a ciphertext; Constructing m nonlinear polynomials co