Информационная безопасность и защита информации


Информационная безопасность и защита информации
1-билет
Генерация последовательностей ПСЧ. Параметры генератора.
ГПСЧ не являются истинно случайными, поскольку генерируют последовательность чисел по некоторому алгоритму. Основные характеристики алгоритма псевдослучайной генерации: начальное значение и период. Начальное значение требуется по той причине, что обычно следующие числа зависят от предыдущих (рекуррентные соотношения). Вспомните: в любом адекватном рекуррентном соотношении есть некое граничное условие, например, если факториал представлять как n! = n * (n-1)!, то 0! = 1 - граничное условие. Другое пример - числа Фибоначчи: f(0) = f(1) = 1 - граничное условие, f(n) = f(n - 1) + f(n - 2) - рекуррентное соотношение. Каждый запросто может придумать другие - самопальные - рекуррентные соотношения... Период - наименьшее T такое, что гарантированно X(i) = X(i + T), где i - целое неотрицательное (ведём нумерацию элементов последовательности с нуля), X(i) - i-ый член последовательности. Иначе говоря, псевдослучайная последовательность представляет собой серию повторяющихся групп из T чисел. Например, {2, 3, 0, 1, 2, 3, 0, 1, 2, ...} - здесь период T = 4, начальное значение X(0) = 2. Зная алгоритм ГПСЧ и начальное значение, легко восстановить любое число X(i). А теперь сформулируем требования, по которым в криптографии создаются ГПСЧ:1. Псевдослучайная последовательность, выдаваемая ГПСЧ, должна иметь как можно больший период. Чем секретнее данные, тем больший период желательно иметь. 2. Зная любой фрагмент последовательности, выдаваемой генератором, злоумышленник не должен иметь эффективной возможности найти начальное значение, загруженное в генератор. 3. Зная любой фрагмент последовательности, выдаваемой генератором, злоумышленник не должен иметь возможности получить достоверную информацию о предыдущих или последующих элементах последовательности. 4. Ну и, разумеется, хотелось бы повыше скорость работы генератора. К сожалению, это несколько противоречит тому, что требуется как можно более высокая защищённость. Требования 2 и 3 можно считать требованиями непредсказуемости.
Существуют истинно случайные генераторы. Примером такого может быть, например, игральный куб без смещённого центра тяжести и прочих жульнических штучек. Но в криптографии принято использовать ГПСЧ, поэтому их касаться не будем.
DES стандарт. Режим электронной кодовой книги.
Стандарт шифрования данных (DES) — блочный шифр с симметричными ключами, разработан Национальным Институтом Стандартов и Технологии (NIST – National Institute of Standards and Technology).
DES (Data Encryption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:
 режим электронной кодовой книги (ECB — Electronic Code Book),
 режим сцепления блоков (СВС — Cipher Block Chaining),
 режим обратной связи по шифротексту (CFB — Cipher Feed Back),
 режим обратной связи по выходу (OFB — Output Feed Back).

3.DES стандарт. Режим с зацеплением блоков.
Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок Ci i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста Mi + 1. Вектор C0 — начальный вектор, он меняется ежедневно и хранится в секрете.

2-билет
Традиционные методы шифрования. Шифры перестановки
Шифры перестановки. При шифровании перестановкой символы шифруемого текста переставляются по определенному правилу в пределах блока этого текста. Шифры перестановки являются самыми простыми и, вероятно, самыми древними шифрами.
Простая перестановка без ключа (с ключом рассматривается здесь) — один из самых простых методов шифрования.
Делают так:
Сообщение записывается в таблицу по столбцам.
После того, как открытый текст записан колонками, для образования шифровки он считывается по строкам. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы.
например, зашифруем фразу "ВРАГ БУДЕТ РАЗБИТ",разместим текст в "таблице" - по три столбца (и не будем вообще использовать пробелы)-запишем текст столбцами:
?1
2
3
4
5 В   Г   Д   Р   Б
 
Р   Б   Е   А   И
 
А   У   Т   З   Т
при считывании по строкам получим шифровку (разделяю на группы по 4-ре только для визуального удобства - можно вообще не разделять):
?1 ВГДР БРБЕ АИАУ ТЗТ
То есть мы получаем перестановку (как результат действия подстановки) исходного множества букв (потому так и называется) таким образом:
?1
2 ВРАГ  БУДЕ  ТРАЗ  БИТ
ВГДР  БРБЕ  АИАУ  ТЗТ
Фактически - чтобы сразу расшифровать такую строку:
?1 ВРАГ  БУДЕ  ТРАЗ  БИТ
достаточно знать число столбцов в исходной таблице,то есть число столбцов и будет являться ключом данной криптосистемы.
Но, как вы поняли на компьютере такая защита весьма просто ломается путём подбора числа столбцов (проверка - получение связного текста)
AES стандарт. RIJNDAEL. Структура.
Алгоритм шифрования, действующий в качестве государственного стандарта в области шифрования данных в США с 2001 года. В основу стандарта положен шифр Rijndael. Шифр Rijndael/AES (то есть рекомендуемый стандартом) характеризуется размером блока 128 бит, длиной ключа 128, 192 или 256 бит и количеством раундов 10, 12 или 14 в зависимости от длины ключа. Основу Rijndael составляют так называемые линейно-подстановочные преобразования. В алгоритме широко используются табличные вычисления, причем все необходимые таблицы задаются константно, т.е. не зависят ни от ключа, ни от данных.
Данный алгоритм разработан двумя специалистами по криптографии из Бельгии. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.
Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах. В структуре алгоритма заложена возможность параллельного исполнения некоторых операций, что на многопроцессорных рабочих станциях может еще поднять скорость шифрования в 4 раза.
Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции :
ByteSub – табличная подстановка 8х8 бит (рис.6),
Рис.6.
ShiftRow – сдвиг строк в двумерном массиве на различные смещения (рис.7),
Рис.7.
MixColumn – математическое преобразование, перемешивающее данные внутри столбца (рис.8),
Рис.8.
AddRoundKey – добавление материала ключа операцией XOR (рис.9).
Рис.9.
В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.
ГОСТ 28147-89. Режим простой замены.
2.1. Зашифрование открытых данных в режиме простой замены
2.1.1. Криптосхема, реализующая алгоритм зашифрования в режиме простой замены, должна иметь вид, указанный на черт.2.
Черт.2. Криптосхема, реализующая алгоритм зашифрования в режиме простой замены

Черт.2
Открытые данные, подлежащие зашифрованию, разбивают на блоки по 64 бита в каждом. Ввод любого блока = ((0), (0). …, (0), (0), (0), (0) …, (0)) двоичной информации в накопители и производится так, что значение (0) вводится в 1-й разряд , значение (0) вводится во 2-й разряд и т.д., значение (0) вводится в 32-й разряд ; значение (0) вводится в 1-й разряд , значение (0) вводится во 2-й разряд и т.д., значение (0) вводится в 32-й разряд . В результате получают состояние ( (0), (0), …, (0), (0)) накопителя и состояние ( (0), (0),
..., (0)) накопителя .
2.1.2. В КЗУ вводятся 256 бит ключа. Содержимое восьми 32-разрядных накопителей , ... , имеет вид:



2.1.3. Алгоритм зашифрования 64-разрядного блока открытых данных в режиме простой замены состоит из 32 циклов.В первом цикле начальное заполнение накопителя суммируется по модулю 2 в сумматоре с заполнением накопителя , при этом заполнение накопителя сохраняется.Результат суммирования преобразуется в блоке подстановки и полученный вектор поступает на вход регистра , где циклически сдвигается на одиннадцать шагов в сторону старших разрядов. Результат сдвига суммируется поразрядно по модулю 2 в сумматоре с 32-разрядным заполнением накопителя . Полученный в результат записывается в , при этом старое заполнение переписывается в . Первый цикл заканчивается.Последующие циклы осуществляются аналогично, при этом во 2-м цикле из КЗУ считывается заполнение в 3-м цикле из КЗУ считывается заполнение и т.д., в 8-м цикле из КЗУ считывается заполнение . В циклах с 9-го по 16-й, а также в циклах с 17-го по 24-й заполнения из КЗУ считываются в том же порядке:
, , , , , , , .
В последних восьми циклах с 25-го по 32-й порядок считывания заполнений КЗУ обратный:
, , , , , , , .
Таким образом, при зашифровании в 32 циклах осуществляется следующий порядок выбора заполнений накопителей:
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , .
В 32 цикле результат из сумматора вводится в накопитель , а в накопителе сохраняется старое заполнение.Полученные после 32-го цикла зашифрования заполнения накопителей и являются блоком зашифрованных данных, соответствующим блоку открытых данных.
2.1.4. Уравнения зашифрования в режиме простой замены имеют вид:

при = 124;

при =25 31;


при = 32,где (0) = ((0), (0), …, (0)) - начальное заполнение перед первым циклом зашифрования;(0) = ((0), (0), …, (0)) - начальное заполнение перед первым циклом зашифрования;= (, , …, ) - заполнение после -го цикла зашифрования;= (, , …, ) - заполнение после -го цикла зашифрования, = 132.Знак означает поразрядное суммирование 32-разрядных векторов по модулю 2.Знак означает суммирование 32-разрядных векторов по модулю 2. Правила суммирования по модулю 2 приведены в приложении 4;- операция циклического сдвига на одиннадцать шагов в сторону старших разрядов, т.е.

.
2.1.5. 64-разрядный блок зашифрованных данных выводится из накопителей , в следующем порядке: из 1-го, 2-го, ... , 32-го разрядов накопителя затем из 1-го, 2-го, ... , 32-го разрядов накопителя , т.е.
.
Остальные блоки открытых данных в режиме простой замены зашифровываются аналогично.
2.2. Расшифрование зашифрованных данных в режиме простой замены
2.2.1. Криптосхема, реализующая алгоритм расшифрования в режиме простой замены, имеет тот же вид (см. черт.2), что и при зашифровании. В КЗУ вводятся 256 бит того же ключа, на котором осуществлялось зашифрование. Зашифрованные данные, подлежащие расшифрованию, разбиты на блоки по 64 бита в каждом. Ввод любого блока

в накопители и производятся так, что значение (32) вводится в 1-й разряд , значение а(32) вводится во 2-й разряд и т.д., значение (32) вводится в 32-й разряд ; значение (32) вводится в 1-й разряд и т.д., значение (32) вводится в 32-й раз
ряд .
2.2.2. Расшифрование осуществляется по тому же алгоритму, что и зашифрование открытых данных, с тем изменением, что заполнения накопителей , , ... , считываются из КЗУ в циклах расшифрования в следующем порядке:
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , .
2.2.3. Уравнения расшифрования имеют вид:

при = 18;

при = 931;


при = 32.
2.2.4. Полученные после 32 циклов работы заполнения накопителей и составляют блок открытых данных., , …, , , , …, ), соответствующий блоку зашифрованных данных, при этом значение блока соответствует содержимому 1-го разряда , значение соответствует содержимому 2-го разряда и т.д., значение соответствует содержимому 32-го разряда ; значение соответствует содержимому 1-го разряда , значение соответствует содержимому 2-го разряда и т.д., значение соответствует содержимому 32-го разряда .Аналогично расшифровываются остальные блоки зашифр
ованных данных.
2.3. Алгоритм зашифрования в режиме простой замены 64-битового блока обозначается через , т.е.
, , .
2.4. Режим простой замены допускается использовать для зашифрования (расшифрования) данных только в случаях, приведенных в п.1.7.
3-билет
ГОСТ 28147-89. Режим гаммирования с обратной связью.
РЕЖИМ ГАММИРОВАНИЯ С ОБРАТНОЙ СВЯЗЬЮ
4.1. Зашифрование открытых данных в режиме гаммирования с обратной связью
4.1.1. Крипстосхема, реализующая алгоритм зашифрования в режиме гаммирования с обратной связью, имеет вид, указанный на черт.4.
Черт.4. Крипстосхема, реализующая алгоритм зашифрования в режиме гаммирования с обратной связью

