30546

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

Доклад

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

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

Русский

2013-08-24

492.5 KB

17 чел.

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 недостаткам данного подхода можно отнести то, что для процедур шифрования и расшифрования в общем случае нельзя использовать одни и те же блоки, что увеличивает аппаратные и/или программные затраты на реализацию.


 

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

53397. Використання інформаційних технологій на уроках математики 1.49 MB
  Застосування компютерної техніки на уроках дозволяє зробити урок нетрадиційним яскравим насиченим наповнюючи його зміст знаннями з інших наочних областей що перетворюють математику з об'єкту вивчення в засіб отримання нових знань. Ефективність застосування нових інформаційних технологій на уроках математики обумовлена наступними факторами: 1 різноманітність форм представлення інформації; 2 висока степінь наочності; 3 можливість моделювання за допомогою комп’ютера різноманітних об’єктів і процесів; 4 звільнення від рутинної роботи...
53398. Засоби пошуку інформації в Інтернеті. Принципи функціонування веб-каталогів та пошукових систем. Стратегії пошуку інформації 1.56 MB
  Сьогодні на уроці продовжим вивчати сільське господарство, характеристику тваринництва, узагальнемо спеціалізацію сільського господарства, ознайомимось і оцінемо проблеми і перспективи розвитку сільського господарства, завершимо виконання практичної роботи №9, використовуючи знання з інформатики.
53399. Алгоритм 434 KB
  В цей час решта членів команд задіяні в перехресному опитуванні: задають один одному по 3 теоретичних питання за темою, які готували дома заздалегідь, причому, задають питання та дають відповіді різні члени команди. Оцінює команди журі, до складу якого входять 2 найбільш підготовлених студента (1 бал за кожну правильну відповідь). Вони ж здійснюють контроль часу.
53400. Засоби масової інформації 66 KB
  Good afternoon boys and girls. I’m very glad to see you. We are also pleased to see our guests today and we’ll try to make our lesson useful and interesting. Today we are having our last lesson on Mass Media and our aim is to generalize our knowledge on this question and to get to know something new concerning mass media.
53401. Основні команди роботи з робочою книгою та її аркушами 607.5 KB
  Актуальність теми : при роботі з великими об’ємами даних важливе значення відіграє їх наглядність та наочність. І навіть наша приймальна комісія використовує електронні таблиці для сортування абітурієнтів та створення бази даних та ведення документації по прийому технікуму.Навчальні цілі заняття : знати правила створення формул в Excel математичні функції СЧЕТЕСЛИ ЧСТРОК ЕСЛИ ІІ рівень абстракції; Оволодіти навичками заповнення електронних таблиць ручним та автоматичним типом вводу даних навчитися проводити розрахунки за...
53402. Інтелектуальне інформ –кафе 525 KB
  Мета: в ігровій формі дати можливість старшокласникам проявити свої розумові та творчі здібності; повторити й закріпити основний матеріал у нестандартній формі; розширити знання про звязки інформатики з іншими предметами; сприяти інтелектуальному та духовному розвитку особистості; розвивати стійкий інтерес до інформатики; формувати творчу особистість; формувати...
53403. Уведення та редагування тексту. Перевірка правопису 69 KB
  Мета уроку Навчальна: Вдосконалити основні знання про текстовий редактор Microsoft Word та його можливості навчити вводити та редагувати текст засобами текстового процесора створювати документи за певною структурою засвоїти правила введення тесту навчитись проводити перевірку правопису. Тип уроку Урок засвоєння нових знань формування умінь та навичок Обладнання Комп’ютери підключені до локальної мережі текстовий процесор Microsoft Word текстовий документ до уроку UROK. Повідомлення теми та плану роботи на уроці мети та завдань...
53404. Розв’язування задач з використанням циклічних операторів 69.5 KB
  Мета: створити умови для формування навичок розв’язування найпростіших задач що містять цикли використовуючи різні команди повторення; розвивати логічне мислення операторську культуру; продемонструвати виконання на комп’ютері різних циклічних програм; виховувати працьовитість інтерес до предмета. Вправа Online Вибудуємо лінію ключових слів з теми Циклічні оператори Цикл повторення параметр циклдоки циклдо циклдля змінна лічильник оператор логічний вираз умова while repet begin end pscl програма виконання. На...
53405. Оформлення тексту в HTML – документі 234 KB
  Хід уроку Перед початком уроку на учнівські комп’ютери та робоче місце вчителя має бути розміщено папки : Організаційний момент Актуалізація опорних знань Учитель пропонує учням виконати завдання “Магічний квадрат. Завдання має бути виведене на інтерактивну дошку а кожен учень повинен отримати картку з наступним текстом : Юний друже Для виконання даного завдання знайди файл що міститься за наступною адресою : C: Documents nd Settings Учень Рабочий стол HTML Урок _3 mgic. Бажаю успіху D O C T I T H B T B D L E H Y G T...