30546

Блочные шифры. Ключевая система блочных шифров. Российский стандарт на блочный шифр ГОСТ 28147-89

Доклад

Математика и математический анализ

Представляют собой семейство обратимых преобразований блоков частей фиксированной длины исходного текста. Если для шифрования исходного текста используется подсистема π из Π ∈ SYM то получающуюся в результате систему подстановок Π называют системой блочных шифров или системой блочных подстановок. Если информация исходного текста не может быть представлена Nразрядными блоками как в случае стандартного алфавитноцифрового текста то первое что нужно сделать это перекодировать исходный текст именно в этот формат причем с...

Русский

2013-08-24

492.5 KB

18 чел.

89. Блочные шифры. Ключевая система блочных шифров. Российский стандарт на блочный шифр ГОСТ 28147-89

Доска:

х = (,  , ..., ) € ;

Выступление:

Блочные шифры.

Представляют собой семейство обратимых преобразований блоков (частей фиксированной длины) исходного текста. Фактически блочный шифр - это система подстановки на алфавите блоков (она может быть моно- или многоалфавитной в зависимости от режима блочного шифра).

Общие сведения о блочных шифрах.

Под N-разрядным блоком будем понимать последовательность из нулей и единиц длины N3:

х = (,  , ..., ) € ;

х в  можно интерпретировать как вектор и как двоичное представление целого числа

Блочным шифром будем называть элемент π €  SYM():

π: х—>у = π(х), где х = (,  , ..., ), у =(,  , ..., ). Большинство симметричных шифров, используемых в системах передачи информации, являются блочными и  блочные шифры удобнее всего описывать в алгоритмическом виде, а не как обычные подстановки.

    Если исходный текст шифруется подстановкой π, выбранной из полной симметрической группы, то злоумышленник, изучающий соответствие между подмножествами исходного и шифрованного текстов

хi ↔ yi , 0 ≤ i ≤ m,

не в состоянии на основе этой информации определить исходный текст, соответствующий y { yi } .

    Если для шифрования исходного текста используется подсистема π из Π SYM(), то получающуюся в результате систему подстановок Π называют системой блочных шифров или системой блочных подстановок.

Блочный шифр представляет собой частный случай моноалфавитной подстановки с алфавитом  = . Если информация исходного текста не может быть представлена N-разрядными блоками, как в случае стандартного алфавитно-цифрового текста, то первое, что нужно сделать, это перекодировать исходный текст именно в этот формат, причем с практической точки зрения неважно, какой из способов перекодирования был применен.

    Ключевой системой блочных шифров является подмножество Π[K] симметрической группы SYM()

П[ K ] = {π{k} : k K } ,

индексируемое по параметру k K ; k является ключом, а K – пространством ключей. При этом не требуется, чтобы различные ключи соответствовали различным подстановкам .

    Ключевая система блочных шифров Π[K] используется следующим образом. Пользователь i и пользователь j некоторым образом заключают соглашение относительно ключа k из K, выбирая, таким образом, элемент из Π[K] и передавая текст, зашифрованный с использованием выбранной подстановки.

    Запись y = π{k , x} используется для обозначения N-разрядного блока шифрованного текста, который получен в результате шифрования N-разрядного блока исходного текста х с использованием подстановки π{k} , соответствующей ключу k.

   Предположим, что злоумышленнику:

   • известно пространство ключей K;

   • известен алгоритм определения подстановки π{k} по значению ключа k;

   • неизвестно, какой именно ключ k выбрал пользователь.

   Какими возможностями располагает злоумышленник? Он может:

   • получить ключ вследствие небрежности пользователя i или пользователя j;

   • перехватить шифрованный текст у, передаваемый пользователем i пользователю j, и производить пробы на все возможные ключи из K до получения читаемого сообщения исходного текста;

   • получить соответствующие исходный и шифрованный тексты x → y и воспользоваться методом пробы на ключ;

   • получить соответствующие исходный и шифрованный тексты и исследовать соотношение исходного текста х и шифрованного текста у для определения ключа k;

   • организовать каталог N-разрядных блоков с записью частот их появления в исходном или шифрованном тексте. Каталог дает возможность производить поиск наиболее вероятных слов, используя, например, следующую информацию: листинг на языке ассемблера характеризуется сильно выраженным структурированным форматом, цифровое представление графической и звуковой информации имеет ограниченный набор знаков.

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки). Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты — A, старшие биты — B). На i-ом цикле используется подключ Ki:

 mod 2 ( = двоичное «исключающее или»)

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8.

Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим). Ключи K25…K32 являются ключами K1…K8, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A33 и B33 склеиваются (обратите внимание, что старшим битом становится A33, а младшим — B33) — результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей Ki.