Черт.4
Открытые данные, разбитые на 64-разрядные блоки , ..., , зашифровываются в режиме гаммирования с обратной связью путем поразрядного суммирования по модулю 2 в сумматоре с гаммой шифра , которая вырабатывается блоками по 64 бита, т.е. = (, , ... , ), где определяется объемом открытых данных, - -й 64-разрядный блок, = 1. Число двоичных разрядов в блоке может быть м
еньше 64.
4.1.2. В КЗУ вводятся 256 бит ключа. Синхропосылка из 64 бит вводится в и аналогично п.3.1.2.
4.1.3. Исходное заполнение и зашифровывается в режиме простой замены в соответствии с требованиями п.2.1. Полученное в результате зашифрования заполнение и образует первый 64-разрядный блок гаммы шифра = , который суммируется поразрядно по модулю 2 в сумматоре с первым 64-разрядным блоком открытых данных = ().В результате получается 64-разрядный блок зашифрованных данных
.
4.1.4. Блок зашифрованных данных одновременно является также исходным состоянием , для выработки второго блока гаммы шифра и по обратной связи записывается в указанные накопители. При этом значение вводится в 1-й раздел N 1, значение вводится во 2-й разряд N 1 и т.д., значение вводится в 32-й разряд N 1; значение вводится в 1-й разряд N 2, значение вводится во 2-й разряд N 2 и т.д., значение вводится в 32-й разряд N 2.Заполнение , зашифровывается в режиме простой замены в соответствии с требованиями п.2.1. Полученное в результате зашифрования заполнение , образует второй 64-разрядный блок гаммы шифра , который суммируется поразрядно по модулю 2 в сумматоре со вторым блоком открытых данных .Выработка последующих блоков гаммы шифра и зашифрование соответствующих блоков открытых данных ( = 3) производится аналогично. Если длина последнего -го блока открытых данных меньше 64 разрядов, то из используется только соответствующее число разрядов гаммы шифра, остальные разр
яды отбрасываются.
4.1.5. Уравнения зашифрования в режиме гаммирования с обратной связью имеют вид:

