Систематическое кодирование и цифровая подпись

– Что у нея... гм... у нея  внутре  за  лэпэчэ...  Лэпэчэ...  Кэпэдэ, наверное? Что еще за лэпэчэ?

– Лампочка, значит, — сказал старичок,  хихикая  и  потирая  руки.

– Кодируем помаленьку.

Стругацкий А., Стругацкий Б. «Сказка о тройке», повесть, 1968.

Однажды Учитель задал Автору следующий вопрос:

Существуют ли иные методы внесения избыточности на уровне информации, кроме тех, которые изучает теория помехоустойчивого кодирования? Подчеркнув, что речь идет об информационной избыточности, Учитель тем самым дал понять, что вопрос не подразумевает различные способы внесения энергетической избыточности, которые хорошо изучены в теории связи. Ведь помехозащищенность передачи  информации традиционно оценивается посредством порогового значения, которое рассчитывается как отношение энергии сигнала к энергии шума. Известно, что методы теории помехоустойчивого кодирования предлагают альтернативное решение, но позволяют сэкономить энергию.

После короткого раздумья Автор ответил утвердительно, следуя скорее интуиции, а не рациональному знанию. Выслушав ответ Учитель заметил, что это неверное заключение и таких методов не существует.

С течением времени Автор стал подозревать, что непреложность сформулированной выше парадигмы может быть подвергнута сомнению. Прежде всего потому, что электронную цифровую подпись (ЭЦП) разумно рассматривать как некоторый конструктивный способ внесения избыточности, который, однако, в силу специфических функциональных свойств не удается отнести к какому-либо известному классу объектов теории помехоустойчивого кодирования. Если коротко, то любой код имеет сходство с ЭЦП в плане обнаружения ошибок, но при этом не обладает другими уникальными свойствами.