Функция  вычисляется следующим образом:

Ai и Ki складываются по модулю 232.

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. 

Дополнительно:

    Предположим, что N = 64 и каждый элемент SYM() может быть использован как подстановка, так что K = SYM(). Тогда:

    • существует 264 64-разрядных блоков, но злоумышленник не может поддерживать каталог с  264 ≈ 1,8 1019 строками;

    • проба на ключ при числе ключей, равном (264)!, практически невозможна; соответствие исходного и шифрованного текстов для некоторых N-разрядных блоков

π{k , xi } , 0 ≤ i < m, не дает злоумышленнику информации относительно значения π{k , x} для х {xi}.

    Системы шифрования с блочными шифрами, алфавитом  и пространством ключей K = SYM() являются неделимыми в том смысле, что поддержание каталога частот появления букв для 64-разрядных блоков или проба на ключ при числе ключей 264 выходит за пределы возможностей злоумышленника. Следует сравнить эту проблему с той задачей, с которой сталкивается злоумышленник в процессе криптоанализа текста, зашифрованного подстановкой Цезаря с алфавитом {А, ..., Я, _}; для определения ключа подстановки Цезаря требуется лишь log232 = 5 бит, в то время как для пространства ключей K = SYM() требуется 264 бит.

    К сожалению, разработчик и злоумышленник находятся в одинаковом положении: разработчик не может создать систему, в которой были бы реализованы все 264! подстановок SYM(), а злоумышленник не может испытать такое число ключей. Остается согласиться с тем, что не каждый элемент из SYM() будет использован в качестве подстановки.

    Таким образом, требования к хорошему блочному шифру формулируются следующим образом. Необходимы:

   • достаточно большое N (64 или более) для того, чтобы затруднить составление и поддержание каталога (в новом стандарте шифрования США N не менее 128);

   • достаточно большое пространство ключей для того, чтобы исключить возможность подбора ключа;

   • сложные соотношения π{k , x} : х → y = π{k , x} между исходным и шифрованным текстами с тем, чтобы аналитические и (или) статистические методы определения исходного текста и (или) ключа на основе соответствия исходного и шифрованного текстов были бы по возможности нереализуемы.

ГЕНЕРИРОВАНИЕ БЛОЧНЫХ ШИФРОВ

    Одним из наиболее распространенных способов задания блочныхшифров является использование так называемых сетей Фейстеля. Сеть Фейстеля представляет собой общий метод преобразования произвольной функции (обычно называемой F-функцией) в перестановку на множестве

блоков. Эта конструкция была изобретена Хорстом Фейстелем и была использована в большом количестве шифров, включая DES и ГОСТ 28147–89. F-функция, представляющая собой основной строительный блок сети

Фейстеля, всегда выбирается нелинейной и практически во всех случаях необратимой.

    Формально F-функцию можно представить в виде отображения

                          F : →  ,

где N – длина преобразуемого блока текста (должна быть четной); k – длина используемого блока ключевой информации.

    Пусть теперь X – блок текста, представим его в виде двух подблоков одинаковой длины X = {А, В}. Тогда одна итерация (или раунд) сети Фейстеля определяется как

                         = ||( F ( , )  ) ,

где X i = { Ai , Bi } , || операция конкатенации, а – побитовое исключающее ИЛИ.

    Структура итерации сети Фейстеля представлена на рис. 

