0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
_
|
а
|
б
|
в
|
г
|
д
|
е
|
ж
|
з
|
и
|
й
|
к
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
22
|
23
|
л
|
м
|
н
|
о
|
п
|
р
|
с
|
т
|
у
|
ф
|
х
|
ц
|
24
|
26
|
27
|
28
|
29
|
30
|
31
|
32
|
33
|
34
|
35
|
ч
|
ш
|
щ
|
ъ
|
ы
|
ь
|
э
|
ю
|
я
|
А
|
Б
|
В
|
36
|
37
|
38
|
39
|
40
|
41
|
42
|
43
|
44
|
45
|
46
|
47
|
Г
|
Д
|
Е
|
Ж
|
З
|
И
|
Й
|
К
|
Л
|
М
|
Н
|
О
|
48
|
49
|
50
|
51
|
52
|
53
|
54
|
55
|
56
|
57
|
58
|
59
|
П
|
Р
|
С
|
Т
|
У
|
Ф
|
Х
|
Ц
|
Ч
|
Ш
|
Щ
|
Ъ
|
61
|
62
|
63
|
64
|
|
Ы
|
Ь
|
Э
|
Ю
|
Я
|
|
Вх. параметры: а
Вых. параметры: m
, где
, где
Где -
исходный символ, -
закодированный символ. Операция кодирования это табличная функция, в результате
которой получается сообщение , состоящее из ,
представленных в виде чисел. Данный алгоритм определяется формулой (1) и
обозначаться:
(1)
Алгоритм
перевода из десятичного числа в двоичное число
Для реализации быстрого возведения в
степень по модулю понадобится перевести число из десятичной системы счисления в
двоичную систему счисления. Для этого необходимо десятичное число представить в
виде суммы, состоящей из произведения степеней двойки. Математически это
записывается так:
Вх. параметры: m
Вых. параметры: ,
n
(2)
Где -
цифры из множества {0,1}, -
количество разрядов двоичного числа , -
исходное заданное нам число в десятичной системе счисления, -
двоичное представление числа m,
=.
Система формул (2) с
начальными условиями полностью описывает алгоритм и будет обозначаться так:
(3)
Алгоритм
быстрого возведения числа в степень
Обыкновенное возведение
в степень по модулю больших чисел непростая и долгая операция, значит,
криптографические действия будут идти довольно медленно, что бы этого избежать
используем метод быстрого возведения в степень с использованием процедуры из
пункта 4.2.
Вх. параметры: а, ,
p
Вых. параметры:
В аналитическом виде
формула для вычисления числа в степень по модулю представляет собой:
Где у - возведенное в
степень по модулю число; i
- индекс, а - возводимое в степень по модулю исходно число, р - простое число -
значение i-ого разряда числа , ,
представленного в двоичном виде с помощью формулы (2):
В рекуррентном виде алгоритм
описывается так:
(4)
где у - возведенное число, а -
возводимое в степень по модулю исходно число, р - простое число, n - количество разрядов, i - индекс. Система формул (3)
определяет процедуру для быстрого возведения числа в степень, которую будем
определять формулой (4):
(5)
Алгоритм
поиска взаимно простых чисел
Для реализации этой задачи требуется
классический алгоритм Евклида.
Пусть и
-
целые положительные числа, a>b, тогда наибольший общий делитель (НОД) чисел и
есть
наибольшее число ,
которое делит и ,
и :
Этот алгоритм описывает следующая
система рекуррентных формул:
(6)
Где a и b - исходные числа, q - остаток от целочисленного
деления.
Система рекуррентных выражений (6)
полностью описывает алгоритм и, для дальнейшего использования, будет
обозначаться:
(7)
где и
-
положительные целые числа, с - НОД этих чисел.
Алгоритм
вычисления обратного числа
Для того чтобы разработать алгоритм
Шифрования и дешифрования Шамира, нужно найти инверсию по модулю. Инверсия
числу называется такое число , удовлетворяющее следующему условию: ), . Для
этого воспользуемся Обобщенным алгоритмом Евклида:
Обобщенный алгоритм
Евклида позволяет вычислять кроме НОД () числа x и y такие, что:
(8)
Вх. переменные: a, b
Вых. переменные: g, x, y
(9)
Система уравнений (9) с начальными
условиями полностью описывает обобщенный алгоритм Евклида.
Что бы найти инверсию по модулю
нужно в уравнение (8) сделать замены:
Тогда уравнение (7)
преобразуется в уравнение (9) с помощью которого и находится инверсию по
модулю:
(10)
Аналитически это записывается так:
(11)
Чтобы число d всегда было положительным (в
последствии оно будет использоваться как степень другого числа), выполняется
следующая операция:
(12)
Выражения (10) и(11) описывают
алгоритм вычисления обратного числа и в дальнейшем будет обозначаться:
(13)
Алгоритм
генерации ключей
Абоненты А и B генерируют ключи - случайные числа и соответственно
взаимно простые с .
Для более быстрого поиска ключей введем диапазон K,
с минимальным значением и
максимальным ,
среди которого будут подбираться ключи:
(14)
Главное условие для
первой пары ключей и
состоит в следующем:
(15)
где р - исходное простое
число, q - это число, выбранное случайным образом из диапазона K, удовлетворяющее условию (15), будет соответствовать ключу для
абонента А. (Таким же образом выбирается ключ для абонента В). В
случае если q не соответствует условию (15), ищется следующее число q, удовлетворяющее этому условию.
Вх. переменные: р
В рекуррентном виде
будет выглядеть так:
(16)
где randi - является генератором случайного числа в диапазоне K, state - параметр,
отвечающий за активацию / деактивацию генератора, -
минимальное и максимальное значение диапазона K,
i - индекс, -
1-ый ключ абонента А (для абонента В генерация первого ключа -
аналогична).
В дальнейшем обозначим
систему уравнений (16) как:
(17)
где K - диапазон, в котором ищем ключи, р - простое число, -
первый ключ абонента А. (для абонента В генерация первого ключа -
аналогична).
Затем абоненты А и B генерируют ключи и,
обратные с и
соответственно,
с помощью функции ,
такие что: и
.
Аналитически это будет
выглядеть так:
(18)
Для дальнейшего использования,
обозначим систему уравнений (18) следующим образом:
(19)
где с - исходное число, m - модуль, -
инверсия числа .
Используя ,
абоненты вычисляют вторые ключи шифрования - и .
Алгоритм
шифрования сообщения по криптоалгоритму Шамира
Абонент A выбирает простое число p,
в нашем случае ,
которое он передаёт по открытому каналу второму абоненту. Затем A вычисляет случайное число взаимно простое с p-1:
(20)
где -
первый секретный ключ абонента А, K
- диапазон ключей, р - исходное простое число. Далее вычисляет число обратное
по
модулю :
(21)
где -
второй секретный ключ абонента А, - первый секретный ключ
абонента А,
р - исходное простое
число.
Эти числа абонент A держит в секрете. Далее абонент А кодирует сообщение по формуле
(22):
(22)
где а - исходное сообщение, m - закодированое сообщение.
После вычисляет по
формуле (23):
(23)
где -
исходный текст, -
первый секретный ключ абонента А, р - исходное простое число, и передаёт это
число второму абоненту.
После получения от
абонента B числа ,
A вычисляет по
формуле (24):
(24)
где -
некоторое число, полученное от абонента , -
второй секретный ключ абонента , р - исходное простое
число, и снова передаёт абоненту B.
Алгоритм дешифрования
сообщения по криптоалгоритму Шамира
Рассмотрим алгоритм
дешифрования. Абонент B
принимает простое число ,
которое открыто передаёт его абонент A.
Затем B вычисляет число взаимно простое с числом
:
(25)
где -
первый секретный ключ абонента В, K
- диапазон ключей, р - исходное простое число. Затем вычисляет обратное
по
модулю:
(26)
где -
второй секретный ключ абонента В, - первый секретный ключ
абонента В,
р - исходное простое
число. После получения числа от абонента A, абонент B
вычисляет по
формуле (27):
(27)
где -
некоторое число полученное от абонента А, - первый секретный ключ
абонента В, р - исходное простое число. Далее абонент В передает абоненту
А.
Затем B снова получает новое число и вычисляет по
формуле (28):
(28)
где -
некоторое число полученное от абонента А, - первый секретный ключ
абонента В, р - исходное простое число, - исходное, пока еще
закодированное, дешифрованное сообщение.
Алгоритм
декодирования сообщения
При дешифровке полученного сообщения
абонент B получит массив чисел, который необходимо перевести в буквенный
текст. Алгоритм декодирования - обратный алгоритму кодирования, то есть каждой
цифре массива соответствует буква по таблице 2 алфавита .
Вх. параметры: m
Вых. параметры: а
, где
, где
Где -
закодированный символ, -
исходный символ, N - количество символов в
сообщении. Операция декодирования, обратная операция кодированию, табличная
функция, в результате которой получается сообщение ,
состоящее из ,
представленных в виде чисел. Данный алгоритм определяется формулой (29) и
обозначаться:
(29)
5. Разработка блок-схемы
алгоритма секретной связи с открытым ключом
В данном разделе разрабатывается
структурная схема секретной связи с открытым ключом методом Шамира.
В блоке передачи абонент
передаёт
некоторое сообщение представленное
в буквенном виде. Это сообщение передается в блок «Кодирование». Оно кодируется
c помощью функции и получается некоторый
набор чисел (пункт
4.1). Также генерируются два ключа , с
помощью функций и
(пункт
4.6) соответстенно - секретные ключи абонента , которые, вместе с ,
передаются в блок «Шифрование», который работает по формулам (20, 21) (Пункт
4.7). Из данного блока в открытый канал связи передаются ,
.
В блоке приема в момент
приема генерируется
пара ключей ,
-
секретные ключи абонента ,
с помощью функций и
(пункт
4.6). Таким образом, все эти параметры попадают в блок «Расшифрование», который
работает по формулам (24, 25) (Пункт 4.8.). После абонент получает
кодированное сообщение ,
которое и есть .
Сообщение необходимо декодировать, поэтому сообщение передается в блок
«Декодирование». Там его декодируют (пункт 4.9) с помощью функции и
на выходе блока получается переданное сообщение а.
6. Разработка
программных модулей
Функция кодирования
текста из букв русского алфавита
%mycodz65.m
%-
% функция для кодирования для
алфавита А65
%==================================================================
%описание входных переменных
%a - исходный текст
%%-
%описание выходных переменных
%m - закодированный текст
%==================================================================[m]
= mycodz65 (a)= ' абвгдежзийклмнопрстуфхцчшщъыьэюяАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ';
n = length(a);= zeros
(1, n);i=1:n(i) = strfind (z, a(i));
end
) Функция преобразования
десятичного числа в двоичное
%mybitget.m
%-
%в двоичной системе
%==================================================================
%описание входных переменных
%a - исходное число
%-
%описание выходных переменных
%x - число в двоичной СС
%n - количество разрядов
%==================================================================[x,
n] = mybitget (a)a <= 0;=0;=1;=fix (log2 (a)+1);=zeros (1, n);k = 1:n(k)=fix
(a/2^(n-k));=a-x(k)*2^(n-k);
end
) Функция реализующая быстрый
алгоритм возведения в степень
%mybegmod2.m
%-
%функция реализующая алгоритм
возведения в степень (слева на право) по
%модулю p
%==================================================================
%описание входных переменных
%a - число
%x - степень
%p - модуль
%-
%описание выходных переменных
%y = a^x mod p
%==================================================================[y]
= mydegmod2 (a, x, p)= 1;
[x, t] = mybitget(x);i =
1:t;= mod (y^2, p);x(i) == 1;= mod (y * a, p);
return
) Функция реализующая
классический алгоритм Евклида
%mycgcd.m
%-
%функция реализующая классический
алгоритм Евклида, вычисляющий наибольший
%общий делитель НОД (a, b)
%==================================================================
%описание входных переменных
%a - первое число
%b - второе число
%-
%описание выходных переменных
%g - наибольший общий делитель НОД
(a, b)
%==================================================================g
= mycgcd (a, b)b ~= 0= mod (a, b);= b;= c;= a;
4) Функция вычисления числа «d» обратному «c» по модулю «n»
.1) Обобщенный алгоритм Евклида
%mygcd.m
%-
%функция реализующая обобщенный
алгоритм Евклида, вычисляющий наибольший
%общий делитель НОД (a, b) и числа x
и y такие, что: ax+by=g
%==================================================================
%описание входных переменных
%a - первое число
%b - второе число
%-
%описание выходных переменных
%g - наибольший общий делитель НОД
(a, b)
%x, y - числа из условия ax+by=g
%==================================================================[g,
x, y] = mygcd (a, b)= [a, 1,0];= [b, 0,1];v(1) ~= 0;
q = fix (u(1)/v(1));=
[mod (u(1), v(1)), u(2) - q*v(2), u(3) - q*v(3)];= v;= t;= u(1);= u(2);= u(3);
return
Функция вычисления обратного числа
%myinvmod.m
%-
% функция вычисления числа «d» обратного данному «m» по модулю «n»
%==================================================================
%описание входных переменных
%m - исходное число
%c - модуль
%-
%описание выходных переменных
%d - инверсия по модулю n
%==================================================================[d]
= myinvmod (m, n)
[g, x, y] = mygcd (m,
n);
d = mod (y, m);
%mydecodz65.m
%-
% функция для декодирования
сообщения алфавита Z65
%==================================================================
%описание входных переменных
%m - закодированный текст
%%-
%описание выходных переменных
%a - исходный текст
%==================================================================[a]
= mydecodz65 (m)= '
абвгдежзийклмнопрстуфхцчшщъыьэюяАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ';
n = length(m);i=1:n=
m(i);(i) = z(k);
Выводы
Целью данной работы была разработка
системы секретной связи с открытым ключом на основе алгоритма Шамира для
абонентов А и В. Для этого были изучены и разработаны следующие алгоритмы и
функции:
· функции кодирования
и декодирования русского алфавита z65;
· функция перевода из
десятичной системы счисления в двоичную систему счисления;
· функция быстрого
возведения в степень по модулю;
· функция поиска
взаимно простых чисел с помощью классического алгоритма Евклида;
· функция инверсии по
модулю с помощью обобщенного алгоритма Евклида;
· алгоритм генерации
ключей.
. Все эти алгоритмы были
реализованы в виде соответствующих программных модулей для вычислительной среды
Матлаб. Для того чтобы проверить достоверность работы всех разработанных m-файлов, был разработан тестовый m-script файл Start.m. Исходное сообщение было: «Ефимов»,
после шифрования / дешифрования полученное сообщение: «Ефимов». Следовательно
алгоритм работоспособный.
. Данная программа была
протестирована. При тесте от пользователя А пользователю B было передано сообщение «Ефимов».
Принятое сообщение соответствует отправленному. Данный факт дает основание
полагать, что программа была разработана правильно. Стойкость протокола
основывается на сложности извлечения квадратного корня по модулю достаточно
большого составного числа n, факторизация которого неизвестна.
. В ходе работы были
определены достоинствами метода Шамира:
· передача информации
по открытому каналу;
· высокая
криптостойкость системы при большом значении р;
. Также были выявлены такие
недостатки как:
· значение p должно быть большим для высокой
криптостойкости
· довольно низкое
быстродействие
Протокол обеспечивает защиту только
от пассивного противника и не обеспечивает аутентификацию. В сущности, он
решает ту же самую задачу, что и классический, хорошо известный протокол обмена
ключами Диффи - Хеллмана, но путем транспортировки ключей, а не обмена ключами,
и используя для этого три пересылки сообщений вместо двух.
Список литературы
1. Собственный конспект лекций по дисциплине «Основы
криптографии», 2017.
2. Санников В.Г. Введение в теорию и методы криптографической
защиты информации: Учебное пособие. - М.: МТУСИ, 2009.
. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты
информации: Учебное пособие. М.: Горячая линия - Телеком, 2005.
. Потемкин В.Г., MATLAB: Справочное пособие. М.:
Диалог-МИФИ., 1997;
. Дьяконов В.П. Справочник по применению системы PC MatLAB.
М.: Наука, Физматлит., 1993.
. Волчков В.П. Электронный файл: Задание и методические
указания к выполнению КР по ОК_10_03_17.doc