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

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

Если к такому языкуприменить любой из простых шифров, то окажется, что нельзя было бы существенноулучшить метод полной системы испытаний и ошибок.Методы, фактически используемые в криптографии, часто включают в себя методиспытаний и ошибок, но несколько отличного типа. Во-первых, испытания проводятся,начиная с более вероятных гипотез, и, во-вторых, каждое испытание относится к большойгруппе ключей, а не к единственному ключу. Так, пространство ключей можно разделить,13То есть log10 26! » 26.3. — Прим. ред.41скажем, на 10 подмножеств, содержащих примерно по одинаковому числу ключей.

С помощью не более чем десяти испытаний находят правильное подмножество. Это подмножестводелится на несколько вторичных подмножеств и процесс повторяется. Для нашего примерас объемом ключа 26! » 2×1026 можно ожидать около 26×5 = 130 испытаний вместо 1026 приполной системе испытаний и ошибок. Этот результат может быть улучшен, если выбиратьсначала наиболее вероятные из подмножеств. Если разделение производить на два подмножества (наилучший способ минимизировать число испытаний), то потребуется только 88испытаний.

В то время как метод полной системы испытаний и ошибок требует числаиспытаний, равного по порядку числу ключей, испытания с разделением на подмножестватребуют только число испытаний по порядку, равное объему ключа в битах.Эти рассуждения остаются верными даже тогда, когда разные ключи имеют разныевероятности14. В этом случае соответствующий процесс минимизации среднего числа испытаний заключается в разделении пространства ключей на равновероятные подмножества.После того как отобрано нужное подмножество, оно снова делится на подмножества равнойвероятности. Если этот процесс может быть продолжен, то среднее число испытаний дляразделений на два подмножества будет равноh=H(K ).log 2Если каждая проверка имеет S возможных исходов, каждый из которых соответствуетнахождению ключа в одном из S равновероятных подмножеств, тоh=H(K )log Sбудет средним числом испытаний.

Следует указать на интуитивное значение этихрезультатов. При проверке с разделением на два равновероятных подмножества каждоеиспытание дает один бит информации относительно ключа. Если подмножества имеютсильно отличающиеся вероятности, как при проверке единственного ключа в методе полнойсистемы испытаний и ошибок, каждое испытание дает лишь малое количество информации.Так, для 26! равновероятных ключей проверка одного ключа дает только26!- 1 11 ùé 26!- 1,-ê+loglog26!26!26! úûë 26!или приблизительно 10–25 бит информации.

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

Известно, что среди 27 монет одна фальшивая и она немного легче остальных.Требуется найти фальшивую монету с помощью ряда взвешиваний на аптекарских весах.Чему равно наименьшее число необходимых для этого взвешиваний? Правильный ответ – 3.Он получается, если сначала разделить все монеты на 3 группы по 9 в каждой. Две из этихгрупп сравниваются на весах. Три возможных результата определяют те 9 монет, средикоторых находится фальшивая. Эти 9 монет снова делятся на 3 группы по 3 монеты ипроцесс продолжается. Множество монет соответствует множеству ключей, фальшиваямонета – правильному ключу, а процесс взвешивания – испытанию или проверке. Первоначальная неопределенность равна 27 бит, и каждое испытание дает log23 бит информации.14Более подробное обсуждение аналогичных вопросов можно найти в книге Яг л о м А.

М . и Ягл о м И. М.,Вероятность и информация, М., 1960. — Прим. ред.42Таким образом, когда нет «диофантовых трудностей», то достаточно log227/log23испытаний.Этот метод решения применим только тогда, когда пространство ключей может бытьразделено на малое число подмножеств так, чтобы существовал простой способ определенияподмножества, содержащего правильный ключ. Для того чтобы применить некоторыйкритерий совпадения и определить, подтверждено ли некоторое предположение, вовсе ненужно, чтобы это предположение относилось ко всему ключу – можно проверить предположение, относящееся только к части ключа (или предположение относительно того, лежит лиключ в некоторой большой части пространства ключей).

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

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

Статистические методы.Многие типы шифров могут быть раскрыты с помощью статистического анализа.Рассмотрим опять простую подстановку. Перехватив криптограмму, противник преждевсего должен произвести подсчет частот букв. Если криптограмма содержит, скажем, 200букв, то без риска можно предположить, что лишь немногие из этих букв (если вообще такиенайдутся) выйдут за пределы своих частотных групп, если группы получены с помощьюразделения всех букв на 4 подмножества с четко отличающимися пределами частот.Логарифм числа ключей при этих ограничениях равенlog 2! 9! 9! 6! = 14.28,и, таким образом, простой подсчет частот уменьшает неопределенность ключа на 12десятичных единиц – огромный выигрыш.В общем случае статистический анализ выполняется следующим образом. Поперехваченной криптограмме E вычисляется некоторая статистика.

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

Поэтому нельзя извлечь никакой пользы из подсчета частот дляраскрытия шифров транспозиции.43Более точно данной статистике S можно приписать некоторую «разрешающуюмощность». Для каждой величины S имеется условная ненадежность ключа HS(K)(ненадежность при фиксированном значении S) и это все, что известно относительно ключа.Взвешенное среднее этих величинS p(S)H (K)Sдает среднюю ненадежность ключа при известном S, где p(S) является априорнойвероятностью конкретного значения S. Разность объема ключа H(K) и этой среднейнеопределенности измеряет «разрешающую мощность» статистики S.В строго идеальном шифре все статистики данной криптограммы не зависят отчастного используемого ключа. Это следует из свойства сохранения меры преобразованиемTjTk–1 в пространстве E или Tj–1Tk в пространстве M.Имеются хорошие и плохие статистики, точно так же, как имеются хорошие иплохие методы испытаний и ошибок.

Фактически проверка некоторой гипотезы методомиспытаний и ошибок представляет собой некоторый тип статистики, и то, что было сказановыше относительно наилучших типов испытаний, верно и вообще. Хорошая статистика длярешения системы должна обладать следующими свойствами.1. Она должна просто вычисляться.2. Она должна зависеть от ключа больше, чем от сообщения, если с ее помощьютребуется находить ключ. Изменения по M не должны маскировать изменений по K.3. Те значения статистики, которые могут быть «различены», несмотря на«размытость», создаваемую изменением по M, должны разделять пространство ключей нанесколько подмножеств, вероятности которых сравнимы по величине, причем статистикабудет характеризовать подмножество, в котором лежит правильный ключ.

Статистикадолжна давать информацию о значительных объемах ключа, а не об объемах, составляющихмалую долю общего числа бит.4. Информация, даваемая статистикой, должна быть простой и удобной дляиспользования. Таким образом, подмножества, на которые статистика разделяетпространство ключей, должны иметь простую структуру в пространстве ключей.Подсчет частот букв для простой подстановки является примером очень хорошейстатистики.Можно предложить два метода (отличных от стремления приблизить систему кидеальной), которые будут мало доступны для статистического анализа. Их можно назватьметодами «распыления» и «запутывания».

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