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

UptoLike

ВУЗ: 

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

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

Рубрика: 

85
ключndnCCДM
d
−== ),), ((mod)(
n)(d,
. Оба эти преобразова-
ния легко выполнить за
)(log0
2
n
операций.
Если теперь ключ (
e, n) преобразования зашифрования
сделать открытым, а параметр
d держать в секрете, то восста-
новление исходного текста
M из зашифрованного текста С даже
при известном алгоритме зашифрования потребует решения
трудной задачи вычисления функции обратной к функции за-
шифрования т.е. вычисления корня степени
e по модулю n. Это
позволяет использовать принцип открытого шифрования, когда
преобразование расширения держится в секрете. В этом случае
(
e,n) - открытый ключ, а - (d,n) - секретный ключ. Более подроб-
но мы рассмотрим этот вопрос при описании блочной криптоси-
стемы
RSA.
Группы подстановок.
При построении криптографических систем широкое при-
менение получили так называемые перестановочные многочле-
ны конечных полей
q
F , которые индуцируют перестановки
элементов конечного поля
q
F и, следовательно, соответствуют
элементам симметрической группы
q
S , т.е. группы всех подста-
новок на множестве из
q элементов.
Дадим определение перестановочного многочлена конеч-
ного поля
q
F и приведем ряд теорем, позволяющих выяснить
является ли данный многочлен перестановочным или нет.
Определение. Многочлен
][)( xFxf
q
∈
называется пере-
становочным многочленом поля
q
F , если соответствующая
ему полиномиальная функция
qq
FFf →:
, отображающая эле-
мент поля
q
Fc ∈
в элемент
q
Fcf ∈)(
, является перестановкой
элементов поля
q
F .
Если
)(
x
f
является перестановочным многочленом, то,
очевидно, для каждого элемента
q
Fa ∈
уравнение
a
x
f
=
)(
86
имеет одно решение в поле
q
F .
Заметим, что операция приведения некоторого многочлена
g(x) по модулю
)(
x
f
обозначается
)(mo
d
)(
f
g
и ее результа-
том является остаток
)(
x
r
от деления )(
x
g
на )(
x
f
.
Тогда можно установить критерий того, что данный мно-
гочлен является перестановочным. Для этого потребуется сле-
дующая лемма.
Лемма. Пусть
110
,...,,
−q
aaa
элементы поля
q
F
. Тогда сле-
дующие два условия эквивалентны:
1.
110
,...,,
−q
aaa
все различны;
2.
∑
−
=
⎩
⎨
⎧
=
=
=
1
0
1-qt 1,-
2-q0,1,..., t,0
q
i
t
i
для
для
a
.
С учетом этой леммы можно получить критерий Эрмита,
того, что данный многочлен является перестановочным.
Критерий Эрмита. Пусть р - характеристика поля
q
F .
Тогда многочлен
][)( xFxf
q
∈
является перестановочным мно-
гочленом поля
q
F в том и только в том случае, если выполня-
ются следующие два условия:
1. Многочлен
)(
x
f
имеет ровно один корень в
q
F .
2. Для каждого целого
t, такого, что
)(mo
d
0 21 p
t
иq
t
≡
/
−
≤≤
, результат приведения многочлена
t
xf )(
по модулю
)( xx
q
−
имеет степень
2
−
≤
qd
.
Отсюда вытекает важное
следствие: Если число 0>d
является делителем числа
q -1, то над полем
q
F не существует
перестановочного многочлена степени
d.
В теории конечного поля имеются и другие критерии того,
что данный многочлен является перестановочным и с ними
можно ознакомится в соответствующей литературе.
Пользуясь критерием Эрмита, можно получить все пере-
становочные многочлены произвольной фиксированной степени

Страницы