Цифровая подпись: принципы работы

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

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

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

целостности цифровых данных до рассмотрения проекта государственного стандарта США - Digital Signature Standard, а также основные правила оформления цифровой подписи.

Контрольные суммы

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

Checkssum = Total % (MaxVal + 1)

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

Допустим, документ, содержимое которого предстоит верифицировать, представляет собой следующую последовательность величин, длиной 10 байт:

36 211 163 4 109 192 58 247 47 92

Если контрольная сумма 1 байт величина, то максимальное число, которое она может содержать, равно 255 Для приведенного выше документа сумма всех его чисел равно

1159. Таким образом, 8-разрядов контрольной суммы будут содержать остаток от деления числа 1159 на 256, то есть 135. Если контрольная сумма, рассчитанная отправителем документа, равнялась, скажем, 246, а после получения она имеет значение 135, значит, информация подверглась изменению. Метод контрольных сумм - это наиболее простая форма цифровой идентификации (digital fingerprint); то есть величина, полученная в результате подсчета содержимого некоторых других данных, изменяется при коррекции данных, на основе которых он получен. Использование алгоритма контрольных сумм началось еще на заре вычислительной техники и до сих пор он является базовым при проверке на ошибки в некоторых версиях широко распространенного протокола передачи данных XMODEM.

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

И что еще хуже - можно изменить отдельные числа в документе и подогнать остальные таким образом, чтобы обеспечить прежнее значение контрольной суммы. При использовании для контрольных сумм 8-разрядной переменной вероятность того, что контрольные суммы двух совершенно случайно выбранных последовательностей данных будут одинаковы, равна 1/256. При увеличении длины переменной под контрольную сумму до 16 или 32 разрядов, вероятность совпадений уменьшается, однако этот механизм все равно слишком чувствителен к возможным ошибкам, чтобы обеспечить высокую степень доверия к представленным данным.

Контроль CRC

Более совершенный способ цифровой идентификации некоторой последовательности данных - это вычисление контрольного значения ее циклического избыточного кода (cyclic redundancy check - CRC). Алгоритм контроля CRC уже в течение длительного времени широко используется в системах сетевых адаптеров, контроллеров жесткого диска и других устройств для проверки идентичности входной и выходной информации.

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

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

f(x) = 4x3 + x2 + 7

Для выполнения расчетов контроля CRC полином, представляющий байт данных со значением 85 (8-разрядный двоичный эквивалент которого - 01010101) выглядит так:

0x7 + 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 0x1 + 1x0

или просто

x6 + x4 + x2 + 1

Ключевым принципом вычислений для механизма CRC является то, что операции умножения и деления этих полиномов выполняются точно так же, как с обычными числами. Если некоторый "магический" полином (коэффициенты которого получены в соответствии с используемым алгоритмом CRC) разделить на полином, представляющий какую-то последовательность данных, то в результате получается полином-частное и полином-остаток. Второе из этих значений служит основой для создания контрольного параметра CRC. Так же, как и для контрольных сумм, параметром CRC не требуется много места (обычно их длина составляет 16 или 32 разряда); однако по сравнению с ними, надежность обнаружения небольших изменений входной информации теперь значительно выше. Если в некотором огромном блоке данных лишь один разряд стал другим, то и контрольный параметр CRC со 100-процентной вероятностью также будет иметь другое значение. Если же изменятся два разряда, то вероятность обнаружения ошибки при длине параметра CRC в 16-разрядов, составляет более 99,99%. В отличие от контрольных сумм метод CRC сможет распознать всякие фокусы с перестановкой двух байт либо с добавлением 1 к одному из них и вычитанием 1 из другого.