Що таке Elliptic Curve Discrete Logarithm Problem (ECDLP)?

Elliptic Curve Discrete Logarithm Problem (ECDLP) це завдання знайти секретне число k, коли відомі лише дві точки на еліптичній кривій, G і P, де P дорівнює k помноженому на G. Перейти від k до P легко і швидко, а от відновити k з P важко, ніби намагаєшся розділити змішаний смузі. Смачно, але важко повернути назад.

Міф

Поширена думка полягає в тому, що Elliptic Curve Discrete Logarithm Problem (ECDLP) тотожна класичній задачі дискретного логарифму і будь-який старий короткий шлях її зламає. Не зовсім так: криві додають особливі властивості, і для цього випадку невідома жодна субекспоненційна атака в криптографії.

Як працює Elliptic Curve Discrete Logarithm Problem (ECDLP)

Ось послідовність, яку ви насправді використовуєте при створенні пари ключів або перевірці транзакції на кривій.

Крок 1: Ви обираєте секретне число k і публічну базову точку G на безпечній кривій.
Крок 2: Ви обчислюєте P як k помножене на G за допомогою повторного додавання точок. Уявіть G як стрибок, а P як місце приземлення після k стрибків.
Крок 3: Усі бачать G і P. Виклик полягає в тому, щоб відновити k з цих значень. Це і є складна задача.
Крок 4: Відомі атаки мають складність, пропорційну квадратному кореню розміру групи, що для реальних кривих залишається астрономічно повільним.
Крок 5: Цей односторонній механізм забезпечує ефективність криптографії на еліптичних кривих (ECC) при коротких ключах.

Коротко: легко в одному напрямку, надзвичайно важко у зворотньому.

Чому має значення Elliptic Curve Discrete Logarithm Problem (ECDLP)

Чому вам це важливо? Тому що воно зачіпає ваші монети і входи частіше, ніж ви думаєте.

Перевага: Дозволяє блокчейнам використовувати коротші ключі при однаковому рівні захисту, що економить байти і пришвидшує перевірку.
Перспектива: Bitcoin, Ethereum і багато гаманців покладаються на цифрові підписи, які спираються на цю стійкість для безпеки коштів.
Де зустрічається: Ви з цим стикаєтеся щоразу, коли вузол перевіряє транзакцію, dapp підтверджує повідомлення або мультипідписний гаманець підписує.

Порада

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

Ключові характеристики Elliptic Curve Discrete Logarithm Problem (ECDLP)

Що вирізняє її, стисло:

Складно: За заданих G і P знаходження k є обчислювально важким для стандартних кривих і розмірів.
Компактність: Сильний захист при коротших розмірах ключів у порівнянні з RSA, що дозволяє тримати блоки і повідомлення менш громіздкими.
Квантове: Великий квантовий комп'ютер з алгоритмом Шора може зламати це, тому ведеться робота над постквантовими рішеннями.

Варіанти

Проблема зустрічається в різних сімействах кривих. Та сама ідея, різні математичні особливості.

Prime: Криві над простими полями часто використовуються в Bitcoin і Ethereum.
Binary: Криві над двійковими полями з'являються в деяких протоколах і в апаратно орієнтованих налаштуваннях.
Edwards: Криві стилю Едвардса дають швидку безпечну арифметику і компактні формули.
Koblitz: Спеціальні криві, які дозволяють прискорення, але потребують ретельного вибору параметрів.

Нагадування

Безпека залежить від вибору надійних кривих і правильної реалізації. Злом однієї слабкої конфігурації не означає поразки всіх кривих, а помилки з одноразовими числами в підписах можуть призводити до витоку секретів навіть якщо складна задача залишається складною.

Приклад

Коли гаманець Bitcoin отримує публічний ключ, множачи приватне число k на базову точку G кривої, ви можете широко поширювати публічний ключ, оскільки відновлення k з цього публічного ключа обчислювально недосяжне.

Цікавинка

Дослідники вирішували тестові задачі на крихітних кривих з групами близько ста біт, часто з великими командами і місяцями обчислень, тоді як популярні криві типу secp256k1 знаходяться далеко за межами такої зони комфорту. Також можливий майбутній квантовий стрибок, який може змінити ситуацію, через що постквантові підписи привертають значну увагу.

Підсумок

Уявіть це як односторонню математику, яка дозволяє ланцюгам більше покладатися на математику замість посередників, Rolex зустрічає Reddit.

Elliptic Curve Discrete Logarithm Problem (ECDLP)