Ускорение secp256k1 с помощью эндоморфизма / Habr

В этой статье мы рассмотрим функцию ускорение secp256k1 с помощью эндоморфизма которая помогает в оптимизации проверки ECDSA для криптовалюты Биткоин, но для начала немного истории.

12 января 2009 года Сатоши Накамото в самых ранних транзакциях Биткоина отправил Хэлу Финни 10 BTC.

То, что Сатоши Накамото выбрал Хэла первым получателем Биткоинов, неудивительно. Сатоши очень уважал Хэла, который зарекомендовал себя как один из самых ярких программистов и криптографов в мире, разработав систему шифрования PGP. Хэл также заложил важную основу для многоразового доказательства работы, которое Сатоши будет использовать при разработке Биткоина.

Будучи одним из лучших в мире криптографов, Хэл понял, что Биткоин стал огромным прорывом сразу же после того, как он наткнулся на него.

Еще в 2008 году он назвал Биткоин «очень многообещающей идеей».

Этот твит, опубликованный 11 января 2009 года, является достаточным доказательством того, что Хэл предсказал успех Биткоина еще до того, как многие узнали, что это такое.

Прошло два года и в 2011 году Хэл Финни как разработчик и Биткоин-энтузиаст написал на форуме Bitcointalk, что функция эндоморфизма secp256k1 может быть использована для ускорения проверки подписи ECDSA

LAMBDA и BETA — это значения на кривой secp256k1, где:

secp256k1 использует следующее простое число для своих координат x и y:

p = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc2f

и порядок кривой:

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

Первым шагом является вычисление значений LAMBDA и BETA, таких что для любой точки кривой Q = (x, y):

LAMBDA * Q = (BETA*х mod р, у)

Это так называемый эффективно вычислимый эндоморфизм, и он означает, что вы можете очень быстро умножить любую точку кривой secp256k1 на это специальное значение LAMBDA, выполнив одно умножение mod p.

Значение которую нашел и опубликовал Хэл Финни:

LAMBDA = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

BETA = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Учитывая, что мы можем быстро умножать на LAMBDA, хитрость заключается в вычисление kQ. Сначала используем вычисление Q' = lambdaQ. Затем k нужно разбить на две части k1 и k2, каждая примерно в половину ширины n, так что:

k = k1 + k2*LAMBDA  mod  n

затем

k*Q = (k1 + k2*LAMBDA)*Q = k1*Q + k2*LAMBDA*Q = k1*Q + k2*Q'

Это последнее выражение можно эффективно вычислить с помощью алгоритма двойного умножения, а поскольку k1 и k2 имеют половинную длину, мы получаем ускорение.

Недостающая часть разбивает k на k1 и k2. При этом используются следующие 4 значения:

а1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
а2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

(это нормально, что a1 = b2)

Используем их следующим образом, чтобы разделить k:

c1 = RoundToNearestInteger(b2*k/n)
c2 = RoundToNearestInteger(-b1*k/n)

k1 = k - c1*a1 - c2*a2
k2 = -c1*b1 - c2*b2

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

Мы узнали о существование эндоморфизма при более детальном изучение репозитории от разработчика и исследователя Jean Luc Pons

Ранее мы опубликовали статью: "Pollard's Kangaroo находим решения дискретного логарифма secp256k1 PRIVATE KEY + NONCES в известном диапазоне" , где мы использовали исходный код для сборки Kangaroo от Jean Luc Pons.

На основе ускоренного механизма Jean Luc Pons указал VanitySearch

Откроем main.cpp

main.cpp

В строках 255 и 256 мы видим что Jean Luc Pons применил функцию ускорение эллиптической кривой secp256k1 с помощью эндоморфизма.

  lambda.SetBase16("5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72");
  lambda2.SetBase16("ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce");

Перейдем к экспериментальной части:

Как мы помним из статьи мы разбирали транзакции Биткоин Адреса 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
из списка Bitcoin Rich List на общую сумму более 10 миллионов долларов США, возьмем этот Биткоин Адрес в качестве примера

Откроем в терминале Google Colab [TerminalGoogleColab] и воспользуемся репозиторием «07EndomorphismSecp256k1»

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/07EndomorphismSecp256k1/

pip3 install base58

Откройте код endomorphism.py в строке 145 мы используем все короткие значение для ускорение secp256k1 с помощью эндоморфизма

def split_scalar_endo(k):
    n = N
    a1 = 0x3086d221a7d46bcde86c90e49284eb15
    b1 = -0xe4437ed6010e88286f547fa90abfe4c3
    a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
    b2 = a1
    c1 = div_nearest(b2 * k, n)
    c2 = div_nearest(-b1 * k, n)
    k1 = mod(k - c1 * a1 - c2 * a2, n)
    k2 = mod(-c1 * b1 - c2 * b2, n)
    k1neg = k1 > POW_2_128
    k2neg = k2 > POW_2_128
    if k1neg:
        k1 = n - k1
    if k2neg:
        k2 = n - k2
    return (k1neg, k1, k2neg, k2)

Скоприуем закрытый ключ в HEX-формате которую мы опубликовали в статье

HEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

Запустим Python-скрипт endomorphism.py указав закрытый ключ:

python3 endomorphism.py 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b > pubkey.txt

Результат публичного ключа сохранится в файл: pubkey.txt

Откроем файл: pubkey.txt и проверим:

cat pubkey.txt

04ca5606a1e820e7a2f6bb3ab090e8ade7b04a7e0b5909a68dda2744ae3b8ecbfa280a47639c811134d648e8ee8096c33b41611be509ebca837fbda10baaa1eb15

Далее получим Биткоин Адрес запустив Python-скрипт pubtoaddr.py

python3 pubtoaddr.py

Откроем файл: BitcoinAddress.txt и проверим:

cat BitcoinAddress.txt

14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
WIF:  5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e
HEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

Проверяем закрытый ключ на сайте bitaddress

Blockchain:

www.blockchain.com/btc/address/14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

По данной тематике вы можете ознакомиться литературой:

Галлант, Роберт П., Роберт Дж. Ламберт и Скотт А. Ванстон. «Более быстрое умножение точек на эллиптических кривых с эффективными эндоморфизмами». Ежегодная международная конференция по криптологии, стр. 190–200. Спрингер, Берлин, Гейдельберг, (2001)
Хэнкерсон, Даррел, Альфред Дж. Менезес и Скотт Ванстон. «Руководство по криптографии на эллиптических кривых». Компьютерные обзоры 46, вып. 1 (2005)
Хэл Финни. bitcointalk — «Ускорение проверки подписи». (2011) https://bitcointalk.org/index.php?topic=3238.0
Блахут, Ричард Э. «Криптография и безопасная связь». Издательство Кембриджского университета, (2014)

Данный видеоматериал создан для портала CRYPTO DEEP TECH для обеспечения финансовой безопасности данных и криптографии на эллиптических кривых secp256k1 против слабых подписей ECDSA в криптовалюте BITCOIN

Исходный код

Telegram: https://t.me/cryptodeeptech

Видеоматериал: https://youtu.be/DH6FyNY-Gh0

Источник: https://cryptodeep.ru/endomorphism