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

UptoLike

ВУЗ: 

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

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

Рубрика: 

81
вопрос о свойствах линейных рекуррентных последовательно-
стей. Если суммировать все результаты, полученные при иссле-
довании этого вопроса в рамках теории конечного поля и других
прикладных дисциплин, то можно сказать следующие:
1. Наиболее важными и интересными свойствами обладают
ЛРП максимального периода, формируемые характеристически-
ми многочленами, являющиеся нормированными неприводимы-
ми многочленами над
соответствующими полями
q
F .
2.ЛРП максимальной длины имеют равномерный спектр и,
следовательно, статистическую равномерность
3. Предельно большая длина периода
1−
k
q
.
4. Отсутствие скрытой периодичности.
Отмеченные свойства делают ЛРП эффективным инстру-
ментом для создания генераторов псевдослучайных последова-
тельностей, на базе которых строится широкий класс поточных
криптосистем.
82
9. Дополнительные математические
элементы криптографии.
Односторонние функции.
Понятие односторонней функции впервые было введено в
работе Нидхема (Needham R.M.) о защите входа в вычислитель-
ные системы.
Определение. Функция )(
x
f
называется односторонней,
если для всех
x из ее области определения легко вычислить
)(
x
f
y =
, но почти для всех y из ее области значений нахожде-
ние
x, для которого
)(
x
f
y
=
, вычислительно неосуществимо.
В данном определении фраза «почти для всех
y» необхо-
дима, т.к. можно легко вычислить и запомнить согласно первой
части определения целую таблицу значений
)(),...,()(
2211 nn
xfyxfyxfy
=
=
=
, если окажется, что вы-
бранное значение
i
y принадлежит этой таблице, то и соответст-
вующий
i
x можно легко определить. Фраза «вычислительно не-
осуществимо» означает с точки зрения теории сложности, что
неосуществимо за полиномиальное время, которое характеризу-
ет решаемые задачи.
До сих пор не доказано, что односторонние функции суще-
ствуют. Показано, что проблема существования односторонних
функций эквивалентна известной нерешенной проблеме совпа-
дения задач классов
Р и NP.
Тем не менее, предложено много функций, которые похо-
жи на односторонние.
В качестве возможной односторонней функции Дж. Гилл
предложил использовать показательную функцию следующего
вида:
)(mod)( naxf
x
=
, где a - (основание) принадлежит интер-
валу (
1, n-1), а умножение ведется по модулю n. Значение
)(mod na
x
вычисляется достаточно эффективно с помощью из-
вестной схемы Горнера «слева на право»
)(mod)...))((()(mod
0
1
21
222
naaaana
x
x
xx
x
kk
⋅⋅⋅⋅=
−−

Страницы