Единое окно доступа к образовательным ресурсам

Криптографическая защита информации: Учебное пособие

Голосов: 4

Пособие содержит материал в соответствии с Государственным образовательным стандартом по специальности 090105 "Комплексное обеспечение информационной безопасности автоматизированных систем". Рассматриваются, классифицируются и анализируются основные алгоритмы шифрования, оценивается их эффективность, надежность и особенности реализации. Пособие может быть полезно при курсовом и дипломном проектировании, аспирантам, а также кругу читателей, интересующихся современными проблемами криптографической защиты информации.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
       Пример. Открытый текст: "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ".
Ключ: гамильтонов путь на графе (рис. 2.13).

4               5                 4                  5                4                    5

     0     1                            0       1                           0          1


     2     3                           2       3                            2          3

6               7                 6                  7                 6                   7
    Общий вид                         Маршрут 1                            Маршрут 2

                     Рис. 2.13. Гамильтоновы пути на графе

     Шифртекст: "ШАОНИРФВИЕЕСЕП_РТОВИАОНК".
     Необходимо отметить, что для данного графа из восьми вершин мож-
но предложить несколько маршрутов записи открытого текста и несколько
гамильтоновых путей для чтения криптограмм.
     В 1991 г. В.М. Кузьмич предложил схему перестановки, основанной
на кубике Рубика. Согласно этой схеме открытый текст записывается в
ячейки граней куба по строкам. После осуществления заданного числа за-
данных поворотов слоев куба считывание шифртекста осуществляется по
столбикам. Сложность расшифрования в этом случае определяется количе-
ством ячеек на гранях куба и сложностью выполненных поворотов слоев.
Перестановка, основанная на кубике Рубика, получила название объемной
(многомерной) перестановки.
     В 1992–1994 гг. идея применения объемной перестановки для шифро-
вания открытого текста получила дальнейшее развитие. Усовершенство-
ванная схема перестановок по принципу кубика Рубика, в которой наряду с
открытым текстом перестановке подвергаются и функциональные элемен-
ты самого алгоритма шифрования, легла в основу секретной системы "Ру-
бикон". В качестве прообразов пространственных многомерных структур,
на основании объемных преобразований которых осуществляются переста-
новки, в системе "Рубикон" используются трехмерные куб и тетраэдр. Дру-
гой особенностью системы "Рубикон" является генерация уникальной вер-
сии алгоритма и ключа криптографических преобразований на основании
некоторого секретного параметра (пароля). Это обеспечивает как дополни-
тельные трудности для криптоанализа перехваченных сообщений наруши-
телем (неопределенность примененного алгоритма), так и возможность
априорного задания требуемой криптостойкости. Криптостойкость данной
системы определяется длиной ключа, криптостойкостью отдельных функ-
циональных элементов алгоритма криптографических преобразований, а
также количеством таких преобразований.
     Использование уникальных алгоритма и ключа шифрования для каж-
дого пользователя системы соответствует положению теории К. Шеннона о
том, что абсолютно стойкий шифр может быть получен только при исполь-
зовании "ленты однократного применения", т.е. уникальных параметров
при каждом осуществлении шифрования.

         2.5.4. МЕТОДЫ АНАЛИТИЧЕСКИХ ПРЕОБРАЗОВАНИЙ
     Шифрование методами аналитических преобразований основано на
понятии односторонней функции. Будем говорить, что функция у = f (х)
является односторонней, если она за сравнительно небольшое число опера-
ций преобразует элемент открытого текста Х в элемент шифртекста Y для
всех значений Х из области определения, а обратная операция (вычисление
X = F-1(Y) при известном шифртексте) является вычислительно трудоемкой.
     В качестве односторонней функции можно использовать следующие
преобразования: умножение матриц; решение задачи об укладке ранца;
вычисление значения полинома по модулю; экспоненциальные преобразо-
вания и др.
     Метод умножения матриц использует преобразование вида
         Y = CX, где Y = ||y1, y2, ..., yn||Т; С = ||Cij||; X = ||x1, x2, ..., xn||.
     Пример. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно
табл. 2.2).


                  13 2    1 3 2 16                     1 3 2 11
     Матрица С: 2 1 5      2 1 5 * 17 = 85 94 91       2 1 5 * 01 = 30 63 43
                3 21       3 2 1 09                    3 2 1 08
     Шифртекст: "85 94 91 30 63 43".
     Задача об укладке ранца формулируется следующим образом.
     Задан вектор С = |c1, c2, ..., cn|, который используется для шифрования
сообщения, каждый символ si которого представлен последовательностью
из n бит si = |x1, x2, ..., xn|T, Xk ⊂ {0, 1}. Шифртекст получается как скалярное
произведение Сsi.
     Пример. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно
