No Image

Шифрование гост 28147 89 примеры

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

Выполните первый цикл алгоритма шифрования ГОСТ 28147 89 в режиме простой замены. Для получения 64 бит исходного текста используйте 8 первых букв из своих данных: Фамилии Имени Отчества. Для получения ключа (256 бит) используют текст, состоящий из 32 букв. Первый подключ содержит первые 4 буквы.

Задача №3. Алгоритм шифрования rsa.

Сгенерируйте открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

Задача №4. Функция хеширования.

Найти хеш–образ своей Фамилии, используя хеш–функцию , гдеn = pq.

Задача №5. Электронная цифровая подпись.

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

Примеры выполнения заданий

Задача №1. Шифр Цезаря. Используя шифр Цезаря, зашифруйте свои данные: Фамилию Имя Отчество.

«КОЗИНА ГАЛИНА ЛЕОНИДОВНА»

Используем алфавит, содержащий 33 буквы и пробел, стоящий после буквы Я:

Ключом в шифре Цезаря является число 3. Каждая буква в исходном тексте сдвигается по алфавиту на 3 позиции. Таким образом, получаем:

Задача №2. Алгоритм шифрования ГОСТ 28147-89. Выполните первый цикл алгоритма шифрования ГОСТ 28147-89 в режиме простой замены. Для получения 64 бит исходного текста используйте 8 первых букв из своих данных: Фамилии Имени Отчества. Для получения ключа (256 бит) используют текст, состоящий из 32 букв. Первый подключ содержит первые 4 буквы.

Исходные данные для зашифрования: КОЗИНА Г

Для ключа возьмем последовательность состоящую из 32 букв:

АЛИНа пошла в лес собирать грибы

Для первого подключа Х используем первые 4 буквы ключа: АЛИН.

Переводим исходный текст и первый подключ в двоичную последовательность (см. Приложение Б):

первый подключ X0

Таким образом, первые 64 бита определяют входную последовательность

L0: 11001010 11001110 11000111 11001000

R0: 11001101 11000000 00100000 11000011

следующие 32 бита определяют первый подключ

Х0: 11000000 11001011 11001000 11001101

I. Найдем значение функции преобразования f(R0,X0) (см. Приложение А)

1). Вычисление суммы R0 и X0 по mod 2 32

R0: 1100 1101 1100 0000 0010 0000 1100 0011

Х0: 1100 0000 1100 1011 1100 1000 1100 1101

1000 1110 1000 1011 1110 1001 1001 0000

2). Преобразование в блоке подстановки

Результат суммирования R0+X0 по mod 2 32

1000 1110 1000 1011 1110 1001 1001 0000

преобразуем в блоке подстановки (см. Приложение В). Для каждого 4-битного блока вычислим его адрес в таблице подстановки. Номер блока соответствует номеру столбца, десятичное значение блока соответствует номеру строки в таблице. Таким образом, 5-тый блок (1011) заменяется заполнением 11-ой строки и пятого столбца в таблице подстановки (1110).

8 7 6 5 4 3 2 1

1000 1110 1000 1011 1110 1001 1001 0000

соответствующие номера строк в таблице подстановки

8 14 8 11 14 9 9 0

9 2 3 14 5 15 3 4

1001 0010 0011 1110 0101 1111 0011 0100

3). Циклический сдвиг результата п.2 на 11 бит влево

1111 0010 1111 1001 1010 0100 1001 0001

Таким образом, нашли значение функции f (R0,X0):

1111 0010 1111 1001 1010 0100 1001 0001

II. Вычисляем R1= f(R0,X0) L0.

Результат преобразования функции f(R0,X0) складываем с L0 по mod2:

L0: 1100 1010 1100 1110 1100 0111 1100 1000

f(R0,X0): 1111 0010 1111 1001 1010 0100 1001 0001

R1: 0011 1000 0011 0111 0110 0011 0101 1001

Задача №3. Алгоритм шифрования RSA. Сгенерируйте откры-тый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

I.Генерация ключей (см. Приложение Г).

Выберем два простых числа р = 13 и q = 19 (см. Приложение Д).

и функция Эйлера

Закрытый ключ d выбираем из условий d 2 mod n = ( 8 + 12) 2 mod 247 = 400 mod 247=153

H2=(H1+M2) 2 mod n = (153 + 16) 2 mod 247 = 28561 mod 247= 156

H3=(H2+M3) 2 mod n = (156 + 9) 2 mod 247 = 27225 mod 247= 55

