на тему: «Цифровые подписи на базе RSA»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Институт компьютерных технологий и информационной безопасности

Кафедра систем автоматизированного проектирования

ДОКЛАД

на тему: «Цифровые подписи на базе RSA»

по курсу: «ЗИ»

Выполнил студент гр. КТбо3-10:

Волков Артем Олегович

Проверил доц. кафедры САПР:

Мелихова Оксана Аскольдовна

Таганрог 2014

Введение

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

История появления RSA

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American, с разрешения Рональда Ривеста появилось первое описание криптосистемы RSA.

Ниже на рисунке 1 приведена хронология событий.

Рисунок 1 - Хронология событий

Протокол Диффи-Хеллмана

Для того лучше понять как работает алгоритм шифрования RSA а так же цифровые подписи на его основе стоит в начале рассмотреть принцип работы протокола Диффи-Хеллмана.

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

Описание алгоритма

· Предположим существует два абонента: Алиса и Боб.

· Обоим абонентам известны некоторые общедоступные числа g и p.

Этап

· Алиса генерирует большое число - a, вычисляет сообщение A и пересылает его Бобу:

· Боб генерирует большое число - b, вычисляет сообщение B и пересылает его Алисе:

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

Этап

· Алиса на основе имеющегося у нее числа a и полученного по сети B вычисляет значение

· Боб на основе имеющегося у нее числа b и полученного по сети A вычисляет значение

Как нетрудно видеть, у Алисы и Боба получилось одно и тоже число Его они и могут использовать в качестве секретного ключа.

Алгоритм RSA

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

· Если известно x, то f(x) вычислить относительно просто

· Если известно y=f(x), то для вычисления x нет простого пути.

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

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

Далее приведем для лучшего понимания описание функции Эйлера:

Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших и взаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и . Например, для числа 24 существует 8 меньших него и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому .

Ф(8) = (1 3 5 7) == 4 для простого числа Ф(7) = (1 2 3 4 5 6) = 7 – 1 = 6.

Ниже на рисунке 2 показан алгоритм создания открытых и закрытых ключей.

Рисунок 2

Алгоритм шифровки сообщения и его дешифровка получателем (Рисунок 3).

Рисунок 3

Далее покажем пример передачи сообщения с помощью RSA. В начале получим открытые и закрытые ключи (Рисунок 4).

Рисунок 4

Оцифруем сообщение “CAB” на английском: A-1 B-2 C-3. Процесс шифровки и декодирования сообщения приведен на рисунке 5.

Рисунок 5

Алгоритм цифровой подписи

Система RSA может использоваться не только для шифрования, но и для цифровой подписи.

Предположим, что Алисе (стороне A) нужно отправить Бобу (стороне B) сообщение m, подтверждённое электронной цифровой подписью.

Алгоритм:

· Взять открытый текст m

· Создать цифровую подпись s с помощью своего секретного ключа

·

· Передать пару , состоящую из сообщения и подписи.

· Принять пару

· Взять открытый ключ Алисы

· Вычислить прообраз сообщения из подписи:

·

· Проверить подлинность подписи (и неизменность сообщения), сравнив m и m'

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

Вывод

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

Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).