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

Решение дискретного журнала с помощью BsG

флаг jo
arsenne lupulupin

Если мы рассмотрим группу G с модулем p, порядок q с $p=2*q+1$, и генератор $г=2$ ($ р $, $q$ огромные простые числа), есть ли способ решить проблему дискретного логарифма $ г ^ х = у $ для заданного y, используя алгоритм гигантского шага детских шагов И тот факт, что $х$ имеет форму: $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in\mathbb{N} $ без необходимости хранить все мелкие шаги в хеш-таблице, что невозможно при величине чисел $р$ и $q$.

редактировать: $ \alpha_i $ значения неизвестны злоумышленнику.

редактировать 2: $\alpha_i \in [0,\infty] $

96
0 + 0
poncho avatar
флаг my
poncho
Злоумышленник знает значения $\alpha_i$?
0
Ответить
kelalaka avatar
флаг in
kelalaka
Действительно ли $\alpha_i \in \{0,1\}$? $\mathbb{N} = \mathbb{Z}^+$ или $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$, по этому поводу нет единого мнения.
1
Ответить
Рейтинг:0
poncho avatar Crypto
флаг my
poncho

есть ли способ решить проблему дискретного журнала $г^х=у$ для $у$ дано, используя алгоритм гигантского шага детских шагов

Нет практического способа, если $р, д$ большие.

Даже если $х$ известно, что в форме $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in\mathbb{N} $ ?

Каждый потенциал $х$ может быть выражено в этой форме; рассмотреть возможность $\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$ и $\альфа_{0} = х$. Следовательно, зная, что $х$ выражается в этой форме, не предоставляет никакой дополнительной информации; BsGs можно использовать только в том случае, если модуль достаточно мал (и вопрос предполагает, что это не так)

0 + 0
Ievgeni avatar
флаг cn
Ievgeni
Нет $х
0
Ответить
poncho avatar
флаг my
poncho
@levgeni: если мы говорим о значениях, которые **могут** быть выражены в этой форме, у нас есть $x \ge 2047$ (и это с условием, что $0 \not\in \mathbb{N}$; в противном случае , все значения $x$ могут быть выражены в этой форме).
0
Ответить
poncho avatar
флаг my
poncho
@levgeni: и, если $x
0
Ответить
kelalaka avatar
флаг in
kelalaka
@poncho Я думаю, что levgeni утверждает, что даже если $x>2046$, это не означает, что $x$ не является тривиально маленьким. Большое понятно, а маленькому нужна метрика.
0
Ответить
poncho avatar
флаг my
poncho
@kelalaka: я не понимаю вашего аргумента; если мы интерпретируем вопрос о том, «разрешим ли DLog, если мы предполагаем, что показатель степени является случайным, обусловленным тем, что его можно выразить в заданной форме?» При таком понимании мой ответ правильный - как вы интерпретируете вопрос?
0
Ответить
kelalaka avatar
флаг in
kelalaka
@poncho, если $x$ мало (здесь нет метрики), но мы знаем границу, то BsG можно параметризовать для более быстрого решения, верно? И опять же, если $x$ мало, то на самом деле нам не нужны BsG, мы можем перебрать его так же, как мы можем перебрать от 1 до $2^{48}$ для возможных $x$'. Или вы неявно предполагаете, что $x$ равномерный случайный?
0
Ответить
Ievgeni avatar
флаг cn
Ievgeni
@poncho Хорошо, я думал, что $\alpha$ - это биты. Я немного потерялся со всеми правками. Я до сих пор не понимаю, почему вы говорили о $2046$. Я хотел бы удалить свой $-1$, но я могу это сделать, только если вы отредактируете свое сообщение.
0
Ответить
poncho avatar
флаг my
poncho
@levgeni: если $0 \not\in \mathbb{N}$, то минимальное значение $\sum_1^{10} 2^i\alpha_i$ может быть равно 2046. Некоторые определения $\mathbb{N}$ не включают 0, другие делают.
0
Ответить
Ievgeni avatar
флаг cn
Ievgeni
Но сумма в вопросе начинает равняться нулю, значит, она должна быть $2047$?
0
Ответить
poncho avatar
флаг my
poncho
@levgeni: я использую $\alpha_0$ в качестве изменяемого значения, поэтому у нас фактически есть $x = \alpha_0 + 2046$ - $\alpha_0 = 0$ не допускается, поэтому у нас есть $x > 2046$
0
Ответить
Ievgeni avatar
флаг cn
Ievgeni
@Ievgeni: Хорошо, спасибо за объяснение. Я понял. Но кажется, что наконец $alpha$ могут быть равны нулю.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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