Как вы можете подтвердить право собственности на закрытый ключ, используя открытый ключ и подпись сообщения?

Когда я подписываю сообщение закрытым ключом и получаю подпись сообщения, как я могу, используя соответствующий открытый ключ, проверить, что эта подпись сообщения/транзакции должна быть создана лицом, владеющим закрытым ключом? ключ за соответствующим открытым ключом?

Насколько я понимаю, с парами закрытый/открытый ключ суть технологии в том, что вы не можете реконструировать закрытый ключ из открытого ключа. Итак, как это возможно сделать?

По сути, в чем разница между обратным проектированием закрытого ключа из открытого ключа и проверкой того, что кто-то должен иметь закрытый ключ для создания подписи сообщения, соответствующей открытому ключу? Как одно возможно, но не другое?

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

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

Во-первых, точки на эллиптической кривой образуют абелева группа при операции, которую мы называем «сложением». Это означает, что вы можете делать то, что выглядит как простая алгебра с точками. Вы можете брать баллы $А$ и $В$, добавьте их, чтобы получить точку $С$, и вы сможете заметить, что $А+В==В+А$. Обратите внимание, что мы определяем только операции сложения и вычитания, и мы не можем «умножать» точки или «делить» точки с другими точками.

Во-вторых, отображения целых чисел закрытого ключа в точки являются «аддитивно гомоморфными». Это означает, что если у вас есть закрытые ключи $а$ и $б$, которые сопоставляются с открытыми ключами $А$ и $В$, то открытый ключ $а+б$ будет равно обоим $А+В$ и к $С$.

Преобразование закрытого ключа в открытый ключ — это просто взять закрытый ключ. $а$ и рассчитать открытый ключ $aG$, что означает добавить известную точку $G$ самому себе $а$ раз. Поскольку вычисление этого путем добавления G к самому себе заняло бы целую вечность. $а$ время, есть математические ярлыки доступны. Поскольку эти ярлыки существуют только для быстрого выполнения умножения, а не для возврата назад и определения закрытого ключа из любого результата умножения, это становится односторонним "люк"функция.

Теперь представьте, что у меня есть закрытый ключ $а$ и открытый ключ $A=aG$, а ты бросаешь мне вызов. Вы придумали случайное целое число закрытого ключа $х$, и вы просите меня дать вам ответное целое число $у$ так что вы можете убедиться, что $xA==yG$. Я смогу пройти ваше испытание только в том случае, если буду знать секретный ключ $а$, что позволило бы мне вычислить $у=ха$. Это подтвердит, потому что тогда $xA==xaG==yG$.

То, что я описал выше, имеет два недостатка. Во-первых, как только я пройду испытание, вы сможете легко вычислить мой закрытый ключ. $а$ как $у/х$.

Второй недостаток заключается в том, что мне нужно, чтобы вы бросили мне вызов, а не просто предоставили вам подпись, не взаимодействуя с вами.

Первый недостаток устранен путем включения «ослепляющего фактора», который позволяет мне пройти испытание, не раскрывая свой закрытый ключ. Например, с подписью Шнорра я выбираю случайный закрытый ключ. $к$, показать только $К=кГ$, а затем попросите вас бросить вызов $х$. Затем я создаю значение $у$ так что вы можете убедиться, что $xA==K+yG$. Теперь, после того, как я раскрою $у$ чтобы пройти вызов, вы знаете, что я мог только рассчитать $у$ со знанием моего закрытого ключа $а$, но вы не можете вычислить мой закрытый ключ, не зная моего секретного ослепляющего фактора $к$.

Второй недостаток устраняется с помощью Эвристика Фиата-Шамира создать задачу, используя функцию, служащую "Случайный оракул", что позволяет мне придумать случайный вызов без возможности обмана. В случае схемы подписи ECDSA выход этой функции представляет собой координату x открытого ключа, сопоставленного с определенным вводом. В случае Шнорра подпись, функция представляет собой криптографически безопасный хеш, такой как SHA512/256.

Когда я подписываю сообщение/транзакцию¹ закрытым ключом,
и я получаю подпись сообщения/транзакции¹,

