Криптоанализ (от греческого kryptós , «скрытый», и analýein , «анализировать») относится к процессу анализа информационных систем с целью понимания скрытых аспектов систем. [1] Криптоанализ используется для взлома криптографических систем безопасности и получения доступа к содержимому зашифрованных сообщений, даже если криптографический ключ неизвестен.
Помимо математического анализа криптографических алгоритмов, криптоанализ включает в себя изучение атак по побочным каналам , которые не нацелены на слабые стороны самих криптографических алгоритмов, а вместо этого используют слабые стороны их реализации.
Несмотря на то, что цель была той же, методы и приемы криптоанализа радикально изменились на протяжении истории криптографии, адаптируясь к возрастающей криптографической сложности, начиная от методов с ручкой и бумагой прошлого, через машины, такие как британские компьютеры Bombes и Colossus в Блетчли-парке во время Второй мировой войны , до математически продвинутых компьютерных схем настоящего. Методы взлома современных криптосистем часто включают решение тщательно построенных задач в чистой математике , самой известной из которых является факторизация целых чисел .
При шифровании конфиденциальная информация (называемая « открытым текстом » ) безопасно отправляется получателю отправителем, который сначала преобразует ее в нечитаемую форму ( « зашифрованный текст » ) с помощью алгоритма шифрования . Зашифрованный текст отправляется получателю по незащищенному каналу. Получатель расшифровывает зашифрованный текст, применяя обратный алгоритм дешифрования , восстанавливая открытый текст. Чтобы расшифровать зашифрованный текст, получателю требуются секретные знания от отправителя, обычно строка букв, цифр или битов , называемая криптографическим ключом . Концепция заключается в том, что даже если несанкционированное лицо получит доступ к зашифрованному тексту во время передачи, без секретного ключа он не сможет преобразовать его обратно в открытый текст.
Шифрование использовалось на протяжении всей истории для отправки важных военных, дипломатических и коммерческих сообщений, а сегодня оно широко применяется в компьютерных сетях для защиты электронной почты и интернет-коммуникаций.
Цель криптоанализа заключается в том, чтобы третья сторона, криптоаналитик , получила как можно больше информации об оригинале ( « открытом тексте » ), пытаясь «взломать» шифрование, чтобы прочитать зашифрованный текст и узнать секретный ключ, чтобы можно было расшифровать и прочитать будущие сообщения. [2] Математический метод для этого называется криптографической атакой . Криптографические атаки можно охарактеризовать несколькими способами:
Криптоаналитические атаки можно классифицировать на основе того, какой тип информации доступен злоумышленнику. В качестве базовой отправной точки обычно предполагается, что для целей анализа известен общий алгоритм ; это максима Шеннона «враг знает систему» [3] – в свою очередь, эквивалентная принципу Керкхоффса . [4] Это разумное предположение на практике – на протяжении всей истории существует бесчисленное множество примеров того, как секретные алгоритмы попадали в более широкое знание, различными способами через шпионаж , предательство и обратную разработку . (И иногда шифры были взломаны с помощью чистой дедукции; например, немецкий шифр Лоренца и японский код Purple , а также множество классических схем): [5]
Атаки также можно характеризовать по ресурсам, которые они требуют. Эти ресурсы включают: [6]
Иногда сложно точно предсказать эти величины, особенно когда атаку непрактично реализовать для тестирования. Но академические криптоаналитики, как правило, предоставляют по крайней мере предполагаемый порядок величины сложности своих атак, говоря, например, «коллизий SHA-1 сейчас 2 52 ». [7]
Брюс Шнайер отмечает, что даже вычислительно непрактичные атаки могут считаться взломами: «Взлом шифра просто означает нахождение слабого места в шифре, которое может быть использовано со сложностью, меньшей, чем грубая сила. Неважно, что грубая сила может потребовать 2 128 шифрований; атака, требующая 2 110 шифрований, будет считаться взломом... проще говоря, взлом может быть просто сертификационной слабостью: доказательством того, что шифр не работает так, как заявлено». [8]
Результаты криптоанализа также могут различаться по полезности. Криптограф Ларс Кнудсен (1998) классифицировал различные типы атак на блочные шифры в зависимости от количества и качества секретной информации, которая была обнаружена:
Академические атаки часто направлены против ослабленных версий криптосистемы, таких как блочный шифр или хэш-функция с удаленными некоторыми раундами. Многие, но не все, атаки становятся экспоненциально более сложными для выполнения по мере добавления раундов к криптосистеме, [9] поэтому возможно, что полная криптосистема будет сильной, даже если варианты с сокращенным числом раундов слабы. Тем не менее, частичные взломы, которые близки к взлому исходной криптосистемы, могут означать, что последует полный взлом; успешные атаки на DES , MD5 и SHA-1 предшествовали атакам на ослабленные версии.
В академической криптографии слабость или взлом в схеме обычно определяются довольно консервативно: это может потребовать непрактичных объемов времени, памяти или известных открытых текстов. Это также может потребовать от злоумышленника возможности делать то, что не могут многие реальные злоумышленники: например, злоумышленнику может потребоваться выбрать определенные открытые тексты для шифрования или даже попросить зашифровать открытые тексты с использованием нескольких ключей, связанных с секретным ключом . Кроме того, это может раскрыть лишь небольшой объем информации, достаточный для доказательства несовершенства криптосистемы, но слишком малый, чтобы быть полезным для реальных злоумышленников. Наконец, атака может применяться только к ослабленной версии криптографических инструментов, например, к блочному шифру с сокращенным раундом, как шаг к взлому всей системы. [8]
Криптоанализ развивался вместе с криптографией, и это состязание можно проследить через историю криптографии — новые шифры разрабатывались для замены старых сломанных конструкций, а новые криптоаналитические методы изобретались для взлома улучшенных схем. На практике они рассматриваются как две стороны одной медали: безопасная криптография требует разработки против возможного криптоанализа. [ необходима цитата ]
Хотя само слово « криптоанализ » появилось сравнительно недавно (его придумал Уильям Фридман в 1920 году), методы взлома кодов и шифров гораздо старше. Дэвид Кан отмечает в своей книге «Взломщики кодов» , что арабские ученые были первыми, кто систематически документировал криптоаналитические методы. [10]
Первое известное письменное объяснение криптоанализа было дано Аль-Кинди (ок. 801–873, также известный как «Алкиндус» в Европе), арабским энциклопедистом IX века , [11] [12] в «Рисала фи Истихрадж аль-Муамма» ( Рукопись о расшифровке криптографических сообщений ). Этот трактат содержит первое описание метода частотного анализа . [13] Таким образом, Аль-Кинди считается первым дешифровальщиком в истории. [14] Его прорывная работа была вдохновлена Аль-Халилем (717–786), который написал « Книгу криптографических сообщений» , в которой впервые использовались перестановки и комбинации для перечисления всех возможных арабских слов с гласными и без них. [15]
Частотный анализ является основным инструментом для взлома большинства классических шифров . В естественных языках некоторые буквы алфавита появляются чаще других; в английском языке « E », вероятно, будет самой распространенной буквой в любом образце открытого текста . Аналогично, диграф «TH» является наиболее вероятной парой букв в английском языке, и так далее. Частотный анализ опирается на то, что шифр не может скрыть эту статистику . Например, в простом шифре замены (где каждая буква просто заменяется другой), наиболее частая буква в шифртексте будет вероятным кандидатом на «E». Частотный анализ такого шифра, следовательно, относительно прост, при условии, что шифртекст достаточно длинный, чтобы дать достаточно репрезентативное количество букв алфавита, которые он содержит. [16]
Изобретение Аль-Кинди метода частотного анализа для взлома моноалфавитных подстановочных шифров [17] [18] было самым значительным криптоаналитическим достижением до Второй мировой войны. В работе Аль-Кинди «Рисалах фи Истихрадж аль-Муамма» описаны первые криптоаналитические методы, в том числе некоторые для полиалфавитных шифров , классификация шифров, арабская фонетика и синтаксис, и, что наиболее важно, дано первое описание частотного анализа. [19] Он также осветил методы шифрования, криптоанализ некоторых шифров и статистический анализ букв и буквенных комбинаций в арабском языке. [20] [13] Важный вклад Ибн Адлана (1187–1268) был в размере выборки для использования частотного анализа. [15]
В Европе итальянский ученый Джамбаттиста делла Порта (1535–1615) был автором плодотворной работы по криптоанализу De Furtivis Literarum Notis . [21]
Успешный криптоанализ, несомненно, повлиял на историю; способность читать предполагаемые тайные мысли и планы других может быть решающим преимуществом. Например, в Англии в 1587 году Мария, королева Шотландии, была осуждена и казнена за измену в результате ее участия в трех заговорах с целью убийства Елизаветы I Английской . Планы были обнаружены после того, как ее закодированная переписка с сообщниками была расшифрована Томасом Фелиппесом .
В Европе в XV и XVI веках идея полиалфавитного подстановочного шифра была разработана, в частности, французским дипломатом Блезом де Виженером (1523–1596). [22] Около трех столетий шифр Виженера , который использует повторяющийся ключ для выбора различных алфавитов шифрования по очереди, считался полностью безопасным ( le chiffre indéchiffrable — «неразборчивый шифр»). Тем не менее, Чарльзу Бэббиджу (1791–1871) и позднее, независимо, Фридриху Касиски (1805–1881) удалось взломать этот шифр. [23] Во время Первой мировой войны изобретатели в нескольких странах разработали роторные шифровальные машины , такие как «Энигма » Артура Шербиуса , в попытке минимизировать повторения, которые использовались для взлома системы Виженера. [24]
В Первой мировой войне взлом телеграммы Циммермана сыграл решающую роль в вовлечении Соединенных Штатов в войну. Во Второй мировой войне союзники извлекли огромную выгоду из их совместного успешного криптоанализа немецких шифров, включая машину «Энигма» и шифр Лоренца , а также японских шифров, в частности «Purple» и JN-25 . Разведке «Ультра» приписывают все, от сокращения окончания европейской войны на два года до определения окончательного результата. Войне на Тихом океане также помогла разведка «Мэджик» . [25]
Криптоанализ вражеских сообщений сыграл значительную роль в победе союзников во Второй мировой войне. Ф. У. Уинтерботэм процитировал западного верховного главнокомандующего союзными войсками Дуайта Д. Эйзенхауэра , который в конце войны описал разведку Ultra как «решающую» для победы союзников. [26] Сэр Гарри Хинсли , официальный историк британской разведки во Второй мировой войне, дал похожую оценку Ultra, заявив, что она сократила войну «не менее чем на два года, а возможно, и на четыре года»; более того, он сказал, что без Ultra неизвестно, как бы закончилась война. [27]
На практике частотный анализ опирается как на лингвистические знания, так и на статистику, но по мере усложнения шифров математика стала играть в криптоанализе более важную роль. Это изменение было особенно заметно до и во время Второй мировой войны , когда попытки взломать шифры стран Оси требовали новых уровней математической сложности. Более того, автоматизация была впервые применена к криптоанализу в ту эпоху с польским устройством Bomba , британским Bombe , использованием оборудования с перфокартами и в компьютерах Colossus — первых электронных цифровых компьютерах, управляемых программой. [28] [29]
С обратными машинными шифрами, такими как шифр Лоренца и машина Enigma, использовавшаяся нацистской Германией во время Второй мировой войны , каждое сообщение имело свой собственный ключ. Обычно передающий оператор сообщал принимающему оператору этот ключ сообщения, передавая некоторый открытый текст и/или шифртекст перед зашифрованным сообщением. Это называется индикатором , поскольку он указывает принимающему оператору, как настроить его машину для расшифровки сообщения. [30]
Плохо спроектированные и реализованные системы индикаторов позволили сначала польским криптографам [31] , а затем британским криптографам в Блетчли-парке [32] взломать систему шифрования Enigma. Подобные плохие системы индикаторов позволили британцам определить глубины , которые привели к диагностике системы шифрования Lorenz SZ40/42 и всестороннему взлому ее сообщений без того, чтобы криптоаналитики видели шифровальную машину. [33]
Отправка двух или более сообщений с одним и тем же ключом является небезопасным процессом. Для криптоаналитика такие сообщения называются «глубинными». [34] [35] Это можно обнаружить по сообщениям, имеющим одинаковый индикатор , с помощью которого оператор-отправитель информирует оператора-получателя о начальных настройках генератора ключей для сообщения. [36]
Как правило, криптоаналитик может извлечь выгоду из выстраивания идентичных операций шифрования среди набора сообщений. Например, шифр Вернама шифрует бит-в-бит, объединяя открытый текст с длинным ключом, используя оператор " исключающее или ", который также известен как " сложение по модулю 2 " (обозначается знаком ⊕):
Расшифровка объединяет те же самые ключевые биты с зашифрованным текстом для восстановления открытого текста:
(В арифметике по модулю 2 сложение равносильно вычитанию.) Когда два таких шифртекста выровнены по глубине, их объединение устраняет общий ключ, оставляя только комбинацию двух открытых текстов:
Затем отдельные открытые тексты можно лингвистически обработать, пробуя вероятные слова (или фразы), также известные как «шпаргалки», в различных местах; правильная догадка, при объединении с объединенным потоком открытого текста, создает понятный текст из другого компонента открытого текста:
Восстановленный фрагмент второго открытого текста часто может быть расширен в одном или обоих направлениях, а дополнительные символы могут быть объединены с объединенным потоком открытого текста для расширения первого открытого текста. Работая вперед и назад между двумя открытыми текстами, используя критерий разборчивости для проверки догадок, аналитик может восстановить большую часть или все исходные открытые тексты. (Имея в глубине только два открытых текста, аналитик может не знать, какой из них соответствует какому шифротексту, но на практике это не является большой проблемой.) Когда восстановленный открытый текст затем объединяется с его шифротекстом, ключ раскрывается:
Знание ключа затем позволяет аналитику читать другие сообщения, зашифрованные тем же ключом, а знание набора связанных ключей может позволить криптоаналитикам диагностировать систему, используемую для их построения. [33]
Правительства давно осознали потенциальные преимущества криптоанализа для разведки , как военной, так и дипломатической, и создали специальные организации, занимающиеся взломом кодов и шифров других стран, например, GCHQ и NSA , организации, которые и сегодня очень активны.
Несмотря на то, что вычисления были использованы с большим эффектом в криптоанализе шифра Лоренца и других систем во время Второй мировой войны, они также сделали возможными новые методы криптографии, на порядок более сложные, чем когда-либо прежде. В целом, современная криптография стала гораздо более непроницаемой для криптоанализа, чем системы с ручкой и бумагой прошлого, и теперь, похоже, имеет преимущество перед чистым криптоанализом. [ необходима цитата ] Историк Дэвид Кан отмечает: [37]
Сегодня сотни коммерческих поставщиков предлагают множество криптосистем, которые невозможно взломать ни одним из известных методов криптоанализа. Действительно, в таких системах даже атака с использованием выбранного открытого текста , в которой выбранный открытый текст сопоставляется с его шифротекстом, не может дать ключ, который разблокирует другие сообщения. В некотором смысле, криптоанализ мертв. Но это не конец истории. Криптоанализ может быть мертв, но есть — если смешивать мои метафоры — более одного способа снять шкуру с кошки.
Кан продолжает упоминать возросшие возможности для перехвата, прослушивания , атак по сторонним каналам и квантовых компьютеров в качестве замены традиционных средств криптоанализа. В 2010 году бывший технический директор АНБ Брайан Сноу сказал, что как академические, так и правительственные криптографы «очень медленно продвигаются вперед в зрелой области». [38]
Однако любые посмертные заключения по криптоанализу могут быть преждевременными. Хотя эффективность криптоаналитических методов, используемых разведывательными службами, остается неизвестной, в современную эпоху компьютерной криптографии было опубликовано много серьезных атак как на академические, так и на практические криптографические примитивы: [39]
Таким образом, хотя лучшие современные шифры могут быть гораздо более устойчивы к криптоанализу, чем Энигма , криптоанализ и более широкая область информационной безопасности остаются довольно активными. [40]
Асимметричная криптография (или криптография с открытым ключом ) — это криптография, которая основана на использовании двух (математически связанных) ключей: одного закрытого и одного открытого. Такие шифры неизменно опираются на «жесткие» математические проблемы как на основу своей безопасности, поэтому очевидным пунктом атаки является разработка методов решения проблемы. Безопасность двухключевой криптографии зависит от математических вопросов таким образом, каким криптография с одним ключом обычно не зависит, и наоборот, связывает криптоанализ с более широкими математическими исследованиями новым способом. [ необходима цитата ]
Асимметричные схемы разрабатываются вокруг (предполагаемой) сложности решения различных математических задач. Если можно найти улучшенный алгоритм для решения задачи, то система ослабевает. Например, безопасность схемы обмена ключами Диффи–Хеллмана зависит от сложности вычисления дискретного логарифма . В 1983 году Дон Копперсмит нашел более быстрый способ нахождения дискретных логарифмов (в определенных группах), и тем самым потребовал от криптографов использовать более крупные группы (или различные типы групп). Безопасность RSA зависит (отчасти) от сложности целочисленной факторизации — прорыв в факторизации повлиял бы на безопасность RSA. [41]
В 1980 году можно было разложить на множители сложное 50-значное число за счет 10 12 элементарных компьютерных операций. К 1984 году уровень развития алгоритмов факторизации достиг точки, когда 75-значное число можно было разложить на множители за 10 12 операций. Достижения в области вычислительной техники также означали, что операции можно было выполнять намного быстрее. Закон Мура предсказывает, что скорость компьютеров будет продолжать расти. Методы факторизации могут продолжать делать это, но, скорее всего, будут зависеть от математической проницательности и креативности, ни то, ни другое никогда не было успешно предсказано. Были разложены на множители 150-значные числа того типа, которые когда-то использовались в RSA. Усилия были больше, чем указано выше, но не были необоснованными на быстрых современных компьютерах. К началу 21-го века 150-значные числа больше не считались достаточно большим размером ключа для RSA. Числа, состоящие из нескольких сотен цифр, все еще считались слишком сложными для разложения на множители в 2005 году, хотя методы, вероятно, будут продолжать совершенствоваться с течением времени, требуя увеличения размера ключа или использования других методов, таких как криптография на основе эллиптических кривых . [ необходима ссылка ]
Еще одной отличительной чертой асимметричных схем является то, что, в отличие от атак на симметричные криптосистемы, любой криптоанализ имеет возможность использовать знания, полученные из открытого ключа . [42]
Квантовые компьютеры , которые все еще находятся на ранних стадиях исследований, имеют потенциальное применение в криптоанализе. Например, алгоритм Шора может факторизовать большие числа за полиномиальное время , фактически взламывая некоторые широко используемые формы шифрования с открытым ключом. [43]
Используя алгоритм Гровера на квантовом компьютере, можно сделать поиск ключа методом перебора квадратично быстрее. Однако этому можно противостоять, удвоив длину ключа. [44]
Аль-Кинди считается первым взломщиком кодов
