Bitcoin in a nutshell — Cryptography / Хабр

Baby-step, giant-step

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

как

, где

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

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

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

для каждого

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

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

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

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

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

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

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

«baby step»

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

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

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

«giant step»

) для

, …, где

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

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

В итоге

мы проверили все точки от до

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

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

(ровно

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

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

Если считать, что поиск в хеш-таблице занимает время временную и пространственную сложность (или , если учесть битовую длину). Это всё ещё экспоненциальное время, но оно намного лучше, чем при атаке перебором.

Ρ полларда

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

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

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

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

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

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

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

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

псевдослучайную последовательность пар

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

. Поскольку

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

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

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

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

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

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

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

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

Поэтому

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

визуальному инструменту, при

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

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

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

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

К случаю нужно относиться немного иначе: уравнения для наклона другое уравнение:

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

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

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

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

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

Что даёт нам

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

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

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

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

как

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

), а

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

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

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

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

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

1. Берём случайное целое , выбранное из (где — это по-прежнему порядок группы).
2. Вычисляем точку (где — базовая точка подгруппы).
3. Вычисляем число (где — это координата ).
4. Если , то выбираем другое и пробуем снова.
5. Вычисляем (где — закрытый ключ Алисы, а — мультипликативная инверсия по модулю ).
6. Если , то выбираем другое и пробуем снова.

Пара

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

над полем

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

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

или

. Если

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

, …,

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

равен

важно брать наименьший, а не случайный делитель. Если мы будем выбирать случайно, то можем получить

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

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

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

, где

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

). Я написал

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

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

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

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

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

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

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

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

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

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

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

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

, что

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

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

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

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

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

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

с помощью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   

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

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

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

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

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

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

Каким будет результат для трёх целых , и ?

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

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