4.1.6. В канал связи или память ЭВМ передаются синхропосылка и блоки зашифрованных данных , , ... , .
4.2. Расшифрование зашифрованных данных в режиме гаммирования с обратной связью
4.2.1. При расшифровании криптосхема имеет тот же вид (см. черт.4), что и при зашифровании.В КЗУ вводятся 256 бит того же ключа, на котором осуществлялось зашифрование , , ... , . Синхропосылка вводится в и аналогично п.3.1.2.
4.2.2. Исходное заполнение , (синхропосылка ) зашифровывается в режиме простой замены согласно подразделу 2.1. Полученное в результате зашифрования заполнение , образует первый блок гаммы шифра , который суммируется поразрядно по модулю 2 в сумматоре с блоком зашифрованных данных . В результате получается первый блок открытых данных
.
4.2.3. Блок зашифрованных данных является исходным заполнением , для выработки второго блока гаммы шифра . Блок записывается в , в соответствии с требованиями п.4.1.4. Полученное заполнение , зашифровывается в режиме простой замены в соответствии с требованиями п.2.1, полученный в результате блок суммируется поразрядно по модулю 2 в сумматоре со вторым блоком зашифрованных данных . В результате получается блок открытых данных .Аналогично в , последовательно записываются блоки зашифрованных данных , , …, , из которых в режиме простой замены вырабатываются блоки гаммы шифра , , …, . Блоки гаммы шифра суммируются поразрядно по модулю 2 в сумматоре с блоками зашифрованных данных , , …, , в результате получаются блоки открытых данных , ... , , при этом длина последнего блока открытых данных может содерж
ать меньше 64 разрядов.
4.2.4. Уравнения расшифрования в режиме гаммирования с обратной связью имеют вид:

Концепция криптосистем с открытым ключом.
Концепция криптосистемы с открытым ключом
Эффективными системами криптографической защиты данных являются асимметричные криптосистемы, называемые также криптосистемами с открытым ключом. В таких системах для зашифрования данных используется один ключ, а для расшифрования - другой ключ (отсюда и название - асимметричные). Первый ключ является открытым и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифрование данных с помощью открытого ключа невозможно.
Для расшифрования данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифрования не может быть определен из ключа зашифрования.
Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рис.1. В этой криптосистеме применяют два различных ключа: КА - открытый ключ отправителя A; КВ -секретный ключ получателя В. Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ КА по незащищенному каналу). Значения ключей КА и КВ зависят от начального состояния генератора ключей.
Раскрытие секретного ключа КВ по известному открытому ключу КА должно быть вычислительно неразрешимой задачей.
Характерные особенности асимметричных криптосистем:
1. Открытый ключ КА и криптограмма С могут быть отправлены по незащищенным каналам, т.е. противнику известны КВ и С.
2. Алгоритмы шифрования и расшифрованияЕВ: М  С,
DВ: C  M,
являются открытыми.

Рис.1. Обобщенная схема асимметричной криптосистемы с открытым ключом
Защита информации в асимметричной криптосистеме основана на секретности ключа КВ.
У.Диффи и М.Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы:
1. Вычисление пары ключей (КА, КВ) получателем В на основе начального условия должно быть простым.
2. Отправитель А, зная открытый ключ КА и сообщение М, может легко вычислить криптограмму
(1)
3. Получатель В, используя секретный ключ КВ и криптограмму С, может легко восстановить исходное сообщение
(2)
4. Противник, зная открытый ключ КА, при попытке вычислить секретный ключ КВ наталкивается на непреодолимую вычислительную проблему.
5. Противник, зная пару (КВ, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.
Алгоритм RSA
Следующий пример наглядно демонстрирует алгоритм шифрования RSA:
Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа - это сократит наши расчеты.
Выберем p=3 and q=11.
Определим n= 3*11=33.
Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9; C2 = (1^7) mod 33 = 1 mod 33 = 1; C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С); M2=(1^3) mod 33 =1 mod 33 = 1(А); M3=(29^3) mod 33 = 24389 mod 33 = 2(В); Данные расшифрованы!
4-билет
Шифрование методом гаммирования.
Еще одним частным случаем многоалфавитной подстановки является гаммирование. В этом способе шифрование выполняется путем сложения символов исходного текста и ключа по модулю, равному числу букв в алфавите. Если в исходном алфавите, например, 33 символа, то сложение производится по модулю 33. Такой процесс сложения исходного текста и ключа называется в криптографии наложением гаммы.
Пусть символам исходного алфавита соответствуют числа от 0 (А) до 32 (Я). Если обозначить число, соответствующее исходному символу, x, а символу ключа – k, то можно записать правило гаммирования следующим образом:
z = x + k (mod N),
где z – закодированный символ, N - количество символов в алфавите, а сложение по модулю N - операция, аналогичная обычному сложению, с тем отличием, что если обычное суммирование дает результат, больший или равный N, то значением суммы считается остаток от деления его на N. Например, пусть сложим по модулю 33 символы Г (3) и Ю (31):
3 + 31 (mod 33) = 1,
то есть в результате получаем символ Б, соответствующий числу 1.
Наиболее часто на практике встречается двоичное гаммирование. При этом используется двоичный алфавит, а сложение производится по модулю два. Операция сложения по модулю 2 часто обозначается , то есть можно записать:

