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

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

ОГЛАВЛЕНИЕ

Следующая >>


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

К р а т к о е содерлсание главы

- Криптосистемы, в которых знание шифротекста ничего не до­
бавляет к той информации, которой атакующий обладал до его
просмотра, называются абсолютно стойкими.
- Абсолютно стойкие системы существуют, но требуют ключей
той же длины, что и само сообщение, причем новых для каждо­
го следующего послания. Поэтому абсолютно стойкие системы
ценны только с теоретической точки зрения и малоприменимы
на практике.
- «Информация» и «неопределенность», по существу, родствен­
ные понятия. Нападающий фактически стремится к извлече­
нию информации об открытом тексте по его шифрованному
варианту. Количество неопределенности в случайной величи­
не измеряется ее энтропией.
- Соотношение Н{К\С) = Н{К) + Н{Р) — Н{С) позволяет нам
оценить величину неопределенности ключа после прочтения
шифротекста.
- Избыточность естественного языка приводит к тому, что для
взлома наивных шифров не требуется слишком длинного ши­
фротекста.


Дополнительная литература
Наше обсуждение теории Шеннона близко следовало книге Стин-
сона. Другой возможный источник информации об этой теории —
книга Уэлша. Общее введение в теорию информации, включая ее
приложения к теории шифрования, изложено в книге ван дер Люббе.
J.C.A. van der Lubbe. Information Theory. Cambridge University Press,
1997.
D. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.
D. Welsh. Codes and Cryptography. Oxford University Press, 1988.
4^4' Ложные ключи и расстояние единственности I 19

Контрольные вопросы
4.1.1. Найдите ошибку в таблице

abed
^1 W XY Z
к2 Z Y Z X
кг X Z W Y
к4 У W X Z
задающей шифруюш;ую функцию, определенную на множе­
стве открытых текстов Р = {а, Ь, с, d} со значениями в ши­
фрограммах С = {W^ X^Y^ Z}^ которая использует ключи


4.1.2. Какая из величин более интересна А,ЛЯ атакуюш;его:
р{С = с\Р = т) или р{Р = т\С = с),
его шифрованная версия?
где т — открытый текст, а с
Объясните свой ответ.
4.1.3. Какими свойствами должен обладать шифротекст, который
обладает теоретико-информационной стойкостью?

4.1.4. Вспомните определение энтропии случайной величины X с
распределением вероятностей pi = р{Х = Xi).

4.1.5. Пусть случайная величина X принимает не более t значений. На­
зовите минимальное и максимальное значение энтропии Н{Х).

4.1.6. Определите, какое из соотношений справедливы р^ля любых
шифров:
а) Н{Р\К,С) - О ,
б) H{K,P)=H{K)-hH{P).
Аргументируйте свой ответ.

4.1.7. Дайте определение терминов «ложный ключ» и «расстояние
единственности».

4.1.8. Известно, что расстояния единственности шифров Ci и С2
равны, соответственно, щ и П2. Какой из них предпочти­
тельней использовать, если щ > П2?
120 Глава 4- Теоретико-информационная стойкость

Лабораторные работы
4.2.1. Напишите программу, вычисляюп1;ую значения Н{Р'^) при
разных п для части введенного текста. Воспользуйтесь Ва­
шей программой для оценки энтропии Hi и избыточности
RL естественного языка.

Упра^кнения
Несколько первых задач относятся к «игрушечной» криптосистеме,
в которой Р = {а, Ь, с, d}, С = {VF, X, У, Z} и К = {/ci, /^2, ^з? k^}i а
функция шифрования задана таблицей

а b с d
h X Y Z
W
X Z W Y
к2
Z X У
W
кг
к^ Y Z X
W

Считайте, что все сообш;ения и ключи равновероятны.

4.3.1. Вычислите вероятности р{С — Ж), р{С = X), р{С = у) и
р{С = Z).

4.3.2. Вычислите условные вероятности р{Р = т\С = с) для всех
пар ( т , с ) .

4.3.3. Оцените с помоп];ью подсчитанных условных вероятностей,
насколько хороша эта криптосистема.

4.3.4. Вычислите энтропии Н{К), Н{Р), Н{С) и Н{К\С), Подтвер­
ждают ли найденные значения Ваши оценки?

4.3.5. Исследуйте докомпьютерные шифры из главы 3 с помощью
техники главы 4. Вычислите приближенное значение рассто­
яния единственности А^ЛЯ шифров Цезаря, Виженера и шифра
замены и примените полученные результаты к объяснению
их незап1;иш;енности от взлома.

4.3.6. Докажите неравенство Иенсена.

4.3.7. Докажите, что неравенство
Н{Х,У)^Н{Х)+Н{?)
4.4' Ложные ключи и расстояние единственности 121

справедливо р^ля любой пары случайных величин X иУ. Кро­
ме того, покажите, что равенство достигается тогда и толь­
ко тогда, когда они независимы.

4.3.8. Покажите, что энтропии случайных величин удовлетворяют
соотношению
H{X,Y) = H{Y)-hH{X\Y).

4.3.9. Проверьте истинность оценки
H{X\Y) К Н{Х).
Покажите, неравенство превращается в равенство тогда и
только тогда, когда ХиУ независимы.

4.3.10. Покажите, что если шифр с каким-то распределением веро­
ятностей открытых текстов является абсолютно стойким, то
он остается таковым и при любом их распределении.

4.3.11. Докажите, что шифротексты абсолютно стойкой криптоси­
стемы с условием # Р = # К = # С распределены равномерно.

