Криптоанализ (от греческого kryptós — «скрытый» и analýein — «анализировать») относится к процессу анализа информационных систем с целью понять скрытые аспекты систем. [1] Криптоанализ используется для взлома систем криптографической безопасности и получения доступа к содержимому зашифрованных сообщений, даже если криптографический ключ неизвестен.
Помимо математического анализа криптографических алгоритмов, криптоанализ включает изучение атак по побочным каналам , которые не нацелены на слабые места в самих криптографических алгоритмах, а вместо этого используют слабые места в их реализации.
Несмотря на то, что цель была той же самой, методы и приемы криптоанализа радикально менялись на протяжении всей истории криптографии, адаптируясь к возрастающей сложности криптографии, начиная от бумажных методов прошлого и заканчивая такими машинами, как британские бомбы и Колоссальные компьютеры в Блетчли-парке во время Второй мировой войны , вплоть до математически продвинутых компьютерных схем настоящего. Методы взлома современных криптосистем часто включают решение тщательно сконструированных задач чистой математики , наиболее известной из которых является факторизация целых чисел .
При шифровании конфиденциальная информация (называемая « открытым текстом » ) безопасно отправляется получателю, когда отправитель сначала преобразует ее в нечитаемую форму ( « зашифрованный текст » ) с использованием алгоритма шифрования . Зашифрованный текст отправляется получателю по незащищенному каналу. Получатель расшифровывает зашифрованный текст, применяя обратный алгоритм дешифрования , восстанавливая открытый текст. Чтобы расшифровать зашифрованный текст, получателю требуются секретные знания от отправителя, обычно это строка букв, цифр или битов , называемая криптографическим ключом . Идея заключается в том, что даже если неавторизованный человек получит доступ к зашифрованному тексту во время передачи, без секретного ключа он не сможет преобразовать его обратно в открытый текст.
Шифрование использовалось на протяжении всей истории для отправки важных военных, дипломатических и коммерческих сообщений, а сегодня очень широко используется в компьютерных сетях для защиты электронной почты и интернет-коммуникаций.
Цель криптоанализа состоит в том, чтобы третья сторона, криптоаналитик , получила как можно больше информации об оригинале ( « открытом тексте » ), попыталась «взломать» шифрование, чтобы прочитать зашифрованный текст, и узнала секретный ключ, чтобы будущие сообщения могли быть прочитаны. расшифровал и прочитал. [2] Математический метод, позволяющий сделать это, называется криптографической атакой . Криптографические атаки можно охарактеризовать несколькими способами:
Криптоаналитические атаки можно классифицировать в зависимости от типа информации, которой располагает злоумышленник. В качестве базовой отправной точки обычно предполагается, что для целей анализа известен общий алгоритм ; это максима Шеннона «враг знает систему» [3] – в свою очередь, эквивалентная принципу Керкхоффса . [4] На практике это разумное предположение — на протяжении всей истории существует бесчисленное множество примеров того, как секретные алгоритмы попадали в более широкие знания, в том числе посредством шпионажа , предательства и обратного проектирования . (А иногда шифры были взломаны посредством чистой дедукции; например, немецкий шифр Лоренца и японский пурпурный код , а также множество классических схем): [5]
Атаки также можно охарактеризовать по требуемым для них ресурсам. Эти ресурсы включают в себя: [6]
Иногда трудно точно предсказать эти величины, особенно когда атаку невозможно реализовать для тестирования. Но академические криптоаналитики склонны предоставлять, по крайней мере, приблизительный порядок сложности своих атак, говоря, например, «коллизии SHA-1 сейчас 2 52 ». [7]
Брюс Шнайер отмечает, что даже непрактичные с вычислительной точки зрения атаки можно считать взломом: «Взлом шифра просто означает обнаружение слабости в шифре, которую можно использовать с меньшей сложностью, чем грубая сила. Неважно, что для грубой силы может потребоваться 2128 шифрований ; атака, требующая шифрования 2110 , будет считаться взломом... проще говоря, взлом может быть просто слабым местом сертификации: свидетельством того, что шифр не работает так, как заявлено». [8]
Результаты криптоанализа также могут различаться по полезности. Криптограф Ларс Кнудсен (1998) классифицировал различные типы атак на блочные шифры в зависимости от количества и качества обнаруженной секретной информации:
Академические атаки часто направлены против ослабленных версий криптосистемы, таких как блочный шифр или хеш-функция с удаленными некоторыми раундами. Многие, но не все, атаки становятся экспоненциально более трудными для выполнения по мере добавления раундов в криптосистему, [9] поэтому полная криптосистема может быть сильной, даже если варианты с сокращенным количеством раундов слабы. Тем не менее, частичные взломы, которые близки к взлому исходной криптосистемы, могут означать, что последует полный взлом; успешным атакам на DES , MD5 и SHA-1 предшествовали атаки на ослабленные версии.
В академической криптографии слабость или нарушение схемы обычно определяются довольно консервативно: это может потребовать непрактичного количества времени, памяти или известных открытых текстов. Это также может потребовать от злоумышленника возможности делать то, что многие злоумышленники в реальном мире не могут: например, злоумышленнику может потребоваться выбрать определенные открытые тексты для шифрования или даже попросить зашифровать открытые тексты, используя несколько ключей, связанных с секретом. ключ. Более того, он может раскрыть лишь небольшой объем информации, которого достаточно, чтобы доказать несовершенство криптосистемы, но слишком мало, чтобы быть полезным для реальных злоумышленников. Наконец, атака может применяться только к ослабленной версии криптографических инструментов, таких как блочный шифр с сокращенным циклом, как шаг к взлому всей системы. [8]
Криптоанализ развивался вместе с криптографией, и эту борьбу можно проследить через всю историю криптографии : новые шифры разрабатывались для замены старых сломанных схем, а новые криптоаналитические методы изобретались для взлома улучшенных схем. На практике они рассматриваются как две стороны одной медали: безопасная криптография требует разработки с учетом возможного криптоанализа. [ нужна цитата ]
Хотя само слово « криптоанализ » появилось относительно недавно (оно было придумано Уильямом Фридманом в 1920 году), методы взлома кодов и шифров гораздо старше. Дэвид Кан отмечает в книге «Взломщики кодов» , что арабские учёные были первыми, кто систематически документировал криптоаналитические методы. [10]
Первое известное письменное объяснение криптоанализа было дано Аль-Кинди (ок. 801–873, также известным как «Алкинд» в Европе), арабским эрудитом 9-го века , [11] [12] в «Рисала фи Истихрадж аль-Му». 'амма ( Рукопись по расшифровке криптографических сообщений ). Этот трактат содержит первое описание метода частотного анализа . [13] Таким образом, Аль-Кинди считается первым взломщиком кодов в истории. [14] На его революционную работу оказал влияние Аль-Халил (717–786), написавший «Книгу криптографических сообщений» , в которой впервые используются перестановки и комбинации для перечисления всех возможных арабских слов с гласными и без них. [15]
Частотный анализ является основным инструментом для взлома большинства классических шифров . В естественных языках одни буквы алфавита встречаются чаще других; в английском языке « E », вероятно, будет самой распространенной буквой в любом образце открытого текста . Точно так же орграф «TH» — наиболее вероятная пара букв в английском языке и так далее. Частотный анализ основан на шифре, который не может скрыть эту статистику . Например, в шифре простой замены (где каждая буква просто заменяется другой) наиболее часто встречающаяся буква в зашифрованном тексте будет вероятным кандидатом на букву «Е». Таким образом, частотный анализ такого шифра относительно прост, при условии, что зашифрованный текст достаточно длинный, чтобы дать достаточно репрезентативное количество содержащихся в нем букв алфавита. [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]
Во время Первой мировой войны взлом телеграммы Циммермана сыграл важную роль в вовлечении Соединенных Штатов в войну. Во Второй мировой войне союзники получили огромную выгоду от совместного успешного криптоанализа немецких шифров, включая машину «Энигма» и шифр Лоренца , а также японских шифров, особенно « Пурпл» и JN-25 . «Ультра» -разведке приписывают все: от сокращения окончания европейской войны на два года до определения конечного результата. Войне на Тихом океане также помогла разведка «Магия» . [25]
Криптоанализ сообщений противника сыграл значительную роль в победе союзников во Второй мировой войне. Ф. В. Уинтерботэм процитировал слова верховного главнокомандующего союзными войсками Запада Дуайта Д. Эйзенхауэра , который в конце войны описал Ультра- разведку как «решающую» для победы союзников. [26] Сэр Гарри Хинсли , официальный историк британской разведки во Второй мировой войне, дал аналогичную оценку «Ультра», заявив, что она сократила войну «не менее чем на два года, а возможно, и на четыре года»; более того, он заявил, что в отсутствие «Ультры» неизвестно, чем бы закончилась война. [27]
На практике частотный анализ в такой же степени опирается на лингвистические знания, как и на статистику, но по мере усложнения шифров математика стала играть более важную роль в криптоанализе. Это изменение было особенно очевидным до и во время Второй мировой войны , когда попытки взлома шифров Оси требовали нового уровня математической сложности. Более того, автоматизация была впервые применена к криптоанализу в ту эпоху с помощью польского устройства «Бомба» , британской «Бомбы» , использования оборудования с перфокартами , а также в компьютерах «Колосс» — первых электронных цифровых компьютерах, управляемых программой. [28] [29]
Благодаря взаимным машинным шифрам, таким как шифр Лоренца и машина «Энигма», использовавшаяся нацистской Германией во время Второй мировой войны , каждое сообщение имело свой собственный ключ. Обычно передающий оператор информировал принимающего оператора об этом ключе сообщения, передавая некоторый открытый текст и/или зашифрованный текст перед зашифрованным сообщением. Это называется индикатором , поскольку он указывает принимающему оператору, как настроить свою машину для расшифровки сообщения. [30]
Плохо спроектированные и реализованные системы индикаторов позволили сначала польским криптографам [31] , а затем британским криптографам из Блетчли-Парка [32] взломать систему шифрования «Энигма». Подобные системы с плохим индикатором позволили британцам определить глубину , что привело к диагностике шифровальной системы Лоренца SZ40/42 и полному взлому ее сообщений без того, чтобы криптоаналитики увидели шифровальную машину. [33]
Отправка двух или более сообщений с одним и тем же ключом — небезопасный процесс. Тогда для криптоаналитика сообщения называются «глубинными». [34] [35] Это может быть обнаружено по сообщениям, имеющим тот же индикатор , с помощью которого оператор-отправитель информирует оператора-получателя о начальных настройках генератора ключей для сообщения. [36]
Как правило, криптоаналитик может получить выгоду от выстраивания идентичных операций шифрования среди набора сообщений. Например, шифр Вернама шифрует путем побитового объединения открытого текста с длинным ключом с использованием оператора « исключающий или », который также известен как « сложение по модулю 2 » (обозначается ⊕):
Дешифрование объединяет те же ключевые биты с зашифрованным текстом для восстановления открытого текста:
(В арифметике по модулю 2 сложение аналогично вычитанию.) Когда два таких зашифрованных текста выровнены по глубине, их объединение устраняет общий ключ, оставляя только комбинацию двух открытых текстов:
Затем отдельные открытые тексты можно разработать лингвистически, пробуя вероятные слова (или фразы), также известные как «шпаргалки», в различных местах; правильное предположение в сочетании с объединенным потоком открытого текста создает понятный текст из другого компонента открытого текста:
Восстановленный фрагмент второго открытого текста часто можно расширить в одном или обоих направлениях, а дополнительные символы можно объединить с объединенным потоком открытого текста для расширения первого открытого текста. Работая между двумя открытыми текстами и используя критерий разборчивости для проверки предположений, аналитик может восстановить большую часть или все исходные тексты. (При наличии только двух открытых текстов аналитик может не знать, какой из них соответствует какому зашифрованному тексту, но на практике это не является большой проблемой.) Когда восстановленный открытый текст затем объединяется с его зашифрованным текстом, ключ раскрывается:
Знание ключа позволяет аналитику читать другие сообщения, зашифрованные тем же ключом, а знание набора связанных ключей может позволить криптоаналитикам диагностировать систему, использованную для их создания. [33]
Правительства уже давно осознали потенциальные преимущества криптоанализа для разведки , как военной, так и дипломатической, и создали специализированные организации, занимающиеся взломом кодов и шифров других стран, например, GCHQ и АНБ , организации, которые до сих пор очень активны.
Несмотря на то, что вычисления с большим успехом использовались при криптоанализе шифра Лоренца и других систем во время Второй мировой войны, они также сделали возможными новые методы криптографии, на порядки более сложные, чем когда-либо прежде. В целом современная криптография стала гораздо более невосприимчивой к криптоанализу, чем бумажные системы прошлого, и теперь, похоже, одерживает верх над чистым криптоанализом. [ нужна цитата ] Историк Дэвид Кан отмечает: [37]
Многие из криптосистем, предлагаемых сегодня сотнями коммерческих поставщиков, не могут быть взломаны никакими известными методами криптоанализа. Действительно, в таких системах даже атака по выбранному открытому тексту , при которой выбранный открытый текст сопоставляется с его зашифрованным текстом, не может дать ключ, который разблокирует другие сообщения. В некотором смысле криптоанализ мертв. Но это еще не конец истории. Криптоанализ, возможно, и мертв, но существует – если использовать мои метафоры – более чем один способ содрать шкуру с кошки.
Далее Кан упоминает об увеличении возможностей перехвата, подслушивания , атак по побочным каналам и квантовых компьютерах в качестве замены традиционных средств криптоанализа. В 2010 году бывший технический директор АНБ Брайан Сноу заявил, что как академические, так и правительственные криптографы «очень медленно продвигаются вперед в зрелой области». [38]
Однако любое вскрытие криптоанализа может оказаться преждевременным. Хотя эффективность криптоаналитических методов, используемых спецслужбами, остается неизвестной, в современную эпоху компьютерной криптографии было опубликовано множество серьезных атак как на академические, так и на практические криптографические примитивы :
Таким образом, хотя лучшие современные шифры могут быть гораздо более устойчивыми к криптоанализу, чем «Энигма» , криптоанализ и более широкая область информационной безопасности остаются весьма активными. [39]
Асимметричная криптография (или криптография с открытым ключом ) — это криптография, основанная на использовании двух (математически связанных) ключей; один частный и один общественный. Такие шифры неизменно полагаются на «сложные» математические задачи как на основу своей безопасности, поэтому очевидной целью атаки является разработка методов решения проблемы. Безопасность двухключевой криптографии зависит от математических вопросов в отличие от одноключевой криптографии, и, наоборот, по-новому связывает криптоанализ с более широкими математическими исследованиями. [ нужна цитата ]
Асимметричные схемы разработаны с учетом (предполагаемой) сложности решения различных математических задач. Если для решения проблемы можно найти улучшенный алгоритм, то система ослабляется. Например, безопасность схемы обмена ключами Диффи-Хеллмана зависит от сложности вычисления дискретного логарифма . В 1983 году Дон Копперсмит нашел более быстрый способ поиска дискретных логарифмов (в определенных группах), что потребовало от криптографов использования более крупных групп (или групп разных типов). Безопасность RSA зависит (частично) от сложности факторизации целых чисел – прорыв в факторинге повлияет на безопасность RSA. [ нужна цитата ]
В 1980 году сложное 50-значное число можно было разложить за счет 10 12 элементарных компьютерных операций. К 1984 году уровень развития алгоритмов факторизации достиг уровня, когда 75-значное число можно было разложить за 10 12 операций. Достижения в области компьютерных технологий также означали, что операции можно было выполнять намного быстрее. Закон Мура предсказывает, что скорость компьютеров будет продолжать расти. Методы факторинга, возможно, продолжат работать так же, но, скорее всего, они будут зависеть от математической проницательности и творческого подхода, ни один из которых никогда не был успешно предсказуем. 150-значные числа, которые когда-то использовались в RSA, были факторизованы. Усилия были больше, чем указано выше, но не были необоснованными на быстрых современных компьютерах. К началу 21 века 150-значные числа больше не считались достаточно большим размером ключа для RSA. В 2005 году числа, состоящие из нескольких сотен цифр, по-прежнему считались слишком сложными для учета, хотя методы, вероятно, будут продолжать совершенствоваться с течением времени, требуя размера ключа, чтобы идти в ногу со временем, или использования других методов, таких как криптография на основе эллиптических кривых . [ нужна цитата ]
Еще одной отличительной чертой асимметричных схем является то, что в отличие от атак на симметричные криптосистемы любой криптоанализ имеет возможность использовать знания, полученные с помощью открытого ключа . [40]
Квантовые компьютеры , исследования которых все еще находятся на ранних стадиях исследования, потенциально могут быть использованы в криптоанализе. Например, алгоритм Шора может учитывать большие числа за полиномиальное время , фактически нарушая некоторые широко используемые формы шифрования с открытым ключом. [41]
Используя алгоритм Гровера на квантовом компьютере, перебор ключей можно выполнить в квадратичном порядке быстрее. Однако этому можно противостоять, удвоив длину ключа. [42]
Аль-Кинди считается первым взломщиком кодов.
