Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ

“МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И
ИНФОРМАТИКИ”

Факультет (филиал)___ВФ__________специальность (направление)___2201________

Кафедра ___ИС______________________________________________________________

Дисциплина___Основы защиты информации______________________________________



 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту (работе) на тему:

______________________________________________________
Программная реализация шифра RSA
______________________________________________________
Генерация ключей RSA
______________________________________________________



Студент______________________________11.01.07______________А.М.Циликин___

Группа___ИС-1________________ шифр______02222____________________________

Обозначение курсового проекта (работы)___________________________________

Проект (работа) защищен(а) на оценку_____________________________________


Руководитель проекта (работы)____________________________Е.В.Письменная__


Члены комиссии___________________________________________________________


_________________________________________________________________________


_________________________________________________________________________




МОСКВА 2007 г.

Дополнения 2018.

Разбирался с реализацией RSA из библиотеки avr-crypto-lib. Стало интересно, что такое dP, dQ, qInv. Могу ли я их вычислить, чтобы их значения совпали с примером из библиотеки. Получилось! Проект можно использовать для создания ключей RSA различной длины, ключи вырабатываются на JavaScript и не передаются на сервер. Более того, эту страницу можно сохранить на диск и скрипт может работать локально, без связи с Интернет. Использовать ключи, полученные в этом проекте с помощью генератора псевдослучайных чисел, не рекомендую. Весьма вероятно, что зная значение первого разряда полученного числа, можно найти остальные. Дать какие-либо рекомендации по использованию ключей, полученных в этом проекте с помощью криптографически стойкого генератора случайных чисел сложно. С одной стороны функция window.crypto.getRandomValues заявлена как надежная, с другой стороны полученные ключи могут остаться в памяти браузера и утечь каким-либо образом.

Для получения возможности вычисления вышеуказанных чисел и сравнения их с примером, в проекте сделаны следующие дополнения:

  1. Добавлен шестнадцатеричный вид записи чисел и основание. Старший первый байт, как в avr-crypto-lib. При переключении, все числа в полях ввода пересчитываются в выбранный вид.
  2. В генераторе ключей добавлено вычисление размера модуля n в битах (т.н. размер ключа RSA).
  3. Добавлено шифрование/дешифрование числа. В десятичном виде все результаты совпадают с примером в Wikipedia.
  4. Добавлено вычисление чисел dP, dQ, qInv. Эти числа нужны увеличения скорости приватного шифрования/дешифрования путем использования Китайской теоремы об остатках (Chinese remainder theorem, CRT). В самом проекте CRT не используется, числа вычисляются для avr-crypto-lib.
  5. Изменен генератор псевдослучайных чисел. Убрано изменение размера числа.
  6. Добавлено создание числа заданного размера в битах.
  7. Добавлено создание блока приватных ключевых данных для avr-crypto-lib.
  8. Добавлена возможность использования криптографически стойкого ГСЧ для создания числе p и q.

I. Программная реализация на JavaScript.

1. Выбор основания.



2. Работа с большими и простыми числами.

Введите большие числа:
число a =
число b =
число c =
Базовые операции с большими числами (приемлемая скорость при размере чисел до 10100000):

Дополнительные операции с большими числами (приемлемая скорость при размере чисел до 10500):


Генерация случайных больших чисел (приемлемая скорость при размере чисел до 101000000):
Размер числа в битах
Базовые операции с простыми числами (приемлемая скорость при размере чисел до 10200):

Результат:



3. Реализация RSA. Генерация ключей.

Укажите начальные значения для p, q и необязательно e. Это можно сделать несколькими способами:

  1. Ввести вручную
  2. Использовать криптографически нестойкий генератор случайных чисел (функция Random)
    Размер числа в битах
  3. Использовать криптографически стойкий генератор случайных чисел (функция window.crypto.getRandomValues).
    Функция может быть недоступна в системе. Кроме того, использование генератора в рамках данного проекта возможно только для BASE=65536
    Размер числа в битах * 16

ближайшее снизу к p =
ближайшее снизу к q =
ближайшее снизу к e =

Результаты:



4. Выбор режима.



В данной реализации шифра используется чистый RSA без перемежения. Более того, символы входят в блок целиком, т.е. часть символа не переходит в соседний блок. Это означает, несмотря на использование больших чисел, непригодность данной реализации для практических целей."Враг", может быть и не сможет прочесть зашифрованное послание, но может его исказить, переставив местами блоки, исключив некоторые из них, или вставив ранее перехваченные. Далее, используется очень не экономный алфавит, поэтому размер шифротекста возрастает аж в минимум 3 раза! Тем не менее, эта курсовая работа мне уже ужасно надоела и перемежение (а также контрольные суммы) здесь реализовываться не будет. УРА!!! Работа закончена!!!