H4=(H3+M4) 2 mod n = ( 55 + 10) 2 mod 247 = 4225 mod 247= 26

H5=(H4+M5) 2 mod n = ( 26 + 15) 2 mod 247 = 1681 mod 247= 199

H6=(H5+M6) 2 mod n = (199 + 1) 2 mod 247 = 40000 mod 247= 233

В итоге получаем хеш-образ сообщения «КОЗИНА», равный 233.

Задача №5. Электронная цифровая подпись. Используя хеш-образ своей Фамилии, вычислите электронную цифровую подпись по схеме RSA.

Пусть хеш-образ Фамилии равен 233, а закрытый ключ алгоритма RSA равен (25, 247). Тогда электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу (см. Приложение Ж)

s = 233 25 mod 247 = 168.

Для проверки ЭЦП, используя открытый ключ (121, 247), найдем

H = 168 121 mod 247 = 233.

Поскольку хеш-образ сообщения совпадает с найденным значением H, то подпись признается подлинной.

О реализации этого алгоритма шифрования уже рассказывал FTM: как в общем и целом, так и про режим простой замены. После изучения существующих библиотек и отдельных реализаций этого ГОСТа на C# я решил написать свой велосипед, в первую очередь, ради интереса и опыта. Результатами этой работы мне и хотелось бы поделиться с уважаемым сообществом.

ГОСТ 28147-89 — симметричный блочный алгоритм шифрования с 256-битным ключом, оперирует блоками данных по 64 бита.
Один из режимов его работы, гаммирования с обратной связью, является потоковым режимом блочного шифра.