Операция сложения по модулю два в алгебре логики называется также "исключающее ИЛИ" или по-английски XOR.
Рассмотрим пример. Предположим, нам необходимо зашифровать десятичное число 14 методом гаммирования с использованием ключа 12. Для этого вначале необходимо преобразовать исходное число и ключ (гамму) в двоичную форму: 14(10)=1110(2), 12(10)=1100(2). Затем надо записать полученные двоичные числа друг под другом и каждую пару символов сложить по модулю два. При сложении двух двоичных знаков получается 0, если исходные двоичные цифры одинаковы, и 1, если цифры разные:

Сложим по модулю два двоичные числа 1110 и 1100:
Исходное число 1 1 1 0
Гамма 1 1 0 0
Результат 0 0 1 0
В результате сложения получили двоичное число 0010. Если перевести его в десятичную форму, получим 2. Таким образом, в результате применения к числу 14 операции гаммирования с ключом 12 получаем в результате число 2.
Каким же образом выполняется расшифрование? Зашифрованное число 2 представляется в двоичном виде и снова производится сложение по модулю 2 с ключом:
Зашифрованное число 0 0 1 0
Гамма 1 1 0 0
Результат 1 1 1 0
Переведем полученное двоичное значение 1110 в десятичный вид и получим 14, то есть исходное число.
Таким образом, при гаммировании по модулю 2 нужно использовать одну и ту же операцию как для зашифрования, так и для расшифрования. Это позволяет использовать один и тот же алгоритм, а соответственно и одну и ту же программу при программной реализации, как для шифрования, так и для расшифрования.
Операция сложения по модулю два очень быстро выполняется на компьютере (в отличие от многих других арифметических операций), поэтому наложение гаммы даже на очень большой открытый текст выполняется практически мгновенно.
Благодаря указанным достоинствам метод гаммирования широко применяется в современных технических системах сам по себе, а также как элемент комбинированных алгоритмов шифрования.
Сформулируем, как производится гаммирование по модулю 2 в общем случае:
символы исходного текста и гамма представляются в двоичном коде и располагаются один под другим, при этом ключ (гамма) записывается столько раз, сколько потребуется;
каждая пара двоичных знаков складывается по модулю два;
полученная последовательность двоичных знаков кодируется символами алфавита в соответствии с выбранным кодом.
На рис. 2.6 показано, как применяется гаммирование к тексту с русскими символами. Символы кодируются в соответствии с принятой кодировкой, а затем производится сложение по модулю 2.
При использовании метода гаммирования ключом является последовательность, с которой производится сложение – гамма. Если гамма короче, чем сообщение, предназначенное для зашифрования, гамма повторяется требуемое число раз. Так в примере на рис. 2.6 длина исходного сообщения равна двенадцати байтам, а длина ключа – пяти байтам. Следовательно, для зашифрования гамма должна быть повторена 2 раза полностью и еще один раз частично.

