Курсовая работа (т): Шифрование. Криптосистемы

7. Алгоритм открытого распределения ключей Диффи-Хеллмана

Алгоритм Диффи-Хеллмана был первым алгоритмом с открытыми ключами (предложен в 1976 г.). Его безопасность обусловлена трудностью вычисления дискретных логарифмов в конечном поле, в отличие от легкости дискретного возведения в степень в том же конечном поле.

Предположим, что два пользователя А и В хотят организовать защищенный коммуникационный канал.

. Обе стороны заранее уславливаются о модуле N (N должен быть простым числом) и примитивном элементе g, (1 £ g £ N -1).

Эти два целых числа N и g могут не храниться в секрете. Как правило, эти значения являются общими для всех пользователей системы.

. Затем пользователи А и В независимо друг от друга выбирают собственные секретные ключи k_А и k_В (k_А и k_В - случайные большие целые числа, которые хранятся пользователями А и В в секрете).

. Далее пользователь А вычисляет открытый ключ

_A = (mod N),

а пользователь В - открытый ключ

_В = (mod N).

. Затем стороны А и В обмениваются вычисленными значениями открытых ключей y_A и y_В по незащищенному каналу.

. Далее пользователи А и В вычисляют общий секретный ключ, используя следующие выражения:

пользователь А:К =  =  (mod N);

пользователь В:К´ =  =  (mod N).

При этом К = К´, так как =  (mod N).

Рис. 7.1- Схема реализации алгоритма Диффи-Хеллмана

8. Решение заданий

Задание №1

Зашифровать методами простой перестановки сообщение:

КОНФИДЕНЦИАЛЬНОСТЬ ДАННЫХ ЭТО СТАТУС ПРЕДОСТАВЛЯЕМЫЙ ДАННЫМ И ОПРЕДЕЛЯЮЩИЙ ТРЕБУЕМУЮ СТЕПЕНЬ ИХ ЗАЩИТЫ

Отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы: 7x13

Шифртекст записываем группами по пять букв:

КНОНТ ЕЛАПЮ БТХОЦ СЫАДЯ НРЩУЕ ЗНИТХ ТОЕНЕ ИЕПАФ АЬЭУС МЫДЙМ ЕЩИЛД ТСТЫМ ЕТУНИ ДЬАОП АЙИЛР ЮЬТЕН НСРВД ОЯЕСИ Ы

Объединение букв шифртекста в 5-буквенные группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При расшифровании действия выполняют в обратном порядке.

Задание №2

Зашифровать выбранное в задании №1 сообщение методом перестановок на основе маршрутов Гамильтона.

L=6, K=2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1

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

Исходный текст разбивается на 11 блоков:

=<КОНФИДЕН>

=<ЦИАЛЬНОС>

=<ТЬ ДАННЫ>

=<Х ЭТО СТ>

=<АТУС ПРЕ>

=<ДОСТАВЛЯ>

=<ЕМЫЙ ДАН>

=<НЫМ И ОП>

=<РЕДЕЛЯЮЩ>

=<ИЙ ТРЕБУ>

=<ЕМУЮ СТЕ>

=<ПЕНЬ ИХ >

=<ЗАЩИТЫ**>

Заполняем 13 матриц с маршрутами 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1

Получим шифртекст путём расстановки символов в соответствии с маршрутами.

=<ФНЕНКОДИЛСОАЦИНЬДЫН_ТЬНАТТСЭХ__ОСЕРУАТП_ТЯЛСДОВАЙНАЫЕМД_М_ЫНИ_ПОДЕЕРЛЯЩЮ_ТЙИРЕУБУЮМЕ_СЕТНЬЕП_И_ХЩИАЗТЫ**>

Разобьем на блоки шифртекст.

=<ФНЕНКО ДИЛСОА ЦИНЬДЫ Н_ТЬНА ТТСЭХ_ _ОСЕРУ АТП_ТЯ ЛСДОВА ЙНАЫЕМ Д_М_ЫН И_ПОДЕ ЕРЛЯЩЮ _ТЙИРЕ УБУЮМЕ _СЕТНЬ ЕП_И_Х ЩИАЗТЫ **>

Задание №3

Зашифровать заданное слово T₀ c помощью заданной матрицы-ключа А, а затем расшифровать зашифрованное слово.

Т₀=МЮЗИКЛ

А=  

