Проверить наличие строки в зашифрованной базе данных

Question

Для системы, которую я разрабатываю, я хочу иметь возможность проверить, является ли конкретная строка «действительной» или нет, но я хочу, чтобы моя база данных «действительных» строк была конфиденциальной.

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

Клиенты должны иметь возможность вводить строки в мою программу, и она будет возвращать логическое значение в зависимости от наличия строки в моем зашифрованном файле.

Что еще более важно, я хочу, чтобы моя программа легко проверяла, находится ли строка в файле, но я хочу помешать другим программам легко использовать (и / или восстанавливать) базу данных.

Я сформулировал это немного абстрактно, потому что я пока не знаю, как будет выглядеть моя система, но я хочу знать, возможно ли что-то подобное.

Answer 1

То, что вы ищете, это криптографические хеш-функции! MD5 и SHA1 являются хорошо известными примерами, но если вы создаете новый код без строгих ограничений производительности, вам следует выбрать SHA256, и если вы хотите сделать его очень трудным для восстановления исходного словами, вы можете рассмотреть scrypt или bcrypt (хотя они не так популярны и маловероятно, что ваш язык включит их в стандартную библиотеку).

Тогда ваша база данных может быть такой же простой, как неупорядоченный набор хэшей, что-то вроде (в Python):

>>> words = ["secret", "hidden"]
>>> db = set([hashlib.sha256(word).hexdigest() for word in words])
>>> db
set(['2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b', 'e564b4081d7a9ea4b00dada53bdae70c99b87b6fce869f0c3dd4d2bfa1e53e1c'])
>>> def word_exists(word):
...     return hashlib.sha256(word).hexdigest() in db
...
>>> word_exists("hello")
False
>>> word_exists("hidden")
True