Алгоритм расчета контрольной суммы CRC32

 

 

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

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

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

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

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

· Хэш-функция имеет бесконечную область определения;

· Хэш-функция имеет конечную область значений;

· Она необратима;

· Изменение входного потока информации на один бит меняет около половины всех бит выходного потока, то есть результата хэш-функции.

Эти свойства позволяют подавать на вход хэш-функции текстовые строки произвольной длины на любом национальном языке и, ограничив область значений функции диапазоном 0..2N-1, где N – длина ключа в битах, получать на выходе достаточно равномерно распределенные по области значения блоки информации – ключи.

Рассмотрим применение хэш-функций для проверки достоверности пароля. Пусть имеется криптографическая функция F, расшифровывающая ключом K последовательность Аi в последовательность Aj.

Разумеется, только для одного единственного K мы получим исходную последовательность Aj, а для всех остальных K – «мусор». Каким способом можно удостовериться, что полученная Aj и есть искомая последовательность? Можно сохранить фрагмент исходной последовательности и затем сверить его с полученным результатом. Однако это очень ненадежно, так как не гарантируется, что совпадение одного фрагмента обеспечивает совпадение всей последовательности.

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

 

Однонаправленные хэш-функции

 

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

Особой разновидностью однонаправленных функций являются однонаправленные функции с тайной лазейкой. Такие функции, кроме однонаправленности, обладают дополнительным свойством – знание некой информации об этой функции делает подсчет обратной функции сравнительно нетрудным. Более формально, для однонаправленных функций с лазейкой нетрудно вычислить F(x) по заданному значению аргумента х, если не знать некую секретную информацию z. Собственно однонаправленные функции с тайной лазейкой служат математической основой для криптографии с открытым ключом.

Однонаправленной хэш-функцией, которую мы будем обозначать Н(М), называется такая однонаправленная функция, которая в качестве аргумента получает сообщение М произвольной длины и возвращает число h фиксированной разрядности m, то есть более формально

h = H(M),

где значение h называемое хэшем (или необратимым хэшем), имеющим разрядность m.

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

· зная М легко вычислить h.

· зная h, трудно определить значение M, для которого H(M) = h.

· зная M, трудно определить другое сообщение M’, для которого H(M) = H(M’).

Простейшей функцией, обладающей перечисленными свойствами, является следующее преобразование h = H(M)

, ,

где H0 и p – параметры хэш-функции, h – результирующее значение хэша (его разрядность совпадает с разрядностью p).

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

Наиболее популярными функциями хэширования являются MD5 (Message Digest 5 – профиль сообщения 5), создающий 16-байтовый результат (128-битное значение хэш-функции), и алгоритм SHA (Secure Hash Algorithm – надежный алгоритм хэширования), формирующий 20-байтовый результат (160-битное значение хэш-функции). В настоящее время алгоритм SHA принят правительством США как стандарт.

Существует отечественный стандарт для хэш-функций ‑ ГОСТ Р34.11‑94; он используется совместно со стандартами ГОСТ Р34.10‑ 94/2001 для ЭЦП.

Стойкость функции хеширования примерно равна 2n/2, где п – длина выходного значения функции. В связи с разработкой в США новых стандартов шифрования с длиной ключа 128, 192 и 256 бит потребовалось создать «сопровождающие» алгоритмы, обеспечивающие такой же уровень стойкости. В качестве нового стандарта США предполагается перейти на алгоритмы вычисления хэш-функции с длиной выходного значения 256, 384 и 512 бит, имеющие название SHA-256, SHA-384, SHA-512 соответственно.

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

Системы, построенные на односторонних функциях при условии отсутствия ошибок реализации, взлому, как правило, не подлежат. Но такие программы сегодня – редкость (вспомним обнаруженные ошибки в продуктах таких гигантов как Microsoft, Novell). Использование контрольной суммы – это один из способов этот пароль найти. Крайне редко в системах массового применения используют односторонние хэш-функции.

Процесс подписания сообщения закрытым ключом К формально будем обозначать так:

SK(M).

Процесс проверки подлинности подписи с помощью соответствующего открытого ключа формально записывается так:

VK(M).

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

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

· Участник-1 подписывает сообщение своим закрытым ключом;

· Участник-1 шифрует подписанное сообщение открытым ключом и отправляет его Участнику-2;

· Участник-2 расшифровывает сообщение своим закрытым ключом;

· Участник-2 проверяет подлинность подписи. Используя открытый ключ Участника-1, и восстанавливает сообщение.

Рис. 8. Протокол работы цифровой электронной подписи

 

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

Возможности, открываемые с использованием криптосистем с открытыми ключами, практически безграничны. С развитием таких криптосистем появились реальные возможности для сетевой идентификации пользователей и придания цифровым электронным подписям юридического статуса (в РФ соответствующий закон был подписан Президентом в начале 2002 года). Правовые условия использования электронной цифровой подписи в электронных документах регламентирует федеральный закон от 10.01.2002 N 1-ФЗ «Об электронной цифровой подписи».

В основе стандартов электронной цифровой подписи в США и России лежит схема Эль-Гамаля.

 


3.12. Алгоритмы работы с большими числами

 

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

· поиска больших простых чисел;

· нахождения взаимно простых больших чисел;

· возведения в степень в конечном поле.