Рейтинг:1

Возможно ли на эллиптической кривой, что по $P$ мы можем сказать, является ли $a$ квадратичным вычетом по модулю $N$?

флаг sr

Представьте себе, что в схеме криптографии на эллиптических кривых, где $P=а\умножить на G$, Боб делится своим открытым ключом $P$ с Евой (дьявол, который хочет знать тайны, ему не положено). Боб также раскрыл подсказку о $а$ случайно. Подсказкой может быть один или комбинация элементов из следующего списка:

  1. Номер $а$ является НЕЧЕТНЫМ/ЧЕТНЫМ целым числом.
  2. Номер $а$ БОЛЬШЕ/МЕНЬШЕ, чем половина группового заказа $N/2$.
  3. Номер $а$ имеет $х$ значимые биты при записи в двоичном виде. (там $х$ это количество битов $а$, например, если $а=152=10011000$ тогда $х=8$
  4. Номер $а$ является квадратичным ОСТАТОК/НЕОСТАТОК по модулю $N$.

Вопрос 1:

Будет ли знание такой подсказки считаться существенной слабостью открытого ключа Боба, чтобы мы могли сказать, что использовать его больше небезопасно?

Вопрос 2:

Подсказки, упомянутые выше, содержат очень мало информации о $а$ Я полагаю. Я прав? Что, если мы сможем выявить их для всех точек кривой с помощью волшебного алгоритма?

Я знаю, что для пунктов 1-3 знание общего алгоритма, который для любого заданного $P=а\умножить на G$ это может сказать нам наверняка, что $а$ нечетный/четный или $а$ БОЛЬШЕ/МЕНЬШЕ, чем $N/2$ или же $а$ имеет $х$ биты полностью нарушат безопасность эллиптических кривых и с помощью которых можно будет получить $а$ от $P$.

А как же пункт 4? Я имею в виду, если кто-то может найти алгоритм, с помощью которого они могут определить, что для любого заданного $P$, $а$ является или не является квадратичным вычетом по модулю $N$, смогут ли они полностью восстановить $а$ и взломать криптографическую схему?

Что, если алгоритм может также определить квадратный корень из $а$ по модулю $N$?

Обновление 1:

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

kelalaka avatar
флаг in
Каково происхождение этого вопроса? Что имеет смысл в (3)? Как вы это измеряете? 1 и 2 уменьшают пространство до 1/4. Эффект числа 4 нельзя точно описать, если не задано значение $N$.
Titanlord avatar
флаг tl
Можете ли вы объяснить (3)? Если это количество единиц и нулей в ключе, это серьезный риск.
PouJa avatar
флаг sr
@kelalaka Я обновил вопрос и попытался ответить на ваши вопросы, пожалуйста, посмотрите.
PouJa avatar
флаг sr
@Titanlord Если я дам вам свой открытый ключ $P$, а также скажу, что в моем личном ключе 124$ единиц и 130$ нулей, сможете ли вы вычислить мой закрытый ключ? Что, если я не скажу количество нулей и единиц, а просто скажу общую сумму в этом примере $ 254 $.
kelalaka avatar
флаг in
Почему закрытый ключ с хорошим случайным источником должен иметь проблему с утечкой 3 бит, за исключением (3), до сих пор неясно, как они просачиваются.
Рейтинг:1
флаг tl

Влияние на безопасность от 1 и 2 можно считать незначительным. Скажем, у вас есть 256-битная безопасность, что подразумевает $2^{256}$ различные ключи на выбор. Если вы знаете, что ключ нечетный, это сводится к $2^{255}$ разные ключи. Для 2 аналогично.

Знание количества единиц и нулей может рассматриваться как значительный риск. Предположим, у вас есть 256-битный ключ, содержащий одну единицу. Остается только 256 возможных ключей. Это приводит к вопросу о том, сколько существует перестановок. Для двоичных чисел с заданной длиной X и заданным числом единиц N это приводит к числам ключа, которые можно рассчитать, используя:

$$ количество\ из\ ключей=\frac{(X!)}{ (N! * (X-N)!)} $$

В лучшем случае это приводит к $\приблизительно 2^{252}$ возможные ключи, на 128 шт. Но для разного количества единиц это только усугубляется. Атаки по времени часто пытаются выяснить, сколько существует различных единиц и нулей (или даже пытаются найти некоторые из них). Эти атаки часто являются серьезной проблемой. Некоторые из этих атак пытались угадать начальную 1 ключей эллиптической кривой, потому что некоторые старые алгоритмы имели различное время вычисления в зависимости от положения ведущей 1. Это не должно быть риском, например. 1 - это первый или второй бит. Но если ведущий был на позиции $я$ безопасность упадет до $2^{256-i}$. В зависимости от $я$ это может быть значительным риском, особенно если ключи выбираются совершенно случайно. Вы определенно не хотите этих рисков.

Насчет 4 я не уверен. Я отредактирую это, если найду хороший ответ.

PouJa avatar
флаг sr
Спасибо за ответ. Вы узнали о 4?
PouJa avatar
флаг sr
Любое обновление о 4?!
Titanlord avatar
флаг tl
Извините, я не могу доказать свое предположение, но я думаю, что это не будет иметь существенного значения. В зависимости от настроек уже могут существовать эффективные алгоритмы для получения этих знаний.
PouJa avatar
флаг sr
Спасибо, вы знаете какой-нибудь эффективный алгоритм, который для данного $P$ может определить, является ли $a$ квадратичным вычетом для выбранной вами кривой?

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

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