Математические основы криптологии. Галуев Г.А. - 44 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

87
поля
q
F .
Примеры перестановочных многочленов можно получить
на основе следующего простого результата.
Теорема:
1. Каждый линейный многочлен над полем
q
F является
перестановочным многочленом поля
q
F .
2. Одночлен
n
x
является перестановочным многочленом
поля
q
F тогда и только тогда, когда
11)-q(n,
=
НОД
(т.е. чис-
ло
n и q -1 взаимно просты).
Например,
3
x
- перестановочный многочлен поля
q
F , ес-
ли
)3(mo
d
1≡
/
q
т.е.
1
/
3
−
q
.
Перестановочные многочлены поля
q
F , имеющие степень
меньшую чем
q, можно комбинировать друг с другом с помо-
щью операции композиции с последующим приведением по мо-
дулю
)( xx
q
−
. Эту операцию обозначают
>>=<><< )()()(
x
h
x
f
x
g
и под ней понимают
)))(mod(())(( xxxhxgf
q
−≡
.
Множество перестановочных многочленов поля
q
F , сте-
пень которых меньше
q, образуют группу относительно опера-
ции композиции. Эта группа изоморфна симметрической группе
q
S , т.е. группе всех перестановок на множестве из q элементов.
Таким образом, симметрическую группу
q
S , перестановок и ее
подгруппы можно представить в виде групп перестановочных
многочленов.
Например:
Теорема. Если q>2, то многочлен
2
−
q
x
вместе с линейны-
ми многочленами над полем
q
F порождает симметрическую
группу подстановок
q
S .
Математические элементы теории перестановочных мно-
88
гочленов над конечными полями и индуцируемых ими групп
подстановок находит применения при построении блочных
криптосистем для перестановки информационных блоков пере-
даваемых сообщений.
Хеш-функции.
Термин хеш-функция (или функция хеширования) возник
в теории сложности вычислений, где он обозначал функцию, ко-
торая сжимает строку чисел произвольного размера в строку чи-
сел фиксированного размера. Это понятие использовалось в ал-
горитмах поиска данных по значениям хеш-функции от них.
Рассмотрим это понятие применительно к криптографии.
Криптографические хеш-функции делятся на два класса:
с
ключом и без ключа. Значение хеш-функции с ключом может
вычислить лишь тот, кто знает некоторый секретный параметр -
ключ. В литературе она еще называется
МАС - кодами аутенти-
фикации сообщений.
Определение. Хеш-функцией с ключом (зависящей от
ключа) называется функция, имеющая следующие свойства:
1. Описание функции
Н(k,x) должно быть открыто, а сек-
ретная информация должна содержаться только в выборе ключа
k (правило Керкхофа).
2. Аргумент
х функции Н(k,x) может быть строкой чисел
произвольной длины, а значение функции должно быть строкой
чисел фиксированной длины.
3. При любых данных
k и х вычисление Н(k,x) должно
быть быстрым (за полиномиальное время)
4. По любому данному
х должно быть трудно угадать зна-
чение
Н(k,x) с вероятностью большей, чем
n2
1
, где n - число бит
в выходной строке. Должно быть трудно определить ключ
k да-
же по большему числу известных пар
)},(,{ xkHx
i
или вычис-
лить по этой информации
Н(k,x’)для x’≠x
i
.
Хеш-функция без ключа называется МДС - код определе-
ния манипуляции. Эти функции делятся на два класса:
слабые
односторонние хеш-функции и сильные односторонние хеш-

Страницы