Bitcoin in a nutshell — Cryptography / Хабр

Baby-step, giant-step

Для начала приведу простое рассуждение: мы всегда можем записать любое целое

$x$

как

, где

$a$

— три произвольных целых. Например, можно записать

$10 = 2 cdot 3   4$

С учётом этого можно переписать уравнение задачи дискретного логарифмирования следующим образом:

Baby-step giant-step — это алгоритм «встречи посередине». В отличие от атаки перебором (при которой придётся вычислять все точки

$xP$

для каждого

$x$

, пока мы не найдём

$Q$

), можно вычислять «несколько» значений для

$bP$

и «несколько» значений для

$Q - amP$

, пока мы не найдём соответствие. Алгоритм работает следующим образом:

  1. Вычисляем $m = leftlceil{sqrt{n}}rightrceil$
  2. Для каждого $b$ из ${0, dots, m}$ вычисляем $bP$ и сохраняем результаты в хеш-таблицу.
  3. Для каждого $a$ из ${0, dots, m}$:
    1. вычисляем $amP$;
    2. вычисляем $Q - amP$;
    3. проверяем хеш-таблицу и ищем точку $bP$, такую, что $Q - amP = bP$;
    4. если такая точка существует, то мы нашли $x = am   b$.


Как видите, изначально мы вычисляем точки

$bP$

с небольшим инкрементом («детскими шагами»

«baby step»

) для коэффициента

$b$

, …). Во второй части алгоритма мы вычисляем точки

$amP$

с большим инкрементом («великанскими шагами»

«giant step»

) для

$am$

, …, где

$m$

— большое число).

Алгоритм baby-step, giant-step: сначала мы вычисляем несколько точек с небольшим шагом и сохраняем их в хеш-таблице. Затем делаем великанские шаги и сравниваем новые точки с точками в хеш-таблице. Найдя соответствие, мы можем вычислить дискретный алгоритм простой перестановкой членов.Чтобы понять, как работает алгоритм, забудем на минуту о том, что $bP$$Q = amP   bP$


В итоге

мы проверили все точки от $0P$ до $nP$

(то есть все возможные точки),

выполнив не более $2m$ сложений и умножений

(ровно

$m$

для «детских шагов», не более

$m$

для «великанских шагов»).

Если считать, что поиск в хеш-таблице занимает время $O(1)$временную и пространственную сложность $O(sqrt{n})$ (или $O(2^{k / 2})$, если учесть битовую длину). Это всё ещё экспоненциальное время, но оно намного лучше, чем при атаке перебором.

Ρ полларда

ρ Полларда — это ещё один алгоритм вычисления дискретных логарифмов. Он имеет ту же асимптотическую временную сложность

$O(sqrt{n})$

, что и baby-step giant-step, но его пространственная сложность равна всего

$O(1)$

. Если baby-step giant-step не мог решить дискретные логарифмы из-за огромных требований к памяти, может быть, ρ Полларда справится? Давайте проверим…

Для начала ещё раз напомню задачу дискретного логарифмирования: найти для заданных $P$$Q$$x$$Q = xP$$P$$Q$целые $a$, $b$, $A$ и $B$, такие, что $aP   bQ = AP   BQ$.Найдя четыре целых числа, мы сможем использовать уравнение $Q = xP$$x$


Теперь мы можем избавиться от

$P$

. Но прежде чем сделать это, вспомним, что наша подгруппа циклическая и имеет порядок

$n$

, то есть коэффициенты, используемые при умножении точек, берутся по модулю

$n$

Принцип работы ρ Полларда прост: мы определяем

псевдослучайную последовательность пар $(a, b)$

. Эту последовательность пар можно использовать для генерирования последовательности точек

$aP   bQ$

. Поскольку

$P$

являются элементами одной циклической подгруппы,

последовательность точек $aP   bQ$ тоже циклическаяЭто значит, что если мы обойдём нашу псевдослучайную последовательность пар $(a, b)$мы найдём пару $(a, b)$ и другую отдельную пару $(A, B)$, такие, что $aP   bQ = AP   BQ$. Те же точки, отдельные пары: мы сможем применить приведённое выше уравнение для нахождения логарифма.

Задача заключается в следующем: как обнаружить цикл эффективным способом?

Алгебраическое сложение

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

