Решите несколько уравнений, используя Z3

У меня есть следующая функция, которая принимает входную строку и число для создания хэша, как показано ниже:

#! /usr/bin/python

def calc_hash(key, num):
    result = 0

    for i in range(len(key)):
        result = (ord(key[i]) + result * 10 - 0x30) % num

    return result

if __name__ == "__main__":
    print hex(calc_hash("you_must_check_this_out", 0x1A5D215))

Итак, если входная строка: «you_must_check_this_out», а число: 0x1A5D215, то вывод будет: 0x7cda66.

Цель состоит в том, чтобы найти входную строку, удовлетворяющую следующим условиям:

calc_hash(input, 0x1A5D215) == 0xd5
calc_hash(input, 0x28DB) == 0xe5
calc_hash(input, 0x5d1) == 0x19
calc_hash(input, 0xff7ff) == 0x53
calc_hash(input, 0x3eff) == 0x87

Я не знаю длину входной строки, однако ограничение на длину заключается в том, что она должна быть меньше или равна 30.

len(input) <= 30

Итак, я написал следующий код, чтобы найти решение с помощью Z3, однако он не работает.

#! /usr/bin/python

import sys
from z3 import *

def calc_hash(input, num):
    result = 0

    for i in range(len(input)):
        result = (ZeroExt(56, input[i]) + result * 10 - 0x30) % num

    return result

if __name__ == "__main__":
    s = Solver()

    input = [BitVec("input%s" % i, 8) for i in range(10)]

    for i in range(10):
      s.add(input[i] >= 0x20)
      s.add(input[i] <= 0x7E)

    s.add(calc_hash(input,0x1A5D215) == 0xd5)
    s.add(calc_hash(input,0x28DB) == 0xe5)
    s.add(calc_hash(input,0x5d1) == 0x19)
    s.add(calc_hash(input,0xff7ff) == 0x53)
    s.add(calc_hash(input,0x3eff) == 0x87)

    print s.check()

    print s.model()

Длина ввода может быть изменена в коде, чтобы попробовать разные длины.

Есть ли проблема с приведенным выше кодом?

Можете уточнить "что не работает?" Что вы ожидали, и что произошло на самом деле?

alias 10.03.2019 05:01

@LeventErkok Судя по 5-минутному тестированию, проблема либо в слишком сложно, либо в кодировке слишком неэффективно. На самом деле, я не понимаю, что здесь происходит с calc_hash(). Преобразуется ли он автоматически в какой-то smt2-подобный набор ограничений или многократно оценивается как "внешняя функция" при поиске?

Patrick Trentin 11.03.2019 13:31
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
2
203
0

Другие вопросы по теме