<< Предыдущая

стр. 14
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

панели в алгоритме и пытаемся нащупать положения всех комму­
тационных дисков и колец. Критерием корректности подбираемо­
го расположения служит близость статистики частично расшифро­
ванного текста к естественной. Как только мы получили искомую
близость, можно с достаточной долей вероятности утверждать, что
найденные установки коммутационных дисков и колец действитель­
но верные. После этого мы поочередно помещаем штекеры на панель
до полной расшифровки текста. Такой подход к взлому не был ис­
пользован в военных действиях, поскольку для его успешной реали­
зации необходим пространный шифротекст, а большинство реаль­
ных перехваченных немецких сообщений были очень короткими.
Для осуществления описанной выше атаки нам необходимо по­
нять, близок ли шифр криптограммы по своей природе к подстано­
вочным шифрам. Другими словами, произошел ли данный шифро­
текст из чего-либо похожего на естественный язык.
Глава 3. Исторические шифры

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

Определение 3.1. (Индекс совпадения.) Пусть a;i, . . . ,ж^ —
строка букв, а /о, . . . , /25 — числа появлений букв в строке. Вели­
чина
25
Е fiUi -1)
1С{х) = ^ —-
п{п — 1)
называется индексом совпадений.
Заметим, что для случайного набора букв этот индекс равен
1С{х) « 0 , 0 3 8 ,
в то время как р^ля осмысленного текста, написанного на английском
или немецком языках он равен
1С{х) ?^0,065.
Эта замечательная находка используется при атаке на шифр
«Энигма» следующим образом.
i. Найдем порядок коммутационных дисков. Освободим панель
от штекеров и установим диски в позицию «а, а, а». Перебирая все
угловые положения дисков и их взаимные расположения, определим
ту комбинацию, которая даст самый высокий индекс совпадения 1С
для преобразованного текста. Па это потребуется
60 • 26^ ^ 2^^
операций расшифрования.
2. Аппроксимируем начальные угловые полоэюения дисков. Тот
факт, что начальные угловые положения дисков на предыдущем ша­
ге были точно определены, не вызывает доверия. Однако мы верим
в то, что их взаимное расположение найдено верно. Теперь выяс­
ним стартовые угловые позиции. Па этом этапе штекерная панель
все еще остается пустой, а диски вновь устанавливаются в позицию
«а, а, а», с соблюдением порядка, найденного на предыдущем шаге.
Проходим через все положения каждого из трех коммутационных
дисков и первого кольца, расшифровывая сообщения при каждой
комбинации. Вновь стремимся приблизить коэффициент 1С к мак­
симальному значению. При этом происходит
26^ « 2^^
расшифрований. После указанной процедуры мы определим наибо-
S.l. Роторные машины и «Энигма»

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


операций. В результате мы найдем точные положения второго коль­
ца и второго коммутационного диска. Похожая процедура прово­
дится и А^ля третьего диска. Теперь мы знаем порядок дисков, их
начальные угловые положения и позиции колец. Единственное, что
остается, — это выявить комбинацию штекеров.
4- Определение позиций штекеров. Мы подбираем штекеры по­
очередно до тех пор, пока не сможем прочитать шифротекст. Это
можно сделать с помош;ью индекса совпадения 1С (что требует
очень большого шифротекста) или статистического теста, основан­
ного на информации о распределении триграмм подлежаш;его языка.

Краткое содержание главы
- Многие шифры, применявшиеся на ранней стадии развития
криптологии, были взломаны, поскольку не смогли скрыть ста­
тистики подлежаш;его языка.
- Важнейшие приемы, лежап1;ие в основе первых шифров — это
замены и перестановки.
- Шифры работали с блоками знаков посредством снабженного
ключом алгоритма или просто прибавляли очередное число из
потока ключей к каждой букве открытого текста.
- Шифры, предназначенные устранить недостатки, связанные
со статистикой языка, оказались менее стойкими, чем ожи­
далось, либо из-за конструкционных недочетов, либо в связи с
неграмотной политикой использования, адаптированной в ин­
тересах операторов.

