Тема 62
Електронен цифров подпис
2. Еднопосочни хеш функции
Хеш функцията е предназначена да компресира подписания документ M до няколко десетки или стотици бита. Хеш функцията h(•) приема като аргумент съобщение (документ) M с произволна дължина и връща хеш стойност h(M)=H с фиксирана дължина. Обикновено хешираната информация е компресирано двоично представяне на основното съобщение с произволна дължина. Трябва да се отбележи, че стойността на хеш функцията h(M) зависи по сложен начин от документа M и не позволява възстановяването на самия документ M.
Хеш функцията трябва да отговаря на редица условия:
- хеш функцията трябва да е чувствителна към всички видове промени в текста M, като вмъквания, емисии, пермутации и т.н.;
- хеш-функцията трябва да има свойството на необратимост, т.е. задачата за избор на документ M', който би имал изискваната стойност на хеш-функцията, трябва да бъде изчислително неразрешима;
- вероятността хеш стойностите на два различни документа (независимо от техните дължини) да съвпаднат трябва да е незначителна.
Повечето хеш функции са изградени на базата на еднопосочна функция f(•), която произвежда изходна стойност с дължина n, когато са дадени две входни стойности с дължина n. Тези входове са изходен блок M и хеш стойността Hi-1 на предишния блок от текст (фиг. 1):
Хеш-стойността, изчислена при въвеждане на последния блок от текст, става хеш-стойността на цялото съобщение M.
Фиг. 1. Изграждане на еднопосочна хеш функция
В резултат на това еднопосочната хеш функция винаги генерира изход с фиксирана дължина n (независимо от дължината на входния текст).
Защитен хеш алгоритъм SHA
SHA защитен алгоритъм за хеширане(Secure Hash Algorithm) е разработен от NIST и US NSA като част от стандарта за сигурно хеширане SHS (Secure Hash Standard) през 1992 г. Алгоритъмът за хеширане SHA е проектиран да се използва заедно с алгоритъма за цифров подпис DSA.
Когато се въведе съобщение M с произволна дължина, по-малка от 264 бита, алгоритъмът SHA генерира 160-битово изходно съобщение, наречено Message Digest (MD). След това това обобщено съобщение се използва като вход към алгоритъма DSA, който изчислява цифровия подпис на съобщението M. Цифровото подписване на обобщеното съобщение, а не на самото съобщение, подобрява ефективността на процеса на подписване, тъй като обобщеното съобщение обикновено е много по-кратко от самото съобщение.
Същото обобщено съобщение трябва да бъде изчислено от потребителя, който проверява получения подпис, използвайки полученото съобщение M като вход към алгоритъма SHA.
Алгоритъмът за хеширане на SHA се нарича защитен, защото е проектиран по такъв начин, че е изчислително невъзможно да се възстанови съобщение, което съответства на даден дайджест, както и да се намерят две различни съобщения, които дават един и същ дайджест. Всяка промяна в съобщението по време на транзит е много вероятно да промени дайджеста и полученият цифров подпис няма да премине проверката.
Нека разгледаме по-подробно работата на алгоритъма за хеширане на SHA. Първо, оригиналното съобщение M е подплатено, така че да стане кратно на 512 бита. Подпълването на съобщението се извършва по следния начин: първо се добавя единица, след това толкова нули, колкото е необходимо, за да се получи съобщение, което е 64 бита по-кратко от кратно на 512, и накрая се добавя 64-битово представяне на дължината на оригиналното съобщение.
Пет 32-битови променливи се инициализират вформа:
A \u003d 0 x 6 7 4 5 2 3 0 1
B \u003d 0 x E F C D A B 8 9
C \u003d 0 x 9 8 V A D C F E
D = 0 x 1 0 3 2 5 4 7 6
E \u003d 0 x C 3 D 2 E 1 F 0
След това започва основният цикъл на алгоритъма. Той обработва 512 бита от съобщението на свой ред за всички 512-битови блокове, налични в съобщението. Първите пет променливи A, B, C, D, E се копират в други променливи a, b, c, d, e:
Основният цикъл съдържа четири цикъла по 20 операции всеки. Всяка операция изпълнява нелинейна функция на три от петте променливи a, b, c, d, e и след това извършва изместване и добавяне.
Алгоритъмът SHA има следния набор от нелинейни функции:
ft (X, Y, Z) = (X Ù Y) Ú (( Ø X) Ù Z) за t = 0,19,
ft (X, Y, Z) =X Å Y Å Z за t =20. 39,
ft (X, Y, Z) = (X Ù Y) Ú (X Ù Z) Ú (Y Ù Z) за t = 40,59,
ft (X, Y, Z) = X Å Y Å Z за t = 60,79,
където t е номерът на операцията.
Алгоритъмът също така използва четири константи:
Kt \u003d 0x5A827999 за t \u003d 0,19,
Kt \u003d 0x6ED9EVA1 за t \u003d 20. 39,
Kt = 0х8F1ВВСДС за t = 40,59,
Kt = 0xCA62C1D6 за t = 60,79.
Блокът на съобщението се преобразува от шестнадесет 32-битови думи (M0.M15) в осемдесет 32-битови думи (W0.W79), като се използва следният алгоритъм:
където t е номерът на операцията (за t = 1,80),
Wt - t-ти разширен подблок на съобщението,
Като се има предвид въведената нотация, основният цикъл от осемдесет операции може да се опише, както следва:
Схемата за изпълнение на една операция е показана на фиг.2.
След края на основния цикъл стойностите a, b, c, d и e се добавят съответно към A, B, C, D и E и алгоритъмът продължава да обработва следващия 512-битов блок данни. окончателен изходсе формира като конкатенация на стойностите A, B, C, D и E.
Фиг.2. Схема за изпълнение на една операция на SHA алгоритъма
Тъй като алгоритъмът SHA произвежда 160-битова хеш стойност, той е по-устойчив на атаки с груба сила и атаки за рожден ден от повечето други хеш алгоритми, които генерират 128-битови хеш стойности.
Еднопосочни хеш функции, базирани на симетрични блокови алгоритми
Еднопосочна хеш функция може да бъде изградена с помощта на симетричен блоков алгоритъм. Най-очевидният подход е да се криптира съобщението M с блоков алгоритъм в режим CBC или CFF, като се използва фиксиран ключ и някакъв вектор за инициализация IV. Последният блок на шифрован текст може да се разглежда като хеш стойността на съобщението M. С този подход не винаги е възможно да се конструира защитена еднопосочна хеш функция, но винаги е възможно да се получи кодът за удостоверяване на съобщението (MAC).
По-сигурна версия на хеш функцията може да бъде получена чрез използване на блока за съобщения като ключ, предишната хеш стойност като вход и текущата хеш стойност като изход. Истинските хеш функции са проектирани да бъдат още по-сложни. Дължината на блока обикновено се определя от дължината на ключа, а дължината на хеш стойността е същата като дължината на блока.
Фиг.3. Схема за генериране на обобщена хеш функция
Тъй като повечето блокови алгоритми са 64-битови, някои хеширащи схеми са проектирани така, че хеш-стойността да е два пъти по-голяма от дължината на блока.
Ако приемем, че получената хеш функция е правилна, сигурността на хеш схемата се основава на сигурността на основния блоков алгоритъм. Показана е схема за хеширане, при която дължината на хеш стойността е равна на дължината на блокана фиг.3. Работата й се описва с изразите:
където In - някаква произволна начална стойност; A, B и C могат да приемат стойностите Mi, Hi-1, (Mi Å Hi-1) или да бъдат константи.
Таблица 1 Схеми за защитено хеширане, при които хеш-стойността е равна на дължината на блока
Съобщението M се разделя на блокове Mi с приета дължина, които се обработват един по един.
Трите различни променливи A, B и C могат да приемат една от четири възможни стойности, така че по принцип има 64 варианта на обща верига от този тип. От тях 52 опции са или тривиално слаби, или несигурни. Останалите 12 сигурни схеми за хеширане са изброени в таблица 1.
Първите четири схеми за хеширане, които са защитени срещу всички атаки, са показани на фигура 4.
Фиг.4. Четири сигурни схеми за хеширане
Българският стандарт ГОСТ Р 34.11-94 определя алгоритъма и процедурата за изчисляване на хеш функцията за всяка последователност от двоични знаци, използвани вкриптографски методи за обработка и защита на информация. Този стандарт се основава на алгоритъма за блоково криптиране GOST 28147-89, въпреки че по принцип може да се използва друг алгоритъм за блоково криптиране с 64-битов блок и 256-битов ключ.
Тази хеш функция генерира 256-битова хеш стойност.
Функцията за компресиране Hi = f(Mi, Hi-1) (двата операнда Mi и Hi-1 са 256-битови стойности) се дефинира, както следва:
1. Генерират се 4 криптиращи ключа Kj, j = 1. 4, чрез линейно смесване на Мі, Ні-1 и някои константи Сj.
2. Всеки ключ Kj се използва за криптиране на 64-битови поддуми hі на думата Hi-1 в режим на проста замяна: Si = EKj(hj).
Получената последователност S4, S3, S2, S1, дълга 256 бита, се съхранява във временната променлива S.
3. Стойността на Hi е сложна, макар и линейна функция на смесване на S, Mi и Hi-1.
При изчисляване на крайната хеш стойност на съобщението M се вземат предвид стойностите на три свързани променливи:
Hn - хеш стойност на последния блок съобщение;
Z-стойност на контролна сума, получена чрез събиране по модул 2 на всички блокове съобщения;
L е дължината на съобщението.
Тези три променливи и подплатеният последен блок M' на съобщението се комбинират в крайната хеш стойност, както следва:
Тази хеш функция е дефинирана от ГОСТ Р 34.11-94 за използване заедно с българския стандарт за електронен подпис.