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

Сериал состоит из четырех частей; каждая часть использует концепции, обнаруженные в предыдущих частях:

  1. Магия эллиптических кривых
  2. Магия эллиптических кривых в сочетании с конечными полями [вы здесь]
  3. Использование магии эллиптических кривых для подписи и проверки сообщений
  4. Реализация ECDSA на Python с использованием нулевых зависимостей

Основы конечных полей

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

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

Вы слышали об операции modulus? Если вы программист, вы, вероятно, так и сделали. Это всего лишь напоминание о делении, и в языках программирования оно обычно выражается оператором % (или mod). Например:

2 по модулю 11 = 2
10 по модулю 11 = 10
11 по модулю 11 = 0
13 по модулю 11 = 2
14 по модулю 11 = 3

Если мы попробуем числа от 0 до 33 mod 11, мы получим следующие числа:
0, 1, 2 , 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0

Он работает как часы. We can call it a finite field of order 11.

Нам нужно знать всего четыре свойства:

  1. Порядок умножения не имеет значения.
     a*b*c mod n то же самое, что и (a mod n) * (b mod n) * (c mod n) mod n, то же самое as (a*b по модулю n) * c по модулю n.
    Пример:
    6 * 7 * 8 mod 11 = 336 mod 11 = 6,
    то же, что и:     (6 * 7 по модулю 11) * 8 по модулю 11 = (42 по модулю 11) * 9 по модулю 11 = 9 * 8 по модулю 11 = 72 по модулю 11 = 6
  2. Отрицательное число mod n то же, что и n-(|отрицательное число| mod n). Примеры:
    1) -4 по модулю 11 = 11-(4 по модулю 11) = 11–4 = 7
    2) -7 по модулю 11     = 11 — (7 по модулю 11) = 11–7 = 4
    3)-9 по модулю 11 = 11 — (9 по модулю 11) = 11–9 = 2
    4) -2 по модулю 11 = 11 — (2 по модулю 11) = 11–2 = 9
    5)-13 по модулю 11 = 11 — (13 по модулю 11) = 11–2 = 9
  3. Мультипликативный обратный: для любого a существует число b, например, a*b mod n = 1.
    Если a * b mod 11 = 1,     a называется мультипликативной инверсией b по модулю n и наоборот: b называется мультипликативной инверсией a по модулю n.
    Примеры:
    1) 5 * x mod 11 = 1. Давайте попробуйте значения для x одно за другим, и мы обнаружим, что x = 9,потому что 5 * 9 = 45, 45 mod 11 = 1. Итак, 9 > мультипликативное обратное число 5 по модулю 11.
    2) 7 * x mod 11 = 1. Давайте попробуем наш брутфорс еще раз, и мы узнаем x = 8. 8 — мультипликативное обратное число 7 по модулю 11.
    3) 10 * x mod 11 = 1. x = 10. Итак, 10 — это мультипликативное обратное число 10 по модулю 11.

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

4. Деление — это та же операция, что и умножение на обратный мультипликатив! Последнее и самое важное свойство:

Итак, когда нам нужно иметь дело с делением по модулю n, мы можем легко его вычислить.
Давайте посмотрим на пример:

Вот оно! Теперь мы знаем, как работать с конечными полями «алгеброй».

Эллиптические кривые над конечными полями

Здесь это становится менее очевидным и немного трудным для понимания. Но именно так эллиптические кривые используются в криптографии. Нам нужно сделать именно то, что сказано в заголовке: положить нашу эллиптическую кривую над конечным полем.

Итак, вот как изменится наша формула:

Все то же самое, что и в исходной формуле, но теперь обе части уравнения меньше модуля p.

Давайте используем эллиптическую кривую со следующей конфигурацией для наших примеров:

  • a = 0
  • b = 7
  • p = 11

Давайте найдем все точки на этой кривой, запустив этот код:

Это javascript, поэтому вы можете запустить его даже в браузере. Но это не обязательно.

Вот результат:
(2, 2), (2, 9), (3, 1), (3, 10), (4, 4), (4, 7), (5 , 0), (5,11), (6, 5), (6, 6), (7, 3), (7, 8)

Посмотрим, как это выглядит на координатной сетке:

Попробуем a=0, b=7, p=23:

Ни на что не похоже. Нет различимой формы.

Но! Оказывается, она сохраняет все свойства и формулы «исходной» эллиптической кривой!

Итак, теперь у нас есть эллиптическая кривая, которая не похожа на эллиптическую кривую. Но! Он имеет конечный набор точек и, что наиболее важно, работает как эллиптическая кривая.

Нам нужно немного изменить наши формулы из Части 1 по модулю p:

  1. Умножение точки на -1:
    Если у нас есть точка A(x, y), мы можем легко получить -A путем умножения его координаты y на -1 по модулю p.
    Пример:
    1) -1 * A(2, 2) → -A(2, -2 по модулю 11) = -A(2, 9)
    2)-1 * A(2, 9) → -A (2, -9 по модулю 11) = -A(2, 2)
    3)-1 * A(6, 5) → -A(6, -5 по модулю 11) = -A(6, 6)
    4)-1 * A(6, 6) → -A(6, -6 mod 11) = -A(6, 5)
  2. Сложение двух точек вместе:

3. Добавление точки к себе:

Если вы еще не понимаете концепцию мультипликативной инверсии, пожалуйста, вернитесь к Основам конечных полей выше и еще раз проверьте третье предложение.

Вот и все! Время практиковаться!

В наших примерах мы будем использовать эллиптическую кривую с a=0, b=7 и порядком p=11.
Возьмем точку C(7, 8) и рассчитайте 2C:

Теперь мы можем легко вычислить 4C:

Теперь давайте посчитаем 4C — C, что по сути равно 3C = 4C + (-C):

Затем добавим 3C = C + 2C и посмотрим, будет ли результат таким же:

Вы видите волшебство? Алгебра здесь работает отлично!

Одно очень важное свойство: каждая точка на кривой имеет свой порядок n! Он работает как по модулю. Например, если порядок n точки C равен 12, это означает, что 12C= 0 (точка не существует),13*C = C, 16*C = 4C, 27 *С = 3С. Это свойство предопределено для точки.

Вы можете потренироваться и убедиться, что это работает.

На самом деле порядок нашей точки C равен 12. Предлагаю вам задание: попробуйте вычислить 8C, сложив 4C + 4C. Затем попробуйте добавить 8C + 8C. Вы получите 16C, что будет равно 4C.

Работает как часы:

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

Резюме

  • Все формулы работают нормально. Мы по-прежнему можем вычислить любое целое число x * Point. Нам все еще нужно примерно log2(x) операций!
  • Эллиптические кривые теперь имеют конечное множество точек.
  • Точки теперь имеют собственный порядок n, поэтому они имеют тенденцию повторяться, как в часах.
  • Теперь для определения эллиптической кривой нам нужны три переменные: a, b и p. p называется порядком эллиптической кривой.

Как узнать, какие a, b и p использовать? Это стандартизировано! Там много стандартов.

Что используют Биткойн и Эфириум?

Они используют стандартизированную эллиптическую кривую, называемую secp256k1. Он имеет следующие переменные:

  • a=0
  • b=7
  • p=115792089237316195423570985008687907853269984665640564039457584007908834671663

Довольно большое число! Я думаю, вы начинаете догадываться, почему эллиптические кривые так хороши для криптографии.

Теперь, когда мы знаем все самое важное, давайте применим это в криптографии в следующей части!

Следующая часть: Использование магии эллиптических кривых для подписи и проверки сообщений

Пишите мне:
[email protected]
https://t.me/exemak
Михаил Караваев