Регистрация Войти
Рейтинг:3
LeonMSH avatar Crypto

Лучший алгоритм модульного возведения в степень на secp256k1/r1

флаг us
LeonMSH

Я знаю модульное возведение в степень ($r = b^e \bmod m$) важен для RSA, и я могу найти некоторый алгоритм, который, если e выражается в двоичной форме (для exp: ) - таким образом, для n-битного e можно ожидать ~ 1,5n раундов умножения модульной операции.

Я работаю над созданием методологии восстановления открытого ключа для ECC, такой как secp256k1/r1. В библиотеке secp256k1 есть очень эффективная реализация, но она написана на ASM-коде, что трудно понять. Но, по крайней мере, я знаю 1-й шаг - вам нужно восстановить $ry$ от $rx$ (т.е. r подписи). Это очень легко получить $ry^2$ от $rx$, но в следующем мне нужно будет сделать квадратный корень модульным, который можно преобразовать в модульное возведение в степень на поле, то есть $e= (p+1)/4.$

Хорошо, а теперь вопросы:

  1. Есть ли лучший алгоритм, кроме обычного модульного возведения в степень, для вычисления ($r = b^e \bmod m$)?
  2. Или, в качестве альтернативы, есть ли какой-нибудь сокращенный алгоритм специально для secp256k1, который мне вообще не нужно запускать модульное возведение в степень и при этом иметь возможность восстановить $ry$ от $rx$?
101
0 + 0
Рейтинг:2
fgrieu avatar Crypto
флаг ng
fgrieu

В криптосистемах вопроса нет замены модульному умножению. Некоторые языки, такие как Python, упрощают это в образовательных целях. Только.

В RSA и DSA и, в меньшей степени, в криптографии ECC на secp256k1 или же секп256р1, нужно вычислить $b^e\bmod м$ для больших $е$. Самые быстрые алгоритмы (например, скользящее окно возведения в степень) выступать о $\log_2 е$ модульное возведение в квадрат и тому подобное $\приблизительно0.2\,\log_2 e$ модульные умножения. Однако существуют и другие алгоритмы, лишь незначительно более дорогостоящие (например, Лестница Монтгомери), что может быть лучше с точки зрения защиты от побочных каналов.

Каждое модульное умножение или возведение в квадрат по модулю $м$, для приведенного выше или (в ECC) сложения или умножения точек на скаляр, вычислительные затраты растут не более чем как $(\лог м)^2$ при использовании алгоритмов, изученных в начальной школе, адаптированных к компьютерным словам вместо цифр. Это может быть снижено до $ (\ журнал м) ^ {\ приблизительно1.6} $ с Карацуба или же $ (\ журнал м) ^ {\ приблизительно 1,5} $ с Тоом-3, но в ECC модуль $м$ не настолько велик, чтобы много платить ($м$ это «всего» несколько сотен бит в ECC, а не несколько тысяч в RSA/DSA).

При разработке подписи или шифрования с использованием secp256k1 или же секп256р1 с нуля в образовательных целях обычно есть этапы:

  • Получение чего-то, что работает, путем создания сложение и удвоение точек в декартовых координатах поверх модульного умножения, затем точечное умножение, затем подпись и/или шифрование.
  • Заставьте его работать намного быстрее, используя лучшее представление точки, например. проективные координаты (что позволяет отложить дорогостоящую модульную инверсию до конца умножения точек)
  • Заставить его работать безопасно, что очень сложно и обычно требует переписывания многих вещей с нуля.
  • Оптимизация производительности.Это можно делать на любом этапе, но задумайтесь над высказыванием «преждевременная оптимизация — корень всех зол».

Некоторые онлайн-ссылки на модульное умножение и возведение в степень (не ECC):

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

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

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