Криптографія з використанням еліптичних кривих: Швидко вперед, важко назад

Эллиптическая кривая

Эллиптическая кривая, используемая в криптографии, — это множество точек (x, y), удовлетворяющих уравнению y² = x³ + ax + b, вычисленное не над действительными числами, а над конечным полем целых чисел по модулю большого простого p — то есть «кривая» на самом деле является конетным множеством дискретных пар (x, y) плюс одна дополнительная точка в бесконечности, которая действует как элемент-идентичность. То, что делает ее полезной для криптографии, заключается в том, что этот конечный набор точек можно снабдить групповой структурой: существует хорошо определенный способ «сложить» две точки на кривой и получить третью точку также находящуюся на кривой.

Точка додавання: хорда та касатка, над кінцевим полем

Геометрично (найлегше уявити над дійсними числами перед зменшенням mod p): щоб додати дві різні точки P і Q, проведіть пряму лінію через них, знайдіть її третє перетин з кривою та віддзеркаліть цю точку відносно осі x, щоб отримати P + Q. Щоб додати точку самій собі (подвоєння), використовуйте касатку в цій точці замість хорди. На кожному кроці арифметика за модулем p замінює арифметику з дійсними числами, але алгебраїчні формули однакові:

Подвоєння P = (x, y), P ≠ O, y ≠ 0: λ = (3x² + a) / (2y) mod p x³ = λ² - 2x mod p y³ = λ(x - x³) - y mod p

Додавання P=(x1,y1), Q=(x2,y2), x1 ≠ x2: λ = (y2 - y1) / (x2 - x1) mod p x³ = λ² - x1 - x2 mod p y³ = λ(x1 - x³) - y1 mod p Тут ділення означає множення на модульний зворотно-значений, обчислений за допомогою розширеного алгоритму Евкліда. На кожному кроці залишається всередині кінцевого поля, і закритість поля під цими операціями гарантує, що P + Q завжди потрапляє назад на криву, ніколи не виходить з неї.

doubling P = (x, y), P ≠ O, y ≠ 0:
  λ = (3x² + a) / (2y)   mod p
  x3 = λ² − 2x        mod p
  y3 = λ(x − x3) − y   mod p

adding P=(x1,y1), Q=(x2,y2), x1 ≠ x2:
  λ = (y2 − y1) / (x2 − x1)   mod p
  x3 = λ² − x1 − x2         mod p
  y3 = λ(x1 − x3) − y1          mod p

Скалярне множення: легкий напрямок

Приватний ключ є випадковим цілим числом k; відповідний публічний ключ — це точка kG — основа, яка обчислюється ефективно за допомогою подвоєння та додавання: щоб обчислити kG, запишіть k у двійковому вигляді і, переглядаючи біти, повторно множте поточну точку вдвічі та додавайте G кожного разу, коли поточний біт дорівнює 1. Це займає лише приблизно log₂(k) множення та додавання, тому навіть 256-бітовий приватний ключ потребує лише кілька сотень операцій з точками, кожна з яких є просто кількома модульними множеннями — достатньо швидко для запуску на смарт-карті.

double_and_add(k, G):
  R = O                      // point at infinity, the identity
  for bit in binary(k), most significant first:
    R = R + R                // double
    if bit == 1: R = R + G   // add
  return R                   // = kG, computed in O(log k) steps

Почему его обратное преобразование сложно: проблема вычисления дискретного логарифма

При заданном G и публичном ключе Q = kG, восстановление k является проблемой дискретного логарифма эллиптической кривой (ECDLP), и не существует известного алгоритма, который решал бы ее быстрее, чем примерно √p шагов для хорошо подобранной кривой над полем размера p (лучшие общие атаки, например, Pollard's rho, работают за время пропорциональное квадратному корню из порядка группы). Это контрастирует с обычной модульной экспонентой, где аналогичная проблема дискретного логарифма подвержена атакам на подэкспоненциальный индекс-вычисления; групповые эллиптические кривые не имеют известных эквивалентных сокращений, что и объясняет, почему ключ эллиптической кривой длиной 256 бит обеспечивает примерно такую же практическую безопасность, как и ключ RSA длиной 3072 бита — меньшие ключи, более быстрые операции для той же устойчивости к атакам.

Що таке ECC і для чого він використовується

ECDH (Elliptic Curve Diffie-Hellman) дозволяє двома сторонам, які обмінюються лише своїми публічними точками, kG та jG, незалежно обчислювати однакову спільну секретність kjG без передавання k або j, забезпечуючи захист ключового обміну, який лежить в основі майже кожної сучасної HTTPS-зв'язку. ECDSA (Elliptic Curve Digital Signature Algorithm) використовує той самий складний для зворотного розрахунку множення скалярів, щоб власник приватного ключа k міг створити підпис, який будь-хто з публічним ключем kG може перевірити, але ніхто без k не міг би його створити — механізм, що лежить в основі Bitcoin транзакційних підписів та TLS сертифікатів перевірки. Обидва повністю базуються на тій самій асиметрії, яка демонструється в цій симуляції: швидке йти вперед навколо кривої k разів, але неможливо визначити k з того, де ви приземлилися.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Elliptic Curve Cryptography і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.