Критически важно, что в этих двух вещах используются разные пары открытого и закрытого ключей. Ничто в остальной части вопроса не касается первой из этих двух вещей. Все сводится к проверке подписи во второй из этих вещей против открытого ключа пары открытый/закрытый ключ, используемой подписывающей стороной в упомянутой второй вещи. Предполагается, что указанный открытый ключ доступен верификатору. Соответствующий закрытый ключ не является.

С парами закрытый/открытый ключ суть технологии в том, что вы не можете реконструировать закрытый ключ из открытого ключа.

Правильный. Это немного больше: с открытым ключом невозможно выполнить то, для чего предназначен закрытый ключ.

В чем разница между реконструированием закрытого ключа из открытого ключа и проверкой того, что кто-то должен иметь закрытый ключ для создания подписи сообщения, соответствующей открытому ключу? Как одно возможно, но не другое?

Подпись работает по этой схеме:

и современный учебник

• $1^n$ кодирует целое число $n$ определение размера ключей. На практике $n$ является фиксированным и общедоступным.
• $(\mathrm{pk},\mathrm{sk})$ представляет собой пару открытый/закрытый ключ, выдаваемую алгоритмом генерации ключа $\mathrm{Общество}$. Предполагается $\mathrm{sk}$ держится в секрете назначенным владельцем пары ключей, который чаще всего является тем, кто запустил $\mathrm{Общество}$.
• $м$ - это сообщение для подписи (произвольная битовая строка, за исключением, возможно, требований к размеру).
• $\сигма$ является подписью сообщения. Он производится из $\mathrm{sk}$ и $м$ по алгоритму подписи $\mathrm{Знак}$.
• $b$ индикатор целостности, который принимает одно из двух значений, Действительный или же Недействителен. Он производится из $\mathrm{пк}$, $м$ и $\сигма$ по алгоритму проверки $\mathrm{Vrfy}$.

Схема подписи верна, когда с вещами по рисунку, $b$ всегда есть Действительный. Это безопасно², когда противники $\mathrm{пк}$ и возможность получения $\sigma_i$ для любой $m_i$ они считают нужным, не могут проявить $(м,\сигма)$ пара с $\mathrm{Vrfy}(\mathrm{pk},m,\sigma)$ Действительный, и $m\ne m_i$ для любой $я$. Есть еще несколько технических деталей³.

Удивительно, что есть правильные и безопасные схемы подписи. Разработка одного из них длилась долго. Но это не более удивительно, чем возможность шифрования с открытым ключом. Если кто-то в основном заботится о понимании использовать подписи, вариант - признать, что такие схемы подписи существуют.

Другой вариант — изучить его. Я предлагаю подпись Шнорра (альт. версия), принцип которого используется в некоторых криптовалютах, является, пожалуй, самым простым и имеет относительно простое количественное снижение безопасности до сложности задачи дискретного логарифма в используемой группе при модели случайного оракула его хэша. Разоблачение этого увеличило бы длину ответа примерно в три раза.

¹ В контексте криптовалюты сообщение может описывать транзакцию.

² По критериям Existentially Unforgeable в соответствии с критериями атаки с выбранным сообщением, часто единственным, обсуждаемым в современном вводном изложении. Существуют и другие полезные критерии безопасности подписи.

³ $\mathrm{Общество}$, $\mathrm{Знак}$, $\mathrm{Vrfy}$ а противники моделируются как вероятностные алгоритмы с полиномиальным временем. Предложения сформулированы для любого фиксированного $(\mathrm{pk},\mathrm{sk})$ парный вывод $\mathrm{Общество}$, и кроме как с незначительной вероятностью $р(п)$, это $р(п)$ такое, что для любого многочлена $Q(n)$ он держит $\displaystyle 0=\lim_{n\to\infty} p(n)\,Q(n)$. На практике $n$ выбирается достаточно высоким, чтобы сделать эту вероятность практически ничтожной.

По сути, в чем разница между обратным проектированием закрытый ключ из открытого ключа и проверка того, что кто-то должен иметь закрытый ключ для создания подписи сообщения, которая соответствует открытый ключ? Как одно возможно, но не другое?

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

public_announcement, подпись = шифровать (sha256 (public_annoucement), private_key)

Любой получатель может вычислить дайджест sha256 для public_annoucement и сравните с расшифровать (sha256 (public_annoucement), public_key)`. Если эти два не совпадают, то либо объявление подделано, либо оно не подписано закрытым ключом, которым оно заявлено.