табл. 2.2). Вектор С = {1,3,5,7,11}. Запишем символы открытого текста пя-
тиразрядным двоичным кодом.
       П         Р      И      К      А                  З
     10000     10001 01001 01011 00001                 01000
     Произведем соответствующие операции:
     y1 = 1∗1 = 1.
     y2 = 1∗1 + 1∗11 = 12.
     y3 = 1∗3 + 1∗11 = 14.
     y4 = 1∗3 + 1∗7 + 1∗11 = 21.
     у5 = 1∗11 = 11.
     y6 = 1∗3 = 3.
     Шифртекст: "01 12 14 21 11 03".
     Метод полиномов основан на преобразовании
                     yi = xin + a1∗xi(n–1) +...+ an∗xi(mod р),
где n, а1, а2, ..., аn – целые неотрицательные числа, не превосходящие р, 1
<= хi, уi <= р; р – большое простое число.
     Пример. Открытый текст: "ПРИКАЗ". ("16 17 09 11 01 08" согласно
табл. 2.2)
     Полином:
     уi = xi3 + 2xi2 + 3xi + 4(mod 991).
     y1 = 163 + 2∗162 + 3∗16 + 4(mod 991) = 696.
     y2 = 173 + 2∗172 + 3∗16 + 4(mod 991) = 591.
     у3 = 93 + 2∗92 + 3∗9 + 4(mod 991) = 922.
     у4 = 113 + 2∗112 + 3∗11 + 4(mod 991) = 619.
     y5 = 13 + 2∗12 + 3∗1 + 4(mod 991) = 10.
     у6 = 83 + 2∗82 + 3∗8 + 4(mod 991) = 668.
     Шифртекст: "96 591 922 619 010 668".
     Экспоненциальный шифр использует преобразование вида
                                уi =a(xi) (mod р),
где хi – целое, 1 <= хi <= р – 1; p – большое простое число; a – целое, 1 <= a
<= p.
     Пример. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно
табл. 2.2); a = 3; p = 991.
     y1 = 316 (mod 991) = 43046721 (mod 991) = 654.
     у2 = 317 (mod 991) = 129140163 (mod 991) = 971.
     у3 = 39 (mod 991) = 19683 (mod 991) = 854.
     y4 = 311 (mod 991) = 177147 (mod 991) = 749.
     у5 = 31 (mod 991) = 3.
     y6 = 38 (mod 991) = 6561 (mod 991) = 615.
     Шифртекст: "654 971 854 749 003 615".
2.5.5. ГАММИРОВАНИЕ (ШИФРОВАНИЕ С ПОМОЩЬЮ ДАТЧИКАПСЕВ-
                         ДОСЛУЧАЙНЫХ ЧИСЕЛ)
     Различают два случая: метод конечной гаммы и метод бесконечной
гаммы. В качестве конечной гаммы может использоваться фраза, а в каче-
стве бесконечной – последовательность, вырабатываемая датчиком псевдо-
случайных чисел.


     Принцип зашифрования заключается в генерации гаммы шифра с по-
мощью датчика псевдослучайных чисел (ПСЧ) и наложении полученной
гаммы на открытые данные обратимым образом (например, при использо-
вании логической операции "исключающее ИЛИ").
     Процесс расшифрования данных сводится к повторной генерации
гаммы шифра при известном ключе и наложению такой гаммы на зашиф-
рованные данные. Полученный зашифрованный текст является достаточно
трудным для раскрытия в том случае, когда гамма шифра не содержит по-
вторяющихся битовых последовательностей. По сути дела гамма шифра
должна изменяться случайным образом для каждого шифруемого слова.
Фактически если период гаммы превышает длину всего зашифрованного
текста и неизвестна никакая часть исходного текста, то шифр можно рас-
крыть только прямым перебором (подбором ключа). В этом случае крипто-
стойкость определяется размером ключа.
     Чтобы получить линейные последовательности элементов гаммы,
длина которых превышает размер шифруемых данных, используются дат-
чики ПСЧ. На основе теории групп было разработано несколько типов та-
ких датчиков. В настоящее время наиболее доступными и эффективными
являются конгруэнтные генераторы ПСЧ. Они вырабатывают последова-
тельности псевдослучайных чисел Т(i), описываемые соотношением
                      T(i + 1) = (A∗T(i) + С) mod М,
где А и С – константы; Т(0) – исходная величина, выбранная в качестве по-
рождающего числа.
     Для шифрования данных с помощью датчика ПСЧ может быть выбран
ключ любого размера. Например, пусть ключ состоит из набора чисел Х(j)
размерностью b, где j = 1, 2, ...., N. Тогда создаваемую гамму шифра G
можно представить как объединение непересекающихся множеств Н(j):
                      G = H(1) ∪ H(2) ∪ … ∪ H(N),
