Регистрация Войти
Рейтинг:1
hambam avatar Crypto

Временная сложность атаки грубой силы на SSS Shamir's Secret Sharing

флаг in
hambam

Я искал повсюду в академических статьях о временной сложности атаки грубой силы на ключ обмена секретами Шамира. Я запутался между тем, если это $ О (р ^ к) $ или же $ О (р) $, такой, что $р$ является модулем шифрования и $к-1$ степень полинома шифрования. Потому что практически, если мы собираемся перестроить полином шифрования, это эквивалентно грубому перебору всех $р$ возможные значения для $к$ коэффициенты, что приводит к $ О (р ^ к) $ алгоритм. Но ища непосредственно секрет, который является постоянным коэффициентом полинома, и зная, что $S<p$, приводит к $ О (р) $ алгоритм. Может кто подскажет, какой правильный и подходит ли он? $ О (р ^ к) $, почему не работает линейный алгоритм?

127
1 + 0
Рейтинг:3
poncho avatar Crypto
флаг my
poncho

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

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

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

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

0 + 5
hambam avatar
флаг in
hambam
спасибо за быстрый ответ! но я нашел здесь [ссылка] (https://www.ijcaonline.org/archives/volume155/number13/kannan-2016-ijca-912051.pdf), что * значение p не должно быть слишком маленьким, иначе оно может быть восприимчивым к грубой силовой атаке. Если значение p равно 128 битам, то это дает 2^128 возможных значений, что является слишком большим диапазоном для попытки грубой силы*. Что это значит тогда?
0
Ответить
Aman Grewal avatar
флаг gb
Aman Grewal
Если есть какой-то способ проверить секрет, его можно взломать, но на самом деле это не атака SSS.
1
Ответить
hambam avatar
флаг in
hambam
@AmanGewal, значит, атака SSS эквивалентна восстановлению полинома, используемого в шифровании, а не только повторному поиску секрета?
0
Ответить
poncho avatar
флаг my
poncho
@HamzaBa-mohammed: тот комментарий, который ты нашел, неверен
1
Ответить
poncho avatar
флаг my
poncho
@AmanGreval: «если есть способ проверить секрет»; ну да, если вы можете просмотреть все возможные секретные значения и определить, какое из них является правильным, да, вы можете его узнать. Однако вы не используете акции; они не дают вам никакой информации, которой у вас еще не было
3
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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