Файл: Ббк 32. 81я7 И74 Составители ст преп. С. И. Жданова ст преп. С. Н. Рога и 74 информационная безопасность методические указания к выполнению лабораторных работ и ргз для студентов очной формы обучения направлений бакалавриата.pdf

53
"трудно" означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа.
Например, если длина входа n битов, и время вычисления функции пропорционально 2
n
, то это считается вычислительно невозможной задачей.
Ассиметричное шифрование
Схема шифрования
Шифрование с открытым ключом состоит из следующих шагов:
1)
Пользователь В создает пару ключей KU
b и KR
b
, используемых для шифрования и дешифрования передаваемых сообщений.
2)
Пользователь В делает доступным некоторым надежным способом свой ключ шифрования, т.е. открытый ключ KU
b
Составляющий пару закрытый ключ KR
b держится в секрете.
3)
Если А хочет послать сообщение В, он шифрует сообщение, используя открытый ключ В KU
b
4)
Когда В получает сообщение, он дешифрует его, используя свой закрытый ключ KR
b
. Никто другой не сможет дешифровать сообщение, так как этот закрытый ключ знает только В.
Достоинства и недостатки асимметричных алгоритмов.
Достоинства:

отсутствие необходимости передачи секретного ключа;

число ключей в ассиметричной системе меньше, чем в симметричной;
Недостатки:

54

низкое быстродействие;

используются более длинные ключи, чем симметричные;

требуются большие вычислительные ресурсы.
Алгоритм шифрования RSA
Алгоритм RSA был одним из первых алгоритмов ассиметричного шифрования. Он был разработан в 1977 году Роном Ривестом, Ади
Шамиром и Леном Адлеманом. С тех пор алгоритм Rivest-Shamir-
Adleman
(RSA ) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.
Алгоритм основан на использовании того факта, что задача
факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.
Алгоритм
RSA представляет собой блочный
алгоритм
шифрования, где зашифрованные и незашифрованные данные являются целыми числами между 0 и n -1 для некоторого n.
Вычисление ключей
Для алгоритма RSA этап создания ключей состоит из следующих операций:
1)
Выбираются два простых различных числа p и q.
Вычисляется n= p*q
2)
Вычисляется функция Эйлера φ(n)=(p-1)⋅(q-1)
3)
Выбирается произвольное число e, такое что 1 и
НОД (n,e)=1

55 4)
Вычисляется d , такое что 1. Число d должно удовлетворять условию
1
)
(
mod


n
d
e

. Для нахождения d используется расширенный алгоритм Евклида. Число d является частью закрытого ключа и хранится в секрете.
5)
Открытым ключом будем называть пару числе KU (e,n).
6)
Закрытый ключ KR (d,n).
Расширенный алгоритм Евклида
Расширенный алгоритм Евклида состоит из двух частей. Первая часть позволяет вычислить НОД двух чисел. При вычислении используется рекуррентное правило:
НОД (A,B)= НОД (B,A mod B)
Вычисление производятся до тех пор, пока A mod B = 0. Последнее ненулевое значение является искомым делителем.
Вторая часть алгоритма позволяет решить уравнение вида
d
y
B
x
A


*
*
, где A, B - заданные числа, d- НОД (A,B).
В расширенном алгоритме Евклида, помимо рекуррентных соотношений из первой части, используются также и следующие соотношения:
i
i
i
i
i
i
B
div
A
y
x
y
y
x
)
(
*
;
1 1
1






Первоначальные значения параметров следующие: x=0,y=1.
Применительно в алгоритму RSA уравнение принимает вид
1
*
)
(
*


y
n
d
e

. В результате необходимо получить значение переменной d.
Пример
Найти d, зная что e=7,φ(n)=40.
Решение:

56
Представим решение в виде таблицы. В рассматриваемом примере
A = e=7,
B(φ(n)=40
A
B
A mod B A div B x y
7 40 7
0 40 7
5 5
7 5
2 1
5 2
1 2
2 1
0 2
Заполняем два последних столбца таблицы, начиная с последней строчки:
A
B
A mod B
A div B x y
7 40 7
0
-17
-17 40 7
5 5
3
-17 7
5 2
1
-2 3
5 2
1 2
1
-2 2
1 0
2 0
1
Таким образом получаем, что искомый параметр d = -17
Получим положительное значение параметра
d:
23 40
mod
17
)
(
mod




n
y
d


57
Шифрование
Отправитель разбивает свое сообщение на блоки m i
, длина которых в битах не превышает log
2 n. Если блок имеет меньшую длину, то он добавляется нулями в двоичном представлении до необходимой величины.
Для каждого m i вычисляется c i
, такое что
n
m
c
e
i
i
mod

Дешифрование
Чтобы получить открытый текст необходимо каждый блок зашифрованного текста дешифровать по следующему правилу:
n
c
m
d
i
i
mod

Рассмотрим конкретный пример:
Выбираем два простых числа p=7,q=17.
Вычисляем n=p⋅q=7⋅17=119
Вычисляем φ (n)= (p-1)⋅(q-1) = 96
Выбираем е, удовлетворяющее требованиям алгоритма: e=5
Определяем d так, чтобы d*e≡1 mod 96. d = 77
Результирующие ключи открытый KU = {5, 119} и закрытый
KR = {77, 119}.
Например, требуется зашифровать сообщение М = 19 19 5
= 66 (mod 119); С = 66
Для дешифрования вычисляется 66 77
(mod 119) = 19
Комбинирование симметричных и асимметричных
алгоритмов
Комбинирование двух криптографических подходов позволяет использовать достоинства каждого из типов алгоритмов. В основном

58 идея сводится к тому, что сообщение шифруется симметричным алгоритмом, что позволяет выиграть в скорости, т.к. сообщение может быть сколь угодно большим, а ключ симметричного алгоритма шифруется асимметричным алгоритмом.
Содержание работы
1.
Реализовать криптоалгоритм RSA.
Требования к реализации:

простые числа p и q генерируются программой или задаются из файла, где они представлены в битовой форме.

Длина генерируемых значение p и q должна задаваться пользователем;

сгенерированные ключи записываются и хранятся в разных файлах.
2.
Реализовать систему шифрования/дешифрования, в которой основным алгоритмом шифрования/дешифрования является AES.
Ассиметричный алгоритм
RSA используется для шифрования/дешифрования ключа.
Требования к реализации:

ключ для симметричного алгоритма должен генерироваться случайным образом;

зашифрованный текст должен сохраняться в первом файле, дешифрованный текст - во втором, а зашифрованный асимметричным алгоритмом ключ симметричного алгоритма – в третьем файле;

Приложение расшифровывает зашифрованный ключ симметричного шифрования. После этого расшифровывает шифртекст.

59

программа должна уметь работать с текстом произвольной длины.
Контрольные вопросы
1.
В чём заключается алгоритм RSA?
2.
В чем заключается криптографическая стойкость алгоритм
RSA?
3.
Дано e=3, φ (n)= 16. Найти d.
4.
Для чего и почему используют комбинированные криптоалгоритмы?
5.
В чём заключаются достоинства и недостатки асимметричных алгоритмов?
6.
В чём заключаются достоинства и недостатки симметричных алгоритмов?

60
Лабораторная работа №7
АЛГОРИТМЫ ХЕШИРОВАНИЯ. ЭЛЕКТРОННАЯ
ПОДПИСЬ
Цель работы: изучить алгоритм хеширования SHA-256.
Ознакомиться со схемами получение электронной подписи и овладеть навыками создания и проверки подлинности электронной подписи.
Краткие теоретические сведения
Однонаправленные хеш-функции
Однонаправленная функция H(M) применяется к сообщению произвольной длины M и возвращает сообщение фиксированной длины h: h= H(M), где h имеет длины M.
Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хеш-функций есть дополнительные свойства, делающие их однонаправленными:
1) зная M, легко вычислить h. Зная H, трудно вычислить M, такое что H(M)=h;
2) зная M, трудно вычислить такое Mʹ
такое, что H(M)=H(Mʹ).
Смысл однонаправленных хеш-функций состоит в обеспечении для
M уникального идентификатора («отпечатка пальца»).
В некоторых приложениях однонаправленности недостаточно, необходимо, чтобы выполнялось другое требование, называемое

61
устойчивостью к столкновению: должно быть трудно вычислить такое Mʹ такое, что H(M)=H(Mʹ)
Хеш-функция, которая удовлетворяет первым двум свойствам, называется простой или слабой хеш-функцией. Выполнение последнего свойства делает хеш-функцию сильной. Оно защищает против класса атак, известных как атака "день рождения".
Атака «день рождения»
В криптографии под атакой «дней рождения» понимают метод взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения.
Для заданной хеш-функции f целью атаки является поиск коллизии второго рода. Для этого вычисляются значения f для случайно выбранных блоков входных данных до тех пор, пока не будут найдены два блока, имеющие один и тот же хеш. Таким образом, если f имеет N различных равновероятных выходных значений, и N является достаточно большим, то из парадокса о днях рождения следует, что, в среднем, после перебора
N
*
25 1
различных входных значений, будет найдена искомая коллизия.
Следующий протокол, впервые описанный Гидеоном Ювалом, показывает, как, если требование устойчивости к столкновению не выполняется, пользователь А может использовать вскрытие методом дня рождения для обмана пользователя Б.
1) Пользователь А готовит две версии контракта: одну, выгодную для пользователя Б, и другую, приводящую его к банкротству.
2) Пользователь
А вносит несколько незначительных изменений в каждый документ и вычисляет хеш-функции. (Этими

62 изменениями могут быть действия, подобные следующим: замена
«пробела» комбинацией «пробел»–«забой»–«пробел», вставка одного- двух «пробелов» перед возвратом каретки и т.д. Делая или не делая по одному изменению в каждой из 32 строк, пользователь А может легко получить 232 различных документа).
3) Пользователь А сравнивает хеш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. Он восстанавливает два документа, дающих одинаковое хеш-значение.
4) Пользователь А получает подписанную пользователем Б выгодную для него версию контракта, используя протокол, которым он подписывает только хеш-значения.
5) Спустя некоторое время, пользователь А подменяет контракт, подписанный пользователем Б, другим, который он не подписывал. Теперь пользователь А может убедить арбитра в том, что пользователь Б подписал другой контракт
Вследствие этого длина хеш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Предпочтительнее, чтобы длина составляла не менее 100 битов.
Для удлинения хеш-значений, выдаваемых конкретной хеш- функцией, был предложен следующий метод:
1) Для сообщения с помощью одной из однонаправленных хеш-функций генерируется хеш-значение.
2) Хеш-значение добавляется к сообщению.
3) Генерируется хеш-значение объединения сообщения и хеш- значения этапа 1.

