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

Изменение задачи дискретного логарифмирования в Zp путем выбора подмножества элементов группы

флаг do
Panos

Позволять $г$ генератор циклической группы $Z_p$ порядка $p-1$, куда $г$ может генерировать все элементы группы $\альфа\в Z_p$ как $\альфа = г^х$мод$р$, $x \in (0..p-1)$, где проблема дискретного логарифмирования сложна, т.е. вычисление $х=$журнал$_ga$.

Предположим, мы создаем криптографическую систему с указанными выше параметрами (например, схема шифрования или схема цифровой подписи), но с модификацией только учитываемых значений $х$ действительный такой, что $\альфа <т$, куда $t \in (0..p-1)$ «целевое» значение. Интуитивно безопасность этой системы эквивалентна системе без этой модификации (т. е. введения требования, что она может использовать только те $х$ таким образом, чтобы в результате $а$ находятся ниже цели), потому что злоумышленнику все равно придется перебирать все $х$ которые не удовлетворяют это.

Однако мой вопрос заключается в том, открывает ли это какую-либо потенциальную теоретико-числовую атаку? Например, можно ли ускорить работу злоумышленника с помощью какой-нибудь математической формулы, исключающей «недопустимые» $х$ и, таким образом, напрямую снизить безопасность криптосистемы?

88
0 + 0
kelalaka avatar
флаг in
kelalaka
Во-первых, убедитесь, что $p-1$ не вызывает атаки Pohlig-Hellman. Во-вторых, ищите кенгуру Полларда, которые очень хорошо работают на дальних дистанциях.
0
Ответить
флаг do
Panos
Таким образом, для того, чтобы Pohlig-Hellman работал, $p-1$ должно быть степенью простого числа, что также относится к исходным параметрам (т.е. кажется, что моя модификация не затрагивается этим). Алгоритм кенгуру выглядит применимым к моей модификации, но я до сих пор не уверен, как он может снизить безопасность исходной задачи. Учитывая алгоритм в https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm, даже если мой допустимый диапазон (0,...t) очень мал (например, если t=1 в крайнем случае), то кенгуру по-прежнему нужно будет вычислять ряд целых чисел $d_0,...,d_p$, что дорого, не так ли?
0
Ответить
fgrieu avatar
флаг ng
fgrieu
Вычислительно сложно создать экземпляр криптографической системы, ограничивающей $x$ с $g^x\bmod p=\alpha
1
Ответить
флаг do
Panos
Я согласен с тем, что достижение $t$ требует вычислительных усилий. Предположим, что $t$ достаточно велико, чтобы это усилие находилось в разумных пределах. Таким образом, интуитивно безопасность модифицированной системы (т. е. необходимая грубая сила злоумышленника) будет равна $p-t$, потому что злоумышленник знает $t$. Я просто пытаюсь понять, существует ли какая-нибудь теоретико-числовая атака, снижающая безопасность ниже $p-t$. Кенгуру, упомянутый выше, кажется мне не проблемой.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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