Цифровая подпись
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: бесплатные дипломы скачать, пяточные шпори
| Добавил(а) на сайт: Куняев.
1
Цифровая подпись
Цифровая подпись: принципы работы
Контрольные суммы, контроль 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 из другого.
Механизм CRC чрезвычайно полезен для проверки файлов, загружаемых из сетевых
информационных служб. Если кто-то сообщает мне, что переданная ему через сеть ZD
Net утилита вдруг без видимой причины перестает работать, то первым делом я
прошу его создать ее архивный файл с помощью программы PKZIP и набрать команду
PKZIP -V для просмотра созданного . ZIP файла. Среди прочих параметров он увидит
также 32-разрядное значение параметра CRC, рассчитанное программой PKZIP для
несжатого файла. Если вычисленное значение параметра CRC для gjkextyyjq утилиты
не совпадает
со значением для исходного варианта файла, значит, при загрузке его произошла
необнаруженная ошибка передачи данных (такое иногда случается).
Можно организовать собственный контроль CRC для идентификации файлов; для этого
потребуется переписать через службу PC Magazine Online файл CRC. COM. (Он
находится в библиотеке Tutor форума Utilities/Tips службы ZD Net/CompuServe и в
файле V15N07. ZIP (на сервере по адресу http://www. pcmag. 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, и если вы выполнили с ним тот же алгоритм хэширования и ваш результат
совпал с исходным значением, определенно можно быть уверенным, что принятый вами
файл не подвергся искажениям.
Алгоритм MD5
Терминология
В данном случае "word" является 32-х битной величиной, "byte" - 8-ми битная
величина. Последовательность бит должна интерпретироваться таким же способом что
и последовательность байт, где каждая последовательная группа из восьми бит
интерпретируется как байт с старшим (наиболее значащим) битом каждого байта
следующим в последовательности первым. Подобно последовательности байт должна
интерпретироваться и последовательность 32-битных слов.
Запись x_i означает "x sub i" (т. е. х с индексом i). Если некоторое выражение
используется как индекс, то оно берется в фигурные скобки, например x_{i+1}.
Символ " ^ " используется для операций возведения в степень, т. е. x^i следует
понимать как х в степени i.
Символ "+" обозначает операцию сложения слов (т. е. сложение по модулю 2^32).
Далее x
циклического сдвига (вращения) предыдущего значения х на s бит влево. not(x) -
поразрядная операция отрицания , x v y - поразрядное ИЛИ(OR) операндов x и y , x
xor y – поразрядное исключающее ИЛИ(XOR) операндов x и y , и xy - поразрядное
И(AND) операндов x и y.
Краткое описание алгоритма MD5
Вначале допускаем, что имеем на входе сообщение из b-бит, и что мы желаем найти
Message Digest этой последовательности бит. Число b является произвольным
неотрицательным целым; b может быть равным нулю, оно не обязательно должно быть
множителем 8, и оно может быть произвольно большим. Представим
последовательность бит сообщения как:
m0 m1 m2 . . . . . . m{b-1}
Следующие пять этапов выполняются для подсчета Message Digest сообщения.
Этап 1. Присоединение заполняющих (дополнительных) битов.
Сообщение расширяется так, чтобы его длина (в битах) совпадала с 448, по модулю
512. Дополнение всегда выполняется, даже если длина сообщения - уже совпадает с
448 по модулю 512. Дополнение выполняется следующим образом: одиночный "1" бит
добавляется к сообщению, и далее "0" биты добавляются так что длина в битах
заполняемого сообщения соответствует 448 по модулю 512. В общем случае, минимум
один бит и максимум 512 бит добавляется.
Этап 2. Добавление длины
64-битное представление входной последовательности b (длина сообщения перед
расширением дополнительными битами) присоединяется к результату предыдущего
этапа. Маловероятно, что длина b будет больше, чем 264 поэтому и используется
64-х разрядная величина для хранения длины b. (Эти биты добавляются как два 32-х
разрядных слова, младшее заносится первым).
В этом месте окончательное сообщение(после выполнения первого и второго этапов)
имеет длину, кратную 512 битам, т. е. сообщение имеет длину, которая точно
кратна 16-ти словам. Последовательность М[0 . . . . N-1] является словами
окончательного сообщения, где N кратно 16.
Этап 3. Инициализация MD буфера.
Буфер на 4-е слова (A, B, C, D) используется для подсчета Message Digest. Каждое
из A, B, C, D является 32-х битным регистром. Эти регистры инициализируются
следующими шестнадцатиричными значениями, где первым следует самый младший байт:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Программисты из RSA Data Security, Inc. , дабы не утруждать себя и остальных
людей по поводу происхождения этих чисел, просто назвали их магическими
константами.
Этап 4. Обработка сообщения в блоках по 16 слов.
Сначала определяются четыре вспомагательных функции каждая из которых имеет на
входе три 32-битных слова и производит одно 32-битное слово на выходе.
F(X, Y, Z) = XY v not(X) Z
G(X, Y, Z) = XZ v Y not(Z)
H(X, Y, Z) = X xor Y xor Z
I(X, Y, Z) = Y xor (X v not(Z))
В каждой битовой позиции функция F действует как условный опреатор : если X то Y
иначе Z. Функция F могла бы определяться с использованием операцию + вместо v,
так как выражение XY and not(X)Z никогда не будет иметь 1 в одинаковых битовых
позициях.
Если биты X, Y и Z независимы и несмещены(??), то каждый бит после выполнения
F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для
нахождения выходного значения от входных битов X, Y и Z, тем же способом, что
если биты X, Y и Z независимы и несмещены, то каждый бит после выполнения
вышеуказанных функций будет независим и несмещен. Обратите внимание, что функция
H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией
контроля четности входных значений). Далее на этом этапе происходит четыре
цикла, в которых происходит трансформация битов сообщения при помощи
вышеуказанных
функций, функций циклического сдвига, и таблицы константных значений.
Этап 5. Вывод
В результате выполнения предыдущих этапов Message Digest производит на выходе
числа A, B, C, D, общая длина которых 128 бит.
Резюме
Алгоритм получает на входе сообщение произвольной длины и после обработки на
выходе получаем 128-битный "отпечаток" или "Message Digest". Предполагается, что
вычислительная трудоемкость нахождения двух сообщений, имеющих одинаковые
Message Digest очень велика. MD5 алгоритм предназначен для приложений,
формирующих цифровые сигнатуры, в которых большой файл должен быть "сжат"
безопасным способом перед зашифровкой открытым (или секретным)ключом в некоторой
криптосистеме с открытым ключом, такой как RSA.
MD5 алгоритм является расширением алгоритма MD4.
MD5 алгоритм полностью разработан для быстрой работы на 32-х разрядных машинах.
К тому же алгоритм не требует каких-либо больших подстановочных таблиц;
обеспечивается компактная кодировка.
MD5 Message Digest алгоритм прост в использовании, и обеспечивает получение
128-ми битного "отпечатка" или Message Digest сообщения произвольной длины.
Предполагается, что сложность нахождения двух сообщений, которые произведут
одинаковые Message Digest является порядка 2 в 64 степени операций, и сложность
построения сообщения по некоторому известному Message Digest является порядка 2
в 128 степени операций.
Примеры исходного кода для реализации MD5.
Макросы
F, G, H, I
Данные макросы определяют четыре вспомогательных функции, каждая из которых
имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.
#define F(x, y, z) (((x) & (y)) ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) (~z)))
В каждой битовой позиции функция F действует как условный оператор : если X то Y
иначе Z. Если биты X, Y и Z независимы и несмещены (??), то каждый бит после
выполнения F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для
нахождения выходного значения от входных битов X, Y и Z, тем же способом, что
если
биты X, Y и Z независимы и несмещены, то каждый бит после выполнения
вышеуказанных функций будет независим и несмещен. Следует обратить внимание, что
функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е.
функцией контроля четности входных значений).
FF, GG, HH, II
Данные макросы определяют четыре вспомагательных функции, которые на входе
получают семь 32-х разрядных параметров, а на выходе получаем одну 32-х
разрядную величину.
Эти фунции используются в функции Transform() для битовых преобразований.
Функции работают следующим образом:
1. В выходной параметр записывается сумма соответствующей функции (для FF() это
F(), для GG() это G(), для HH() это H(), для II() это I()) от 2-го, 3-го и 4-го
параметров с 5-м и 7-м параметрами.
2. Производится циклический сдвиг влево выходного параметра на количество бит,
указанное в 6-м входном параметре.
3. Производится приращение выходного параметра на величину, указанную во 2-м
входном параметре.
#define FF(a, b, c, d, x, s, ac) /
{(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define GG(a, b, c, d, x, s, ac) /
{(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define HH(a, b, c, d, x, s, ac) /
{(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define II(a, b, c, d, x, s, ac) /
{(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
Сразу можно отметить, что входные параметры вышеуказанных функций представляют
собой следующие значения:
register UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; Как видно
регистровые переменные a, b, c, d типа UINT4 инициализируются значениями
временного буфера buf[4] содержащемся в основной структуре Message Digest
MD5_CTX. Пятый параметр x всегда инициализируется символом из входного буфера
in[64] также находящемся в структуре MD5_CTX.
Параметр s равен одной из шестнадцати констант, определенных в функции
Transform().
А вот самый последний параметр ас равен одной из 64-х "таинственных констант".
Разработчики из RSA Data Security, Inc. предлагают вам расположить эти константы
в "little-endian" порядке, расшифровать при помощи DES и вы получите ТАЙНЫЕ
ПОСЛАНИЯ. (вот только DESовый ключик они не указали).
ROTATE_LEFT
Данный макрос сдвигает x влево на n бит.
#define ROTATE_LEFT(x, n) (((x) < (n)) ((x) >> (32-(n))))
Если n > 32, то результат равен нулю.
Функции
void MD5Init ( MD5_CTX *mdContext)
Функция MD5Init(MD5_CTX *mdContext) выполняет инициализацию некоторых полей
структуры Message Digest MD5_CTX В качестве параметра функция получает указатель
на структуру MD5_CTX.
{
/* Обнуление полей, которые будут содержать длину сообщения */
mdContext->i[0] = mdContext->i[1] = (UINT4)0;
/* Загрузка магических констант инициализации. */
mdContext->buf[0] = (UINT4)0x67452301L;
mdContext->buf[1] = (UINT4)0xefcdab89L;
mdContext->buf[2] = (UINT4)0x98badcfeL;
mdContext->buf[3] = (UINT4)0x10325476L;
}
void MD5Update (register MD5_CTX *mdContext, unsigned char *inBuf, unsigned int
inLen)
Данная функция обрабатывает содержимое структуры MD5_CTX.
В качестве параметров функция получает:
Указатель mdContext на структуру MD5_CTX;
Cимвольный буфер inBuf[], который содержит символы исходного сообщения, чей
Message Digest мы подсчитываем; Длину inLen передаваемого буфера.
Вначале подсчитывается целочисленная величина mdi:
mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
Эта величина равна длине сообщения в байтах по модулю 64. Длина сообщения в
битах хранится в структуре MD5_CTX в буфере i[0. . 1].
Длина сообщения в битах заносится в буфер i[0. . 1] следующим образом:
mdContext->i[0] += ((UINT4)inLen
mdContext->i[1] += ((UINT4)inLen >> 29);
Следующий участок кода выполняет следующие действия:
while (inLen--)
{
/* добавляем новый символ в буфер, инкрементируя mdi */
mdContext->in[mdi++] = *inBuf++;
/* Если необходимо выполняем преобразование */
if (mdi == 0x40)
{
for (i = 0, ii = 0; i < 16; i++, ii += 4)>
in[i] = (((UINT4)mdContext->in[ii+3])
(((UINT4)mdContext->in[ii+2])
(((UINT4)mdContext->in[ii+1])
((UINT4)mdContext->in[ii]);
Transform (mdContext->buf, in);
mdi = 0;
}
}
Пока уменьшаемая на 1 длина переданного в функцию сообщения не станет равной
нулю выполняем следующие действия:
Заносим новый символ из входного буфера функции в 64-х байтный буфер структуры
MD5_CTX, увеличивая при этом переменную mdi на 1. Если mdi равна 64, то
преобразуем
однобайтные символы буфера in[] структуры MD5_CTX в 4-х байтные величины типа
UINT4, заносим в промежуточный буфер на 16 величин типа UINT4, и далее передаем
функции Transform(). Присваиваем переменной mdi 0.
void MD5Final (MD5_CTX *mdContext)
Функция завершает вычисление Message Digest и заносит полученное значение в
структуре MD5_CTX в символьный буфер digest[0. . . 15].
Входным параметром функции является указатель на структуру MD5_CTX.
Основные моменты:
Расширение сообщения дополнительными заполняющими символами из таблицы PADDING[]
/* Подсчет длины сообщения в байтах по модулю 64 */
mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
/* Расширить до 56 по модулю 64 */
padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi);>
MD5Update(mdContext, PADDING, padLen);
Присоединение битов длины и вызов функции Transform().
in[14] = mdContext->i[0];
in[15] = mdContext->i[1];
for (i = 0, ii = 0; i < 14; i++, ii += 4)>
in[i] = (((UINT4)mdContext->in[ii+3])
(((UINT4)mdContext->in[ii+2])
(((UINT4)mdContext->in[ii+1])
((UINT4)mdContext->in[ii]);
Transform (mdContext->buf, in);
Сохранение буфера в digest(т. е. получение окончательного Message Digest):
for (i = 0, ii = 0; i < 4; i++, ii += 4)>
{
mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF);
mdContext->digest[ii+1] = (unsigned char)((mdContext->buf[i] >> 8) & 0xFF);
mdContext->digest[ii+2] = (unsigned char)((mdContext->buf[i] >> 16) & 0xFF);
mdContext->digest[ii+3] = (unsigned char)((mdContext->buf[i] >> 24) & 0xFF);
}
void Transform(register UINT4 *buf, register UINT4 *in)
Данная функция является основным шагом в алгоритме MD5.
Входными параметрами являются указатель на буфер buf[] из структуры MD5_CTX и
указатель на буфер in[], хранящем значения типа UINT4. Функция выполняет 4 цикла
по 16 шагов в каждом. В каждом цикле используется одна из функций FF, GG, HH,
II. Далее окончательный результат после 64-х преобразовательных итераций
добавляется к содержимому буфера buf[].
Структура MD5_CTX
Структура MD5_CTX является основной структурой для формирования MessageDigest.
Структура содержит следующие поля:
typedef struct
{
UINT4 i[2]; /* количество бит в сообщении по mod 2^64 */
UINT4 buf[4]; /* временный буфер */
unsigned char in[64]; /* входной буфер */
unsigned char digest[16]; /* содержит действительный Message Digest
после вызова MD5Final() */
} MD5_CTX;
Цифровая подпись и криптосистемы с ключом общего пользования.
Если использовать алгоритмы хэширования вместе с криптосистемами с ключом общего
пользования, то можно создать цифровую подпись, гарантирующую подлинность
полученного набора данных, аналогично тому, как рукописная подпись, подтверждает
аутентичность напечатанного документа. Криптосистема с ключом общего пользования
- это метод, позволяющий осуществлять кодирование и декодирование информации, с
помощью двух исходных ключей: ключа общего пользования, свободно передаваемого
всем желающим, и личного ключа, известного только его владельцу.
Смысл ключа и пароля примерно одинаков. Допустим, Том желает, чтобы Сэм мог
отправить ему зашифрованный документ, и оба они не хотели бы рисковать,
передавая пароль или ключ по линиям связи, так как в этом случае он может быть
кем-то перехвачен. Тогда Том может передать Сэму свой ключ общего пользования
(схема 1).
Используя этот ключ, Сэм шифрует документ и отправляет его Тому. Том дешифрует
документ с помощью своего личного ключа. Это единственный ключ, с помощью
которого можно восстановить документ, зашифрованный с применением ключа общего
пользования, принадлежащего Тому. Тот факт, что ключ общего пользования Тома
может стать кому-то известен, не имеет особого значения, потому что он абсолютно
бесполезен для расшифровки документа. А личный ключ, известный одному лишь Тому,
по открытым линиям связи не передавался; теоретически том хранит его только в
собственной памяти и наоборот, работа других криптосистем с ключом общего
пользования строится на обратном принципе: Сэм шифрует документ с помощью своего
личного ключа и передает свой ключ общего пользования Тому, с помощью которого
тот мог бы расшифровать этот документ. Существующие ныне криптосистемы с ключом
общего пользования, такие, например, как система RSA (сокращение, составленное
из первых букв фамилий трех создателей этого алгоритма), широко используются.
Как же осуществляется цифровая подпись? Рассмотрим еще один пример. Допустим,
Сэм собирается отправить Тому контракт или номер своей кредитной карточки в
цифровом виде. Для подтверждения подлинности этих документов Тому необходима
цифровая подпись Сема. Сначала Сэм отправляет свой документ. Затем использует
алгоритм хэширования для вычисления идентификатора этого документа, шифрует
хэшированное значение с помощью своего личного ключа и отправляет его Тому. Это
и есть цифровая подпись Сэма. Том с помощью того же алгоритма хэширования
сначала вычисляет идентификатор принятого документа. Затем он расшифровывает
значение, которое получил от Сэма, используя предоставленный Сэмом ключ общего
пользования. Если два значения хэширования совпали, Том не только узнает, что
этот документподлинный, но и то, что подпись Сэма действительна. Понятно, что
проведение коммерческих транзакций по такому сценарию значительно безопаснее,
чем с использованием подписи от руки на бумаге, которую можно подделать. А если
сведения, передаваемые Сэмом Тому, конфиденциальны (например, содержат номер
кредитной карточки), то и их можно зашифровать так, чтобы прочитать их смог
только Том.
Message Digest и цифровые сигнатуры
При создании цифровой сигнатуры некоторого сообщения PGP необходимо зашифровать
его секретным ключом. Но PGP в действительности не использует секретный ключ для
шифрования полностью всего сообщения, т. к. этот процесс был бы долгим. Вместо
этого PGP шифрует MessageDigest.
MessageDigest является компактной (128 бит) "перегонкой" вашего сообщения,
подобно концепции контрольной суммы. Вы также можете представить MessageDigest
как "отпечаток" сообщения. MessageDigest представляет ваше сообщение таким
образом, что если это сообщение будет изменено каким-либо образом, то из
изменившегося сообщения будет подсчитано отличное от первоначального
MessageDigest. Это дает возможность обнаружения любых изменений, сделанных
взломщиком. MessageDigest вычисляется, используя криптографически устойчивую
однонаправленную хэш-функцию сообщения. Подбор сообщения, которое произведет
идентичное MessageDigest является с вычислительной точки зрения неосуществимо
для взломщика. В этом отношении МessageDigest намного лучше, чем контрольная
сумма (т. к. легче подобрать разные сообщения, которые будут иметь одинаковые
контрольные суммы). Невозможно получить исходное сообщение по его MessageDigest.
Одного только MessageDigest не достаточно для аутентификации сообщения. Алгоритм
MD опубликован, и не требует знания секретных ключей для вычислений. Если мы
просто будем прикреплять MessageDigest к сообщению, то взломщик сможет изменить
сообщение, вычислить его MessageDigest, прикрепить MessageDigest к измененному
сообщению и отправить дальше. Для обеспечения реальной аутентификации
отправитель шифрует (подписывает) MessageDigest своим секретным ключом.
MessageDigest вычисляется из сообщения отправителем. Секретный ключ отправителя
используется для зашифровки MessageDigest и некоторого временного отпечатка
(timestamp), формируя цифровую сигнатуру, или сертификат сигнатуры. Отправитель
посылает цифровую сигнатуру перед сообщением. Получатель получает сообщение и
цифровую сигнатуру, восстанавливает исходное MessageDigest из цифровой сигнатуры
при помощи расшифровки открытым ключом отправителя, заново вычисляет
MessageDigest сообщения и производит сравнение с полученным от отправителя
MessageDigest. Если они равны, то над сообщением не было произведено никаких
изменений.
Потенциальный взломщик должен либо произвести некоторое сообщение, которое
порождает идентичное MessageDigest (что неосуществимо), или он должен создать
новую цифровую сигнатуру от измененного MessageDigest (что также неосуществимо
без знания секретного ключа отправителя).
Цифровые сигнатуры производят аутентификацию сообщения, а также проверку
правильности сообщения при его передаче между пользователями для обнаружения
изменений сообщения от воздействия каких-либо ошибок или намеренных действий.
Использование MessageDigest для формирования цифровых сигнатур имеет и другие
преимущества кроме существенной быстроты, чем непосредственное подписывание
полного сообщения секретным ключом. Message Digest позволяет сигнатурам быть
cтандартной функцией небольшой фиксированной длины, вне зависимости от размеров
действительного сообщения. Также позволяет контролировать целостность сообщения
автоматически, способом подобным использованию контрольной суммы, позволяет
сигнатуре храниться отдельно от сообщения, возможно в некотором публичном
архиве, без разоблачения секретной информации о действительном сообщении, т. к.
никто не сможет извлечь сообщение из его MessageDigest.
Схема. Система цифровой подписи.
1. Сэм обрабатывает по специальному алгоритму документ, который собирается
отправить Тому, в результате получает некоторый параметр, рассчитанный на
основании содержимого документа. Обычно это занимает значительно меньше места,
чем исходный документ - параметр 128 или 160 двоичных разрядов.
Затем Сэм с помощью своего личного ключа шифрует полученный параметр. Итоговое
значение служит цифровой подписью Сэма.
Сэм отправляет Тому документ и свою цифровую подпись.
Том пропускает документ, полученный от Тома, через тот же алгоритм, которым
пользовался Том.
Затем Том дешифрует цифровую подпись, полученную от Сэма, пользуясь
предоставленным Сэмом ключом общего пользования.
Том сравнивает значение параметра, полученного при выполнении операции 4, с
расшифрованным значением цифровой подписи. Если эти значения совпадают, значит,
подпись подлинная и документ "в пути" не подвергся изменениям. В противном
случае, либо документ искажен, либо подпись подделана, либо и то и другое.
Вероятнее всего именно по такой, или подобной схеме будут вестись дела через
Internet или любую другую информационную службу. Этот алгоритм послужил основой
проекта государственного стандарта США - Digital Signature Standard (DSS). В нем
применяются: алгоритм Secure Hash Algorithm для расчета параметров хэширования и
криптосистема с ключом общего пользования, известная под названием Digital
Signature Algorithm (DSA) и предназначенная для получения цифровой подписи по
параметрам хэширования. Ряд пунктов проекта DSS подверглись критике, однако
многие из замечаний исходили от групп, финансово заинтересованных в отклонении
данного проекта.
Время покажет, будет ли какой-либо из методов создания цифровой подписи принят в
качестве стандарта. Однако вне зависимости от результата, важно другое:
действительно существует возможность совершенно безопасно осуществлять цифровые
торговые операции.
Скачали данный реферат: Apraksin, Шулёв, Havronija, Видина, Карявин, Цорн, Chupov.
Последние просмотренные рефераты на тему: оценка реферата, скачать дипломную работу на тему, текст для изложения, урок реферат.
1
Цифровая подпись: принципы работы
Контрольные суммы, контроль 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 из другого.
Механизм CRC чрезвычайно полезен для проверки файлов, загружаемых из сетевых
информационных служб. Если кто-то сообщает мне, что переданная ему через сеть ZD
Net утилита вдруг без видимой причины перестает работать, то первым делом я
прошу его создать ее архивный файл с помощью программы PKZIP и набрать команду
PKZIP -V для просмотра созданного . ZIP файла. Среди прочих параметров он увидит
также 32-разрядное значение параметра CRC, рассчитанное программой PKZIP для
несжатого файла. Если вычисленное значение параметра CRC для gjkextyyjq утилиты
не совпадает
со значением для исходного варианта файла, значит, при загрузке его произошла
необнаруженная ошибка передачи данных (такое иногда случается).
Можно организовать собственный контроль CRC для идентификации файлов; для этого
потребуется переписать через службу PC Magazine Online файл CRC. COM. (Он
находится в библиотеке Tutor форума Utilities/Tips службы ZD Net/CompuServe и в
файле V15N07. ZIP (на сервере по адресу http://www. pcmag. 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, и если вы выполнили с ним тот же алгоритм хэширования и ваш результат
совпал с исходным значением, определенно можно быть уверенным, что принятый вами
файл не подвергся искажениям.
Алгоритм MD5
Терминология
В данном случае "word" является 32-х битной величиной, "byte" - 8-ми битная
величина. Последовательность бит должна интерпретироваться таким же способом что
и последовательность байт, где каждая последовательная группа из восьми бит
интерпретируется как байт с старшим (наиболее значащим) битом каждого байта
следующим в последовательности первым. Подобно последовательности байт должна
интерпретироваться и последовательность 32-битных слов.
Запись x_i означает "x sub i" (т. е. х с индексом i). Если некоторое выражение
используется как индекс, то оно берется в фигурные скобки, например x_{i+1}.
Символ " ^ " используется для операций возведения в степень, т. е. x^i следует
понимать как х в степени i.
Символ "+" обозначает операцию сложения слов (т. е. сложение по модулю 2^32).
Далее x
циклического сдвига (вращения) предыдущего значения х на s бит влево. not(x) -
поразрядная операция отрицания , x v y - поразрядное ИЛИ(OR) операндов x и y , x
xor y – поразрядное исключающее ИЛИ(XOR) операндов x и y , и xy - поразрядное
И(AND) операндов x и y.
Краткое описание алгоритма MD5
Вначале допускаем, что имеем на входе сообщение из b-бит, и что мы желаем найти
Message Digest этой последовательности бит. Число b является произвольным
неотрицательным целым; b может быть равным нулю, оно не обязательно должно быть
множителем 8, и оно может быть произвольно большим. Представим
последовательность бит сообщения как:
m0 m1 m2 . . . . . . m{b-1}
Следующие пять этапов выполняются для подсчета Message Digest сообщения.
Этап 1. Присоединение заполняющих (дополнительных) битов.
Сообщение расширяется так, чтобы его длина (в битах) совпадала с 448, по модулю
512. Дополнение всегда выполняется, даже если длина сообщения - уже совпадает с
448 по модулю 512. Дополнение выполняется следующим образом: одиночный "1" бит
добавляется к сообщению, и далее "0" биты добавляются так что длина в битах
заполняемого сообщения соответствует 448 по модулю 512. В общем случае, минимум
один бит и максимум 512 бит добавляется.
Этап 2. Добавление длины
64-битное представление входной последовательности b (длина сообщения перед
расширением дополнительными битами) присоединяется к результату предыдущего
этапа. Маловероятно, что длина b будет больше, чем 264 поэтому и используется
64-х разрядная величина для хранения длины b. (Эти биты добавляются как два 32-х
разрядных слова, младшее заносится первым).
В этом месте окончательное сообщение(после выполнения первого и второго этапов)
имеет длину, кратную 512 битам, т. е. сообщение имеет длину, которая точно
кратна 16-ти словам. Последовательность М[0 . . . . N-1] является словами
окончательного сообщения, где N кратно 16.
Этап 3. Инициализация MD буфера.
Буфер на 4-е слова (A, B, C, D) используется для подсчета Message Digest. Каждое
из A, B, C, D является 32-х битным регистром. Эти регистры инициализируются
следующими шестнадцатиричными значениями, где первым следует самый младший байт:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Программисты из RSA Data Security, Inc. , дабы не утруждать себя и остальных
людей по поводу происхождения этих чисел, просто назвали их магическими
константами.
Этап 4. Обработка сообщения в блоках по 16 слов.
Сначала определяются четыре вспомагательных функции каждая из которых имеет на
входе три 32-битных слова и производит одно 32-битное слово на выходе.
F(X, Y, Z) = XY v not(X) Z
G(X, Y, Z) = XZ v Y not(Z)
H(X, Y, Z) = X xor Y xor Z
I(X, Y, Z) = Y xor (X v not(Z))
В каждой битовой позиции функция F действует как условный опреатор : если X то Y
иначе Z. Функция F могла бы определяться с использованием операцию + вместо v,
так как выражение XY and not(X)Z никогда не будет иметь 1 в одинаковых битовых
позициях.
Если биты X, Y и Z независимы и несмещены(??), то каждый бит после выполнения
F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для
нахождения выходного значения от входных битов X, Y и Z, тем же способом, что
если биты X, Y и Z независимы и несмещены, то каждый бит после выполнения
вышеуказанных функций будет независим и несмещен. Обратите внимание, что функция
H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией
контроля четности входных значений). Далее на этом этапе происходит четыре
цикла, в которых происходит трансформация битов сообщения при помощи
вышеуказанных
функций, функций циклического сдвига, и таблицы константных значений.
Этап 5. Вывод
В результате выполнения предыдущих этапов Message Digest производит на выходе
числа A, B, C, D, общая длина которых 128 бит.
Резюме
Алгоритм получает на входе сообщение произвольной длины и после обработки на
выходе получаем 128-битный "отпечаток" или "Message Digest". Предполагается, что
вычислительная трудоемкость нахождения двух сообщений, имеющих одинаковые
Message Digest очень велика. MD5 алгоритм предназначен для приложений,
формирующих цифровые сигнатуры, в которых большой файл должен быть "сжат"
безопасным способом перед зашифровкой открытым (или секретным)ключом в некоторой
криптосистеме с открытым ключом, такой как RSA.
MD5 алгоритм является расширением алгоритма MD4.
MD5 алгоритм полностью разработан для быстрой работы на 32-х разрядных машинах.
К тому же алгоритм не требует каких-либо больших подстановочных таблиц;
обеспечивается компактная кодировка.
MD5 Message Digest алгоритм прост в использовании, и обеспечивает получение
128-ми битного "отпечатка" или Message Digest сообщения произвольной длины.
Предполагается, что сложность нахождения двух сообщений, которые произведут
одинаковые Message Digest является порядка 2 в 64 степени операций, и сложность
построения сообщения по некоторому известному Message Digest является порядка 2
в 128 степени операций.
Примеры исходного кода для реализации MD5.
Макросы
F, G, H, I
Данные макросы определяют четыре вспомогательных функции, каждая из которых
имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.
#define F(x, y, z) (((x) & (y)) ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) (~z)))
В каждой битовой позиции функция F действует как условный оператор : если X то Y
иначе Z. Если биты X, Y и Z независимы и несмещены (??), то каждый бит после
выполнения F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для
нахождения выходного значения от входных битов X, Y и Z, тем же способом, что
если
биты X, Y и Z независимы и несмещены, то каждый бит после выполнения
вышеуказанных функций будет независим и несмещен. Следует обратить внимание, что
функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е.
функцией контроля четности входных значений).
FF, GG, HH, II
Данные макросы определяют четыре вспомагательных функции, которые на входе
получают семь 32-х разрядных параметров, а на выходе получаем одну 32-х
разрядную величину.
Эти фунции используются в функции Transform() для битовых преобразований.
Функции работают следующим образом:
1. В выходной параметр записывается сумма соответствующей функции (для FF() это
F(), для GG() это G(), для HH() это H(), для II() это I()) от 2-го, 3-го и 4-го
параметров с 5-м и 7-м параметрами.
2. Производится циклический сдвиг влево выходного параметра на количество бит,
указанное в 6-м входном параметре.
3. Производится приращение выходного параметра на величину, указанную во 2-м
входном параметре.
#define FF(a, b, c, d, x, s, ac) /
{(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define GG(a, b, c, d, x, s, ac) /
{(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define HH(a, b, c, d, x, s, ac) /
{(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define II(a, b, c, d, x, s, ac) /
{(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
Сразу можно отметить, что входные параметры вышеуказанных функций представляют
собой следующие значения:
register UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; Как видно
регистровые переменные a, b, c, d типа UINT4 инициализируются значениями
временного буфера buf[4] содержащемся в основной структуре Message Digest
MD5_CTX. Пятый параметр x всегда инициализируется символом из входного буфера
in[64] также находящемся в структуре MD5_CTX.
Параметр s равен одной из шестнадцати констант, определенных в функции
Transform().
А вот самый последний параметр ас равен одной из 64-х "таинственных констант".
Разработчики из RSA Data Security, Inc. предлагают вам расположить эти константы
в "little-endian" порядке, расшифровать при помощи DES и вы получите ТАЙНЫЕ
ПОСЛАНИЯ. (вот только DESовый ключик они не указали).
ROTATE_LEFT
Данный макрос сдвигает x влево на n бит.
#define ROTATE_LEFT(x, n) (((x) < (n)) ((x) >> (32-(n))))
Если n > 32, то результат равен нулю.
Функции
void MD5Init ( MD5_CTX *mdContext)
Функция MD5Init(MD5_CTX *mdContext) выполняет инициализацию некоторых полей
структуры Message Digest MD5_CTX В качестве параметра функция получает указатель
на структуру MD5_CTX.
{
/* Обнуление полей, которые будут содержать длину сообщения */
mdContext->i[0] = mdContext->i[1] = (UINT4)0;
/* Загрузка магических констант инициализации. */
mdContext->buf[0] = (UINT4)0x67452301L;
mdContext->buf[1] = (UINT4)0xefcdab89L;
mdContext->buf[2] = (UINT4)0x98badcfeL;
mdContext->buf[3] = (UINT4)0x10325476L;
}
void MD5Update (register MD5_CTX *mdContext, unsigned char *inBuf, unsigned int
inLen)
Данная функция обрабатывает содержимое структуры MD5_CTX.
В качестве параметров функция получает:
Указатель mdContext на структуру MD5_CTX;
Cимвольный буфер inBuf[], который содержит символы исходного сообщения, чей
Message Digest мы подсчитываем; Длину inLen передаваемого буфера.
Вначале подсчитывается целочисленная величина mdi:
mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
Эта величина равна длине сообщения в байтах по модулю 64. Длина сообщения в
битах хранится в структуре MD5_CTX в буфере i[0. . 1].
Длина сообщения в битах заносится в буфер i[0. . 1] следующим образом:
mdContext->i[0] += ((UINT4)inLen
mdContext->i[1] += ((UINT4)inLen >> 29);
Следующий участок кода выполняет следующие действия:
while (inLen--)
{
/* добавляем новый символ в буфер, инкрементируя mdi */
mdContext->in[mdi++] = *inBuf++;
/* Если необходимо выполняем преобразование */
if (mdi == 0x40)
{
for (i = 0, ii = 0; i < 16; i++, ii += 4)>
in[i] = (((UINT4)mdContext->in[ii+3])
(((UINT4)mdContext->in[ii+2])
(((UINT4)mdContext->in[ii+1])
((UINT4)mdContext->in[ii]);
Transform (mdContext->buf, in);
mdi = 0;
}
}
Пока уменьшаемая на 1 длина переданного в функцию сообщения не станет равной
нулю выполняем следующие действия:
Заносим новый символ из входного буфера функции в 64-х байтный буфер структуры
MD5_CTX, увеличивая при этом переменную mdi на 1. Если mdi равна 64, то
преобразуем
однобайтные символы буфера in[] структуры MD5_CTX в 4-х байтные величины типа
UINT4, заносим в промежуточный буфер на 16 величин типа UINT4, и далее передаем
функции Transform(). Присваиваем переменной mdi 0.
void MD5Final (MD5_CTX *mdContext)
Функция завершает вычисление Message Digest и заносит полученное значение в
структуре MD5_CTX в символьный буфер digest[0. . . 15].
Входным параметром функции является указатель на структуру MD5_CTX.
Основные моменты:
Расширение сообщения дополнительными заполняющими символами из таблицы PADDING[]
/* Подсчет длины сообщения в байтах по модулю 64 */
mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
/* Расширить до 56 по модулю 64 */
padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi);>
MD5Update(mdContext, PADDING, padLen);
Присоединение битов длины и вызов функции Transform().
in[14] = mdContext->i[0];
in[15] = mdContext->i[1];
for (i = 0, ii = 0; i < 14; i++, ii += 4)>
in[i] = (((UINT4)mdContext->in[ii+3])
(((UINT4)mdContext->in[ii+2])
(((UINT4)mdContext->in[ii+1])
((UINT4)mdContext->in[ii]);
Transform (mdContext->buf, in);
Сохранение буфера в digest(т. е. получение окончательного Message Digest):
for (i = 0, ii = 0; i < 4; i++, ii += 4)>
{
mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF);
mdContext->digest[ii+1] = (unsigned char)((mdContext->buf[i] >> 8) & 0xFF);
mdContext->digest[ii+2] = (unsigned char)((mdContext->buf[i] >> 16) & 0xFF);
mdContext->digest[ii+3] = (unsigned char)((mdContext->buf[i] >> 24) & 0xFF);
}
void Transform(register UINT4 *buf, register UINT4 *in)
Данная функция является основным шагом в алгоритме MD5.
Входными параметрами являются указатель на буфер buf[] из структуры MD5_CTX и
указатель на буфер in[], хранящем значения типа UINT4. Функция выполняет 4 цикла
по 16 шагов в каждом. В каждом цикле используется одна из функций FF, GG, HH,
II. Далее окончательный результат после 64-х преобразовательных итераций
добавляется к содержимому буфера buf[].
Структура MD5_CTX
Структура MD5_CTX является основной структурой для формирования MessageDigest.
Структура содержит следующие поля:
typedef struct
{
UINT4 i[2]; /* количество бит в сообщении по mod 2^64 */
UINT4 buf[4]; /* временный буфер */
unsigned char in[64]; /* входной буфер */
unsigned char digest[16]; /* содержит действительный Message Digest
после вызова MD5Final() */
} MD5_CTX;
Цифровая подпись и криптосистемы с ключом общего пользования.
Если использовать алгоритмы хэширования вместе с криптосистемами с ключом общего
пользования, то можно создать цифровую подпись, гарантирующую подлинность
полученного набора данных, аналогично тому, как рукописная подпись, подтверждает
аутентичность напечатанного документа. Криптосистема с ключом общего пользования
- это метод, позволяющий осуществлять кодирование и декодирование информации, с
помощью двух исходных ключей: ключа общего пользования, свободно передаваемого
всем желающим, и личного ключа, известного только его владельцу.
Смысл ключа и пароля примерно одинаков. Допустим, Том желает, чтобы Сэм мог
отправить ему зашифрованный документ, и оба они не хотели бы рисковать,
передавая пароль или ключ по линиям связи, так как в этом случае он может быть
кем-то перехвачен. Тогда Том может передать Сэму свой ключ общего пользования
(схема 1).
Используя этот ключ, Сэм шифрует документ и отправляет его Тому. Том дешифрует
документ с помощью своего личного ключа. Это единственный ключ, с помощью
которого можно восстановить документ, зашифрованный с применением ключа общего
пользования, принадлежащего Тому. Тот факт, что ключ общего пользования Тома
может стать кому-то известен, не имеет особого значения, потому что он абсолютно
бесполезен для расшифровки документа. А личный ключ, известный одному лишь Тому,
по открытым линиям связи не передавался; теоретически том хранит его только в
собственной памяти и наоборот, работа других криптосистем с ключом общего
пользования строится на обратном принципе: Сэм шифрует документ с помощью своего
личного ключа и передает свой ключ общего пользования Тому, с помощью которого
тот мог бы расшифровать этот документ. Существующие ныне криптосистемы с ключом
общего пользования, такие, например, как система RSA (сокращение, составленное
из первых букв фамилий трех создателей этого алгоритма), широко используются.
Как же осуществляется цифровая подпись? Рассмотрим еще один пример. Допустим,
Сэм собирается отправить Тому контракт или номер своей кредитной карточки в
цифровом виде. Для подтверждения подлинности этих документов Тому необходима
цифровая подпись Сема. Сначала Сэм отправляет свой документ. Затем использует
алгоритм хэширования для вычисления идентификатора этого документа, шифрует
хэшированное значение с помощью своего личного ключа и отправляет его Тому. Это
и есть цифровая подпись Сэма. Том с помощью того же алгоритма хэширования
сначала вычисляет идентификатор принятого документа. Затем он расшифровывает
значение, которое получил от Сэма, используя предоставленный Сэмом ключ общего
пользования. Если два значения хэширования совпали, Том не только узнает, что
этот документподлинный, но и то, что подпись Сэма действительна. Понятно, что
проведение коммерческих транзакций по такому сценарию значительно безопаснее,
чем с использованием подписи от руки на бумаге, которую можно подделать. А если
сведения, передаваемые Сэмом Тому, конфиденциальны (например, содержат номер
кредитной карточки), то и их можно зашифровать так, чтобы прочитать их смог
только Том.
Message Digest и цифровые сигнатуры
При создании цифровой сигнатуры некоторого сообщения PGP необходимо зашифровать
его секретным ключом. Но PGP в действительности не использует секретный ключ для
шифрования полностью всего сообщения, т. к. этот процесс был бы долгим. Вместо
этого PGP шифрует MessageDigest.
MessageDigest является компактной (128 бит) "перегонкой" вашего сообщения,
подобно концепции контрольной суммы. Вы также можете представить MessageDigest
как "отпечаток" сообщения. MessageDigest представляет ваше сообщение таким
образом, что если это сообщение будет изменено каким-либо образом, то из
изменившегося сообщения будет подсчитано отличное от первоначального
MessageDigest. Это дает возможность обнаружения любых изменений, сделанных
взломщиком. MessageDigest вычисляется, используя криптографически устойчивую
однонаправленную хэш-функцию сообщения. Подбор сообщения, которое произведет
идентичное MessageDigest является с вычислительной точки зрения неосуществимо
для взломщика. В этом отношении МessageDigest намного лучше, чем контрольная
сумма (т. к. легче подобрать разные сообщения, которые будут иметь одинаковые
контрольные суммы). Невозможно получить исходное сообщение по его MessageDigest.
Одного только MessageDigest не достаточно для аутентификации сообщения. Алгоритм
MD опубликован, и не требует знания секретных ключей для вычислений. Если мы
просто будем прикреплять MessageDigest к сообщению, то взломщик сможет изменить
сообщение, вычислить его MessageDigest, прикрепить MessageDigest к измененному
сообщению и отправить дальше. Для обеспечения реальной аутентификации
отправитель шифрует (подписывает) MessageDigest своим секретным ключом.
MessageDigest вычисляется из сообщения отправителем. Секретный ключ отправителя
используется для зашифровки MessageDigest и некоторого временного отпечатка
(timestamp), формируя цифровую сигнатуру, или сертификат сигнатуры. Отправитель
посылает цифровую сигнатуру перед сообщением. Получатель получает сообщение и
цифровую сигнатуру, восстанавливает исходное MessageDigest из цифровой сигнатуры
при помощи расшифровки открытым ключом отправителя, заново вычисляет
MessageDigest сообщения и производит сравнение с полученным от отправителя
MessageDigest. Если они равны, то над сообщением не было произведено никаких
изменений.
Потенциальный взломщик должен либо произвести некоторое сообщение, которое
порождает идентичное MessageDigest (что неосуществимо), или он должен создать
новую цифровую сигнатуру от измененного MessageDigest (что также неосуществимо
без знания секретного ключа отправителя).
Цифровые сигнатуры производят аутентификацию сообщения, а также проверку
правильности сообщения при его передаче между пользователями для обнаружения
изменений сообщения от воздействия каких-либо ошибок или намеренных действий.
Использование MessageDigest для формирования цифровых сигнатур имеет и другие
преимущества кроме существенной быстроты, чем непосредственное подписывание
полного сообщения секретным ключом. Message Digest позволяет сигнатурам быть
cтандартной функцией небольшой фиксированной длины, вне зависимости от размеров
действительного сообщения. Также позволяет контролировать целостность сообщения
автоматически, способом подобным использованию контрольной суммы, позволяет
сигнатуре храниться отдельно от сообщения, возможно в некотором публичном
архиве, без разоблачения секретной информации о действительном сообщении, т. к.
никто не сможет извлечь сообщение из его MessageDigest.
Схема. Система цифровой подписи.
1. Сэм обрабатывает по специальному алгоритму документ, который собирается
отправить Тому, в результате получает некоторый параметр, рассчитанный на
основании содержимого документа. Обычно это занимает значительно меньше места,
чем исходный документ - параметр 128 или 160 двоичных разрядов.
Затем Сэм с помощью своего личного ключа шифрует полученный параметр. Итоговое
значение служит цифровой подписью Сэма.
Сэм отправляет Тому документ и свою цифровую подпись.
Том пропускает документ, полученный от Тома, через тот же алгоритм, которым
пользовался Том.
Затем Том дешифрует цифровую подпись, полученную от Сэма, пользуясь
предоставленным Сэмом ключом общего пользования.
Том сравнивает значение параметра, полученного при выполнении операции 4, с
расшифрованным значением цифровой подписи. Если эти значения совпадают, значит,
подпись подлинная и документ "в пути" не подвергся изменениям. В противном
случае, либо документ искажен, либо подпись подделана, либо и то и другое.
Вероятнее всего именно по такой, или подобной схеме будут вестись дела через
Internet или любую другую информационную службу. Этот алгоритм послужил основой
проекта государственного стандарта США - Digital Signature Standard (DSS). В нем
применяются: алгоритм Secure Hash Algorithm для расчета параметров хэширования и
криптосистема с ключом общего пользования, известная под названием Digital
Signature Algorithm (DSA) и предназначенная для получения цифровой подписи по
параметрам хэширования. Ряд пунктов проекта DSS подверглись критике, однако
многие из замечаний исходили от групп, финансово заинтересованных в отклонении
данного проекта.
Время покажет, будет ли какой-либо из методов создания цифровой подписи принят в
качестве стандарта. Однако вне зависимости от результата, важно другое:
действительно существует возможность совершенно безопасно осуществлять цифровые
торговые операции.
Скачали данный реферат: Apraksin, Шулёв, Havronija, Видина, Карявин, Цорн, Chupov.
Последние просмотренные рефераты на тему: оценка реферата, скачать дипломную работу на тему, текст для изложения, урок реферат.
Категории:
1
Главная