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

UptoLike

ВУЗ: 

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

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

Рубрика: 

83
или «справа налево»
)mod()(...)(
1
1
1
0
22
naaa
k
k
x
x
x
−
−
⋅⋅⋅
для числа
x при его двоичном разложении в виде
∑
−
=
=
1
0
2
k
i
i
i
xx
.
Даже при больших числах
x из интервала (1, n) вычисление
)(mod)( naxf
x
=
можно осуществить за
][log0
2
n
операций. Об-
ратная к этой функции - операция вычисления дискретного ло-
гарифма
x: по данным a и y найти такое целое x, что
yna
x
=)(mod
. До настоящего времени не известно эффектив-
ных алгоритмов решения этой задачи. Известно лишь, что слож-
ность вычисления дискретного логарифма
x эквивалента слож-
ности разложения целого числа на произведение простых чисел
и оценивается как
)2(0
n
,т.е. экспоненциальная оценка времен-
ной сложности.
На основе такой показательной односторонней функции
Диффори и Хеллман разработали так называемую криптографи-
ческую схему открытого распределения ключей, о которой более
подробно поговорим на следующих лекциях.
В качестве односторонней функции Кнут Д. предложил
использовать функцию вида
2121
, pиpгдеppa ⋅=
простые
числа. Идея здесь заключается в том, что произведение двух
простых чисел вычислить достаточно просто, а вот разложение
числа
a на сомножители
21
pиp
достаточно трудная задача.
В ряде случаев в качестве односторонней функции предла-
гается использовать известную задачу о рюкзаке. Напомним, что
эта задача имеет следующую формировку: дано множество
n це-
лых чисел
n
aa ,...,
1
и целое число S, требуется определить су-
ществует - ли множество чисел
i
a ni
≤
≤1 , такое что их сумма
равна числу
S. Эта задача принадлежит к числу NP полных за-
дач и имеет экспоненциальную временную сложность
)2(0
n
.
Следует отметить, что использование односторонних
функций в чистом виде для зашифрования информации не имеет
84
смысла, так как никто, даже законный адресат не сможет рас-
шифровать шифротекст
)(
M
f
c
=
, полученный с ее помощью.
Однако идея, лежащая в основе построения таких функций, мо-
жет быть использована для построения так называемых одно-
сторонних функций с секретом, которые уже имеют практиче-
ский смысл.
Рассмотрим принципы построения односторонних функ-
ций с секретом на примере степенной функции вида
)(mod)( nxxf
m
=
.
Определение. Односторонней функцией с секретом на-
зывается зависящая от параметра
К функция
)(xf
k
, такая, что
при известном
К можно найти полиномиальные алгоритмы
k
ДиE
k
, позволяющие легко вычислить как
)(xf
k
, так и об-
ратную к ней функцию
)(
1
yf
k
−
для всех x из области определе-
ния функции
)(xf
k
. При этом нахождение
)(
1
yf
k
−
вычисли-
тельно неосуществимо без знания секретного параметра
К даже
при известном алгоритме
k
E
.
Степенная функция
)(mod)( nxyxf
m
==
достаточно лег-
ко, за
)(log0
2
n
операций может быть вычислена при известных
m и n. Преобразование возведения в степень
)(mod nxy
m
=
на-
зывается вычислением корня
m степени по модулю n. В настоя-
щее время вычисление такого
x, что
)(mod nxy
m
=
при извест-
ных
y,m,n относится классу трудных задач. Основная идея ис-
пользования односторонних функций с секретом сводится к сле-
дующему.
Получение шифрованного текста С из исходного текста М
осуществляется путем использования указанной степенной
функции в виде:
)(mod)(
),(
nMMEC
e
ne
==
, где e,n - ключ
преобразования зашифрования.
При расшифровании открытый текст
M восстанавливается
путем использования преобразования расшифрования на базе
этой же функции но с другой степенью
d в качестве ключа:

Страницы