Віталік Бутерін через в Блог Віталіка Бутеріна
Це дзеркало поста на https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Тригер попередження: мат.
Одним із ключових криптографічних примітивів, що стоять за різними конструкціями, включаючи детерміновані порогові сигнатури, zk-SNARK та інші простіші форми доказів із нульовим знанням, є парування еліптичних кривих. Поєднання еліптичних кривих (або «білінійні карти») є нещодавнім доповненням до 30-річної історії використання еліптичних кривих для криптографічних програм, включаючи шифрування та цифрові підписи; спарювання вводить форму «зашифрованого множення», значно розширюючи можливості протоколів на основі еліптичних кривих. Метою цієї статті буде детально розглянути поєднання еліптичних кривих і пояснити загальну схему їх роботи.
Ви не очікуєте, що ви все зрозумієте тут, коли прочитаєте вперше чи навіть удесяте; це справді важко. Але, сподіваюся, ця стаття дасть вам хоча б трохи уявлення про те, що відбувається під капотом.
Еліптичні криві самі по собі є дуже нетривіальною темою для розуміння, і ця стаття загалом передбачає, що ви знаєте, як вони працюють; якщо ви ні, я рекомендую цю статтю тут як грунтовку: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Як короткий підсумок, криптографія еліптичної кривої включає математичні об’єкти, які називаються «точками» (це буквально двовимірні точки з (�,�) координатами), зі спеціальними формулами для їх додавання та віднімання (тобто для обчислення координат �= �+�), і ви також можете помножити точку на ціле число (тобто �⋅�=�+�+…+�, хоча є набагато швидший спосіб обчислити це, якщо � велике).
Ось як графічно виглядає додавання точок.
Існує спеціальна точка, яка називається «точка на нескінченності» (�), еквівалент нуля в точковій арифметиці; завжди так, що �+�=�. Крім того, крива має "порядок“; існує таке число �, що �⋅�=� для будь-якого � (і, звичайно, �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5 і так далі). Існує також деяка загальновизнана «генеруюча точка» �, яка в певному сенсі представляє число 1. Теоретично будь-яка точка на кривій (крім �) може бути �; все, що має значення, це те, що � є стандартизованим.
Парування йде ще далі, оскільки дозволяє перевіряти певні типи складніших рівнянь на точках еліптичної кривої — наприклад, якщо �=�⋅�,�=�⋅� і �=�⋅�, ви можете перевірити, чи не �⋅�=�, маючи лише �,� та � як вхідні дані. Це може здатися, що фундаментальні гарантії безпеки еліптичних кривих порушуються, оскільки інформація про � просочується просто через знання P, але виявляється, що витік дуже обмежений — зокрема, проблема Діффі Хеллмана, що приймає рішення легко, але обчислювальна проблема Діффі Хеллмана (знаючи � та � у наведеному вище прикладі, обчислення �=�⋅�⋅�) і проблема дискретного логарифма (відновлення � з �) залишаються обчислювально нездійсненними (принаймні, якщо вони були раніше).
Третій спосіб подивитися на те, що роблять пари, і той, який, мабуть, є найбільш яскравим для більшості випадків використання, про які ми говоримо, полягає в тому, що ви розглядаєте точки еліптичної кривої як односторонні зашифровані числа (тобто ���� ���(�)=�⋅�=�), тоді як традиційна математика еліптичної кривої дозволяє перевірити лінійний обмеження на числа (наприклад, якщо �=�⋅�,�=�⋅� і �=�⋅�, перевірка 5⋅�+7⋅�=11⋅� є насправді перевіряючи, що 5⋅�+7⋅�=11⋅�), пари дозволяють перевірити квадратичний обмеження (наприклад, перевірка �(�,�)⋅�(�,�⋅5)=1 є насправді перевіряючи, що �⋅�+5=0). І переходу до квадратичного достатньо, щоб ми могли працювати з детермінованими пороговими сигнатурами, програмами квадратичної арифметики та всіма іншими хорошими речами.
Тепер, що це за смішний оператор �(�,�), який ми представили вище? Це парування. Математики також іноді називають це a білінійна карта; слово «білінійний» тут в основному означає, що він задовольняє обмеженням:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Зверніть увагу, що + і ⋅ можуть бути довільними операторами; коли ви створюєте нові типи математичних об’єктів, абстрактній алгебрі байдуже, як стоять + і ⋅ певний, якщо вони узгоджені звичайними способами, наприклад. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) і (�⋅�)+(�⋅�)=(�+�)⋅�.
Якби �, �, � і � були простими номера, то зробити просте поєднання легко: ми можемо зробити �(�,�)=2��. Тоді ми можемо побачити:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Це білінійно!
Однак такі прості пари не підходять для криптографії, оскільки об’єкти, з якими вони працюють, є простими цілими числами, і їх занадто легко проаналізувати; цілі числа полегшують ділення, обчислення логарифмів і виконання різноманітних інших обчислень; прості цілі числа не мають поняття «відкритий ключ» або «одностороння функція». Крім того, за допомогою описаного вище поєднання ви можете повернутися назад – знаючи � і знаючи �(�,�), ви можете просто обчислити ділення та логарифм, щоб визначити �. Ми хочемо, щоб математичні об’єкти були максимально наближені до «чорних ящиків», де можна додавати, віднімати, множити та ділити, але більше нічого не робити. Тут з’являються еліптичні криві та поєднання еліптичних кривих.
Виявляється, що можна створити білінійну карту над точками еліптичної кривої, тобто придумати функцію �(�,�), де вхідні дані � і � є точками еліптичної кривої, а вихідні дані – це те, що називається (��)12 (принаймні в конкретному випадку, який ми тут розглянемо; особливості відрізняються залежно від деталей кривої, про це пізніше), але математика, що стоїть за цим, досить складна.
Спочатку розглянемо прості поля та поля розширення. Гарна еліптична крива на зображенні раніше в цій публікації виглядає так, лише якщо припустити, що рівняння кривої визначено за допомогою звичайних дійсних чисел. Однак, якщо ми дійсно використовуємо звичайні дійсні числа в криптографії, тоді ви можете використовувати логарифми, щоб «повернутися назад», і все зламається; крім того, кількість простору, необхідного для фактичного зберігання та представлення чисел, може довільно зростати. Отже, замість цього ми використовуємо числа в a первинне поле.
Просте поле складається з набору чисел 0,1,2…�−1, де � є простим числом, а різні операції визначаються таким чином:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
В основному всі обчислення виконуються за модулем � (див тут для вступу в модульну математику). Поділ — окремий випадок; зазвичай 32 не є цілим числом, і тут ми хочемо мати справу лише з цілими числами, тому ми натомість намагаємося знайти таке число �, щоб �⋅2=3, де ⋅, звичайно, відноситься до модульного множення, як визначено вище. Завдяки Маленька теорема Ферма, трюк піднесення до степеня, показаний вище, виконує роботу, але є також швидший спосіб зробити це, використовуючи Розширений алгоритм Евкліда. Припустимо �=7; ось кілька прикладів:
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
Якщо ви пограєте з таким типом математики, ви помітите, що він абсолютно послідовний і задовольняє всі звичайні правила. Останні два приклади вище показують, як (�/�)⋅�=�; ви також можете побачити, що (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, і всі інші шкільні алгебраїчні тотожності, які ви знаєте і любите, продовжуються також вірно. На еліптичних кривих насправді точки та рівняння зазвичай обчислюються в простих полях.
Тепер поговоримо про це поля розширення. Можливо, ви вже бачили поле розширення раніше; найпоширенішим прикладом, який ви зустрічаєте в підручниках з математики, є поле комплексних чисел, де поле дійсних чисел «розширено» додатковим елементом −1=�. По суті, поля розширення працюють, беручи існуюче поле, потім «винаходячи» новий елемент і визначаючи зв’язок між цим елементом і існуючими елементами (у цьому випадку �2+1=0), переконавшись, що це рівняння не виконується для будь-якого числа, яке знаходиться у вихідному полі, і дивлячись на набір усіх лінійних комбінацій елементів вихідного поля та нового елемента, який ви щойно створили.
Ми також можемо робити розширення простих полів; наприклад, ми можемо розширити просте поле mod7, яке ми описали вище, за допомогою �, а потім ми можемо зробити:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Цей останній результат може бути трохи важко зрозуміти; там сталося те, що ми спочатку розклали добуток на 4�⋅2+4�⋅�, що дає 8�−4, а потім, оскільки ми працюємо в математиці mod7, це стало �+3. Щоб розділити, робимо:
�/�:(�⋅�(�2−2)) % �
Зауважте, що показник степеня для маленької теореми Ферма тепер дорівнює �2 замість �, хоча знову ж таки, якщо ми хочемо бути ефективнішими, ми можемо замість цього розширити розширений алгоритм Евкліда, щоб виконати цю роботу. Зверніть увагу, що ��2−1=1 для будь-якого � в цьому полі, тому ми називаємо ��2−1 “порядком мультиплікативної групи в полі”.
З дійсними числами Основна теорема алгебри гарантує, що квадратичне розширення, яке ми називаємо комплексними числами, є «повним» — ви не можете розширити його далі, тому що для будь-якого математичного відношення (принаймні, будь-якого математичного відношення, визначеного алгебраїчною формулою), яке ви можете знайти між якимось новим елементом � і існуючих комплексних чисел, можна придумати принаймні одне комплексне число, яке вже задовольняє цей зв’язок. Однак із простими полями ми не маємо цієї проблеми, тому ми можемо піти далі та зробити кубічні розширення (де математичний зв’язок між деяким новим елементом � та існуючими елементами поля є кубічним рівнянням, тому 1,� і �2 є кубічними рівняннями усі лінійно незалежні одне від одного), розширення вищого порядку, розширення розширень тощо. І саме на цих видах надзаряджених модульних комплексних чисел будуються пари еліптичних кривих.
Для тих, хто хоче побачити точну математику, залучену до написання всіх цих операцій у коді, тут реалізовано прості поля та розширення полів: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Тепер перейдемо до поєднання еліптичних кривих. Поєднання еліптичних кривих (точніше, конкретна форма поєднання, яке ми досліджуватимемо тут; існують також інші типи поєднання, хоча їх логіка досить схожа) є відображенням �2×�1→��, де:
- �1 – це еліптична крива, де точки задовольняють рівняння виду �2=�3+�, і де обидві координати є елементами �� (тобто вони є простими числами, за винятком того, що арифметика виконується за модулем деякого простого числа)
- �2 є еліптичною кривою, де точки задовольняють таке ж рівняння, як �1, за винятком того, що координати є елементами (��)12 (тобто це надзаряджені комплексні числа, про які ми говорили вище; ми визначаємо нове “магічне число” ” �, який визначається поліномом 12-го степеня, наприклад �12−18⋅�6+82=0)
- �� — це тип об’єкта, до якого потрапляє результат еліптичної кривої. На кривих, які ми розглядаємо, �� дорівнює (��)12 (те саме надзаряджене комплексне число, яке використовується в �2)
Основною властивістю, якій він повинен задовольняти, є білінійність, що в цьому контексті означає, що:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Є ще два важливі критерії:
- Ефективна обчислюваність (наприклад, ми можемо зробити легке поєднання, просто взявши дискретні логарифми всіх точок і помноживши їх разом, але це так само складно з точки зору обчислень, як спочатку зламати криптографію еліптичної кривої, тому це не зараховується)
- Невиродженість (звичайно, ви можете просто визначити �(�,�)=1, але це не дуже корисне поєднання)
То як нам це зробити?
Математика, чому працюють функції парування, досить складна і включає в себе досить складну алгебру, що виходить навіть за рамки того, що ми бачили досі, але я надаю схему. Перш за все, нам потрібно визначити поняття a спліттер, в основному альтернативний спосіб представлення функцій на точках еліптичної кривої. Дільник функції в основному підраховує нулі та нескінченності функції. Щоб зрозуміти, що це означає, розглянемо кілька прикладів. Зафіксуємо деяку точку ��=(��,��) і розглянемо таку функцію:
�(�,�)=�−��
Дільник дорівнює [�]+[−�]−2⋅[�] (квадратні дужки використовуються для позначення того факту, що ми маємо на увазі наявність точки � в множині нулів і нескінченностей функції, а не сама точка P; [�]+[�] є НЕ те саме, що [�+�]). Аргументація така:
- Функція дорівнює нулю в �, оскільки � is ��, тому �−��=0
- Функція дорівнює нулю в −�, оскільки −� і � мають однакову � координату
- Функція прямує до нескінченності, коли � прямує до нескінченності, тому ми говоримо, що функція дорівнює нескінченності в �. Існує технічна причина, чому цю нескінченність потрібно рахувати двічі, тому � додається з «кратністю» −2 (негативною, оскільки це нескінченність, а не нуль, два через цей подвійний рахунок).
Технічна причина приблизно така: оскільки рівняння кривої таке: �3=�2+�,� йде до нескінченності “в 1.5 рази швидше”, ніж �, щоб �2 не відставав від �3; отже, якщо лінійна функція включає лише �, то вона представляється як нескінченність кратності 2, але якщо вона включає �, то вона представляється як нескінченність кратності 3.
Тепер розглянемо «лінійну функцію»:
��+��+�=0
Де �, � і � ретельно вибрано так, що лінія проходить через точки � і �. Через те, як працює додавання еліптичної кривої (див. діаграму вгорі), це також означає, що воно проходить через −�−�. І він зростає до нескінченності залежно від � і �, тому дільник стає [�]+[�]+[−�−�]−3⋅[�].
Ми знаємо, що кожна «раціональна функція» (тобто функція, визначена лише за допомогою кінцевої кількості операцій +,−,⋅ та / над координатами точки) однозначно відповідає деякому дільнику, аж до множення на константу (тобто. якщо дві функції � і � мають однаковий дільник, то �=�⋅� для деякої константи �).
Для будь-яких двох функцій � і � дільник �⋅� дорівнює дільнику � плюс дільнику � (у підручниках з математики ви побачите (�⋅�)=(�)+(�)), так, наприклад, якщо �(�,�)=��−�, то (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � і −� «враховуються втричі», щоб врахувати той факт, що �3 наближається до 0 у цих точках «утричі швидше» в певному математичному сенсі.
Зауважте, що існує теорема, яка стверджує, що якщо ви «знімете квадратні дужки» з дільника функції, сума точок має становити �([�]+[�]+[−�−�]−3⋅[ �] явно підходить, оскільки �+�−�−�−3⋅�=�), і будь-який дільник, який має цю властивість, є дільником функції.
Тепер ми готові поглянути на поєднання Тейт. Розглянемо такі функції, визначені через їхні дільники:
- (��)=�⋅[�]−�⋅[�], де � порядок �1, тобто. �⋅�=� для будь-якого �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Тепер розглянемо продукт ��⋅��⋅��. Дільник це:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
Що акуратно спрощує:
�⋅[�+�]−�⋅[�]
Зверніть увагу, що цей дільник має точно такий самий формат, як дільник для �� і �� вище. Отже, ��⋅��⋅��=��+�.
Тепер ми запроваджуємо процедуру, яка називається кроком «кінцевого піднесення до степеня», де ми беремо результат наших функцій (��,�� тощо) і підносимо його до степеня �=(�12−1)/�, де �12−1 є порядком мультиплікативної групи в (��)12 (тобто для будь-який �∈(��)12,�(�12−1)=1). Зауважте, що якщо застосувати це піднесення до будь-якого результату, який має вже було зведено до степеня �, ви отримаєте піднесення до степеня �12−1, тому результат перетворюється на 1. Отже, після остаточного піднесення до степеня �� скорочується, і ми отримуємо ���⋅���=( ��+�)�. Для вас є якась дволінійність.
Тепер, якщо ви хочете створити функцію, яка є білінійною за обома аргументами, вам потрібно вдатися до моторошнішої математики, де замість того, щоб брати �� значення безпосередньо, ви берете �� із спліттер, і саме звідси походить повне «поєднання Тейт». Щоб довести ще кілька результатів, вам доведеться мати справу з такими поняттями, як «лінійна еквівалентність» і «взаємність Вейля», і звідти починається «кроляча нора». Ви можете знайти більше матеріалів для читання про все це тут та тут.
Для реалізації модифікованої версії парування Тейта, що називається оптимальним паруванням Ате, дивіться тут. Код реалізує Алгоритм Міллера, який необхідний для фактичного обчислення ��.
Зауважте, що той факт, що подібні пари можливі, є певною мірою змішаним благословенням: з одного боку, це означає, що всі протоколи, які ми можемо виконувати з парами, стають можливими, але це також означає, що ми повинні бути більш обережними щодо еліптичних кривих ми використовуємо.
Кожна еліптична крива має значення, яке називається an ступінь вбудовування; по суті, найменше � таке, що ��−1 є кратним � (де � є простим числом, яке використовується для поля, а � є порядком кривої). У полях вище, �=12, і в полях, які використовуються для традиційного ECC (тобто, де ми не дбаємо про пари), ступінь вбудованості часто надзвичайно великий, аж до того, що обчислення пар неможливо обчислити; однак, якщо ми не будемо обережні, ми можемо створити поля, де �=4 або навіть 1.
Якщо �=1, то проблему «дискретного логарифма» для еліптичних кривих (по суті, відновлення �, знаючи лише точку �=�⋅�, проблему, яку вам потрібно вирішити, щоб “зламати” закритий ключ еліптичної кривої) можна зменшити. у подібну математичну задачу над ��, де проблема стає набагато легшою (це називається Атака MOV); використання кривих зі ступенем вбудовування 12 або вище гарантує, що це скорочення або недоступне, або що вирішення проблеми дискретного журналу над результатами сполучення є принаймні таким же складним, як відновлення закритого ключа з відкритого ключа «звичайним способом» (тобто. обчислювально неможливо). Не турбуйтесь; усі параметри стандартної кривої були ретельно перевірені на цю проблему.
Незабаром очікуйте математичне пояснення того, як працюють zk-SNARK.
Особлива подяка Крістіану Райтвіснеру, Аріелю Габізону (з Zcash) і Альфреду Менезесу за перегляд і внесення виправлень.
- Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
- PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
- PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
- ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
- PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
- BlockOffsets. Модернізація екологічної компенсаційної власності. Доступ тут.
- джерело: Інформація про дані Платона.