Криптография и виды шифрования

Научная основа

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

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

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

Основные  принципы построения криптосистем с  открытым ключом

1. Начинаем с трудной задачи  . Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи   за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу — так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.
2. Можно выделить легкую подзадачу   из  . Она должна решаться за полиномиальное время и лучше, если за линейное.
3. «Перетасовываем и взбалтываем»  , чтобы получить задачу  , совершенно не похожую на первоначальную. Задача   должна по крайней мере выглядеть как оригинальная труднорешаемая задача  .
4.  открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из   получить  , держится в секрете как секретная лазейка.
5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает  -задачу, первый использует секретную лазейку и решает  -задачу.

Криптография  с несколькими открытыми ключами

• В следующем примере показана схема, в которой Алиса шифрует сообщение так, что только Боб может прочитать его, и наоборот, Боб шифрует сообщение так, что только Алиса может расшифровать его.

Пусть есть 3 ключа  ,  ,  , распределенные так, как показано в таблице.

Лицо	Ключ
Алиса
Боб
Кэрол
Дэйв	,
Эллен	,
Франк	,

Тогда Алиса  может зашифровать сообщение  ключом  , а Эллен расшифровать ключами  ,  , Кэрол — зашифровать ключом  , а Дэйв расшифровать ключами  ,  . Если Дэйв зашифрует сообщение ключом  , то сообщение сможет прочитать Эллен, если ключом  , то его сможет прочитать Франк, если же обоими ключами   и  , то сообщение прочитает Кэрол. По аналогии действуют и другие участники. Таким образом, если используется одно подмножество ключей для шифрования, то для расшифрования требуются оставшиеся ключи множества. Такую схему можно использовать для n ключей.

Шифруется ключом	Расшифровывается  ключом
и
и
и
	,
	,
	,

• Теперь можно посылать сообщения группам агентов, не зная заранее состав группы.

Рассмотрим  для начала множество, состоящее из трех агентов: Алисы, Боба и Кэрол. Алисе выдаются ключи   и  , Бобу —   и  , Кэрол —   и  . Теперь, если отправляемое сообщение зашифровано ключом  , то его сможет прочитать только Алиса, последовательно применяя ключи   и  . Если нужно отправить сообщение Бобу, сообщение шифруется ключом  , Кэрол — ключом  . Если нужно отправить сообщение и Алисе и Кэрол, то для шифрования используются ключи   и  .

Преимущество  этой схемы заключается в том, что для её реализации нужно только одно сообщение и n ключей (в схеме с n агентами). Если передаются индивидуальные сообщения, то есть используются отдельные ключи для каждого агента (всего n ключей) и каждого сообщения, то для передачи сообщений всем различным подмножествам требуется  ключей.

Недостатком такой схемы является то, что необходимо также широковещательно передавать подмножество агентов (список имён может быть внушительным), которым нужно передать сообщение. Иначе каждому из них придется перебирать все комбинации ключей в поисках подходящей. Также агентам придется хранить немалый объём информации о ключах.

Криптоанализ  алгоритмов с открытым ключом

Казалось бы, что криптосистема с открытым ключом — идеальная система, не требующая безопасного канала для передачи ключа шифрования. Это подразумевало бы, что два легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению, это не так. Рисунок иллюстрирует, как Ева, выполняющая роль активного перехватчика, может захватить систему (расшифровать сообщение, предназначенное Бобу) без взламывания системы шифрования.

Рисунок 3.Криптосистема с открытым ключом и активным перехватчиком

В этой модели Ева  перехватывает открытый ключ  , посланный Бобом Алисе. Затем создает пару ключей   и  , «маскируется» под Боба, посылая Алисе открытый ключ  , который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа  , заново зашифровывает открытым ключом   Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение  , так и подменить его на ложное сообщение  . Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей.

Ещё одна форма  атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования  , анализируя его, пытается найти  . Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов, посланных лицом A лицу B.

Рисунок 4.Ассиметричная криптосистема с пассивным перехватчиком.

Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето».

 

Год	Число десятичных разрядов  в разложенном числе	Во  сколько раз сложнее разложить  на множители 512-битовое число
1983	71	> 20 млн
1985	80	> 2 млн
1988	90	250 тыс.
1989	100	30 тыс.
1993	120	500
1994	129	100

Также задачу разложения потенциально можно решить с помощью Алгоритма Шора при использовании достаточно мощного квантового компьютера.

Для многих методов  несимметричного шифрования криптостойкость, полученная в результате криптоанализа, существенно отличается от величин, заявляемых разработчиками алгоритмов на основании теоретических оценок. Поэтому во многих странах вопрос применения алгоритмов шифрования данных находится в поле законодательного регулирования. В частности, в России к использованию в государственных и коммерческих организациях разрешены только те программные средства шифрования данных, которые прошли государственную сертификацию в административных органах, в частности, в ФСБ.

 

Заключение

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

1. Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. - СПб.: СПбГИТМО(ТУ), 2002.
2. Кон П. Универсальная алгебра. - М.: Мир. – 1968
3. Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002.
4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002.