Вопрос про Черный ящик

[Ales]

Пусть в черном ящике сидит булева функция (алгоритм, программа).
Неизвестно как она устроена, известно лишь, что ее запись не слишком длинна (то есть практически реализуема).
У ящика есть несколько входов (переменных, от которых зависит функция) и несколько выходов (значение функции).
На входы ящика можно подавать единицы и нули, после чего на выходах ящика появляются соответствующие единицы и нули.

Итак, неизвестна конструкция ящика, но зато есть входные данные в черный ящик и соответствующие им выходные данные.

Можно ли по последовательности испытаний (входные данные - выходные данные) восстановить функцию и ее запись?

-- Чт май 13, 2010 10:18:45 --

Добавление: все должно быть практически реализуемо.
Последовательность испытаний должна быть не слишком длинной и
восстановление почти совпадающей (совпадающей с вероятностью близкой к 1) функции тоже годится.

[lel0lel]

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

[Ales]

lel0lel в сообщении #318825 писал(а):

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

Почему же тогда "неоднозначное соответствие"?

А как это делать? Я не очень в это верю.

-- Чт май 13, 2010 10:49:13 --

Конечно, когда входов мало, сделать легко.
Но если их 1000?

[Xaositect]

Тут такая сложность. Изменение одного выхода делается достаточно просто ($+(x_1-{\sigma_1})\dots (x_n-{\sigma_n})$). Поэтому для совсем точного восстановления надо проверить все наборы.

Если допускается неточное - то выбираете сколько хочется точек, выделяете значения и интерполируете. По значениям в $m$ точках можно построить полином по $\mathrm{mod}\ 2$ с $m$ слагаемыми.

Если известны какие-то особенности нашей функции или схемы, то можно еще какие-нибудь соображения использовать, но в общем случае восстановление - это сложная задача.

[Ales]

Xaositect в сообщении #318844 писал(а):

Если известны какие-то особенности нашей функции или схемы, то можно еще какие-нибудь соображения использовать, но в общем случае восстановление - это сложная задача.

То есть - нельзя решить. Или это открытая проблема?
Вопрос то действительно - из теории сложности.

[Xaositect]

Ales в сообщении #318851 писал(а):

То есть - нельзя решить. Или это открытая проблема?

Можно решить, но надо перебрать все возможные наборы.
Это в предположении того, что если $f $ - простая функция, то и $f + (x_1+\sigma_1)\dots(x_n+\sigma_n)$ - тоже простая. Тогда если мы не вычислили значения на множстве наборов $S\subsetneq \mathbb{F}_2^n$, то найдется набор $(\sigma_1 + 1, \dots, \sigma_n + 1)\notin S$, на котором две простые функции различаются.

[Ales]

Предположим, что в ящике возведение натурального числа в 1025 степень по модулю какого нибудь 300-значного простого числа.
Можно ли решить?

-- Чт май 13, 2010 11:22:10 --

Xaositect в сообщении #318856 писал(а):

Ales в сообщении #318851 писал(а):

То есть - нельзя решить. Или это открытая проблема?

Можно решить, но надо перебрать все возможные наборы.
Это в предположении того, что если $f $ - простая функция, то и $f + (x_1+\sigma_1)\dots(x_n+\sigma_n)$ - тоже простая. Тогда если мы не вычислили значения на множстве наборов $S\subsetneq \mathbb{F}_2^n$, то найдется набор $(\sigma_1 + 1, \dots, \sigma_n + 1)\notin S$, на котором две простые функции различаются.

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

-- Чт май 13, 2010 11:29:14 --

Почему такой вопрос? Для взлома шифра с открытым ключом надо найти обратную функцию.
Чтобы найти обратную функцию необходимо ли использовать код прямой функции,
или достаточно только черного ящика с этой функцией?

[Xaositect]

Ну это значительно проще. Тут одного-двух запросов должно хватить вроде. Вроде остатки от деления $2^{1025}$ на 300-значные числа не должны сильно повторяться.

[Ales]

Xaositect в сообщении #318863 писал(а):

Ну это значительно проще. Тут одного-двух запросов должно хватить вроде.

А если Вы не знаете что 1025 степень и может быть любая степень.

Или Вы вообще ничего не знаете. Но там 1025 степень по модулю $10^{300}$.

[Xaositect]

Ales в сообщении #318864 писал(а):

А если Вы не знаете что 1025 степень и может быть любая степень.

Если неизвестна степень - то это дискретный логарифм. Все верят, что это сложно, но это пока не доказано даже в предположении $\mathrm{P}\neq \mathrm{NP}$

[Ales]

Xaositect в сообщении #318863 писал(а):

Ну это значительно проще. Тут одного-двух запросов должно хватить вроде. Вроде остатки от деления $2^{1025}$ на 300-значные числа не должны сильно повторяться.

Неужели можно так просто найти простое число по модулю которого идет операция?

Интересно, кто-нибудь раньше задавал этот вопрос про черный ящик или нет?

[lel0lel]

Ales в сообщении #318873 писал(а):

Интересно, кто-нибудь раньше задавал этот вопрос про черный ящик или нет?

Задача Йоста, обратная задача рассеяния.

[Xaositect]

Ales в сообщении #318873 писал(а):

Неужели можно так просто найти простое число по модулю которого идет операция?

Ну давайте посмотрим. $10^{300} = 1000^{100} \approx 2^{1000}$.
Забудем пока, что модуль простой и возьмем два последовательных числа $t$ и $t + 1$ как модули.
Если $2^{1025}\ \mathrm{mod}\ t = r$, т.е. $2^{1025} = at + r$. тогда $2^{1025} = a(t + 1) + (r - a)$, т.е. для моследовательных чисел модули различаются на $a$, если не происходит перехода через 0. Ну и $a\approx 2^{1025}/t \approx 2^{25}$
Грубое, конечно, приближение, но оно говорит нам о том, что остатки все-таки редко повторяются. Если еще несколько чисел запросить, то точно определим модуль.

[Ales]

Xaositect в сообщении #318889 писал(а):

Ales в сообщении #318873 писал(а):

Неужели можно так просто найти простое число по модулю которого идет операция?

Ну давайте посмотрим. $10^{300} = 1000^{100} \approx 2^{1000}$.
Забудем пока, что модуль простой и возьмем два последовательных числа $t$ и $t + 1$ как модули.
Если $2^{1025}\ \mathrm{mod}\ t = r$, т.е. $2^{1025} = at + r$. тогда $2^{1025} = a(t + 1) + (r - a)$, т.е. для моследовательных чисел модули различаются на $a$, если не происходит перехода через 0. Ну и $a\approx 2^{1025}/t \approx 2^{25}$
Грубое, конечно, приближение, но оно говорит нам о том, что остатки все-таки редко повторяются. Если еще несколько чисел запросить, то точно определим модуль.

Не очень понял.
В этом примере можно за $\approx 2^{25}$ шагов факторизовать $2^{1025} - r$ и найти модуль. Но если увеличить степень, например до 2049, так сделать уже не получится.

Или есть другой способ кроме факторизации?

[Xaositect]

Не уверен, надо думать.
Но мне кажется, что проще. Вот если подавать на вход пары вида $a$ и $a^2$, то можно получить соотношения вида $q^2 \equiv r (\mathrm{mod}\ m)$, если набрать несколько таких $q$ и $r$ и сделать НОД от $q^2-r$, то будет уже значительно проще.