Новый метод сокрытия данных с помощью простых чисел?

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

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

$p = p_0 \ || \ данные \ || \ p_{конец}\ \ $ и $ \ \ q = q_0 \ || \ маркер \ || \ q_{конец}$

куда $p_0$ и $q_0$ случайны $сингл$ ненулевые цифры с $p_0 < q_0$, $данные$ это число с $к$ (десятичные) цифры, $маркер$ это случайное число с $к-1$ ненулевые цифры, за которыми следует $0$, и $p_{конец}$ и $q_{конец}$ случайные числа с $nk-1$ цифры.

Закодированные данные $N = P \× Q$ куда $P$ и $Q$ являются следующими простыми числами после $р$ и $q$. $n$ выбирается достаточно большим, чтобы факторизация $2n$-значное число невозможно и чтобы вместе с выбором $p_{конец}$ и $q_{конец}$, строительство $P$ и $Q$ не вызывает $данные$ или же $маркер$ изменить.

Несколько комментариев: (1) Хотя некоторые ограничения на $P$ и $Q$ известны, недостаточно использовать «факторинг с частичной информацией/известными битами». (2) Зная $P$ и $Q$, в любом порядке, позволяет однозначно найти скрытые данные. (3) Метод легко адаптируется к двоичному коду.

Пример: $данные$ это 271828 с $к$ = 6. Для простоты используем $n$ = 12:

$p = \mathtt {1 \underline {271828} 67213}$, $P = \mathtt {1 \underline {271828} 67221} \ \ $ и $ \ \ q = \ matthtt {6 \ underline {97811} \ underline {\ underline {0}} 97478} $, $ Q = \ matthtt {6 \ underline {97811} \ underline {\ underline {0}} 97499 $

$N = P \times Q = \mathtt {88749616158555602180279}$.

РЕДАКТИРОВАТЬ: данные могут быть любым целым числом (ноль или больше). Чтобы подчеркнуть, что оно не обязательно должно быть простым, я изменил данные примера с 314159 (что является простым числом) на 271828 (составное число).

РЕДАКТИРОВАТЬ (30 марта): добавлено «сингл» в описания $p_0$ и $q_0$ подчеркнуть, что каждый из $p_0$ и $q_0$ является одной ненулевой цифрой. Обратите внимание, что размер данных ($к$) заранее неизвестен, но обозначается $маркер$. Кроме того, самый известный результат, полученный Копперсмитом, заключается в том, что факторизация проста, если известна половина битов множителя.

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

Как вы знаете, Боб, схема обязательств — это схема, в которой у Алисы есть секрет; она публикует приверженность секрету («совершает секрет»), а затем позже она «открывает» обязательство, раскрывая секрет.

В схеме фиксации интересны два свойства безопасности:

• Прячется; Боб, который видит обязательство, не может сказать, в чем секрет (даже если у него есть предположение)
• привязка; когда Алиса открывает обязательство, она должна открыть его для значения, которое она имела в виду, когда создавала обязательство (то есть она не может открыть его для любого из двух разных значений в момент открытия).

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

Сейчас есть две стандартные схемы обязательств:

• Обязательства на основе хэша, где Алиса берет секрет $S$ и случайное значение $R$ и публикует обязательство $\text{Хэш}( S || R )$, для устойчивой к коллизиям хеш-функции $\text{Хэш}$; чтобы открыть его, она публикует $S$ и $R$. Это оказывается связывающим с точки зрения вычислений (на основе устойчивости хэша к коллизиям и при условии, что длина либо S, либо R хорошо известна) и статистически скрывающим (при условии, что $R$ достаточно длинный и нестандартное, но интуитивно понятное предположение о хеш-функции).

• Обязательства Педерсена, где у нас есть два разных генератора $г$ и $ч$ (с неизвестной взаимосвязью) какой-то группы, где проблема дискретного логарифма сложна; принять значение $S$, она выбирает случайное значение $R$ и публикует $g^Sh^R$; чтобы открыть его, она публикует $S$ и $R$. Это оказывается совершенным сокрытием и вычислительной привязкой (сводимой к проблеме DLog).

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

Теперь по вашей схеме:

• Что касается связывающего свойства, вы полностью связываете; У Алисы есть только один способ открыть секрет (при условии, что Боб проверит раскрытые факторы на простоту).

• Что касается свойства сокрытия, то на первый взгляд может показаться, что оно сводится к проблеме факторизации. Однако все не так просто; злоумышленник знает априори что-то о факторах (например, если он догадывается о секрете, и он также догадывается, где в $P$ что появляется (не так много возможностей), то у него есть как несколько цифр $P$ и знает, где ненулевые цифры в $Q$ появляются (а также цифра ноль)). Хотя неясно, как это можно использовать для упрощения факторизации, это было бы нестандартным предположением.

Оценивая эту схему, она не ужасна (пока секрет короткий, дополнительная информация, доступная злоумышленнику, вряд ли может быть использована); с другой стороны, это также неэффективно (генерация простых чисел стоит дорого, проверка выявленных $P$ и $Q$ значения (убедившись, что они простые), хотя и не такие дорогие, но все же не слишком дешевые). И было бы неочевидно, как вы могли бы создать эффективное доказательство с нулевым разглашением об утверждении о зафиксированных значениях.

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

• Установить, что ваши данные равны (или представлены) простым числом, не всегда так просто. Учитывая определенное сообщение, которое шифруется до простого числа 1, что мешает другому сообщению такой же длины зашифроваться до того же простого числа. (Может быть, маленькое пространство для сообщений?)

• Как здесь работает расшифровка...

• Я не вижу здесь доказательства безопасности. Атаки на RSA показали, что вы можете восстановить простые числа, если в них есть определенное количество битов. Вы можете как бы приблизиться к атаке грубой силы по длине сообщения, затем может быть использовать какую-то атаку частичного раскрытия ключа

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