Для начала давайте избавимся от самых раздражающих тупиковых ситуаций. Мы уже знаем, что $P   (-P) = 0$$P   0 = 0   P = P$две ненулевые несимметричные точки $P = (x_P, y_P)$ и $Q = (x_Q, y_Q)$.Если $P$ и $Q$ не совпадают ($x_P ne x_Q$наклон:Пересечение

этой прямой с эллиптической кривой — это третья точка

$R = (x_R, y_R)$

или, аналогично:


Поэтому

$(x_P, y_P)   (x_Q, y_Q) = (x_R, -y_R)$

(обратите внимание на знаки и помните, что

$P   Q = -R$$R$$P$$Q$$R$$R$визуальному инструменту, при $P = (1, 2)$$Q = (3, 4)$$y^2 = x^3 - 7x   10$$P   Q = -R = (-3, 2)$

Да, всё верно!

Заметьте, что эти уравнения работают даже в случае, когда точка $P$ или $Q$ является точкой касания. Давайте проверим на $P = (-1, 4)$$Q = (1, 2)$

Мы получили результат

$P   Q = (1, -2)$

, который совпадает с результатом, полученным в

К случаю $P = Q$ нужно относиться немного иначе: уравнения для $x_R$$y_R$$x_P = x_Q$наклона другое уравнение:


Заметьте, что, как можно ожидать, это выражение для

$m$

является первой производной:

Чтобы доказать правильность этого результата, достаточно убедиться, что

$R$

принадлежит к кривой и что прямая, проходящая через

$P$

, имеет только два пересечения с кривой. Но мы снова не будем доказывать это и вместо этого разберём пример:

$P = Q = (1, 2)$


Что даёт нам

$P   P = -R = (-1, -4)$

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

Блокчейн: атаки, безопасность и криптография

Сегодня в статье мы предлагаем чуть более подробно рассмотреть потенциальные атаки на блокчейн как технологию, а так же продукты и сервисы основанные на нем. И конечно же чуть глубже заглянем внутрь его криптографической сердцевины, как основы обеспечения безопасности крипто вычислений

Пару слов о технологии

Прежде чем перейти непосредственно к вопросам безопасности буквально пару кратеньких абзацев о самой технологии Блокчейн простым языком.

Как говорят нам

, технология

BlockChain

(блокчейн) появилась по ИТ-шным меркам достаточно давно, а именно в 2009 году. И спустя некоторое время  громогласно на весь мир заявила о своем существовании, к примеру наиболее ярко проявив себя в качестве технологической платформы для

, коим сейчас является

.

Если не вдаваться в сложные формулировки и математическое описание, то Блокчейн (blockchain) – это по сути распределенная база данных, состоящая из множества блоков информации сгенерированным таким образом, что несанкционированная их модификация или удаление практически невозможно.

Фича этой технологии в том, что после того как блоки данных были опубликованы в реестре, используя криптографические функции, штампы времени и ссылки на предыдущий блок (связанная цепочка блоков) откатить их назад или же внести какие-то изменения в запись невозможно. Достигается это за счет того, что все вычисления децентрализованны, то есть нет единого управляющего центра и монопольной власти над вычислениями. К тому же вся информация о вычислениях хранится в сети сразу же у нескольких участников (так называемых ). Хотя само содержимое блоков не зашифровано и доступно в открытом виде, данные в блоке защищены криптографически через . А децентрализованная база публично хранит в незашифрованном виде полную информацию о всех современных транзакциях, подписываемых с помощью .

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

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

В ИТ-индустрии  блокчейн нашел себя прежде всего в сфере хранения и подтверждение данных, к примеру, то, что в настоящее время используется для интеллектуального анализа данных ().

Некоторые технические основы блокчейна

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

Как мы уже выше выяснили Блокчейн использует для вычислений  и защиты блоков . Рассмотрим чуть ближе понятия “цифровая подпись” и “хеш-цепочка”.

Если взять определение из , то

– это особый реквизит документа, который позволяет установить отсутствие искажения информации в электронном документе с момента формирования ЭП и подтвердить принадлежность ЭП владельцу. Значение реквизита получается в результате криптографического преобразования информации.

Как работает цифровая подпись?
И так, каждый человек для общения в Интернете или обмена данными с другими пользователями посредством компьютера и теллекомуникационных каналов связи может создать себе «личный идентификатор» (ID, никнейм) и «цифровую подпись», подтверждающее подлинность автора.

Электронная подпись позволяет:

  • Подтвердить авторство отправителя сообщения
  • Гарантировать, что отправленное и подтвержденное через ЭП сообщение никто не сможет подделать

Итак,

закрытым ключом

мы подписываем

«письма передачи прав собственности»

(транзакции), и тем самым, к примеру отдаем свои монеты кому-то другому.

Открытым ключом

 (сертификат) мы проверяем подлинность чужих транзакций.

(англ. hashing)

— преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины. Функция, реализующая алгоритм и выполняющая преобразование, называется

«хеш-функцией»

или

«функцией свёртки»

. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется

Читайте также:  Электронная подпись для ЕГАИС Лес (ЛесЕГАИС) от 2000 рублей

«хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения»

.

Криптографическая хеш-функция — всякая хеш-функция, являющаяся криптостойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений.

Как работает хеширование?

Показать хеширование довольно просто. Возьмем некоторое число… например номер телефона 7 (495) 606-36-02. Сложим все цифры вместе, несколько раз:
7 4 9 5 6 0 6 3 6 0 2=48 => 4 8=12 => 1 2=3
Так можно однозначно сопоставить любому номеру телефона некоторое число. Процесс суммирования называется хешированием, сам способ — хеш функцией, полученное число — хеш-суммой или просто хешем.

Обычно добиваются следующий свойств от хеширования:

  • Зная хеш-сумму (в нашем случае 3) нельзя определить исходный номер телефона.
  • Нельзя подогнать номер телефона под заранее известную сумму (в нашем примере неприменимо, обязательно для bitcoin).
  • Малое изменение номера телефона приведет к кардинальному изменению хеша (в нашем примере неприменимо, но обязательно для bitcoin).

Данный пример взят из

на Хабре.

Сложность вычислений

За требование к хешам блоков отвечает специальный параметр, называемый «сложность». Так как вычислительные мощности сети непостоянны, этот параметр пересчитывается клиентами сети через каждые 2021 блоков таким образом, чтобы поддерживать среднюю скорость формирования блокчейна на уровне 2021 блоков в две недели.

Таким образом, 1 блок должен создаваться примерно раз в десять минут. На практике, когда вычислительная мощность сети растёт — соответствующие временные промежутки короче, а когда снижается — длиннее. Перерасчёт сложности с привязкой ко времени возможен благодаря наличию в заголовках блоков времени их создания.

Атаки на Блокчейн и проблемы безопасности

Любые новые технологии всегда несут не только блага для цивилизации, но и содержат в себе новые риск,  в том числе риски связанные с информационной безопасностью.

Блокчейн, по мимо ИТ-феномена еще и явление социальное, вспомните хотя бы вокруг биткоина и в Китае! А как известно в любой социальной группе рано или поздно происходят  попытки обмана (мошенничества).

И так рассмотрим наиболее реалистичные и ключевые атаки на технологию Блокчейн и продукты построенные на его основе.

Атака 51%

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

Атаки на отказ  в обслуживании (DoS)

Отправка большого количества “мусорных” данных на узел, обрабатывающий транзакции, может усложнить его работу. Например, клиент Bitcoin Satoshi версии 0.7.0 блокирует все подозрительные узлы и транзакции, не позволяет дублировать транзакции, контролирует появление атаки DoS, ловит в системе злоумышленников, исправляет ошибки и т.д.

Взлом крипто алгоритмов хэш-функций

Атака Сибиллы

Хакер может попытаться наполнить сеть подконтрольными ему узлами, и остальные пользователи смогут подключиться только к блокам, созданным для мошенничества. К примеру, Атакующий блокирует транзакции от других пользователей, отсоединив вас от общей сети. После этого Атакующий подсоединяет вас только к блокам, которые создает он, в отдельной сети. В результате этого будут появляться транзакции, которые будут пересылать деньги повторно (double-spending).

Замедление времени в системе

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

Уязвимость транзакций

Несмотря на то, что транзакции в Bitcoin подписываются, эта подпись охватывает не всю информацию, которая хешируется для получения хеша транзакции. Фактически, существуют возможность изменить параметры транзакции так, что изменится хеш, но подпись останется прежней.

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

Есть еще одна разновидность этой атаки получившие название  «гибкость транзакций». Суть атаки в том, что  злоумышленник изменяет уникальный идентификатор транзакции биткоинов до ее подтверждения в сети Bitcoin. При таком изменении и при соблюдении должных условий пользователь может сделать вид, что транзакция не была осуществлена.

Ошибки кода

Баги могут привести к нестабильности в защите системы. Например, в узле информация должна обновляться за короткий отрезок времени. Если из-за бага это не произошло, в цепочке не появилась нужная информация, неправильные данные начали распространяться по сети и т.д. Все это может стать причиной остановки работы сети на несколько часов.

Криптография на страже безопасности блокчейна

Базовая идея

Что такое ECDSA

Эллиптические кривые – теория

В эллиптических кривых нет ничего сложного. Алгебраически каждая такая кривая может быть представлена как уравнение вида:

y² = x³ ах b

Для а = 0 и b = 7 (а это именно та версия, которую использует Биткойн) эта кривая выглядит так:

Эллиптические кривые имеют некоторые полезные свойства. Например, не-вертикальная прямая, пересекающая кривую в двух точках, всегда будет пересекать ее и в третьей точке, лежащей на кривой. Другим свойством является то, что если не-вертикальная прямая является касательной к кривой в одной из точек, то она обязательно пересекает кривую еще ровно в одной точке.

Мы можем использовать эти свойства, чтобы определить две операции над точками, составляющими кривую: сложение точек и удвоение.

Для сложения точек, P Q = R мы проводим через точки P и Q прямую, которая, по свойствам эллиптических кривых, пересекает кривую в некоторой третьей точке R. Затем мы находим точку на кривой, симметричную точке R относительно оси X. Именно эта точка R и будет считаться суммой P и Q. Это легче всего понять, глядя на следующую схему:

Это все хорошо, но как бы нам сложить точку саму с собой? Для этого определяется операция удвоения точки, P P = R. При удвоении мы проводим прямую, касательную к данной эллиптической кривой в точке P, которая, согласно свойствам кривой, должна пересекать ее еще в одной точке R‘. Точка R, симметричная Rотносительно оси X, и будет считаться точкой удвоения P. На графике это выглядит следующим образом:

Эти две операции можно использовать, чтобы определить операцию скалярного умножения, R = a P, определяемую как добавление точки Р самой к себе a раз. Например:

R = 7P

R = P (P (P (P (P (P P)))))

Процесс скалярного умножения, как правило, можно упростить, используя комбинацию сложения и удвоения точек.

Например:

R = 7P

R = P 6P

R = P 2 (3P)

R = P 2 (Р 2P)

Здесь операция 7P была разбита на два этапа удвоения точек и два сложения точек — в итоге, вместо 7 операций нужно произвести всего четыре.

Собственно, теперь вы знаете об эллиптических кривых все, что о них стоит знать.

Закрытый ключ – теория

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

По этой же причине большинство Bitcoin клиентов при создании приватного ключа просто берут 256 случайных бит — вероятность коллизии крайне мала.

Открытый (публичный) ключ – теория

Два важных нюанса. Во-первых, несложно видеть, что операция получения публичного ключа определена однозначно, то есть конкретному приватному ключу всегда соответствует один единственный публичный ключ. Во-вторых, обратная операция является вычислительно трудной и, в общем случае, получить приватный ключ из публичного можно только полным перебором первого.

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

ECDSA в биткойне

Уравнение эллиптической кривой:
y² = x³ 7

Простой модуль:
2256— 232 — 29 — 28 — 27 — 26 — 24 — 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Базовая точка:

04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Жирным шрифтом выделена координата X в шестнадцатеричной записи. За ней сразу следует координата Y.

Читайте также:  Как в Подмосковье получить усиленную квалифицированную электронную подпись

Порядок: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Этот набор параметров для эллиптической кривой известен как secp256k1 и является частью семейства стандартов SEC (Standards for Efficient Cryptography), предлагаемых для использования в криптографии. В биткойне кривая secp256k1 используется совместно с алгоритмом цифровой подписи ECDSA (elliptic curve digital signature algorithm). В ECDSA секретный ключ — это случайное число между единицей и значением порядка. Открытый ключ формируется на основании секретного: последний умножается на значение базовой точки. Уравнение имеет следующий вид:

Открытый ключ = секретный ключ * G

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

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

  • Выбирается некоторое целое k в пределах от 1 до n-1
  • Рассчитывается точка (х, у) = k * G с использованием скалярного умножения
  • Находится r = х mod n. Если r = 0, то возврат к шагу 1
  • Находится s = (z r * d) / k mod n. Если s = 0, то возврат к шагу 1
  • Полученная пара (r, s) является нашей подписью

После получения данных и подписи к ним, третья сторона, зная публичный ключ, может их верифицировать. Шаги для проверки подписи такие (Q — открытый ключ):

  • Проверка, что и r, и s находятся в диапазоне от 1 до n-1
  • Рассчитывается w = s-1 mod n
  • Рассчитывается u = z * w mod n
  • Рассчитывается v = r * w mod n
  • Рассчитывается точка (x, y) = uG vQ
  • Если r = x mod n, то подпись верна, иначе — недействительна

В самом деле,

uG vQ = u vdG = (u vd)G = (zs-1 rds-1)G = (z rd) s-1G = kG

Последнее равенство использует определение s на этапе создания подписи.

Безопасность ECDSA связана со сложностью задачи поиска секретного ключа, описанной выше. Помимо этого, безопасность исходной схемы зависит от «случайности» выбора k при создании подписи. Если одно и то же значение k использовать более одного раза, то из подписей можно извлечь секретный ключ, что и

с PlayStation 3. Поэтому современные реализации ECDSA, в том числе используемые в большинстве биткойн-кошельков, генерируют k детерминировано на основе секретного ключа и подписываемого сообщения.

Отечественный  ГОСТ Р 34.10-2021 vs ECDSA

– российский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи. Принят и введён в действие Приказом Федерального агентства по техническому регулированию и метрологии от 7 августа 2021 года № 215-ст вместо утратившего силу предыдущего ГОСТ Р 34.10-2001.

ГОСТ Р 34.10-2021  основан на эллиптических кривых. Стойкость этих алгоритмов основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции.

После подписывания сообщения М к нему дописывается цифровая подпись размером 512 или 1024 бит и текстовое поле. В текстовом поле могут содержаться, например, дата и время отправки или различные данные об отправителе.

Криптостойкость цифровой подписи опирается на две компоненты — на стойкость хэш-функции и на стойкость самого алгоритма шифрования.
Вероятность взлома хэш-функции по ГОСТ 34.11-94 составляет Bitcoin in a nutshell — Cryptography / Хабр при подборе коллизии на фиксированное сообщение и Bitcoin in a nutshell — Cryptography / Хабр при подборе любой коллизии. Стойкость алгоритма шифрования основывается на проблеме дискретного логарифмирования в группе точек эллиптической кривой. На данный момент нет метода решения данной проблемы хотя бы с субэкспоненциальной сложностью.
Один из самых быстрых алгоритмов, на данный момент, при правильном выборе параметров — Bitcoin in a nutshell — Cryptography / Хабр-метод и Bitcoin in a nutshell — Cryptography / Хабр-метод Полларда.
Для оптимизированного Bitcoin in a nutshell — Cryptography / Хабр-метода Полларда вычислительная сложность оценивается как Bitcoin in a nutshell — Cryptography / Хабр. Таким образом для обеспечения криптостойкости Bitcoin in a nutshell — Cryptography / Хабропераций необходимо использовать 256-разрядное Bitcoin in a nutshell — Cryptography / Хабр.
Особенностью стандарта ГОСТ Р 34.10-2021 то, что в документе не зафиксированы какие-либо кривые, рекомендуемые для использования, присутствует только набор требований к ним. Для конкретных примеров кривых, приведенных в стандарте, явно оговорено, что они должны использоваться сугубо в тестовых целях. В этом наш стандарт существенно отличается, например, от документа, определяющего схему ECDSA: в FIPS PUB 186-4 [4] приведены рекомендованные (даже с пометкой “для использования в государственных учреждениях”) кривые. С одной стороны, данный подход позволяет сохранять стандарт неизменным даже при появлении новых результатов о “слабых” классах эллиптических кривых: достаточно будет проверить новые ограничения для используемых на практике кривых и при необходимости быстро провести их замену – но не менять государственный стандарт. С другой стороны, отсутствие рекомендуемых для использования параметров требует дополнительных действий от криптографического сообщества по выбору и обоснованию конкретных параметров, а также согласованию их с регулирующими органами и созданию методических рекомендаций.

ФСБ участвует в разработке международного стандарта блокчейна

мы рассказываем о главных новостях из мира IT, актуальных угрозах и событиях, которые оказывают влияние на

, бизнес глобальных корпораций и безопасность пользователей по всему миру. Узнай первым как

Геометрическое сложение

Благодаря тому, что мы находимся в абелевой группе, то можем записать

$P   Q   R = 0$

как

$P   Q = -R$

. Это уравнение в такой форме позволяет нам вывести геометрический способ вычисления суммы двух точек

$P$если мы проведём линию, проходящую через $P$ и $Q$, эта прямая пересечёт третью точку кривой $R$

(это подразумевается, потому что

$P$

находятся на одной прямой)

. Если мы возьмём обратную величину этой точки $-R$, мы найдём сумму $P   Q$Проводим прямую через $P$ и $Q$. Прямая пересекает третью точку $R$. Симметричная ей точка $-R$ является результатом $P   Q$.

Геометрический способ работает, но требует усовершенствования. В частности, нам нужно ответить на несколько вопросов:

  • Что если $P = 0$ или $Q = 0$? Разумеется, мы не сможем провести прямую (0 не находится на плоскости $xy$). Но поскольку мы определили 0 как единичный элемент, $P   0 = P$ и $0   Q = Q$ для любой $P$ и любой $Q$.
  • Что если $P = -Q$? В этом случае прямая, проходящая через две точки, вертикальна, и не пересекает третью точку. Но если $P$ является обратной величиной $Q$, то $P   Q = P   (-P) = 0$ из определения обратной величины.
  • Что если $P = Q$? В этом случае через точку проходит бесконечное количество прямых. Здесь всё становится немного сложнее. Но представим, что точка $Q' ne P$. Что произойдёт, если мы заставим $Q'$ стремиться к $P$, всё больше приближаясь к ней?
    При сближении двух точек проходящая через них прямая становится касательной к кривой.

    Поскольку $Q'$ стремится к $P$, прямая, проходящая через $P$ и $Q'$ становится касательной к кривой. В свете этого мы можем сказать, что $P   P = -R$, где $R$ — это точка пересечения между кривой и касательной к кривой в точке $P$.

  • Что если $P ne Q$, но третьей точки $R$ нет? В этом случае ситуация похожа на предыдущую. На самом деле, в этой ситуации прямая, проходящая через $P$ и $Q$, является касательной к кривой.
    Если наша прямая пересекает только две точки, то это значит, что она является касательной к кривой. Легко увидеть, как результат сложения становится симметричным одной из двух точек.

    Предположим, что $P$ является точкой касания. В предыдущем случае мы записали $P   P = -Q$. Это уравнение теперь превращается в $P   Q = -P$. С другой стороны, если бы точкой касания была $Q$, то правильным было бы уравнение $P   Q = -Q$.

Геометрический способ теперь полон и учитывает все случаи. С помощью карандаша и линейки мы можем выполнить сложение всех точек любой эллиптической кривой. Если хотите попробовать,

взгляните на визуальный инструмент на HTML5/JavaScript, созданный мной для вычисления сумм эллиптических кривых

Подписывание с помощью ecdsa

Сценарий следующий:

Алиса хочет подписать сообщение своим закрытым ключом$d_A$

), а

Боб хочет проверить подпись с помощью открытого ключа Алисы$H_A$

). Никто, кроме Алисы не должен иметь возможности создать действительные подписи. Каждый должен иметь возможность проверить подписи.