где Н(j) – множество соответствующих j-му сегменту данных и получен-
ных на основе порождающего числа Y(j), определенного как функция от
Х(j) (например, ПСЧ, полученное на основе Х(j)).
      Разумеется, возможны и другие, более изощренные варианты выбора
порождающих чисел для гаммы шифра. Более того, гамму шифра необяза-
тельно рассматривать как объединение непересекающихся множеств. На-
пример, гамма шифра может быть представлена в виде
                     G = H(1) (+) H(2) (+) … (+) H(N),
где символ (+) обозначает операцию "исключающее ИЛИ".
     Шифрование с помощью датчика ПСЧ является довольно распростра-
ненным криптографическим методом, а качество шифра определяется не
только и не столько характеристиками датчика, сколько алгоритмом полу-
чения гаммы. Хорошие результаты дает метод гаммирования с обратной
связью, который заключается в том, что для получения сегмента гаммы
используется контрольная сумма определенного участка шифруемых дан-
ных.

                   2.6. Примеры потоковых шифров

                          2.6.1. АЛГОРИТМ RC4
      Алгоритм RC4 представляет собой потоковый шифр с переменной
длиной ключа, разработанный в 1987 г. Роном Ривестом для компании RSA
Data Security, Inc. В течение семи лет этот шифр лицензировался компани-
ей только на условиях неразглашения. Однако, в 1994 г. он был анонимно
опубликован в Интернете и с тех пор стал доступен для независимого ана-
лиза.
      Описывается шифр очень просто. Алгоритм работает в режиме OFB.
Ключевая последовательность не зависит от исходного текста. Структура ал-
горитма включает блок замены размерностью 8 × 8: S0, ..., S255. Блок замены
представляет собой зависимую от ключа переменной длины перестановку
чисел 0, ..., 255. Имеется два счетчика i и j, первоначально равные 0. Для
генерирования псевдослучайного байта выполняются следующие действия:


                             i = (i + 1) mod 256,
                              j = ( j + Si ) mod 256.
     Далее переставить Si и Sj:
                             t = ( Si + S j ) mod 256,
                             k = Si .

     Затем байт k складывается по модулю 2 с байтом исходного текста для
получения шифрованного.
     Инициализация блока замены также проста. Вначале он заполняется
линейно: S0 = 0, ..., S255 = 255. Затем заполняется еще один 256-байтный массив
ключом, при этом ключ может повторяться необходимое число раз для за-
полнения всего массива: k0, ..., k255. Счетчик j устанавливается в 0. После
чего производятся следующие действия:
                                for i = 0 to 255
                           j = (j + ki + Si) mod 256
переставить Si и Sj.
     Шифрование по этому алгоритму, примерно, в 10 раз быстрее, чем
шифрование DES при программной реализации.
     Возможно обобщение алгоритма на большие длину слова и размер
блока замены. Например, можно построить шифр с блоком замены размер-
ностью 16 × 16 и длиной слова 16 бит. Этап инициализации будет значи-
тельно медленнее, необходим цикл до 65535, но получившийся в результа-
те алгоритм будет более быстрым.

                           2.6.2. АЛГОРИТМ SEAL
     Алгоритм SEAL (Software Encryption Algorithm) представляет собой
приспособленный для программной реализации потоковый шифр, разрабо-
танный Филом Рогэвэем и Доном Копперсмитом из компании IBM. Алго-
ритм оптимизирован для 32-разрядных процессоров. Для эффективной ра-
боты ему требуются восьми 32-разрядных регистров и кэш объемом не-
сколько килобайт.
     Одним из замечательных свойств этого шифра является то, что он не
является потоковым шифром в традиционном смысле, а представляет со-
бой семейство псевдослучайных функций. 160-битовый ключ k и 32-
битовое значение п (индекс) шифр преобразует в L-битовую строку k(n). L
может принимать любое значение, меньшее 64 килобайт. Такой шифр обо-
значают SEAL(k, n, L). Предполагается, что если k выбирается случайно, то
k(n) будет вычислительно неотличима от случайной L-битовой функции от
п.
     Большинство шифров генерирует битовые последовательности в од-
ном направлении. Зная ключ k и позицию i, определить значение i-го бита
ключевой последовательности можно, только вычислив все биты до i-го
один за другим. В случае семейства псевдослучайных функций можно по-
лучить простой доступ к любому элементу ключевой последовательности.
     Предположим, что необходимо зашифровать содержимое жесткого
диска компьютера по 512-байтным секторам. Тогда сектор с номером п
будет шифроваться с помощью ключевой последовательности k(n). При
этом легко может быть обеспечен доступ к произвольному сектору диска.
     Данный шифр также облегчает проблему синхронизации, свойствен-
