Вивчення асиметричної криптографії на основі шифросистеми RSA

Лабораторна робота №9

Тема: «Вивчення асиметричної криптографії на основі шифросистеми RSA» 

Мета: вивчення асиметричної криптографії на основі шифросистеми RSA.

Теоретична  частина:

     Алгоритм  шифрування RSA відноситься до криптографічних  систем з відкритим ключем. Криптосистеми з відкритим ключем (асиметричні криптосистеми) були розроблені в другій половині сімдесятих років ХХ сторіччя. У асиметричних криптосистемах процедури прямого і зворотного криптоперетворення виконуються на різних ключах і не мають між собою очевидних і таких зв'язків, що легко простежуються, що дозволяють по одному ключу визначити інший. У такій схемі знання тільки ключа шифрування не дозволяє розшифрувати повідомлення, тому він не є секретним елементом шифру і зазвичай публікується учасником обміну для того, щоб будь-який охочий міг послати йому шифроване повідомлення.

     Принцип функціонування асиметричної  криптосистеми  полягає в наступному:

• користувач А генерує два ключі - відкритий (незасекречений)  і секретний - і передає відкритий ключ по незахищеному каналу користувачеві Б;
• користувач Б шифрує повідомлення, використовуючи відкритий ключ шифрування користувача А;
• користувач Б посилає зашифроване повідомлення користувача А по незахищеному каналу;
• користувач А отримує зашифроване повідомлення і дешифрує його, використовуючи свій секретний ключ.

     Пари { відкритий ключ; секретний ключ} обчислюються за допомогою спеціальних  алгоритмів, причому жоден ключ не може бути виведений з іншого.

     Авторами  алгоритму RSA, запропонованого в 1977 р., є Р.Рівест (Rivest), А.Шамір (Shamir) і А.Адлеман (Adleman). Надійність алгоритму грунтується на трудності факторизації (розкладання на множники) великих чисел і труднощі обчислення дискретних алгоритмів (знаходження x при відомих а, b і n з рівняння  ах = b (mod n) ).

     Алгоритм RSA складається з трьох частин: генерації ключів, шифрування і дешифрування.

    Криптосистема RSA

    Схему шифрования данных RSA, предложили в 1978г. три автора: P. Ривест (R.Rivest), А. Шамир (A. Shamir) и Л. Адлеман (L. Adleman). Схема получила свое название по первым буквам фамилий его авторов. RSA стала первой полноценной схемой с открытым ключом, так как она может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

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

      В криптосхеме RSA сообщение T и криптограмма S_T принадлежат полной системе вычетов по (mod N):

    Z_N={0, 1, 2,..., N-1)

    где:

    N=P*Q

    Здесь P и Q случайные большие простые  числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.

    Открытый  ключ К¹ выбирают случайным образом так, чтобы выполнялись условия:

    К¹– нечетное целое,

    1< К¹<φ(N),

    НОД(К¹,φ(N))=1;

    φ (N)=(P-l)(Q-l),

    где φ (N) – функция Эйлера.

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

    Далее c помощью расширенного алгоритма Евклида вычисляется секретный ключ K², такой, что K¹*K² ≡ l(mod φ(N))

    Преобразование  зашифрования определяет криптограмму S_T через пару (открытый ключ К¹, сообщение T) в соответствии со следующей формулой:

    S_T ≡ T ^K1 (mod N)

    Обращение функции S_T ≡ T ^K1 (mod N), т. е. определение значения T по известным S_T, K¹, и N практически не осуществимо при N=2⁵¹²

    Однако  обратную задачу, т. е. задачу расшифрования  криптограммы S_T, можно решить, используя пару (секретный ключ K², криптограмма S_T) по следующей формуле:

    T=(S_T) ^K2 (mod N)≡ Т ^К1*K2 (mod N) ≡T,

    т.к. К¹* К² ≡1 (mod φ(N)) ≡1.

    Таким образом, получатель закрывает секретный  ключ K² и пару чисел (P, Q), произведение которых дает значение модуля N. С другой стороны, получатель открывает значение модуля N и открытый ключ К¹.

    Противнику  известны лишь значения N и К¹. Если бы он смог разложить число N на множители P и Q, то он вычислил бы значение функции Эйлера и определил значение секретного ключа.

    Однако  разложение большого N на множители  вычислительно не осуществимо (при  условии, что длины P и Q составляют не менее 100 десятичных знаков). 

    Процедуры зашифрования и расшифрования  в схеме RSA

    Предположим, что абонент А хочет передать абоненту В сообщение в зашифрованном виде, используя схему шифрования данных RSA. В таком случае абонент А выступает в роли отправителя сообщения, а абонент В – в роли получателя.

    Как отмечалось выше, параметры шифрования в схеме RSA должен сформировать получатель сообщения, то есть абонент В. Рассмотрим последовательность действий абонента В и абонента А.

    Действия  абонента В (получателя):

    1. Выбирает два произвольных больших  простых числа Р и Q.

    2. Вычисляет значение модуля N  = Р *Q .

    3. Вычисляет функцию Эйлера φ(N ) = (Р – 1) * (Q – 1) .

    4. Выбирает случайным образом значение  открытого ключа К¹ с учетом выполнения условий:

    а) К¹– нечетное число

    б) l< К¹< φ(N ),

    в) НОД(К¹,( φ(N )) = 1 .

    5. Вычисляет значение секретного  ключа К², используя расширенный алгоритм Евклида для сравнения

    К²*К¹≡ 1 (mod φ(N ))

    т.е. К² является обратным мультипликативным элементом для К¹ по mod φ(N )

    6. Пересылает абоненту А пару  чисел (N, К¹) по незащищенному каналу.

    Действия  абонента А (отправителя):

    Если  абонент А хочет передать абоненту В сообщение Т , он выполняет следующие шаги.

    1. Разбивает исходный открытый  текст T на блоки, каждый из которых может быть представлен в виде числа T_i, причем 1 ≤ T_i  ≤ N-1, т.к. T_i Є Z_N.

    2. Зашифровывает текст, представленный  в виде последовательности чисел T_i по формуле

    S_Ti =T_i^K1 (mod N),

    и отправляет криптограмму

    S_T1, S_T2, S_T3, … S_Ti, …

    абоненту В.

    Практична частина:

    Повідомлення, яке будемо шифрувати: 250.

    р = 61, q = 31

    n = p*q=61*31 = 1891 

      

Листинг программы:

Public Class UserForm

    Dim p, q, n, phi, d, KeyE As Integer

    Dim Crypt() As String

    Dim TempText As String 

    '-----------------Нахождение простого числа-------------------------------------'

    Private Function Simple(ByVal x As Integer) As Boolean

        Dim y As Integer = 2 

        While (x / 2 >= y) And (x Mod y > 0)

            y += 1

        End While

        If x / 2 < y Then

            Simple = True

        Else

            Simple = False

        End If

    End Function 

    '-----------------Алгоритм Евклида для нахождения НОД чисел --------------------'

    Private Function GCD(ByVal a As Integer, ByVal b As Integer) As Integer

        If b = 0 Then Return a

        Return GCD(b, a Mod b)

    End Function 

    Private Function GetD() As Integer

        Randomize()

        Dim x As Integer 

        Do

            x = CInt(127 * Rnd() + 2)

        Loop Until (GCD(x, phi) = 1) And (x Mod 2) = 1

        GetD = x

    End Function 

    '-----------------Нахождение E расширенным алгоритмом Евклида-------------------'

    Private Sub FindE(ByVal a As Integer, ByVal b As Integer, ByRef x As Integer, ByRef y As Integer)