Алиса и Боб снова используют одинаковые параметры области определения. Мы рассмотрим алгоритм ECDSA, разновидность Digital Signature Algorithm, применённого к эллиптическим кривым.

ECDSA работает с хешем сообщения, а не с самим сообщением. Выбор хеш-функции остаётся за нами, но, очевидно, нужно выбирать криптографическую хеш-функцию. Хеш сообщения необходимо урезать, чтобы битовая длина хеша была такой же, что и битовая длина $n$Урезанный хеш — это целое число и оно будет обозначаться как $z$.

Алгоритм, выполняемый Алисой для подписывания сообщения, работает следующим образом:

  1. Берём случайное целое $k$, выбранное из ${1, dots, n - 1}$ (где $n$ — это по-прежнему порядок группы).
  2. Вычисляем точку $P = kG$ (где $G$ — базовая точка подгруппы).
  3. Вычисляем число $r = x_P bmod{n}$ (где $x_P$ — это координата $x$$P$).
  4. Если $r = 0$, то выбираем другое $k$ и пробуем снова.
  5. Вычисляем $s = k^{-1} (z   rd_A) bmod{n}$ (где $d_A$ — закрытый ключ Алисы, а $k^{-1}$ — мультипликативная инверсия $k$ по модулю $n$).
  6. Если $s = 0$, то выбираем другое $k$ и пробуем снова.
