Z3 为 XOR 密码花费了意想不到的时间

Question

我正在尝试通过破解一个简单的（3 个字符）异或密码来学习 Z3：https://projecteuler.net/problem=59

到目前为止我已经指定了一些简单的要求，比如明文需要等同于密文^密码，明文必须由7位ascii组成，密码只能使用小写字符。

ciphertext_bytes = parse_input("p059_cipher.txt")
set_param("parallel.enable", True)
set_param("parallel.threads.max", os.cpu_count())
s = Solver()
ctx = s.ctx

password = IntVector('x', 3, ctx)
ciphertext = IntVector('c', len(ciphertext_bytes), ctx)
plaintext = IntVector('p', len(ciphertext_bytes), ctx)

for x in password:
    s.add(x >= 97)
    s.add(x <= 122)

for i, value in enumerate(ciphertext_bytes):
    ciphertext[i] = Int(value, ctx)
    password_index = i % len(password)

    password_char = BitVecRef(Z3_mk_int2bv(ctx.ref(), 8, password[password_index].as_ast()), ctx)
    ciphertext_char = BitVecRef(Z3_mk_int2bv(ctx.ref(), 8, ciphertext[i].as_ast()), ctx)
    plaintext_char = BitVecRef(Z3_mk_int2bv(ctx.ref(), 8, plaintext[i].as_ast()), ctx)

    s.add(password_char ^ ciphertext_char == plaintext_char)

    s.add(plaintext[i] >= 0)
    s.add(plaintext[i] <= 127)
    s.add(ciphertext[i] >= 0)
    s.add(ciphertext[i] <= 255)

print(s.check())
print(s.model())

然而，s.check() 调用不会在任何合理的时间内终止。

由于指定的问题（目前仍然）可以通过 26*3 次尝试（分别猜测每个密码字符并随后检查明文）进行暴力破解，我一定是在某处犯了错误。

为什么这段代码很慢？

为什么Z3这里不使用多线程？

Answer 1

唉，这对于 SMT 求解器来说并不是一个合适的问题。这里的问题是不是你不能用SMT解决这个难题；但它不会给你带来任何新东西。请注意，在基于 XOR 的加密中，等式：

  cipher = plain ^ key

对cipher和key的每个值有一个解决方案：你只需得到一个字节序列的纯文本，以及SMT求解器无法确保它是有效的英语。（是的，您可以将其限制为每个字符 7 位等，但这实际上并没有以任何有意义的方式减少搜索 space。）这里的技巧是确保纯文本“有意义”英文，因为是密码。但是 SMT 求解器中没有固有知识可以告诉您字节序列是否对应于有意义的英语文本，或者任何已知自然语言的文本。

那么，解决这个问题最好的方法就是使用经典的解密技术；像频率分析、基于字典的枚举等。其中 none 真的将从 SMT 求解器中获得任何东西。或者，鉴于这是一个欧拉项目问题，最好的办法可能是浏览计算机中的字典文件并详尽地搜索合适的解决方案；因为只有那么多三个字母的单词可以用作有效密码。

关于您观察到的“速度”问题：请注意，int2bv 是一项昂贵的操作。你应该避免它，而只是使用位向量。但同样，这在这里对您没有帮助，因为您将“快速”得到一个无意义的解决方案。

Z3 为 XOR 密码花费了意想不到的时间

Z3 takes an unexpected amount of time for an XOR cipher

python

z3

smt