Вопрос о коэффициенте ECDSA при решетчатой ​​атаке

Обновление: наконец-то я заставил свою решетчатую атаку работать. Поскольку фактическая причина довольно сложна, я решил написать ответ ниже, чтобы описать, как это работает, чтобы любой, у кого есть подобный вопрос, мог черпать вдохновение из моей работы. Вопрос не изменен.

Недавно я изучал решетчатую атаку. Я пытался использовать данные из TPM-FAIL чтобы помочь мне понять эту атаку и попытаться реализовать атаку, используя «метод учебника» (в сценариях атаки TPM-FAIL есть некоторая оптимизация). У меня возникли некоторые вопросы по прочтению материалов, в которых я не смог разобраться сам. Пожалуйста, помогите мне, если у вас есть идеи.

1. Формула подписи DSA, наконец, может быть преобразована в следующую уравнение:

   $k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n}$

   где k — эфемерный ключ, (r, s,) — пара подписей, d — закрытый ключ, H(m) - это дайджест сообщения, как обычно... вы знаете, как это делается.
   Затем это можно преобразовать в решетчатую форму. Что-то вроде следующего уравнение:

   $k_i+A_id+B_i\экв 0\pmod n$, куда $A_i=-s_i^{-1}r_i$ и $B_i=-s_i^{-1}H(м)$

   Чего я не понимаю, так это почему он должен быть отрицательным? фактически пытался изменить сценарий атаки, указанный в TPM-FAIL. набор данных и обнаружил, что удаление -1 в A_i и B_i сделает атаку неуспешный. Но мы можем переписать первое уравнение так:

   $s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n}$

   Концепция атаки по решетке должна оставаться в силе: если решетка вектор мал, алгоритм редукции базиса должен генерировать ответ. Что я сделал не так?

2. Во-вторых, я пытался использовать неоптимизированный подход, решетка SVP построена, как показано ниже:

$\begin{bmatrix}n&&&&&\&n&&&&&\&&\ddots&&&\&&&n&&\A_1&A_2&\dots&A_t&K/n&\ B_1&B_2&\dots&B_t&&K\end{bmatrix}$

Но мы ясно видим, что K/n будет дробным числом, которое не может использовать метод BKZ() или LLL() в sagemath. Я понимаю, что мы можем умножить все в этой матрице на n, чтобы все в этой матрице было целым числом. После применения BKZ() мы делим все на n, чтобы восстановить исходный результат: закрытый ключ должен находиться в предпоследнем столбце первой строки. Однако мне не удалось восстановить закрытый ключ. Даже если бы я использовал 100 подписей с 8-битными утечками. Верен ли мой подход?

Спасибо за вашу помощь заранее!

О первом вопросительном предложении вопроса:

почему он должен быть отрицательным?

читать буквально и с "it" относительно количества $A_i$ и $B_i$.

Второй набор уравнений действительно является (или может быть изменен) $k_i+{A_i}\,d+B_i\equiv0\pmod n$ куда $A_i=-s_i^{-1}\,r_i\bmod n$ и $B_i=-s_i^{-1}\,H(m)\bmod n$. $\bмод п$ подразумеваются. Поэтому в этом $A_i$ и $B_i$ неотрицательны.

Это по определению $\bmod$ оператор:

• $х\bмод п$ это $z$ в диапазоне $[0,n)$ с $ х \ эквив г \ pmod n $.
• $x^{-1}\bmod n$ это $z$ в диапазоне $[0,n)$ с $x\,z\equiv1\pmod n$
• $-x^{-1}\,y\bmod n$ это $z$ в диапазоне $[0,n)$ с $x\,z\equiv-y\pmod n$

Напомним, что $ х \ эквив г \ pmod n $ определяется как означающее, что $x-z$ является кратным $n$.

Мы можем переписать первое уравнение как $s_i^{-1}\,r_i+s_i^{-1}\,H(m)\equiv k_i\pmod n$. Концепция атаки на решетку должна оставаться в силе: если вектор решетки мал, алгоритм сокращения базиса должен генерировать ответ. Что я сделал не так?

Я смутно предполагаю, что проблема в том, что используемый код сокращения решетки требует ввода в матричной форме. Мы можем сопоставить это, переписав уравнение как $s_i^{-1}\,r_i+s_i^{-1}\,H(m)+k'_i\equiv 0\pmod n$ с $k'_i=n-k_i$. Но помните, что атака вращается вокруг возможности выбора с помощью атаки по времени $я$ такой, что $k_i$ маленький. Тот же метод отбора не даст малых $k'_i$; и я не уверен, что подходящий метод вообще возможен.