Описание алгоритма

  1. Исходное сообщение разбивается на блоки по 64 бита
  2. На каждый блок XOR’ом «накладывается» гамма, тоже длиной 64 бита
  3. Гамма формируется шифрованием 64-битного блока «состояния» с помощью ключа в режиме простой замены
    • В момент начала шифрования сообщения блок принимается равным синхропосылке или вектору инициализации
    • В следующей итерации вместо синхропосылки используется зашифрованный блок текста из предыдущей
    Читайте также:  Формат lossless что это

    Обратите внимание, что приведённая последовательность действий справедлива как для шифрования, так и расшифрования. Разница в том, откуда берётся зашифрованный блок текста для обработки следующего блока, это лучше всего видно на картинке:

    Реализация

    Данный алгоритм был реализован в форме плагина к менеджеру паролей KeePass.
    Исходники доступны на GitHub.

    Гаммирование с обратной связью

    Ниже приведён фрагмент кода класса, реализующего стандартный интерфейс ICryptoTransform, собственно выполняющий криптографическое преобразование данных поблочно. При создании экземпляра в атрибут _state записывается значение синхропосылки, в дальнейшем от направления работы (шифрование или расшифровывание) в него заносится очередной блок зашифрованных данных.

    Режим простой замены

    GostECB.Process — реализация того же ГОСТа в режиме простой замены, или «электронной кодовой книги». Хорошее описание алгоритма есть в соответствующем разделе статьи Википедии, а также в статье ГОСТ 28147-89 (Часть 2. Режим простой замены) на Хабрахабре.

    Размер снихропосылки, гаммы и «состояния» равен 64 байтам, поэтому шифрование в режиме простой замены можно рассматривать в рамках одного блока. Впрочем, было бы несколько — они просто шифровались бы по очереди.

    Для работы с 32-битными частями исходного блока очень удобно использовать тип uint.
    Так, в функции F() сложение по модулю ключа и части блока, а также циклический сдвиг на 11 бит запишется просто и лаконично:

    Метод подстановки по S-блокам работает с 4-битными кусочками 32-битного подблока, их достаточно удобно отделять побитовым сдвигом и дальнейшим умножением на 0x0f:

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

    Известный исследователь, основоположник алгебраического криптоанализа Николя Куртуа утверждает, что блочный шифр ГОСТ, который в ближайшее время должен был стать международным стандартом, фактически взломан и ожидает в дальнейшем множества публикаций, которые должны развить его идеи о нестойкости этого алгоритма.

    Далее приведены краткие выдержки из этой работы, которую можно рассматривать как алармистский выпад в разгаре международной стандартизации (схожими преувеличениями автор был известен и в отношении AES, однако его работы тогда оказали большое теоретическое влияние на криптоанализ, но так и не привели на сегодняшний момент к практическим атакам на сам AES). Но, возможно, это и реальное предупреждение о начале этапа "пикирующего в штопор самолёта", которое может закончиться крахом национального стандарта шифрования, как это было с алгоритмом хэширования SHA-1 и алгоритмом хэширования "де-факто" MD5.

    ГОСТ 28147-89 был стандартизирован в 1989 году и впервые стал официальным стандартом защиты конфиденциальной информации, но спецификация шифра оставалась закрытой. В 1994 году стандарт был рассекречен, опубликован и переведён на английский язык. По аналогии с AES (и в отличие от DES), ГОСТ допущен к защите секретной информации без ограничений, в соответствии с тем, как это указано в российском стандарте. Т.о. ГОСТ — это не аналог DES, а конкурент 3-DES с тремя независимыми ключами или AES-256. Очевидно, что ГОСТ — это достаточно серьёзный шифр, удовлетворяющий военным критериям, созданный с расчётом на самые серьёзные применения. По крайней мере два набора S-блоков ГОСТа были идентифицированы на основе приложений, используемых российскими банками. Эти банки нуждаются в проведении секретных коммуникаций с сотнями филиалов и защите миллиардов долларов от мошеннических хищений.

    ГОСТ — это блочный шифр с простой структурой Файстеля, с размером блока 64 бита, 256-битным ключом и 32 раундами. Каждый раунд содержит сложение с ключом по модулю 2^32, набор из восьми 4-битных S-блоков и простой циклический сдвиг на 11 битов. Особенностью ГОСТа является возможность хранения S-блоков в секрете, что можно представить как второй ключ, увеличивающий эффективный ключевой материал до 610 битов. Один набор S-блоков был опубликован в 1994 году в рамках спецификации хэш-функции ГОСТ-Р 34.11-94 и, как писал Шнайер, использовался Центральным Банком Российской Федерации. Он также вошёл в стандарт RFC4357 в части "id-GostR3411-94-CryptoProParamSet". В исходных кодах в конце книги Шнайера была ошибка (в порядке S-блоков). Наиболее точную эталонную реализацию исконно российского происхождения сейчас можно встретить в библиотеке OpenSSL. Если где-то применяются секретные S-блоки, то они могут быть извлечены из программных реализаций и из микросхем, по факту чего были опубликованы соответствующие работы.

    ГОСТ — серьёзный конкурент

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

    Неудивительно, что ГОСТ стал интернет-стандартом, в частности, он включён во многие криптобиблиотеки, такие как OpenSSL и Crypto++, и становится всё популярнее за пределами страны своего происхождения. В 2010 году ГОСТ был заявлен на стандартизацию ISO как всемирный стандарт шифрования. Крайне малое количество алгоритмов смогли стать международными стандартами. ISO/IEC 18033-3:2010 описывает следующие алгоритмы: четыре 64-битных шифра — TDEA, MISTY1, CAST-128, HIGHT — и три 128-битных шифра — AES, Camellia, SEED. ГОСТ предлагается добавить в этот же самый стандарт ISO/IEC 18033-3.

    Читайте также:  Телефоны на горбушке отзывы

    Впервые в истории промышленной стандартизации мы имеем дело со столь конкурентоспособным алгоритмом в терминах оптимальности между стоимостью и уровнем безопасности. ГОСТ имеет за собой 20 лет попыток криптоанализа и до недавних пор его безопасность военного уровня не подвергалась сомнению.

    Как стало недавно известно автору из приватной переписки, большинство стран высказались против ГОСТа на голосовании ISO в Сингапуре, однако результаты этого голосования будут ещё рассматриваться на пленарном заседании ISO SC27, так что ГОСТ всё ещё находится в процессе стандартизации на момент публикации этой работы.

    Мнения экспертов по поводу ГОСТ

    Ничто из имеющихся сведений и литературы по поводу ГОСТа не даёт оснований полагать, что шифр может быть небезопасным. Наоборот, большой размер ключа и большое число раундов делают ГОСТ, на первый взгляд, подходящим для десятилетий использования.

    Все, кому знаком закон Мура, понимают, что, в теории, 256-битные ключи останутся безопасными по крайней мере 200 лет. ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайер, Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.

    Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенноновскими подстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было". Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).

    Линейный и дифференциальный анализ ГОСТ

    В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов. На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2-360).

    Более сложные атаки включают множества дифференциалов, следующих определённым паттернам, например с использованием отдельных S-блоков, имеющих нулевые дифференциалы, в то время как на других битах имеются ненулевые. Речь об атаках-различителях, основанных на плохих диффузионных свойствах ГОСТа. Лучшая из таких атак работает против 17 раундов ГОСТа, зависит от ключа и имеет сама по себе на выходе крайне слабый различитель от случайных данных, чтобы его как-то можно было использовать для получения информации о ключе.

    Атаки скольжения и отражения

    Согласно Бирюкову и Вагнеру, структура ГОСТа, включающая обратный порядок подключей в последних раундах, делает его стойким против атак скольжения (т.н. "слайд-атаки"). Однако из-за наличия большой величины самоподобия в шифре, это позволяет проводить атаки инверсии ключей на комбинации неподвижных точек и свойства "отражения" (т.н. "рефлективные атаки") для определённых слабых ключей. Сложность этой атаки 2^192 и 2^32 подобранных открытых текстов.

    Читайте также:  Что значит режим не беспокоить на андроид

    Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.

    Множество новых атак на основе самоподобия работают против всех ключей ГОСТа и позволяют взламывать полнораундовый ГОСТ с 256-битным ключом, а не только для слабых ключей, как было ранее. Все эти атаки требуют значительно меньше памяти и они значительно быстрее.

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

    Алгебраический криптоанализ и атаки с небольшой сложностью данных на шифры с уменьшенным числом раундов

    Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.

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

    Как взломать ГОСТ?

    Алгебраическая атака на полнораундовый ГОСТ более подробно представлена в рассматриваемой публикации. В предыдущей работе автор уже изложил 20 алгебраических атак на ГОСТ и ожидает большого их числа в ближайшем будущем. Атака, предложенная в данной работе — не лучшая из них, но открывает простой (по крайней мере для понимания криптографами) путь для последующих разработок для создания специфичной методологии к взлому ГОСТа.

    Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан".

    ГОСТ спроектирован на обеспечение военного уровня безопасности на 200 лет вперёд. Большинство ведущих экспертов, изучавших ГОСТ, приходили к соглашению о том, что "несмотря на значительные криптоаналитические усилия на протяжении 20 лет, ГОСТ всё ещё не взломан". В 2010 году ГОСТ продвигают в ISO 18033 в качестве мирового стандарта шифрования.

    Основа идей об алгебраическом криптоанализе возникла более 60 лет назад. Но только лишь за последние 10 лет были разработаны эффективные программные средства (частичного) решения множества NP-полных проблем. Было взломано некоторое число потоковых шифров. Только один блочный шифр был взломан этим методом — сам по себе слабый KeeLoq. В этой работе автор взламывает важный, реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.

    Простая атака "MITM с отражением" на ГОСТ уже представлена на конференции FSE 2011. В работе же, рассматриваемой в данной статье, представлена другая атака лишь для иллюстрации факта того, как много атак на ГОСТ уже появилось сейчас, многие из которых быстрее, а сама алгебраическая атака требует намного меньше памяти и открывает практически неисчерпаемое пространство возможностей для противника, атакующего шифр разными способами. Также в данной работе показано отсутствие необходимости использования свойства отражения для взлома.

    Автор утверждает: очевидно, что ГОСТ имеет серьёзные изъяны и теперь не обеспечивает уровня стойкости, требуемого ISO. Множество атак на ГОСТ представлено в рамках подтверждения парадигмы редуцирования алгебраической сложности.

    Напоследок исследователь особенно отмечает некоторые факты, которые пока недоступны читателю, но известны исследователю, являющиеся важными в ходе процесса стандартизации ISO. Данная атака — не просто "сертификационная" атака на ГОСТ, которая быстрее перебора грубой силой. Фактически, стандартизация ГОСТа сейчас была бы крайне опасной и безответственной. Это так потому, что некоторые из атак возможны к осуществлению на практике. Некоторые ключи ГОСТа на практике даже могут быть дешифрованы, будь они слабые ключи или ключи из частных реальных применений ГОСТа. В предыдущей работе автор приводит детальное рассмотрение случаев возможности практических атак. Важно также то, что "это первый случай в истории, когда серьёзный стандартизированный блочный шифр, созданный для защиты секретов военного уровня и предназначенный для защиты документов государственной тайны для правительств, крупных банков и других организаций, оказался взломан математической атакой".

    Подписывайтесь на каналы "SecurityLab" в Telegram и Яндекс.Дзен, чтобы первыми узнавать о новостях и эксклюзивных материалах по информационной безопасности.

    Комментировать
    0 просмотров
    Комментариев нет, будьте первым кто его оставит

    Это интересно
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    Adblock detector