63 4) Создаётся большее хеш-значение, состоящее из объединения хеш-значения этапа 1 и хеш-значения этапа 3.
Этапы 1–4 повторяются нужное количество раз для обеспечения требуемой длины хеш-значения.
Обзор однонаправленных хеш-функций
Нелегко построить функцию, вход которой имеет произвольный размер, а тем более сделать её однонаправленной. В реальном мире однонаправленные хеш-функции строятся на идее функции сжатия.
Такая однонаправленная функция выдаёт хеш-значение длины при заданных входных данных большей длины. Входами функции сжатия являются блок сообщения и выход предыдущего блока текста. Выход представляет собой хеш-значение всех блоков, т.е. хеш-значение блока
Mi равно h
i
= f(M
i
, h i-1
)
Это хеш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия. Хеш-значением всего сообщения будет хеш-значение последнего блока.
Хешируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения.
Таким образом, преодолевается потенциальная проблема, вызванная тем, что

64 сообщения различной длины могут давать одно и то же хеш-значение.
Иногда такой метод называется MD-усилением.
В качестве однонаправленных хеш-функций можно использовать симметричные блочные алгоритмы шифрования. Самый очевидный способ – это шифрование сообщения в режиме CBC и CFB с помощью фиксированного ключа и ключа инициализации, хеш-значением будет последний блок шифр текста.
Более хороший способ использует в качестве ключа блок сообщения, в качестве входа – предыдущее хеш-значение, а выходом служит текущее хеш-значение.
Действительные хеш-функции ещё сложнее. Размер блока обычно совпадает с длиной ключа, размером хеш-значения будет длина блока.
Т.к. большинство блочных алгоритмов 64-битные, то спроектирован ряд схем, дающих хеш-значение, в два раза большее длины блока.
При условии, что хеш-функция правильна, безопасность этой схемы основана на безопасности используемой блочной функции.
Однако есть и исключения. Дифференциальный криптоанализ лучше работает против блочных функций в хеш-значениях, чем против блочных функций, используемых для шифрования: ключ известен, поэтому можно использовать различные приёмы. Для успеха нужна только одна правильная пара, и можно генерировать столько выбранного открытого текста, сколько нужно. Полезной мерой для хеш-функций, основанных на блочных шифрах, является скорость хеширования или количество n-битовых блоков сообщения, обрабатываемых при шифровании. Чем выше скорость хеширования, тем быстрее алгоритм

65
Хеш-функция SHA-256
SHA-256 представляет собой криптографическую функцию хеширования. Данная хеш-функция была принята в качестве стандарта в 2001 году.
Основные показатели (измеряются в битах):
Длина сообщения: менее 2 64
Длина блока: 512
Длина слова: 32
Количество итераций в цикле: 64
Длина хеш-значения: 256
Алгоритм работает с данными, разбитыми на куски в 512 бит.
Раунд в алгоритме SHA-256 повторяется 64 раза. Все операции выполняются над 32-битными словами. Результатом каждой функции также является 32-битное слово.
SHA-256 использует шесть логических функций: конъюнкция, побитовое "И", исключающее "ИЛИ", логический сдвиг вправо на n бит (SHR
n
), циклический сдвиг вправо на n бит (ROTR
n
), сложение по модулю 2 32
:
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
^
(
)
^
(
)
^
(
)
,
,
(
)
^
(
)
^
(
)
,
,
(
10 19 17 256 1
3 18 7
256 0
25 11 6
256 1
22 13 2
256 0
x
SHR
x
ROTR
x
ROTP
x
x
SHR
x
ROTR
x
ROTP
x
x
ROTR
x
ROTR
x
ROTP
x
x
ROTR
x
ROTR
x
ROTP
x
z
y
z
x
y
x
z
y
x
Maj
z
x
y
x
z
y
x
Ch





