Сеть Фейстеля состоит из некоторого фиксированного числа итераций, определяемого соображениями стойкости разрабатываемого шифра, при этом на последней итерации перестановка местами половин блока текста не производится, так как это не влияет на стойкость шифра.

    Данная структура шифров обладает рядом достоинств, а именно:

    • процедуры шифрования и расшифрования совпадают, с тем исключением, что ключевая информация при расшифровании используется в обратном порядке;

    • для построения устройств шифрования можно использовать те же блоки в цепях шифрования и расшифрования.

    Недостатком является то, что на каждой итерации изменяется только половина блока обрабатываемого текста, что приводит к необходимости увеличивать число итераций для достижения требуемой стойкости.

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

    Другим подходом к построению блочных шифров является использование обратимых зависящих от ключа преобразований. В этом случае на каждой итерации изменяется весь блок и, соответственно, общее количество итераций может быть сокращено. Каждая итерация представляет собой последовательность преобразований (так называемых "слоев"), каждое из которых выполняет свою функцию. Обычно используются слой нелинейной обратимой замены, слой линейного перемешивания и один или два слоя подмешивания ключа K недостаткам данного подхода можно отнести то, что для процедур шифрования и расшифрования в общем случае нельзя использовать одни и те же блоки, что увеличивает аппаратные и/или программные затраты на реализацию.


 

А также другие работы, которые могут Вас заинтересовать

19884. Провадження слідчих дій 212 KB
  ТЕМА 11: Провадження слідчих дій 1. Поняття і сутність слідчих дій 2. Загальна характеристика слідчих дій 1. Поняття і сутність слідчих дій При розслідуванні кримінальної справи слідчий виконує дії та ухвалює рішення передбачені або зумовлені кримінальнопроцесуа
19886. Притягнення як обвинуваченого 149 KB
  ТЕМА 12: Притягнення як обвинуваченого План 1. Поняття і підстави притягнення особи як обвинуваченого. 2. Процесуальне оформлення притягнення особи як обвинуваченого. 3. Пред'явлення обвинувачення. Допит обвинуваченого. 4. Притягнення як обвинувачених окремих посадо...
19887. Застосування запобіжних заходів 122.5 KB
  ТЕМА 13: Застосування запобіжних заходів План 1. Поняття підстави і мета застосування заходів процесуального примусу. 2. Види запобіжних заходів. 3. Процесуальний порядок обрання зміни і скасування запобіжного заходу. 1. Поняття підстави і мета застосування захо
19888. Зупинення і закінчення досудового слідства 131 KB
  ТЕМА 14: Зупинення і закінчення досудового слідства 1. Поняття підстави та процесуальний порядок зупинення досудового слідства 2. Підстави форми та процесуальний порядок закінчення досудового слідства 1. Поняття підстави та процесуальний порядок зупинення досуд
19889. Прокурорський нагляд за виконанням законів при провадженні дізнання і досудового слідства 46.17 KB
  ТЕМА 15: Прокурорський нагляд за виконанням законів при провадженні дізнання і досудового слідства План 1. Сутність прокурорського нагляду за органами дізнання і досудового слідства. 2. Форми і методи прокурорського нагляду за провадженням дізнання і досудового слі...
19890. Підсудність. Попередній розгляд справи суддею 25.78 KB
  ТЕМА 16: Підсудність. Попередній розгляд справи суддею План 1. Поняття і значення підсудності. 2. Види підсудності. 3. Процесуальний порядок попереднього розгляду справи суддею. 1. Поняття і значення підсудності Правосуддя в Україні здійснюється виключно судами.
19891. Судовий розгляд кримінальної справи 49.77 KB
  ТЕМА 17: Судовий розгляд кримінальної справи 1. Загальні положення судового розгляду. 2. Підготовча частина судового засідання. 3. Судове слідство 4. Судові дебати та останнє слово підсудного. 5. Постановлення вироку. 1. Загальні положення судового розгляду Судови...
19892. Провадження справ у апеляційній інстанції 48.86 KB
  ТЕМА 18: Провадження справ у апеляційній інстанції План 1. Суть завдання та основні риси апеляційного провадження. 2. Суб'єкти процесуальний порядок і строки розгляду в суді кримінальних справ у апеляційному провадженні. 3. Скасування зміна вироку ухвали постанови ...