Клод Шеннон - Теория связи в секретных системах, страница 11

Далее, известно, что шифры сбегущим ключом могут быть обычно решены единственным образом. Это говорит о том,что английский текст может быть сжат в два раза, откуда следует, что избыточность должнасоставлять не менее 50%. Однако эта цифра не может быть значительно увеличена по рядупричин (если только не рассматривать далеко распространяющуюся «смысловую» структуруанглийского языка), приводящих к статистическим связям между далекими буквами.Шифр бегущего ключа легко может быть усовершенствован таким образом, чтосистема не может быть решена без ключа. Во-первых, если использовать вместо одного,скажем, четыре различных текста в качестве ключа, прибавляя все их к сообщению, то этимсамым вводится объем ключа, достаточный для того, чтобы создать высокую положительную ненадежность.

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

Одним из методовдостижения идеальности секретной системы является использование в качестве частисистемы расшифровки знания английского языка шифровальщиком адресата.3820. Распределение ненадежности.Более полное описание секретной системы, применяемой к некоторому языку, чемто, которое дается характеристиками ненадежности, можно получить из рассмотренияраспределения ненадежности. Для N перехваченных букв рассмотрим то множество криптограмм, для которых ненадежность и именно ненадежность при условии, что фиксированыэти конкретные криптограммы, а не средняя ненадежность HE(M), лежит в определенныхпределах. Это дает плотность распределенияP(HE(M),N) dHE(M)вероятности того, что для N букв ненадежность лежит между H и H + dH.

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

Это верно по крайней мере тогда, когда вблизи от наивысшей точкинет точки единственности. В этом случае, или в том случае, когда эти условияудовлетворены приближенно, кривая среднего значения распределения дает довольнополное представление о системе.С другой стороны, если язык не является чистым, но составлен из несколькихчистых компонентL=SpL ,i iимеющих различные характеристики ненадежности, то полное распределение будет состоятьобычно из нескольких «гребней». Каждый из них будет соответствовать некоторому Li, иони взвешиваются в соответствии с весами pi.

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

Поэтому можно ожидать, что в этой области вычисления, основанные наслучайном шифре, должны давать до некоторой степени заниженный результат.Часть III.ПРАКТИЧЕСКАЯ СЕКРЕТНОСТЬ.21. Рабочая характеристика.После того как объем перехваченного текста превзойдет точку единственности,обычно будет существовать единственное решение криптограммы. Задача криптографического анализа и состоит в выделении этого единственного решения, имеющего высокуювероятность.

До того как достигнута точка единственности, задача криптографического39анализа состоит в выделении всех возможных решений с большой (по сравнению состальными решениями), вероятностью и в определении вероятностей этих решений.Хотя в принципе всегда можно найти эти решения (например, испытывая все возможные ключи), но для различных систем нужно будет затратить весьма различный объемработы. Средний объем работы, необходимой для определения ключа, если криптограммаимеет N букв, W(N) измеренное, скажем, в человеко-часах, можно назвать рабочей характеристикой системы. Это среднее значение берется по всем сообщениям и всем ключам ссоответствующими им вероятностями.

Функция W(N) измеряет количество «практическойсекретности» в данной системе.Для простой подстановки, примененной к английскому языку, рабочая характеристика и характеристика ненадежности будут выглядеть примерно такими, как показано на рис.12. Пунктирная часть кривой относится к области, где имеется несколько возможныхрешений и все они должны быть определены. Для сплошной части кривой после точкиединственности существует, вообще говоря, только одно решение, но если необходимыеданные имеются в минимальном количестве, то для нахождения этого решения нужнопроделать большую работу. По мере увеличения количества данных объем необходимойработы быстро уменьшается, стремясь к некоторому асимптотическому значению, котороедостигается, когда дополнительные данные уже не уменьшают объема работы.По существу, такое же поведение кривых, как показано на рис.

12, можно ожидатьдля любого типа секретной системы, в которой ненадежность стремится к нулю. Однакомасштаб количества требуемых человеко-часов будет сильно отличаться для разных типовшифров, даже тогда, когда кривые функции HE(M) почти совпадают. Например, шифрВиженера или составной шифр Виженера с тем же самым объемом ключа имели бы намноголучшие (т. е. более высокие) рабочие характеристики, чем простая подстановка.

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

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

Для этого недостаточно просто бытьуверенным, что никаким из обычных криптографических методов нельзя раскрыть шифр.Надо быть уверенным, что этого нельзя добиться вообще никаким методом. И действительно, это оказалось слабой стороной многих секретных систем. Спроектированные так, чтобыбыть недоступными для всех известных методов решения, они затем приводили к созданиюновых криптографических методов, делавших возможным их раскрытие.Проблема создания хорошего шифра является по существу проблемой нахождениянаиболее сложных задач, удовлетворяющих определенным условиям. Это довольнонетривиальная ситуация, так как обычно в заданной области отыскивают простые и легкоразрешимые задачи.Как можно быть уверенным в том, что неидеальная система, которая необходимоимеет единственное решение для достаточно большого N, потребует большого объема работы для нахождения решения при любом методе анализа? Имеются два подхода к решениюэтого вопроса.

1) Можно изучить возможные методы решения, которыми пользуется про12См. сноску на стр. 341. Ситуацию, складывающуюся между создателем шифра и противником, можно рассматривать как игру очень простой структуры: игра двух партнеров с нулевой суммой, с полной информацией ировно с двумя «ходами». Создатель шифра в качестве своего «хода» выбирает некоторую систему. Послеэтого противник информируется об этом выборе и выбирает метод анализа. «Цена» игры – это средняя работа,требуемая для решения криптограммы выбранным методом.40тивник, и попытаться описать их в достаточно общих терминах, с тем чтобы включить всеметоды, которые могли бы быть им использованы. Тогда наша система будет недоступнойдля этого «общего» метода решения. 2) Можно составить наш шифр таким образом, чтобырешение его было эквивалентно (или включало в себя) решению некоторой проблемы, прокоторую, известно, что для ее решения требуется большой объем работ.

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

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

расшифрованное сообщение, «имеющее смысл» в исходном языке. Простое вычисление показывает, чтоэтот метод решения (который можно назвать методом полной системы испытаний и ошибок)совершенно непрактичен, кроме тех случаев, когда ключ невероятно мал.Предположим, например, что имеется ключ с 26! возможностями, (что составляетоколо 26.3 десятичных единиц)13, т.е. того же самого объема, что и для простой подстановкив английском языке. Этот ключ при любом приемлемом способе измерения является малымключом. Он может быть выписан на клочке бумаги, и его можно выучить в течение пятиминут.

Его можно записать на 27-разрядном десятичном регистре или же на 88-миразрядном двоичном регистре.Предположим далее, давая противнику все возможные преимущества, что онсконструировал электронное устройство для испытания ключей со скоростью один ключ водну микросекунду (скажем, с помощью автоматического выбора и проверки с помощьюкритерия значимости c2). Можно ожидать, что он выберет правильный ключ примернопосле половины всех возможных испытаний, т.е. по прошествии примерно2 ´ 1026/2 ´ 602 ´ 24 ´ 365 ´ 106 = 3 ´ 1012 лет.Другими словами, даже для малого ключа метод полной системы испытаний иошибок не может быть использован на практике для решения криптограмм, исключая тотслучай, когда ключ крайне мал, например, в шифре Цезаря, где имеются только 26 возможностей (или 1,4 десятичных единицы).