Задание 1.1. Несимметричное шифрование – дешифрование

Введение

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

Курсовая работа посвящена изучению систем шифрования с закрытым ключом. Задание №1 посвящено шифрованию с закрытым ключом. Рассматривается алгоритм RSA, а также предлагаются расчеты по электронной подписи с использованием хеш-функции.

Задание №2 посвящено асимметричному шифрованию или шифрованию с открытым ключом. Рассматриваются алгоритмы Диффи–Хелмана, Шамира и Эль-Гамаля.

Исследование симметричных и ассиметричных методов шифрования

Целью курсовой работы является ознакомление студентов с математической основой построения систем защиты информации в телекоммуникационных системах - методами криптографии.

Задание № 1

Задание 1.1. Несимметричное шифрование – дешифрование

Зашифровать информацию по методу RSA для последующей передачи.

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

Вариант задания определяется последними цифрами номера студенче-ского билета. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма числа р и q.

Таблица 1.1 - Исходные данные:

Продолжение таблицы 1.1

Методические указания к решению задания 1.1

Одним из наиболее распространенных методов несимметричного шифрования - дешифрования является метод шифрования с открытым ключом, в котором используется алгоритм RSA.

Несмотря на довольно большое число различных СОК (система с открытым ключом), наиболее популярна – криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.

Возможность, гарантированно оценить защищенность алгоритма RSA стала одной из причин популярности этой СОК на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).

Рассмотрим математические результаты, положенные в основу этого алгоритма.

Теорема 1. (Малая теорема Ферма.)

Если р – простое число, то

x^p-1 = 1(mod p) (1)

для любого х, простого относительно р, и

x^p = x(mod p) (2)

для любого х.

Доказательство. Достаточно доказать справедливость уравнений (1) и (2) для x^p. Проведем доказательство методом индукции.

Очевидно, что уравнение (3) выполняется при х=0 и 1.

Далее

x^p = (x –1 + 1)^p = C(p,j)(x –1)^j = (x –1)^p + 1(mod 2),

так как C(р,j)=0(mod р) при 0<j<р.

С учетом этого неравенства и предложений метода доказательства по индукции, теорема доказана.

Определение. Функцией Эйлера φ(n) называется число положительных целых, меньших n и простых относительно n.

Таблица 1.2 - Исходные данные:

Теорема 2. Если n = рq, (р и q – отличные друг от друга простые числа), то

φ(n)=(р-1)(q-1).

Теорема 3. Если n = рq, (р и q - отличные друг от друга простые числа) и х – простое относительно р и q, то

x^φ(n) = 1(mod n).

Следствие. Если n = рq, (р и q - отличные друг от друга простые числа) и е простое относительно (n), то отображение

E_в,n : xx^в(mod n)

является взаимно однозначным на Z_n.

Очевиден и тот факт, что если е – простое относительно f(n), то существует целое d, такое, что

ed ≡ 1 (mod φ(n)). (3)

На этих математических фактах и основан популярный алгоритм RSA.

Пусть n = рq, где р и q – различные простые числа. Если e и d удовлетворяют уравнению, то отображения Еe,n и Еd,n являются инверсиями на Zn. Как Еe,n, так и Еd,n легко рассчитываются, когда известны e, d, р, q.

Если известны e и n, но р и q неизвестны, то Еe,n представляет собой одностороннюю функцию; нахождение Еd,n по заданному n равносильно разложению n. Если р и q – достаточно большие простые, то разложение n практически неосуществимо. Это и заложено в основу системы шифрования RSA.

Шифросистема RSA.

Система RSA в настоящее время является наиболее распространенной системой шифрования с открытым ключом.

Пусть n = pq – целое число, представляемое в виде произведения двух больших простых чисел p, q. Числа e и d, определяющие алгоритмы шифрования и расшифрования соответственно, должны отвечать условию

ed ≡ (mod φ(n)), (1)

где φ(n) = (p-1)(q-1) – значение функции Эйлера от числа n.

Пусть k = (n,p,q,e,d) – выбранный ключ, состоящий из открытого ключа k1 = (n,e) и секретного ключа k2 = (n,p,q,d).

