Цифровая подпись и криптосистемы с ключом общего пользования

Технология работы электронной подписи.

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

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

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 из другого.

Механизм CRC чрезвычайно полезен для проверки файлов, загружаемых из сетевых информационных служб. Если кто-то сообщает мне, что переданная ему через сеть ZD Net утилита вдруг без видимой причины перестает работать, то первым делом я прошу его создать ее архивный файл с помощью программы PKZIP и набрать команду PKZIP -V для просмотра созданного.ZIP файла. Среди прочих параметров он увидит также 32-разрядное значение параметра CRC, рассчитанное программой PKZIP для несжатого файла. Если вычисленное значение параметра CRC для gjkextyyjq утилиты не совпадает со значением для исходного варианта файла, значит, при загрузке его произошла необнаруженная ошибка передачи данных (такое иногда случается).

Можно организовать собственный контроль CRC дл идентификации файлов; для этого потребуется переписать через службу PC Magazine Online файл CRC.COM. CRC.COM - это утилита DOS, которой в качестве входного параметра указывается имя файла. Исходя из содержащейс в нем информации она рассчитывает 32-разрядное значение контроля CRC. В программе использован известный алгоритм расчета параметра CRC-32, применяемый PKZIP и сетевых адаптерах Token-Ring фирмы IBM. Этот алгоритм отличается высоким быстродействием (исходный текст полностью написан на языке ассемблера; производитс буферизация при чтении/записи с диска; прекрасно реализован алгоритм расчета CRC-32 - все это позволяет сократить до минимума объем производимых вычислений) и обработает файлы любого размера. Теперь при пересылке файлов через модем утилита CRC.COM сможет оказать вам неоценимую услугу - дать уверенность, что информаци передана без искажений.

Получив по сети файл CRC.COM, первым делом проверьте сам этот файл, набрав в строке DOS команду:

CRC CRC.COM

Если полученное значение параметра CRC не равно 86C23FA, значит файл следует загрузить снова.

Алгоритмы хэширования

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

Более высокой надежности, чем при контроле CRC, можно достичь при использовании односторонних алгоритмов хэширования; результатом их работы являютс особые "хэшированные" значения. Под термином "односторонние" понимается следующее: имея на входе А, можно без особого труда получить на выходе В, но сделать обратное - то есть из В получить А - невозможно, или, во всяком случае, практически невозможно. Важная отличительная особенность любого хорошего алгоритма хэширования заключается в том, что генерируемые с его помощью значения настолько уникальны и трудноповторимы, что вряд ли кто-то даже с помощью серии суперкомпьютеров Cray и затратив колоссальное количество времени, сможет найти два набора входных данных, имеющих одинаковые значение хэширования. Как правило, эти параметры занимают не менее 128 разряды. Чем больше их длина, тем труднее воспроизвести входной набор данных, то есть найти последовательность, обеспечивающую соответствующий результат.

Среди односторонних алгоритмов хэшировани наибольшей известностью пользуются два из них: алгоритм MD5 (message digest), разработанный профессором Массачусетского технологического института Роном Ривестом (Ron Rivest) (один из авторов популярной криптосистемы с ключом общего пользования RSA), и алгоритм Secure Hash Algorithm (SHA), созданный совместными усилиями Национального института по стандартизации и технологическим разработкам (NIST) и Управления национальной безопасности США (NSA). Результат анализа последовательности входных данных с помощью алгоритма MD5 - 128-разрядный цифровой идентификатор, а при использовании алгоритма SHA - 160-разрядное значение. Учитывая, что пока никому не удалось подобрать ключ ни к одному из названных алгоритмов, можно считать, что восстановление исходных данных по некоторому хэшированному значению, являющемуся результатом работы алгоритма SNA либо по некоторому коэффициенту алгоритма MD5 нереально. Таким образом, если вам отправили какой-то файл и идентификатор, полученный в результате применения к нему алгоритма MD5 или SHA, и если вы выполнили с ним тот же алгоритм хэширования и ваш результат совпал с исходным значением, определенно можно быть уверенным, что принятый вами файл не подвергся искажениям.

Цифровая подпись и криптосистемы с ключом общего пользования

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

Смысл ключа и пароля примерно одинаков. Допустим, Том желает, чтобы Сэм мог отправить ему зашифрованный документ, и оба они не хотели бы рисковать, передава пароль или ключ по линиям связи, так как в этом случае он может быть кем-то перехвачен. Тогда Том может передать Сэму свой ключ общего пользования (схема 1). Используя этот ключ, Сэм шифрует документ и отправляет его Тому. Том дешифрует документ с помощью своего личного ключа. Это единственный ключ, с помощью которого можно восстановить документ, зашифрованный с применением ключа общего пользования, принадлежащего Тому. Тот факт, что ключ общего пользования Тома может стать кому-то известен, не имеет особового значения, потому что он абсолютно бесполезен для расшифровки документа. А личный ключ, известный одному лишь Тому, по открытым линиям связи не передавался; теоретически том хранит его только в собственной памяти и наоборот, работа других криптосистем с ключом общего пользовани строится на обратном принципе: Сэм шифрует документ с помощью своего личного ключа и передает свой ключ общего пользования Тому, с помощью которого тот мог бы расшифровать этот документ. Существующие ныне криптосистемы с ключом общего пользования, такие, например, как система RSA (сокращение, составленное из первых букв фамилий трех создателей этого алгоритма), широко используются.

Как же осуществляется цифровая подпись? Рассмотрим еще один пример. Допустим, Сэм собирается отправить Тому контракт или номер своей кредитной карточки в цифровом виде. Для подтверждения подлинности этих документов Тому необходима цифровая подпись Сема. Сначала Сэм отправляет свой документ. Затем использует алгоритм хэширования для вычисления идентификаторf этого документа, шифрует хэшированное значение с помощью своего личного ключа и отправляет его Тому. Это и есть цифровая подпись Сэма. Том с помощью того же алгоритма хэширования сначала вычисляет идентификатор принятого документа. Затем он расшифровывает значение, которое получил от Сэма, используя предоставленный Сэмом ключ общего пользования. Если два значени хэширования совпали, Том не только узнает, что этот документ подлинный, но и то, что подпись Сэма действительна. Понятно, что проведение коммерческих транзакций по такому сценарию значительно безопаснее, чем с использованием подписи от руки на бумаге, которую можно подделать. А если сведения, передаваемые Сэмом Тому, конфиденциальны (например, содержат номер кредитной карточки), то и их можно зашифровать так, чтобы прочитать их смог только Том.

Поделиться:

Воспользуйтесь поиском по сайту: