Асимметричные системы шифрования. Криптосистема rsa

1 АСИММЕТРИЧНЫЕ СИСТЕМЫ ШИФРОВАНИЯ. КРИПТОСИСТЕМА RSA

Введение

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

1. Проблема рассылки ключей. Симметричнае криптоситемы требуют наличия специального защищенного канала для передачи секретного ключа. Кроме того, при общении N пользователей необходимо пересылать N^2/2 ключей. При нарушении конфиденциальности компьютера одного пользователся злоумышленник получает доступ сразу ко всем его ключам и может начать от его имени рассылать сообщения всем адресатам, с которыми этот пользователь состоял в переписке.
2. Проблема подписи, т.е. проверки подлинности автора сообщения.

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах.

Идея криптографии с открытым ключом очень тесно связана с идеей  односторонних функций, то есть таких  функций f(x), что по известному x довольно просто найти значение f(x), тогда как определение x из f(x) сложно в смысле теории.

Но сама односторонняя функция  бесполезна в применении: ею можно  зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x) и y, можно вычислить x. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.

Алгоритмы криптосистемы  с открытым ключом можно использовать:

• Как самостоятельные средства для защиты передаваемой и хранимой информации
• Как средства распределения ключей. Обычно с помощью алгоритмов криптосистем с открытым ключом распределяют ключи, малые по объёму. А саму передачу больших информационных потоков осуществляют с помощью других алгоритмов.
• Как средства аутентификации пользователей.

 

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

Начало  асимметричным шифрам было положено в работе «Новые направления в  современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркле (англ. Ralph Merkle) о распространении  открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи — Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 и опубликован в 1978 году, его также называют загадкой Меркле.

В 1977 году учёными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского технологического института был разработан алгоритм шифрования, основанный на проблеме о разложении на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена в 1973 году Клиффордом Коксом (англ. Clifford Cocks), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании было не известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

Вообще, в основу известных асимметричных  криптосистем кладётся одна из сложных  математических проблем, которая позволяет  строить односторонние функции  и функции-лазейки. Например, криптосистемы  Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака.

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

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

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

9686	9613	7546	2206
1477	1409	2225	4355
8829	575	9991	1245
7431	9874	6951	2093
816	2982	2514	5708
3569	3147	6622	8839
8962	8013	3919	9055
1829	9451	5781	5154

В качестве открытых параметров системы были использованы числа n=1143816...6879541 (129 десятичных знаков, 425 бит, также известно как RSA-129 и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет. Однако чуть более чем через 15 лет, 3 сентября 1993 года было объявлено о старте проекта распределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (две из которых были факс-машинами). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)» («Волшебные слова — это брезгливый ягнятник»). Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

После публикации Мартина Гарднера полное описание новой криптосистемы любой  желающий мог получить, выслав по почте  запрос Рональду Ривесту, с приложенным конвертом с обратным адресом и марками на 35 центов. Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года.

Заявка  на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года, а 21 сентября 2000 года срок его действия истёк. Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации.

В 1982 году Ривест, Шамир и Адлеман организовали компанию RSA Data Security (англ.) (в настоящий  момент — подразделение EMC). В 1989 году RSA, вместе с симметричным шифром DES, упоминается в RFC 1115, тем самым  начиная использование алгоритма в зарождающейся сети Internet, а в 1990 году использовать алгоритм начинает министерство обороны США.

В ноябре 1993 года открыто публикуется версия 1.5 стандарта PKCS1 (англ.), описывающего применение RSA для шифрования и создания электронной  подписи. Последние версии стандарта также доступны в виде RFC (RFC 2313 — 1.5, 1993 год; RFC 2437 — 2.0, 1998 год; RFC 3447 — 2.1, 2002 год).

В декабре 1997 года была обнародована информация, согласно которой британский математик  Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал криптосистему аналогичную RSA в 1973 году.

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

RSA-ключи генерируются  следующим образом:

1. Выбираются два различных случайных простых числа   и   заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение  , которое называется модулем.
3. Вычисляется значение функции Эйлера от числа  :

4. Выбирается целое число   ( ), взаимно простое со значением функции  . Обычно в качестве   берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
• Число   называется открытой экспонентой (англ. public exponent)
• Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в  .
• Слишком малые значения  , например 3, потенциально могут ослабить безопасность схемы RSA.^[15]
5. Вычисляется число  , мультипликативно обратное к числу   по модулю  , то есть число, удовлетворяющее условию:

• Число   называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6. Пара   публикуется в качестве открытого ключа RSA (англ. RSA public key).

7. Пара   играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Шифрование и расшифрование

Предположим, Боб хочет послать Алисе сообщение  .

Сообщениями являются целые числа в интервале от   до  , т.е  .

Алгоритм: Взять открытый ключ   Алисы Взять открытый текст  Зашифровать сообщение с использованием открытого ключа Алисы:

Алгоритм: Принять зашифрованное сообщение  Взять свой закрытый ключ  Применить закрытый ключ для расшифрования сообщения:

 

Уравнения   и  , на которых основана схема RSA, определяют взаимно обратные преобразования множества 

Таблица -1

Этап	Описание операции	Результат операции
Генерация ключей	Выбрать два простых числа	,
	Вычислить модуль
	Вычислить функцию Эйлера
	Выбрать открытую экспоненту
	Вычислить секретную экспоненту
	Опубликовать открытый ключ
	Сохранить закрытый ключ
Шифрование	Выбрать текст для зашифровки
	Вычислить шифротекст
Расшифрование	Вычислить исходное сообщение

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

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

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

Алгоритм: Принять пару  Взять открытый ключ   Алисы Вычислить прообраз сообщения из подписи: Проверить подлинность подписи (и неизменность сообщения), сравнив   и

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

Важное свойство цифровой подписи заключается в том, что  её может проверить каждый, кто  имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона   может переслать стороне   электронный чек. После того как сторона   проверит подпись стороны   на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.