Криптология

   Криптоло́гия (от др.-греч. κρυπτός — скрытый и λόγος — слово) — наука, занимающаяся методами шифрования и дешифрования. Криптология состоит из двух частей — криптографии и криптоанализа. Криптография занимается разработкой методов шифрования данных, в то время как криптоанализ занимается оценкой сильных и слабых сторон методов шифрования, а также разработкой методов, позволяющих взламывать криптосистемы.

   Слово «криптология» (англ. cryptology) встречается в английском языке с XVII века, и изначально означало «скрытность в речи»; в современном значении было введено американским учёным Уильямом Фридманом и популяризовано писателем Дэвидом Каном.

   Криптография

   Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений

   Криптогра́фия (от др.-греч. κρυπτός —скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.

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

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

   Криптография — одна из старейших наук, ее история насчитывает несколько тысяч лет.

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

   Первый  период (приблизительно с 3-го тысячелетия  до н. э.) характеризуется господством моноалфавитных шифров (основной принцип — замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Второй период (хронологические рамки — с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) — до начала XX века) ознаменовался введением в обиход полиалфавитных шифров. Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.

   Роторная  шифровальная машина Энигма, разные модификации которой использовались германскими войсками с конца 1920-х годов до конца Второй мировой войны

   Четвертый период — с середины до 70-х годов XX века — период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам — линейному и дифференциальному криптоанализам. Однако, до 1975 года криптография оставалась «классической», или же, более корректно, криптографией с секретным ключом.

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

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

   Современная криптография

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

• симметричные DES, AES, ГОСТ 28147-89, Camellia, Twofish, Blowfish, IDEA, RC4 и др.;
• асимметричные RSA и Elgamal (Эль-Гамаль);
• хэш-функций MD4, MD5, MD6, SHA-1, SHA-2, ГОСТ Р 34.11-94.

   Во многих странах приняты национальные стандарты шифрования. В 2001 году в США принят стандарт симметричного шифрования AES на основе алгоритма Rijndael с длиной ключа 128, 192 и 256 бит. Алгоритм AES пришёл на смену прежнему алгоритму DES, который теперь рекомендовано использовать только в режиме Triple DES. В Российской Федерации действует стандарт ГОСТ 28147-89, описывающий алгоритм блочного шифрования с длиной ключа 256 бит, а также алгоритм цифровой подписи ГОСТ Р 34.10-2001. 

   Криптоанализ (от др.-греч. κρυπτός — скрытый и анализ) — наука о методах получения исходного значения зашифрованной информации, не имея доступа к секретной информации (ключу), необходимой для этого. В большинстве случаев под этим подразумевается нахождение ключа. В нетехнических терминах, криптоанализ есть взлом шифра (кода). Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году.

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

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

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

   Классический криптоанализ

   Хотя  понятие криптоанализ было введено  сравнительно недавно, некоторые методы взлома были изобретены десятки веков назад. Первым известным письменным упоминанием о криптоанализе является «Манускрипт о дешифровке криптографических сообщений», написанный арабским учёным Ал-Кинди ещё в 9 веке. В этом научном труде содержится описание метода частотного анализа.

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

   В период XV-XVI веков в Европе создавались  и развивались полиалфавитные шифры замены. Наиболее известным является шифр французского дипломата Блеза де Виженера, в основу которого легло использование последовательности нескольких шифров Цезаря с различными значениями сдвига. На протяжении трёх веков Шифр Виженера считался полностью криптографически устойчивым, пока в 1863 году Фридрих Касиски не предложил свою методику взлома этого шифра. Основная идея метода Касиски заключается в следующем: если в открытом тексте между двумя одинаковыми наборами символов находится такой блок текста, что его длина кратна длине ключевого слова, то эти одинаковые наборы символов открытого текста при шифровании перейдут в одинаковые отрезки шифротекста. На практике это означает то, что при наличии в шифротексте одинаковых отрезков длиной в три и больше символов, велика вероятность того, что эти отрезки соответствуют одинаковым отрезкам открытого текста. Как применяется метод Касиски: в шифротексте ищутся пары одинаковых отрезков длины три или больше, затем вычисляется расстояние между ними, то есть количество символов, разделяющих стартовые позиции парных отрезков. В результате анализа всех пар одинаковых отрезков мы получим совокупность расстояний d₁, d₂, d₃,… Очевидно, что длина ключевого слова будет делителем для каждого из расстояний и, следовательно, для их наибольшего общего делителя.

   Следующий этап развития криптоанализа связан с изобретением роторных шифровальных машин таких как, например, изобретённая Артуром Шербиусом Энигма. Целью таких устройств было минимизировать количество повторяющихся отрезков шифротекста, статистика появления которых использовалась при взломе шифра Виженера. Польским криптоналитикам удалось построить прототип дешифровальной машины для версии Энигмы, используемой Нацистской Германией. Машина получила название "Бомба" за то, что при работе издавала звуки похожие на тиканье часов. Позже она была доработана и взята на вооружение английскими криптоаналитиками.

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

   По  мере развития новых методов шифрования математика становилась всё более и более значимой. Так, например, при частотном анализе криптоаналитик должен обладать знаниями и в лингвистике, и в статистике. В то время как теоретические работы по криптоанализу Энигмы выполнялись преимущественно математиками, например, Аланом Матисоном Тьюрингом. Тем не менее благодаря всё той же математике криптография достигла такого развития, что количество необходимых для взлома элементарных математических операций стало достигать астрономических значений. Современная криптография стала гораздо более устойчивой к криптоанализу, чем некогда используемые, устаревшие методики, для взлома которых было достаточно ручки и листа бумаги. Может показаться, что чистый теоретический криптоанализ не способен более эффективно взламывать современные шифры. Тем не менее историк Дэвид Кан в своей заметке к 50-ой годовщине Агентства национальной безопасности пишет:

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

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

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

• В 1998 было обнаружена уязвимость к атакам на основе шифротекста у блочный шифр MADRYGA, предложенный ещё в 1984, но не получивший широкого распространения.
• Целая серия атак со стороны научного сообщества, многие из которых были целиком практическими, буквально уничтожила блочный шифр FEAL, предложенный как замена DES в качестве стандартного алгоритма шифрования, но также не получивший широкого распространения
• Также было установлено, что при помощи широко доступных вычислительных средств поточные шифры A5/1, A5/2, блочный шифр CMEA, и стандарт шифрования DECT, используемые для защиты мобильной и беспроводной телефонной связи, могут быть взломаны за считанные часы или минуты, а порою и в режиме реального времени.
• Атака методом грубой силы помогла взломать некоторые из прикладных систем защиты, например, CSS— систему защиты цифрового медиаконтента на DVD-носителях.

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

   Методы криптоанализа

   Брюс Шнайер выделяет 4 основных и 3 дополнительных метода криптоанализа, предполагая знание криптоаналитиком алгоритма шифра:

   Основные  методы криптоанализа:

1. Атака на основе шифротекста
2. Атака на основе открытых текстов и соответствующих шифротекстов
3. Атака на основе подобранного открытого текста (возможность выбрать текст для шифрования)
4. Атака на основе адаптивно подобранного открытого текста

   Дополнительные  методы криптоанализа:

1. Атака на основе подобранного шифротекста
2. Атака на основе подобранного ключа
3. Бандитский криптоанализ

   Основные методы криптоанализа

   Атаки на основе шифротекста

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

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

   Атака на основе открытых текстов и соответствующих шифротекстов

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

   Тогда существуют два варианта постановки задачи:

1. Найти ключ, использованный для преобразования открытого текста в шифротекст
2. Создать алгоритм, способный дешифровать любое сообщение, закодированное с помощью этого ключа

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

   В случае взлома переписки можно сделать  предположение, что письмо имеет  структуру типа:

• «Приветствие»
• «Основной текст»
• «Заключительная форма вежливости»
• «Подпись»

   Следовательно, атака может быть организована путём подбора различных видов «Приветствия» (например, «Здравствуйте!», «Добрый день» и т. д.) и/или «Заключительной формы вежливости» (таких как «С уважением», «Искренне Ваш» и т. п.). Легко заметить, что данная атака сильнее атаки на основе одного лишь шифротекста.

   Атака на основе подобранного открытого текста

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

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

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

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

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

   Атаки на основе адаптивно подобранного открытого текста

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

   Атака на основе подобранного шифротекста

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

   Сжато сформулировать эту задачу можно  таким образом:

   Дано: С₁, P₁=D_k(С₁), С₂, P₂=D_k(С₂), С₃, P₃=D_k(С₃), …, С_n, P_n=D_k(С_n),

   где С_n — n-ый имеющийся шифротекст, P_n — соответствующий С_n открытый текст, а D_k — функция дешифрования при помощи ключа k.

   Найти: используемый ключ шифрования k.

   Интересным  может быть тот факт, что атака  на основе подобранного шифротекста  также может носить название «Атаки в обеденное время» (lunchtime attack) или  «Ночной атаки» (midnight attack). Скажем, в  названии «Атаки в обеденное время» отражается тот факт, что легитимный пользователь может оставит свой компьютер с функцией дешифрования без присмотра на время обеда, а криптоаналитик может этим воспользоваться.

   Атака на основе подобранного ключа

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

   Бандитский криптоанализ

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