Дополнительная литература
Лучшая книга по истории шифров написана Каном. Однако она
слишком большая, и тому, кто хочет получить быстрое представле­
ние о истории криптографии, можно рекомендовать книгу Сингха.
Монография Черчхауса тоже содержит краткий обзор множества
Глава 3. Исторические шифры

исторических шифров. Особенно хорошо в ней рассказано о маши­
не «Энигма» и истории ее взлома.
R. Churchhouse. Codes and Ciphers. Julius Caesar, the Enigma and the
Internet, Cambridge University Press, 2001.
D. Kahn. The Codebreakers: The Comprehensive History of Secret Com­
munication from Ancient Times to the Internet. Scribner, 1996.
S. Singh. The Codebook: The Evolution of Secrecy from Mary Queen of
Scots to Quantum Cryptography. Doubleday, 2000.

Контрольные вопросы
3.1.1. Назовите три наиболее популярные буквы английского алфа­
вита.

3.1.2. Какие из биграмм и триграмм английского языка наиболее
употребительны?

3.1.3. Объясните, какое отношение имеет шифр Виженера к шифру
сдвига.

3.1.4. Расскажите, как шифр замены связан с машиной «Энигма».

3.1.5. Покажите, чем похожи и в чем разнятся перестановки и за­
мены как компоненты шифров.

3.1.6. Приведенный ниже шифротекст был получен с помощью ши­
фра сдвига. Расшифруйте его.
PELCG BTENC ULVFN AVAGR ERFGV ATFHO WRPG.

Лабораторные работы
3.2.1. Напишите программы, реализуюп1;ие шифрование и расши­
фрование (при условии известного ключа), для следуюш;их
шифров:
(а) сдвига,
(б) Виженера,
(в) замены,
(г) «Энигма».
Для компьютерной реализации последнего Вам стоит чуть больше
узнать о шифре «Энигма» из интернета или книги Черчхауса.

3.2.2. Создайте программу, которая дешифрует шифротекст, по­
лученный с помощью шифра сдвига (предполагая, что соот-
ветствуюш;ий открытый текст написан по-английски).
3.7. Роторные машины и «Энигма»

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

3.2.4*. Сделайте аналогичную программу р^ля «Энигмы».

3.2.5. Насколько большой шифротекст Вы должны обработать Ва­
шими программами для получения достаточно разумного ре­
зультата?

Упражнения
3.3.1. Книэюный шифр похож на шифр Виженера, но р,ля формиро­
вания потока ключей вместо повторяющегося лозунга берет­
ся часть текста из книги, начинающегося с заранее оговорен­
ного места. Следующее сообщение зашифровано с помощью
книжного шифра:
BAACG WLTIV SLSKH ZFSVI RESSM HPACW LPCHB BUIK.
Попытайтесь его расшифровать.

3.3.2. Криптоаналитик при атаке с выбором открытого текста пыта­
ется подсунуть противнику для шифрования открытый текст
по своему выбору. Покажите, что шифры Цезаря, Виженера
и замены могут быть мгновенно взломаны таким способом.
Для каждого из этих шифров определите наименьшую длину
открытого текста, достаточную ^\ля взлома.
ГЛАВА 4
ТЕОРЕТИКО-
ИНФОРМАЦИОННАЯ
СТОЙКОСТЬ

Ц е л и главы
• Ввести концепцию абсолютной стойкости.
• Обсудить стойкость одноразового шифр-блокнота.
• Ввести понятие энтропии.
• Объяснить понятия ложного ключа, фиктивных ключей и рас­
стояния единственности.
• Использовать эти понятия для объяснения слабой криптостой-
кости ранних алгоритмов шифрования.


