Разработка системы секретной связи с открытым ключом на основе алгоритма Шамира

Разработка системы секретной связи с открытым ключом на основе алгоритма Шамира

Курсовая работа

Разработка системы секретной связи с открытым ключом на основе алгоритма Шамира

1. Задание на курсовую работу

) Используя математический пакет Matlab, разработать программу реализующую алгоритмы шифрования и дешифрования Шамира в случае двух абонентов A и B. Первым шагом надо определить номер No своего варианта курсовой работы. Он определяется по номеру N фамилии студента в журнале своей группы из следующей таблицы соответствия.

криптоалгоритм кодирование дешифрование шамир

Таблица 1. Таблица соответствия номера по журналу и номера варианта курсовой работы

Номер по журналу N=2, следовательно, номер варианта курсовой работы равен No=7.

В качестве простого модуля взять число p, указанное в таблице 2. Остальные параметры генерировать случайным образом.

Таблица 2. Таблица соответствия номера варианта и числа p

Номер варианта курсовой работы равен No=7, следовательно, р=5701.

) Алгоритмы протестировать с использованием кодировки русского алфавита  на примере шифрации / дешифрации своей фамилии.

2.      Актуальность и предыстория проблемы построения систем связи с открытым ключом

Исторически первыми появились симметричные криптосистемы c закрытым ключом. В данных системах для шифрования, и для дешифрования используется один и тот же криптографический ключ.

Шифрование с закрытым ключом основано на том, что доступ к ключу имеет только авторизованный персонал. Этот ключ должен держаться в секрете. Если ключ попадет в нехорошие руки, посторонний сможет получить несанкционированный доступ к зашифрованной информации. И отправитель, который шифрует сообщение, и получатель, который дешифрует сообщение, владеют одним и тем же ключом.

Главный минус симметричных криптосистем состоит в том, что для отправки кому-то защищенного сообщения необходимо располагать защищенным каналом передачи этому лицу закрытого ключа. А если у вас есть безопасный метод передачи ключа, то почему не воспользоваться этим же методом для передачи сообщений? То есть необходимо защищённо отправить ключ. К счастью, в 1976 году произошел прорыв, когда Дифи и Хелман опубликовали первый алгоритм шифрования с открытым ключом.

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

Наиболее известный алгоритм с открытым ключом - это алгоритм RSA, который был разработан Ривестом, Шамиром и Адельманом в Мичиганском технологическом институте (MIT) и опубликован в 1978 году. Ранее алгоритм RSA был защищен патентом, но срок действия патента истек в сентябре 2000 года.

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

3.      Постановка задачи

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

.        Разработка функции «mycodz65», преобразующую исходное, буквенное сообщение  в массив чисел, с использованием алфавита . Результатом работы данной функции будет закодированное сообщение , состоящее из цифр.

.        Разработка процедуры «mybitget» преобразования сообщения, представленного в десятичном виде в двоичное. Делается это для того, чтобы алгоритм возведения числа в степень был как можно быстрее.

.        Разработка алгоритма быстрого возведения числа в степень «mybegmod2». Этот алгоритм необходим для реализации алгоритма шифрования и дешифрования.

4.      Разработка алгоритма поиска взаимно простых чисел «mygcd». Данный алгоритм нужен для поиска ключей  и.

.        Разработка функции вычисления обратного числа «myinvmod». Она так же понадобится для алгоритма шифрования и дешифрования.

.        Разработка этапа генерации секретных ключей для абонентов А и В. Без них реализовать алгоритм Шамира невозможно.

.        Следующим этапом является разработка функции, реализующей алгоритм шифрования «shamir_enc».

.        Разработка алгоритма дешифрования Шамира «shamir_dec», т.к. после передачи зашифрованного сообщения его надо дешифровать.

.        Разработка функции декодирования сообщения «mydecodz65» для преобразования массива цифр, который получает абонент , в исходное сообщение.

10.    И, наконец, проверка работоспособности алгоритма с помощью тестового m-Script файла. Для проверки нужно использовать свою фамилию.

.        Описание метода решения

В данном разделе приводится подробное математическое описание всех этапов, перечисленных в разделе 3.

Алгоритм кодирования

При реализации алгоритма Шамира используются цифры, поэтому необходимо преобразовать буквенное сообщение в цифры с помощью алфавита Z65, приведенного в таблице 3.

Таблица 3. Алфавит

Вх. параметры: а

Вых. параметры: 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