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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Безопасность цепи зависит от самого слабого звена: чем оно надежнее, тем цепь прочнее. В хорошей криптосистеме должны быть досконально проверены и алгоритм, и протокол, и ключи, и все остальное. Если криптографический алгоритм достаточно стоек, а генератор случайных чисел, используемый для создания ключей, никуда не годится, любой достаточно опытный криптоаналитик в первую очередь обратит свое внимание именно на него. Если удастся улучшить генератор, но не будут зачищаться ячейки памяти компьютера, после того как в них побывал сгенерированный ключ, грош цена такой безопасности. Если используются стойкий криптографический алгоритм и действительно случайные ключи, которые аккуратно стираются из памяти компьютера после того, как они были использованы, но перед шифрованием файл, в котором вместе с вашим адресом и фамилией указаны все ваши доходы за текущий год, был по ошибке отправлен электронной почтой в налоговую службу, то зачем, спрашивается, вам понадобились и стойкий алгоритм, и случайные ключи, и зачистка компьютерной памяти в придачу?!

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

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

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

В 1976 г. У. Диффи и М. Хеллманом [DH76] был предложен новый тип криптографической системы - система с открытым ключом [public key cryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.

С появлением систем с открытым ключом понятие о защите информации, а вместе с ним функции криптографии значительно расширились. Если раньше основной задачей криптографических систем считалось надежное шифрование информации, в настоящее время область применения криптографии включает также цифровую подпись (аутентификацию), лицензирование, нотаризацию (свидетельствование), распределенное управление, схемы голосования, электронные деньги и многое другое (см. [BFS91], ч.7, [S94], ч.1). Наиболее распространенные функции криптографических систем с открытым ключом - шифрование и цифровая подпись, причем роль цифровой подписи в последнее время возросла по сравнению с традиционным шифрованием: некоторые из систем с открытым ключом поддерживают цифровую подпись, но не поддерживают шифрование.

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

Из-за особенностей алгоритмов, лежащих в основе систем с открытым ключом, их быстродействие при обработке единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. А затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа - полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция (дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом.

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

Система RSA

В 1978 г. Р. Ривест, А. Шамир и Л. Адлеман [RSA78] создали первую криптосистему с открытым ключом для шифрования и цифровой подписи, получившую название RSA (по первым буквам фамилий авторов). Система описывается в терминах элементарной теории чисел. Ее надежность обуславливается практической неразрешимостью задачи разложения большого натурального числа на простые множители. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита - безусловно надежным. Длина подписи в системе RSA совпадает с длиной ключа.

Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, а также задачи разложения на множители к классу NP-полных задач, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов.

Идея криптосистемы с открытым ключом

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

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

Понять идеи и методы криптографии с открытым ключом помогает следующий пример -- хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции f(ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Имя f(имя_пароль)

АЛИСА РОМАШКА

БОБ НАРЦИСС

Вход в систему теперь выглядит так:

Имя: АЛИСА

Пароль: ГЛАДИОЛУС

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

В предыдущем примере используется односторонняя функция без лазейки, поскольку не требуется по зашифрованному сообщению получить исходное. В следующем примере рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:Сообщение Выбранное имя Криптотекст

К Королёв 5643452

О Орехов 3572651

Р Рузаева 4673956

O Осипов 3517289

Б Батурин 7755628

К Кирсанова 1235267

А Арсеньева 8492746

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

Примеры таких криптотекстов:

Криптотекст 1 Криптотекст 2 Криптотекст 3

1235267 5643452 1235267

3572651 3517289 3517289

4673956 4673956 4673956

3517289 3572651 3572651

7755628 7755628 7755628

5643452 1235267 5643452

8492746 8492746 8492746

Чтобы расшифровать текст, надо иметь справочник, составленный согласно возрастанию номеров. Этот справочник является лазейкой (секрет, который помогает получить начальный текст), известной только легальным пользователям. Не имея на руках копии справочника, криптоаналитик затратит очень много времени на расшифровку.[2]

Схема шифрования с открытым ключом

Пусть K -- пространство ключей, а e и d -- ключи шифрования и расшифрования соответственно. Ee -- функция шифрования для произвольного ключа eK, такая что:

Ee(m) = c

Здесь cC, где C -- пространство шифротекстов, а mM, где M -- пространство сообщений.

Dd -- функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :

Dd© = m

{Ee: eK} -- набор шифрования, а {Dd: dK} -- соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная Ee, невозможно решить уравнение Ee(m) = c, то есть для данного произвольного шифротекста cC, невозможно найти сообщение mM. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. Ee является односторонней функцией, а d -- лазейкой.[3]

Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемыми Алиса и Боб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего называют Евой.

Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).

Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: Ee(m) = c, c -- полученный шифротекст.

Боб расшифровывает шифротекст c, применяя обратное преобразование Dd, однозначно определённое значением d.

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

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

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

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

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

Начинаем с трудной задачи P. Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи P за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу -- так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.

Можно выделить легкую подзадачу P' из P. Она должна решаться за полиномиальное время, лучше, если за линейное.

«Перетасовываем и взбалтываем» P', чтобы получить задачу P'', совершенно не похожую на первоначальную. Задача P'', по крайней мере, должна выглядеть как оригинальная труднорешаемая задача P.

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

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

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

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

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

Лицо Ключ

Алиса KA

Боб KB

Кэрол KC

Дэйв KA, KB

Эллен KB, KC

Франк KA, KC

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

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

KB и KC KA

KA и KC KB

KA и KB KC

KC KA, KB

KA KB, KC

KB KA, KC

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

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

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

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

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

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

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

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

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

Во сколько раз сложнее разложить на множители 512-битовое число

1983 71 > 20 000 000

1985 80 > 2 000 000

1988 90 250 000

1989 100 30 000

1993 120 500

1994 129 100

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

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

Особенности системы

Применение

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

Как самостоятельные средства для защиты передаваемой и хранимой информации

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

Как средства аутентификации пользователей.

Преимущества

Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу.

В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный.

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

В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Недостатки

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

Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.[8]

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

криптография шифрование информация ключ

Длина симметричного ключа, бит Длина несимметричного ключа, бит

56 384

64 512

80 768

112 1792

128 2304

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

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

Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.

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

Размещено на Allbest