Почему невозможно получить закрытый ключ из открытого ключа?

Насколько я понимаю, уравнение для открытого ключа определяется так:

K = k * G

Где K — открытый ключ, k — закрытый ключ, а G — точка-генератор.

  • Является ли G константой? (насколько я читал, это константа.)
  • Если да, то почему нельзя просто сделать K/G = k?
  • Если это не так, как он создается из закрытого ключа?

Ответы (3)

Насколько я понял, уравнение для открытого ключа определяется так K = k * G: K — открытый ключ, k — закрытый ключ, а G — точка-генератор.

Правильно.

Теперь мой первый вопрос: является ли G константой? (насколько я читал, это константа)

Это. Это точка с координатами (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424). Вы можете проверить, что эти координаты удовлетворяют уравнению кривой : Y^2 = X^3 + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663).

И если да, то как нельзя просто сделать K/G = k?

Ответ прост: мы не знаем эффективного способа «деления» эллиптических кривых (это называется проблемой дискретного логарифмирования ), и предполагается, что такой способ не может быть найден. Самый известный алгоритм для этой конкретной кривой требует около 2128 итераций , что невероятно много.

Вы должны знать, что то, *что k * Gвы пишете, не является обычным умножением (что это вообще может означать для очков?). Это довольно сложная операция , и люди выяснили ее полезные свойства, которые чем-то похожи на умножение (она образует циклическую группу , поэтому используется тот же символ). Но никто так и не нашел способа выполнить обратную операцию, и это стало основой для криптографии на эллиптических кривых .

Это многое прояснило для меня. Спасибо за объяснение и ссылки!

Математикам нравятся их аналогии, иногда эти аналогии могут быть полезными, но в равной степени они могут сбивать с толку, особенно новичков в какой-либо области.

В математике «группа» состоит из набора элементов и оператора, удовлетворяющего некоторым требованиям. Оператор должен быть ассоциативным, должен существовать единичный элемент, и для каждого элемента должен существовать обратный элемент относительно оператора.

Некоторые группы записываются по аналогии сложения, то есть групповой оператор представлен знаком «+», а единичный элемент представлен «0». Другие группы записываются по аналогии с умножением, то есть групповой оператор записывается как операция умножения (например, «*», «.» или вообще ничего), а элемент идентичности представлен «1». Эллиптические кривые традиционно записываются по аналогии сложения.

Мы можем вообразить многократное применение группового оператора к k копиям G. Если группа записывается по аналогии сложения, то это аналогично умножению, если группа записывается по аналогии с умножением, то это аналогично возведению в степень.

So k * Gотносится не к обычному умножению, а к операции, которая в определенном смысле аналогична умножению.

Вы можете наивно подумать, что это займет время, пропорциональное k, но благодаря ассоциативности мы можем вычислить его за время, пропорциональное логарифму k. Таким образом, мы можем быстро вычислить k * Gдаже для очень больших k.

Однако отменить операцию не так просто. Эта проблема известна как «проблема дискретного логарифмирования эллиптических кривых», и самые известные методы имеют сложность, пропорциональную примерно квадратному корню из числа элементов в группе.

Почему это называется «проблемой дискретного логарифмирования эллиптических кривых», хотя это больше похоже на деление, чем на логарифмирование в обозначениях, обычно используемых для эллиптических кривых? потому что это вариант аналогичной задачи, изучаемой для группы, которая традиционно записывается по аналогии с умножением.

«Другие группы записываются по аналогии с умножением, то есть . Эллиптические кривые традиционно записываются по аналогии со сложением». Вероятно, там было съедено несколько слов. Также я предлагаю использовать полное название «дискретный логарифм», а не аббревиатуру «дискретный логарифм», поскольку для непосвященного не обязательно очевидно, что означает этот «лог».

k = K/G несколько вводит в заблуждение. Во многих отношениях лучше писать k = K * G^-1. Это подчеркивает, что в «деление» вовлечены две операции: умножение и обратное (Кроме того, это облегчает признание того, что K * G^-1 и G^-1 * K являются разными понятиями и что существование Необходимо показать, что существует G^-1. Здесь это не так важно, потому что умножение на эллиптических кривых является абелевым и всегда имеет обратное, но это соображения, которые вы должны иметь в виду при работе с группами и кольцами в целом. )

Математика на эллиптических кривых имеет место в абстрактной группе, а не в системе действительных чисел, и использование записи действительных чисел поощряет вводящую в заблуждение интуицию (а в абстрактной алгебре косая черта используется для частных групп, а не для деления элементов группы). Тот факт, что найти обратное в математике эллиптических кривых сложно, в первую очередь делает ее криптографической системой. В противном случае любой, у кого был открытый ключ, мог тривиально инвертировать шифрование. «Криптографическая система» почти по определению относится к системе с некоторой операцией, в которой найти a*b значительно проще, чем найти a^-1.

(Существуют способы вычисления K * G^-1 без явного вычисления G^-1, но они по-прежнему так же трудны или труднее, как и вычисление G^-1.)

А если нет, то как он создается из закрытого ключа?

Хм? Вы только что привели уравнение для открытого ключа: K = k * G.

Кроме того, я думаю, что вы должны указать, что вы говорите о secp256k1, в теле вашего текста, а не просто как тег. Можно предположить, что это биткойн SE, но лучше, чтобы это было ясно.

Я нахожу это объяснение более запутанным, если честно. G^-1 — это не то, что вы можете вычислить. Каков будет его тип? Не точка, потому что тогда K G^-1 была бы точкой^2, которой не существует. И не скаляр, потому что тогда K G^-1 была бы точкой. Вам нужно будет ввести концепцию «перевернутых точек», которой, насколько я знаю, не существует, а также она не связана с тем, как K/G фактически вычисляется в таких алгоритмах, как ро Полларда... которые фактически принимают K и G в качестве входных данных - не просто G - а выход k.
@PieterWuille: Вы ошибочно применяете реальную арифметику к абстрактной алгебре, как предостерегает Accumulation. «Тип» продукта над абстрактной группой имеет единицы, которые являются произведением единиц двух входов, но размерность не так проста. Например, трехмерное векторное перекрестное произведение имеет трехмерное значение, как и оба входа, а векторное скалярное произведение дает скаляр независимо от размерности входных данных. Другой пример: квадратная матрица имеет обратную той же размерности, что и она сама, и это не создает проблем при умножении обращенной матрицы на векторы-столбцы.
Ответ буквально гласит: «... но они все еще так же сложны или сложнее, как найти G^-1». Насколько мне известно, это ложное утверждение, так как не существует известного способа вычисления G^-1 (даже игнорируя вопрос о том, каким будет его тип). Алгоритмы вычисления дискретного логарифма (= деление двух групповых элементов) принимают на вход два групповых элемента. Они не вычисляют обратное значение одного, а затем умножают его на другое. Вы, конечно, могли бы определить «инверсию элемента группы по отношению к скалярному умножению» как некоторый абстрактный объект, но это не то, как вы его вычисляете.
Здесь больше неправильного. Обратное, о котором мы говорим, - это обратное скалярное умножение (число, умноженное на групповой элемент), а не обратное относительно самой групповой операции (групповой элемент плюс групповой элемент). Последнее существует для каждого элемента любой группы (включая неабелевы группы). Однако первое, если вы хотите его определить, определенно не существует для каждого элемента абелевой группы; он существует для каждого ненулевого элемента в secp, потому что он циклический с простым порядком, но в общем случае он не будет существовать для элементов с немаксимальным порядком в группе.
Почему невозможно получить закрытый ключ из открытого ключа?
СпросиСетьПолитика конфиденциальности1y, 0v