Анализ стойкости криптографических систем с использованием искусственного интеллекта

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

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

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

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

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

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

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

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

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

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

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

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

Алфавит конечное множество используемых для кодирования информации знаков.

Текст упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

- алфавит Z33 – 32 буквы русского алфавита (исключая "ё") и пробел;

- алфавит Z256 – символы, входящие в стандартные коды ASCII и КОИ-8;

- двоичный алфавит Z2 = {0,1};

- восьмеричный или шестнадцатеричный алфавит.

Шифрование – процесс преобразования исходного текста, который носит также название открытого текста, в шифрованный текст.

Расшифрование – процесс, обратный шифрованию. На основе ключа шифрованный текст преобразуется в исходный.

Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k обычно называется ключом. Преобразование Tk определяется соответствующим алгоритмом и значением ключа k.

Ключ – информация, необходимая для беспрепятственного шифрования и расшифрования текстов.

Пространство ключей K – это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы подразделяются на симметричные и асимметричные (или с открытым ключом).

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

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

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

- среднее время, необходимое для успешной криптоаналитической атаки того или иного вида.

Эффективность шифрования с целью защиты информации зависит от сохранения тайны ключа и криптостойкости шифра.

1.1.1.Требования к криптографическим системам

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

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

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

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

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

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

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

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

- структурные элементы алгоритма шифрования должны быть неизменными;

- дополнительные биты, вводимые в сообщение в процессе шифрования,