Читайте также:  Как сделать простую электронную подпись? -

Пара

$(r, s)$ является подписьюАлиса подписывает хеш $z$ с помощью закрытого ключа $d_A$ и случайного $k$. Боб проверяет правильность подписи сообщения с помощью открытого ключа Алисы $H_A$.Проще говоря, этот алгоритм сначала генерирует секретный ключ ($k$$r$$r$$s = k^{-1} (z   rd_A) bmod{n}$$s$$k$$n$$n$Если подгруппа имеет порядок непростого числа, ECDSA использовать не удастся. Неслучайно все стандартизированные кривые имеют простой порядок, а имеющие непростой порядок неприменимы для ECDSA.

Поиск базовой точки


Для алгоритмов ECC требуются подгруппы с высоким порядком. Поэтому обычно выбирается эллиптическая кривая, вычисляется её порядок (

$N$

), в качестве порядка группы (

$n$

) выбирается большой делитель, а потом находится подходящая базовая точка. То есть мы не выбираем базовую точку, после чего вычисляем её порядок, а производим обратную операцию: сначала выбираем достаточно хороший порядок, а потом ищем подходящую базовую точку. Как же это сделать?

Во-первых, нужно ввести ещё одно понятие. Теорема Лагранжа подразумевает, что число $h = N / n$ всегда целое (потому что $n$$N$$h$кофактор подгруппы.Теперь рассмотрим, что для каждой точки эллиптической кривой есть $NP = 0$$N$$n$

Теперь допустим, что

$n$

— простое число (мы предпочитаем простые порядки по причинам, изложенным в первой части статьи). Это уравнение, записанное в такой форме, говорит нам, что точка

$G = hP$

создаёт подгруппу порядка

$n$

(за исключением случая

$G = hP = 0$

, в котором подгруппа имеет порядок 1).

В свете этого мы можем определить следующий алгоритм:

  1. Вычисляем порядок $N$ эллиптической кривой.
  2. Выбираем порядок $n$ подгруппы. Чтобы алгоритм сработал, число должно быть простым и быть делителем $N$.
  3. Вычисляем кофактор $h = N / n$.
  4. Выбираем на кривой случайную точку $P$.
  5. Вычисляем $G = hP$.
  6. Если $G$ равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком $n$ и кофактором $h$.

Заметьте, что алгоритм работает только если

$n$

простое. Если бы

$n$

не было простым, то порядок

$G$

мог быть одним из делителей

$n$

Порядок подгруппы


Можно задаться вопросом,

каков порядок подгруппы, порождённой точкой $P$

(или, иными словами, каков порядок

$P$

). Для ответа на этот вопрос мы не можем использовать алгоритм Шуфа, потому что этот алгоритм работает только для целых эллиптических кривых, но не для подгрупп. Прежде чем приступить к решению задачи, нам нужно ещё немного информации:

  • Пока мы определяли порядок как количество точек группы. Это определение по-прежнему действительно, но в циклических подгруппах мы можем дать новое аналогичное определение: порядок $P$ — это минимальное положительное целое $n$, такое, что $nP = 0$.

    На самом деле, если посмотреть на предыдущий пример, то наша подгруппа состояла из пяти точек, и $5P = 0$.

  • Порядок $P$ связан с порядком эллиптической кривой теоремой Лагранжа, согласно которой порядок подгруппы — это делитель порядка исходной группы.

    Иными словами, если эллиптическая кривая содержит $N$ точек, а одна из подгрупп содержит $n$, то $n$ является делителем $N$.

Два этих факта вместе дают нам возможность определить порядок подгруппы с базовой точкой

$P$

  1. Вычисляем порядок эллиптической кривой $N$ с помощью алгоритма Шуфа.
  2. Находим все делители $N$.
  3. Для каждого делителя $n$ порядка $N$ вычисляем $nP$.
  4. Наименьшее $n$, такое, что $nP = 0$, является порядком подгруппы.


Например, кривая

$y^2 = x^3 - x   3$

над полем

$mathbb{F}_{37}$

имеет порядок

$N = 42$

. Её подгруппы могут иметь порядок

$n = 1$

или

$42$

. Если

, то увидим, что

$P ne 0$

, …,

$7P = 0$

, то есть порядок

$P$

равен

$n = 7$важно брать наименьший, а не случайный делитель. Если мы будем выбирать случайно, то можем получить $n = 14$$y^2 = x^3 - x   1$$mathbb{F}_{29}$$N = 37$$n = 1$$37$$n = 1$$n = N$

Скалярное умножение и циклические подгруппы


Для вещественных чисел умножение можно определить как:

И, повторюсь, мы можем использовать алгоритм удвоения-сложения для выполнения умножения за

$O(k)$

, где

$k$

— это количество бит

$n$

). Я написал

интерактивный инструмент для скалярного умноженияУмножение точек для эллиптических кривых над $mathbb{F}_p$$y^2 equiv x^3   2x   3 pmod{97}$$P = (3, 6)$вычислим все величины, кратные $P$Все значения, кратные $P = (3, 6)$, представляют собой пять различных точек ($0$, $P$, $2P$, $3P$, $4P$), которые циклически повторяются. Легко заметить сходство между скалярным умножением для эллиптических кривых и сложением в модулярной арифметике.


Можно сразу же заметить две особенности: во-первых, значений, кратных

$P$

, всего пять: другие точки эллиптической кривой никогда ими не становятся. Во-вторых, они

повторяются циклически

. Можно записать:

для любого целого

$k$

. Заметьте, что благодаря оператору деления с остатком эти пять уравнений можно «ужать» в одно:

$kP = (k bmod{5})P$эти пять точек замкнуты относительно операции сложения. Что это значит: как бы я ни суммировал $0$$P$$2P$$3P$$4P$$P = (3, 6)$$P$


Что означает:

если мы складываем два значения, кратных $P$, то получаем значение, кратное $P$

(т.е. значения, кратные

$P$

, замкнуты относительно операции сложения). Этого достаточно для того, чтобы

, что

множество кратных $P$ значений — это циклическая подгруппа

группы, образованной эллиптической кривой.

«Подгруппа» — это группа, являющаяся подмножеством другой группы. «Циклическая подгруппа» — это подгруппа, элементы которой циклически повторяются, как мы показали в предыдущем примере. Точка $P$генератором или базовой точкой циклической подгруппы.

Циклические подгруппы — фундамент для ECC и других криптосистем. Позже я объясню, почему это так.

Черепаха и заяц

Для обнаружения цикла мы можем проверить все возможные значения

$a$

с помощью

, но при условии, что существует

$n^2$

таких пар, алгоритм будет иметь сложность

$O(n^2)$

, что намного хуже атаки простым перебором.

Но существует и более быстрый способ: алгоритм черепахи и зайца (также известный как алгоритм нахождения цикла Флойда). На рисунке ниже показан принцип работы метода черепахи и зайца, на котором основан ρ-алгоритм Полларда.

У нас есть кривая $y^2 equiv x^3   2x   3 pmod{97}$ и точки $P = (3, 6)$ и $Q = (80, 87)$. Точки принадлежат циклической подгруппе с порядком 5. Мы обходим последовательность пар с разными скоростями, пока не находим две разные пары $(a, b)$ и $(A, B)$, дающих одну точку. В этом случае мы нашли пары $(3, 3)$ и $(2, 0)$, что позволяет нам вычислить логарифм как $x = (3 - 2)(0 - 3)^{-1} bmod{5} = 3$. И на самом деле, у нас получилось $Q = 3P$.В сущности, мы берём псевдослучайную последовательность пар $(a, b)$$aP   bQ$$(a, b)$$P$$Q$

Теперь мы берём двух животных, черепаху и зайца, и заставляем обходить последовательность слева направо. Черепаха (зелёная точка на изображении) медленная и считывает каждую точку, одну за другой; заяц (красная точка) быстр и пропускает точку на каждом шаге.

Через какое-то время черепаха и заяц найдут одну точку, но с разными парами коэффициентов. Или, если выразить это уравнениями, черепаха найдёт пару $(a, b)$$(A, B)$$aP   bQ = AP   BQ$$O(log n)$ пространства. Вычисление сложности асимптотического времени не так просто, но мы можем построить вероятностное доказательство, показывающее, что временная сложность равна $O(sqrt{n}$), как мы уже говорили.

Шифрование с помощью ecdh

ECDH — это разновидность

для эллиптических кривых. На самом деле это скорее

, а не алгоритм шифрования. В сущности, это означает, что ECDH задаёт (в определённой степени) порядок генерирования ключей и обмена ими. Способ шифрования данных с помощью таких ключей мы можем выбирать сами.

Он решает следующую проблему: две стороны (обычно Алиса и Боб) хотят безопасно обмениваться информацией, чтобы третья сторона (посредник, Man In the Middle) мог перехватывать её, но не мог расшифровать. Например, это один из принципов TLS.

Вот как это работает:

  1. Сначала Алиса и Боб генерируют собственные закрытые и открытые ключи. У Алисы есть закрытый ключ $d_A$ и открытый ключ $H_A = d_AG$, у Боба есть ключи $d_B$ и $H_B = d_BG$. Заметьте, что и Алиса, и Боб используют одинаковые параметры области определения: одну базовую точку $G$ на одной эллиптической кривой в одинаковом конечном поле.
  2. Алиса и Боб обмениваются открытыми ключами $H_A$ и $H_B$ по незащищённому каналу. Посредник (Man In the Middle) перехватывает $H_A$ и $H_B$, но не может определить ни $d_A$, ни $d_B$, не решив задачу дискретного логарифмирования.
  3. Алиса вычисляет $S = d_A H_B$ (с помощью собственного закрытого ключа и открытого ключа Боба), а Боб вычисляет $S = d_B H_A$ (с помощью собственного закрытого ключа и открытого ключа Алисы). Учтите, что $S$ одинаков и для Алисы, и для Боба. На самом деле:

    $S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A$

Однако посреднику известны только

$H_A$

(вместе с другими параметрами области определения) и он не сможет найти

общий секретный ключ $S$

. Это известно как задача Диффи-Хеллмана, которую можно сформулировать следующим образом:

Каким будет результат $abP$ для трёх точек $P$, $aP$ и $bP$?


Или, аналогично:

Каким будет результат $k^{xy}$ для трёх целых $k$, $k^x$ и $k^y$?

(Последняя формулировка используется в исходном алгоритме Диффи-Хеллмана, основанном на модулярной арифметике.)

Протокол Диффи-Хеллмана: Алиса и Боб могут «просто» вычислить общий секретный ключ, посреднику же придётся решать «сложную» задачу.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector