Материал: MSZI_2003
Классификация
криптографических
методов
341
Под
шифрованием
в
данном
случае
понимается
такой
вид
криптографического
за
-
крытия
,
при
котором
преобразованию
подвергается
каждый
символ
защищаемого
сооб
-
щения
.
Все
известные
способы
шифрования
разбиты
на
пять
групп
:
подстановка
(
заме
-
на
),
перестановка
,
аналитическое
преобразование
,
гаммирование
и
комбинированное
шифрование
.
Каждый
из
этих
способов
может
иметь
несколько
разновидностей
.
Под
кодированием
понимается
такой
вид
криптографического
закрытия
,
когда
неко
-
торые
элементы
защищаемых
данных
(
не
обязательно
отдельные
символы
)
заменяются
заранее
выбранными
кодами
(
цифровыми
,
буквенными
,
буквенно
-
цифровыми
сочета
-
ниями
и
т
.
д
.).
Этот
метод
имеет
две
разновидности
:
смысловое
и
символьное
кодирова
-
ние
.
При
смысловом
кодировании
кодируемые
элементы
имеют
вполне
определенный
смысл
(
слова
,
предложения
,
группы
предложений
).
При
символьном
кодировании
коди
-
руется
каждый
символ
защищаемого
текста
.
Символьное
кодирование
по
существу
сов
-
падает
с
подстановочным
шифрованием
.
К
отдельным
видам
криптографии
относятся
методы
рассечения
-
разнесения
и
сжа
-
тия
данных
.
Рассечение
-
разнесение
заключается
в
том
,
что
массив
защищаемых
данных
делится
(
рассекается
)
на
такие
элементы
,
каждый
из
которых
в
отдельности
не
позволяет
раскрыть
содержание
защищаемой
информации
.
Выделенные
таким
образом
элементы
данных
разносятся
по
разным
зонам
памяти
или
располагаются
на
разных
носителях
.
Сжатие
данных
представляет
собой
замену
часто
встречающихся
одинаковых
строк
данных
или
последовательностей
одинаковых
символов
некоторыми
заранее
выбранны
-
ми
символами
.
342
Глава
18.
Криптографическая
защита
Рис
. 18.1.
Классификация
криптографических
методов
Требования
к
криптографическим
методам
защиты
информации
Раскрытие
зашифрованных
текстов
(
в
первую
очередь
нахождение
ключа
)
осуществ
-
ляется
при
помощи
методов
криптоанализа
.
Основными
методами
криптоанализа
явля
-
ются
:
•
статистические
,
при
которых
зная
статистические
свойства
открытого
текста
пы
-
таются
исследовать
статистические
закономерности
шифротекста
и
на
основании
об
-
наруженных
закономерностей
раскрыть
текст
;
•
метод
вероятных
слов
,
в
котором
при
сопоставлении
некоторой
небольшой
части
шифротекста
с
известным
фрагментом
открытого
текста
пытаются
найти
ключ
и
с
его
помощью
расшифровать
весь
текст
.
Требуемый
фрагмент
открытого
текста
мож
-
но
найти
с
помощью
статистических
методов
или
просто
угадать
,
исходя
из
предпо
-
лагаемого
содержания
или
структуры
открытого
текста
.
Классификация
криптографических
методов
343
Поскольку
криптографические
методы
ЗИ
применяются
давно
,
то
уже
сформулиро
-
ваны
основные
требования
к
ним
.
1.
Метод
должен
быть
надежным
,
т
.
е
.
восстановление
открытого
текста
при
владении
только
шифротекстом
,
но
не
ключом
должно
быть
практически
невыполнимой
зада
-
чей
2.
Из
-
за
трудности
запоминания
объем
ключа
не
должен
быть
большим
.
3.
Из
-
за
трудностей
,
связанных
со
сложными
преобразованиями
,
процессы
шифрования
должны
быть
простыми
.
4.
Из
-
за
возможности
появления
ошибок
передачи
дешифрование
шифротекста
,
содер
-
жащего
отдельные
ошибки
,
не
должно
привести
к
бесконечному
увеличению
ошибок
в
полученном
предполагаемом
открытом
тексте
.
5.
Из
-
за
трудностей
передачи
объем
шифротекста
не
должен
быть
значительно
больше
открытого
текста
.
Перечисленные
требования
были
разработаны
для
традиционной
криптографии
.
При
современном
развитии
техники
необходимость
удовлетворения
перечисленным
требованиям
претерпевает
существенные
изменения
.
В
связи
с
развитием
технологии
,
позволяющей
с
большой
плотностью
записать
и
длительное
время
надежно
хранить
большие
объемы
информации
,
условие
небольшого
объема
ключа
может
быть
ослаблено
(
по
существу
это
условие
,
как
и
все
остальные
,
приобретает
новый
смысл
,
соответствующий
достигнутому
уровню
техники
).
В
связи
с
развитием
микроэлектроники
появляется
возможность
разработки
дешевых
устройств
,
осуществляющих
быстро
и
точно
сравнительно
сложные
преобразования
информации
.
С
другой
стороны
,
возможность
увеличения
скорости
передачи
отстает
от
возможности
увеличения
скорости
обработки
информации
.
Это
,
несомненно
,
позволяет
ослабить
тре
-
бование
п
. 3
без
ущерба
для
практически
достигаемой
скорости
передачи
.
В
настоящее
время
связное
оборудование
является
высоконадежным
,
а
методы
обнаружения
и
ис
-
правления
ошибок
—
хорошо
развитыми
.
К
тому
же
,
обычно
используемые
в
компью
-
терных
сетях
протоколы
сеансов
связи
предусматривают
передачу
любого
текста
даже
при
наличии
сбоев
во
время
передачи
.
Поэтому
требование
п
. 4
в
значительной
мере
по
-
теряло
свою
актуальность
.
В
отдельных
случаях
,
если
каналы
связи
не
перегружены
,
может
быть
ослаблено
и
требование
п
. 5.
Таким
образом
,
не
затронутым
осталось
требование
п
. 1,
при
рассмотрении
которого
следует
учесть
два
обстоятельства
.
Во
-
первых
,
в
автоматизированных
системах
(
АС
)
циркулируют
большие
объемы
ин
-
формации
,
а
наличие
большого
объема
шифротекста
облегчает
задачу
криптоанализа
.
Во
-
вторых
,
для
решения
задачи
криптоанализа
можно
использовать
ЭВМ
.
Это
позво
-
ляет
в
новых
условиях
требовать
значительного
увеличения
надежности
.
Другим
важ
-
ным
отрицательным
фактором
применения
криптографии
в
АС
является
то
,
что
часто
используются
языки
с
весьма
ограниченным
запасом
слов
и
строгим
синтаксисом
(
языки
программирования
).
344
Глава
18.
Криптографическая
защита
В
связи
с
новыми
специфическими
применениями
криптографических
методов
могут
быть
выдвинуты
также
другие
требования
.
Так
,
например
,
второй
важной
областью
применения
криптографических
методов
ЗИ
являются
системы
управления
базами
дан
-
ных
(
СУБД
).
В
этом
случае
к
криптографическим
методам
ЗИ
предъявляются
следую
-
щие
дополнительные
требования
.
1.
Из
-
за
невозможности
чтения
и
возобновления
записей
с
середины
файла
,
шифрова
-
ние
и
дешифрование
каждой
записи
должны
производиться
независимо
от
других
за
-
писей
.
2.
Для
создания
больших
удобств
обработки
и
во
избежание
излишней
перегрузки
сис
-
темы
вспомогательными
преобразованиями
необходимо
все
операции
с
файлами
проводить
с
данными
в
зашифрованном
виде
.
Специфика
СУБД
оказывает
влияние
на
надежность
защиты
по
следующим
причи
-
нам
:
•
данные
в
СУБД
продолжительное
время
находятся
в
зашифрованном
виде
.
Это
за
-
трудняет
или
даже
делает
невозможной
частую
смену
ключей
,
и
в
связи
с
этим
ЗИ
становится
менее
надежной
;
•
ключи
могут
не
передаваться
по
разным
адресам
,
а
храниться
все
в
одном
месте
.
Это
повышает
надежность
системы
из
-
за
уменьшения
возможности
овладения
ключами
посторонними
лицами
.
В
файловых
системах
вероятность
появления
ошибки
гораздо
меньше
,
чем
в
каналах
связи
,
поэтому
требование
п
. 4
для
файловых
систем
не
имеет
большого
практического
значения
.
Появление
быстродействующих
ЭВМ
способствует
возникновению
так
называемой
вычислительной
криптографии
,
тесно
связанной
с
вычислительной
техникой
.
Математика
разделения
секрета
Рассмотрим
следующую
,
в
наше
время
вполне
реальную
ситуацию
.
Два
совладельца
драгоценности
хотят
положить
ее
на
хранение
в
сейф
.
Сейф
современный
,
с
цифровым
замком
на
16
цифр
.
Так
как
совладельцы
не
доверяют
друг
другу
,
то
они
хотят
закрыть
сейф
таким
образом
,
чтобы
они
могли
открыть
его
вместе
,
но
никак
не
порознь
.
Для
это
-
го
они
приглашают
третье
лицо
,
называемое
дилером
,
которому
они
оба
доверяют
(
на
-
пример
,
потому
что
оно
не
получит
больше
доступ
к
сейфу
).
Дилер
случайно
выбирает
16
цифр
в
качестве
“
ключа
”,
чтобы
закрыть
сейф
,
и
затем
сообщает
первому
совладель
-
цу
втайне
от
второго
первые
8
цифр
“
ключа
”,
а
второму
совладельцу
втайне
от
первого
—
последние
8
цифр
“
ключа
”.
Такой
способ
представляется
с
точки
здравого
смысла
оп
-
тимальным
,
ведь
каждый
из
совладельцев
,
получив
“
полключа
”,
не
сможет
им
восполь
-
зоваться
без
второй
половины
,
а
что
может
быть
лучше
?!
Недостатком
данного
примера
является
то
,
что
любой
из
совладельцев
,
оставшись
наедине
с
сейфом
,
может
за
пару
минут
найти
недостающие
“
полключа
”
с
помощью
несложного
устройства
,
предназна
-
ченного
для
перебора
ключей
и
работающего
на
тактовой
частоте
1
МГц
.
Кажется
,
что
единственный
выход
—
в
увеличении
размера
“
ключа
”,
скажем
,
вдвое
.
Но
есть
другой
Математика
разделения
секрета
345
математический
выход
,
опровергающий
(
в
данном
случае
—
к
счастью
)
соображения
здравого
смысла
.
А
именно
,
дилер
независимо
выбирает
две
случайные
последователь
-
ности
по
16
цифр
в
каждой
,
сообщает
каждому
из
совладельцев
втайне
от
другого
“
его
”
последовательность
,
а
в
качестве
“
ключа
”,
чтобы
закрыть
сейф
,
использует
последова
-
тельность
,
полученную
сложением
по
модулю
10
соответствующих
цифр
двух
выбран
-
ных
последовательностей
.
Довольно
очевидно
,
что
для
каждого
из
совладельцев
все
10
16
возможных
“
ключей
”
одинаково
вероятны
и
остается
только
перебирать
их
,
что
потре
-
бует
в
среднем
около
полутора
лет
для
устройства
перебора
ключей
,
оборудованного
процессором
с
частотой
100
МГц
.
И
с
математической
,
и
с
практической
точки
зрения
неинтересно
останавливаться
на
случае
двух
участников
и
следует
рассмотреть
общую
ситуацию
.
Неформально
говоря
,
схема
,
разделяющая
секрет
(
СРС
)
позволяет
“
распределить
”
секрет
между
n
участни
-
ками
таким
образом
,
чтобы
заранее
заданные
разрешенные
множества
участников
могли
однозначно
восстановить
секрет
(
совокупность
этих
множеств
называется
структурой
доступа
),
а
неразрешенные
—
не
получали
никакой
дополнительной
к
имеющейся
ап
-
риорной
информации
о
возможном
значении
секрета
.
СРС
с
последним
свойством
назы
-
ваются
совершенными
.
История
СРС
начинается
с
1979
года
,
когда
эта
проблема
была
поставлена
и
во
мно
-
гом
решена
Блейкли
и
Шамиром
для
случая
пороговых
(n, k)
-
СРС
(
т
.
е
.
разрешенными
множествами
являются
любые
множества
из
k
или
более
элементов
).
Особый
интерес
вызвали
так
называемые
идеальные
СРС
,
т
.
е
.
такие
,
где
объем
информации
,
предостав
-
ляемой
участнику
,
не
больше
объема
секрета
.
Оказалось
,
что
любой
такой
СРС
соответ
-
ствует
матроид
и
,
следовательно
,
не
для
любой
структуры
доступа
возможно
идеальное
разделение
секрета
.
С
другой
стороны
,
было
показано
,
что
для
любого
набора
разрешен
-
ных
множеств
можно
построить
совершенную
СРС
,
однако
известные
построения
весь
-
ма
неэкономны
.
Рассмотрим
некоторые
алгебро
-
геометрические
и
комбинаторные
зада
-
чи
,
возникающие
при
математическом
анализе
СРС
.
Будем
говорить
,
что
семейство
подпространств
{L
0
, …, L
n
}
конечномерного
век
-
торного
пространства
L
над
полем
K
удовлетворяет
свойству
“
все
или
ничего
”,
если
для
любого
множества
A
⊂
{1, …, n}
линейная
оболочка
подпространств
{L
a
: a
∈
A}
либо
содержит
подпространство
L
0
целиком
,
либо
пересекается
с
ним
только
по
век
-
тору
0
.
В
подразделе
“
Линейное
разделение
секрета
”
мы
увидим
,
что
такое
семейство
задает
“
линейную
”
СРС
,
у
которой
множество
A
⊂
{1, …, n}
является
разрешенным
,
если
и
только
если
линейная
оболочка
подпространств
{L
a
: a
∈
A}
содержит
подпро
-
странство
L
0
целиком
.
В
связи
с
этим
понятием
возникает
ряд
вопросов
.
Например
,
если
поле
K
конечно
(
|K| = q
)
и
все
подпространства
{L
0
, …, L
n
}
одномерны
,
то
ка
-
ково
максимально
возможное
число
участников
n
для
линейных
пороговых
(
n
,
k
)-
СРС
(
k > 1
)?
Иначе
говоря
,
каково
максимально
возможное
число
векторов
{h
0
, …, h
n
}
та
-
ких
,
что
любые
k
векторов
,
содержащие
вектор
h
0
,
линейно
независимы
,
а
любые
k +
1
векторов
,
содержащие
вектор
h
0
,
линейно
зависимы
.
Оказывается
,
что
это
свойство
эквивалентно
следующему
,
на
первый
взгляд
более
сильному
,
свойству
:
любые
k
век
-
торов
линейно
независимы
,
а
любые
k + 1
—
линейно
зависимы
.
Такие
системы
век
-