Криптоанализ: методы вскрытия шифров¶

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

¶Классификация атак

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

• Атака на основе шифртекста — аналитику известны только зашифрованные сообщения.
• Атака на основе известного открытого текста — есть пары «открытый текст — шифртекст».
• Атака на основе подобранного открытого текста — противник может получать шифртексты для выбранных им сообщений.
• Атака на основе подобранного шифртекста — аналитик имеет доступ к расшифровке выбранных блоков.
• Атаки по сторонним каналам — используют утечки через время работы, энергопотребление, электромагнитное излучение.

¶Исторические методы

До появления вычислительной техники криптоанализ опирался на статистику и лингвистику.

Частотный анализ — сопоставление частот символов шифртекста с частотами букв языка. Впервые применён арабским учёным аль-Кинди в IX веке для вскрытия моноалфавитных шифров. Устойчив против простой замены, но теряет эффективность при полиалфавитных системах.

Метод Касиски (1863) — определяет длину ключа шифра Виженера через поиск повторяющихся последовательностей и вычисление наибольшего общего делителя расстояний между ними.

Криб — предположение о фрагменте открытого текста, проверяемое по шифртексту. Широко применялся при взломе немецкой машины «Энигма» в Блетчли-парке, где ключевую роль сыграли работы Алана Тьюринга и криб-метод с использованием «бомб» — электромеханических вычислителей.

¶Современный криптоанализ

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

Дифференциальный криптоанализ (Бихам и Шамир, 1990) — анализ влияния разностей пар открытых текстов на разности шифртекстов. Эффективен против DES-подобных сетей Фейстеля.

Линейный криптоанализ (Мацуи, 1993) — поиск линейных приближений, связывающих биты открытого текста, шифртекста и ключа с вероятностью, отличной от ½.

Атака «дней рождения» — поиск коллизий хеш-функций; лежит в основе практических атак на MD5 и SHA-1.

Квантовый криптоанализ — алгоритм Шора (1994) теоретически позволяет факторизовать большие числа и решать задачу дискретного логарифма за полиномиальное время, что ставит под угрозу RSA и криптографию на эллиптических кривых. Алгоритм Гровера даёт квадратичное ускорение перебора ключей.

¶Стойкость и практика

Криптостойкость оценивают по числу операций, необходимых для успешной атаки. Современные симметричные шифры (AES) считаются стойкими при длине ключа 128 бит и более. Асимметричные схемы уязвимы к атакам на математическую основу: факторизацию, дискретный логарифм, решётчатые задачи.

На практике большинство взломов происходит не через математику шифра, а через ошибки реализации: слабые генераторы случайных чисел, утечки по времени, атаки «человек посередине», социальную инженерию. Это привело к развитию постквантовой криптографии — алгоритмов, устойчивых к атакам на квантовых компьютерах.

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