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

UptoLike

ВУЗ: 

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

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

Рубрика: 

17
)()
/
( C
P
C
M
P
= ,
т.е. вероятности получения конкретного шифра С, при условии
что был зашифрован текст М, одинаковы для всех М.
Используя то факт, что уменьшение объема известных све-
дений может лишь увеличить неопределенность, т.е. энтропию,
получим
(/) (,/) (/) (/,)
(/) ()
HM C HMK C HK C HM CK
HK C HK
≤
=+ =
=≤
(Здесь естественно
0),
/
(
=
K
C
M
H
, т.к. ключ секрет-
ный). Другими словами неопределенность секретного ключа
должна быть не меньше, т.е.
≥ неопределенности шифруемого с
его помощью текста отсюда можно сделать вывод, что размер
ключа
k
не должен быть меньше размерности открытого текста
М. Такое условие является очень жестким, т.е. это практически
очень неудобно (слишком большие по размеру секретные ключи
равные длинам передаваемых сообщений). Примером совер-
шенно секретной криптосистемы является рассмотренная на
прошлой лекции система Вернама когда
{}
nn
KMKMKMC
⊕
⊕=
⊕
=
,...,
11
,
при случайном равновероятном выборе ключа
n
kkk ,...,
1
= и
n
i
kP
−
= 2)(
для всех i=1,…,n, откуда
n
MCP
−
= 2)/(
для всех С и М т.е. выполняется условие совер-
шенно секретной системы.
Помимо теоретической стойкости криптосистемы рассмат-
ривают ее
практическую стойкость. Для этого вводят рабочую
характеристику
W(n) - среднее количество работы (измеренное
в удобных единицах), требуемое для нахождения ключа
k
на
основе знания
n знаков шифротекста с помощью наилучшего
криптоаналитического алгоритма. Обычно криптосистемы оце-
нивают с помощью достигнутой оценки рабочей характеристики
W( ∞ ) при использовании наилучшего из известных методов
дешифрования. Криптосистемы называются
практически
стойкими
если они не могут быть вскрыты в течение реального
времени (
Cons
W ≥∞)( ) всеми общедоступными методами.
18
На практике используют именно это понятие стойкости крипто-
систем. По сути дела из этого определения можно сделать вывод
о том, что проблема создания практически стойких криптоси-
стем или шифров может быть сведена к проблеме нахождения
наиболее сложных задач, удовлетворяющих определенным ус-
ловием. Можно составить шифр таким
образом, чтобы раскры-
тие его было эквивалентно (или включало в себя, решение неко-
торой задачи, про которую известно, что для ее решения требу-
ется определенный (желательно большой объем) работы). По-
этому стойкость криптосистемы можно определить вычисли-
тельной сложностью алгоритмов, применяемых криптоаналити-
ками для шифрования. Такой подход к определению стойкости
криптосистем, основанный
на понятии вычислительной сложно-
сти криптоаналитических алгоритмов (в отличие от информаци-
онно - теоретического, рассмотренного выше) основан не на во-
просе о том возможно ли извлечь информацию об открытом тек-
сте из анализа шифротекста, а на вопросе о том, осуществимо ли
это в приемлемое время. Этот подход позволяет достичь свойст-
ва
совершенной секретности криптосистемы даже для случаев,
когда используется секретные ключи значительно меньше по
размерам чем длина открытого шифруемого текста.
Вычислительная сложность алгоритма в свою очередь
измеряется его временной
τ
и емкостной S сложностями в зави-
симости от размера
n входных данных.
Временная сложность - это время, затрачиваемое алго-
ритмом для решения задачи, рассматриваемое как функция раз-
мера задачи или количества входных данных.
Емкостная сложность - это емкость необходимой ма-
шинной памяти. Поведение этих сложностей в пределе при уве-
личении размера задачи называется
асимптотическими слож-
ностями. Эти сложности алгоритма определяют в итоге размер
задачи, которую можно решить этим алгоритмом.
Если при данном размере задачи в качестве меры сложно-
сти берётся наибольшая из сложностей по всем входам этого
размера, то она называется
сложностью в худшем случае. Если
в качестве меры сложности берется «средняя» сложность по

Страницы