Я предполагаю, что предлагаемая система подписи принимает сообщение $ млн $, преобразует его в целое число $м$ меньше, чем $n$ путем добавления фиксированной константы $с$ слева от выражения $ млн $ как $я$ цифры в некотором основании $b\ge2$ (основание 10 в вопросе) таким образом $m:=c\,b^i+M$, затем строит подпись $\sigma=\mathrm{Sig}(M)$ по учебнику RSA с закрытым ключом $(н,д)$, это $\sigma:=m^d\bmod n$; и верификатор дан $(п,е)$ и $(М,\сигма)$ (или просто $\сигма$) вычисляет $\sigma^e\bmod n$ затем проверяет, что $c\,b^i+M$. Пока я оставляю это неуточненным, если $я$ фиксировано или зависит от $ млн $ (и как).
Добавляя известный префикс, злоумышленник может подделывать сообщения только методом грубой силы, и в результате безопасность этой схемы пропорциональна длине префикса.
Чтобы это утверждение имело шанс остаться верным, мы должны добавить "вплоть до префикса $с$ становится настолько большим, что факторизация $n$ становится самой легкой атакой". Я предполагаю это в следующем.
Это утверждение кажется верным (но у нас нет доказательства), если мы примем за определение безопасности подписи Экзистенциальная невозможность подделки при атаке с известным сообщением, в котором у злоумышленников есть открытый ключ $(п,е)$ плюс ряд действительных $(M_j,\sigma_j)$ пары для случайного $M_j$, и попытайтесь представить $(М,\сигма)$ пара для $ млн $ ни один из $M_j$.
Но это неправильно, если мы возьмем Экзистенциальная невозможность подделки при атаке выбранного сообщения, в котором злоумышленнику разрешено запрашивать подпись $\sigma_j$ любого сообщения $M_j$ по своему выбору, перед выставкой $(М,\сигма)$ как указано выше. Проблема в том, что при этой модели безопасности есть атаки лучше, чем брутфорс.
- Атака проста, если мы позволяем $я$ быть количеством цифр $ млн $ в базе $b$ (будь то с подавлением начальных нулей или без него) и используйте небольшую общедоступную экспоненту $е$ (например, 3): злоумышленник находит подпись любого сообщения $ млн $ он считает нужным (до некоторого предела размера) из подписи сообщения $М'=М\,б^е$ если $ млн $ достаточно короток, чтобы соответствовать $c\,b^{i'}+M'=c\,b^{i+e}+M\,b^e<n$ требование, так как $\mathrm{Sig}(M')\,b^{-1}\bmod n=\mathrm{Sig}(M)$.
- Для фиксированного $я$, все сложнее, но Десмедт и Одлызко атака позволяет подделку с трудностью, намного меньшей, чем грубая сила, далеко не удвоенной, когда мы позволяем $с$ быть в два раза больше, и даже субэкспоненциальным с $\log_2(с)$.
- Предыдущая атака становится легче, если мы позволим $я$ фиксируется для данного $с$, но равно размеру $с$ в базе $b$.
Знание префикса не является преимуществом для перебора сообщений (кроме того факта, что злоумышленник знает, как должны выглядеть выходные данные).
Мотивация подписи состоит в том, чтобы разрешить проверку без секретной информации, и секретность префикса противоречит этому. Я все же предположу.
Тогда это утверждение верно, за исключением нереалистичных атак с использованием только ключей, но спорно по той самой причине, которая делает его правильным: злоумышленники знают по крайней мере один $(M_0,\sigma_0)$ пара в дополнение к открытому ключу $(п,е)$, и поэтому они могут легко найти префикс $с$ вычисляя ${\sigma_0}^e\bmod n$.