Рис. 2.6. Механизм гаммированияЧем длиннее ключ, тем надежнее шифрование методом гаммирования. Связь длины ключа с вероятностью вскрытия сообщения, а также некоторые принципы дешифрования сообщений, закрытых методом гаммирования, обсуждаются в "Поточные шифры и генераторы псевдослучайных чисел. Часть 2" и "Шифрование, помехоустойчивое кодирование и сжатие информации" . На практике длина ключа ограничена возможностями аппаратуры обмена данными и вычислительной техники, а именно выделяемыми объемами памяти под ключ, временем обработки сообщения, а также возможностями аппаратуры подготовки и записи последовательностей ключей. Кроме того, для использования ключа вначале необходимо каким-либо надежным способом доставить его обеим сторонам, обменивающимся сообщениями. Это приводит к возникновению проблемы распределения ключей, сложность решения которой возрастает с увеличением длины ключа и количества абонентов в сети передачи сообщений.
DES стандарт. Режим с обратной связью по шифртексту.
Режим обратной связи по шифротексту (CFB — Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z0,Z1,...Zi = DESk(Ci - 1)

. Начальный вектор C0 сохраняется в секрете.

Расширенный алгоритм Евклида.
2.2.3. Расширенный алгоритм Евклида
Для различных приложений очень важно уметь представлять наибольший общий делитель целых чисел а и b в виде (теорема 2.2.3). Очевидно, один из способов состоит в применении алгоритма Евклида и затем «обратного» прохода. Например, для получаем

откуда следует, что 18 — наибольший общий делитель чисел 612 и 342. Проведя вычисления в обратном порядке, получим

т.е. и мы решили нашу задачу.
Другой подход к решению этой задачи, имеющий, как мы убедимся в дальнейшем, много приложений, состоит в применении расширенного алгоритма Евклида. Значения вычисляются в серии шагов, в каждом из которых мы выражаем а, - (вычисленное в процессе работы алгоритма Евклида, разд. 2.2.2) в форме
А именно рассмотрим последовательность

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

Конечно, мы мажем также вычислить как но приведенное выше выражение подчеркивает, что вычислено таким же способом, как Мы получили следующий алгоритм.
ХБА. Расширенный алгоритм Евклида (Extended Euclidean Algorithm)
Вход:
Выход: такие, что
1. [Инициализация]
2. [Основной цикл] Пока выполнять
3. [Выход] Вернуть
Анализ времени работы аналогичен проведенному для ЕА, детали мы оставляем читателю. Применяя расширенный алгоритм Евклида в нашем примере получим:

Заметим, что равенство выполняется на каждом шаге. Алгоритм выдает проверим ответ:
5-билет
Китайская теорема об остатках.
Китайская теорема об остатках (CRT — Chinese Reminder Theorem) используется, чтобы решить множество уравнений с одной переменной, но различными взаимно простыми модулями, как это показано ниже:

Китайская теорема об остатках утверждает, что вышеупомянутые уравнения имеют единственное решение, если модули являются взаимно простыми.
Пример 12.35
Следующий пример содержит систему уравнений с различными модулями:

Для этой системы уравнений x = 23. Это значение удовлетворяет все уравнения: , , .
Решение
Решение системы уравнений выполняется в следующем порядке:
Найти . Это общий модуль.
Найти M1 = M/m1, M2 = M/m2,…., Mk = M/mk.
Используя соответствующие модули m1, m2,…., mk, найти мультипликативную инверсию M1, M2,…, Mk. Обозначим ее M1-1, M2-1,…, Mk-1.
Решение системы уравнений

Обратите внимание, что система уравнений может иметь решение, даже если модули не взаимно простые. Однако в криптографии мы интересуемся только решением уравнений с взаимно простыми модулями.
Пример 12.36
Найдите решение системы уравнений

Из предыдущего примера мы уже знаем, что ответ x = 23. Определим его в четыре шага.
Решение

M1 = 105/3 = 35, M2 = 105/5 =21, M3 = 105/7 = 15
Инверсии M1-1 = 2, M2-1 = 1, M3-1 = 1

Пример 12.37
Найти целое, которое дает в остатке 3, если его разделить на 7 и 13, но без остатка делится на 12.
Решение
Это проблема китайской теоремы об остатке. Мы можем составить три уравнения и найти значение x.

Если проведем четыре шага, мы найдем x = 276. Можем проверить, что 276 = 3 mod 7, 276 = 3 mod 13 и 276 делится на 12 (частное 23 и остаток 0).
Приложения
Китайская теорема об остатках часто применяется в криптографии. Одно из таких применений – решение квадратных уравнений — будет обсуждаться в следующей секции. Другое приложение — представление очень большого числа в виде списка малых целых чисел.
Пример 12.38
Предположим, нам надо вычислить z = x + y, где x = 123 и y = 334, но система принимает только числа меньше 100. Эти числа можно представить следующими уравнениями:

Сложим каждое уравнение x с соответствующим уравнением y:

Теперь эти три уравнения могут быть решены, используя китайскую теорему об остатках, чтобы найти z. Один из приемлемых ответов равен z = 457.
Квадратичные вычеты.
В уравнении . a называется квадратичным вычетом (QR), если уравнение имеет два решения; a называется квадратичным невычетом (QNR), если уравнение не имеет решений. Может быть доказано, что в ZP* с p – 1 элементами (p – 1)/2 элементов — квадратичные вычеты и (p – 1)/2 являются квадратичными невычетами.
Пример 13.3
Есть 10 элементов в Z11*. Пять из них – квадратичные вычеты, и пять — невычеты. Другими словами, Z11* может быть разделен на два отдельных множества, QR и QNR, как это показано на рис. 13.1.

Вычисления в конечных полях.
2.6.1 Вычисления в конечных полях
В конечных полях, как обычно, можно складывать, вычитать, умножать и делить.
Задача 2.65. Решить следующую систему уравнений над :

(Следует воспользоваться таблицей соответствия из задачи 2.59.)
Решение. Используем метод подстановки. Из первого уравнения находим подставляя его во второе уравнение, получаем

Для решения указанной выше системы уравнений можно воспользоваться также методом Крамера:

Утверждение 2.66. Пусть — произвольный ненулевой элемент поля Если существует такой элемент что то а называется квадратичным вычетом.
В противном случае, т. е. если в не существует такого элемента что называется квадратичным невычетом.
1) Если то любой элемент поля, за исключением элемента 0, является квадратичным вычетом.
2) Если нечетное число, то четные степени примитивного элемента являются квадратичными вычетами, а нечетные степени — квадратичными невычетами (следовательно, имеется квадратичных вычетов и столько же квадратичных невычетов).
6-билет
Традиционные методы шифрования. Шифры замены
Шифры простой замены. При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита по одному правилу на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.
DES стандарт. Режимы с обратной связью по выходу.
Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z0,Z1,...

, i>=1

ГОСТ 28147-89. Режим гаммирования.
При работе ГОСТ 28147-89 в режиме гаммирования описанным ниже образом формируется криптографическая гамма, которая затем побитно складывается по модулю 2 с исходным открытым текстом для получения шифротекста. Шифрование в режиме гаммирования лишено недостатков, присущих режиму простой замены[2]. Так, даже идентичные блоки исходного текста дают разный шифротекст, а для текстов с длиной, не кратной 64 бит, "лишние" биты гаммы отбрасываются. Кроме того, гамма может быть выработана заранее, что соответствует работе шифра в поточном режиме.
Выработка гаммы происходит на основе ключа и так называемой синхропосылки, которая задает начальное состояние генератора. Алгоритм выработки следующий:
Синхропосылка шифруется с использованием описанного алгоритма простой замены, полученные значения записываются во вспомогательные 32-разрядные регистры N3 и N4 - младшие и старшие биты соответственно.
N3 суммируется по модулю 232 с константой C2 = 101010116
N4 суммируется по модулю 232-1 с константой C1 = 101010416
N3 и N4 переписываются соответственно в N1 и N2, которые затем шифруются с использованием алгоритма простой замены. Полученный результат является 64 битами гаммы.
Шаги 2-4 повторяются в соответствии с длиной шифруемого текста.
Для расшифровывания необходимо выработать такую же гамму, после чего побитно сложить её по модулю 2 с зашифрованным текстом. Очевидно, для этого нужно использовать ту же синхропосылку, что и при шифровании. При этом, исходя из требований уникальности гаммы, нельзя использовать одну синхропосылку для шифрования нескольких массивов данных. Как правило, синхропосылка тем или иным образом передается вместе с шифротекстом.
Особенность работы ГОСТ 28147-89 в режиме гаммирования заключается в том, что при изменении одного бита шифротекста изменяется только один бит расшифрованного текста. С одной стороны, это может оказывать положительное влияние на помехозащищённость; с другой - злоумышленник может внести некоторые изменения в текст, даже не расшифровывая его