ную традиционным потоковым шифрам. Сообщение с номером п будет
шифроваться с ключевой последовательностью k(n), и п будет передаваться
вместе с сообщением. Получателю не нужно будет хранить состояние генера-
тора ключевой последовательности и беспокоиться о потерянных сообщениях
и их влиянии на процесс расшифрования.
     Алгоритм SEAL предусматривает использование трех зависящих от
ключа таблиц: R, S и Т заполняются на предварительном этапе при помощи
алгоритма, основанного на SHA (описан далее), и зависят только от ключа.
     Заполнение таблиц можно описать с помощью функции Ga(i), которая
представляет собой функцию сжатия из алгоритма SHA: а – 160-битное
значение, i – 32-битный индекс. Значение а используется для инициализа-
ции внутренних регистров А, В, С, D и Е в алгоритме SHA, а 512-битный


блок для обработки представляет собой строку i||0480. Выходное значение
функции G также имеет длину 512 бит.
     Основные идеи, лежащие в основе этого алгоритма, можно сформули-
ровать следующим образом:
   1.    использование большого секретного, зависящего от ключа блока
замены Т;
   2.    перемежение операций, не коммутирующих друг с другом (сло-
жение и исключающее ИЛИ);
   3.    использование внутреннего состояния, явно не проявляющегося в
потоке данных (значения ni, используемые в конце итерации для модифи-
кации регистров А и С);
   4.    изменение шаговой функции в зависимости от номера шага и из-
менение итерационной функции в зависимости от номера итерации;
   5.    использование известных и отработанных алгоритмов для запол-
нения таблиц.
     Шифр SEAL требует пять элементарных машинных операций в пере-
счете на один байт текста при шифровании и расшифровании. Таким обра-
зом, он является одним из самых быстрых программно реализуемых алго-
ритмов.

                            2.6.3. АЛГОРИТМ WAKE
     Алгоритм WAKE (Word Auto Key Encryption – шифрование слов с ав-
тоключом) был предложен Дэвидом Уилером. На выходе получается по-
следовательность 32-битовых слов, которые могут служить в качестве гам-
мы шифра. WAKE работает в режиме СFВ – предыдущее слово шифрован-
ного текста используется для генерации следующего слова ключевой по-
следовательности.
     В алгоритме используется специальный блок замены S из 256 32-
битных слов. При этом старшие байты этих слов являются перестановкой
чисел от 0 до 255, а остальные три младших байта выбираются случайны-
ми.
     Вначале инициализируется блок замены на основе ключа. Затем ини-
циализируются четыре регистра А, В, С и D начальными значениями, также
зависящими от ключа (возможно другого): a0, b0, с0, d0. Очередное слово
ключевой последовательности получается по формуле ki = di .
     После этого изменяется значение регистров:
                                ai +1 = M (ai , di );
                                bi +1 = M (bi , ai +1 );
                                ci +1 = M (ci , bi +1 );
                                di +1 = M (di , ci +1 ).
где M ( x, y ) = ( x + y ) 8 ⊕ S( x + y )&255 $ здесь 8 младших бит суммы х + у ис-
пользуются для входа в таблицу замены.
     Данный шифр является достаточно быстрым, хотя и нестойким к ата-
кам по выбранному исходному тексту.

                       2.7. Комбинированные методы
     Шифрование комбинированными методами основывается на резуль-
татах, полученных К. Шенноном. Наиболее часто применяются такие ком-
бинации, как подстановка и гамма, перестановка и гамма, подстановка и
перестановка, гамма и гамма. При составлении комбинированных шифров
необходимо проявлять осторожность, так как неправильный выбор состав-
лявших шифров может привести к исходному открытому тексту.
     В качестве примера можно привести шифр, предложенный Д. Френд-
бергом, который комбинирует многоалфавитную подстановку с генерато-
ром ПСЧ. Особенность данного алгоритма состоит в том, что при большом
объеме шифртекста частотные характеристики символов шифртекста близ-
ки к равномерному распределению независимо от содержания открытого
текста.
     Комбинация методов подстановки и перестановки была применена в
1974 г. фирмой IBM при разработке системы ЛЮЦИФЕР.
     Система ЛЮЦИФЕР строится на базе блоков подстановки (S-блоков)
и блоков перестановки (Р-блоков). Блок подстановки включает линейные и


нелинейные преобразования.
     Первый преобразователь S-блока осуществляет развертку двоичного
числа из n разрядов в число по основанию 2n. Второй преобразователь осу-
ществляет свертку этого числа.
     Блок перестановки осуществляет преобразование n разрядного вход-