4.1. Введение
Теория информации — один из краеугольных камней вычислитель­
ной техники. В данной главе изучается ее отношение к криптогра­
фии. Мы не будем предполагать, что читатель знаком с этой тео­
рией.
На первом этапе нам потребуется обш;ее представление о разни­
це между теоретико-информационной стойкостью (или теоретиче­
ской стойкостью) и вычислительной заш;иш;енностью (или практи­
ческой стойкостью). Говоря неформально, криптографическая си­
стема называется вычислительно защищенной (или вычислитель­
но стойкой), если наилучший из возможных алгоритмов, взламыва-
юш;их ее, требует неоправданно высоких затрат вычислительных
ресурсов. Принимая во внимание мощность современных компью­
теров, можно считать, что
280
операции, необходимых для взло­
ма шифра, это тот предел, выходя за который алгоритмы взлома
становятся слишком дорогостояп1;ими. Таким образом, если мини­
мальное число N операций, необходимых алгоритму, атакуюп];ему
данную криптосистему, больше 2^^, то говорят, что она вычисли­
тельно заш;иш;ена. Заметим, что никакую реальную систему нельзя
4.1. Введение

обоснованно считать вычислительно защищенной, поскольку мы не
сможем доказать оптимальность найденного метода взлома. Поэто­
му на практике мы утверждаем ее защищенность в вычислительном
отношении в том случае, если лучший из известных алгоритмов для
ее взлома требует недопустимо большого количества вычислений.
Другой практический подход, связанный с вычислительной за­
щищенностью, состоит в том, чтобы свести взлом системы к реше­
нию хорошо изученных трудных проблем. Например, мы можем по­
пытаться показать, что вскрытие конкретной криптосистемы рав­
носильно разложению данного большого целого числа на множите­
ли. Такие системы часто называют доказуемо стойкими. Однако
при этом стойкость системы обосновывается сведением к трудной
задачи, что нельзя считать корректным доказательством.
По существу, вычислительно, или доказуемо, стойкая криптоси­
стема является стойкой по отношению к противнику, чьи вычисли­
тельные ресурсы ограничены. Даже в том случае, когда противник
обладает большими, но ограниченными ресурсами, он все еще не
сможет взломать систему.
При изучении вычислительно запщщенных схем необходимо иметь
четкие представления о некоторых проблемах:
- Нужно позаботиться о длине ключа. Если размер ключа мал,
то у противника вполне может хватить ресурсов для взлома
криптосистемы.
- Важно следить за последними алгоритмическими достижени­
ями и развитием компьютерной техники.
- Мы должны быть готовы к тому, что наша криптосистема в
какой-то момент будет взломана либо из-за усовершенствова­
ния аппаратных средств, либо в результате крупного алгорит­
мического прорыва.
Большинство криптосистем, активно эксплуатирующихся в на­
стоящее время, вычислительно защищены. Поэтому в каждой из по­
следующих глав мы будем уделять много внимания вычислительной
стойкости изучаемых криптосистем.
С другой стороны, система называется абсолютно стойкой или
совершенной., если мы не ограничиваем вычислительной мощности
противника. Иначе говоря, криптосистема совершенна, если ее не­
льзя взломать даже с помощью бесконечного числа операций. Сле­
довательно, независимо от алгоритмических достижений и совер­
шенства вычислительной техники, абсолютно стойкую схему взло­
мать невозможно. В литературе можно встретить и другой тер-
Глава 4' Теоретико-информационная стойкость

мин, закрепленный за абсолютной стойкостью, а именно, теоретико-
информационная стойкость.
Мы уже видели, что следуюш;ие системы не являются вычисли­
тельно заш;иш;енными, поскольку их можно полностью раскрыть,
имея довольно скромные компьютерные мош;ности:
- шифр сдвига,
- шифр замены,
- шифр Виженера.
К вычислительно стойким системам можно отнести криптоси­
стемы
- DES и Rijndael,
- RSA,
- ЭльГамаля.
С ними мы познакомимся в следующих разделах. Однако упомяну­
тые системы не являются абсолютно стойкими.
Чуть позже в этой главе мы познакомимся с одноразовым шифр-
блокнотом. Вот эту систему можно назвать совершенной, но только
в том случае, если она используется корректно.

<< Предыдущая

стр. 14
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>