русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Однонаправленная ХЕШ-функция


Дата добавления: 2013-12-23; просмотров: 538; Нарушение авторских прав


 

Хеш-функция предназначена для сжатия подписываемого документа до 10-100 бит

h-функция ( h(.) ) принимает в качестве аргумента документ М произвольной длины и возвращает Хеш-значение фиксированной длины.

Обычно хешированная информация является сжатым 2-ным представлением произвольной длины.

Значение h(M) сложным образом зависит от документа М и не позволяет определить этот самый документ по значению функции.

h-функция должна соответствовать условиям:

- Чувствительна к любым изменениям в М

- Обладать свойством необратимости, то есть задачи подбора некоего документа М’, который обладал бы требуемым значением h-функции была бы вычислительно неразрешима.

- Вероятность того, что значение h-функции 2 различных документов совпадут должна быть ничтожно мала.

Большинство h-функций строится на основе однонаправленной функции f, которая образует выходное значение длиной M при заданных 2х входных значениях длиной N. Этими входными значениями является n-блок исходного текста M(i) и хеш-значение h-1 предыдущего блока.

H(i) = f (Mi, Hi-1 )

Хешированное значение вычисляется при вводе последовнего блока текста, оно становится h-значением всего сообщения M.

В результате однонаправленная h-функция всегда формирует выход фиксированной длины N, независимо от длины входного текста.

Основы построения h-функции - h(.):

 

В ХОДНОЙ ПОТОК
k-n бит n
СФ
k-n бит n  
СФ  
k-n бит n  
НЗ

 

 


Общепринятым построением h(.) является интерактивная последовательная схема.

Ядром алгоритма является преобразование k бит в n бит, где n – разрядность результата хеширования, а k >> n производное значение.

Базовое преобразование должно обладать всеми свойствами h(.), то есть необратимостью и невозможностью инвариантного изменения входных данных. Хеширование производится с помощью промежуточной вспомогательной переменной разрядностью n, в качестве которой выбирают произвольное, всем известное значение, например a.



Входные данные разбиваются на блоки по k-n бит.

На каждой итерации хеширования со значением промежуточной величины, полученной из предыдущей итерации объединяется очередная k-n битная порция входных данных и над получившимся k блоком производятся преобразования.

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

Кроме более полупроходных алгоритмов хеширования существуют многопроходные.

 

Однонаправленные h(.) на основе суммирующих блочных элементов.

Однонаправленные h(.) можно построить используя симметричный блочный алгоритм.

Наиболее явный подход: шифровать сообщение М посредством блочного алгоритма CBC, CFB с помощью фиксированного ключа и некоторого вектора инициализации IV.

 

ШИФРАТОР
КЛЮЧ
+
С
Hi
B
A

 


Начальное значение – H0

Случайное значение – Iн

H0=Iн

+
Hi = EA(B) C

+
ABC → Mi, Hi-1, (Mi Hi-1), const *

 

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

 

Реальные h(.) проектируются значительно более сложно. Длина блока обычно определятеся длиной ключа, а длина h-значения совпадает с длиной блока. Схема h-значения, у которой длина h-значения = длине блока.

 

ABC могут принимать значения *

Переменные A, B, C могут принимать любое из 4-х значений. Общее число значений 64. Из них 52 варианта тривиальны (слабые). Из остальных 12 правильно 4:

 

Ш
К
+
Hi-1
Mi-1
Hi
Ш
К
+
Hi-1
Mi-1
Hi
+
Ш
К
+
Hi-1
Mi-1
Hi
+
+
Ш
К
+
Hi-1
Mi-1
Hi
+

 


Недостатком h(.), спроектированных на основе алгоритмов является заниженная скорость работы.

 



<== предыдущая лекция | следующая лекция ==>
Электронная цифровая подпись (ЭЦП) | Алгоритм ЦП RSA


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.