ного числа в n разрядное число.
     Входные данные (открытый текст) последовательно проходят через че-
редующиеся слои 32-разрядных Р-блоков и 8-разрядных S-блоков.
     Реализация шифрования данных в системе ЛЮЦИФЕР программными
средствами показала низкую производительность, поэтому P- и S-блоки
были реализованы аппаратно, это позволило достичь скорости шифрования
до 100 Кбайт/с. Опыт, полученный при разработке и эксплуатации систе-
мы, позволил создать стандарт шифрования данных DES (Data Encryption
Standard).

            2.7.1. САМОСИНХРОНИЗИРУЮЩИЕСЯ ШИФРЫ
     В 1946 г. в США была запатентована базовая идея так называемых са-
мосинхронизирующихся потоковых шифров (или шифрования с автоклю-
чом – CipherText Auto Key (CTAK)). Она заключается в том, что внутреннее
состояние генератора является функцией фиксированного числа предшест-
вующих битов шифрованного текста. Поскольку внутреннее состояние за-
висит только от п бит шифрованного текста, генератор на приемной сторо-
не войдет в синхронизм с передающей стороной после получения п бит.
     Реализация этого подхода выглядит следующим образом. Каждое со-
общение предваряется случайным заголовком длиной п бит. Этот заголовок
шифруется и передается в линию. На приемной стороне заголовок расшиф-
ровывается. Результат расшифрования будет неверным, но после обработки
п бит заголовка оба генератора будут синхронизированы.
     Недостатком системы является распространение ошибок. При искаже-
нии одного бита генератор на приемной стороне выдаст п неверных бит
ключевой последовательности, пока ошибочный бит не будет вытолкнут из
памяти, что приведет к ошибочному расшифрованию п бит исходного тек-
ста.
     Кроме того, самосинхронизирующиеся шифры уязвимы для атак типа
"воспроизведение". Злоумышленник записывает некоторое количество бит
шифрованного текста. Затем, позднее, он подменяет биты трафика запи-
санными – "воспроизводит" их. После некоторого количества "мусора",
пока приемная сторона не синхронизируется, старый шифрованный текст
будет расшифровываться нормально. У приемной стороны нет никаких
средств определения того, что принимаемые данные не являются актуаль-
ными.
     Самосинхронизирующиеся потоковые шифры могут быть реализова-
ны в виде блочных шифров, используемых в режиме обратной связи по
шифрованному тексту. При этом за один раз может шифроваться произ-
вольное число бит, меньшее либо равное длине блока. Проиллюстрируем
это на примере шифрования по одному байту за цикл.
     Блочный шифр работает над очередью размером, равным длине блока.
Первоначально очередь заполняется синхропосылкой. Затем очередь шиф-
руется и левые 8 бит складываются с первыми 8 битами исходного текста.
Полученные 8 бит шифрованного текста передаются в линию, очередь
сдвигается влево на 8 бит, левые биты отбрасываются, а правые заполня-
ются 8 битами шифрованного текста, переданными в линию. Далее проце-
дура повторяется. Число 8 взято только для примера. За один цикл работы
блочного алгоритма может шифроваться и один бит, хотя это будет не
слишком эффективно с точки зрения скорости работы схемы. В режиме СРВ
синхропосылка должна быть уникальна для каждого сообщения в течение сро-
ка действия ключа. Если это будет не так, злоумышленник сможет восстано-
вить исходный текст.
     В случае возникновения ошибки в шифрованном тексте на приемной
стороне в общем случае возникнут ошибки при расшифровании текущего и
последующих [m/n] блоков, где т – размер блока; п – число бит, шифруе-
мых за один цикл, т.е. пока ошибочный бит шифрованного текста не будет
вытеснен из памяти.


                     2.7.2. СИНХРОННЫЕ ШИФРЫ
     Потоковые шифры носят название синхронных, если выходные значения
генератора не зависят от исходного или шифрованного текстов.
     Основная сложность в данном подходе заключается в необходимости
синхронизации генераторов ключа на передающей и приемной сторонах.
Если в процессе передачи произошло выпадение или вставка хотя бы одно-
го бита, то вся последовательность битов шифрованного текста после оши-
бочного бита не сможет быть расшифрована. Если такое произойдет, сто-
роны должны провести повторную синхронизацию. При этом синхрониза-
ция должна быть проведена так, чтобы никакой отрезок ключевой последо-
вательности не повторился, так что очевидное решение возвратиться к не-
которому предыдущему состоянию генератора не подходит.
     Положительным свойством синхронных потоковых шифров является
отсутствие эффекта распространения ошибок. Один искаженный бит при
передаче приведет к искажению только одного бита текста при расшифро-
вании.
     Синхронные шифры также защищают от вставок и выбрасываний от-
