Файл: Контрольная работа Вариант 1 Обзор развития криптографической защиты информации Фамилия Чудинов.docx

Недостатком алгоритма является то, что в случае большого количества нулей в младших или в старших разрядах ключа, результат может содержать много нулей даже в средних разрядах.

Алгоритм умножения

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

Первой операцией, которая выполняется в этом алгоритме, является умножение ключа x на константу C с отбрасыванием старших разрядов произведения, не уместившихся в разрядной сетке. Цель этой операции – рассеять ключи по всему множеству допустимых целых чисел. Вторая операция – переход от диапазона всех целых чисел к диапазону индексов хеш-таблицы. Для этого выполняют умножение числа на размер хеш-таблицы N, но из произведения выделяют только те разряды, которые выходят за разрядную сетку целых чисел. Очевидно, что число, образованное этими разрядами, будет находиться в пределах от 0 до N–1, причем, если результат первого умножения был равномерно рассеян по множеству целых чисел, то значение хеш-функции будет так же хорошо рассеяно по множеству индексов.

Описанные действия можно записать в виде формул с использованием операций mod и div, однако это намеренно не сделано, чтобы не создавать соблазна использовать mod и div на практике. На самом деле, все гораздо проще, особенно если размер хеш-таблицы N = 2^k. При выполнении умножения на константу C старшие разряды произведения просто отбрасываются, а вместо умножения на N с выделением переполняющих разрядов выполняют просто сдвиг числа вправо, так, чтобы оставить только k старших разрядов.

Как видно из рисунка, весь алгоритм сводится к одной операции умножения и одному сдвигу на m – k разрядов вправо.

Важную роль в алгоритме умножения играет константа-множитель C. В литературе можно найти рекомендации по выбору значения C, основанные на глубоком анализе алгоритма с использованием методов теории чисел. Приведем здесь лишь несколько простых советов, позволяющих избежать грубых ошибок при выборе. (Предполагается, что размер хеш-таблицы N = 2^k.):

· значение C обязательно должно быть нечетным, а еще лучше – простым числом;

· не следует выбирать слишком маленькие значения; лучше, если C, по крайней мере, не меньше 1000;

---

· нежелательно также использовать числа, лишь на несколько единиц отличающиеся от одной из степеней двойки, например, такие, как 2 047 (почти равно 2¹¹ = 2 048) или 4 099 (близко к 2¹² = 4 096).

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

Недостаток алгоритма – дополнительный расход памяти на организацию списков, при том, что значительная часть хеш-таблицы может пустовать. Еще хуже то, что выделение динамической памяти (по new или malloc) – довольно медленная операция. Достоинства – отсутствие скучивания и простота удаления записей. Кроме того, в этом алгоритме невозможно переполнение таблицы, наблюдается только снижение скорости поиска при большом числе записей.

Алгоритм Уильямса

Он представляет собой компромиссное решение: записи с одинаковым h(x) организованы в линейные списки, но эти списки размещаются не в динамической памяти, а в основном массиве хеш-таблицы. При этом элементы массива должны, помимо ключа и данных, содержать еще поле связи, в котором указан индекс следующего элемента списка. Кроме того, для ускорения поиска свободного места при вставке используется переменная R, которая при пустой таблице равна N, а затем всегда указывает на позицию в массиве, начиная с которой свободного места наверняка нет. При вставке новой записи, если занята позиция h(k), свободное место ищется вниз от позиции R, а R уменьшается, получая значение индекса найденной позиции. Удаление записей нежелательно, а если оно все же происходит и номер удаляемой записи
i ³ R, то переменной R следует присвоить значение i+1.

Заключение

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

---

СПИСОК ЛИТЕРАТУРЫ

1.Хоффман Л.Дж. Современные методы защиты информации / Пер. с англ. - М: Сов. радио, 1980.

2.Мельников В.В. Защита информации в компьютерных системах. - М.: Финансы и статистика; Электронинформ, 1997.

3.https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82 %D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F

4.http://sec4all.net/modules/myarticles/article.php?storyid=605

5.http://sumk.ulstu.ru/docs/mszki/Zavgorodnii/

---