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

66
Добавление недостающих блоков
Сообщение добавляется таким образом, чтобы его длинна была кратна 448 по модулю 512, то есть
512
mod
448

dlina
. Добавление происходит всегда и включает в себя 1 и необходимое количество нулей. После этого сообщение представляет собой последовательность из N блоков по 512 бит .
Основной алгоритм
Определяются 8 32-битных переменных: a,b,c,d,e,f,g,h. Данные переменные представляют собой промежуточные значения хеш-кода.
Над каждым полученным блоком исходного сообщения производиться 64 циклические обработки:
2 1
1
)
,
,
(
256 0
)
(
2 256
)
,
,
(
256 1
)
(
1
T
T
a
a
b
b
c
c
d
T
d
e
e
f
f
g
g
h
c
b
a
j
Ma
a
T
t
W
t
K
g
f
e
Ch
e
h
T



















Ki - шестьдесят четыре 32-битных константы, каждая из которых является первыми 32-мя битами дробной части кубических корней первых 64 простых чисел.
Wt вычисляются из очередного блока сообщения по следующим правилам:

67
















63 16
,
)
(
)
(
15 0
,
16 15 256 01 7
2 256 1
t
W
W
W
W
t
M
W
t
t
t
t
i
t
t


Каждое i-ое промежуточное значение хеша вычисляется так:
H
0
i
= a + H
0
i-1
H
1
i
= b + H
1
i-1
H
2
i
= c + H
2
i-1
H
3
i
= d + H
3
i-1
H
4
i-
= e + H
0 4-1
H
5
i
= f + H
5
i-1
H
6
i
= g + H
6
i-1
H
7
i
= h + H
7
i-1
Электронная подпись
Использование симметричных систем не позволяет полностью решить проблему проверки подлинности получаемого сообщения.
Факт наличия секретного ключа у отправиля и получателя дает второму участнику возможность формирования нового сообщения с использованием имеющегося аутентификатора.
Для исключения подобных ситуаций необходимо присутствие третьего участника (доверенного лица), которому должна посылаться копия сообщения. Однако, такой сценарий является не самым удобным. Решением проблемы стало использование ассиметричных алгоритмов шифрования.
В соответствии с Федеральным законом "Об электронной подписи" от 06.04.2011 под электронной подписью понимается информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом

68 связана с такой информацией и которая используется для определения лица, подписывающего информацию.
Проверка подлинности сообщения осуществляется с помощью открытого ключа автора. Эти данные доступны любому пользователю.
К электронной подписи предъявляются следующие требования:
1) уникальность (т. е. возможность использования ее только одним определенным пользователем);
2) невозможность отказа от выполненной подписи;
3) допустимость верификации подписи любым пользователем;
4) простота выполнения процедур создания и верификации подписи;
5) возможность выполнения для больших объемов информации
(файлов, дисков и т. д.).
В настоящее время применяется несколько алгоритмов электронной подписи:
1)
RSA (наиболее популярен);
2)
DigitalSignatureAlgorithm, DSA (одно из средств электронной подписи, применяемое в стандарте DSS);
3) алгоритм Эль-Гамаля (иногда можно встретить);
4) алгоритм, который применяют в стандарте ГОСТ РЗ4.10-94 (в основе лежит DSA и является вариацией подписи Эль-Гамаля);
5) так же существуют алгоритмы подписей, в основе которых лежит криптография эллиптических кривых; они похожи на все прочие, но в некоторых ситуациях работают эффективнее.
Электронная подпись на основе алгоритма RSA
Схема использования алгоритма RSA при большом модуле N практически не позволяет злоумышленнику получить

69 закрытый ключ и прочитать зашифрованное сообщение. Однако она дает возможность злоумышленнику подменить сообщение от пользователя А к пользователю Б, так как пользователь А шифрует свое сообщение открытым ключом, полученным от пользователя Б по открытому каналу связи. Так как открытый ключ передается по открытому каналу, любой может получить его и использовать для подмены сообщения. Избежать этого можно, используя более сложные протоколы, например, следующий.
Пусть, как и раньше, пользователь А хочет передать пользователю
Б сообщение, состоящее из нескольких блоков m i
. Перед началом сеанса связи абоненты генерируют следующие открытые и закрытые ключи.
Открытый ключ
Закрытый ключ
Пользователь А
N
A
, d
A
e
A
Пользователь Б
N
Б
, d
Б
e
Б
В результате каждый пользователь имеет свои собственные открытый (состоящий из двух частей) и закрытый ключи. Затем пользователи обмениваются открытыми ключами.
Это подготовительный этап протокола.
Основная часть протокола состоит из следующих шагов.
Сначала пользователь А вычисляет числа
A
A
e
i
i
N
m
c
mod

, то есть шифрует сообщение своим закрытым ключом. В результате этих действий пользователь А подписывает сообщение.
Затем пользователь А вычисляет числа
B
B
d
i
i
N
c
g
mod

, то есть шифрует то, что получилось на шаге 1 открытым ключом