резков шифрованного текста из потока. Такие операции приведут к нару-
шению синхронизации, что будет сразу же обнаружено на приемной сторо-
не.
     Однако, такие шифры уязвимы к изменению отдельных бит. Если зло-
умышленник знает исходный текст, то он сможет изменять биты в потоке
шифрованного текста таким образом, что он будет расшифровываться так,
как необходимо злоумышленнику.
     Синхронный потоковый шифр может быть реализован в виде блочно-
го шифра, работающего в режиме обратной связи по выходу (режим OFB) с
любым размером обратной связи, меньшим размера блока. Однако, данный
способ не рекомендуется, так как при этом снижается период генератора
до, примерно, 2m/2. При длине блока 64 это будет около 232, чего явно не-
достаточно.
     В этом случае выходная функция очень часто выбирается простой, на-
пример, суммой по модулю 2 нескольких бит состояния или вообще одним
битом состояния. Криптографическая стойкость обеспечивается функцией
перехода к следующему состоянию, которая зависит от ключа. Иногда дан-
ный режим называют режимом с внутренней обратной связью, поскольку
обратная связь является внутренней по отношению к алгоритму генерации
ключевой последовательности.
     Вариантом этого режима является схема, когда ключ задает начальное
состояние генератора, после чего последний работает без дальнейшего
вмешательства.
     Еще одним способом построения потокового шифра является исполь-
зование счетчика в качестве входного значения для блочного шифра. После
каждого цикла шифрования блока значение счетчика увеличивается, чаще
всего на единицу. Свойства данного режима в отношении распространения
ошибок и синхронизации будут такими же, как и для режима OFB. В каче-
стве счетчика может быть использован любой генератор псевдослучайных
чисел, вне зависимости от его криптографической стойкости.
     При использовании потокового шифра в режиме счетчика выбирается
простая функция перехода и сложная, зависящая от ключа функция выхода.
Функция перехода может быть простым счетчиком, увеличивающимся на
единицу на каждом такте.

                    2.7.4. МЕТОДЫ КОДИРОВАНИЯ
     Как уже отмечалось, под кодированием понимается замена элементов
открытого текста (букв, слов, фраз и т.п.) кодами. Различают символьное и
смысловое кодирование.
     При символьном кодировании каждый знак алфавита открытого текста
заменяется соответствующим символом. Примером символьного кодиро-
вания служит азбука Морзе, а также методы шифрования заменой и пере-
становкой. Рассмотрим метод символьного кодирования, который исполь-
зует предыдущие символы открытого текста. Этот метод, называемый ме-


тодом стопки книг, был предложен Б.Я. Рябко.
       Предположим, что нужно передать сообщение X из алфавита А, в ко-
тором буквы алфавита отождествлены с числами 1, 2, …, L, где L – число
элементов алфавита А. Каждой букве алфавита соответствует код ki, 1 = 1,
..., L. При появлении в сообщении X очередной буквы хj ее код представля-
ется кодом номера позиции j, занимаемой в данный момент буквой хj в
списке. Это дает возможность на приемном конце по коду номера позиции
j определить букву хj. После кодирования буквы хj одновременно на прием-
ном и передающих концах перемещают букву хj в начало списка, увеличи-
вая тем самым на единицу номера букв, стоявших на позициях от 1 до j – 1.
Номера букв, стоявших на позициях от j + 1 до L, остаются без изменений.
В результате кодирования открытого текста в начале списка будут нахо-
диться буквы, которые наиболее часто встречались в открытом тексте.
       Интересный метод кодирования в 1992 г. предложил С.П. Савчук. В
отличие от метода стопки книг перемещению подвергается список кодов.
Пусть алфавит А = {а1, а2, ..., аn}. Данному порядку расположения букв со-
ответствует начальный список кодов K0 = {k1, k2, ..., kn}. При появлении в
кодируемом сообщении буквы ai в качестве кода выбирается соответст-
вующий ее местоположению код ki. После этого осуществляется сдвиг спи-
ска кодов:
                  {k1, k2, ..., ki, ..., kn} → {k2, k3, ..., kn, k1}.
     Таким образом, список кодов образует замкнутое кольцо.
     Смысловое кодирование – это кодирование, в котором в качестве ис-
ходного алфавита используются не только отдельные символы (буквы), но
и слова и даже наиболее часто встречающиеся фразы.
     Рассмотрим пример одноалфавитного и многоалфавитного смыслово-