7-билет
ГОСТ 28147-89. Режим выработки имитовставки.
Этот режим не является в общепринятом смысле режимом шифрования. При работе в режиме выработки имитовставки создаётся некоторый дополнительный блок, зависящий от всего текста и ключевых данных. Данный блок используется для проверки того, что в шифротекст случайно или преднамеренно не были внесены искажения. Это особенно важно для шифрования в режиме гаммирования, где злоумышленник может изменить конкретные биты, даже не зная ключа; однако и при работе в других режимах вероятные искажения нельзя обнаружить, если в передаваемых данных нет избыточной информации.
Имитовставка вырабатывается для M ≥ 2 блоков открытого текста по 64 бит. Алгоритм следующий:
Блок открытых данных записывается в регистры N1 и N2, после чего подвергается преобразованию, соответствующему первым 16 циклам шифрования в режиме простой замены
К полученному результату побитно по модулю 2 прибавляется следующий блок открытых данных. Последний блок при необходимости дополняется нулями. Сумма также шифруется в соответствии с пунктом 1.
После добавления и шифрования последнего блока из результата выбирается имитовставка длиной L бит: с бита номер 32-L до 32 (отсчёт начинается с 1). Стандарт рекомендует выбирать L исходя из того, что вероятность навязывания ложных данных равна 2-L. Имитовставка передается по каналу связи после зашифрованных блоков.
Для проверки принимающая сторона после расшифровывания текста проводит аналогичную описанной процедуру. В случае несовпадения результата с переданной имитовставкой все соответствующие M блоков считаются ложными.
Следует отметить, что выработка имитовставки может проводиться параллельно шифрованию с использованием одного из описанных выше режимов работы

Алгоритм Диффи-ХеллманаПредположим, что обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = gamod p и пересылает его второму, а второй вычисляет B = gbmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение Bamod p = gabmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Abmod p = gabmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = gabmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления gabmod p по перехваченным gamod p и gbmod p, если числа p,a,b выбраны достаточно большими.

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ
При работе алгоритма, каждая сторона:
генерирует случайное натуральное число a — закрытый ключ
совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где
p является случайным простым числом
g является первообразным корнем по модулю p
вычисляет открытый ключ A, используя преобразование над закрытым ключом
A = ga mod p
обменивается открытыми ключами с удалённой стороной
вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a
K = Ba mod p
К получается равным с обоих сторон, потому что:
Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p
В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.
Схема шифрования Эль Гамаля.
Асимметричный алгоритм, предложенный в 1985 году Эль-Гамалем (T. ElGamal), универсален. Он может быть использован для решения всех трех основных задач: для шифрования данных, для формирования цифровой подписи и для согласования общего ключа. Кроме того, возможны модификации алгоритма для схем проверки пароля, доказательства идентичности сообщения и другие варианты. Безопасность этого алгоритма, так же как и алгоритма Диффи-Хеллмана, основана на трудности вычисления дискретных логарифмов. Этот алгоритм фактически использует схему Диффи-Хеллмана, чтобы сформировать общий секретный ключ для абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ.
И в случае шифрования, и в случае формирования цифровой подписи каждому пользователю необходимо сгенерировать пару ключей. Для этого, так же как и в схеме Диффи-Хеллмана, выбираются некоторое большое простое число Р и число А, такие, что различные степени А представляют собой различные числа по модулю Р. Числа Р и А могут передаваться в открытом виде и быть общими для всех абонентов сети.
Затем каждый абонент группы выбирает свое секретное число Хi, 1 < Хi < Р-1, и вычисляет соответствующее ему открытое число . Таким образом, каждый пользователь может сгенерировать закрытый ключ Хi и открытый ключ Yi.
Информация о необходимых параметрах системы сведена в следующую таблицу.
Общие параметры Открытый ключ Закрытый ключ
Пользователь 1 Р, А Y1 Х1
… … …
Пользователь i YiХi
Шифрование
Теперь рассмотрим, каким образом производится шифрование данных. Сообщение, предназначенное для шифрования, должно быть представлено в виде одного числа или набора чисел, каждое из которых меньше Р. Пусть пользователь 1 хочет передать пользователю 2 сообщение m. В этом случае последовательность действий следующая.
Первый пользователь выбирает случайное число k, взаимно простое с Р-1, и вычисляет числа

где Y2 – открытый ключ пользователя 2. Число k держится в секрете.
Пара чисел (r, е), являющаяся шифротекстом, передается второму пользователю.
Второй пользователь, получив (r,e), для расшифрования сообщения вычисляет