70 пользователя Б. На этом этапе сообщение шифруется, чтобы никто посторонний не мог его прочитать.
Последовательность чисел g i
передается к пользователю Б.
Пользователь Б получает g i
и вначале вычисляет последовательно числа
B
B
e
i
i
N
g
c
mod

, используя свой закрытый ключ. При этом сообщение расшифровывается.
Затем пользователь Б определяет числа
A
A
d
i
i
N
c
g
mod

, используя открытый ключ пользователя А. За счет выполнения этого этапа производится проверка подписи пользователя А.
В результате пользователь Б получает исходное сообщение и убеждается в том, что его отправил именно пользователь А. Данная схема позволяет защититься от нескольких видов возможных нарушений, а именно:

пользователь А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему;

нарушитель без знания секретного ключа не может ни сформировать, ни сделать осмысленное изменение сообщения, передаваемого по линии связи.
Данная схема позволяет избежать многих конфликтных ситуаций.
Иногда нет необходимости зашифровывать передаваемое сообщение, но нужно его скрепить электронной подписью. В этом случае из приведенного выше протокола исключаются шаги 2 и 4, то есть текст шифруется закрытым ключом отправителя, и полученная последовательность присоединяется к документу. Получатель с помощью открытого ключа отправителя расшифровывает прикрепленную подпись, которая, по сути, является зашифрованным

71 повторением основного сообщения. Если расшифрованная подпись совпадает с основным текстом, значит, подпись верна.
Существуют и другие варианты применения алгоритма RSA для формирования ЭП.
Например, можно шифровать
(то есть подписывать) открытым ключом не само сообщение, а хеш-код от него.
Для осуществления подписи сообщения M=M
1
M
2
M
3
….M
n необходимо вычислить хеш- функцию m=h(M=M
1
M
2
M
3
….M
n
), которая ставит в соответствие сообщению M число m. На следующем шаге достаточно снабдить подписью только число m, и эта подпись будет относиться ко всему сообщению M.
Далее по алгоритму RSA вычисляются ключи (e, n) и (d, n).
Затем вычисляется ???? = ????
????
???????????? ????
Число s– это и есть электронная подпись. Она просто добавляется к сообщению и получается подписанное сообщение (M, s)
Теперь каждый, кто знает параметры подписавшего сообщение (т.е. числа e и N), может проверить подлинность подписи.
Для этого необходимо проверить выполнение равенства
ℎ(????) = ????
????
???????????? ????.
Возможность применения алгоритма RSA для получения электронной подписи связана с тем, что секретный и открытый ключи в этой системе равноправны. Каждый из ключей, d или e, могут использоваться как для шифрования, так и для расшифрования. Это свойство выполняется не во всех криптосистемах с открытым ключом.
Алгоритм RSA можно использовать также и для обмена ключами.

72
Электронная подпись на основе алгоритма Эль-Гамаля
Принцип создания и проверки подписи
Алгоритм
Эль-Гамаля также можно использовать для формирования электронной подписи. Группа пользователей выбирает общие параметры Р и А. Затем каждый абонент группы выбирает свое секретное число Хi, такое что 1<Хi<Р-1, и вычисляет соответствующее ему открытое число
P
A
Y
Y
i
X
i
i
mod
:

. Таким образом, каждый пользователь получает пару (закрытый ключ; открытый ключ) = (Хi,
Yi). Открытые ключи пользователей могут храниться в общей базе системы распределения ключей и при необходимости предоставляться всем абонентам системы.
Сообщение, предназначенное для электронной подписи, должно быть представлено в виде числа, меньшего модуля Р. При большом размере сообщение разбивается на блоки необходимого размера. В некоторых случаях подписывается не само сообщение, а значение хеш- функции от него. В любом варианте электронная подпись вычисляется в зависимости от некоторого числа m (m < P).
Пусть пользователь А хочет подписать свое сообщение цифровой подписью и передать его пользователю Б. В этом случае алгоритм действий следующий.
Пользователь А выбирает случайное секретное число k, взаимно простое с Р-1, и вычисляет число
P
A
a
a
i
k
mod
:

Затем с помощью расширенного алгоритма Евклида необходимо найти значение b в следующем уравнении: m = (x
⋅a +k⋅b) mod (P-1)
Пара чисел (a, b) будет электронной подписью сообщения m.

73
Сообщение m вместе с подписью (a, b) отправляется пользователю
Б.
Пользователь Б получает сообщение m и с использованием открытого ключа пользователя А и вычисляет два числа по следующим формулам: mod mod
*
2 1
1
P
A
c
P
a
Y
c
m
b


Если с1 =с2, то электронная подпись пользователя А верная. Для подписывания каждого нового сообщения должно каждый раз выбираться новое значение k.
Подписи, созданные с использованием алгоритма Эль-Гамаля, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (a, b), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма
RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.
Пример вычисления и проверки электронной подписи
Пусть абоненты, обменивающиеся через
Интернет зашифрованными сообщениями, имеют следующие общие параметры: Р = 11, А = 7.
Один из пользователей этой системы связи хочет подписать свое сообщение m=5 электронной подписью, сформированной по алгоритму Эль-Гамаля. Вначале он должен выбрать себе закрытый ключ, например, Х=3 и сформировать открытый ключ
Y= 7 3 mod 11 = 2. Открытый ключ может быть передан всем