го кодирования.
     Пример. Открытый текст: "19.9.1992 ГОДА" (табл. 2.10).

                        2.10. Таблица кодирования
      Элементы откpытого текста                                    Коды
                 1                                         089 146 214 417
                 2                                         187 226 045 361
                 9                                         289 023 194 635
                ГОД                                        031 155 217 473
                  .                                        786 432 319 157

     Закодированное сообщение при одноалфавитном кодировании:
     "089 289 786 289 786 089 289 289 187 031".
     Закодированное сообщение при многоалфавитном кодировании:
     "089 289 786 023 432 146 194 635 187 031" (при многоалфавитном ко-
дировании одинаковые символы заменяются кодами из следующего столб-
ца).
     Среди различных кодов, применяемых для кодирования естественных
языков, особый интерес вызывает код Хаффмена, который позволяет сжи-
мать открытый текст. Суть его состоит в присваивании наиболее часто
встречающимся буквам наиболее коротких кодов.
     Строка двоичных символов кодов Хаффмена единственным образом
разлагается на коды символов (такие коды называются префиксными).
     Пример. Закодированное кодом Хаффмена сообщение имеет вид:
     "01101000100000010101111000100000".
     Пользуясь деpевом для английского языка, получаем 0110=S.
     Далее снова начинаем движение из вершины: 100=E; 01000=C;
00010=U; 1011=R; 1010=I; 001=T; 00000=Y.
     Открытый текст: "SECURITY".

                           2.7.5. ДРУГИЕ МЕТОДЫ
     Широкое применение персональная ЭВМ (ПЭВМ) сделало актуальной
задачу защиты хранящихся данных (файлов). Для защиты файлов могут
быть применены рассмотренные методы шифрования и кодирования.
     Специфика применения ПЭВМ позволяет реализовать дополнитель-


ные методы кодирования для надежного закрытия содержимого файлов.
Примером такого кодирования является метод рассечения-разнесения, в
соответствии с которым содержимое одного файла разбивается на блоки,
которые разносятся по нескольким файлам. Каждый такой файл не несет
никакой информации, а сбор данных в единое целое осуществляется про-
стой программой.
     Пример. Блок (файл открытого текста) начинается словами: "МЕ-
ТОД_РАССЕЧЕНИЯ-РАЗНЕСЕНИЯ".
     Для рассечения блока открытого текста на 8 частей запишем откры-
тый текст в следующем виде (табл. 2.11).

                       2.11. Рассечения открытого текста

    1    2    3    4      1   2   3    4    1    2    3    4    1    2    3    4

1   М    Е    Т    О      С   С   Е    Ч    –    Р    А    З    Н    И    Я    _

2   Д    _    Р    А      Е   Н   И    Я    Н    Е    С    Е
     Для рассечения текста на 8 частей выбраны 2 строки и 4 столбца.
Пусть столбцы sj выбираются в последовательности {4, 1, 3, 2}, а строки ri
– в последовательности {2, 1}. Тогда номер k блока Фk, куда записывается
очередной символ открытого текста, определяется по формуле
                              k = (ri – 1)n + sj,
где n – число столбцов.
      Первый символ М запишется в блок с номером (ri = 2, sj = 4) : k = (2 –
1)*4 + 4 = 8; второй символ E – в блок с номером (ri = 2, sj = 1) : k = (2 – 1)*4
+ 1 = 5, и т.д.
      Тогда блоки Фk, записанные в порядке номеров, будут содержать
следующие       символы:    Ф1 = (_НЕ...),      Ф2 = (АЯЕ...),    Ф3 = (РИС..,),
Ф4 = {ДЕН...), Ф5 = {ЕСРИ...}, Ф6 = {ОЧЗ...), Ф7 = {ТЕАЯ...), Ф8 = {МС-
Н...}. Таким образом, один блок открытого текста заменяется восемью бло-
ками, которые в сумме дают длину исходного блока.
      Одной из важных проблем при использовании ПЭВМ является про-
блема хранения больших массивов данных. Для этой цели применяют раз-
личные методы сжатия данных (сжатие рассматривается как метод кодиро-
вания).
      Методы сжатия данных осуществляют такое преобразование повто-
ряющихся символов и строк символов, которое позволяет использовать для
хранения данных меньший объем памяти. Методы сжатия можно разделить на
два класса: статические и динамические (адаптивные).
      Методы статического сжатия данных эффективны, когда частоты по-
явления символов изменяются незначительно. Методы динамического сжа-
тия адаптивно отслеживают неравномерности частот появления символов с
сохранением последовательности изменений вероятностей появления сим-
волов.
      Адаптивные методы сжатия могут динамично реагировать на измене-
ния в открытом тексте, происходящие по мере кодирования. Первые такие
методы являлись модификацией кодов Хаффмена и использовали счетчики
для хранения текущих частот появления каждого символа. При таких мето-
дах наиболее часто встречающиеся символы сдвигаются ближе к корню
дерева и, следовательно, получают более короткие кодовые слова.
      Кодирование Лемпеля-Зива использует синтаксический метод для ди-
