ГОСТ Р 34.11-94: различия между версиями
[непроверенная версия] | [непроверенная версия] |
→Другие примеры: обратный порядок байт? |
Rushless (обсуждение | вклад) Используемость ГОСТ. См. http://ypn.ru/269/asymmetric-crypto-algorythms/ |
||
Строка 17: | Строка 17: | ||
* Разработчик: ГУБС [[ФАПСИ]] и ВНИИС |
* Разработчик: ГУБС [[ФАПСИ]] и ВНИИС |
||
Стандарт определяет алгоритм и процедуру вычисления хэш-функции для последовательности символов. |
Стандарт определяет алгоритм и процедуру вычисления хэш-функции для последовательности символов. Этот стандарт является обязательным для применения в качестве алгоритма хэширования в государственных организациях РФ и ряде коммерческих организаций. |
||
== Вводные обозначения == |
== Вводные обозначения == |
Версия от 15:20, 16 октября 2010
ГОСТ Р34.11-94 — российский криптографический стандарт вычисления хэш-функции.
- Дата введения: 23 мая 1994 г.
- Размер хэша: 256 бит
- Размер блока входных данных: 256 бит
- Разработчик: ГУБС ФАПСИ и ВНИИС
Стандарт определяет алгоритм и процедуру вычисления хэш-функции для последовательности символов. Этот стандарт является обязательным для применения в качестве алгоритма хэширования в государственных организациях РФ и ряде коммерческих организаций.
Вводные обозначения
Для описания алгоритма хэширования будем использовать следующие обозначения:
- — блок длиной j бит заполненный нулями.
- — длина блока M в битах по модулю 2256.
- — слияние (конкатенация) двух блоков в один.
- — сложение двух блоков длиной 256 бит по модулю 2256
- — побитное сложение (XOR) двух блоков одинаковой длины.
Далее будем считать, что младший (нулевой) бит в блоке находится справа, старший — слева.
Описание
Основой описываемой хэш-функции является шаговая функция хэширования где , , — блоки длины 256 бит.
Входное сообщение разделяется на блоки по 256 бит. В случае если размер последнего блока меньше 256 бит, то к нему приписываются слева нули для достижения заданной длины блока.
Каждый блок сообщения, начиная с первого, подаётся на шаговую функцию для вычисления промежуточного значения хэш-функции:
Значение можно выбрать произвольным.
После вычисления конечное значение хэш-функции получают следующим образом:
- , где L — Длина сообщения M в битах по модулю
- , где K — Контрольная сумма сообщения M:
h — значение хэш-функции сообщения M
Алгоритм:
- Инициализация:
- — Начальное значение хэш-функции. Т.е. - 256 битовый IV вектор, определяется пользователем.
- — Контрольная сумма
- — Длина сообщения
- Функция сжатия внутренних итераций: для i = 1 … n — 1 выполняем следующее (пока ):
- - итерация метода последовательного хэширования
- - итерация вычисления длины сообщения
- - итерация вычисления контрольной суммы
- Функция сжатия финальной итерации:
- - вычисление полной длины сообщения
- - набивка последнего блока
- - вычисление контрольной суммы сообщения
- - MD - усиление
- Выход. Значением хэш-функции является h,
Замечание: так как длина сообщения участвует в хэшировании, то нет необходимости указывать в передаваемом сообщении количество добавленных нулей к блоку .
Алгоритм вычисления шаговой функции хэширования
Шаговая функция хэширования H отображает два блока длиной 256 бит в один блок длиной 256 бит: и состоит из трех частей:
- Генерирование ключей
- Шифрующее преобразование — шифрование с использованием ключей
- Перемешивающее преобразование результата шифрования
Генерация ключей
В алгоритме генерации ключей используются:
- Два преобразования блоков длины 256 бит:
- Преобразование , где — подблоки блока Y длины 64 бит.
- Преобразование , где , а — подблоки блока Y длины 8 бит.
- Три константы:
C2 = 0 C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00 C4 = 0
Алгоритм:
- Для j = 2,3,4 выполняем следующее:
Шифрующее преобразование
После генерирования ключей происходит шифрование по ГОСТ 28147—89 в режиме простой замены на ключах (для ), процедуру шифрования обозначим через E (Примечание: функция шифрования E по ГОСТ 28147 шифрует 64 битные данные 256 битным ключом). Для шифрования разделяют на четыре блока по 64 бита: и зашифровывают каждый из блоков:
После чего блоки собирают в 256 битный блок:
Перемешивающее преобразование
На последнем этапе происходит перемешивание , S и m с применением регистра сдвига, в результате чего получают .
Для описания процесса преобразования сначала необходимо определить функцию ψ, которая производит элементарное преобразование блока длиной 256 бит в блок той же длины: , где — подблоки блока Y длины 16 бит.
Перемешивающее преобразование имеет вид , где означает i-ую степень преобразования . Другими словами преобразование представляет собой LFSR — линейный сдвиговый регистр с обратной связью, а индекс указывает на количество раундов LFSR.
Ряд отличительных особенностей ГОСТ Р 34.11-94
- При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
- Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
- Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
- Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S — боксах, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий.
Оценка криптостойкости
В 2008 году командой экспертов из Австрии и Польши была обнаружена техническая уязвимость, сокращающая поиск коллизий в 223 раз.[1] Количество операций, необходимое для нахождения коллизии, таким образом, составляет 2105, что, однако, на данный момент практически не реализуемо. Проведение коллизионной атаки на практике имеет смысл только в случае цифровой подписи документов, причём если взломщик может изменять неподписанный оригинал.
Использование
Функция используется при реализации систем цифровой подписи на базе асимметричного криптоалгоритма по стандарту ГОСТ Р 34.10-2001. Сообщество российских разработчиков СКЗИ согласовала используемые в Интернет параметры ГОСТ Р 34.11-94, см. RFC 4357.
- Использование в сертификатах открытых ключей.[2]
- Использование для защиты сообщений в S/MIME (Cryptographic Message Syntax, PKCS#7).[3]
- Использование для защиты соединений в TLS (SSL, HTTPS, WEB).[4]
- Использование для защиты сообщений в XML Signature (XML Encryption).[5]
- Защита целостности Интернет адресов и имён (DNSSEC).[6]
Примеры хэшей
В качестве шифрующего преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147-89 в режиме простой замены. При этом заполнение узлов замены (S-box) следующее:
Номер S-box | Значение | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 4 | 10 | 9 | 2 | 13 | 8 | 0 | 14 | 6 | 11 | 1 | 12 | 7 | 15 | 5 | 3 |
2 | 14 | 11 | 4 | 12 | 6 | 13 | 15 | 10 | 2 | 3 | 8 | 1 | 0 | 7 | 5 | 9 |
3 | 5 | 8 | 1 | 13 | 10 | 3 | 4 | 2 | 14 | 15 | 12 | 7 | 6 | 0 | 9 | 11 |
4 | 7 | 13 | 10 | 1 | 0 | 8 | 9 | 15 | 14 | 4 | 6 | 12 | 11 | 2 | 5 | 3 |
5 | 6 | 12 | 7 | 1 | 5 | 15 | 13 | 8 | 4 | 10 | 9 | 14 | 0 | 3 | 11 | 2 |
6 | 4 | 11 | 10 | 0 | 7 | 2 | 1 | 13 | 3 | 6 | 8 | 5 | 9 | 12 | 15 | 14 |
7 | 13 | 11 | 4 | 1 | 3 | 15 | 5 | 9 | 0 | 10 | 14 | 7 | 6 | 8 | 2 | 12 |
8 | 1 | 15 | 13 | 0 | 5 | 7 | 10 | 4 | 9 | 2 | 3 | 14 | 6 | 11 | 8 | 12 |
В качестве стартового вектора взято нулевое значение, то есть
H1=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.
Подробный пример из описания стандарта
M = 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854
Т.к. длина сообщения равна 256 битам, то нет необходимости дописывать нули. Вычисляем :
- Генерация ключей
K1=0x733D2C20 65686573 74746769 79676120 626E7373 20657369 326C6568 33206D54 K2=0x110C733D 0D166568 130E7474 06417967 1D00626E 161A2065 090D326C 4D393320 K3=0x80B111F3 730DF216 850013F1 C7E1F941 620C1DFF 3ABAE91A 3FA109F2 F513B239 K4=0xA0E2804E FF1B73F2 ECE27A00 E7B8C7E1 EE1D620C AC0CC5BA A804C05E A18B0AEC
- Шифрующее преобразование
S1=0x42ABBCCE 32BC0B1B S2=0x5203EBC8 5D9BCFFD S3=0x8D345899 00FF0E28 S4=0xE7860419 0D2A562D S =0xE7860419 0D2A562D 8D345899 00FF0E28 5203EBC8 5D9BCFFD 42ABBCCE 32BC0B1B
- Перемешивающее преобразование
H2=0xCF9A8C65 505967A4 68A03B8C 42DE7624 D99C4124 883DA687 561C7DE3 3315C034
Вычисляем :
L = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000100
- Генерация ключей
K1=0xCF68D956 9AA09C1C 8C3B417D 658C24E3 50428833 59DE3D15 6776A6C1 A4248734 K2=0x8FCF68D9 809AAC9C 3C8C3B41 C7658C24 BB504288 2859DE3D 666676A6 B3A42487 K3=0x4E70CF97 3C8065A0 853C8CC4 57389A8C CABB50BD E3D7A6DE D1996788 5CB35B24 K4=0x584E70CF C53C8065 48853C8C 1657389A EDCABB50 78E3D7A6 EED19867 7F5CB35B
- Шифрующее преобразование
S =0x66B70F5E F163F461 468A9528 61D60593 E5EC8A37 3FD42279 3CD1602D DD783E86
- Перемешивающее преобразование
H3=0x2B6EC233 C7BC89E4 2ABC2692 5FEA7285 DD3848D1 C6AC997A 24F74E2B 09A3AEF7
Вычисляем :
= 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854
- Генерация ключей
K1=0x5817F104 0BD45D84 B6522F27 4AF5B00B A531B57A 9C8FDFCA BB1EFCC6 D7A517A3 K2=0xE82759E0 C278D95E 15CC523C FC72EBB6 D2C73DA8 19A6CAC9 3E8440F5 C0DDB66A K3=0x77483AD9 F7C29CAA EB06D1D7 641BCAD3 FBC3DAA0 7CB555F0 D4968080 0A9E56BC K4=0xA1157965 2D9FBC9C 088C7CC2 46FB3DD2 7681ADCB FA4ACA06 53EFF7D7 C0748708
- Шифрующее преобразование
S =0x2AEBFA76 A85FB57D 6F164DE9 2951A581 C31E7435 4930FD05 1F8A4942 550A582D
- Перемешивающее преобразование
H4=0xFAFF37A6 15A81669 1CFF3EF8 B68CA247 E09525F3 9F811983 2EB81975 D366C4B1
Таким образом, результат хэширования:
H = 0xFAFF37A6 15A81669 1CFF3EF8 B68CA247 E09525F3 9F811983 2EB81975 D366C4B1
Другие примеры
В разделе не хватает ссылок на источники (см. рекомендации по поиску). |
Возможно, примеры не верны. Программа RHash-1.1.8-win32 выдаёт аналогичные результаты, но байты идут в обратном порядке.
M = 0x7365747962203035203D206874676E656C20736168206567617373656D206C616E696769726F206568742065736F70707553 H = 0x0852F5623B89DD57AEB4781FE54DF14EEAFBC1350613763A0D770AA657BA1A47
M = "" H = 0x8D0F49492C91F45A68FF5C05D2C2B4AB78027B9AAB5CE3FEFF5267C49CB985CE
M = "ГОСТ Р 34.11-94" H = 0xB6A83547677B534FEDB3C68BC7207129F7454928554CF2847DD7E30165F1CF30
M = "The quick brown fox jumps over the lazy dog" H = 0x94421F6D370FA1D16BA7AC5E31296529C968047DCA9BF4258AC59A0C41FAB777
Малейшее изменение сообщения в подавляющем большинстве случаев приводит к совершенно другому хэшу вследствие лавинного эффекта. К примеру, при изменении dog на cog получится:
M = "The quick brown fox jumps over the lazy cog" H = 0x45C4EE4EE1D25091312135540D6702E6677F7A73B5DA31E10B8BB7AADAC4EBA3
Примечания
- ↑ European cryptologists attack hash functions (англ.)
- ↑ Leontiev, S., Ed. and D. Shefanovskij, Ed. Using the GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 Algorithms with the Internet X.509 Public Key Infrastructure Certificate and CRL Profile (англ.) (май 2006). — RFC 4491. Дата обращения: 12 июня 2009.
- ↑ Leontiev, S., Ed. and G. Chudov, Ed. Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS) (англ.) (май 2006). — RFC 4490. Дата обращения: 12 июня 2009.
- ↑ Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (декабрь 2008). — Internet-Drafts, work in progress. Дата обращения: 12 июня 2009.
- ↑ S. Leontiev, P. Smirnov, A. Chelpanov. Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (декабрь 2008). — Internet-Drafts, work in progress. Дата обращения: 12 июня 2009.
- ↑ V.Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (апрель 2009). — Internet-Drafts, work in progress. Дата обращения: 12 июня 2009.
Ссылки
- Текст ГОСТ Р 34.11-94
- ГОСТ Р 34.11 — 94. Функция хеширования. Краткий анализ.
- Реализация алгоритма на языке C++ с комментариями
- RHash - консольная Open source утилита, способная вычислять и проверять ГОСТ Р 34.11-94.