.Определим числовой эквивалент исходного слова как последовательность соответствующих порядковых номеров букв слова :

=<13, 31, 8, 9, 11, 12>

.Разобьём  на два вектора  и

. Умножим матрицу А на векторы  и :

5.      Зашифрованное слово запишем в виде последовательности чисел

=<279, 86, 397, 203, 62, 213>.

Расшифруем текст.

.Вычислим определитель IAI=65

.Определим присоединённую матрицу , каждый элемент которой является алгебраическим дополнением элемента  матрицы А:

3.Получим транспонированную матрицу

.Вычислим обратную матрицу  по формуле:

=,

В результате вычислений обратная матрица имеет вид:

.Определим векторы  и :

;

6.Получим числовой эквивалент расшифрованного слова:

=<13, 31, 8, 9, 11, 12>, который заменяется символами, в результате получается исходное слово

<МЮЗИКЛ>

Задание №4

Выполнить шифрование и расшифрование в асимметричной криптосистеме RSA заданного сообщения при заданных значениях простых p и q, а также открытого ключа е.

p=53, q=107, e=97

Сообщение: 663 487 195 324 672 817

1.

. Найдём секретный ключ  в результате решения сравнения:

 ,   .

Воспользуемся расширенным алгоритмом Евклида:

 97=5512*0+97,

 5512=97*56+80,

 97=80*1+17,

 80=17*4+12,

 17=12*1+5,

 12=5*2+2

  5=2*2+1

  2=1*2+0.

к=7

В самом деле

  ,

Следовательно, d=2273.

.        Разобьём сообщение на блоки m_i, которые должны иметь длину, меньшую, чем п= pq = 53^.107 = 5671.

, , , , ,

.        Затем шифруем блоки:

3383

2846

1846

Получим криптограмму: С=() =1612 2911 3383 2846 1846 4354

     .

. Для дешифрования нужно выполнить возведение в степень, используя ключ дешифрования d, т.е.

Задание №5

Сформировать и проверить ЭЦП Эль Гамаля при заданных начальных условиях: Р-простое целое число, G-целое число, Х -секретный ключ.

P=31, G=3, X=6

Вычисляем значение открытого ключа:

Y = G^X mod P = 3⁶ mod 31 = 16.

Предположим, что исходному сообщению M соответствует хэш-значение m = 1.

Для того, чтобы вычислить цифровую подпись под сообщением M, имеющем хэш-значение m = 1, сначала выберем случайное целое число K = 7. Убедимся, что числа K и (P - 1) являются взаимно простыми. Действительно,

НОД (7, 30) = 1.

Далее вычисляем элементы a и b подписи:

a = G^K mod P = 3⁷ mod 31 = 17,

элемент b определяем, используя расширенный алгоритм Евклида:

m = (X * a + K * b) (mod (P - 1)).

При m = 1, a = 17, X = 6, K = 7, P = 31 получаем

1 = (6 * 17 + 7 * b)(mod 30)

или

* b º - 101 (mod 30).

Решая сравнение, получаем b = 7. Цифровая подпись представляет собой пару: а = 17, b = 7.

Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 16, получатель вычисляет хэш-значение для сообщения M: m = 5, а затем вычисляет два числа:

1) Y^aa^b (mod P) = 16¹⁷ * 17⁷ (mod 31) =26;

) G^m (mod P) = 3⁵ (mod 31) =26.

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Задание №6

В симметричной криптографической системе реализовать алгоритм открытого распределения ключей Диффи-Хеллмана и вычислить общий секретный ключ K при заданных начальных условиях: N -модуль, g -примитивный элемент, К_а и К_в -секретные ключи пользователей А и В соответственно.

N=59

g=37

К_а=19

К_в=31

Для того, чтобы иметь общий секретный ключ К, пользователи А и В сначала вычислим значения частных открытых ключей:

y_A = (mod N)= 37¹⁹(mod 59) = 2, _В = (mod N)= 37³¹(mod 59) = 47

После того, как пользователи А и В обменяются своими значениями y_A и y_В, они вычисляют общий секретный ключ

К =(mod N)=(mod N)= 47¹⁹(mod 59)= 2³¹ (mod 59)= =37^19*31 (mod 59)= 55.

Кроме того, они находят секретный ключ расшифрования, решая следующее сравнение:

К * К* º 1 (mod N -1),

* К* º 1 (mod 58),

откуда К* = 19.