намического источника. Этот метод осуществляет синтаксический анализ
символьных потоков, которые не превышают заданной длины, и строит
таблицу отображения этих потоков в кодированные слова фиксированной
длины. Длина кодового слова зависит от размера таблицы, используемой
для хранения кодового отображения поток-слово. Например, размер табли-
цы в 4096 слов требует 12-битового кодового слова. Кодовое слово являет-
ся просто табличным адресом соответствующих слов в таблице.
      При кодировании по методу Лемпеля-Зива-Уэлча таблица инициали-
зируется символьным множеством и содержит вместо потоков заданной
длины пары (кодовое слово, символ) фиксированной длины. Таблица стро-
ится на основе синтаксического анализа самого длинного опознанного в
таблице потока и использовании последующего символа для формирования
нового входа в таблицу. Это позволяет уменьшить размеры таблицы.


    В последнее время широкое распространение получили методы сжа-
тия на основе расширяющихся деревьев. Префиксный код переменной
длины в этих методах строится на основе положения символов в дереве.
Для получения оптимальных кодов дерево балансируется.
    Несомненно, криптография должна стать обязательным компонентом
защиты всех сколько-нибудь развитых систем. К сожалению, этому мешает
огромное количество самых разных барьеров.

                      КОНТРОЛЬНЫЕ ВОПРОСЫ
     1. Дайте определение шифра и сформулируйте основные требования
к нему.
     2. Назовите и охарактеризуйте методы шифрования.
     3. Дешифруйте сообщение, зашифрованное с помощью шифра про-
стой замены: " 11 03 18 21 11 04 15 02 13 29 12 10 01 28 02 18 21 11 01 28 28
12 30 12 21 32 04 00 27 32 01 21 11 12 27 32 01 32 12 14 28 12 21 28 01 23 32
02 21 22 04 27 32 12 21 28 01 21 00 12 32 12 29 12 22 21 28 01 06 12 11 02 32
27 18 21 27 03 12 10 12 21 11 04 15 02 13 29 12 10 01 28 02 04".
     4. Поясните, что вы понимаете под совершенным шифром. Приведи-
те пример совершенного шифра.
     5. Дешифруйте следующее сообщение: "15 03 23 21 22 32 14 06 25 14
04 07 24 16 31" методом перебора всех возможных ключей. Исходное со-
общение состоит из цифр от 0 до 32, которыми закодированы буквы в соот-
ветствии с табл. 4. Шифрование произведено сложением по модулю 32 с
псевдослучайной гаммой: K, (K2) mod 32, …, (Kn) mod 32, где K – неизвест-
ный ключ из множества чисел от 0 до 32.
     6. Перечислите основные режимы работы, предусмотренные в рос-
сийском стандарте на шифрование данных.
     7. Проведите сравнительный анализ параметров алгоритмов шифро-
вания DES, AES и Российского стандарта (в режиме простой замены).
     8. Сравните наиболее распространенные стандарты шифрования.
            3. АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ



                          3.1. Общие положения

     Еще одним обширным классом криптографических систем являются
так называемые асимметричные или двухключевые системы. Эти системы
характеризуются тем, что для шифрования и для расшифрования исполь-
зуются разные ключи, связанные между собой некоторой зависимостью.
Применение таких шифров стало возможным благодаря К. Шеннону пред-
ложившему строить шифр таким способом, чтобы его раскрытие было эк-
вивалентно решению математической задачи, требующей выполнения объ-
емов вычислений, превосходящих возможности современных ЭВМ (на-
пример, операции с большими простыми числами и их произведениями).
     Один из ключей (например, ключ шифрования) может быть сделан
общедоступным, и в этом случае проблема получения общего секретного
ключа для связи отпадает. Если сделать общедоступным ключ расшифро-
вания, то на базе полученной системы можно построить си-стему аутенти-
фикации передаваемых сообщений. Поскольку в большинстве случаев один
ключ из пары делается общедоступным, такие системы получили также
название криптосистем с открытым ключом.
     Первый ключ не является секретным и может быть опубликован для
использования всеми пользователями системы, которые зашифровывают
данные. Расшифрование данных с помощью известного ключа невозможно.
Для расшифрования данных получатель зашифрованной информации ис-
пользует второй ключ, который является секретным. Разумеется, ключ
расшифрования не может быть определен из ключа зашифрования.
     Использование асимметричного шифрования иллюстрирует рис. 3.1.
     Криптосистема с открытым ключом определяется тремя алгоритмами:
генерации ключей, шифрования и расшифрования. Алгоритм генерации



    
Яндекс цитирования Яндекс.Метрика