Представьте себе, что в схеме криптографии на эллиптических кривых, где $P=а\умножить на G$, Боб делится своим открытым ключом $P$ с Евой (дьявол, который хочет знать тайны, ему не положено). Боб также раскрыл подсказку о $а$ случайно. Подсказкой может быть один или комбинация элементов из следующего списка:
- Номер $а$ является НЕЧЕТНЫМ/ЧЕТНЫМ целым числом.
- Номер $а$ БОЛЬШЕ/МЕНЬШЕ, чем половина группового заказа $N/2$.
- Номер $а$ имеет $х$ значимые биты при записи в двоичном виде. (там $х$ это количество битов $а$, например, если $а=152=10011000$ тогда $х=8$
- Номер $а$ является квадратичным ОСТАТОК/НЕОСТАТОК по модулю $N$.
Вопрос 1:
Будет ли знание такой подсказки считаться существенной слабостью открытого ключа Боба, чтобы мы могли сказать, что использовать его больше небезопасно?
Вопрос 2:
Подсказки, упомянутые выше, содержат очень мало информации о $а$ Я полагаю. Я прав? Что, если мы сможем выявить их для всех точек кривой с помощью волшебного алгоритма?
Я знаю, что для пунктов 1-3 знание общего алгоритма, который для любого заданного $P=а\умножить на G$ это может сказать нам наверняка, что $а$ нечетный/четный или $а$ БОЛЬШЕ/МЕНЬШЕ, чем $N/2$ или же $а$ имеет $х$ биты полностью нарушат безопасность эллиптических кривых и с помощью которых можно будет получить $а$ от $P$.
А как же пункт 4? Я имею в виду, если кто-то может найти алгоритм, с помощью которого они могут определить, что для любого заданного $P$, $а$ является или не является квадратичным вычетом по модулю $N$, смогут ли они полностью восстановить $а$ и взломать криптографическую схему?
Что, если алгоритм может также определить квадратный корень из $а$ по модулю $N$?
Обновление 1:
Эти вопросы возникли, когда я изучал риски частичной компрометации базы данных закрытых ключей. Вот что происходит, если злоумышленник знает ключи к нашим закрытым ключам.