Я опишу стандартный прием Шамира, адаптированный к контексту Проверка подписи ECDSA. Отбрасывая некоторые индексы, вычислительно затратная часть вычислений
$$u\cdot G+v\cdot Q$$
куда $u$ и $v$ являются (мы предполагаем, строго положительными) целыми числами, $G$ и $Q$ являются точками эллиптической кривой, а $+$ является точечное сложение (которое для упрощения я считаю черным ящиком, выполнение которого доминирует над вычислительными затратами). Напомним, что по определению $$u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{terms}}$$
Хорошо подмечено $\mathbin\|u\mathbin\|$ для количества битов в целом $u$, это $\влево\lfloor\log_2(u)+1\вправо\rfloor$; то же самое для $\mathbin\|v\mathbin\|$.
Распространенный способ вычисления $u\cdotG$ это
- установлен $ Р: = Г $
- немного $b$ скопировано из двоичного представления $u$, начиная с индекса $\mathbin\|u\mathbin\|-1$ (первый бит справа от крайнего левого $1$ немного) до $0$ (самый правый бит)
- установлен $Р:=Р+Р$
- если $б=1$, установлен $R:=R+G$
Основной способ вычисления $u\cdot G+v\cdot Q$ было бы вычислить $u\cdotG$, тогда $v\cdot Q$ тем же методом, затем добавьте два результата. Трюк Шамира улучшает это:
- установлен $Ч:=Г+К$
- если $\mathbin\|u\mathbin\|>\mathbin\|v\mathbin\|$, установлен $ Р: = Г $;
- иначе, если $\mathbin\|u\mathbin\|<\mathbin\|v\mathbin\|$, установлен $R:=Q$;
- иначе (это если $\mathbin\|u\mathbin\|=\mathbin\|v\mathbin\|$ ), установлен $ Р: = Н $;
- немного $b$ (отв. $с$) скопировано из бинарного представления $u$ (отв. $v$), с представлениями $u$ или же $v$ дополняется слева нулями по мере необходимости, по индексу от $\max(\mathbin\|u\mathbin\|,\mathbin\|v\mathbin\|)-1$ вплоть до $0$
- установлен $Р:=Р+Р$
- если $б=1$ и $с=0$, установлен $R:=R+G$
- (иначе) если $б=0$ и $с=1$, установлен $R:=R+Q$
- (иначе) если $б=1$ и $с=1$, установлен $ Р: = Р + Н $
Это утверждение почти эквивалентно приведенному в этот ответ под названием трюк Штрауса-Шамира (когда я знаю этот трюк как трюк Шамира). Вариант, который я даю, избегает необходимости знать нейтральную группу, но требует $\макс(и,в)>0$.
Корректность стандартного умножения точек и трюка Шамира можно формально доказать по индукции.
Для больших случайных $u$ и $v$ из $к$ биты, наивный алгоритм вычисления $u\cdot G+v\cdot Q$ работает в среднем $\примерно3k$ точечные добавления, трюк Шамира сводит это к $\приблизительно1.75k$, например, на 42% меньше (экономическая выгода ниже, в значительной степени из-за удвоения точки $Р:=Р+Р$ это самый быстрый вид добавления очков, и тот, который больше всего уменьшается). Возможны дальнейшие улучшения, например. группировка битов по два или чуть больше, возможно, со «скользящим окном», когда $б=0=с$.
Обратите внимание, что в контексте проверки подписи $u$, $v$, $G$ и $Q$ все они общедоступны, поэтому побочные каналы (синхронизация, потребляемая мощность, эмиссия, кэши…) не являются проблемой безопасности, поскольку они связаны с генерацией сигнатур.
Я не знаю трюка Штрауса-Шамира с вопросом. другая ссылка, но смутно подозреваю, что он еще больше улучшает это, иногда выполняя вычитание вместо сложения, и / или более совместим с методом ускорения для сложения точек.