Пусть M – блок открытого текста и C – соответствующий блок шифрованного текста. Тогда правила шифрования и расшифрования определяются формулами:

С = E_k (M) =M^e (mod n), D_k(C) = C^d (mod n). (2)

Заметим, что в соответствии с (2) D_k(C) = M.

При нахождении значений e и d, удовлетворяющих условию (1), значение e обычно задают таким образом, чтобы оно было взаимнопростым с φ(n), а значение d определяют из уравнения

φ(n)x + ed = 1. (3)

В общем случае уравнение (3) имеет вид ax + by = c (здесь a = φ(n), b = e, y = d) и называется Диафантовым уравнением.

Решение этого уравнения

y = (–1)^μ · a_μ-1 · x = (–1)^μ+1 · b _μ-1 (4)

можно получить с помощью разложения отношения a/b в цепную дробь:

,

где μ – порядок цепной дроби, т.е. индекс коэффициента дроби, у которого остаток равен нулю,

(5)

а для всех членов, начиная с третьего справедливо

(6)

Таким образом, для решения уравнения (3) необходимо представить отношение a/b в виде цепной дроби, определить при этом значения r₀, r₁…r_μ и μ. Потом в соответствии с (4) – (6) определяются значения a_i, b_i, а также x и y.

Пример.

Зашифруем аббревиатуру RSA, используя p = 17, q = 31. Для этого вычислим n = pq = 527 и μ(n) = (p-1)(q-1) = 480. Выберем далее в качестве e число, взаимно простое с μ(n), например, e = 7. С помощью цепных дробей найдем целые числа x и y, удовлетворяющие соотношению μ(n)x + ey = 1. Запишем 480x + 7y = 1

Следовательно,

μ = 3, a₀ = 68, b₀ = 1, a₁ = 69, a₂ = 1·69 + 68 = 137, b₂ = 1·1 + 1 = 2.

Таким образом, x = –2, y = –137.

Поскольку

–137 (mod 480) = 343, то d = 343.

Проверка

7 · 343 = 2401 = 1(mod 480).

Теперь представим данное сообщение в виде последовательности чисел, содержащихся в интервале 0…526. Для этого буквы R, S и A закодируем пятимерными двоичными векторами, воспользовавшись двоичной записью их порядковых номеров в алфавите:

R = 18 = (10010), S = 19 (10011), A = 1 (00001).

Тогда RSA = (100101001100001). Укладываясь в заданный интервал 0…526, получаем следующее представление:

RSA = (100101001), (100001) = (M₁ = 297, M₂ = 33).

Далее последовательно шифруем M₁ и M₂:

C₁ = E_k (M₁) = M₁^в = 297⁷ (mod 527) = 474.

При этом мы воспользовались тем, что

т.е. 297⁷ = ((297²)³297)(mod 527) = ((200³(mod 527)297)mod 527),

C₂ = E_k(M₂) = M₂^в = 33⁷(mod 527) = 407.

В итоге получаем шифротекст: С₁ = 474, С₂ = 407.

При расшифровании нужно выполнить следующую последовательность действий. Во-первых, вычислить

D_k (C₁) = C₁^d = 33⁷ (mod 527) = 474³⁴³ (mod 527).

Отметим, что при возведении в степень, удобно воспользоваться тем, что 343 = 256 + 64 + 16 + 4 + 2 + 1. На основании этого представления получаем:

474²(mod 527) = 174, 474⁴(mod 527) = 237,

474⁸(mod 527) = 307, 474¹⁶(mod 527) = 443,

474³²(mod 527) = 205, 474⁶⁴(mod 527) = 392,

474¹²⁸(mod 527) = 307, 474²⁵⁶(mod 527) = 443,

в силу чего

474³⁴³(mod 527) = (443×392×443×237×174×474)(mod 527) = 297,

Аналогично

407³⁴³(mod 527) = 33.

Возвращаясь к буквенной записи, получаем после расшифрования RSA.

Произвести генерацию закрытого ключа используя расширенный алгоритм Эвклида, подробно описанный в алгоритме Шамира п.2.2.

Поиск по сайту: