Математические основы криптологии и криптографические методы и средс

на один шаг затрачивается минимальный квантовомеханический квант энергии) превзойдет массу солнца или вселенной.

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

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

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

Симметричные криптосистемы. В симметричной криптоси­ стеме отправитель и получатель сообщения используют один и тот же секретный ключ (рис. 2).

Этот ключ должен быть известен всем пользователям и требует периодического обновления одновременно у отправителя (Алиса) и получателя (Боб).

Рис. 2. Общая схема симметричного шифрования

Процесс распределения секретных ключей между абонентами обмена конфиденциальной информацией в симметричных криптоси­ стемах имеет весьма сложный характер. Имеется в виду, что переда­ ча секретного ключа нелегитимному пользователю может привести к вскрытию всей передаваемой информации. Наиболее известные симметричные криптосистемы - шифр Цезаря, шифр Вижинера, американский стандарт шифрования DES, шифр IDEA и отечествен­ ный стандарт шифрования данных ГОСТ 28147 - 89, каждый из ко­ торых будет рассмотрен подробно во второй главе.

Шифром принято называть обратимый способ преобразования информации с целью защиты ее от просмотра, в котором использует­ ся некий секретный элемент. Исходная информация в этом случае будет называться открытым текстом, а результат применения к ней шифра - закрытым текстом или шифртекстом. Если давать строгое определение, то шифр есть совокупность всех возможных крипто­ графических преобразований (их число равно числу всех возможных ключей), отображающих множество всех открытых текстов во мно­ жество всех шифртекстов и обратно.

♦Алгоритм шифрования - формальное описание шифра.

♦Шифрование - процесс преобразования открытого текста

в шифртекст с использованием ключа.

♦Дешифрование - процесс восстановления открытого текста из шифртекста.

♦Ключ-сменный элемент шифра, позволяющий сделать сам алгоритм шифрования открытым и использовать его много­ кратно, меняя лишь ключ.

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

Комбинировать можно любые методы шифрования и в любом количестве, однако на практике наибольшее распространение полу­ чили следующие комбинации:

1)подстановка + гаммирование;

2)перестановка + гаммирование;

3)гаммирование + гаммирование;

4)подстановка + перестановка.

Типичным примером комбинированного шифра является нацио­ нальный стандарт США криптографического закрытия данных DES.

Системы с открытым ключом. Криптографические системы с открытым ключом (рис. 3) используют так называемые необрати­ мые, или односторонние, функции, которые обладают следующим свойством: при заданном значении х относительно просто вычислить значение fix), однако если М =fix), то нет более простого пути для вычисления значения х.

Множеству классов необратимых функций соответствует все разнообразие систем с открытым ключом, однако не всякая необра­ тимая функция годится для использования в реальных ИС.

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

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

♦преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа;

♦определение закрытого ключа на основе открытого также должно быть невозможным при современном уровне разви­

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых сис­ тем и рекомендован МККТТ.

Все предлагаемые в настоящее время криптосистемы с откры­ тым ключом основаны на одном из следующих типов необратимых преобразований:

♦разложение больших чисел на простые множители;

♦вычисление логарифма в конечном поле;

♦вычисление корней алгебраических уравнений.

Следует отметить, что алгоритмы криптосистемы СОК можно использовать в трех назначениях:

1) как самостоятельные средства защиты передаваемых и хра­ нимых данных;

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

3) средства аутентификации пользователей (электронная под­ пись).

1.1.2. Оценка криптостойкости шифров, их программно­ аппаратных реализаций и технико-экономических показателей

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

♦число всех возможных ключей;

♦среднее время, необходимое для криптоанализа.

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

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

♦Можно ли вообще раскрыть данный шифр?

♦Если да, то насколько это трудно сделать практически?

Шифры, которые вообще невозможно раскрыть, называются аб­ солютно, или теоретически, стойкими. Существование подобных шифров доказывается теоремой К. Шеннона, однако ценой этой стойкости является необходимость использования для шифрования каждого сообщения ключа, не меньшего по размеру, чем само сооб­ щение. В большинстве случаев эта цена чрезмерна, поэтому на прак­ тике в основном используют шифры, не обладающие абсолютной стойкостью. Таким образом, наиболее употребительные схемы шиф­ рования могут быть раскрыты за конечное время или, точнее, за ко­ нечное число шагов, каждый из которых является некоторой опера­ цией над числами. Для таких схем важнейшее значение имеет поня­ тие «стойкость», определяющее практическую трудность их раскры­ тия. Количественной мерой этой трудности может служить число элементарных арифметических и логических операций, которые не­ обходимо выполнить, чтобы раскрыть шифр, т.е. для конкретного шифротекста с вероятностью, не меньшей заданной, определить со­ ответствующий открытый текст. При этом в дополнение к дешиф­ руемому массиву данных криптоаналитик может располагать блока­ ми открытых данных и соответствующих им зашифрованных данных или даже иметь возможность получить для любых выбранных им открытых данных соответствующие зашифрованные данные. В зави­ симости от перечисленных и многих других условий различают от­ дельные виды криптоанализа.

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

Моноалфавитная подстановка является наименее стойким шиф­ ром, так как при ее использовании сохраняются все статистические закономерности исходного текста. Уже при длине зашифрованного текста в 20-30 символов указанные закономерности, как правило, позволяют вскрыть исходный текст. Поэтому такое шифрование счи­ тается пригодным только для закрытия паролей, коротких сигналь­ ных сообщений и отдельных знаков.