4.3.12. Пусть X и? — случайные величины, отражающие результат
бросания двух костей. Обозначим через Z = X + Y их сумму.
Проверьте, что
H{Z) <H{X,Y).

4.3.13. После удаления из высказывания всех гласных букв и проме­
жутков между словами получилось следующее:
WHTWLDYLKFRLNCHTDY.
Восстановите сообщение.
ГЛАВА 5
СИММЕТРИЧНЫЕ
ШИФРЫ

Ц е л и главы
• Понять основные принципы современных симметричных алго­
ритмов.
• Разобраться в работе алгоритма DES,
• Понять, как работает алгоритм Rijndael.
• Узнать о стандартных режимах работы блочных шифров.
• Очертить область поточных шифров и регистров сдвига с ли­
нейной обратной связью (РСЛОС).


5.1. Введение
Работа симметричных шифров включает в себя два преобразова­
ния:
C = Ek{m) и m = Dk{C),
где т — открытый текст, Е — шифруюш;ая функция, D — расши-
фровываюш;ая функция, к — секретный ключ, С — шифротекст.
Следует отметить, что как шифруюп1;ая, так и расшифровываюш;ая
функции обш;еизвестны, и тайна сообщения при известном шифро-
тексте зависит только от секретности ключа к. Хотя этот хорошо
обоснованный принцип, называемый принципом Керкхоффа^ был из­
вестен еще начиная с середины 1800-ых годов, множество компаний
все еще игнорирует его. Существует много отдельных фирм, разра­
батывающих собственные секретные схемы шифрования, которые
теряют свою стойкость, как только кто-то из персонала допускает
утечку информации о деталях алгоритмов. Опыт показывает, что
наилучшими схемами шифрования являются те, которые изучались
в течение длительного времени большой армией исследователей и
рекомендованы к применению как наиболее безопасные. Схема, из
которой создают коммерческую тайну, не может изучаться никем,
кто не работает на соответствующую компанию.
5.1. Введение

Алгоритм, символическая запись которого приведена в начале
главы, называется криптосистемой с симметричным ключом, по­
скольку обе стороны, обменивающиеся шифрованной информаци­
ей, применяют один и тот же секретный ключ. Иногда симметрич­
ные криптосистемы используют два ключа: один д^ля шифрования,
а другой для обратного процесса. В этом случае мы будем предпо­
лагать, что шифрующий ключ легко восстанавливается по расши­
фровывающему и наоборот.
Позже мы встретимся с криптосистемами с открытым ключом.
В них только один ключ хранится в тайне и называется секретным,
в то время как второй, открытый ключ, доступен всем желающим.
При этом считается невозможным для кого бы то ни было вычи­
слить секретный ключ, опираясь на информацию об открытом.
Возвращаясь к симметричной криптографии, отметим, что чи­
сло возможных ключей должно быть очень велико. Это требование
возникает в связи с тем, что при проектировании криптоалгоритма
мы обязаны учитывать самый плохой сценарий развития событий,
ставя гипотетического противника в максимально выгодное поло­
жение, т.е. мы считаем, что атакующий
- обладает полнотой информации о шифрующем (расшифровы­
вающем) алгоритме,
- имеет в своем распоряжении некоторое количество пар (откры­
тый текст, шифротекст) ассоциированньвс с истинным ключом к.
Если количество возможных ключей мало, то атакующий имеет воз­
можность взломать шифр простым перебором вариантов. Он может
шифровать один из данных открытых текстов, последовательно ис­
пользуя разные ключи, до тех пор, пока не получит соответству­
ющий известный шифротекст. В результате искомый ключ будет
найден. Именно для исключения такого сорта атаки необходимо преду­
смотреть достаточно большое пространство ключей. Принято счи­
тать, что вычисления, состоящие из 2^^ шагов, в ближайшие нес­
колько лет будут неосуществимы. Поэтому ключ, исключаюыщй взлом
простым перебором, должен насчитывать по крайней мере 80 битов.
Хороший разработчик шифра в совершенстве владеет двумя спе­
циальностями: он должен взламывать криптосистемы так же бле­
стяще, как и изобретать их. В наши дни, несмотря на многочислен­
ные попытки, все еще не найден метод аналитического доказатель­
ства стойкости симметричных криптосистем, в отличие от алгорит­
мов с открытым ключом, где криптостойкость шифров доказыва­
ется цепочкой логических рассуждений, начинающейся достаточно
Глава 5. Симметричные шифры

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

5.1Л. Упрощенная модель
На рис. 5.1 изображена упрощенная модель шифрования битовой
строки, которая, несмотря на свою простоту, вполне подходит р^ля
практического применения. Идея модели состоит в применении к
открытому тексту обратимой операции р^ля получения шифротек-
ста, а именно, побитовое сложение по модулю 2 открытого текста со
«случайным потоком» битов. Получатель может восстановить текст
с помоп];ью обратной операции, сложив шифротекст с тем же самым
случайным потоком.

открытый текст \ шифрование 1 ШИФРОТЕКСТ, [расшифрование! открытый текст


случайный поток битов] случайный поток битов




Р и с . 5 . 1 . Упрощенная модель, шифрующая строку битов

Такую модель легко реализовать на практике, поскольку р^ля ее
реализации необходима одна из простейших компьютерных опера­
ций — исключающее ИЛИ, т. е. сложение по модулю 2, которое обо­
значается знаком «©». В главе 4 мы убедились, что шифруя каждое
новое сообп];ение своим ключом, длина которого совпадает с дли­
ной открытого текста, мы получим абсолютно стойкую симметрич­
ную криптосистему. Напомним, что такая криптосистема называ­

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

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

ОГЛАВЛЕНИЕ

Следующая >>