где Х2 – закрытый ключ пользователя 2. В результате он получает исходное сообщение m.
Если злоумышленник узнает или перехватит Р, А, Y2, r, e, то он не сможет по ним раскрыть m. Это связано с тем, что противник не знает параметр k, выбранный первым пользователем для шифрования сообщения m. Вычислить каким-либо образом число k практически невозможно, так как это задача дискретного логарифмирования. Следовательно, злоумышленник не может вычислить и значение m, так как m было умножено на неизвестное ему число. Противник также не может воспроизвести действия законного получателя сообщения (второго абонента), так как ему не известен закрытый ключ Х2 (вычисление Х2 на основании Y2 — также задача дискретного логарифмирования).
По аналогичному алгоритму может производиться и согласование ключа, используемого для симметричного шифрования больших объемов данных. Более того, алгоритм Эль-Гамаля на практике целесообразно использовать именно для согласования общего ключа сессии, а не прямого шифрования больших сообщений. Это связано с тем, что в алгоритме используются операции возведения в степень и умножения по большому модулю. Так же как и в алгоритмах RSA и Диффи-Хеллмана, операции производятся над большими, состоящими из нескольких сотен или тысяч бит, числами. Поэтому шифрование больших сообщений производится крайне медленно.
8-билет
Безопасные хэш-функции. Функции хэширования.
Хэш-функция — это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m – исходные данные, h(m) – хэш от них. Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 не равно m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),
хэш-функции c ключом (MАC (Message Authentication Code) - коды).
Хэш-функции без ключа разделяются на два подкласса:
слабые хэш-функции,
сильные хэш-функции.
Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:
аргумент x может быть строкой бит произвольной длины;
значение H (x) должно быть строкой бит фиксированной длины;
значение H (x) легко вычислить;
для любого фиксированного x вычислительно невозможно найти другой x'!=x , такой что H(x')=H(x). Пара x'!=x , когда H(x')=H(x) называется коллизией хэш-функции.
Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1–3 для слабой хэш-функции и свойству 4': 4') вычислительно невозможно найти любую пару x'!=x, такой что H(x')=H(x).
Поскольку из свойств 1–2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4' говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.
Хэш-функцией с ключом (MAC) называется функция H(k,x), удовлетворяющая свойствам:
аргумент х функции H(k, x) может быть строкой бит произвольной длины;
значение H(k, x) должно быть строкой бит фиксированной длины;
при любых k и x легко вычислить H(k, x);
для любого х должно быть трудно вычислить H(k, x), не зная k;
должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k, x)} при выбранном наборе х или вычислить по этой информации H(k, x') для x'!=x.
Зачем нужна хэш-функция? Дело в том, что многие криптографические преобразования (в частности, вычисление и проверка электронной цифровой подписи, ЭЦП) выполняются над данными фиксированного размера. Поэтому перед просталением электронной подписи под многомегабайтным файлом обычно рассчитывают значение хэш-функции от него, а уже от этого значения считают ЭЦП. Кроме того, удобно, например, пароли в базе хранить не в открытом виде, а в хэшированном (так сделано во всех юниксах).
Некоторые алгоритмы хэш-функций:
MD 2. Message Digest. Алгоритм криптографической сверки. Порождает 128- bit блок от сообщения произвольной длины.
MD 4. Другой алгоритм свертки. Порождает 128-bit блок.
MD 5. Существенно переделанный MD 4. Автор тот же – Риверст.
SHA. Результирующий хэш равен 160-bit.
ГОСТ Р34.11–94. Российский алгоритм. Длина свертки – 256 бит (очень удобно для формирования по паролю ключа для ГОСТ 28147–89).
Алгоритм SHA.
SECURE HASH STANDARD (семейство криптографических функций SHA-1 и SHA-2)

Семейство криптографических функций SHA делят на два подмножества: непосредственно алгоритм SHA-1 (опубликован в 1995 году – FIPS PUB 180-1) и ряд алгоритмов под общим названием SHA-2 (опубликован в 2002 году – FIPS PUB 180-2, обновлен в 2008 году - FIPS PUB 180-3): SHA-224, SHA-256, SHA-384, SHA-512; в 2012 году в FIPS PUB 180-4 добавлены алгоритмы SHA-512/224 и SHA-512/256. Мы рассмотрим стандарт FIPS PUB 180-4, объединяющий все семейство хэш-функций SHA-1 и SHA-2.

Этот стандарт определяет следующие хэш-алгоритмы: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256, вычисляющие сжатое представление цифровых данных (сообщений). Если на вход хэш-алгоритма подать сообщение любой длины, но меньшее, чем 264 бит (для SHA-1, SHA-224 и SHA-256) или меньше, чем 2128 бита (для SHA-384, SHA-512, SHA-512/224 и SHA-512/256), то результатом будут данные, называемые дайджестом или хэш-значением сообщения. Размер хэш-значения сообщения лежит в диапазоне от 160 до 512 бит (или от 20 до 64 байт), зависит от выбранного алгоритма. SHA алгоритмы обычно используются совместно с другими криптографическими алгоритмами, например, с алгоритмами цифровой подписи или при хешировании с ключом для аутентификации сообщений (HMAC), или при создании случайных чисел (бит).
Хэш-алгоритмы, указанные в этом стандарте называются безопасными потому, что по заданному алгоритму невозможно вычислить следующее: 1) восстановить сообщение по конкретному дайджесту сообщения, или 2) найти два различных сообщения, у которых один и тот же дайджест сообщения (найти коллизию). Любые изменения в сообщении, с очень высокой вероятностью, приводят к различным хэш-значениям. Это свойство полезно при создании и проверке цифровых подписей, при аутентификации сообщений, при создании случайных чисел.
Каждый алгоритм состоит из двух этапов: предварительная обработка и вычисление хэша. Предварительная обработка включает в себя дополнение сообщения, разбиение дополненного сообщения на M-битные блоки, и установка инициализирующих значений, используемые при вычислении хэша. Вычисление хэша проходит итерационно, обрабатывая каждый M-битный блок дополненного сообщения, и использует функции, константы и операции над словами, чтобы получить хэш-значение. Результатом работы процедуры вычисление хэша является дайджест сообщения.
Алгоритмы различаются по размеру блоков и слов хэшируемых данных и хэш-значений – см. таблицу 1.
Алгоритм Размер сообщения (в битах) Размер блока (в битах) Размер слова (в битах) Размер дайджеста сообщения (в битах)
SHA-1 < 264 512 32 160
SHA-224 < 264 512 32 224
SHA-256 < 264 512 32 256
SHA-384 < 2128 1024 64 384
SHA-512 < 2128 1024 64 512
SHA-512/224 < 2128 1024 64 224
SHA-512/256 < 2128 1024 64 256
Функции
SHA-1SHA-224, SHA-256SHA-384, SHA-512, SHA-512/224, SHA-512/384SHA-1 использует последовательность нелинейных функций f0 , f1 ,…, f79. Каждая функция ft, где 0 ≤ t < 79, оперирует тремя 32-битными переменными: x, y, и z, в результате возвращая одно 32-битное слово. В алгоритме SHA-1 используется следующий набор нелинейных функций ft (x, y, z):00 ≤ t ≤ 19     Ch(x, y, z) = (x AND y) XOR ( NOT x AND z)20 ≤ t ≤ 39     Parity(x, y, z) = x XOR y XOR z40 ≤ t ≤ 59     Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)60 ≤ t ≤ 79     Parity(x, y, z) = x XOR y XOR z
Булева алгебра.Обратите внимание, что, например, функцию Ch может выразить по-другому:z XOR (x AND (y XOR z))Результат не изменится. В различных реализациях алгоритма такие варианты можно встретить.
Константы
SHA-1SHA-224, SHA-256SHA-384, SHA-512, SHA-512/224, SHA-512/384Константы Kt00 ≤ t ≤ 19     0x5a82799920 ≤ t ≤ 39     0x6ed9eba140 ≤ t ≤ 59     0x8f1bbcdc60 ≤ t ≤ 79     0xca62c1d6
(Если вас заинтересовал вопрос, откуда взялись эти числа, то укажем их источник:0x5A827999 = 2√/4, 0x6ED9EBA1 = 3√/4, 0x8F1BBCDC = 5√/4, 0xCA62C1D6 = 10−−√/4; все умножено на 232).
Предварительная обработка
1. Дополнение сообщения
Цель – сделать сообщение кратным 512 или 1024 бит, зависит от выбранного алгоритма SHA. Дополнение может быть выполнено перед процедурой вычисления хэша, или в ходе выполнения хэша, но до обработки блока(ов), который (ые) будут содержать дополнение.
SHA-1, SHA-224, SHA-256SHA-384, SHA-512, SHA-512/224, SHA-512/384Предположим, что длина сообщения M равна l бит. Сначала в конец сообщения добавляется «1», а затем нули - в количестве k - так, чтобы размер полученного сообщения был на 64 разряда меньше числа, кратного 512 (l+1+k = 448 mod 512). Далее, к полученному результату добавляется 64-битовое представление размера l исходного сообщения М. Например, (ASCII текст) у нас есть сообщение «abc», длиной 8 * 3 = 24 бита. Добавляем к сообщению «1», затем 448 - (24 +1) = 423 бит «0», и в конце 64-битовое представление размера 24 = 00…011000. В итоге получим 512-битовое сообщение вида:

