Учебное пособие: Дискретная мат-ка_УП
106
Выход: р –
индекс
самого
длинного
слова
в
словаре
,
совпа
-
дающего
с
символами
f[k]..f[k + l].
Если
такого
слова
в
словаре
нет
,
то
р
= 0.
l: = 0; р: = 0 {
начальное
состояние
}
for
i from 1 to d do
if
D[i] = f[k..k + Length(D[i]) – l]&Length(D[i]) > l then
p: = i;l: = Length(D[i]) {
нашли
более
подходящее
слово
}
end if
end for
return
p
Распаковка
осуществляется
следующим
алгоритмом
.
Алгоритм 4.
Распаковка
по
методу
Лемпела
-
Зива
Вход
:
сжатый
текст
,
представленный
массивом
пар
g : array
[l..
m] of record p : int; q : char endrecord,
где
p –
номер
слова
в
словаре
,
q –
код
дополняющей
буквы
.
Выход
:
исходный
текст
,
заданный
последовательностью
строк
и
символов
.
D[0]: = ««; d: = 0 {
начальное
состояние
словаря
}
for
k
≤ n do
p: = g[k].p { p –
индекс
слова
в
словаре
}
q:= g[k].q { q –
дополнительная
буква
}
yield
p U q {
вывод
слова
и
еще
одной
буквы
}
d: = d + 1; D[d]: = D[p] U q
{
пополнение
словаря
,
здесь
U –
это
конкатенация
}
end for
На
практике
применяют
различные
усовершенствования
этой
схемы
.
1.
Словарь
можно
сразу
инициализировать
,
например
,
кода
-
ми
символов
(
то
есть
считать
,
что
однобуквенные
слова
уже
из
-
вестны
).
2.
В
текстах
часто
встречаются
регулярные
последовательно
-
сти
:
пробелы
и
табуляции
в
таблицах
и
т
.
п
.
Сопоставлять
каждой
подпоследовательности
такой
последовательности
отдельное
сло
-
во
в
словаре
нерационально
.
В
таких
случаях
лучше
применить
специальный
прием
,
например
,
закодировать
последовательность
107
пробелов
парой
<
k,s>,
где
k –
количество
пробелов
, a
s –
код
про
-
бела
.
8.5
Шифрование
Защита
компьютерных
данных
от
несанкционированного
доступа
,
искажения
и
уничтожения
в
настоящее
время
является
серьезной
социальной
проблемой
.
Применяются
различные
под
-
ходы
к
решению
этой
проблемы
.
●
Поставить
между
злоумышленником
и
данными
в
ком
-
пьютере
непреодолимый
барьер
,
то
есть
исключить
саму
воз
-
можность
доступа
к
данным
путем
физической
изоляции
компь
-
ютера
с
данными
,
применения
аппаратных
ключей
защиты
и
т
.
п
.
Такой
подход
надежен
,
но
он
затрудняет
доступ
к
данным
и
ле
-
гальным
пользователям
,
а
потому
постепенно
уходит
в
прошлое
.
●
Поставить
между
злоумышленником
и
данными
в
ком
-
пьютере
логический
барьер
,
то
есть
проверять
наличие
прав
на
доступ
к
данным
и
блокировать
доступ
при
отсутствии
таких
прав
.
Для
этого
применяются
различные
системы
паролей
,
реги
-
страция
и
идентификация
пользователей
,
разграничения
прав
доступа
и
т
.
п
.
Практика
показывает
,
что
борьба
между
«
хакера
-
ми
»
и
модулями
защиты
операционных
систем
идет
с
перемен
-
ным
успехом
.
●
Хранить
данные
таким
образом
,
чтобы
они
могли
«
сами
за
себя
постоять
».
Другими
словами
,
так
закодировать
данные
,
чтобы
даже
получив
их
,
злоумышленник
не
смог
бы
нанести
ущерба
.
Этот
раздел
посвящен
обсуждению
методов
кодирования
,
применяемых
в
последнем
случае
.
8.6
Криптография
Шифрование –
это
кодирование
данных
с
целью
защиты
от
несанкционированного
доступа
.
Процесс
кодирования
сообщения
называется
шифрованием
(
или
зашифровкой
),
а
процесс
декодирования
– расшифровыва
-
нием (
или
расшифровкой
).
Само
кодированное
сообщение
назы
-
108
вается
шифрованным
(
или
просто
шифровкой
),
а
применяемый
метод
называется
шифром
.
Основное
требование
к
шифру
состоит
в
том
,
чтобы
рас
-
шифровка
(
и
,
может
быть
,
зашифровка
)
была
возможна
только
при
наличии
санкции
,
то
есть
некоторой
дополнительной
инфор
-
мации
(
или
устройства
),
которая
называется
ключом
шифра
.
Про
-
цесс
декодирования
шифровки
без
ключа
называется
дешифро
-
ванием (
или
дешифрацией
,
или
просто
раскрытием
шифра
).
Область
знаний
о
шифрах
,
методах
их
создания
и
раскрытия
называется
криптографией
(
или
тайнописью
).
Свойство
шифра
противостоять
раскрытию
называется
криптостойкостъю (
или
надежностью
)
и
обычно
измеряется
сложностью
алгоритма
дешифрации
.
В
практической
криптографии
криптостойкость
шифра
оце
-
нивается
из
экономических
соображений
.
Если
раскрытие
шифра
стоит
(
в
денежном
выражении
,
включая
необходимые
компью
-
терные
ресурсы
;
специальные
устройства
и
т
.
п
.)
больше
,
чем
са
-
ма
зашифрованная
информация
,
то
шифр
считается
достаточно
надежным
.
Криптография
известна
с
глубокой
древности
и
использует
самые
разнообразные
шифры
,
как
чисто
информационные
,
так
и
механические
.
В
настоящее
время
наибольшее
практическое
зна
-
чение
имеет
защита
данных
в
компьютере
,
поэтому
далее
рас
-
сматриваются
программные
шифры
для
сообщений
в
алфавите
{0,1}.
Шифрование с помощью случайных чисел
Пусть
имеется
датчик
псевдослучайных
чисел
,
работающий
по
некоторому
определенному
алгоритму
.
Часто
используют
сле
-
дующий
алгоритм
:
T
i+1
:
=(a –T
i
+ b) mod с,
где
T
i
–
предыдущее
псевдослучайное
число
,
T
i+1
–
следующее
псевдослучайное
число
,
а
коэффициенты
а
, b, с
постоянны
и
хо
-
рошо
известны
.
Обычно
с
= 2
n
,
где
n –
разрядность
процессора
,
a mod 4 = 1, a b –
нечетное
.
В
этом
случае
последовательность
псевдослучайных
чисел
имеет
период
с.
Процесс
шифрования
определяется
следующим
109
образом
.
Шифруемое
сообщение
представляется
в
виде
последо
-
вательности
слов
S
0
, S
1
,...,
каждое
длины
п
,
которые
складывают
-
ся
по
модулю
2
со
словами
последовательности
T
0
,
Т
1
...,
то
есть
С
i
: =
S
i
⊕ T
i
.
Последовательность
Т
0
, Т
1
,…
называется
гаммой
шифра.
Процесс
расшифровывания
заключается
в
том
,
чтобы
еще
раз
сложить
шифрованную
последовательность
с
той
же
самой
гаммой
шифра
:
S
i
:
= C
i
⊕ T
i
.
Ключом
шифра
является
начальное
значение
Т
0
,
которое
яв
-
ляется
секретным
и
должно
быть
известно
только
отправителю
и
получателю
шифрованного
сообщения
.
Шифры
,
в
которых
для
зашифровки
и
расшифровки
исполь
-
зуется
один
и
тот
же
ключ
,
называются
симметричными
.
Если
период
последовательности
псевдослучайных
чисел
достаточно
велик
,
чтобы
гамма
шифра
была
длиннее
сообщения
,
то
дешифровать
сообщение
можно
только
подбором
ключа
.
При
увеличении
п
экспоненциально
увеличивается
криптостойкость
шифра
.
Это
очень
простой
и
эффективный
метод
часто
применяют
«
внутри
»
программных
систем
,
например
,
для
защиты
данных
на
локальном
диске
.
Для
защиты
данных
,
передаваемых
по
откры
-
тым
каналам
связи
,
особенно
в
случае
многостороннего
обмена
сообщениями
,
этот
метод
применяют
не
так
часто
,
поскольку
возникают
трудности
с
надежной
передачей
секретного
ключа
многим
пользователям
.
Криптостойкость
Описанный
в
предыдущем
подразделе
метод
шифрования
обладает
существенным
недостатком
.
Если
известна
хотя
бы
часть
исходного
сообщения
,
то
все
сообщение
может
быть
легко
дешифровано
.
Действительно
,
пусть
известно
одно
исходное
сло
-
во
S
i
.
Тогда
T
i
: = C
i
⊕ S
i
и
далее
вся
правая
часть
гаммы
шифра
определяется
по
указан
-
ной
формуле
датчика
псевдослучайных
чисел
.
110
На
практике
часть
сообщения
вполне
может
быть
известна
злоумышленнику
.
Например
,
многие
текстовые
редакторы
поме
-
щают
в
начало
файла
документа
одну
и
ту
же
служебную
инфор
-
мацию
.
Если
злоумышленнику
известно
,
что
исходное
сообщение
подготовлено
в
данном
редакторе
,
то
он
сможет
легко
дешифро
-
вать
сообщение
.
Для
повышения
криптостойкости
симметричных
шифров
применяют
различные
приемы
:
1)
вычисление
гаммы
шифра
по
ключу
более
сложным
(
или
секретным
)
способом
;
2)
применение
вместо
ф
более
сложной
(
но
обратимой
)
опе
-
рации
для
вычисления
шифровки
;
3)
предварительное
перемешивание
битов
исходного
сооб
-
щения
по
фиксированному
алгоритму
.
В
настоящее
время
широкое
распространение
получили
шифры
с
открытым ключом.
Эти
шифры
не
являются
симмет
-
ричными
–
для
зашифровки
и
расшифровки
используются
разные
ключи
.
При
этом
ключ
,
используемый
для
зашифровки
,
является
открытым
(
не
секретным
)
и
может
быть
сообщен
всем
желаю
-
щим
отправить
шифрованное
сообщение
,
а
ключ
,
используемый
для
расшифровки
,
является
закрытым
и
хранится
в
секрете
полу
-
чателем
шифрованных
сообщений
.
Даже
знание
всего
зашифро
-
ванного
сообщения
и
открытого
ключа
,
с
помощью
которого
оно
было
зашифровано
,
не
позволяет
дешифровать
сообщение
(
без
знания
закрытого
ключа
).
Для
описания
метода
шифрования
с
открытым
ключом
нужны
некоторые
факты
из
теории
чисел
,
изложенные
(
без
дока
-
зательств
)
в
следующем
подразделе
.
Модулярная арифметика
В
этом
подразделе
все
числа
целые
.
Говорят
,
что
число
а
сравнимо по модулю п
с
числом
b (
обозначение
: а
≡ b (mod n)),
если
а
и
b
при
делении
на
п
дают
один
и
тот
же
остаток
:
а
≡
b (mod п) : = a mod п= b mod п.
Отношение
сравнимости
рефлексивно
,
симметрично
и
транзитивно
и
является
отношением
эквивалентности
.
Классы