5. Реализация RSA. Шифрование.

Введите числа N и E:
N =
E =
Введите открытый текст:


6. Реализация RSA. Дешифрование.

Введите числа n и e:
N =
D =
Введите шифротекст:


II. Пояснительная часть.

1. Работа с большими числами.

Основной способ работы с числом большой разрядности это представление такого числа в виде массива коэффициентов:

A = an·BASEn + an-1·BASEn-1 + ... + a0·BASE0.

Для повышения скорости работы надо брать BASE=2m, а для наглядности удобно взять BASE=10m. В данной работе можно использовать оба варианта: 1 - написание чисел в десятичном виде и BASE=105. 2 - написание чисел в шестнадцатеричном виде и BASE=216

2. Простые числа. Проверка на простоту.

После написания основных функций работы с большими числами, можно выполнить проверку большого числа на простоту. Существует два метода проверки числа на простоту. Один - пробное деление с порядком роста sqrt(n), другой - вероятностный, с порядком роста log (n). При использовании первого метода испытываемое число n пробуют делить на все числа a, которые могут являться его делителем 1<a<sqrt(n). Использовать для проверки больших чисел этот метод затруднительно, ввиду очень значительных затрат времени. Второй метод использует подходы с более высокой вероятностью того, что число, прошедшее тест является простым. Проведя тест многократнo, можно повысить вероятность до приемлемого уровня. Все тесты основаны на свойстве простых чисел, носящем название "Малая теорема Ферма":

Для любого простого числа n и натурального числа a, такого, что gcd(a,n)=1, выполняется равенство:
an-1 mod n = 1.

Для любых случайных n и a данное равенство выполняется с вероятностью 1/4. Если равенство не выполняется, то число n однозначно составное.Существуют числа, которые не являются простыми и тем не менее удовлетворяют равенству при всех значениях a. Такие числа называются числами Кармайкла (Carmichael numbers), и про них почти ничего неизвестно, кроме того, что они очень редки. Существует 255 чисел Кармайкла, меньших 100 000 000. Несколько первых - 561, 1105, 1729, 2465, 2821 и 6601. Есть варианты теста Ферма, которые обмануть невозможно. В таких тестах, подобно методу Ферма, проверка числа n на простоту ведется путем выбора случайного числа a < n и проверки некоторого условия, зависящего от n и a. Один из вариантов теста Ферма, который невозможно обмануть, называется тест Миллера-Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980). Ввиду того, что числа Кармайкла очень редки, в данной работе при генерации ключей используется тест Ферма.

3. Шифр RSA.

Шифр RSA основан на функции Эйлера. Эйлер расширил малую теорему Ферма для любого натурального n:

Для любого натурального числа n и натурального числа a, такого, что gcd(a,n)=1, выполняется равенство:
aφ(n) mod n = 1, где φ(n) - функция Эйлера.

Функцией Эйлера φ(n) называется количество чисел, меньших n и взаимно простых с n, т.е. не имеющих с n общих делителей. Эйлер не только придумал эту функцию, но вывел её значение аналитически:

Если разложить n на простые множители n = p1d1·p2d2 … pidi, то
φ(n) = n·(1-1/p1)·(1-1/p2) … (1-1/pi)

Шифр RSA очень красив и состоит из следующих шагов:

  1. Взять n = p·q, где p и q - простые числа.
    Вычислить φ(n) = (p-1)·(q-1) = n-p-q+1.
  2. Взять произвольное натуральное E, такое что gcd(E, φ(n)=1.
    Вычислить D = E-1 mod φ(n), т.е. D·E = 1 mod φ(n) = 1 + k ·φ(n)
  3. Числа n и E поместить в открытый каталог (открытый ключ).
    Число D получатель держит в секрете (закрытый ключ).
  4. Отправитель представляет исходное сообщение M в виде чисел, разбивает его на блоки Mj < n.
    Шифрует Сj = MjE mod n, отправляет в линию связи.
  5. Получатель получает шифрованное число.
    Расшифровывает Mj = CjD mod n, собирает из блоков, представляет в виде сообщения.
Математический смысл производимых действий:

С = ME mod n
M = CD mod n = (ME)D mod n = ME · D mod n = M1 + k · φ(n) mod n = M · Mk · φ(n) mod n = M · (Mφ(n))k mod n = M · 1k = M

Числа p и q нигде в алгоритме не используются, они нужны для того, чтобы зная n, нельзя было вычислить φ(n) и получить D.