2. Разбиение дополненного сообщения на M-битные блоки.
Дополненное сообщение разбивается на N M-битных блоков.
SHA-1, SHA-224, SHA-256SHA-384, SHA-512, SHA-512/224, SHA-512/384Дополненное сообщение разбивается на N 512-битовых блоков: M(1), M(2) … M(N). Т.к. 512 бит можно выразить как 16 (шестнадцать) 32-битных слов, то первые 32 бита i-го блока сообщения обозначим M0(i), следующие 32 бита M1(i), и так дойдем до M15(i).
3. Установка инициализирующих значений
Перед процедурой вычисления хэша алгоритм устанавливает начальные значения H. Размер и количество слов H зависит от выбранного алгоритма.
SHA-1SHA-224SHA-256SHA-384SHA-512SHA-512/224SHA-512/256Четыре 32-битных слова.H0 = 0x67452301H1 = 0xefcdab89H2 = 0x98badcfeH3 = 0x10325476H4 = 0xc3d2e1f0
Вычисление хэшаSHA-1SHA-256SHA-224SHA-512SHA-384SHA-512/224SHA-512/256В алгоритме сложение "+" происходит по модулю 232.
For i = 1 to N:{     1. i-й блок сообщения с помощью приведенного далее алгоритма     преобразуется из 16 слов размером в 32 разряда (с М0(i) по М15(i))     в 80 слов размером 32 разряда (с W0 по W79):     Wt = Mt, для t = 0..15     Wt = ROTL(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16, 1), для t = 16..79     (Интересно, что в первоначальном варианте спецификации SHA (алгоритм SHA-0) не было     циклического сдвига влево ROTL(x, 1))
     2. Инициализируем переменные a,b,c,d,e.     a = H0(i-1)     b = H1(i-1)     c = H2(i-1)     d = H3(i-1)     e = H4(i-1)
     3. Главный цикл функции сжатия     For t = 0 to 79          TEMP = ROTL(a, 5) + ft(b,c,d) + e + Wt + Kt          e = d          d = c          c = ROTL(b, 30)          b = a          a = TEMP
     4. Считаем промежуточное хэш-значение     H0(i) = (H0(i-1) + a)     H1(i) = (H1(i-1) + b)     H2(i) = (H2(i-1) + c)     H3(i) = (H3(i-1) + d)     H4(i) = (H4(i-1) + e)}
Результирующее хэш-значение – 160-битный дайджест сообщения:H0(N) || H1(N) || H2(N) || H3(N) || H4(N) (5 слов * 32 бита = 160 бит)Внимание: порядок байт в каждом слове "big-endian"
Операции над словами (32-битными).ROTL - циклический сдвиг влево на n бит:ROTL(x, n) = (x « n) | (x » (32-n))
Стандарт получения хэш-функции - ГОСТ Р34.11-94.

9-билет
Электронная цифровая подпись.
Стандарт DSS.
ГОСТ Р34.10-94 – стандарт цифровой подписи.
10-билет
Защита программного обеспечения от исследования
Алгоритм Евклида нахождения наибольшего общего делителя.
Способы вычисление обратных чисел.
11-билет
Расширенный алгоритм Евклида.
Алгоритмы цифровой подписи
Управление ключами
12-билет
Какие шифры называются шифрами простой замены?
Какие шифры называются шифрами перестановки?
Что является ключом шифра Виженера?
13-билет
Назовите основные понятия информационной безопасности компьютерных систем.
Назовите основные типы угроз безопасности АСОИ.
Какие требования предъявляются к криптографически стойкому генератору псевдослучайной последовательности чисел
14-билет
Что понимается под накоплением ключей?
Как называются ключи, зашифровывающие ключевую информацию?
Для чего используется алгоритма Диффи-Хелмана?
15-билет
Что может сделать нарушитель через Internet?
Какие службы и протоколы Internet являются уязвимыми?
Что должна включать политика сетевой безопасности каждой организации?
16-билет
Как можно защититься от статического исследования программы?
Назовите средства статического исследования программы.
Назовите средства динамического исследования программы.
17-билет
Что представляет собой рассеивание?
Каким способом достигаются эффекты рассеивания и перемешивания?
Как выполняется функция шифрования?
18-билет
Цель использования многоалфавитной подстановки.
Назовите традиционные методы шифрования
Назовите биграммные шифры
20-билет
Какую длину блоков имеет шифр?
Как зависят друг от друга длина ключа и длина блока?
Стандарт криптографической защиты AES - RIJNDAEL
21-билет
В каком режиме работает алгоритм RC4?
Элементы теории чисел, используемые в криптографии
Назначение функции Эйлера?
22-билет
Асимметричные криптоситемы.
Перечислите способы нахождения обратных чисел.
Для чего используется расширенный алгоритм Евклида?

Приложенные файлы

  • docx 8890238
    Размер файла: 986 kB Загрузок: 0

Добавить комментарий