Следует сразу оговориться, что мы не обсуждаем вопросы так называемой «кодовой криптографии», смысл которой заключается в использовании методов теории помехоустойчивого кодирования для конструирования  криптографических примитивов. Справедливости ради отметим, что упомянутая концепция привлекает внимание специалистов потенциальной возможностью разработки криптопримитивов, устойчивых к атакам с применением квантового компьютера. Кроме этого, даже если рассматривать схемы ЭЦП на основе методов теории помехоустойчивого кодирования, а такие известны, например схема Г. А. Кабатянского, Е. А. Крука и Б. Дж. М. Смитса (Kabatianskii G., Krouk E., Smeets B.J.M. A Digital Signature Scheme Based on Random Error-Correcting Codes // Lect. Notes in Comp. Sci. Springer-Verlag. 1997. Vol. 1355. Pp. 161-167), то представленные ниже рассуждения не только сохраняют содержательность, но приобретают дополнительный смысл.

Настоящую заметку следует расценивать как попытку объяснения функционального сходства и отличия методов теории помехоустойчивого кодирования, в частности систематического кодирования, и механизма ЭЦП. 

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

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

При передаче информации по зашумлённому каналу связи возникают ошибки. Природа этих ошибок разнообразна, но важно одно: то, что подают на вход канала может отличаться от того, что получают на выходе. Существенное значение имеет модель канала. Известно множество различных моделей, например модель канала со стираниями, модель канала со вставками и выпадениями символов и так далее, но мы будем опираться на самую известную и простую — модель двоичного симметричного канала без памяти (ДСК). Из названия следует, что мы имеем дело с двоичным алфавитом и арифметикой по модулю два. В этой модели двоичная единица на входе канала может перейти в двоичную единицу на выходе с некоторой вероятностью P и перейти в двоичный ноль с вероятностью 1-P. То же самое касается двоичного нуля. Именно по этой причине такая модель называется симметричной. Известно обобщение этой модели на q-ичные алфавиты, где q — некоторая степень простого числа. Канал не имеет памяти, то есть все предшествующие переходы не оказывают никакого влияния на последующие. Обнаружение и исправление ошибок осуществляется в контексте модели ДСК.

В частности, если известна позиция, на которой произошла ошибка, то в случае ДСК для исправления ошибки достаточно выполнить суммирование по модулю два символа на этой позиции с двоичной единицей. Действительно, если двоичный ноль перешёл в двоичную единицу, то 1+1=0, а если двоичная единица перешла в двоичный ноль, то 0+1=1. В случае q-ичных алфавитов для исправления надо знать не только позицию, но и значение ошибки.

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

Кодированием будем называть способ внесения избыточности, а декодированием — обнаружение и исправление ошибок при помощи внесенной ранее избыточности. В результате кодирования получают кодовое слово. Именно оно и передается по каналу с шумом. По сути, кодовое слово — это информационные символы, к которым в соответствии с некоторым правилом  добавлены дополнительные проверочные символы. Декодирование позволяет определить позиции, на которых произошли ошибки, а для q-ичного алфавита и значение ошибки в соответствующей позиции.

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

Линейность — другое важное свойство кода. Если имеется два различных кодовых слова, принадлежащих конкретному коду, то линейность означает, что поразрядное суммирование этих кодовых слов позволяет получить другое кодовое слово этого же кода. Для простоты будем считать, что код двоичный и суммирование выполняется по модулю два. Иными словами, имеет место замкнутость пространства кодовых слов относительно некоторого линейного оператора. Например, сложения. Существуют также нелинейные коды, для которых это свойство не выполняется.

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

Представленных выше сведений достаточно для сравнения схем ЭЦП и методов систематического кодирования с обнаружением ошибок. 

Для начала следует описать назначение и правила применения ЭЦП. Того, кто формирует ЭЦП будем называть заверителем. Здесь и далее термин «общедоступный ключ» равнозначен англоязычному термину public key.

1. ЭЦП формируется заверителем на основе заданного сообщения и секретного ключа, который известен только заверителю.

2. ЭЦП и сообщение логически связаны и могут передаваться по незащищенным каналам связи или сохраняться в общедоступной долговременной памяти как вместе, так и раздельно.

3. Проверка осуществляется на основе ЭЦП для некоторого сообщения, не обязательно совпадающего с исходным сообщением, а также актуального общедоступного ключа заверителя, подлинность и целостность которого подтверждена при помощи действующего сертификата.

4. В результате проверки ЭЦП формируется значение булевской переменной, которая принимает истинное значение, если подпись валидна (сообщение соответствует тому, для которого ранее была сформирована ЭЦП), в противоположном случае булевская переменная принимает ложное значение.

5. Секретный и общедоступный ключи образуют уникальную пару. Причём секретный ключ известен только заверителю, а общедоступный ключ доставляется по запросу, либо располагается в общедоступной долговременной памяти и может храниться как в составе сертификата, так и отдельно.

6. Сертификат для общедоступного ключа имеет ограниченный срок действия. После истечения этого срока пара ключей выводится из обращения. Как следствие, ЭЦП, сформированная при помощи секретного ключа из этой пары, не гарантирует подлинности и целостности заверенного сообщения.

7. Различают честного и нечестного заверителя. Честный следует установленным правилам формирования подписи, тогда как нечестный ничем не ограничен и действует как злоумышленник.

8. Проверяющий всегда следует установленным правилам проверки подписи.

9. Любой, кто располагает парой ключей способен сформировать ЭЦП для некоторого сообщения, проверить валидность которой может каждый, кто имеет доступ к актуальному общедоступному ключу, подлинность и целостность которого подтверждена при помощи действующего сертификата или иным надежным способом.

10. Злоумышленник стремится изменить/заменить сообщение при неизвестном секретном ключе так, чтобы факт фальсификации не был обнаружен при проверке подписи: заверитель первоначально формирует ЭЦП для заданного сообщения, а злоумышленник изменяет/заменяет ЭЦП и/или заданное сообщение на альтернативные, такие, что при проверке валидности булевская переменная принимает истинное значение.

11. Кроме фальсификации, возможен также подлог: злоумышленник формирует ЭЦП для заданного сообщения при неизвестном секретном ключе, такую, что при проверке на валидность при помощи общедоступного ключа заверителя, от лица которого злоумышленник сформировал эту ЭЦП,  булевская переменная принимает истинное значение.

12. С целью подлога и/или фальсификации злоумышленник может оперировать с отдельной подписью для конкретного сообщения или подписями для несхожих сообщений, а также множеством различных подписей для фиксированного сообщения.

13. Злоумышленник способен навязать заверителю множество различных сообщений и вынудить сформировать для них ЭЦП. Распространенной практикой следует считать доказательство криптостойкости схемы ЭЦП в фокусе модели экзистенциальной фальсификации/подлога при атаке с подбором сообщений. Особенность модели в том, что сообщение изменяется/выбирается произвольным образом, без сохранения смыслового содержания. Криптостойкость трактуется как неспособность злоумышленника при неизвестном секретном ключе, располагающего полиномиально-ограниченными ресурсами, как вычислительными, так и памяти, сформировать ЭЦП для некоторого сообщения с использованием множества заверенных ЭЦП произвольных сообщений, такую, что для сообщения, которое не принадлежит упомянутому множеству, при проверке на валидность булевская переменная принимает истинное значение.

Сформулируем положения, которые позволяют уяснить существующие сходства и отличия.

1. Схемы ЭЦП и коды, обнаруживающие/исправляющие ошибки, используют единый математический аппарат— арифметические операции выполняются в конечном поле или его расширении в границах таких алгебраических структур как мультипликативная группа конечного поля или группа точек эллиптической кривой, если рассматриваются алгебро-геометрические коды и схемы ЭЦП на эллиптических кривых.

2. Избыточность, которая в схеме ЭЦП задействована в процедуре проверки подписи на валидность, отделена от информационных символов.

3. Систематический код и схема ЭЦП позволяют обнаруживать ошибки. 

4. Для систематического кода вероятность ошибки определяется природой канала связи, тогда как в случае ЭЦП ошибка имеет в том числе и рукотворный характер.

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

6. В схемах ЭЦП если и существует ограничение на число информационных символов (зависит от используемой хеш-функции), то оно не сказывается на практическом применении, однако число избыточных символов фиксировано.

7. Вероятность фальсификации ЭЦП зависит от вероятности коллизии хеш-функции. Коллизии всегда существуют и их можно отыскать, однако асимптотическая оценка трудоемкости (числа опробований) универсального метода нахождения коллизий для произвольной хеш-функций не превышает корня квадратного из мощности пространства значений. Как правило, такая мощность не меньше 2²⁵⁶.

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

9. Систематический код в рамках обнаруживающей способности гарантирует такую услугу как целостность, но не обеспечивает подлинности.

10. Схема ЭЦП гарантирует как подлинность, так и целостность.

11. Свойство линейности для схем ЭЦП не выполняется. Если бы такое свойство выполнялось, то ЭЦП была бы уязвима в плане фальсификации/подлога.

12. Как правило систематические блоковые коды имеют фиксированную длину блока (в символах алфавита). Параметры, выбранные с привязкой к оценке вероятности ошибочного декодирования, а именно число информационных и проверочных символов, также фиксированы.

13. В схемах ЭЦП не предусмотрен заключительный вывод аналогичный  отказу от декодирования.

14. Схемы ЭЦП не привязаны к конкретной модели канала, а ориентированы на модель экзистенциальной фальсификации/подлога, где одновременно возможны трансформация символов, а также вставки и выпадения.

Допустим, что перечисленного выше достаточно для формулировки выводов.

С точки зрения избыточности и функциональной содержательности схемы ЭЦП выделяются на фоне всех остальных криптографических инструментов. Методы, обеспечивающие конфиденциальность, а именно алгоритмы блочного зашифрования/расшифрования, безызбыточны по своей природе. Что касается кода аутентификации сообщения (message authentication code) в контексте модели условной подлинности (conditional authenticity), когда отправитель и получатель разделяют общий секретный ключ и доверяют друг другу, то тут сходство с обнаруживающим ошибки систематическим блоковым кодом не вызывает сомнений. Однако, в отличие от ЭЦП, код аутентификации сообщения не гарантирует безусловной подлинности (unconditional authenticity).

Прежде всего очевидно, что так же как систематический блоковый код схема ЭЦП обеспечивает обнаружение ошибок. Однако, поскольку не накладывается заметных ограничений на число информационных символов при фиксированной избыточности, можно предположить, что при прочих равных вероятность фальсификации/подлога для схем ЭЦП существенно ниже вероятности ошибочного декодирования. Для более точных рассуждений необходимо привлечение адекватного математического аппарата, однако это не согласуется с ранее заявленным намерением обойтись упрощенной манерой изложения.

Возможно, что корректное сравнение лежит в плоскости нелинейных кодов, ведь как указано в п.11, линейность  для схем ЭЦП — это паразитное свойство существенно повышающее риск фальсификации/подлога.

Никаких других сходств обнаружить не удаётся, а выявленные отличия имеют принципиальный характер. Основное заключается в том, что систематический блоковый код не является инструментов асимметричной криптографии и поэтому не гарантирует подлинности. Вообще при обсуждении кодов, обнаруживающих/исправляющих ошибки, подобная функциональность даже вскользь не упоминается. Это и понятно, методы теории помехоустойчивого кодирования имеют отношение к несколько иным задачам. Но при этом кодирование и формирование ЭЦП безусловно относятся к способам внесения избыточности. А декодирование и проверка ЭЦП используют эту избыточность для заключительного вывода в рамках установленного решающего правила.

Итак, существуют ли иные методы внесения избыточности на уровне информации, кроме тех, которые изучает теория помехоустойчивого кодирования? Да, существуют. К таким методам можно отнести схемы формирования/проверки ЭЦП.