Бегом по ECDSA
Сегодня мы попробуем разобраться в ECDSA
Уравнение ECDSA
Криптография на основе эллиптических кривых основана на уравнении вида:
Первое, что вы заметите, это то, что есть модуль и что «у» возведено в квадрат (не забывайте, что это уравнение кривой на графике). Это означает, что для любой координаты x (не забывайте также, что мы работаем только с целыми числами) у вас будет два значения y и что кривая симметрична относительно оси X. Модуль является простым числом и гарантирует, что все значения находятся в пределах нашего диапазона 160 бит, и позволяет использовать «модульный квадратный корень» и «модульную мультипликативную обратную» математику, которые упрощают вычисления. Поскольку у нас есть модуль (p) , это означает, что возможные значения y^2 находятся между 0 и p-1, что дает нам общее количество p возможных значений. Однако, поскольку мы имеем дело с целыми числами, только меньшее подмножество этих значений будет «идеальным квадратом» (квадратное значение двух целых чисел), что дает нам N возможных точек на кривой, где N < p (где N — число совершенных квадратов между 0 и p)
Поскольку каждый x дает две точки (положительные и отрицательные значения квадратного корня из y^2), это означает, что существует N/2 возможных координат x, которые являются допустимыми и дают точку на кривой. Итак, эта эллиптическая кривая имеет конечное число точек, и все это из-за целочисленных вычислений и модуля
Подведем итоги, прежде чем двигаться дальше. Уравнение ECDSA дает нам кривую с конечным числом допустимых точек на ней (N), потому что ось Y ограничена модулем (p) и должна быть идеальным квадратом (y^2) с симметрией по оси X. Всего у нас есть N/2 возможных допустимых координат x, не забывая при этом, что N < p
Добавление точки
Еще одна вещь, которую вам нужно знать об эллиптических кривых — это понятие «сложения точек». Оно определяется как добавление одной точки P к другой точке Q, что приведет к такой точке S, что если вы проведете линию от P до Q, то она пересечет кривую в третьей точке R, которая является отрицательным значением S (помните, что кривая симметрична относительно оси X). В этом случае мы определяем R = -S для представления симметричной точки R на оси X. Это легче проиллюстрировать с помощью изображения, поэтому посмотрите на изображение выше
Таким образом, вы можете видеть кривую формы y^2 = x^3 + ax + b (где a = -4 и b = 0), которая симметрична относительно оси X, и где P+Q симметрична по оси Х к точке R, которая является третьим пересечением линии, идущей из P в Q.
Перемножение точек
Таким же образом, если вы делаете P + P, то это будет симметричная точка R, которая является пересечением линии, которая является касательной к точке P. И P + P + P является дополнением между результирующей точкой P + P с точкой P, поскольку P + P + P можно записать как (P + P) + P. Это определяет «умножение точек», где k * P — это добавление точки P к самой себе k раз. Посмотрите на два изображения выше для примеров умножения точек
Здесь вы можете видеть две эллиптические кривые и точку P, из которой вы проводите касательную, а она пересекает кривую с третьей точкой, и ее симметричная точка — 2P, затем оттуда вы проводите линию из 2P и P, и она будет пересекать кривую, а симметричная точка — 3P. и т. д., вы можете продолжать делать это для умножения точек. Вы также можете уже догадаться, почему вам нужно взять симметричную точку R при выполнении сложения, иначе многократные сложения одной и той же точки всегда будут давать одну и ту же прямую и те же три пересечения
Функция ловушка
Одной из особенностей этого умножения точек является то, что если у вас есть точка R = k*P, где вы знаете R и знаете P, то нет никакого способа узнать, каково значение «k». Поскольку нет вычитания или деления точек, вы не можете просто решить k = R/P. Кроме того, поскольку вы можете добавить миллионы точек, вы просто окажетесь в другой точке кривой, и у вас не будет возможности узнать, как вы туда попали. Вы не можете отменить эту операцию, и вы не можете найти значение «k», которое было умножено на вашу точку P, чтобы получить результирующую точку R
Этот момент, когда вы не можете найти множитель, даже если вы знаете исходную и конечную точки, является всей основой безопасностью алгоритма ECDSA, и этот принцип называется «Trap Door Function»
Алгоритм ECDSA
Теперь, когда мы разобрались с «основами», давайте поговорим о реальном алгоритме подписи ECDSA
Для ECDSA вам сначала нужно знать параметры вашей кривой, это a, b, p, N и G. Вы уже знаете, что «a» и «b» — это параметры функции кривой (y^2 = x^3 + ax + b), что «p» — это простой модуль, а «N» — это количество точек кривой, но есть также «G», который необходим для ECDSA, и он представляет собой «точку отсчета». Контрольной точкой может быть любая точка на кривой
Эти параметры кривой важны, и, не зная их, вы, очевидно, не сможете подписать или проверить подпись. Да, проверка подписи заключается не только в знании открытого ключа, вам также необходимо знать параметры кривой, из которых получен этот открытый ключ. NIST (Национальный институт стандартов и технологий) и SECG (Группа стандартов эффективной криптографии) предлагают готовые и стандартизированные параметры кривых, которые, как известно, безопасны и эффективны
Итак, прежде всего, у вас будет закрытый и открытый ключи. Закрытый ключ — это случайное число (тоже 160 бит), которое сгенерировано, а открытый ключ — это точка на кривой, сгенерированная из точки умножения G с закрытым ключом. Мы устанавливаем «dA» в качестве закрытого ключа (случайное число) и «Qa» в качестве открытого ключа (точка), поэтому мы имеем: Qa = dA * G (где G — точка отсчета в параметрах кривой)
Создание подписи
Подпись составляет 40 байт и представлена двумя значениями по 20 байт каждое, первое из которых называется R, а второе называется S, поэтому пара (R, S) вместе и есть ваша ECDSA подпись. Теперь, когда вы уже можете создать эти два значения, чтобы подписать файл, вы должны сгенерировать случайное значение «k» (из 20 байтов) и использовать умножение точек для вычисления точки P = k * G. Значение x этой точки будет представлять «R». Поскольку точка на кривой P представлена ее координатами (x, y) (каждая из которых имеет длину 20 байтов), вам нужно только значение «x» (20 байтов) для подписи, и это значение будет называться «R». Теперь все, что вам нужно, это значение «S»
Чтобы вычислить S, вы должны сделать SHA1-хэш сообщения, это даст вам 20-байтовое значение, которое вы будете рассматривать как очень большое целое число, и мы назовем его «z». Теперь вы можете рассчитать S, используя уравнение:
Обратите внимание на k^-1, который является «модульной мультипликативной инверсией» k, это в основном инверсия k, но так как мы имеем дело с целыми числами, то это невозможно, так что это число такое, что (k^-1 * k ) mod p равно 1. И снова напомню, что k — это случайное число, используемое для генерации R, z — это хэш сообщения, которое нужно подписать, dA — закрытый ключ, а R — это x координата k*G (где G — исходная точка параметров кривой).
Проверка подписи
Теперь, когда у нас есть подпись, мы хотим ее проверить. Это тоже довольно просто, и для этого вам нужен только публичный ключ (и параметры кривой, конечно). Вы используете это уравнение для вычисления точки P:
Если координата x точки P равна R, то это означает, что подпись действительна, иначе нет
Довольно просто, да? Теперь давайте посмотрим, почему и как, а для проверки этого потребуется немного математики:
P = S^-1*z*G + S^-1 * R * dA*G = S^-1 (z + dA* R) * G
Но x координата P должна совпадать с R, а R является х координатой k*G, что означает:
Мы можем упростить, удалив G, что дает нам:
Инвертируя k и S, мы получаем:
И это уравнение, используемое для создания подписи, так что оно совпадает, и именно по этой причине вы можете проверить подпись с помощью того уравнения выше
Безопасность ECDSA
Вы можете заметить, что нам нужны как «k» (случайное число), так и «dA» (закрытый ключ) для вычисления S, но вам нужны только R и Qa (открытый ключ) для проверки подписи. А поскольку R=k*G и Qa=dA*G и из-за функции лазейки в умножении точек ECDSA (объяснено тут), мы не можем вычислить dA или k, зная Qa и R, это делает алгоритм ECDSA безопасным. Невозможно найти закрытые ключи и невозможно подделать подпись, не зная закрытого ключа
Важность случайного K
Давайте теперь обсудим, как и почему подписи ECDSA, которые Sony использовала в Playstation 3, были ошибочными, и как они позволили хакерам получить доступ к закрытому ключу ECDSA PS3
Итак, вы помните уравнения, необходимые для создания подписи: R = k*G и S= k^-1(z + dA*R) mod p. Сила этого уравнения в том, что у вас есть одно уравнение с двумя неизвестные (k и dA), поэтому невозможно определить ни один из них
Однако безопасность алгоритма основана на его реализации, и важно убедиться, что «k» генерируется случайным образом и что никто не может его угадать, вычислить или использовать атаку по времени или любой другой тип атаки чтобы найти случайное значение 'k'. Но Sony допустила огромную ошибку в своей реализации, они везде использовали одно и то же значение для «k», а это означает, что если у вас есть две подписи с одинаковым k, то они обе будут иметь одинаковое значение R, а это значит, что вы можете вычислить k, используя две подписи S двух файлов с хэшами z и z' и подписями S и S' соответственно:
S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)
Поэтому: k = (z – z’) / (S – S’)
Как только вы знаете k, уравнение для S становится уравнением с одним неизвестным и затем легко решается для dA:
Как только вы узнаете секретный ключ dA, вы сможете подписывать свои файлы, и PS3 будет распознавать их как подлинные файлы, подписанные Sony. Вот почему важно убедиться, что случайное число, используемое для генерации подписи, действительно является «криптографически случайным». Это также причина, по которой невозможно иметь кастомную прошивку выше 3.56, просто потому, что начиная с версии 3.56 Sony исправила реализацию алгоритма ECDSA и использовала новые ключи, для которых теперь невозможно найти закрытый ключ
Другим примером этой проблемы является то, что некоторые биткойн-клиенты использовали некриптографический генератор случайных чисел (в некоторых браузерах и на некоторых клиентах Android), что заставляло их подписывать свои транзакции одним и тем же значением «k», и злоумышленники могли найти закрытый ключ биткойн-кошелька пользователя и украсть оттуда средства
Это показывает важность использования действительно случайного числа каждый раз, когда вы делаете подпись, поскольку вы будете раскрывать закрытый ключ, если значение R пары подписей (R, S) одинаково для двух разных подписей
Алгоритм ECDSA очень безопасен, для него невозможно найти закрытый ключ, если, конечно, реализация выполнена правильно. Если бы был способ найти закрытый ключ, то безопасность каждого компьютера, веб-сайта, системы могла бы быть скомпрометирована, поскольку многие системы полагаются на ECDSA для обеспечения своей безопасности
Надеюсь статья была интересной и понятной!