Материал: MSZI_2003
Математика
разделения
секрета
351
Определение
18.3
Матрица
V
задает
БД
-
совершенную
СРС
,
реализующую
структуру
доступа
Г
,
если
||V
A
∪
0
|| = ||V
A
|| × ||V
0
||
δГ
(
А
)
,
(18.4)
где
δ
Г
(
А
) = 0
,
если
А
∈
Г
,
и
δ
Г
(
А
) = 1
в
противном
случае
.
Это
определение
отличается
от
определений
1
и
2
тем
,
что
на
неразрешенные
множе
-
ства
А
накладываются
довольно
слабое
условие
,
а
именно
,
если
множество
строк
V
с
данными
значениями
координат
из
множества
А
непусто
,
то
все
возможные
значения
секрета
встречаются
в
нулевой
координате
этих
строк
(
без
требований
“
одинаково
час
-
то
”
как
в
комбинаторном
определении
2
или
же
“
с
априорной
вероятностью
”
как
в
веро
-
ятностном
определении
1).
Легко
видеть
,
что
матрица
любой
совершенной
вероятност
-
ной
СРС
задает
БД
-
совершенную
СРС
,
но
обратное
неверно
.
Для
произвольной
комбинаторной
СРС
,
задаваемой
матрицей
V
,
определим
на
мно
-
жествах
А
⊆
{0, 1, …, n}
функцию
h(A) = log
q
||V
A
||,
где
q = |S
0
|
.
Легко
проверить
,
что
max{h(A), h(B)}
≤
h(A
∪
B)
≤
h(A) + h(B)
для
любых
множеств
А
и
В
,
а
условие
(184)
может
быть
переписано
в
виде
h
q
(V
A
∪
0
) = h
q
(V
A
) +
δ
Г
(
А
) h
q
(V
0
)
Лемма
.
Для
любой
БД
-
совершенной
СРС
если
А
∉
Г
и
{A
∪
i}
∈
Г
,
то
h(i)
≥
h(0)
.
Доказательство
.
По
условиям
леммы
h(A
∪
0) = h(A) + h(0)
и
h(A
∪
i
∪
0) = h(A
∪
і
)
.
Следовательно
,
h(A) + h(i)
≥
h (A
∪
і
) = h (A
∪
і
∪
0)
≥
h(A
∪
0) = h(A) + h(0)
Так
мы
предполагаем
,
что
все
точки
і
∈
{1, …, n}
существенные
,
т
.
е
.
для
любого
і
найдется
подмножество
А
такое
,
что
А
∉
Г
и
{A
∪
і
}
∈
Г
,
то
из
леммы
вытекает
Следствие
.
Для
любой
БД
-
совершенной
СРС
|S
i
|
≥
|S
0
|
для
всех
і
= 1, ..., n
.
Следствие
означает
,
как
отмечалось
выше
,
что
для
совершенных
СРС
“
размер
”
про
-
екции
не
может
быть
меньше
“
размера
”
секрета
.
Поэтому
БД
-
совершенная
СРС
называ
-
ется
идеальной
,
если
|S
i
| = |S
0
|
для
всех
і
= 1, ..., n
.
Замечание
.
Неравенство
|S
i
|
≥
|S
0
|
справедливо
и
для
совершенных
вероятностных
СРС
,
поскольку
их
матрицы
задают
БД
-
совершенные
СРС
.
Естественный
вопрос
состоит
в
том
,
для
каких
структур
доступа
Г
существуют
реа
-
лизующие
их
идеальные
(
вероятностные
или
комбинаторные
)
СРС
.
Как
уже
отмеча
-
лось
,
наилучший
на
сегодняшний
день
ответ
использует
слово
матроид
.
Напомним
определение
матроидов
и
некоторые
их
основные
свойства
.
Матроидом
называется
конечное
множество
Х
и
семейство
I
его
подмножеств
,
на
-
зываемых
независимыми
(
остальные
множества
называются
зависимыми
),
если
выпол
-
нены
следующие
свойства
:
352
Глава
18.
Криптографическая
защита
∅
∈
I;
(18.5.1)
Если
A
∈
I
и
B
⊂
A
,
то
B
∈
I
;
(18.5.2)
Если
A
,
B
∈
I
и
|A| = |B| + 1
,
то
существует
a
∈
A\B
такое
,
что
a
∪
B
∈
I
. (18.5.3)
Пример
18.4.
Множество
Х
—
это
множество
векторов
в
некотором
линейном
век
-
торном
пространстве
,
а
независимые
подмножества
—
это
линейно
независимые
под
-
множества
векторов
.
Собственно
с
этого
примера
и
началась
теория
матроидов
,
вначале
как
попытка
дать
аксиоматическое
определение
линейной
независимости
векторов
через
“
внутренние
свойства
”,
т
.
е
.
не
апеллируя
к
понятию
вектора
.
К
счастью
,
попытка
не
удалась
,
так
как
нашлись
матроиды
,
не
представимые
как
линейные
(
т
.
е
.
как
системы
векторов
),
а
сама
теория
матроидов
разрослась
далеко
за
пределы
линейной
алгебры
.
Пример
18.5. (
матроид
Вамоса
)
.
Рассмотрим
следующее
множество
:
Х
= {1, 2, 3, 4,
5, 6, 7, 8}
и
положим
a = {1, 2}, b = {3, 4}, c = {5, 6}
и
d = {7, 8}
.
Матроид
Вамоса
оп
-
ределяется
как
матроид
,
в
котором
множества
a
∪
c, a
∪
d, b
∪
c, b
∪
d, c
∪
d
,
а
так
-
же
все
подмножества
из
пяти
или
более
элементов
являются
зависимыми
.
Известно
,
что
этот
матроид
не
является
линейным
.
Матроид
также
можно
определить
через
так
называемую
ранговую
функцию
r(A)
мат
-
роида
,
определяемую
как
максимальная
мощность
независимого
подмножества
В
⊆
А
.
Оче
-
видно
,
что
независимые
множества
(
и
только
они
)
задаются
условием
r(A) = |A|
.
Ранговая
функция
матроида
обладает
свойствами
r(A)
∈
Z; r(
∅
) = 0;
(18.6.1)
r(A)
≤
r(A
∪
b)
≤
r(A) + 1;
(18.6.2)
Если
r(A
∪
b) = r (A
∪
c) = r(A)
,
то
r (A
∪
b
∪
c) = r(A)
. (18.6.3)
Обратно
,
пусть
некоторая
функция
r(A)
обладает
свойствами
(18.6).
Назовем
незави
-
симыми
те
множества
А
,
для
которых
r(A) = |A|
.
Тогда
эти
множества
задают
матроид
,
а
функция
r
является
его
ранговой
функцией
.
Возможно
также
определить
матроид
че
-
рез
минимальные
зависимые
множества
,
называемые
циклами
.
Матроид
называется
связным
,
если
для
любых
двух
его
точек
существует
содержащий
их
цикл
.
Теперь
мы
можем
сформулировать
основной
результат
.
Теорема
.
Для
любой
БД
-
совершенной
идеальной
СРС
,
реализующей
структуру
дос
-
тупа
Г
,
независимые
множества
,
определяемые
условием
log|
S0
| ||V
A
|| = |A|
,
задают
связный
матроид
на
множестве
{0, 1,…, n}
.
Все
циклы
этого
матроида
,
содержащие
точку
0
,
имеют
вид
0
∪
А
,
где
А
∈
Г
min
.
Доказательство
теоремы
приведено
в
соответствующей
литературе
и
выходит
за
рам
-
ки
данной
книги
.
Главным
в
доказательстве
теоремы
является
“
проверка
”
целочислен
-
ности
функции
h(A)
.
В
самом
деле
,
h(A)
очевидно
обладает
остальными
свойствами
(6)
Секретность
и
имитостойкость
353
и
,
следовательно
,
при
условии
целочисленности
является
ранговой
функцией
и
задает
матроид
.
Отметим
,
что
из
второй
части
утверждения
теоремы
следует
,
что
разным
идеальным
СРС
,
реализующим
данную
структуру
доступа
Г
,
всегда
соответствует
один
и
тот
же
матроид
,
поскольку
матроид
однозначно
определяется
всеми
циклами
,
проходящими
че
-
рез
фиксированную
точку
.
Тем
самым
,
каждой
идеальной
реализуемой
структуре
досту
-
па
соответствует
однозначно
определенный
матроид
.
В
связи
с
теоремой
возникает
несколько
естественных
вопросов
.
Прежде
всего
,
не
порождают
ли
идеальные
СРС
все
матроиды
?
Нет
,
например
,
матроид
Вамоса
не
может
быть
получен
как
матроид
идеальной
СРС
.
С
другой
стороны
линейные
матроиды
есть
ни
что
иное
,
как
рассмотренные
идеальные
одномерные
линейные
СРС
.
В
связи
с
этим
возникает
вопрос
о
существовании
структуры
доступа
Г
,
которую
невозможно
реализо
-
вать
в
виде
идеальной
одномерной
линейной
СРС
,
но
можно
в
виде
идеальной
много
-
мерной
линейной
СРС
.
Такие
примеры
имеются
,
и
,
значит
,
мы
можем
говорить
о
мно
-
гомерных
линейных
матроидах
как
классе
матроидов
более
общем
,
чем
линейные
.
Итак
,
идеальных
СРС
больше
,
чем
линейных
матроидов
,
но
меньше
,
чем
всех
мат
-
роидов
.
Уточнить
,
насколько
больше
,
представляется
довольно
сложной
задачей
.
В
ча
-
стности
,
существует
ли
идеально
реализуемая
структура
доступа
Г
,
которую
невозмож
-
но
реализовать
как
идеальную
линейную
многомерную
СРС
?
Секретность
и
имитостойкость
Криптографические
преобразования
обеспечивают
решение
двух
главных
проблем
ЗИ
:
проблемы
секретности
(
лишение
противника
возможности
извлечь
информацию
из
канала
связи
)
и
проблемы
имитостойкости
(
лишение
противника
возможности
ввести
ложную
информацию
в
канал
связи
или
изменить
сообщение
так
,
чтобы
изме
-
нился
его
смысл
).
В
случае
телефонной
связи
главной
является
проблема
имитостойкости
,
поскольку
вызванная
сторона
не
может
часто
определить
,
кто
звонит
.
Подслушивание
,
требующее
подключения
к
проводам
,
технически
более
сложно
и
юридически
более
опасно
,
чем
вы
-
зов
корреспондента
и
выдача
себя
за
кого
-
то
другого
.
В
случае
радиосвязи
ситуация
прямо
противоположная
.
Перехват
здесь
является
пассивным
и
сопряжен
с
незначитель
-
ной
юридической
опасностью
,
тогда
как
введение
информации
связано
с
риском
обна
-
ружения
незаконного
передатчика
и
юридического
преследования
.
Проблема
секретности
Проблемы
секретности
и
имитостойкости
между
собой
тесно
связаны
,
поэтому
мето
-
ды
решения
одной
из
них
часто
применимы
для
решения
другой
.
Из
двух
названных
проблем
проблема
секретности
обычно
рассматривается
первой
,
как
более
старая
и
шире
известная
.
Рассмотрим
схему
прохождения
потока
информации
в
криптографической
системе
,
обеспечивающей
секретность
(
рис
. 18.3).
354
Глава
18.
Криптографическая
защита
Рис
. 18.3.
Поток
информации
в
криптографической
системе
,
обеспечивающей
секретность
Отправитель
генерирует
открытый
текст
,
или
шифрованное
сообщение
Р
,
которое
должно
быть
передано
получателю
по
незащищенному
прослушиваемому
каналу
.
Для
того
чтобы
перехватчик
не
смог
узнать
содержания
сообщения
Р
,
отправитель
шифрует
или
кодирует
его
с
помощью
обратимого
преобразования
S
k
и
получает
криптограмму
или
шифрованный
текст
С
= S
k
(P)
.
Получатель
,
приняв
сообщение
С
,
дешифрирует
или
декодирует
его
с
помо
-
щью
обратного
преобразования
S
k
-1
и
получает
исходное
сообщение
S
k
-1
(C) = S
k
-1
[S
k
(P)] =P
Преобразование
S
k
выбирается
из
семейства
криптографических
преобразований
,
на
-
зываемых
криптографической
,
или
общей
,
системой
.
Параметр
,
выбирающий
отдельное
используемое
преобразование
,
называется
клю
-
чом
.
Общая
система
—
это
набор
инструкций
,
аппаратурных
средств
и
программного
обеспечения
ЭВМ
,
с
помощью
которого
можно
зашифровать
и
расшифровать
текст
раз
-
ными
способами
,
один
из
которых
выбирается
с
помощью
конкретного
ключа
.
Говоря
более
формально
,
криптографическая
система
—
это
однопараметрическое
семейство
(S
k
)
к
∈
K
обратимых
преобразований
S
k
:
Р
→
С
из
пространства
Р
сообщений
открытого
текста
в
пространство
С
шифрованных
сообщений
.
Параметр
,
или
ключ
К
,
называется
пространством
ключей
.
Обычно
общая
система
рассматривается
как
общедоступная
.
С
одной
стороны
,
от
-
крытая
для
всех
часть
общей
системы
является
предметом
соглашения
,
а
с
другой
сто
-
роны
,
это
отражает
очень
важное
правило
техники
защиты
:
защищенность
системы
не
должна
зависеть
от
секретности
чего
-
либо
такого
,
что
нельзя
быстро
изменить
в
случае
утечки
секретной
информации
.
Обычно
общая
система
является
некоторой
совокупно
-
стью
аппаратуры
и
программ
,
которую
можно
изменить
только
со
значительной
затра
-
той
времени
и
средств
,
тогда
как
ключ
представляет
собой
легко
изменяемый
объект
.
Поскольку
вся
секретность
сосредоточена
в
секретности
ключа
,
то
его
надо
переда
-
вать
отправителю
и
получателю
по
защищенному
каналу
распространения
ключей
,
та
-
кому
,
как
курьерская
служба
и
т
.
д
.
Проблема
имитостойкости
Безусловная
и
теоретическая
стойкость
355
Теперь
рассмотрим
схему
прохождения
потока
информации
в
криптографической
системе
,
обеспечивающей
имитостойкость
(
рис
. 18.4).
Рис
. 18.4.
Поток
информации
в
криптографической
системе
,
обеспечивающей
имитостойкость
При
решении
проблемы
имитостойкости
противник
может
не
только
видеть
все
криптограммы
,
передаваемые
по
каналу
,
но
может
также
изменять
их
по
своему
жела
-
нию
.
Законный
получатель
защищает
себя
от
обмана
,
дешифрируя
все
полученные
со
-
общения
и
принимая
только
те
сообщения
,
которые
зашифрованы
правильным
ключом
.
Любая
попытка
со
стороны
перехватчика
расшифровать
криптограмму
С
для
полу
-
чения
открытого
текста
Р
или
зашифровать
свой
текст
Р
'
для
получения
приемлемой
криптограммы
С
'
без
получения
ключа
должно
быть
полностью
исключено
.
Если
криптоанализ
невозможен
и
криптоаналитик
не
может
вывести
Р
и
С
или
С
'
из
Р
'
без
предварительного
получения
ключа
,
то
такая
криптографическая
система
являет
-
ся
криптостойкой
.
Безусловная
и
теоретическая
стойкость
Существует
два
принципиально
разных
метода
обеспечения
стойкости
криптографи
-
ческих
систем
против
криптоаналитического
нападения
.
В
некоторых
системах
объем
доступной
криптоаналитику
информации
фактически
недостаточен
для
того
,
чтобы
найти
преобразования
и
дешифрирования
,
причем
данная
ситуация
не
зависит
от
того
,
какие
вычислительные
мощности
имеет
криптоаналитик
.
Система
такого
рода
называется
безусловно
стойкой
.
В
том
случае
,
когда
перехваченный
материал
содержит
достаточно
информации
для
однозначного
решения
криптоаналитической
задачи
,
нет
никакой
гарантии
,
что
это
ре
-
шение
будет
найдено
криптоаналитиком
,
имеющим
определенные
вычислительные
ре
-
сурсы
.
Следовательно
,
цель
разработчика
криптографической
системы
состоит
в
том
,
чтобы
уменьшить
затраты
на
операции
шифрования
и
дешифрирования
,
но
чтобы
в
тоже
время
любая
криптоаналитическая
операция
была
слишком
сложной
и
поэтому
эконо
-
мически
невыгодной
.
Иными
словами
,
необходимо
,
чтобы
задача
криптоанализа
,
о
ко
-
торой
известно
,
что
она
разрешима
при
конечном
объеме
вычислений
,
была
бы
столь
громоздкой
,
что
для
ее
решения
не
хватило
бы
физических
вычислительных
ресурсов
всего
мира
.
Задачу
такого
объема
называют
вычислительно
нереализуемой
,
а
связанную
с
ней
криптографическую
систему
—
вычислительно
стойкой
.