74 заинтересованным абонентам или помещен в базу данных открытых ключей системы связи.
Затем пользователь выбирает случайное секретное число k, взаимно простое с Р-1. Пусть k=9 (9 не имеет общих делителей с 10 ).
Далее необходимо вычислить число a=7 9 mod 11=8.
После этого с помощью расширенного алгоритма Евклида находится значение b в уравнении: m = (x
⋅ a +k ⋅ b) mod (P-1)=(3⋅8+9⋅b) mod 10
Решением последнего уравнения будет значение b=9.
Таким образом, пара чисел (8, 9) будет электронной подписью сообщения m=5.
Если любой другой пользователь сети желает проверить электронную подпись в сообщении, он должен получить из базы данных открытый ключ первого пользователя (он равен 2), вычислить два числа с1 и с2 и сравнить их. c
1
=2 8
8 9
mod 11=10 c
2
= 7 5
mod 11=10
Так как с1 =с2=10, то электронная подпись первого пользователя верная.
Содержание работы
1.
Разработать программу, выдающую дайджест сообщения произвольной длины, на основе алгоритма SHA- 256.
2.
Вручную получить и проверить ЭЦП на основе алгоритма
Эль-Гамаля.
3.
Реализовать приложение, позволяющее вычислять ЭЦП, сформированную по алгоритмам RSA и Эль-Гамаля. Программа

75 должна работать с простыми числами большими 2 64
. С помощью разработанного приложения проверить решение пункта 2.
Варианты заданий.
№
ЭЦП по алгоритму Эль-Гамаля
Секретные параметры
1
X=11,k=3
2
X=10,k=15
3
X=3,k=13
4
X=6,k=13
5
X=13,k=19
6
X=17,k=5
7
X=8,k=17
8
X=15,k=15
9
X=14,k=17
10
X=13,k=19
Контрольные вопросы
1.
Что такое хеш-функция, для чего она используется? В чём заключается устойчивость к столкновениям?
2.
Как обмануть подписчика, если требование устойчивости к столкновению не выполняется?
3.
Что такое коллизия хеш-функций?
4.
Создание хеш-функции алгоритмом SHA-256?
5.
Для чего нужна цифровая подпись? Основные свойства цифровой подписи.
6.
Какие схемы цифровой подписи существуют? Какая схема самая распространенная и почему?

76 7.
Как осуществляется подпись RSA? В чем отличие подписи
RSA от алгоритма шифрования RSA?
8.
Как осуществляются подпись и проверка на подлинность подписи по алгоритму Эль-Гамаля?

77
Лабораторная работа №8
ЭЛЕКТРОННАЯ ПОДПИСЬ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
Цель работы: изучить алгоритм получения ЭЦП на основе эллиптической кривой.
Краткие теоретические сведения
Теория эллиптических кривых развивается во многих направлениях. Отдельного внимания заслуживает рассмотрение вопроса использования алгоритмов на основе эллиптической кривой в криптографии.
Преимущества использования ESDSA
(Elliptic Curve Digital
Signature Algorithm):
1) Степень защищенности на каждый бит выше, чем при использовании в системах с открытым ключом;
2) Быстродействие при программной и аппаратной реализации;
3) Успешно встраиваются в работу стандартных схем ассиметричного шифрования (шифрование Эль-Гамаля, RSA)
Эллиптическая кривая и эллиптическая группа
Эллиптической кривой называют множество пар точек (X,Y), удовлетворяющих уравнению:y
2
= ax
3
+ bx + c.
Эллиптическая группа E
p
(a,b) представляет собой набор точек (x,y) с целыми положительными координатами, x удовлетворяют соотношению: y
2
=x
3
+ ax + b ( mod p).
Алгоритм формирования элементов эллиптической группы:

78 1)
Для всех значений x (0 3
+ ax + b (mod p).
2)
Для каждого значения из шага 1 определяется квадратный корень по модулю M и элемент включается в группу E
p
(a,b), если результат положительный.
Использование эллиптических кривых для создания
стандарта цифровой подписи
В качестве секретного ключа выбирается некоторое случайное число x. Открытым ключом являются координаты точки на эллиптической кривой P, определяемую как P = x*Q, где
Q - специальным образом выбранная точка эллиптической кривой
(«базовая точка»). Координаты точки Q вместе с коэффициентами уравнения, задающего кривую, являются параметрами схемы подписи и должны быть известны всем участникам обмена сообщениями.
Выбор точки Q зависит от используемых алгоритмов и весьма непрост. Так, стандарт ГОСТ 34.10-2001 определяет, что точка Q должна иметь порядок q, где q — простое число с «хорошими алгебраическими свойствами».
Число q довольно велико
(2254 < q< 2256).
Алгоритм ЭП ESDSA
Алгоритм состоит из трех основных этапов: генерации, подписывания и проверки.
Алгоритм генерации
1)
Выбирается эллиптическая кривая E, определённая на Z
p
Количество точек в E(Z
p
) должно быть сравнимо с большим n.