如何将非线性 XOR 方程组转换为 CNF
How to convert a system of non-linear XOR equations to CNF
我正在尝试分析 trivium 中的相移故障分析，遇到了一个需要求解的非线性方程组。我阅读了有关 sat 求解器和高斯消元法的信息，但不幸的是，我在互联网上找到的 none 篇文章展示了如何处理具有大量变量的非线性方程组（此处 trivium 提供 288 个变量）。所以我现在非常困惑如何解决这些变量。
您可以将您的问题表示为布尔门网络 - 网表 - 并使用 bc2cnf 将其转换为 CNF。您可以指示 bc2cnf 以 XCNF 格式输出 XOR 子句，这是一种扩展的 CNF 格式，其中 "x" 个子句表示 XOR 个子句。
SAT 求解器，例如 cryptominisat are capable of reading XCNF and/or detecting the contained XOR gates and performing Gaussian elimination. Cryptominisat reportedly has been used several times to attack the Trivium 流密码。
我建议您看一下 SMT 求解器，例如Z3。使用 SMT，您可以以自然的方式表达布尔方程和不等式，而不是将所有内容都分解成 SAT 实例。有大量在线文档可帮助您入门。
我正在尝试分析 trivium 中的相移故障分析，遇到了一个需要求解的非线性方程组。我阅读了有关 sat 求解器和高斯消元法的信息，但不幸的是，我在互联网上找到的 none 篇文章展示了如何处理具有大量变量的非线性方程组（此处 trivium 提供 288 个变量）。所以我现在非常困惑如何解决这些变量。
您可以将您的问题表示为布尔门网络 - 网表 - 并使用 bc2cnf 将其转换为 CNF。您可以指示 bc2cnf 以 XCNF 格式输出 XOR 子句，这是一种扩展的 CNF 格式，其中 "x" 个子句表示 XOR 个子句。
SAT 求解器，例如 cryptominisat are capable of reading XCNF and/or detecting the contained XOR gates and performing Gaussian elimination. Cryptominisat reportedly has been used several times to attack the Trivium 流密码。
我建议您看一下 SMT 求解器，例如Z3。使用 SMT，您可以以自然的方式表达布尔方程和不等式，而不是将所有内容都分解成 SAT 实例。有大量在线文档可帮助您入门。