Стойкость простой полиалфавитной подстановки, например подстановки по таблице Виженера, оценивается значением 20п, где п - число различных алфавитов, используемых для замены. При ис­ пользовании таблицы Виженера число различных алфавитов опреде­ ляется числом букв в ключевом слове. Усложнение полиалфавитной подстановки существенно повышает ее стойкость. Монофоническая подстановка может быть весьма стойкой (и даже теоретически нераскрываемой), однако строго монофоническую подстановку, в ко­ торой все символы имеют равные вероятности появления, реализо­ вать на практике трудно, а любые отклонения от монофоничности снижают реальную стойкость шифра.

Стойкость простой перестановки однозначно определяется раз­ мерами используемой матрицы. Например, при использовании мат­ рицы 16x16 число возможных перестановок достигает 1,4-1026 Та­ кое число вариантов невозможно перебрать даже с использованием современных ЭВМ. Стойкость усложненных перестановок может быть выше. Однако при шифровании перестановкой полностью со­ храняются вероятностные характеристики исходного текста, что об­ легчает криптоанализ.

Стойкость гаммирования однозначно определяется длиной пе­ риода гаммы. В настоящее время реальным становится применение бесконечной гаммы, при использовании которой теоретическая стой­ кость зашифрованного текста также будет бесконечной. Можно от­ метить, что для надежного закрытия больших массивов информации наиболее пригодны гаммирование и усложненные перестановки и подстановки.

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

Клод Шеннон в своих трудах ввел понятие стойкости шифра и показал, что существует шифр, обеспечивающий абсолютную сек­ ретность. Иными словами, знание шифртекста не позволяет против­ нику улучшить оценку соответствующего открытого текста. Им мо­ жет быть, например, шифр Виженера при использовании бесконечно длинного ключевого слова и абсолютно случайном распределении символов в этом слове. Очевидно, что практическая реализация тако­ го шифра (бесконечная случайная лента) невозможна (точнее, в большинстве случаев - экономически невыгодна), поэтому обычно рассматривают практическую стойкость необходимой для его взлома (с учетом текущего уровня развития техники). Кстати, первый пред­ ложил использовать такой шифр Вернам, но обоснование дал именно Шеннон. Абсолютно стойкий шифр - это абстрактно-математическое понятие, с практикой не имеющее почти ничего общего. Абсолютно стойкий шифр может оказаться абсолютно нестойким против таких атак, как physical attack или social engineering attack, все зависит от реализации.

Современные методы шифрования должны отвечать следую­ щим требованиям:

1.Стойкость шифра к противостоянию криптоанализу (крипто­ стойкость) должна быть такой, чтобы вскрытие его могло быть осу­ ществлено только путем решения задачи полного перебора ключей.

2.Криптостойкость обеспечивается не секретностью алгоритма шифрования, а секретностью ключа.

3.Шифртекст не должен существенно превосходить по объему исходную информацию.

4.Ошибки, возникающие при шифровании, не должны приво­ дить к искажениям и потере информации.

5.Время шифрования не должно быть большим.

6.Стоимость шифрования должна быть согласована со стоимо­ стью закрываемой информации.

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

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

Вконце 1970-х годов использование ключа длиной в 56 бит га­ рантировало, что для раскрытия шифра потребуется несколько лет непрерывной работы самых мощных по тем временам компьютеров. Прогресс в области вычислительной техники позволил значительно сократить время определения ключа путем полного перебора. Со­ гласно заявлению специалистов Агентства национальной безопасно­ сти США 56-битный ключ для DES может быть найден менее чем за 453 дня с использованием суперЭВМ Cray T3D, которая имеет 1024 узла и стоит 30 млн долл. Используя чип FRGA {Field Programmable Gate Array - программируемая вентильная матрица) стоимостью 400 долл., можно восстановить 40-битный ключ DES за пять часов. По­ тратив 10 000 долл, за 25 чипов FPGA, 40-битный ключ можно найти

всреднем за 12 мин. Для вскрытия 56-битного ключа DES при опоре на серийную технологию и затратах в 300 000 долл, требуется в сред­ нем 19 дней, а если разработать специальный чип, то - три часа. При затратах в 300 млн долл. 56-битные ключи могут быть найдены за 12 с.

Расчеты показывают, что в настоящее время для надежного закрытия информации длина ключа должна быть не менее 90 бит.

Все методы шифрования могут быть классифицированы по раз­ личным признакам. Эти методы можно подразделить на две группы: методы шифрования с симметричными ключами и системы шифро­ вания с открытыми ключами.

Первая группа включает в себя методы:

-замены - прямой замены, алгоритмов моноалфавитной замены, методы полиалфавитной замены, модифицированной матрицы шиф­ рования;

-перестановки - простая перестановка, усложненная переста­ новка по таблице, усложненная перестановка по маршрутам;

-аналитические - подразумевают применение матричной ал­

гебры;

-аддитивные (гаммирование) - предусматривают применение генераторов псевдослучайных чисел;

-комбинированные - подразумевают применение указанных выше методов в различных комбинациях.

Во второй группе выделяют системы RSA, Эль-Гамаля и крип­ тосистемы Мак-Элиса.

Для современных криптографических систем защиты процессов переработки информации сформулированы следующие общеприня­ тые требования:

-зашифрованное сообщение должно поддаваться чтению толь­ ко при наличии ключа;

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

исоответствующего ему открытого текста, должно быть не меньше общего числа возможных ключей;

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

-знание алгоритма шифрования не должно влиять на надеж­ ность защиты;