В. О. Осипян, К. В. Осипян
КРИПТОГРАФИЯ
В УПРАЖНЕНИЯХ
И
ЗАДАЧАХ
В. О. Осипян, К. В. Осипян
КРИПТОГРАФИЯ
В ЗАДАЧАХ
И УПРАЖНЕНИЯХ
Москва
«Гелиос АРВ »
2004
ББК 32.81b
074
Рецензенты:
доктор технических наук, профессор РГТЭУ
Р. 3. Камалян,
кафедра прикладной математики КГТУ.
Осипян В. О., Осипян К. В.
074 Криптография в задачах и упражнениях. — М.: Гелиос
АРВ, 2004. — 144 с., ил.
ISBN 5-85438-009-9
Приведено более 450 различных задач и упражнений, сгруппированных в
соответствии с основными направлениями развития криптографических мето-
дов повышения информационной безопасности автоматизированных систем об-
работки данных. Каждому разделу предшествует краткое введение, состоящее
из определений и основных понятий соответствующей области науки. Пред-
ставленные задачи и упражнения охватывают как классические методы крипто-
графической защиты информации, так и современные методы обеспечения кон-
фиденциальности и целостности данных, ориентированные на применение вы-
числительной техники.
Для студентов, обучающихся по специальностям группы «Информацион-
ная безопасность», а также может быть полезен всем, желающим повысить соб-
ственный уровень знаний в области безопасной передачи и обработки информа-
ции.
ББК32.81вб
ISBN 5-85438-009-9
© Осипян В. О., Осипян К. В., 2004
© Оформление. Издательство «Гелиос АРВ», 2004
ГЛАВА 1
ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
И ПОНЯТИЯ
1.1. Основные обозначения
А, А* — алфавит и множество всех слов (словарь) над А соот-
ветственно;
t, Т — буква и открытый текст источника информации соот-
ветственно;
е, Е — шифр и шифртекст (криптограмма) соответственно;
к, К — элемент ключа и сам ключ шифрования соответствен-
но;
TV, Р, Z, Q — множество натуральных, простых, целых и ра-
циональных чисел соответственно;
Zm = {0,1,2,..., тп — 1} — кольцо вычетов по модулю т;
I — отношение делимости (а | Ь означает а делит Ь; соответ-
ственно а { b означает а не делит Ь);
= — отношение сравнимости (а = b(mod m) означает а срав-
нимо с b по модулю т);
(а, 6) — наибольший общий делитель целых чисел а и 6;
а, Ь] — наименьшее общее кратное целых чисел а и 6;
ж] — наименьшая целая часть действительного числа х (или
же P(z));
]х[ — наибольшая целая часть действительного числа х;
{х} — дробная часть действительного числа ж;
ф(п) — функция Эйлера;
/1(п) — функция Мёбиуса;
7V(*) — количество числовых значений, удовлетворяющих *;
1 . . п — отрезок натуральные числа от 1 до п.
3
Задачи и упражнения
1.1.1.	Определить мощность А*, если А — множество мощно-
сти п.
1.1.2.	Привести различные примеры шифртекстов.
1.1.3.	Доказать, что если р — простое число, отличное от 2, то
его можно представить в виде: 1) Зт ± 1; 2) 4m ± 1.
1.1.4.	Доказать, что множество простых чисел бесконечно.
1.1.5.	Какими свойствами обладают отношения /, =?
1.1.6.	Доказать, что если п = Р^Ръ2 '''Р^ ~ каноническое
разложение числа п, то: т{п) = (оц + 1)(а2 + 1) • • • (о^ + 1)? где
r{ri) — число делителей числа п,
1.1.7.	Доказать, что если п = р^р^2' * т0 S{n) = П
i=i PI
где S{n) — сумма делителей числа п.
1.1.8.	Доказать, что если (а, 6) = d, то уравнение ах + by — d
имеет решение.
1.1.9.	Доказать, что имеет место равенство [а, Ь] = а&/(а, 6).
1.1.10.	Доказать, что если п = р^р^2 • ’ 'Р^, то Ф{п) — п П (^”
1=1
-1/рд
1.1.11.	Доказать, что Ф{^) — п Для любого натурального п.
d\n
1.1.12.	Доказать, что ^2//(d) = \ ’ вСЛ П для любого
d\n [о, если п/1
натурального п.
1.1.13.	Доказать, что [ж + 1/2] = [2х] — [х .
1.1.14.	Доказать, что функции {х}, ||я|| периодичны с наи-
меньшим периодом единица (||я|| = шш(ж — [#],]#[—#)) — рассто-
яние до ближащего целого).
1.1.15.	Доказать, что [ж] + [гс+1/п] + [з;+2/п] + ... + [а?+ -^1-] =
[пяф
4
1.1.16.	Доказать, что если
/(n) =	9(d), то д(п) = ^2^(d)/(n/d),
d\n	d\n
где /i(d) — функция Мёбиуса.
1.1.17.	Доказать, что если
/ы = П6^)’то
d\n	d\n
1.2. Основные понятия
Криптография изучает различные методы преобразования,
шифрования или кодирования данных (данные могут быть пись-
менными, телеграфными, телефонными, телевизионными, данны-
ми электронного обмена в ЭВМ и т. п.), которые не позволили бы
противнику извлечь интересующую его информацию.
При этом по каналу связи передается, как правило, не само
сообщение, предназначенное для пересылки адресату (открытый
текст), а преобразованная с применением некоторого конкретно-
го шифра (chiffre — от франц, цифра) информация (криптотекст,
шифртекст, криптограмма), и для противника возникает слож-
ная задача — ’’взламывание шифра”.
Под шифром понимается совокупность условных знаков, при-
меняемых для сокрытия содержимого открытого текста, а так-
же сами условные знаки.
Криптоанализ, напротив, рассматривает всевозможные спосо-
бы раскрытия шифров, или различные несанкционированные спо-
собы доступа и модификации самих данных.
Вскрытие (взламывание) шифра — процесс получения защи-
щаемой информации из шифрованного сообщения без знания при-
мененного шифра. Способность шифра противостоять всевозмож-
ным атакам на него называется стойкостью шифра.
5
Под ключом в криптографии понимают элемент шифра, ко-
торый применяется для конкретного сообщения и представляет
собой последовательность символов, которая управляет выполне-
нием шифрования и расшифрования. Причем безопасность защи-
щаемой информации, в первую очередь, определяется ключом.
Задачи и упражнения
1.2.1.	Построить общую схему передачи, хранения информа-
ции.
1.2.2.	Привести примеры отправителей и получателей инфор-
мации.
1.2.3.	Привести конкретные примеры каналов связи. Какие
могут быть преобразования сигналов в каналах связи?
1.2.4.	Привести конкретные примеры ключей длины 6, 7, 11,
13 ,14 и п.
1.2.5.	Привести конкретные примеры шифров с ключами из
п. 1.2.4.
1.2.6.	Оценить криптостойкость для каждого шифра из п. 1.2.5.
1.2.7.	Оценить секретность шифра с ключом длины п.
1.2.8.	Привести примеры криптограмм для заданных откры-
тых данных.
1.2.9.	Привести примеры шифрования и расшифрования дан-
ных.
1.2.10.	Как раскрыть шифртекст криптоаналитику? Какие мо-
гут быть подходы?
1.2.11.	Что означает восстановить открытый текст?
1.2.12.	Что такое целостность информации?
1.2.13.	Какие могут быть подходы к проблеме безопасной пе-
редачи информации?
1.2.14.	Пусть
W = СОВЕРШЕННО СЕКРЕТНО - НАТАЛЛИИ.
Можно ли рассмотреть его как криптограмму?
1.2.15.	Зашифруйте текст п. 1.2.14 с помощью шифра Цезаря.
6
1.2.16.	Какие вам известны шифры подстановок и перестано-
вок? Определить возможное число ключей.
1.2.17.	Что называется паролем?
1.2.18.	Сколько необходимо времени для раскрытия пароля
длины 13?
1.2.19.	Что называется алфавитом канала связи? Что называ-
ется сигналом? Какие вам известны типы каналов?
1.2.20.	Какие свойства открытого текста используются при
вскрытии произвольного шифра?
7
ГЛАВА 2
ОБЩИЕ ПРИНЦИПЫ БЕЗОПАСНОЙ
ПЕРЕДАЧИ ИНФОРМАЦИИ
2.1.	Общие подходы засекречивания
информации
Для засекречивания информации можно использовать различ-
ные способы, среди которых мы выделим два основных подхода
— стеганографию (steganos — скрытый, grapho — пишу) и крип-
тографию. Если применяется стеганографический подход, то сам
факт передачи секретного сообщения скрывается от предполага-
емого противника, т. е. сообщение передается секретно.
При криптографическом способе передачи сообщения само со-
общение скрывается с помощью специальных шифров таким об-
разом, чтобы информация, перехваченная аналитиком, без пред-
варительной обработки не имела бы смысла. То есть если в пер-
вом случае сам факт передачи скрывается каким-либо образом,
например, секретная информация смешана с некоторой другой
информацией или рассчитана на незнание оппонента, то во вто-
ром — скрывается само содержание передаваемого сообщения с
помощью конкретного способа шифрования исходного открытого
текста.
Практически считается, что разработчики систем защиты в
выигрыше, если последние успели разработать новую систему за-
щиты до взлома их оппонентами старой системы.
Задачи и упражнения
2.1.1.	Какие имеются подходы к засекречиванию данных?
2.1.2.	Чем отличаются подходы к обеспечению безопасности
информации в методах криптографии и стеганографии?
2.1.3.	Укажите преимущества и недостатки каждого из двух
указанных подходов. Приведите примеры.
8
2.1.4.	Как оценить криптостойкость криптографического под-
хода?
2.1.5.	Как оценить криптостойкость стеганографического под-
хода?
2.2.	Общая схема системы защиты
информации
Под защитой информации понимается совокупность меропри-
ятий, методов и средств (программных, программно-аппаратных
или других), обеспечивающих как исключение НСД к самой ин-
формации, так и ее безопасность в самом широком смысле. Причем
в зависимости от носителя информации меры защиты могут быть
самые разнообразные.
Система, позволяющая защитить информацию на этапах ее об-
работки и передачи (хранение информации есть ее передача во
времени), называется системой защиты. Схематически структура
секретной системы показана на рис. 1.
Рис. 1. Общая схема секретной системы
9
Она всегда состоит из следующих компонентов:
1.	Пространство исходных сообщений Vp, которое содержит
всевозможные исходные тексты Т (открытые тексты).
2.	Ключевое пространство Vk- Каждому ключу К из Vk соот-
ветствует алгоритм шифрования Ек и расшифрования Dp. Если
к исходному тексту Т применить Ек, а к результату шифрования
— Dp. то снова получим Т.
3.	Пространство криптотекстов Ve> которое содержит всевоз-
можные криптотексты или шифртексты Е, получаемые как ре-
зультаты применения к элементам Т из Vp методов шифрования
Ек, где К пробегает все пространство ключей
Так, например, для криптосистемы с алгоритмом шифрования
Е = аТ + 6(mod п)
ключ Ке состоит из пары чисел (а, Ь), а ключ расшифрования
Kd
(а-1, —а-16).
Таким образом, секретная система (криптосистема), или си-
стема защиты информации (СЗИ), определяется как некоторое
множество отображений одного пространства (множество возмож-
ных сообщений) в другое пространство (множество возможных
криптограмм). Каждое конкретное отображение из этого множе-
ства соответствует способу шифрования при помощи конкретного
ключа.
Задачи и упражнения
2.2.1.	Найти все открытые тексты Т длины п над алфавитом
А = {а, Ь, с}.
2.2.2.	Пусть Т = СОВЕРШЕННО СЕКРЕТНО и F(t, 13) - t+
+13. Найти шифртекст Е.
2.2.3.	Привести примеры различных функций шифрований.
2.2.4.	Как построить шифрофункцию F(t,K) из тригономет-
рических функций?
10
2.2.5.	Расшифровать следующую криптограмму:
Е = НЕ_СПЕШИТЕ_ВЕТТЕСС
2.2.6.	Что означает дешифровать криптограмму?
Е = АРАБЛИНКА_В_ОПАСНОСТИ
2.2.7.	Приведите примеры криптосистем. Что называется чис-
ловым эквивалентом элемента открытого текста?
2.2.8.	Пусть функция шифрования имеет вид
F(t, 13) = t3 + 14t2 + 14t + 13
(здесь ключ К = 13). Из F(t, 13) = 105 находим значение t = 2,
решая уравнение t3 + 14t2 + 14t + 13 = 105.
Для каждого ли значения Е = F(t, 13) можно однозначно опре-
делить t?
2.2.9.	Пусть криптограмма открытого текста имеет вид
Е = ААТТЛЛААСС_ММААТТЕЕРРИИККООВВ
Можно ли однозначно определить Т?
2.2.10.	Что называется полиалфавитным шифрованием?
2.2.11.	Приведите примеры числовых эквивалентов, если эле-
ментом для открытого текста является:
1.	Отдельная буква некоторого алфавита;
2.	Биграмма заданного алфавита;
3.	Блок длины d (d-грамма).
2.2.12.	Иногда удобнее обозначать элементарные сообщения
иными математическими объектами, нежели целые числа, напри-
мер векторами, матрицами или точками некоторой кривой.
Привести примеры таких криптосистем.
2.2.13.	Для заданного алфавита и функции шифрования F(t, К)
построить:
1.	Пространство исходных сообщений Vt‘,
2.	Ключевое пространство Vk\
3.	Пространство криптотекстов Ve-
2.2.14.	Могут ли одному и тому элементарному сообщению
соответствовать различные шифры?
11
2.3.	Построение функций
шифрования. Односторонние
функции
Пусть для простоты алфавит числовых эквивалентов букв от-
крытого текста имеет вид:
А = {1,2,... ,п},
а исходный открытый текст Т длины m —
Т — t\t2 • • • tm^ im £ ^4*
Функцией шифрования, в частности, назовем такую функцию
е = /(<),
которая любым двум различным значениям аргументов t±
сопоставляет два различных значения функции /(ti)
Например, для открытого текста
Т = ^1^2 • • • ^тч £ -^4
имеем следующий шифртекст:
• • •/(tm),
где f(tm) может быть любое нецелое действительное значение.
Пример 1. Если в качестве функции шифрования выбрать функ-
цию:
Y = sin7r(T — 1)/2(п — 1),
то она отобразит буквы алфавита
Л = {1,2,... ,п}
на отрезок [0,1].
12
Так, если Т = БАС = 2_1_3 (для русского алфавита п = 33),
то его криптограмма имеет вид
Е = sin7r/64_sinO_sin7r/32.
Пример 2. Теперь рассмотрим пример шифра с помощью быст-
ро растущей функции шифрования, а именно с помощью функ-
ции 1(и,р) — числа простых полиномов степени и над полем Галуа
GF(p).
Сопоставим каждой букве t G А слово из коэффициентов поли-
нома — простого над GF(p) степени t. Длина такого слова равна
п + 1.
Так, например при р = 2 (см. табл. 1), если
Т = БАС-2_1_3,
то имеем следующие четыре различных шифртекста:
1.	Е = 00... 111_00... 01_00... 1010
2.	Е = 00... 111_00... 01_00... 1101
3.	Е = 00... 111-00... 11_00... 1010
4.	Е = 00... 111_00... 11_00... 1101
Таблица 1
t	1	2	3	4	• • •	п
f(x)	X х + 1	X2 + х + 1	X6 + х + 1 а?3 + х2 + 1	х4 + Xs + х2 + 1		
е	00... 01 00...11	00...Ill	00...1011 00...1101	00...11111		
Отметим, что данный способ шифрования открытого текста Т
рассеивает частоту встречаемости букв в нем. Кроме того, здесь
можно использовать число l(t,p) простых полиномов степени t
для представления одной буквы t Е Л, количество которых с ро-
стом Р быстро растет.
Хотя указанные функции могут быть использованы как функ-
ции шифрования, на практике применяют так называемые одно-
13
сторонние функции или односторонние функции с секретом (с ла-
зейкой) S. Понятие односторонней функции было введено в 1976 г.
Диффи и Хеллманом.
Односторонней называется функция F(x), обладающая двумя
свойствами:
1. Существует полиномиальный алгоритм вычисления значе-
ний F(t);
2. Не существует полиномиального алгоритма инвертирования
функции F(x), т. е. решения уравнения F(x) = у относительно х
по заданному у.
Односторонней функцией с секретом S называется функция
Fs(x), зависящая от параметра S и обладающая следующими свой-
ствами:
1.	При любом S существует полиномиальный алгоритм вычис-
ления значений Р$(х\7
2.	При неизвестном S не существует полиномиального алго-
ритма инвертирования функции Fs(x);
3.	При известном S существует полиномиальный алгоритм ин-
вертирования функции Fs(x).
Существование односторонних функций является необходимым
и достаточным условием для построения стойких криптосистем.
При этом задача инвертирования этих функций эквивалентна неко-
торой сложной математической задаче.
Задачи и упражнения
2.3.1.	Какие из функций являются функциями шифрования:
1)	у = 7^ + 13;
2)	у = 13т2 + 6 + 14;
3)	у = х — 11 + COST.
2.3.2.	Зашифровать открытый текст Т — НЕ_ТОРОПИСЬ с
помощью функции шифрования У = Е(х). Построить крипто-
грамму для открытого текста
Т = АНТИКАНАЛЬЧИК ВЕТТЕСС
14
2.3.3.	Пусть для входа в систему потенциальный пользователь
применил однажды значение функции F(x) = х + K(mod 1001),
где х — значение пяти последних значащих цифр таймера, & К —
свой числовой пароль. Сможет ли он войти в систему еще раз?
2.3.4.	Привести примеры односторонних функций с секретом
и без него.
2.3.5.	Определить открытый текст Г, если шифртекст имеет
вид
Е = ФВМЖТИВФЮ
2.3.6.	Пусть a?i, а?2, а?з — корни многочлена
= х3 + х — 7.
Зашифровать сообщение Т = НЕ_ОШИБИСЬ с помощью функ-
ции
f(x) = 2х7 + 7 а?5 — 14а?4 — 4а?3 — 35а?2 — а? + 10
следующим образом: е = f(xK) + 5, где з — числовой эквивалент
текущей буквы, а хк — произвольный корень ^(а?).
2.3.7.	Зашифровать сообщение
Т = ВСТРЕЧА_ОТМЕНЯЕТСЯ_ЯВКА_РАСКРЫТА
с помощью ключа табл. 2.
2.3.8.	Функция
Y = Е(Х) = [X]
рассеивает частоту встречаемости букв в открытом тексте Т.
Для шифрования открытого текста воспользуемся, например
табл. 2:
Таблица 2
t	1	2	3	• • •	п
е	[0,1)	[1,2)	[2,3)	• • •	[п — 1, п)
15
Так, например, если Т =БАС=2_1_3, то имеем следующий за-
шифрованный текст:
Е = 1.q_0./3_2.7,
где диапазон значений се, /?, 7 очень велик.
Какими свойствами обладает данный шифр?
2.3.9.	Доказать, что для любого п ф 2 существует циклическая
последовательность периода п, которой соответствует неприводи-
мый в GF(2) полином степени п. Построить криптограмму за-
данного сообщения, используя указанные циклические последо-
вательности.
2.4.	Защита информации от помех
в каналах связи
В процессе хранения (передачи информации во времени), пере-
дачи и обработки информации могут возникнуть ошибки (искаже-
ние сигналов в каналах связи под воздействием шума), и для того
чтобы уменьшить или исключить канальные ошибки, т. е. защи-
тить информацию от помех в каналах связи, необходимо предста-
вить информацию в таком виде (т. е. выбрать подходящий способ
кодирования), чтобы она была устойчивой к различным каналь-
ным ошибкам. Как правило, достижение последней на практике
реализуется с помощью помехоустойчивых кодов исходя из харак-
теристик канала связи и типов канальных ошибок.
Рассмотрим основные виды преобразований кодовых слов (сиг-
налов), называемых канальными ошибками.
I.	Симметричные ошибки. Это такие ошибки, при которых ве-
роятности изменения каждого канального символа равны между
собой. При этом соответствующий канал называется симметрич-
ным каналом. Примером такого канала является двоичный сим-
метричный канал (ДСК) (см. рис. 2).
16
Рис. 2
Здесь с вероятностью р (0 < р < 0,5) двоичный символ 0 пе-
реходит в двоичный символ 1: {0 - 1} , а символ 1 — в 0: {1 —>
—> 0}. Ошибки указанного типа {0 —> 1,1 —> 0} иначе называют
аддитивными ошибками, или ошибками типа замещения.
Симметричные ошибки типов выпадения (или стирания) и встав-
ки имеют соответственно вид: {0 —> Л, 1 —> Л}, {Л —> 0,Л —» 1},
где Л — пустой символ.
II.	Асимметричные ошибки. Это такие ошибки, при которых
вероятности изменения разных канальных символов не равны меж-
ду собой. Тогда соответствующий канал называется асимметрич-
ным каналом.
Так, например, при асимметричной ошибке типа {1 —> 0} про-
исходит замена 1 на 0 с некоторой вероятностью р, но не наоборот.
Аналогично можно рассматривать асимметричные ошибки видов:
{0	1}, {1	0}, {0	Л}, {1	Л}, {Л 0}, {Л !}.(*)
Здесь отметим лишь следующее: если, например канал типа
ДСК, то необходимо применить соответствующий код для защиты
информации от симметрических ошибок. Этого можно достичь,
например, с помощью кода Хэмминга, если число ошибок предпо-
лагается не более одной.
Если же могут возникнуть арифметические ошибки вида
+2г(—2г), что характерно при выполнении арифметических и ло-
гических операций, выполняемых на ЭВМ, то защитить резуль-
таты вычислений от таких ошибок можно, например с помощью
арифметических А JV-кодов.
Таким образом, необходимо на основании характеристик кана-
ла выбрать такой способ кодирования, чтобы вероятность искаже-
17
ния передаваемого сообщения была бы меньше наперед заданной
величины.
Задачи и упражнения
2.4.1.	Привести пример двоичного шифрования информации,
устойчивого относительно канальных ошибок типа 0 —> 1 или
1 ->0.
2.4.2.	Привести пример шифрования информации, устойчиво-
го относительно канальных ошибок типа ’’вставки Л —> е”, где Л
— пустой символ.
2.4.3.	Привести пример шифрования информации, устойчиво-
го относительно канальных ошибок типа "выпадение е —> Л".
2.4.4.	Построить СЗИ, устойчивую относительно канальных
ошибок типов, указанных в (*).
2.4.5.	Привести пример шифрования данных, устойчивого от-
носительно арифметических ошибок вида +2г(—2г).
2.4.6.	Показать, что код Варшамова обнаруживает и исправ-
ляет все указанные асимметричные ошибки.
2.5.	Различные способы сокрытия
информации
1.	Сокрытие информации с помощью естественного языка.
Для этого можно применить естественный язык, которого не зна-
ет оппонент. Так, например, если открытый текст имеет вид Т =
= "ШиШ ПИП", то для многих оппонентов, не владеющих ар-
мянским языком, данный текст ни о чем не говорит. Очевидно,
здесь ключом для раскрытия текста является применяемый есте-
ственный язык, т. е. в данном случае армянский язык.
2.	Сокрытие информации с помощью заданного кода. В дан-
ном случае необходимо задать способ кодирования информации
при шифровании и способ декодирования — при восстановлении
информации.
18
3.	Сокрытие информации с помощью заданного условия.
Пусть а — некоторый примитивный элемент поля Галуа, и он
является корнем полинома f(x) степени 130614 с коэффициентами
того же поля. Требуется найти порядок элемента а.
Очевидно, данная задача имеет одно единственное решение из
всех возможных, т. е. имеется единственный ключ, удовлетворя-
ющий условию указанной задачи.
4.	Сокрытие информации с помощью маскировки.
Системы маскировки включают применение таких методов,
как, например представление сообщения в форме картинки или
безобидного текста. В данном случае, кроме того, что информа-
ция закодирована, противнику необходимо догадаться, что она
хранится, например в BMP-файле, что намного усложнит его за-
дачу.
Отметим особо, что все математические задачи, да и не толь-
ко они, являются системами сокрытия информации с заданными
условиями, а сами решения указанных задач соответствуют пра-
вильным ключам. Что же касается вопроса решений, то они со-
ответствуют испытанию или проверке правильного ключа, т. е.
выбор подходящей задачи позволит строить систему защиты ин-
формации на должном уровне.
Задачи и упражнения
2.5.1.	Придумать эффектные способы сокрытия информации.
2.5.2.	Привести примеры систем маскировки.
2.5.3.	С помощью датчика случайных чисел к криптограмме
добавлено некоторое количество символов ’’блефов”. Возможно
ли после этого однозначное расшифрование?
2.5.4.	Описать алгоритм смешивания и разъединения различ-
ных файлов при маскировке.
2.5.5.	Расшифровать текст:
Т = HAYERECDZERTCSAVITANEM
2.5.6.	Это что? Т = BARIARAVOTIMSIRELILUSINE
19
2.5.7.	Чем отличаются подходы к обеспечению безопасности
информации в криптографии и в методах сокрытия информации?
2.5.8.	Предложите подходы для распознавания криптограмм.
2.5.9.	Какими методами обеспечивается конфиденциальность
информации? Приведите примеры.
2.5.10.	Для каких аспектов информационного взаимодействия
необходима аутентификация? Приведите примеры.
2.6. Защита данных с элементом
маскировки
Пусть
А — {й,	• • • Дп}
— алфавит открытого текста, а
М = {т1,7П2,... ,тп
— все различные символы алфавита маскировки (в частности, они
суть пробелы или некоторые специальные символы — символы
’’блефов”), причем теоретически можно считать, что М — неко-
торое счетное множество.
Идея применения маски заключается в том, чтобы при шиф-
ровании открытого текста к шифрам необходимо добавлять сим-
волы из алфавита маскировки, а при расшифровании — отсеять
их.
Реализацию указанной идеи можно свести, например к акти-
визации датчика случайных чисел соответствующим образом.
Так, например, если открытый текст имеет вид = ПАЙ-ПАЙ,
Е =	. • ,minnm2i,m22, •• •	Am3i,m32,... ,т3пЙт41,
m42,..., m4n - m5i, m52,..., m5n Пm6i,m62,..., m&n A m71,
m72,..., m7n Й m81, m82, • • •, m8n,
где m7j — суть элементы из M.
20
Задачи и упражнения
2.6.1.	Определить криптостойкость способа шифрования с эле-
ментом маскировки.
2.6.2.	Пусть А = {06, D, £}, М = {07,08,09, В, С} и = В_6_В.
Построить криптограмму В, применяя способ шифрования с эле-
ментом маскировки.
2.6.3.	Расшифровать криптограмму Е = D0707060708E09BC,
используя алфавиты из 2.6.2.
2.6.4.	Привести пример шифрования данных с элементом мас-
кировки, используя одни и те же ключи для обоих алфавитов А
и М.
2.6.5.	Привести пример шифрования данных с элементом мас-
кировки, используя различные ключи для алфавитов А и М.
2.6.6.	Разработать алгоритм реализации способа шифрования
данных с элементом маскировки.
2.6.7.	Зашифровать текст Т = СТУДЕНТ ФПМ с помощью
шифра с автоключом:
__ I xi + если I < d,
1 xi + Ki + если I > d.
2.6.8.	Пусть известны алфавиты Wв и Wt букв ’’блефов” и от-
крытого текста. При каких |ТУв| и |Ит| вероятность взлома шиф-
ра составит не менее
21
ГЛАВА 3
ЭЛЕМЕНТАРНЫЕ МЕТОДЫ
ЦИФРОВОГО ШИФРОВАНИЯ.
СИММЕТРИЧНЫЕ СИСТЕМЫ ЗАЩИТЫ
ИНФОРМАЦИИ
3.1.	Криптографические методы
защиты информации
Пусть А = {t | t G Г}, Р = {е | е Е Е} — алфавиты сообщения
и шифрования соответственно, причем в общем случае п — | А |>
>| Р |= т, ибо возможно соответствие целому слову из Т одного
шифра е из Р.
Здесь и ниже будем использовать следующие шифры для букв
русского алфавита:
Таблица 3
А	Б	В	г	д	Б}		3	И		о	 и	к	л	М	н
0 1	0 2	0 3	0 4	0 5	0 6	0 7	0 8	0 9	1 0	1 1	1 2	1 3	1 4
0	п	р	С	Т	"У	(J)		Ц		Ш
1 5	1 6	1 7	1 8	1 9	2 0	2 1	2 2	2 3	2 4	2 5
J J J	Ъ	Ы	Ь	Э	ю	я		
2 6	2 7	2 8	2 9	3 0	3 1	3 2	3 3
22
Так, например, если
Т = ЭТО_ЕСТЬ_ОТКРЫТЫЙ_ТЕКСТ
то для него имеем следующую криптограмму
Е = 3019153306181929331519111728192810331906111819
В более общем случае эту таблицу можно заменить таблицей 4.
Таблица 4
А	Б	В	• • •	я	*
М}	{Б}	{В}	• • •	{Я}	{*}
Здесь {*} означает множество шифров для символа *, при этом
все множества шифров не пересекаются. Это так называемая по-
лиалфавитная таблица шифрования. В частности, в качестве {*}
в табл. 4 можно выбрать различные между собой числа, представ-
ления которых имеют одинаковую длину.
Задачи и упражнения
3.1.1.	Приведите примеры моноалфавитного и полиалфавит-
ного шифров.
3.1.2.	Какие имеются алгоритмы шифрования по ключу.
3.1.3.	Что называется открытым ключом? Приведите приме-
ры.
3.1.4.	Что называется секретным ключом? Приведите приме-
ры.
3.1.5.	Какая связь существует между открытым и секретным
ключами?
3.1.6.	Какими основными способами может атаковать крипто-
аналитик?
3.1.7.	Что называете криптостойкостью алгоритма шифрова-
ния?
3.1.8.	Какими основными величинами характеризуется слож-
ность криптоаналитических атак?
23
3.1.9.	Приведите примеры симметричных и асимметричных
систем защиты информации.
3.1.10.	Можно ли из симметричной системы защиты инфор-
мации построить асимметричную систему? Приведите примеры.
3.1.11.	Доказать, что линейная функция является целой пере-
становочной функцией для любого конечного поля GF(p). (Функ-
цию f(x) назовем перестановочной над GF(p), если /(0),/(1),
/(2),..., /(m — 1) суть различные между собой элементы GF(p).)
3.1.12.	Доказать, что блочные шифры Плейфера и Виженера
являются многоалфавитными шифрами. Рассмотреть, в частно-
сти случай биграмм.
3.1.13.	Пусть ключ состоит из слова, содержащего 6 разных
букв русского алфавита (см. табл. 3), например:
К = МАТЕМАТИКА
Подписывая ключ под алфавитом с любого места и сопоставив
каждой из букв алфавита, состоящего из 33 букв, одну из букв
ключа (повтор не в счет), получим отображение не всех букв ал-
фавита на последовательность, состоящую из тех же букв.
Можно ли таким образом полученный шифр применять для
зашифрования и расшифрования заданного открытого текста?
3.1.14.	Доказать, что дробно-линейная функция является пе-
рестановочной функцией для любого конечного поля GF(p) и най-
ти Np((ax + b)/(cx + d)).
3.1.15.	Пусть Np,n(f(x)) — количество целых перестановочных
функций степени п конечного поля GF(p). Найти Np,n(f(xY) для
различных пир.
24
3.2.	Метод простой подстановки
(замены)
При моноалфавитной замене каждой букве t Е Т ставится в
соответствие одна буква е Е Е при условии, что А = Р, т. е.
е = К± * t + /<2 (mod n),
или
e = t + A^mod n),
где и K2 — секретные ключи шифрования и расшифрования
одновременно, п — количество символов в алфавите А. Запись
вида t ± K(mod п) означает букву, отстающую от t в алфавите А
на ±A(mod п) позиций.
Так, например, если
Т = ШИФР ЗАМЕНЫ
то при е = t + 13(mod 33) имеем
Е = ДЦАЭМФНЩТЪЗ
Очевидно, для восстановления Т по Е достаточно воспользо-
ваться равенством: t = е — 13(mod 33).
Если же в качестве ключа К взять вполне определенное слово
или фразу (секретный ключ) длины d
K = KxK2...Kd,
то мы тем самым определим более сложный метод подстановки,
суть которого сводится к следующему шифру (шифр Виженера):
a = ti + Ki(mod n),
где
{z(mod d), если /|d,
d, если z|d,
25
ti — г-й символ открытого текста, et — г-й символ шифртекста.
Так, например, если
Т = ШИФР ЗАМЕНЫ
— открытый текст, а
К = РРВО
— секретный ключ длины 4, то шифртекст Виженера будет иметь
вид
Е = ИЩЧЯРШГЫЦЮЮ
На практике для зашифрования открытого текста Т и рас-
шифрования Е по шифру Виженера с секретным ключом К —
—	длины d можно использовать таблицу Виженера
(см. Приложение).
Задачи и упражнения
3.2.1.	Программа ROT13 (ОС UNIX) циклически сдвигает каж-
дую букву латинского алфавита на 13 позиций вправо. Как рас-
шифровать криптограмму, применяя только программу ROT13?
3.2.2.	Пусть кодовый текст ЛЕДЕНЕЦ соответствует фразе
открытого текста ПОВЕРНУТЬ КЛЮЧ ВПРАВО НА 90°.
Расшифровать кодовый текст
ЛЕДЕНЕЦ+ЛЕДЕНЕЦ+ЛЕДЕНЕЦ
3.2.3.	Докажите, что:
a)	Y ф К — X ;
б)	Y ф Y' = X,
где Y' — копия шифртекста У, сдвинутого на величину длины
ключа К.
3.2.4.	Докажите, что способ шифрования с помощью операции
сложения по модулю 2 обладает очень слабой стойкостью.
3.2.5.	Как, исходя из шифртекста, найти секретный ключ спо-
соба шифрования с помощью операции сложения по модулю 2?
26
3.2.6.	Применяя статистику встречаемости букв, провести крип-
тоанализ и дешифровать криптограмму, зашифрованную с помо-
щью шифра сдвига букв кириллицы:
Е = ЫЛЧУВФНУЮЕГИХВФСЗИУЙГРЛИВХИНФХГ
3.2.7.	Пусть
X = ШИФР_СКРЫВАЕТ_СОДЕРЖАНИЕ_ТЕКСТА
— открытый текст, и к нему применяется следующий ключ (см.
табл. 5) замены один раз, затем к полученному слову еще раз
и т. д. Через сколько таких замен впервые появится исходный
открытый текст Т?
Таблица 5
А	Б	в	г	Д	Е	ж	3	и	о и		Л	м	н
Т	"У	(J)		ц	ну	Т;Т	ттт^	ъ	А	Б	В	г	д
О	у j	р	с	т	"У	(J)		Ц	ч	у уу
Е		3	и	й	к	л	м	н	О	уу
у у у		ы	ь	э	ю	я	
р	с	ь	э	ю	я	——	ы
3.2.8	(Шифр Полибия). Рассмотрим способ сопоставления
букв латинского алфавита к биграммам на основе следующей таб-
лицы:
	А	В	С	D	Е
А	А	в	С	D	Е
В	F	G	Н	I	К
С	L	м	N	О	Р
D	Q	R	S	Т	и
Е	V	W			Z
27
Каждой букве сопоставим пару букв, указывающих на строку
и столбец, в которых расположена данная буква (например V—
-ЕА, R-DB).
Зашифровать открытый текст:
Т = ТЛЮСТЕН ВАШИ ФАТИМА НАШИ ДРУЗЬЯ
Является ли данный шифр моноалфавитным?
3.2.9.	Дешифровать криптограмму:
Т = ЕС ИМ АНУШ АЙАСТАНИ АРЕВААМ БАРН ЭМ
СИРУМ МЕР ЙИН САЗИ ВОГБАНВАГ ЛАЦАКУМАЦ
ЛАРН ЭМ СИРУМ
3.2.10.	Восстановить текст:
Т = ЕИЙТДЕФЪЙЭ ФЭКЧЛЫ ДЧФЕЩГЕШДЕ СКЧ ВЯУЬЧ
ШЩОМЩЙН-ЧЧ АЧФЫУЧ КИКХКУВ_ЯЙ
3.2.11.	Пусть криптограмма некоторого открытого текста име-
ет вид ИЩЧЯРШГЫЦЮЮ:
(25 + 17)mod 33 = 09 => ух = И;
(09 4- 17)mod 33 = 26 => у2 = Щ;
(21 + 03)mod 33 = 24 => уз = Ч;
(17 + 15)mod 33 = 32 => у4 = Я;
(33 + 17)mod 33 = 17 => у5 = Р;
(08 + 17)mod 33 = 25 => у6 = Ш;
(01 + 03)mod 33 = 04 => у7 = Г;
(13 + 15)mod 33 = 28 => у8 = Ы;
(06 + 17)mod 33 = 23 => у9 = Ц;
(14 + 17)mod 33 = 31 => yiO = Ю;
(28 + 03)mod 33 = 31 => yil = Ю.
Провести криптоанализ и вскрыть данный шифр.
3.2.12	(Шифр Виженера). Чтобы получить шифртекст Е
из Т, предварительно подписываем секретный ключ К =
= КхК2... К(1 длины d с повторением над буквами открытого
28
текста Т, а затем находим очередной шифр е* как букву, распо-
ложенную на пересечении t^-й строки (первая строка, в которой
находится буква и Kj-ro столбца (первый столбец, в котором
находится буква /Q), начиная с первой буквы открытого текста
Для расшифровывания очередной буквы е* шифртекста Е на-
ходим ее как букву £г-, расположенную в таблице на пересечении
Ki-ro столбца и ег-й строки (в качестве системы отсчета необходи-
мо выбрать первую строку и первый столбец таблицы Виженера).
Так, например, пусть секретный ключ К состоит из одного
слова ЗИМА, т. е.
К = ЗИМА
а открытый текст
Т = ШИФР_ВИЖЕНЕРА_Д Л Я_Х АКЕРОВ
Тогда с помощью таблицы Виженера получим
Т = ШИФР_ВИЖЕНЕРА_ДЛЯ_ХАКЕРОВ
К=ЗИМАЗИМАЗИМАЗИМАЗИМАЗИМАЗ
Е = АРБРЖКФЖМХСРЗЗРЛЖЗВАСНЭОЙ
Какими свойствами обладает данный шифр Виженера? Пред-
ложить эффективный метод для криптоанализа.
3.2.13.	Рассмотрим способ шифрования — с помощью опера-
ции сложения по модулю 2. К битам открытого текста Т при-
бавляются соответствующие биты ключа К (здесь использованы
ASCII-коды для символов).
Так, например, если Т = А
ВАС = 412042414316 =
= 0100 0001 0010 0000 0100
0010 0100 0001 0100 00112
29
то записывая ключ К = 1101 под Г 10 раз, начиная с начала
и применяя сложние по модулю 2, получим следующую крипто-
грамму:
Е = 10011100 1111 1101 10011111 1001 11001001 1110
Или E’ = 9CFD9F9C9Ei6 (указанный алгоритм использует-
ся в цифровых сотовых телефонах американских производителей
для засекречивания речевых переговоров). Какой эффективный
метод можно предложить для вскрытия данного шифра?
3.2.14.	Какие существуют разновидности относительно метода
замены? Приведите соответствующие примеры.
3.3.	Метод перестановки
В шифре перестановки буквы открытого текста не замещаются
на другие, а меняется сам порядок их следования. Поэтому для
реализации любого метода перестановки предварительно разби-
вается открытый текст Т на блоки некоторой заданной длины
п, и шифруется открытый текст поблочно — путем перестановки
символов блока в соответствии с заданными правилами переста-
новки.
Данные правила перестановки и составляют ключ шифрова-
ния. При этом, очевидно, символы открытого текста не изменя-
ются, а изменяется только их порядок следования.
Так, например, если исходный открытый текст имеет вид
Т = ШИФР ПЕРЕСТАНОВКИ
то после перестановки букв в каждом блоке длины четыре с по-
рядковыми номерами 1-й, 2-й, 3-й, 4-й на номера 2-й, 3-й, 4-й, 1-й,
соответственно, получим шифртекст (здесь ключ К = 2 3 4 1):
Е = ИФРШ ЕРЕПТАНСВКИО
30
В общем случае, когда длина блока равна п, то шифрование
открытого текста Т нужно произвести по подстановке S степени
п:
где К{ — номер места криптограммы, на которое попадает г-я
буква открытого текста при заданной перестановке, т. е.
I tki, если i < п,
et—\
tki-пч еСЛИ i > П.
Можно придумать совершенно уникальные способы записи ис-
ходного текста Т и считывание Е с помощью геометрических фи-
гур и рассмотреть различных маршруты в них. Такой шифр на-
зывают маршрутной перестановкой.
Пусть, например, имеем открытый текст:
Т = ТОЛЬКО_ДЛЯ_СТУДЕНТОВ_ФПМ_КУБГУ
Предварительно запишем его в прямоугольную таблицу раз-
мерности 5 х 6 по строкам следующим образом:
т	О	л	ь	К	О
		д	л	я	——	
т	'У	д		н	Т'
О	в		ф	J £	м
	к	'У	Б	г	У
Затем выпишем текст Т из этой таблицы другим способом, на-
пример по столбцам, в виде:
Е = Т_ТО_ОДУВКЛЛД_УЬЯЕФБК_НПГОСТМУ
31
Задачи и упражнения
3.3.1.	Определить ключевое пространство шифра перестанов-
ки с ключом длины d.
3.3.2.	Зашифровать заданный открытый текст, применяя шифр
перестановки с ключом К = 130614.
3.3.3.	Определить ключевое пространство композиционного
шифра, получаемого с помощью двух ключей — перестановки и
замены длины d.
3.3.4.	Определить различные схемы шифра перестановки, осно-
ванной на кубике Рубика.
3.3.5.	Доказать, что множество всех различных шифров пере-
становок одного и того же алфавита образует группу относитель-
но умножения шифров.
3.3.6.	Определить число двоичных (Р-ичных) циклических по-
следовательностей длины и периода d.
3.3.7.	Для изменения статистических свойств исходного текста
Т воспользуемся методом полиалфавитных подстановок, ключи
которых определяются с помощью не менее двух различных под-
становок и алфавитов.
Пусть шифртекст Е выписывается, например как результат
умножения соответствующих подстановок. По существу таким об-
разом мы имеем ключ длины шифруемого текста. Такой ключ
назовем "бесконечным". Какими преимуществами и недостатка-
ми обладает данный шифр?
3.3.8.	Пусть необходимо зашифровать открытый текст
Т = ПРИМЕР Д1АДЕЖНОГО_ШИФРА
с бесконечным ключом. В качестве ключа К примем произволь-
ный текст длины шифруемого текста Т:
К = МАТЕМАТИКА_ЦАРИЦА_НАУК
а для построения самого шифртекста Е воспользуемся, например,
следующей таблицей:
32
Таблица 6
Т: ПР И ME Р _ НА Д
1101013100
6793673415
К: МАТЕМАТИКА
1010101010
3 1 9 6 3 1 9 9 1 1
+	2121111210
9889989326
Е ЖН О Г О _ ШИ ФРА
001101320210
674545359171
_ ЦА Р ИЦ А _ НАУ К
320102031021
331793134101
031310022201
605235153242
Е:		Ь	С	Ы	rJ1	rJ1	с	rJ1	ц	л	Е	Е	Э	О	Я	М	Д		ш	Ц	X	J4*	
Оценить криптостойкость данного шифра и разработать эф-
фективный алгоритм для его раскрытия.
3.3.9.	Пусть буквы открытого текста Т и ключ К представле-
ны в ASCII-коде. Тогда, независимо от длины ключа, выполнив
сложение Т ф К побайтно, мы получим шифртекст Е, что будет
результатом перестановок букв также в ASCII-коде.
Какими свойствами обладает данный шифр?
3.3.10.	На практике способы шифрования подстановки и пе-
рестановки, как правило, применяются одновременно. Привести
практические примеры СЗИ, которые относятся к симметричным
системам защиты данных.
3.3.11.	Какие существуют разновидности относительно метода
перестановки?
3.3.12.	Сравните между собой два способа шифрования под-
становки и перестановки. Укажите преимущества и недостатки
каждого из них.
33
3.4.	Метод блочных шифров
На практике чаще всего применяются блочные шифры некото-
рой заданной длины, т. е. элементарными сообщениями являют-
ся не отдельные буквы (их можно рассмотреть как блоки длины
один), а отдельные блоки состоящие из двух (биграмм), трех (три-
грамм) и более букв. Шифрование и расшифрование для таких
шифров производятся поблочно.
Для /с-буквенного блока n-буквенного алфавита можно взять,
например, в качестве их числовых эквивалентов числа сегмента
от 0 до пк — 1, рассматривая каждый такой блок fc-разрядное целое
число в системе счисления с основанием п.
Пусть, например, биграмме NO 26-буквенного английского ал-
/ 13 \
фавита соответствует матрица Т — (	1, а шифрующая мат-
рица имеет вид
16 1
21/
Тогда криптограмму Е определим как
„ л /2 3\ /13\	/68
Е = А * Т = I ) I ) — I
V 8/\14/	\203
которому соответствует биграмма QV.
Очевидно для восстановления открытого текста Т необходимо
решить матричное уравнение:
Заметим, что если открытый текст Т состоит из L биграмм, ко-
торым соответствует матрица размерности 2 х L, то аналогич-
но определяются криптограмма Е как произведение двух матриц
А * Т и открытый текст как Т = А-1 * Е.
В более общем случае относительно биграмм открытого текста
можно применить шифрующее аффинное преобразование вида

34
где В — некоторая столбцевая матрица размерности 2 х 1. А для
расшифрования — воспользоваться равенством
Т = А~ХЕ + А~ХВ.
Задачи и упражнения
3.4.1.	Решить следующую систему сравнений
Г2х + Зу = l(mod 26),
+ 8у = 2(mod 26).
3.4.2.	Сколько имеется аффинных шифрующих преобразова-
ний для триграмм (fe-грамм) n-буквенного алфавита?
3.4.3.	Определить количество Np(ax + 5) линейных шифрую-
щих преобразований над полем GF(P).
3.4.4.	Определить количество Np((ax + Ь)/(сх + d)) дробно-
линейных шифрующих преобразований над полем GF(JP).
3.4.5.	Определить количество АГр(А) шифрующих матриц по-
рядка 2 над полем GF(JP).
3.4.6.	Определить количество Np(A * Т + ) шифрующих аф-
финных преобразований над GF(P), если открытый текст разбит
на триграммы (А:-граммы) n-буквенного алфавита.
3.4.7.	Расшифровать сообщение
Т = FBRTLWUGAJQINZTHHXTEPHBNXSW
зашифрованное линейным шифрующим преобразованием три-
грамм 26-буквенного алфавита А — Z с числовыми эквивален-
тами 0—25. Известно, что последние три триграммы — это под-
пись отправителя JAMESBOND. Найти дешифрующую матрицу
и прочитать сообщение.
3.4.8.	Пусть Yk — функция блочного шифрования, К — ее
секретный ключ и
1)	е/ - tj ф Ук(е/-1),	е0 = const,
2)	ej = t/_i ф YK(xi ф	t0 = const,
35
где ® — сложение по модулю 2. Зашифровать текст
Т = БЛОЧНЫЙ_ШИФР
Какими свойствами обладает данный шифр?
3.4.9	(Шифр двойной квадрат). Пусть имеются две табли-
цы со случайно расположенными в них алфавитами (здесь клю-
чами являются сами матрицы).
Каждой паре букв открытого текста сопоставим некоторым об-
разом биграмму букв заданных таблиц.
Определить, какими свойствами обладает данный шифр?
3.4.10.	Рассмотрим несколько простых случаев взаимно-одно-
значных шифрующих преобразований.
1.	Каждой биграмме аЬ сопоставим одно число из сегмента от
О до п2 — 1.
2.	Каждой биграмме ab сопоставим одно число abn = а*п + Ь
— число в системе счисления с основанием п.
3.	Каждой биграмме ab сопоставим одно число по модулю п2.
4.	Каждой биграмме ab сопоставим пару чисел по модулю п
или столбцевую матрицу .
При каком шифрующем преобразовании стойкость соответству-
ющего шифра предпочтительна?
3.4.11.	Каждому /с-буквенному блоку	открытого
текста Т с n-буквенным алфавитом сопоставим число:
(ата^аз ... ак)п = ain 1 + а2пк 2 + а3пк 3 + ... + afc.
Разработать эффективный алгоритм восстановления открытого
текста по криптограмме Е.
36
гаммирования
Под гаммой шифра понимается псевдослучайная последова-
тельность, вырабатываемая по заданному алгоритму, для зашиф-
ровывания открытых данных и расшифровывания зашифрован-
ных данных.
Шифрование методом гаммирования — это наложение по опре-
деленному правилу гаммы шифра на открытые данные.
Псевдослучайной последовательностью (ПСЧ) назовем всякую
последовательность, построенную с помощью некоторого алгорит-
ма.
Так, например, определим последовательность ап с помощью
равенства
ап = [тг1Оп] — [тг1Оп 1
п	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	• • •
Ом	3	1	4	1	5	9	2	6	5	3	5	8	9	7	9	3	2	3	• • •
Одним из хороших конгруэнтных генераторов является ли-
нейный конгруэнтный датчик ПСЧ. Он вырабатывает последо-
вательности псевдослучайных чисел описываемые соотноше-
нием
Xi+i = (A* Xi + C)mod m,
где А и С — константы, Х(0) — исходная начальная величина,
выбранная в качестве порождающего числа. Очевидно, что эти
три величины — А, С, Х(0) и образуют ключ для СЗИ.
Так, например, если Х(0) = А — С = 7, т = 10, то из указан-
ного соотношения получаем следующую, периодическую, длины
4, последовательность:
7, 6, 9, 0, 7, 6, 9, 0, ...
Для шифрования открытых данных методом гаммирования
необходимо к открытым данным обратимым образом (например,
37
с помощью функции XOR — исключающее ИЛИ) наложить нуж-
ную гамму к шифру, получаемую с помощью генератора случай-
ных чисел.
Процесс расшифрования криптограммы сводится к повторной
генерации гаммы шифра при известном ключе и наложению та-
кой же гаммы на зашифрованные данные (так, например, ключ в
случае конгруэнтных генераторов это — Л, С, Х(0)).
Фактически, если период гаммы превышает длину всего за-
шифрованного текста и неизвестна никакая часть исходного тек-
ста, то шифр можно раскрыть только прямым перебором ключа.
Последнее означает, что криптостойкость данной СЗИ определя-
ется размером ключа.
Задачи и упражнения
3.5.1.	Пусть псевдослучайная последовательность (ПСП) опре-
деляется равенством Фибоначчи:
Fn+2 = Fn+1 + Fn(mod т).
Определить период последовательности Фибоначчи при т =
= р(гп = рк).
3.5.2.	Пусть ПСП определяется нелинейным равенством:
Хп+1 = (АХп2 + ВХп + C)mod т.
Определить период этой последовательности, если коэффициенты
Л, В, С и модуль т — элементы поля GF(p).
3.5.3.	Приведите недостатки метода шифрования на примере
ситуации, когда результатом атаки служит фрагмент исходного
текста и соответствующей криптограммы.
3.5.4.	Пусть ПСП определяется равенством
^п+1 “ (АХп + ВХП_1 + C)mod р.
Определить наибольший период этой ПСП при заданных це-
лых чисел Xq, Xi, А, В и С.
38
3.5.5.	Рассмотрим алгоритм:
Si = ASq + С (mod m),
S2 = ASi + C(mod m),
Sl — ASl-i + C(mod m),
который определяет последовательность порождающих чисел: Si,
S2, ..., Sl. Определить L при известном значении Sq.
3.5.6.	Разработать алгоритм атаки на криптосистему, постро-
енную методом гаммирования.
3.5.7.	Пусть линейный конгруэнтный датчик ПСЧ описывает-
ся соотношением
-Xj+i = (А * Xi + C)mod т.
Значение т обычно устанавливается равным 2П или 2П-1,
где п — длина машинного слова в битах. При этом необходимо
выбирать числа А и С таким образом, чтобы период последова-
тельности был максимальным.
Доказать, что линейный конгруэнтный датчик ПСЧ имеет мак-
симальную длину т тогда и только тогда, когда С — нечетное, и
A mod 4 = 1.
3.5.8.	Доказать, что над конечным полем GF(pk) последова-
тельность случайных чисел, определяемая равенством
Хп ~	1 4" аъХп—2 + ... + &kAn_k)mod р
имеет длину периода рк — 1 тогда и только тогда, когда нормиро-
ванный полином
f(x) = хк — а\хк~х — а2Хк~2 — ... — ак
является примитивным с коэффициентами из поля GF(p).
3.5.9.	Доказать, что над каждым полем GF(pk) существует
примитивный полином любой положительной степени.
3.5.10.	Определить число примитивных элементов поля GF(pk).
39
3.5.11.	Минимальным полиномом элемента а над полем GF(p)
называется нормированный полином М[х) с коэффициентами из
GF(p) наименьшей возможной степени такой, что М(а) = 0.
Какими свойствами обладает полином М(х)?
3.5.12.	Доказать, что при р = 2 гарантированно можно стро-
ить последовательность случайных чисел наперед заданной дли-
ны.
3.5.13.	Доказать или опровергнуть гипотезу Артина: элемент
2 является примитивным для бесконечного класса простых полей
GF(p).
3.6.	Метод шифрования на основе
теоремы Эйлера—Ферма
Данная система шифрования основана на применении теоремы
Эйлера—Ферма о представлении простого числа Р в виде:
X2 + kY2 = P, к = 1,2,3
и наложении последовательности случайных чисел с последую-
щими перестановками шифртекста. Здесь к используется в ка-
честве текущего ключа совместно с заранее выбранными п про-
стыми числами и последовательностью псевдослучайных чисел.
Отметим, что выбор простых чисел pi, Р2 ? • • • ,Рп зависит от к сле-
дующим образом:
)4t + 1,	если к — 1,
8i + 1, 8t + 3, если к = 2,
6i + 1,	если к = 3.
Как известно, при указанном выборе pi соответствующее ему урав-
нение разрешимо в целых и взаимно простых числах ж, у с усло-
вием х притом единственным способом, что позволяет за-
шифровать открытый текст Т и расшифровать криптограмму Е
однозначно.
40
Если Р очень большое простое число, то для определения х и
у криптоаналитику потребуется много времени для решения со-
ответствующего сравнения, так как кроме простого перебора нет
быстрых алгоритмов отыскания их решений.
Задачи и упражнения
3.6.1.	Доказать, что если Р = l(mod 4), то Р можно предста-
вить в виде суммы двух натуральных чисел единственным спосо-
бом. С учетом доказанного зашифровать текст:
Т = XOTHAR_KHOTAL
3.6.2.	Доказать теорему Эйлера—Ферма о представлении про-
стого числа Р в виде X2 + kY2 — Р, к = 1,2,3.
3.6.3.	Можно ли строить СЗИ на основе следующей проблемы
Гольдбаха: любое четное число п > 6 можно представить в ви-
де суммы двух простых чисел, а любое нечетное число — в виде
суммы трех простых чисел.
3.6.4.	Нечетное составное число п назовем псевдопростым по
основанию 6, если (п, 6) = 1 и выполняется условие:
bn-1 = l(mod п).
Доказать, что число п является псевдопростым по основанию
b тогда и только тогда, когда порядок числа Ъ делит п — 1. (Так,
например, число п = 91 — псевдопростое по основанию Ь — 3, так
как З90 = l(mod 91).)
3.6.5.	Доказать, что первые п простых чисел pi = 2, р% =
= 3,... ,рп связаны соотношением
п
Р,П(1-1/^) = 1+	{Pn/d}^d), neN.
i=l	dlpi...pn
41
3.7.	Композиция шифров
Пусть имеется СЗИ 5, построенная из различных простых под-
систем 51,52,.. •, Sm (в частности, можно полагать, что 51 — это
СЗИ на основе шифра простой замены, 52 — СЗИ на основе шиф-
ра перестановки и т. д.).
Две системы 5 и R назовем эквивалентными (5 О 7?), ес-
ли обе они произвольный открытый текст Т переводят в одну и
ту же криптограмму Е. При этом, если 5 и R состоят из т и
п простых подсистем соответственно, то в практическом плане
предпочтительна та система, которая состоит из меньшего числа
простых подсистем. Такую систему назовем оптимальной систе-
мой защиты информации.
Обозначим через К2,..., Кт ключи простых подсистем
Si, 52,..., Sm соответственно, а через
S[k] = S[K1,K2,...,Km]
— СЗИ 5 с результирующим составным ключом К =	0 К2 0
• • • 0 Кт.
Таким образом построенный шифр назовем композицией шиф-
ров, а саму СЗИ — композиционной шифросистемой.
Далее, пусть для определенности алфавит сообщений имеет
вид
{1,2, ...,т},
а ключи шифров замены и перестановки имеют вид
где /1,12,...,/ш — все различные буквы нашего алфавита, а
<71, <72, • • •, Jd ~ все различные числа из множества {1,2,..., d},
т > d.
Так, например, если т — 6, d = 2, то при = 561324,
К2 = 21 для следующего текста сообщений Т = 13614225 име-
ем:
42
ЕК1(Т) = 51453662 -7i;
Ek2(Ti) = 15546326 -72
— КОМПОЗИЦИЯ двух шифров С КЛЮЧОМ К = К\ ® К%-
Очевидно, применяя обратную процедуру относительно 72, а
затем и к 71, тем самым выполним расшифровку исходного текста
Задачи и упражнения
3.7.1	(Тюремная азбука — аналог шифра Полибия).
Пусть буквам русского алфавита (без букв ё, й, ъ) сопоставле-
ны пары чисел (количество стуков) — номер строки и столбца, в
которых расположена данная буква (например О — 32, В — 13 и
т. д.), исходя из следующей табл. 7:
Таблица 7
	1	2	3	4	5	6
1	А	Б	в	Г	Д	Ej
2	Ж	3	и		л	м
3	Н	О	п	р	с	т
4	"'у	Ф		ц	ч	ш
5	щ	Ь	ы	э	ю	я
Так, например, вопрос: ’’КТО ТАМ?” с помощью этого шифра
представляется:
Зашифровать открытый текст: Т = ТЮРЕМНАЯ АЗБУКА.
Является ли данный шифр моноалфавитным? Какими свойства-
ми он обладает?
3.7.2.	Определить простые ключи шифртекста:
Е = ТЕАГАШ_НАВАРАК_ТЕАЛ_АКАБОС
и расшифровывать его.
43
3.7.3.	Пусть имеется открытый текст
Т = ШИФР КОМПОЗИЦИЙ
Можно ли построить СЗИ, которая открытый текст Т инверти-
рует?
3.7.4.	Можно ли построить СЗИ, которая открытый текст:
1)	Т = Б_АЛЕКСАНДР_В шифрует в криптограмму Е =
=Б_АРТУР_В?
2)	Т = ОВЕН шифрует в криптограмму Е = ПАУК?
3)	Т — МАРАНД шифрует в криптограмму Е = АХБЮУР?
3.7.5.	Пусть А = {1,2,..., т} — алфавит сообщений, а АГт(Л1,
.. ,Кт) — число всех шифров замен с ключом К = Ki,
А2,..., Кт. Определить Nm(Ki,K2,..., Кт) для любого т.
3.7.6.	Пусть А = {1,2, ...,т} — алфавит сообщений. Nd(Ki,
Ki, - • • ^Kd) — число всех шифров перестановок с ключом КП=
= АГ1,АГ2, • • •, Kd длины d.
Определить Nd^K^K^ ..., Kd) для длин d = 1,2,3,..., т.
3.7.7.	Пусть КЗ = Ki, К2,. •., Кт — ключ моноалфавитного
шифра замены, а КП= Ai, , Кп — ключ моноалфавитного
шифра перестановки.
При каких т, пи Kj соответствующие им СЗИ эквивалентны?
3.7.8.	Решить предыдущую задачу 3.7.7 для полиалфавитного
случая.
3.7.9.	Рассмотреть вопрос минимизации числа простых подси-
стем, композиция которых реализует оптимальную систему. Дру-
гими словами, необходимо определить простые ключи К?,...
..., Кт, следовательно, и сами подсистемы Si, S2,..., Sm СЗИ S
таким образом, чтобы полученная система R[Ki\, , К/г
была оптимальной относительно системы S, т. е. чтобы выпол-
нялись условия:
1)	S[K1}K2,	Л[Кп,К12,К1г];
2)	т > г.
Решить задачу для элементарных подсистем.
44
3.8.	Симметричные системы защиты
информации
Абсолютно все рассмотренные ранее примеры и задачи отно-
сятся к симметрическим системам защиты информации, к так на-
зываемым классическим системам, и их можно представить такой
диаграммой:
Vt^Ve^ Vt.
Характерная черта этих криптосистем заключается в том, и
отправитель, и получатель информации используют один и тот
же секретный ключ, хотя они могут быть в общем случае не со-
всем одинаковыми. Важно то, что имея данные о шифровании
открытого текста, можно реализовать расшифрование шифртек-
ста примерно за такое же время, что и шифрование открытого
текста.
Кроме того, если симметрическая система защиты информа-
ции построена с помощью ключей Ке и Kd соответственно, то,
очевидно, ключ расшифрования Kd определяется на основе клю-
ча шифрования Ке, причем предполагается, что ключ Ке дол-
жен храниться в тайне и передаваться способом, исключающим
его перехват.
В данном случае криптостойкость системы зависит только от
длины ключа, так как чем длиннее ключ, тем меньше вероятность
выбора правильного ключа со стороны ПППА.
Задачи и упражнения
3.8.1. Пусть для построения симметрической системы приме-
няется сравнение у = х + fc(mod п), где х — буква алфавита сооб-
щения, состоящего из п элементов, у — его шифр, к — симметри-
ческий секретный ключ.
Определить пространство ключей для русского алфавита и за-
шифровать сообщение:
45
Т = С??ЗД Ц?ЛИ??М ? П?ЛН???ЬЮ ОД??РИ? М??ОПР??
Т?Я Ц? ПАР??? ?0 ??РЬБ? ? ?А?О?ОМ с помощью секретного
ключа к = 13.
3.8.2. Пусть Т = ЯСНОЕ_СТАНОВИТСЯ_НЕПОНЯТНЫМ
— открытый текст. Необходимо зашифровать его по ключу К =
3.8.3. Пусть буквы латинского алфавита расположены в таб-
лице 5X5 случайным образом, причем столбцы и строки пронуме-
рованы также случайно — цифрами пятеричной системы. Букве
Ы/j сопоставим пятеричное число 5 * I + j.
Повторить указанные операции К раз, а затем зашифровать
текст Т = DROBNIE.SHIFRI.
Оценить криптостойкость полученной системы.
3.8.4 (Одиночная перестановка по ключу). Пусть ключ
К имеет вид: К — ВАЛКАР, а исходный открытый текст пред-
ставлен по строкам в таблице следующим образом:
3 1 5 4 2 6
ВАЛКАР
т	О	л	ь		О
—		л	я	—	с
т	у	д		н	т
О	в		ф	п	м
	к	у	Б	г	у
Тогда после одиночного шифрования по ключу К — ВАЛКАР по-
лучаем следующий шифртекст: Е = ОКТЬЛО Д_ЯЛС УНТЕДТ
ВПОФМ КГ-БУУ.
Зашифровать текст по ключу К = МАРАНД. Определить чис-
ло всех ключей.
3.8.5 (Двойные перестановки столбцов и строк). Пусть
ключ по столбцам КК имеет вид: КК = ВАЛКАР; ключ по стро-
кам KS имеет вид: KS = ВЭТЭС.
Зашифровать открытый текст из предыдущей задачи 3.8.4,
46
применив ключи КК и KS. Определить число всех ключей ана-
логичного вида.
3.8.6. Пусть в условиях задачи 3.8.4 применяются двойные пе-
рестановки столбцов и строк один раз, затем к полученному шиф-
ру еще раз и т. д.
Через сколько таких перестановок впервые появится исходный
открытый текст?
3.8.7 (Криптосистема Хилла). Пусть К =	— квад-
ратная обратимая матрица размерности п х п и Т = (iu)h —
исходный открытый текст, представленный по строкам матрицы
размерности п х I. Тогда шифртекст определим как строки мат-
рицы произведения: С = К *Т. Зашифровать открытый текст из
задачи 3.8.4, применив ключ К = Определить число всех
ключей аналогичного вида, если алфавит состоит из m букв.
3.8.8 (Шифрование с помощью аффинных преобразо-
ваний). Пусть функция шифрования определяется сравнением
у = Кух + K2(mod n2), (Ki,n) = 1,
где х — буква алфавита сообщений, состоящего из п элементов, у
— его шифр, К = (Ki,J<2) ~ симметрический секретный ключ.
3.8.9 (Шифр Плейфейра). Пусть все буквы латинского ал-
фавита, кроме J, расположены в квадрате 5x5 произвольным
образом, например:
S Y D W Z
R I Р U L
Н С А X F
Т N О G Е
В К М Q V
Пусть исходный текст разбит должным образом на биграммы, и
пусть каждой биграмме VО соответствуют угловые буквы прямо-
угольника ME. Если же буквы биграммы НА попадают в одну и
ту же строку (соответственно столбец), то необходимо циклически
смещаться на один шаг вправо (соответственно вниз) СХ.
47
Расшифровать текст:
Т = CHARTAR AYRENIC AZIZYAN IN NKAO
Является ли данная система шифрования многоалфавитной?
3.8.10 (Парный шифр). Пусть ключ состоит из фразы, со-
держащей 15 разных букв русского алфавита (без букв ё, й, ъ),
например:
К = МАТЕМАТИКА СПРАВЕДЛИВА КАК БОГ
Подписывая ключ под алфавит и сопоставив каждой букве из
алфавита, состоящего из 30 букв, одну из букв ключа (повтор не
в счет), получим отображение букв алфавита на последователь-
ность, состоящую из тех же букв:
1	2	3	4				5	6			7	8	9	
м	А	т	Ej	м	А	Т	И	К	А		С	П	Р	А
	3	н	У				Ф				Ц		ш	
Е = ЮХУЗТБНЮАЬЮШЮЩЮ
Какими свойствами обладает данный шифр? Указать его силь-
ные и слабые стороны. Какое обобщение имеет данный шифр?
Можно ли путем перестановок букв указанного ключа из откры-
того текста Т = ЛЮДМИЛА получить шифртекст Е = СВЕТУ-
ЛЯ?
48
3.9.	Стандарт криптосистемы США —
DES
Наиболее широко известна симметричная криптосистема
шифрования данных — стандарт DES (Data Encryption Standard,
1977 г.) — федеральный стандарт США. DES-алгоритм был раз-
работан специально для электронных устройств для зашифровки
и расшифровки данных. Зашифровка и расшифровка, согласно
DES, осуществляются одной и той же ключевой системой К =
— {^i,	5 &1б}> каждый из которых имеет длину 48 бит.
Процесс шифрования состоит в начальной IP перестановке 64-
битового входного блока Т, шестнадцати циклах шифрования и
конечной JP-1 перестановки. Более полное описание данного ал-
горитма можно найти в известных источниках. Здесь мы приво-
дим лишь блок схему этого алгоритма (см. рис. 3).
Имея построенные Ln_\ и Rn-i для 1 < п < 16, мы определим
Ln и Rn как
Ln ~ Rn—1, Rn — Ln_i ф f (Rn—i, Kn),
где ф означает побитовое сложение по модулю 2, а / — функция
шифрования.
Расшифрование осуществляется в обратном порядке. Оно дей-
ствительно очень просто: указанные равенства могут быть пере-
писаны в виде
Rn—i — Ln>
и, таким образом, ’’спуститься” от Liq и R^q к Lq и Rq, после чего
расшифрование очевидно.
Отметим, что DES-алгоритм работает быстро и обладает очень
желательной с точки зрения секретности особенностью: незна-
чительное изменение исходного сообщения или ключа приводит
к большим изменениям в криптотексте. Кроме того, криптоана-
лиз приводит к многочисленным нелинейным системам уравне-
49
Вход (64 бит)
1
Конечная перестановка IP -1
Выход (64 бит)
Рис. 3
50
ний, т. е. возникающие при этом задачи будут по крайней мере
NP-полными.
Отметим также, что новый стандарт симметричного крипто-
алгоритма США является AES.
Задачи и упражнения
3.9.1.	Выписать ключи Ке и Ке для СЗИ DES.
3.9.2.	Влияют ли на криптотойкость DES перестановки IP и
ZP-1?
3.9.3.	Оценить криптостойкость системы DES. Какие сильные
и слабые места криптосистемы DES?
3.9.4.	Разработать программу, реализующую криптосистему
DES.
3.9.5.	При зашифровании очередного блока Т системы DES
его биты подвергаются начальной перестановке IP:
58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	И	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7
Определить конечную перестановку 1Р~\
51
3.10.	Стандарт криптосистемы
России — ГОСТ 28147-89
Чтобы получить подробные спецификации алгоритма крипто-
графического преобразования, следует обратиться к ГОСТу 28147-
89. Мы рассмотрим лишь основные принципы реализации крип-
тографического преобразования, так как они во многом сходны с
алгоритмом DES. Схема алгоритма шифрования имеет вид:
Рис. 4- Схема алгоритма ГОСТа 28Ц7-89
52
При описании алгоритма используются следующие обозначе-
ния:
М,ЛГ2 ~ 32-разрядные накопители;
СМ\ и СМ2 — сумматоры по модулю 232 и 2 двух 32-разрядных
двоичных чисел соответственно;
КЗУ — ключевое запоминающее устройство объемом 256 бит,
состоящее из восьми 32-разрядных накопителей;
R — 32-разрядный регистр циклического сдвига.
Алгоритм криптографического преобразования предусматри-
вает несколько режимов работы. Но в любом случае для шиф-
рования данных используется ключ, который имеет размерность
256 бит и представляется в виде восьми 32-разрядных чисел Х(г).
Если обозначить ключ через К, то
К = Х(7)Х(6)Х(5)Х(4)Х(3)Х(2)Х(1)Х(0).
Первый и самый простой режим работы алгоритма — замена.
Открытые данные, подлежащие зашифровыванию, разбивают на
блоки T(J) по 64 бит в каждом.
Очередная последовательность бит T(j) разделяется на две
подпоследовательности В(0) (левые, или старшие, биты) и А(0)
(правые, или младшие, биты), каждая из которых содержит 32
бита. Затем выполняется итеративный процесс шифрования, ко-
торый описывается следующими формулами:
L ГЛ(/) = f(A(I - 1)[+]X{j) ф В(1 - 1)),
|^В(/) = А(1 — 1), если I = 1... 24, j — (J — l)mod8;
2 Г АЩ = f(A(I - l)[+]X(j) Ф В(1 - 1)),
’ |в(/) = A(I- 1), если Z = 25,26,... ,31, j = 32 - i;
3 р(32)=А(31),
’ (В(32) = /(А(31)[+]Х(0)) Ф В(31), если I = 32.
Здесь г, i = 1... 32 обозначает номер итерации, a f — функция
шифрования. Ее аргументом является сумма по модулю 232 числа
53
А(г), полученного на предыдущем шаге итерации, и числа X(j)
ключа.
Функция шифрования включает две операции над полученной
32-разрядной суммой. Первая операция называется подстановкой
S.
Вторая операция — циклический сдвиг влево на 11 позиций
32-разрядного вектора, полученного в результате подстановки S.
Результатом зашифрования блока То является блок 7ш и пред-
ставляется в виде:
Тш - Л(32)В(32).
Следующий режим шифрования — режим гаммирования. От-
крытые данные, разбитые на 64-разрядные блоки Т(г) (г — 1... т,
где m определяется объемом шифруемых данных), зашифровы-
ваются в режиме гаммирования путем поразрядного сложения по
модулю 2 с гаммой шифра Г пт, которая вырабатывается блоками
по 64 бит, т. е.
ГШ = (Г(1), Г(2),..., Г(г),... ,Г(т)).
Уравнение зашифрования данных в режиме гаммирования мо-
жет быть представлено в следующем виде:
Ш(/) = Л(У(/-1)[+]С'2),
z(i - i){+}ei ф т(г> = г(/) © т(1),
Гш = (Г(1),Г(2),...,ГЦ),...,Г(т)).
В ГОСТе 28147-89 определяется процесс выработки имитовстав-
ки, который единообразен для любого из режимов. Из-за зна-
чительно большей длины ключа он является существенно более
стойким, нежели DES.
54
Задачи и упражнения
3.10.1.	Выписать ключи Ке и Kjj для СЗИ ГОСТ 28147-89?
3.10.2.	Первый и самый простой режим работы алгоритма
ГОСТа 28147-89 — замена. Описать алгоритм замены.
3.10.3.	Разработать алгоритм для реализации шифрования от-
крытых данных в режиме гаммирования.
3.10.4.	Оценить криптостойкость системы ГОСТ 28147-89. Ка-
кие сильные и слабые места она имеет?
3.10.5.	Провести сравнительный анализ систем ГОСТ 28147-
89 и DES.
3.10.6.	Разработать программу, реализующую криптосистему
ГОСТа.
55
ГЛАВА 4
СИСТЕМЫ ЗАЩИТЫ ИНФОРМАЦИИ
С ОТКРЫТЫМ КЛЮЧОМ.
АСИММЕТРИЧНЫЕ СИСТЕМЫ
4.1.	Асимметричные системы защиты
информации
В асимметричных системах для зашифровывания открытых
данных используется один ключ Ке, который не является сек-
ретным, а для расшифровывания — другой Ке, являющийся сек-
ретным. При этом сам ключ расшифровывания выбирается адре-
сатом самостоятельно в отличие от симметричных криптосистем.
По определению криптосистема с открытым ключом обладает тем
свойством, что знание функции шифрования не позволяет по клю-
чу шифрования Ке найти ключ расшифрования Ке, избежав
чрезвычайно больших вычислений, хотя эти ключи математиче-
ски тесно связаны между собой. Другими словами, шифрующая
функция F легко вычисляется по ключу Ке, но вычислять зна-
чения обратной функции F' без дополнительной информации о
ключе расшифрования Ке ~ весьма трудно разрешимая в вы-
числительном отношении задача.
А что касается смысла названия ’’системы с открытым клю-
чом", то его надо воспринимать как СЗИ, ключ шифрования ко-
торой — Ке — без особого риска общедоступен для всех пользо-
вателей.
Задачи и упражнения
4.1.1.	Какие асимметричные СЗИ вы знаете?
4.1.2.	Чем отличается асимметричная СЗИ от симметричной?
Какие преимущества и недостатки имеют асимметричные СЗИ?
4.1.3.	Можно ли из симметричной СЗИ синтезировать асим-
метричную СЗИ? А наоборот? Приведите примеры.
56
4.1.4.	Привести пример асимметричной СЗИ с указанием Ке
и Кр> и зашифровать текст
Т = ГРАЧ_ХМЕНК_ЫНКЕРНЕР_КЕНАЦЫ_КОТНАЛИ
4.1.5.	Пусть функцией шифрования является функция
Fp(x) = Т2001 + «1Т1001 + (12^101 + а3
с коэффициентами из поля характеристики р. При каких р функ-
цию Fp(x) можно рассмотреть как одностороннюю функцию?
4.1.6.	Пусть функцией шифрования является функция Ер(т) =
= ах, где а — примитивный элемент простого поля GF(P).
Решить уравнение ах = Y для заданного и известного у.
4.1.7.	Пусть функцией шифрования является функция Fq(x) =
= где а — примитивный элемент составного поля GF(q).
Решить уравнение ах = Y для заданного q и известного у.
4.1.8.	Разработать эффективный алгоритм синтеза асиммет-
ричной СЗИ. Рассмотрите вопросы шифрования и расшифрова-
ния таких криптосистем.
4.2.	Примеры асимметричных систем
защиты информации
Рассмотрим следующие общеизвестные и их различные вари-
анты модификации систем защиты информации с открытым клю-
чом.
Следует отметить, что в целом асимметричные системы защи-
ты информации значительно медленнее симметричных СЗИ. По-
этому разумнее использовать их в качестве дополнения к симмет-
ричным криптосистемам, с помощью которых и передается сооб-
щение.
Это означает, что на практике рекомендуется процедуру со-
гласования ключей СЗИ реализовать с помощью эффективных
57
асимметричных криптосистем, а зашифровывать открытый текст
— симметричной криптосистемой.
Отметим также, что здесь основным преимуществом является
установление секретного ключа без всяких посредников.
4.2.1.	Числовой вариант системы защиты RSA
Данная система — RSA — была разработана в 1978 г. Разра-
ботчиками был предложен пример функции шифрования, опреде-
ляемый чрезвычайно трудной задачей — полной факторизацией
большого составного целого числа при неизвестных заранее про-
стых его множителях. При этом учитывается тот факт, что если
р — взаимно простое относительно то существует целое d,
такое, что
р* d = l(mod
На этих математических фактах и основан популярный алгоритм
RSA.
Чтобы использовать на практике числовой вариант системы
RSA, необходимо сначала сгенерировать открытый и секретный
ключи, выполнив следующие шаги:
1.	Выбрать два произвольных очень больших простых числа
и q;
2.	Определить п как результат умножения р на q, т. е. п — p*q\
3.	Выбрать любое большое число L между 1 и ф(п) такое, что
((р - 1) * (g - 1), £) = 1 или (</>(n), £) = 1;
4.	Определить такое число S, для которого выполняется соот-
ношение:
L* S = 1((р — 1) * (q — 1)) или S = L 1mod
5.	Установить Ке = {Д п} как открытый ключ, а Ке — {S', п}
— секретный ключ.
Таким образом, для числового варианта системы RSA имеем
следующую функцию шифрования:
F(t) = tL mod (п)
58
и соответствующую функцию расшифрования:
F-1(c) = cs mod (n).
4.2.2.	Многопользовательский вариант
системы защиты RSA
Для простоты изложения рассмотрим случай, когда п равен
произведению трех простых чисел. Пусть, например:
п = рг * Р2 * Рз, т — ф(п) = (Pi - 1) * (Р2 - 1) * (Р3 - 1).
Как и в предыдущем случае, выберем один открытый ключ
Ke — {L,n} и, например, два секретных ключа K^i = {5i,n} и
— {^2,71}, исходя из условия:
L * S\ * S2 = 1 mod (m).
В данном случае мы разделяем общий секрет S как бы на две
части 51 и 52, что существенно в тех случаях, когда участники
СЗИ не доверяют друг другу.
Так, например, при Pi = 3, Р2 = 7, Рз — И имеем:
n = PiP2P3 = 231, m = (/>(231) = 120,
и в качестве открытого ключа возьмем Ке = {13,231}, а в каче-
стве двух других секретных ключей — K^i = {11,231} и К^2 —
= {47,231} соответственно.
Пусть
Т = ВАС АВ АВ
— исходный открытый текст. Тогда после шифрования (здесь функ-
ция шифрования — F(t) = tL mod (n)) с помощью открытого клю-
ча получаем:
F(l) - I13 mod (231) = 1;
Р(2) - 213 mod (231) = 107;
Р(3) = З13 mod (231) = 192.
59
И первую криптограмму:
Ех = 107 1 192 1 107 1 107.
Теперь после преобразования = 107 1 192 1 107 1 107 вто-
рым пользователем со своим ключом Кщ = {11,231} получается
криптограмма
Е2 = 74 1 159 1 74 1 74,
так как
F(l) = I11 mod (231) = 1;
F(107) = 10711 mod (231) = 74;
F(192) = 19211 mod (231) = 159.
Наконец, после преобразования
E2 = 74 1 159 1 74 1 74
третьим пользователем с ключом Кр2 = {47,231} окончательно
получается исходный открытый текст:
7ч = 2131212 или Т = ВАС АВ АВ, так как
F(74) = 7447 mod (231) = 2;
F(l) = I47 mod (231) - 1;
F(159) - 15947 mod (231) = 3.
Аналогично можно применить более сложные варианты модифи-
кации системы RSA, когда число участников более трех, а для по-
давления частот встречаемости букв применяется некоторая по-
лиалфавитная криптосистема.
4.2.3.	Полиномиальный вариант системы
защиты RSA
Чтобы использовать на практике полиномиальный вариант си-
стемы RSA, аналогично, необходимо сначала сгенерировать от-
крытый и секретный ключи, выполнив следующие шаги:
60
1.	Выбрать два очень больших простых над GF(P) полинома
р(х) и q(x) степеней и и v соответственно;
2.	Определить п(т) как результат умножения р(х) на <?(т), т. е.
п(т) = (т) * <?(т);
3.	Выбрать случайный полином L(x) большой степени такой,
что
((р(ж) - 1) * (q(x) - l),L(x)) = 1;
4.	Определить такой полином 5(т), для которого выполняется
соотношение:
* L(x) = 1 mod (((т) — 1) * (<?(т) — 1));
5.	Установить Ке — {L(x),n} как открытый ключ, a Kd =
— {5(т),п} — секретный ключ. Существование указанных про-
стых над GF(P) полиномов гарантируется соотношением — число
/р(п) простых над GF(P) полиномов степени п больше или равно
единице.
Этапы шифрования открытого текста и расшифрования крип-
тограммы соответствуют этапам предыдущих двух вариантов, по-
этому здесь их не рассматриваем.
Задачи и упражнения
4.2.1.	Построить пример системы RSA для полиномиального
варианта над полем GF(2).
4.2.2	(Малая теорема Ферма). Доказать, что если р — про-
стое число, то = l(modp) для любого х, простого относи-
тельно р, и хр = т(тобр) для любого х.
4.2.3.	Определить ф(п) для любого п и сравнить его с соответ-
ствующими значениями для малых п, приведенных в следующей
таблице:
п 23456789 10 11 12
ф(п) I 1 2 2 3 2 6 4 6 4 16 4“
4.2.4.	Доказать, что если п — р* q (р и q — отличные друг от
друга простые числа), то ф(п) = (р — l)(g — 1).
61
4.2.5.	Доказать, что если п = р* q, (р и q — отличные друг
от друга простые числа) и х — простое относительно р и <?, то
ХФМ — i(modn).
4.2.6.	Доказать, что если п = p*q, (р и q — отличные друг от
друга простые числа), и I простое относительно <^(п), то отобра-
жение
Е: х —+ j/(mod п)
является взаимно однозначным на Zn.
4.2.7.	Доказать, что если (т — 1)! + 1 делится на т, то т —
число простое.
4.2.8.	Для успешного решения проблемы практической реа-
лизации системы RSA необходима генерация больших простых
чисел.
Разработать эффективный алгоритм генерации больших про-
стых чисел.
4.2.9.	Построить криптосистему RSA для всех трех вариантов
и зашифровать текст:
Т = ПАУК_НА_СУРАНЕН_КЕРЦЕ
4.2.10.	Пусть буквам А, В, С соответствуют числовые экви-
валенты 1, 2, 3 соответственно. Если в качестве открытого текста
взять фразу
Т = ВАС АВ АВ
то с учетом, что п = 33 (количество букв исходного открытого
текста) при р = 3, q = 11, Ке = {7,33}, Ке = {3,33}, получим
числовой эквивалент
Тч = 2 1 3 1 2 1 2.
Теперь зашифруем Г, используя открытый ключ Ке = {7,33}.
Имеем:
F(l) = I7 mod (33) = 1;
F(2) = 27 mod (33) = 29;
F(3) = 37 mod (33) = 9,
62
следовательно, получаем следующую криптограмму:
Е = 2919129129.
А теперь по криптограмме Е = 29 1 91 29 129, на основе сек-
ретного ключа Кр — {3,33}, получаем открытый текст
Т = ВАС АВ АВ,
так как
F-1(l) = I3 mod (33) = 1;
F-1(9) = 93 mod (33) = 3;
F-1(29) = 293 mod (33) = 2.
Разработать алгоритм реализации числового варианта метода
RSA.
4.2.11.	Разработать эффективный алгоритм генерации боль-
ших простых над GF(P') полиномов степени п, число 1р(п) кото-
рых больше или равно единице.
4.3.	Система защиты информации
Диффи—Хеллмана
Пусть GF(q) — поле Галуа порядка q. Тогда для любых двух
элементов а и & из мультипликативной группы GF*(c[) сравнение
ах = b(modp)
всегда разрешимо относительно х.
Целое число х из GF(q), удовлетворяющее указанному сравне-
нию, называется индексом, или дискретным логарифмом числа b
по основанию а, и формально записывается: х = loga 6.
Так, например, для простого поля Галуа GF(5) = {0,1,2,3,4}
сравнение
Зж = 4(mod5)
63
имеет решение х = log3 4 = 2.
А для составного поля Галуа GF(9), в котором элемент а —
примитивный корень уравнения
X2 + 2Х + 2 = 0, т. е. а2 + 2а + 2 = О,
имеем
logQ(—1) = 4, так как а4 = —1.
Необратимость криптографического преобразования в данном
случае обеспечивается тем, что достаточно легко вычислить пока-
зательную функцию у = ах в конечном поле Галуа, состоящего из
q элементов (q — либо простое число, либо степень простого). Вы-
числение же логарифма х — loga у в таких полях — значительно
более трудоемкая операция, чем и определяется криптостойкость
данного метода.
Пусть исходные значения q (порядок поля) и а (некоторый
фиксированный элемент поля GF(q), на практике а — прими-
тивный элемент) — общедоступны.
Приведем алгоритм установления общего секретного ключа
для системы Диффи—Хеллмана:
1.	Выбрать случайное число a, 1 < а < д;
2.	Вычислить Т — ыа mod q и отправить получателю;
3.	Получатель выбирает случайное число &, 1 < Ь < q и вычис-
ляет Н = ab mod д, затем посылает отправителю;
4.	Получатель вычисляет К± = Tb = aab mod д;
5.	Отправитель вычисляет К% = На = ааЬ mod q = К\.
Задачи и упражнения
4.3.1.	Построить таблицы логарифмов для элементов полей
GF(8) и GF(9).
4.3.2.	Построить таблицу логарифмов для GF (31) и восполь-
зоваться ею для вычисления 13 *7, 19 * 13, 29 * 17, 29/7, 13/23.
4.3.3.	Построить пример установления общего секретного клю-
ча между двумя участниками в случае простого поля GF(101) и
64
зашифровать повторно текст сообщения Т = МАРАНД — ЭТО
АХБЮУР.
4.3.4.	Модифицировать криптосистему Диффи—Хеллмана на
случай, если число участников больше или равно трем.
4.3.5.	Пусть применяется функция шифрования /(а?) = х+
+13(mod 44) к открытым данным из 44 букв в поле Галуа GF(101).
Организовать обмен ключами и секретно передать информацию:
Т = ПОРА ДЕЛИТЬСЯ С СЕКРЕТАМИ
4.3.6.	Разработать алгоритм атаки на криптосистему Диффи-
Хеллмана с целью установления секретного ключа.
4.3.7.	Известно, что 2 является примитивным элементом для
бесконечного класса простых полей Галуа. Определить первые сто
таких полей.
4.4.	Система защиты информации
на основе заданного рюкзака
Пусть заданы рюкзачный вектор из п > 3 различных нату-
ральных компонентов
и натуральное число V. Требуется, если это возможно, найти та-
кой n-разрядный двоичный набор
w - (ai,a2,...,an),
где ап € {0,1}, чтобы выполнялось равенство:
п
ajaj = V.
1=1
Входом задачи о рюкзаке назовем пару (А, V), а его решением
— подмножество элементов А, сумма которых равна V.
65
Так, например, если а = (1,6,13,21), а V = 35, то w = (1,0,1,1)
и для входа (Л, 35) имеем решение — (1,13,21).
Если вектор
— (&15	• • • ? &п)
сверхрастущий, т. е. его компоненты удовлетворяют неравенству
а/ > Q1 * ai + Q2 *	+ • • • + <^Z-1 * &Z-1, а £ {0, 1},
для любого I, то функция F(V) определена для всех допустимых
V	F(0) = F(00... 00) = О,
F(l) = F(00...01) = ab
F(2n - 1) = F(ll... 11) = ai + a2 + ... + an.
Используя векторное умножение, мы можем записать функ-
цию шифрования в виде
F(x) = А*ВХ,
где Вх — вектор-столбец двоичного представления х. Причем дли-
на Вх определяется исходя из количества элементов алфавита со-
общений.
В качестве секретной лазейки для легального пользователя
можно выбрать числа е , е-1 и т или секретную пару (е, т), где
т = max{ai}, (m,e) = 1. Тогда по идее рюкзачной системы неле-
гальный пользователь должен анализировать шифртекст, исходя
из другого рюкзачного вектора
в = (ЬъЬ2,..,.Ьп),
где
bn = е * an(mod т)
для всех индексов п.
Относительно вектора В говорят, что он получен из вектора А
с помощью сильного модульного умножения.
66
Так, например, для приведенного вектора
А - (1,2,6,11,21,42,85,170,340,680)
при т = 683 и е — 37 имеем вектор
В = (37, 74,222,407,94,188,413,143,286, 572).
По определению рюкзачный вектор В называется супердости-
жимым, если существует сверхрастущий вектор А, такой, что В
получается из А сильным модульным умножением.
Для г < 1 назовем вектор В r-гипердостижимым, если най-
дется последовательность векторов Aq, Ai,..., Аг = В, такая, что
Ао сверхрастущий и для всех I — 0... г — 1 вектор А 7-4-1 получа-
ется из А/ сильным модульным умножением.
Рюкзачный вектор А имеет низкую плотность, если его компо-
ненты располагаются в отрезке от 1 до п очень редко. Для полей
Галуа GF(P) имеет место противоположный случай: компонен-
ты рюкзачного вектора А можно выбрать с высокой плотностью,
т. е. можно строить плотный рюкзак (см. задачу 4.4.3).
Задачи и упражнения
4.4.1.	Пусть алфавит открытого текста состоит из следующих
букв: А, Б, Г, Д, Е, 3, О, Ы. Зашифровать текст сообщения Т —
= ГДЕ БОЗ ГЕГЫ на основе двух рюкзаков:
1.	л = (1,2,4);
2.	В = (100,200,400).
4.4.2.	Решить задачу криптоаналитика: по заданному рюкзач-
ному вектору В = (bi, i>2, • • • 5 Ьп) определить сверхрастущий век-
тор А = (ai,a2, • • • ,ап).
4.4.3.	Пусть компонентами рюкзачного вектора А = (ai, а2,...
..., ар) являются ненулевые элементы поля Галуа GF(P) и h > 2
— целое число, причем aj = log^(a + 1—1), где g — образую-
щая группы GF*(P), а — алгебраический элемент степени h над
GF(P).
67
Доказать, что если
где
{х1,Х2,...,Хр} = {У1,У2,---,УР},
р	р
г=1	г=1
4.4.4.	Пусть первые три компоненты рюкзачного вектора рав-
ны 13, 6, 14. Определить все остальные компоненты рюкзачного
вектора длины 711.
Можно ли строить СЗИ, если некоторые из компонентов рюк-
зачного вектора отрицательны или рациональные числа?
4.4.5.	Доказать, что для любого натурального числа к отно-
сительно элементов группы GF*(P) имеет место равенство
При каких Р и к вектор А = (lfc, 2fe,..., (р — l)fe) будет рюкзач-
ным?
4.4.6.	Разработать алгоритм определения рюкзака для задан-
ных параметров.
4.4.7.	Рюкзак А = (йц,а2,... ,ап) назовем без повторений или
с повторениями, если в нем компоненты соответственно повторя-
ются или нет.
Разработать алгоритм создания СЗИ на основе заданного рюк-
зака А,
4.4.8.	Функцию шифрования F(x) для рюкзака A — (oi, 02,...
..., ап) назовем с повторениями или без него, если в шифре ком-
поненты рюкзака А входят соответственно с кратностью t > 1.
Разработать алгоритм создания СЗИ на основе заданного рюк-
зака.
4.4.9.	Пусть буквы открытого текста представлены в троичной
системе счислений и вектор рюкзака имеет вид: А — (19,39,129).
68
Можно ли строить СЗИ и однозначно расшифровывать шифр-
текст:
Т = МАРЕНИЯИ_ПАШАГА_АЗГИП^МЕКЫ_КАГИН_
УТЕЛОВ_ЫНКАВ_ГЮМРИ
4.4.10.	Пусть имеем натуральные числа п и h. Существует
ли рюкзачный вектор А = (&i,&2» • • • >ап) с неотрицательными
компонентами а/, такой, что все суммы, состоящие ровно из h
компонент, не обязательно разных, попарно различны.
4.4.11.	Пусть буквы A — Z имеют числовые эквиваленты 1—26
и пробел 0 соответственно. Сопоставим им, например, двоичные
5-разрядные числа от (00000)2 (для пробела) до (11001)2 следую-
щим образом:
А (00001)2, В (00010)2,..., Z (11001)2-
Пусть рюкзачный вектор имеет вид:
А = (1,2,6,11,21,42,85,170,340,680),
а текст для шифрования — Т = А ВАС АВ АВ.
Тогда, учитывая, что буквам алфавита соответствуют шифры,
получаемые из FA(x) = Aq * Вх, имеем:
Fa(_) = (1,2,6, И, 21) * (00000) - 0,
Fa(A) = (1,2,6,11,21) * (00001) = 21,
РЛ(В) = (1,2,6,11,21) * (00010) - 11,
FA(C) = (1,2,6,11,21) * (00011) = 32,
где Ао — вектор для кодирования самих букв заданного алфавита
(очевидно, в более общем случае можно взять совершенно другой
способ кодирования), FA(x) — функция шифрования букв алфа-
вита.
Рассмотреть вопрос расшифрования. Какими свойствами об-
ладает данная рюкзачная криптосистема?
69
4.5.	Система защиты информации
на основе кода Варшамова
Рассмотрим вопрос обобщения СЗИ на основе заданного рюк-
зака, применив Р-ичные коды Варшамова:
Wn = {^1^2 • • •	ixi = a(mod п + 1),
i=l
хп € В = {0,1,... ,р - 1}, а е Z}.
Так, в частности, при р = 3, п — 4, а = 0 из указанного сравне-
ния получаем код W4, состоящий из 17 следующих кодовых слов:
0000
1001
1200
1111
2120
2002
0212
0220
1221
0102
0021
2112
ОНО 2010
1022 2201
2222
Код W4 является 3-ичным, равномерным и нелинейным кодом.
Сопоставим, во-первых, буквам открытого текста кодовые слова
кода Варшамова, а, во-вторых, при определении шифра, на осно-
ве заданного рюкзака в отличие от стандартного случая, когда
те или иные компоненты рюкзачного вектора либо присутствуют,
либо нет, здесь мы применим повтор самих компонент рюкзачно-
го вектора. При этом наибольшее число повторов может быть не
более р — 1.
Пусть открытый текст имеет вид: Т = CODE RRW ВАС АВ
АВ.
Выбираем случайным образом 26 слов из (см. задачу 4.5.9.)
для первоначального способа кодирования. Каждое выбранное сло-
во будет соответствовать только одной букве английского алфа-
вита.
70
Предположим, что мы имеем следующие соответствия:
Л-000000 F - 001212 К - 010010 Р — 011222 U - 020020
В-000120 G-002022 L- 010211 Q - 012121 V - 020221
С-000201 Я-002111 М- 011021 R - 012202 W - 021000
В-001011 I- 002200 Я-011102 S - 012210 X - 021112
В-001100 J- 010002 0-011110 Г-020012 Y - 021120
- 100001
Z -021201
Наконец, в качестве рюкзачного вектора выберем вектор
Л = (1,2,6,11,21,43)
и определим значения функции FA(x) для всех букв, входящих в
открытый текст:
Г = CODE RRW ВАС АВ АВ.
Учитывая, что буквам алфавита соответствуют шифры, полу-
чаемые из
Fa(x) = Л * Wx,
где Wx — шифр Варшамова буквы X, имеем:
Вл(_) = (1,2,6,11,21,43) * (100001) =44,
Ял(Л) = (1,2,6,11,21,43) * (000000) = 0,
Fa(b) = (1,2,6,11,21,43) * (000120) = 53.
Аналогично получаем:
FA(C) = 65,
Я4 (В) = 70,
ЯЛ(В) = 17,
Я4 (О) = 40,
Fa(R) = 122,
FA(W) = 10.
В этом случае исходный текст
Т = CODE RRW ВАС АВ АВ
шифруется как:
Е = 65,40,70,17,44,122,122,10,44,53,0,65,44,0,53,44,0,53.
71
В нашем примере константы п, р и а подобраны так, что
|W6| = 105 > 26.
В данном случае условие однозначного шифрования и расшиф-
рования можно сформулировать, например, следующим образом:
для любого рюкзачного вектора А = (ai,a2, • • •, ап) его компонен-
ты должны удовлетворять неравенству
а/ > Qi * &1 + С^2 * CL2 + • • • + Q7-1 * dj-l
для любого Z, где ai > р — 1.
В более общем случае в качестве рюкзачного набора можно
взять любой сверхрастущий вектор.
Задачи и упражнения
4.5.1.	Разработать алгоритм синтеза криптосистемы, в основе
которой лежат сами Р-ичные представления элементов шифра в
системе счисления с основанием Р.
4.5.2.	Разработать алгоритм определения всех слов кода Вар-
шамова Wn. Зависит ли количество кодовых слов от параметра
а?
4.5.3.	Построить СЗИ с повторяющимися компонентами рюк-
зака и зашифровать текст Т = DAHRAZ - AYRENIK SUMANTC.
4.5.4.	Построить СЗИ с повторяющимися компонентами рюк-
зака, если элементарными сообщениями являются отдельные за-
писи некоторой заданной длины — так называемые Z-граммы, или
блоки длины Z, представленные с помощью кода Варшамова. За-
шифровать текст, если I = 3:
Т = ЧАРТАР ТАМ ГДЕ ЧУВСТВУЕТСЯ
НАДЕЖДА ВОЗРОЖДЕНИЯ
4.5.5.	Построить СЗИ для многоалфавитного случая, на осно-
ве кодов Варшамова и зашифровать текст Т = СИГНАХ ТАМ
ГДЕ КОТАЛ.
72
4.5.6.	Найти число натуральных решений уравнения:
l)cti + 2q2 4" 3«з + ... + (Р — 1)<тр_1 = П;
+ <12^2 + . . . +	— П
(здесь А = (ai, а,2,..., ап) — заданный рюкзак).
4.5.7.	Разработать алгоритм атаки для определения секретно-
го ключа заданной СЗИ:
1)	по известной криптограмме длины N]
2)	по известному вектору В = (Ьц, 62,, bn).
4.5.8.	Доказать, что для двоичного кода Варшамова Wn число
его кодовых слов можно найти по формуле
|Wn| = (1/2 * (п + 1)) *	* 2(и+1)/сг, d\n + 1,
причем сумма берется по нечетным делителям d.
4.5.9.	Положим р = 3, п = 6, а — 0. Для выбранных р, п и а
построить код Wq, состоящий из 105 слов. Вот первые 24 слова:
000000	000112	000120	000201	001011	001100
001212	001220	002022	002111	002200	010002
010010	010122	010211	011021	011102	011110
011222	012001	012121	012202	012210	020012
4.5.10.
Из представлений видно, что Ц = 13, Z5 = 26. А чему равен
Zn?
73
4.6.	Обобщенная рюкзачная
криптосистема с открытым
ключом
Пусть
Zp =	р>2
— множество коэффициентов повторений компонент возрастаю-
щего рюкзачного вектора
Л = (йЦ, • • • ,
Решением без повторений компонент для входа (Л, г) назовем
подмножество элементов А, сумма которых равна v, т. е.:
п
Oti&i — V
1=1
при условии, что а/ 6 {0,1}.
Если же ai Е {0,1,2,... ,р — 1}, р > 2 и хотя бы один из коэф-
фициентов а/ > 2, то назовем решение с повторениями с соответ-
ствующими коэффициентами повторений компонент из Zp.
Такое определение означает, что существует вектор
W-y = (<21, #2, . . . , G"n),
представляющий собой спектр повторений для числа v, где Е
Е {0,1,2,... ,р — 1}, такой, что выполняется равенство
v — А * w*
причем решение будет без повторений или с повторениями, если
соответственно р = 2 или р > 2.
Так, например, если А = (1,6,13,21), a v = 35, то его спектр
без повторений равен W35 = (1,0,1,1), и для входа (Л, 35) имеем
единственное решение без повторений
35 = 1 * 1 + 0 * б + 1 * 13 + 1 * 21.
74
Аналогично для входа (А, 35) имеем спектр с повторениями —
W35 = (2,2,0,1) и следующее единственное решение — тоже с по-
вторениями: 35 = 2*1 + 2*6 + 0*13 + 1*21.
Рюкзачный вектор будем называть инъективным, если для про-
извольного v его вход (А, г) обладают не более чем одним реше-
нием. При этом, если для такого вектора рассматриваются реше-
ния с коэффициентами повторений компонент вектора А из
то такой инъективный вектор назовем обобщенным рюкзачным
вектором и обозначим его через Ар.
Так, например, для р = 3 вектор
А3 = (2,5,15,45,135,405)
является обобщенным инъективным рюкзачным вектором, и каж-
дый его допустимый вход (A3, г) имеет одно единственное реше-
ние с повторениями или без них. Так, если v = 74, то его спектр
W74 = (2,2,1,1,0,0), и имеем единственное решение с повторени-
ями
74 = 2*2 + 2*5 + 1* 15 + 1* 45 + 0* 135 + 0* 405.
Если же v = 62, то его спектр wq2 = (1,0,1,1,0,0), и имеем един-
ственное решение без повторений:
62 = 1*2 + 0*5 + 1* 15 + 1* 45 + 0* 135 + 0* 405.
Рюкзачный вектор Ар = (ai, . ,ап) назовем обобщенно
сверхрастущим, если для любого J = 2...П имеет место нера-
венство
J-1
aj > 52(Р-
k=i
где р > 2 — некоторое натуральное число.
Так, например, А13 = (6,74,965,12550,163145) — обобщенно
сверхрастущий рюкзачный вектор длины 5.
Очевидно, если рюкзачный вектор сверхрастущий, то он инъ-
ективен и одновременно возрастающий. Хотя возможно, что рюк-
75
зачныи вектор не сверхрастущии, однако он инъективен, как, на-
пример, для вектора
А = (2,3,4,8,16).
Инъективный рюкзачный вектор А назовем плотным, если раз-
ность между произвольными его двумя соседними компонентами
по модулю есть число минимальное. Очевидно, если рюкзачный
вектор является плотным, то он одновременно и возрастающий.
Так, например, при р = 3. с = 2 и п = $ имеем следующий
плотный и инъективный обобщенный рюкзачный вектор (см. за-
дачу 4.6.8.)
Л3 = (2,5,15,45,135,405,1215,3645).
Здесь следует заметить, что условие инъективности выполня-
ется также для всех других обобщенных рюкзачных векторов бо-
лее низкой плотности и в том случае, когда выполняется неравен-
ство:
J-1
dj > СХ&кч J —	. . ,П,
к—1
где а > р — 1, что представляет собой особое направление иссле-
дований.
Пусть
Лр = (<21, (12ч • • • ч ап)
— обобщенный инъективный рюкзачный вектор размерности п,
п > 3. Очевидно, любое допустимое значение для v представля-
ется в виде
V = Qi *	+ 012 *	. • • + О^п * О"пч
или v = А * w^, где wv = (ai, а25 • • •,	~ спектр числа v, а
диапазон его значений определяется неравенствами
0 < и < (р - 1)(п1 + а2 + ... + ап\
76
Для каждого из рп допустимых значений v определим обоб-
щенную функцию шифрования следующим образом: Fp(y) =
= Ар* w^.
Итак, пусть каждому элементарному сообщению * (в частности
букве) открытого текста соответствует свой спектр:
W* < > (од 5 0^2 ? • • • 5	’
и установим шифр Е такого сообщения, как
77! ТУ / „ * „ *	„ * \	Л*/л*л*
Е гр^О^ ^2’ • • ’ > &п)	^2» * ’ • 1 ^п)
Затем представим открытый текст Т в виде строки р-ичных
разрядов, используя для его представления соответствующий р-
ичный код (в предыдущем пункте мы применили р-ичный код
Варшамова), а потом разобьем полученную строку на сегменты
длины п. После этого зашифруем открытый текст посегментно,
прцменив к нему функцию шифрования Fp(x).
Процедура восстановления криптограммы Е аналогична дво-
ичному случаю, коим является стандартный случай рюкзака. Раз-
ница лишь в том, что при выборе очередной компоненты рюкзака
необходимо учитывать возможный ее повтор.
Задачи и упражнения
4.6.1.	Доказать, что любое десятичное число можно предста-
вить в р-ичной системе счисления единственным способом.
4.6.2.	Является ли вектор А = (1,р,р2,... ,рп-1) инъектив-
ным? Определить число секретных ключей.
4.6.3.	Пусть Ар — обобщенный рюкзачный вектор. Как найти
все его секретные пары?
4.6.4.	Построить все рюкзачные инъективные вектора, значе-
ния компонент которых не превосходят 2003.
4.6.5.	Пусть А = (191,691,573,337,365,730,651,493,177,354),
a v = 2200. Найти решение для входа (Д, г).
4.6.6.	Для обобщенного рюкзачного вектора
АР = (2,5,15,45,135,405,1215,3645)
77
определить:
—	все допустимые входы;
—	все секретные пары (т, е);
— Вз, полученный из А% сильным модульным умножением;
— СЗИ с открытым ключом для заданного алфавита.
4.6.7.	Найти необходимое и достаточное условия для существо-
вания обобщенного инъективного рюкзачного вектора Ар.
4.6.8.	Доказать что обобщенный рюкзачный вектор
Ар = («1^2? • • • ^п)
размерности п, п > 3 является плотным и инъективным, если
аг = с, aj =pJ~2 * ((р- 1)с + 1), J-2...n,
где с — некоторая целая положительная константа.
4.6.9.	Доказать, что инъективный рюкзачный вектор
4 = (1,р,р2,...,рп-1)
является одновременно и плотным.
4.6.10.	Доказать что обобщенный рюкзачный вектор
Лр = (ai,a2,... ,ап)
размерности п, п > 3 является инъективным, если он обобщенно
сверхрастущий, т. е. для любого J = 2... п имеет место неравен-
ство
J-1
aj > /^(р -
fc=i
где ai = const и р > 2 — некоторое натуральное число.
4.6.11.	Пусть
Лр = (tti, «2, • • • , ап)
— инъективный и обобщенный рюкзачный вектор размерности п,
п > 3, а вектор
Вр = (61,• • •,bn), bi = е* ai(mod m), (m,е) = 1
78
получен из Ар сильным модульным умножением относительно т
и е.
Доказать что решение задачи о рюкзаке для входа (Вр, v * ё)
совпадает с единственным решением для входа (Ap,v).
4.6.12.	Количество всех различных числовых значений функ-
ции Fp(x) для рюкзачного вектора Ар обозначим через /ДАр).
Очевидно, для сверхрастущего и плотного рюкзака имеем: //(Лр) =
= рп различных числовых значений или входов (Др, v).
Найти /х(Лр) для произвольного обобщенного рюкзачного век-
тора Ар.
4.6.13.	Если взять для вектора Ар = (2,5,15,45,135,405) сле-
дующую секретную пару {2003,738}, где т = 2003, е = 738 (е"1 =
= 19), то мы получим открытый ключ зашифрования — вектор
Вр = (1476,1687,1055,1162,1483,443). Очевидно, что вектор Вр
уже не является сверхрастущим, поэтому криптоаналитик столк-
нется с большими сложностями при его анализе.
Разработать эффективный алгоритм атаки со стороны крип-
тоаналитика.
4.6.14.	Рассмотрите криптосистемы, в основе которых лежат
не Р-ичные коды Варшамова, как это было сделано ранее, а сами
Р-ичные представления элементов сообщения в системе счисле-
ния с основанием Р или любой другой код с соответствующей
модификацией.
4.6.15.	Доказать, что процедура восстановления открытого тек-
ста в целом не зависит от самих компонент рюкзачного вектора,
а зависит только от размера самого рюкзака и способа первона-
чального Р-ичного кодирования букв открытого текста.
79
4.7. Системы защиты информации
на основе решений
многостепенных систем
диофантовых уравнений
Пусть запись
&1,	• • • »	— &1, &2> • • • > Ът
означает следующую многостепенную систему диофантовых урав-
нений
di + tt2 + • • • +	— 61 +	+ • • • + bmi
пп -I- пп -4-	4- пп = hn 4~ hn 4~	4~ hn
или в компактной записи
т	т
22 = £ где к =
1=1	1=1
Как известно, решения этой системы определяются как набор
чисел, удовлетворяющих всем уравнениям системы и, как пра-
вило, общее решение содержит одно, два или более параметров.
Очень часто из одних решений следуют другие, возможно, содер-
жащие меньшее число параметров.
Рассмотрим ниже новый класс криптосистем с открытым клю-
чом, в основе которых лежат диофантовые трудности.
4.7.1.	Система защиты информации на основе
специального рюкзака
В данном случае в качестве рюкзачного вектора А необходи-
мо выбрать специальным образом определяемое параметрическое
решение многостепенной системы диофантовых уравнений.
80
Так, например, в качестве А можно выбрать параметрическое
решение многостепенной системы вида
Хр + Х2" + ... + Х6" = У^ + У2п + ...+У6", п = 1,2,3,4, 5.
Приведем здесь лишь одно из его решений на основе следую-
щего тождества:
(t + 5)к + (t + 6)* + (< + И)* + (t- 5)* + (t - 6)к + (t - 11)* =
= (t + l)k + (t + 9)* + (t + 10)* + (t - 1)* + (t - 9)* + (t - 10)*,
к = 1,2,3,4,5.
При t = 12 имеем
1* + 6* + 7* + 17* + 18* + 23* = 2* + 3* + 11* + 13* + 21* + 22*,
к = 1,2,3,4,5.
Таким образом, в качестве рюкзачного вектора А можно взять
Ах = (1,6,7,17,18,23)
ИЛИ
Л2 = (2,3,11,13,21,22).
В качестве секретней лазейки для легального пользователя в
данном случае можно выбрать основные секретные параметры
рюкзачной системы
т = шах{аЛ, (т,ё) = 1
V, J 1	\	7	/
и, например вектор — решение А± с соответствующим парамет-
ром.
В данной криптосистеме различия в том, что легальный по-
лучатель имеет набор А± = (1,6,7,17,18,23), а криптоаналитик
имеет тот же набор, но только возведенный в пятую степень, т. е.
набор
= (32,243,161051,371293,4084101,5153632).
81
Для противника сложность заключается в том, чтобы найти
параметры диофантового уравнения пятой степени.
Идея проста: сделать для противника задачу трудновычисли-
мой, запутать его в высоких степенях.
4.7.2.	Система защиты информации на основе
секретного рюкзака
Идея построения данной СЗИ заключается в том, что легаль-
ный пользователь системы связи лишь по одному шифру само-
стоятельно определяет одно из многочисленных решений много-
степенной системы диофантовых уравнений в качестве секретного
рюкзака и расшифровывает криптограмму.
Для противника сложность заключается в том, чтобы найти
само решение известной ему многостепенной системы диофанто-
вых уравнений. Эту задачу легальный пользователь решает лег-
ко, так как он знает, как найти сами параметрические решения
диофантового уравнения для высоких степеней.
Отметим, что чаще всего параметрические решения задаются
в виде систем линейных или нелинейных уравнений.
Проиллюстрируем данный подход, например, на следующем
примере.
Пусть для уравнения
I V5 I 1	_ у5
А1 “Г А2 -и ... Л5 — Г
на основе тождества индийского математика Шастри (1934)
(7565 - а5)5 + (а5 + 25Ь5)5 + (а5 - 25Ь5)5 + (10а3Ь2)5 + (50аЬ4)5 =
= (а5 + 75Ь5)5
имеется следующее двупараметрическое решение:
Xi = 75b5 - а5,
Х2 = а5 + 25Ь5,
Х3 = а5 - 25b5,
Х4 = 10а362,
Х5 = 50аЬ4,
Y = а5 + 75b5.
82
Тогда адресат по полученному искомому шифру, например, Е =
= 14025517307 определяет сначала соответствующие значения па-
раметров а = 2, b = 1 из равенства
а5 + 75b5 = 140255173071/5 = 107,
а затем и сами решения = 74, Х% = 57, Хз = 7, Х4 = 80,
- 100.
После чего легальному пользователю легко построить основ-
ной секретный ключ
А = (7,57,74,80,100),
а затем и приступить к расшифровыванию криптограммы отпра-
вителя, имея для этого все необходимое.
Отметим, что в данном случае криптоаналитик, помимо про-
чих качеств, должен обладать еще умением решить системы дио-
фантовых уравнений заранее заданной сложности.
4.7.3.	Система защиты информации на основе
многопараметрических решений
Синтезируемая здесь криптосистема содержит некоторое чис-
ло как открытых, так и секретных ключей, применить которые
можно в зависимости от конкретных режимов передачи данных.
Так, например, если участники канала связи не доверяют друг
другу, то можно зашифровать данные одним способом, а переда-
вать их другим — с помощью дилера, разделив секрет поровну
между всеми участниками связи.
Пусть имеем систему диофантовых уравнений
F^(x1,X2,...,Xm') = Р£(у1,у2,...,ут'),
П - П1,П2,	П, £ N,
которая имеет следующие параметрические решения:
Xi — Xi(at,a2, •  г = 1,2,... ,т, х, е N,
Уг = Уг(аЬ°2, • • • ,««), г = 1,2,... ,m, y,EN.
83
Допустим, что алфавит W = {ci, С2, • •., сх} исходного текста Т
содержит х букв. Установим взаимно однозначное соответствие
между буквами алфавита W и параметрами Р = {«1, «2? • • • ^ах}
многостепенной системы диофантовых уравнений (в противном
случае можно ввести новые формальные параметры с тем, чтобы
количество букв в алфавите W и параметров (шифров) Р были
одинаковы). Затем сопоставим каждому параметру щ G Р букву
Cj е W.
Далее предварительно текст Т разобьем на блоки В = ТцТг2 ...
... Tim по тп букв и сопоставим каждому блоку В одно решение
X = Х1Х2 - - - хт, Х{ ф Xj многостепенной системы диофантовых
уравнений следующим образом:

(здесь открытый ключ К = Х\Х2 •.. хт)-
После чего предварительно сопоставим решению X решение
Y = У1У2^-Ут (здесь К' = У1У2^-Ут ~ полуоткрытый ключ
дилера) и зашифрованный текст Tf передадим по каналу связи
адресату.
В силу того, что по решению Y однозначно определяется реше-
ние X, то адресат восстановит Г, имея Т'. Здесь секретом явля-
ется само решение многостепенной системы диофантовых уравне-
ний и все секретные параметры, присущие открытым системам.
В частности для легального пользователя можно выбрать, на-
пример, наименьшее решение системы. Причем в зависимости от
самой системы можно установить режимы шифрования, завися-
щие от значений п, т и списка параметров таким образом, чтобы
всегда адресат по Y восстановил Тг с учетом Уг = yi(ai,a2, • • • ,at).
Задачи и упражнения
4.7.1.	Найти все натуральные (целые, рациональные, действи-
тельные) решения уравнений:
1)	7Х + 13У = 2003;
2)	X + Y = XY;
84
3)	X2 + Y2 = Z2.
4.7.2.	Определить, при каких к и t имеет место равенство
(i + 5)* + (t + 6)* + (i + ll)fe + (t - 5)* + (t - 6)* + (t - ll)fe =
= (t + 1)* + (t + 9)* + (t + 10)* + (t - 1)* + (t- 9)* + (f - 10)*.
4.7.3.	Построить СЗИ на основе решений многостепенной си-
стемы диофантовых уравнений
—.	У 4*	V У L* -ТУГ*	Т У Ь	т у Ь
Д< А/ | Д< »v |	| Д< »v , Д/ f\j | Д/ |	| Д/ fv
Л1 +Л2 t ... ±Л5 -	+ 12 + • • • + 15 >
(Х1,Х2,...,Х5,У1)У2,...,У5) = 1, к = 1,2,3,4,5.
4.7.4.	Доказать, что уравнние
5 * 5Ж + 10 * 7х + 9х = 5 * 8х + 10 * 6Ж + 4Ж
имеет решения и построить на основе его решения СЗИ с откры-
тьем ключом.
4.7.5.	При каких а, Ь и т имеет место равенство
2ai —m, 2(2i—3m, 2(22 —m, 2а% — 3m, 2^з + т = 2пз+m, 2аз + 3т,
2Ь1 — т, 2?>2 — Зт, п = 1,3, 5, 7
или
(—(21 + 7(22 + «з)П 4" (—3(21 + 5(22 + Заз)п + (5(21 — 3(22 + 3(2з)П+
+ (7(21 — (22 + (2з)П + ((21 + (22 + 8&з)П = (—(21 — (22 + (2з + 8Ь1)П +
+ ( — (21 — (22 + (2з + 86з)П + ((21 + (22 + 7(2з)п + (3(21 4” 3(22 + 5(2з)п +
+3П((21 + (22 - <2з)П, П = 1, 3, 5, 7.
4.7.6.	Разработать алгоритм атаки криптоаналитика на СЗИ,
построенные выше.
4.7.7.	Построить СЗИ на основе ранее приведенных уравне-
ний. Для каких уравнений этого сделать невозможно?
4.7.8	(Эйлер). Решить уравнения:
при W = 2,3,4,..., [7,
85
2)	Х^ + Х^' + ... + X™ - Yw при W - 2, 3, 4, ... , U.
4.7.9	(Elkies N. D.). Известно, что
26824404 + 153656394 + 1879604 = 206156734.
Как найти другие решения на основе известного?
4.7.10.	Пусть
«1, <з2, ^з, • • • , ат = ^1, Ь2, Ьз,... ,Ьт
какое-либо решение многостепенной системы n-й степени
т	т
У^ х[ =	у[, I = 1,2,..., п, п = 2к — 1 или п = 2к,
г=1	г=1
т
Y&bi)r(a!r2r - Ь1~2г) = О,
1=1
где натуральные числа г и I пробегают все без исключения нату-
ральные числа в следующих границах:
1 < г < к — 1, 2r + 1 < Z < п,
а и Ъ — произвольные целые числа, отличные от нуля и не равные
между собой, тогда
aai + ЬЬ1, аа2 + bb2,..., аат + bbm =
= bdi + abi, bd2 + ab2,..., bam + аЬт,
т. e. при выполнении указанных условий из
т	т
вытекает
т
т
86
доставляющие двупараметрические решения системы.
4.7.11.	Найти все параметрические решения уравнения
А4 + В4 + С4 = В4,
а затем предложить эффективную нетривиальную криптосистему
на основе полученных решений.
4.7.12.	Найти все параметрические решения уравнений:
1.	А3 + В3 = С3-,
2.	А5 + В5 + С5 + D5 = Е5-
3.	А3 + В3 + С3 = D3-
4.	А4 + В4 + С4 + D4 = Е4.
Можно ли подобрать параметры таким образом, чтобы из об-
щего параметрического решения следовали натуральные реше-
ния?
4.8.	Временные оценки относительно
трудоемкости арифметических
операций
Пусть Т(Г) — время обработки информации I, что в конечном
итоге можно представить в виде
к
где tk — время выполнения процессором операции типа 1^-
Пусть далее JV(*) — количество числовых значений, удовле-
творяющих соотношению *. Так, например, 7V(+) — количество
операций сложений, a 7V(n!) — количество операций, необходи-
мых для вычисления п\.
Из данной схемы
по х легко вычисляется F(x)
по F(x) трудно вычислимо х
87
видно, что основная задача безопасной передачи информации сво-
дится к отысканию трудно вычислимых функций.
Пример 1. Оценить число операций при умножении /с-разрядного
двоичного числа т на /-разрядное двоичное число п.
Очевидно, что
N(m * п) < к *1,
или
N(m * n) < ([Log т] + 1) * ([Log п] + 1),
где основание логарифма считается равным 2.
Пример 2. Найти верхнюю границу для числа двоичных опе-
раций, необходимых для вычисления п!.
Также очевидно, что
7V(n!) = п * (п — 2) * ([Log п] + I)2.
Задачи и упражнения
4.8.1.	Оценить время, необходимое для перевода заданного це-
лого числа в систему счисления с основанием Ь.
4.8.2.	Разработать алгоритм для нахождения целочисленного
решения уравнения X2 + У2 = п, где п — некоторое заданное
положительное число. Определить его временную сложность.
4.8.3.	Оценить время, необходимое для нахождения НОД(а, Ь)
и НОК(а, Ь) заданных натуральных чисел а и Ь.
4.8.4.	Оценить время, необходимое для проверки того, явля-
ется ли заданное целое число
а)	простым;
Ь)	совершенным;
с)	псевдопростым;
d)	полигональным.
4.8.5.	Оценить время, необходимое для вычисления функций:
а)	Эйлера ф(п)]
Ь)	Мебиуса ц(п).
88
4.8.6.	Доказать, что число N(al = b) операций умножения на
элементы конечной группы G для нахождения I из равенства а1 —
= b можно оценить неравенством
N(a! = b) < 2(аА + log2t) — 1,
где t = ord b, а и b — элементы G.
4.8.7.	Простое число вида М(п) — 2п — 1 называется числом
Мерсенна. Оценить количество операций для вычисления дис-
кретного логарифма элемента поля jF^5, если М(55) — 23 * 31*
*89 * 881 * 3191 * 201961.
4.8.8.	Найти простые числа вида 22n + 1 заданного отрезка.
Оценить количество операций, для вычисления наибольшего про-
стого числа этого отрезка.
4.8.9.	Известно (теорема Евклида), что если число р — 2n+1 —1
— простое, то число 2пр является совершенным.
Оценить количество операций для вычисления наибольшего
совершенного числа заданного отрезка.
4.8.10.	Пусть 7г(я) — количество простых чисел отрезка 1... х.
Известно, что при х > 70 имеет место неравенство
Учитывая указанную оценку, определить количество операций
для вычисления наибольшего простого числа заданного отрезка.
4.8.11.	Обозначим через N(ri) наименьшее число операций сло-
жения, вычитания и умножения (выполняемых над коэффици-
ентами многочленов и промежуточными числовыми результата-
ми), требующихся для переумножения двух многочленов степе-
ней, меньших п > 0.
Доказать, что
1.	2V(n) < 2 * N(]n/2[) + N([n/2]) + 4 * [п/2] + 2 * п - 4;
2.	N{n) < 3fc(N(n/2fe) + 8 * n/2k - 2) - 8 * п + 2 при 2к\п;
3.	ЛГ(п) < п2 + (п — I)2.
4.8.12.	Доказать, что для любого r-разрядного числа п число
м = [24г-1/([24г-1/п] - [24г-1/(п + 1)])] - п
89
отличается от п2 не более чем на 3.
4.8.13.	Определить количество N(rip) р-ичных разрядов fc-знач-
ного целого десятичного числа п.
Доказать, что
N(nio) = [Log п] + 1.
4.8.14.	Определить время Т(1) генерации всех перестановок
заданной длины.
4.8.15.	Пусть длина пароля равна d, а для выбора одного сим-
вола на клавиатуре потребуется одна секунда. Оценить время
Т(/) для разгадки пароля.
4.9.	Относительная криптостойкость
систем защиты информации
Будем считать СЗИ относительно криптостойкой на заданный
период времени, если за это время нельзя без знания ключа де-
шифровать шифр, определяющий его стойкость.
Для определения криптостойкости СЗИ имеется несколько по-
казателей криптостойкости, среди которых выделим следующие:
—	количество всех возможных ключей;
—	среднее время, необходимое для криптоанализа.
Отметим, что относительное ожидаемое безопасное время опре-
деляется как полупроизведение числа возможных ключей и вре-
мени, требуемого для того, чтобы испытывать каждый ключ крип-
тоаналитиком.
Очевидно, уровень стойкости СЗИ зависит еще от возможно-
стей криптоаналитика и от пользователя, хотя известно, что СЗИ
по степени доказуемости их безопасности существуют (примером
безусловной стойкой СЗИ является система с разовым использо-
ванием ключей — шифр Бернама).
Более того, стойкость доказуемо криптостойких СЗИ опреде-
ляется сложностью решения математической задачи, на основе
90
которой создана СЗИ. Примером сказанного могут служить си-
стемы Диффи—Хеллмана, или RSA, основанные на сложностях
соответственно дискретного логарифмирования и разложения це-
лого числа на множители. Другими примерами служат СЗИ ГОСТ
28147-89 и DES.
К сожалению, безусловно криптостойкие СЗИ неудобны на
практике, к тому же на практике никто не может помешать спо-
собному криптоаналитику снизить оценку стойкости СЗИ, при-
думав новый, более эффективный метод анализа. К тому же с
развитием математики и средств вычислительной техники крип-
тостойкость СЗИ может только уменьшаться.
Задачи и упражнения
4.9.1.	Хакеру известно, что длина пароля не более чем 13-
разрядное десятичное число. Сколько ему необходимо времени,
чтобы гарантированно вручную установить этот пароль?
4.9.2.	Файл имеет внутренний 32-битовый ключ. Вызов и про-
верка для открытия замка файлов требует 20 мкс.
Определить ожидаемое безопасное время для раскрытия паро-
ля методом проб и ошибок.
4.9.3.	Разработать алгоритм определения любого пароля за-
данной длины для несанкционированного доступа к PC IBM.
4.9.4.	Определить криптостойкость для следующих СЗИ с ал-
фавитом в 44 буквы и расположить их по возрастанию безопас-
ного времени:
1)	СЗИ А. Цезаря;
2)	СЗИ задается формулой: X + Y = Z;
3)	СЗИ с ключом К = 641325;
4)	СЗИ с ключом К = XS11AH,
5)	СЗИ методом блочного шифра с ключом К — ВИКТЛЮД.
4.9.5.	Укажите наиболее и наименее стойкие шифры из мно-
жества существующих.
4.9.6.	Пусть имеется конечное число возможных сообщений
тг,т2,...,тк
91
с априорными вероятностями
P(r1),P(T2),...,P(Tfc).
Эти сообщения преобразуются в возможные криптограммы:
Ei, Еъ,..., Е^,
так что имеет место следующее равенство: Е = F(M).
Установить необходимые и достаточные условия для надежной
передачи сообщений на заданный период времени.
92
ГЛАВА 5
ВОПРОСЫ УСТАНОВЛЕНИЯ
ПОДЛИННОСТИ И ЦЕЛОСТНОСТИ
ДАННЫХ. СИСТЕМЫ ЭЛЕКТРОННОЙ
ПОДПИСИ
5.1.	Аутентификация данных
Аутентификация (удостоверение подлинности) представляет
собой метод установления подлинности данных в самом широком
смысле слова. Ее можно применить также для проверки подлин-
ности источника сообщений, его целостности и некоторых других
специальных вопросов.
Так, например, парольная защита — один из основных при-
меняемых на практика механизмов аутентификации. Хотя, как
известно, сетевые вирусы Worm, WANK&OILZ и другие, широко
распространившиеся в сети Internet, решают противоположную
задачу — задачу угадывания паролей.
Приведем еще один способ установления подлинности пользо-
вателя с помощью так называемой процедуры в режиме рукопо-
жатия. Этот способ обеспечивает большую степень безопасности,
чем многие другие схемы и его суть сводится к следующей про-
цедуре.
Пользователю представляют последовательность случайных
чисел и предлагают ее продолжить. Если пользователь знает алго-
ритм получения последовательности случайных чисел, то он про-
должит представленную последовательность, тем самым устанав-
ливает свою подлинность.
В более общем случае, можно применить криптографический
протокол, представляющий собой алгоритм обмена информацией
между различными пользователями, как соперничающими между
собой сторонами, так и нет.
93
Пусть А и В — два участника системы связи передачи инфор-
мации, a Fa и Fb — их функции шифрований, которыми может
воспользоваться любой пользователь системы, кто отправляет со-
общение участникам А и В соответственно. Наконец, пусть t —
подпись участника А (включающая в себя, возможно, идентифи-
кационный номер А, время и дату отправления сообщения и т. п.).
Если А просто пошлет В некоторое сообщение F#(i), то нет
способа установить подлинность сообщения, так как способ вы-
числения Fs(t) — общеизвестен. Однако если в определенном ме-
сте (например в конце сообщения) будет помещено F^F^1^), то
участник В, применив F^1, расшифрует все сообщение, включая
и эту добавку, которая примет вид F^1^).
Так как участник В знает, что сообщение должно поступить
от участника А, то он применит к добавке ключ А, т. е. Fa (ключ
Fa открыт и следовательно общеизвестен), и получит t — под-
пись участника А. К тому же, так как никто, кроме участника
А, не может воспользоваться функцией FJ1, обратной к F4, то
он удостоверяется в том, что сообщение послано действительно
участником А.
Задачи и упражнения
5.1.1.	Какими недостатками обладают все схемы с паролями?
5.1.2.	Какие преимущества и недостатки имеет алгоритм уста-
новления подлинности по сравнению со схемой с паролем?
5.1.3.	Допустим, что для установления подлинности пользова-
теля при входе в систему применяется процедура в режиме руко-
пожатия. И пусть пользователь перехватывает следующие значе-
ния аргумента х и функции F(t):
х:	1111, 2222, 3333, 4444, 1312, 4752, 5472, 6836, 8831
F(z): 0, 0, 36, 64, 4, 86, 76, 120, 64
Определить функцию F(z).
5.1.4.	Построить схему установления подлинности адресата на
основе криптосистемы RSA (применить его числовой вариант).
5.1.5.	Построить криптосистему с открытым ключом, которая
защищает папку RRWO от:
94
— несанкционированного доступа;
— несанкционированного копирования файлов из RRWO (до-
ступ к папке имеется).
5.1.6.	Пусть функция шифрования имеет следующий вид:
F(X) = 2 * (ai * щ + ^2 * «з) mod (ai * «2 * &з * щ),
где X =	— десятичный четырехзначный числовой экви-
валент буквы открытого текста.
Найти период этой функции.
5.2.	Электронная цифровая подпись
В конце обычного письма или документа исполнитель или от-
ветственное лицо обычно ставит свою подпись, преследуя две це-
ли. Во-первых, получатель имеет возможность убедиться в истин-
ности письма, сличив подпись с имеющимся у него образцом. Во-
вторых, личная подпись является юридическим гарантом автор-
ства документа, что особенно важно при заключении договоров,
составлении доверенностей, обязательств и т. д.
Аналогичные задачи позволяет решить цифровая подпись.
Пусть пользователю А необходимо подписать сообщение Т. Он,
зная секрет К и применяя функцию с секретом Fk, находит та-
кое Р, что Fk(P) = Т, и вместе с сообщением Т отправляет ад-
ресату В в качестве своей цифровой подписи Р. Как правило,
сообщение, подписанное цифровой подписью, можно представить
как пару (Т, Р), где Т и Р — сообщение и подпись отправителя
соответственно.
Таким образом, имея пару (Т, Р), предназначенную для адре-
сата, параллельно можно решить следующие задачи.
1.	Подписать сообщение Т, т. е. решить уравнение Fk(P) = Т
может только адресат, подделать подпись за менее чем безопасное
время невозможно.
2.	Проверить подлинность подписи может любой, знающий функ-
цию Рк, т. е. только легальный пользователь.
95
3.	При возникновении споров отказаться от подписи невозмож-
но.
4.	Подписанное сообщение (Г, F) можно, не опасаясь ущерба,
пересылать по соответствующим каналам связи.
На практике алгоритмы с открытыми ключами, часто недоста-
точно эффективны для подписи длинных документов. Поэтому
для удобства протоколы цифровой подписи нередко используют
вместе с односторонними хэш-функциями, и отправитель подпи-
сывает не сам документ, а значение хэш-функции для данного
документа.
В принятых стандартах США и России в цифровой подписи
(DSA и ГОСТ Р 34.10-94 соответственно) используются специаль-
но созданные алгоритмы, в частности алгоритмы типов Диффи-
Хеллмана, Эль-Гамаля и Шнорра для больших простых чисел.
Задачи и упражнения
5.2.1.	Привести протокол подписи одного и того же документа
одновременно двумя пользователями с помощью хэш-функций,
если пользователи не доверяют друг другу.
5.2.2.	Рассмотрим следующий пример криптосистемы без пе-
редачи ключей. Пусть два участника А и В передачи информа-
ции (а и b — ключи для А и В соответственно) решили установить
между собой секретную связь без передачи ключей при открытом
ключе р = 23.
1.	Выбор случайных элементов а и b из С?В*(23): пусть а = 5,
а Ь = 7.
2.	Определение секретных ключей из соответствующих срав-
нений: as = 9, a bs = 19.
Зашифровать и подписать сообщение:
Т = НЕ ПИШИТЕ ДЛИННЫЕ ПИСЬМА
5.2.3.	Известно, что все криптосистемы, реализующие цифро-
вую подпись, основаны на односторонних функциях, т. е. любую
асимметричную систему можно взять за основу для нанесения
цифровой подписи.
96
Приведите формальную схему нанесения цифровой подписи с
помощью известных вам криптосистем.
5.2.4.	Трудность модификации подписи в криптосистемах осно-
вана на вычислительной сложности математических задач раз-
личной природы: как факторизация полиномов высоких степеней
(в частности больших чисел), решение систем нелинейных буле-
вых и диофантовых уравнений, построение примитивных полино-
мов или дискретного логарифмирования в больших полях Галуа
и т. д.
Приведите конкретные примеры таких криптосистем.
5.2.5.	Разработать алгоритм реализации цифровой подписи
для известных вам криптосистем.
5.2.6.	Показать, что в криптографических системах, основан-
ных на открытых ключах, нельзя использовать одинаковые клю-
чи для шифрования и цифровой подписи.
5.2.7.	Что общего между обычной и цифровой подписями? Чем
они различаются?
5.2.8.	В чем заключается принципиальная сложность в прак-
тическом применении систем цифровой подписи?
5.3.	Реализация цифровой подписи
на основе криптосистемы
Эль-Гамаля
Пусть GF(p) — простое конечное поле с большой характери-
стикой р, (&, р — 1) = 1, и д — его примитивный элемент. Сначала
установим необходимые параметры криптосистемы Эль-Гамаля
для шифрования/расшифрования сообщений. Они суть:
открытый ключ:
р — простое число (может быть общим для всех);
д < р (может быть общим для всех);
у = дх mod р (х — случайное число);
97
секретный ключ:
х<р\
шифрование:
к — выбирается случайным образом, (fc,p — 1) = 1;
1-я часть шифртекста
a = gK(mod р);
2-я часть шифртекста
b = М * дК(mod р) (М — сообщение).
Результатом шифрования М является пара (a, b) = Е, что в
два раза длиннее открытого текста.
Расшифрование:
М = b/ax (mod р).
А теперь рассмотрим модификацию этой криптосистемы, поз-
воляющую использовать ее для цифровой подписи. Параметры
для вычисления и проверки подписи в целом совпадают с пара-
метрами криптосистемы, за исключением второй части подписи:
Ь такое, что М = (ха + A:b)(mod (pl)).
Проверка подписи:
если yaab(modp) = gM(modp), то подпись правильная.
Пример. Пусть р=13,р = 2иМ = 7, а секретный ключ х = 6.
Тогда
у — дх mod р = 26 mod 13 = 12,
и мы имеем следующие открытые ключи: р = 12, р = 2, р = 13.
Чтобы подписать сообщение М = 7, выберем случайное число
к — взаимно простое с р — 1, например к = 11. Далее определим
Е = (а, Ь), где
а = p^(mod р) = 211 mod 13 - 7,
а для определения b решим уравнение
М = (ха + fcb)(mod (р — 1)),
98
т. е. 7 — 6*7 + 11*6 mod 12, откуда следует, что Ь = 11, и имеем
следующую подпись: Е — (а, Ъ) = (7,11).
Для проверки подписи убедимся, что yaab(modp) = дм(mod р).
Имеем: 1277п mod 13 = 35831808 * 1977326743 mod 13 = 12*
*2 mod 13 = 11; 27 mod 13 = 128 mod 13 = 11, т. e. подпись
правильная.
Задачи и упражнения
5.	3.1. Чем отличаются друг от друга криптосистемы Эль-Гамаля
и Диффи—Хеллмана? Всегда ли в качестве числа д (д < р) необ-
ходимо выбрать примитивный элемент поля GF(p)?
5.	3.2. Построить криптосистему Эль-Гамаля для р = 19 и под-
писать сообщение М = ВЕРНИСЬ_В_АРЦАХ.
5.	3.3. Схема аутентификации Шнорра состоит из следующих
пунктов:
1.	А выбирает случайное число к из множества {1,2,..., q — 1},
вычисляет г = д * к mod р и посылает г Б\
2.	Б выбирает случайный запрос е из множества {0,1,..., 2* —
1}, где t — некоторый параметр, и посылает е А;
3.	А вычисляет s = к + х * е mod q и посылает s Б;
4.	Б проверяет соотношение г = gs * уе mod р и, если оно
выполняется, принимает доказательство, в противном случае —
отвергает.
Разработать алгоритм реализации подписи для криптосистемы
Шнорра и подписать сообщение Т = ХАБА_РАК_ОТЭ_ХАЦРА.
5.4.	Математика разделения секрета
Во всех рассмотренных ранее симметричных и асимметричных
криптосистемах так или иначе было распределение секретной ин-
формации S таким образом, что одни участники, владея секретом
криптосистемы, имели полный доступ к передаваемой информа-
ции, а другие, не имея его, — только пытались различными спо-
собами достичь этой информации. При этом для тех и других
99
участников ясно, что доступ к информации зависит только от од-
ного единственного секретного ключа.
Пример 1. Пусть два совладельца драгоценностей решили хра-
нить их в одном сейфе с цифровым замком на 20 цифр, Тогда
каждый из них, имея один и тот же ключ, состоящий из 20 цифр,
может либо совместно, либо порознь иметь доступ к сейфу.
Но это возможно лишь тогда, когда они доверяют друг дру-
гу. В противном случае, во избежание ссоры, каждому из них
необходимо иметь свой ключ, например по 10 цифр, который рас-
пределит третье лицо — доверенное для обоих. Тогда они могут
открыть сейф только вместе. Данную задачу о доступе к сейфу
можно обобщить, имея ввиду любое число совладельцев.
Пример 2. Будем говорить, что из п участников А/, I = 1... п,
к — разделяют (1 < к < п) секрет S тогда и только тогда, когда
выполнены следующие условия:
1.	Каждый участник А/ знает некоторую информацию а/, неиз-
вестную остальным участникам Aj, где j Г,
2.	Значение S легко может быть вычислено по любым к значе-
ниям aj;
3.	Знание любых к — 1 или менее значений ai не позволяет
определить само значение секрета S = (so, si,. •., sn).
Множество {«i, а<2,..., ап}, удовлетворяющее условиям (2) —
(3), будем называть (fc,n) пороговой схемой разделения секрета.
Приведем решение указанной задачи, предложенное Шами-
ром. Пусть GF(q) поле Галуа из q элементов (в частности q = р)
и q > п, где п — количество участников схемы разделения сек-
рета. Сопоставим участникам п различных ненулевых элементов
поля {«1, «2, • • •, ап} и положим «о — 0. Как и в случае с сейфом,
дилер схемы разделения секрета (СРС) генерирует к — 1 незави-
симых равномерно распределенных на GF(q) случайных величин
/1? /*2, • • •, fk-i и передает каждому г-му участнику его долю сек-
рета s/ = /(аД где
/(ж) = /о + fix + f2x2 + . . . + fk-lXk~\ Sq = f(ty.
100
Иными словами, можно однозначно восстановить многочлен
степени к — 1 по к его значениям sj = f(af), I = 1... к. Другими
словами, это означает, что любые к участников СР С вместе могут
найти значение секрета sq — /(0).
Здесь секретный ключ задается свободным членом /о = /(0) =
= «о? а все остальные коэффициенты — случайные числа.
Задачи и упражнения
5.4.1.	Привести геометрическое решение задачи СРС для слу-
чая двух участников.
Что указывают точки пересечения с осями координат?
5.4.2.	Выписать матрицу Н = (^-1)з для простого конечного
поля GF(7) и рассмотреть, какими свойствами она обладает.
5.4.3.	Определить наименьшее число замков сейфа и наимень-
шее число ключей у каждого из п участников СРС, если только
т (т < п) участников, объединившись, могут открыть сейф.
5.4.4.	Построить схему разделения секрета на основе кодов
Рида—Соломона.
5.4.5.	Разработать алгоритм раздачи различных секретных
ключей всем К абонентам некоторой группы, подготавливающей
документы для секретной передачи, если дилер:
1.	Доверяет всем участникам одинаково;
2.	R участников из К — вне доверии (R < К).
5.4.6.	Пусть множество {&i,	• • •, удовлетворяющее усло-
виям (2) —(3) из 5.4, образует (fc, п) пороговую схему разделения
секрета S.
Разработать алгоритм для определения значений aj и S при
фиксированном к.
5.4.7.	Применителен ли аксиоматический подход к теории по-
строения криптосистем? Ответ обосновать конкретными приме-
рами.
101
ГЛАВА 6
ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИ
И УПРАЖНЕНИЯ
ПО КРИПТОГРАФИИ
6.1.	Зашифруйте исходный текст
DONOTGOTOSAUNASOONAFTEREATING,
используя криптосистему Цезаря с ключевым словом SUPERDOG
и числом 9.
6.2.	Исходный текст SAUNA зашифрован как TAKE BACK
VAT OR BONDS. Опишите используемую криптосистему.
6.3.	Исходный текст SAUNAANDLIFE зашифрован как
RMEMHCZZTCEZTZKKDA.
Опишите используемую криптосистему.
6.4.	В криптосистеме с блочным шифром Хилла и с матрицей
/ 17	17	5	\
I 21	18	21	.
\ 2	2	19	/
Зашифруйте текст PAYMOREMONEY.
/ И 2
6.5. Матрица А = I 5 23
\ 20 7
19 I
25 I. Зашифруйте текст
1 /
STOPPAYMENTX.
6.6.	Сформулируйте необходимое и достаточное условие об-
ратимости матрицы М, когда арифметические операции выпол-
няются по модулю 26. (Это требуется в криптосистеме Хилла.)
Найдите обратную матрицу для нескольких матриц порядка 2.
102
6.7.	Известно, что при зашифровании использовалась крипто-
система Хилла с матрицей 2-го порядка. Наиболее часто встреча-
ющиеся в криптотексте биграммы — RH и NI, в то время как в
исходном языке они TH и НЕ. Какая матрица может быть вычис-
лена из этой информации?
6.8.	Для зашифрования вначале используется матрица
затем к результату применяется матрица
Постройте одну матрицу с тем же действием.
6.9.	Условие, как и в задаче 6.8, но в данном случае матрицы
следующие:
6.10.	В более общем случае, если исходные матрицы имеют
порядки т и п, то каков будет порядок матрицы с объединенным
действием?
6.11.	Криптосистема замкнута относительно композиции, ес-
ли для любых двух ключей зашифрования найдется один ключ,
обладающий эффектом последовательного применения этих двух
ключей. Замкнутость относительно композиции означает, что по-
следовательное применение двух ключей не добавляет безопасно-
сти. Предыдущие задачи показывают, что криптосистема Хилла
замкнута относительно композиции. Изучите это свойство при-
менительно к некоторым другим криптосистемам, рассматривае-
мым в книге.
103
6.12.	В простых криптосистемах каждый ключ зашифрова-
ния может быть представлен как композиция нескольких порож-
дающих ключей. В криптосистеме Цезаря такой порождающий
ключ — Е1, который отображает каждую букву в следующую. В
аффинной системе буква х, 0 < х < 25, отображается в букву
(ах + 6, mod 26), где (а, 26) = 1. Покажите, что никакой ключ не
может быть порождающим для аффинной системы, в то время
как два ключа могут.
6.13.	Расшифруйте следующий криптотекст, предложенный
участникам конференции EUROCRYPT-88 в Давосе:
EXVITL AMSYMX EAKSSI KIRZMS YEKDAY OSINAL
PVITHE RRJMLO OIEUSM GPLKSM ADAVOS LULRVK
SIXMTA IDAVOS
6.14.	Название какого города из четырех букв зашифровано
как BHFLYPBT, если был использован следующий алгоритм за-
шифрования. Вначале произвольная "мусорная” буква добавля-
лась после каждой буквы исходного текста. (Таким образом, в
результирующем слове 2-я, 4-я, 6-я и 8-я буквы не существенны.)
Затем использовалась криптосистема Хилла с матрицей 2-го по-
рядка, в которой слово AIDS шифруется как слово ALDS.
6.15.	Исходный алфавит {А, В,С, D}. Используется моноал-
фавитная система, в которой индивидуальные буквы шифруются
так:
А -> ВВ, В ААВ, С -> BAB, D А.
Например, слово ABDA шифруется как ВВААВАВВ. Покажи-
те, что расшифрование всегда однозначно. Покажите, что оно не
будет однозначным, если буквы зашифровать так:
А АВ, В —> ВА, С A, DС.
6.16.	Дополнение х бита, х определяется обычным образом.
Докажите, что в криптосистеме DES замена в исходном тексте
104
и в ключе каждого бита на его дополнение приводит к замене
каждого бита на его дополнение в криптотексте.
6.17.	Любое слово над алфавитом {Л, В} может возникнуть
как исходный текст. Первый моноалфавитный ключ зашифрова-
ния определяется соотношениями А —> CCD, В —> С, а второй
ключ — соотношениями А —> (7, В —> DC С.
Какие слова над {Л, В} шифруются как одно и то же слово
над {С,D} для обоих ключей?
6.18.	Наиболее часто встречающиеся триграммы в некотором
криптотексте есть LME, WRI и ZYC, в то время как в исходном
языке они THE, AND и ТНА. Какая матрица использовалась в
криптосистеме Хилла?
6.19.	Каждая буква х, 0 < х < 25 шифруется как (/(ж), mod
26), где f(x) — квадратный трехчлен. Найдите его, если известно,
что три наиболее часто встречающиеся буквы в криптотексте Z,
V, В (в этом порядке), в то время как в исходном языке это Е, Т,
N.
6.20.	Рассмотрим один очень слабый вариант криптосистемы
с одноразовым блокнотом. В качестве основной книги будет ис-
пользоваться эта. Например: ключ 12345 означает пятую букву
четвертого слова из третьего абзаца из параграфа 1.2. Зашиф-
руйте текст RACCOONDOGANDSAUNA, используя ключ 43333.
6.21.	И ключевое слово, и исходный текст могут считываться
из таблиц Виженера и Бьюфорта различными способами. Запи-
шите арифметические выражения для некоторых возникающих
отображений.
6.22.	Простую криптосистему, основанную на подстановках,
можно задать следующим образом. Фиксированная подстановка
на множестве чисел {1,2, ...,п} применяется к каждому блоку.
105
Например, SAUNA превращается в UNSAA, если п = 5, и подста-
новка меняет местами первую и третью буквы, а также вторую
и четвертую, оставляя пятую букву на месте. Покажите, что та-
кой же результат всегда можно получить, используя подходящую
криптосистему Хилла.
6.23.	Всякая криптосистема порождает отображение из мно-
жества слов исходных текстов в множество слов криптотекстов. В
целом о таких отображениях известно бывает очень много, но, на-
пример, отображение, индуцированное системой Цезаря, охарак-
теризовать легко. Рассмотрите различные криптосистемы и вы-
ясните, будут ли индуцированные отображения сохранять длины
слов?
6.24.	Дайте необходимые и/или достаточные условия реализу-
емости отображения с помощью квадрата Плейфейра.
6.25.	Объясните разницу (кроме разницы в размерах алфави-
тов) между отображениями, реализуемыми с помощью квадрата
Плейфейра и прямоугольника Плейфейра размера 3x9.
6.26.	Условие то же, что и в задаче 6.24, но теперь для ко-
леса Джефферсона. Обратите особое внимание на важную роль
расстояния между строчками исходного текста и криптотекста.
6.27.	Какой период получается у кулачковой матрицы (двоич-
ная матрица, в каждом столбце которой не более двух единиц) и
ступенчатой матрицы из текста книги?
6.28.	Постройте кулачковую и ступенчатую матрицы, приво-
дящие к периоду 17 (соответственно 19 * 21).
6.29.	Постройте кулачковую и ступенчатую матрицы, приво-
дящие к максимальному периоду.
6.30.	Покажите, что вектор А' размерности 10 является инъ-
106
ективным, т. е. не найдется такого а, что задача о рюкзаке имела
бы два решения.
6.31.	Пусть А = (&i,...,an) — рюкзачный вектор, т. е.
i = 1... п являются различными натуральными числами. Неко-
торое натуральное число V представляется при помощи Л, если
V можно выразить суммой а*, причем никакое щ не появляется
в сумме дважды. Если А — инъективный вектор, то тогда ясно,
что 2п — 1 числа представляются при помощи А. Это наибольшее
из возможных значений. Каким будет наименьшее из возможных
значений в терминах п?
6.32.	Для заданной задачи о рюкзаке (А, к) требуется найти
все решения. Покажите, что эта проблема даже не из NP.
6.33.	Почему число 2047 будет неудачным выбором для модуля
в криптосистеме RSA, кроме того, что это число слишком мало?
6.34.	Покажите, что экспоненты зашифровывания и расшиф-
ровывания будут совпадать, если модуль в RSA равен 35.
6.35.	Некоторые блоки исходного текста остаются неизменен-
ными при зашифровывании в RSA. Покажите, что их число будет
(1 + (е - 1,р - 1))(1 + (е - l)(g - 1)).
6.36.	Постройте пример применения алгоритма Шамира, ко-
гда для и/т отыскиваются, по крайней мере, два различных ин-
тервала. Можно ли что-нибудь сказать в общем случае о числе
различных интервалов. Возможно ли, что интервал вырождается
в точку?
6.37.	Докажите, что вектор (г, г — 1, г — 2,..., i — j), i — j > 1
будет супердостижимым только в случае, если j = 2 и п > 4.
6.38.	Докажите, что вектор (7,3,2) является ((7,15,38), 73,84)
супердостижимым.
107
6.39.	Докажите, что любой инъективный вектор (bl, 62; ЬЗ) бу-
дет перестановочно-супердостижимым.
6.40.	Опишите алгоритм нахождения наименьшего модуля ш,
такого, что данный сверхрастущий вектор будет (ДД,т) супер-
достижимым.
6.41.	Рассмотрите все рюкзачные векторы с компонентами
< 4. Покажите, что являются супердостижимыми следующие век-
торы:
(2,4,3), (4,3,2), (1,2,4), (2,4,1), (4,1,2).
6.42.	Докажите, что векторы (5,3,4) и (5,4,3) являются един-
ственными супердостижимыми векторами среди векторов с ком-
понентами 3, 4, 5.
6.43.	Выразите элементы поля GF(27) через корень многочле-
на, неприводимого над GF(3). Найдите порождающий элемент и
постройте таблицу дискретных логарифмов.
6.44.	Проведите криптоанализ криптосистемы, основанной на
плотных рюкзаках, в случае когда известна некоторая информа-
ция о секретной лазейке.
6.45.	Рассмотрите криптосистему RSA при р = 5, q = 11. По-
шлите подписанное сообщение пользователю, чья открытая экс-
понента зашифрования есть 13. (Имеем е = 7, d = 23.)
6.46.	Покажите, что число 3215031751 — составное и сильно
псевдопростое по каждому из оснований 2, 3, 5, 7.
6.47.	Рассмотрите общий метод обмена ключами в случае неко-
торых конкретных функций /. Можно ли улучшить отношение
108
т/т2 между работой, выполняемой легальным пользователем, и
работой, выполняемой криптоаналитиком.
6.48.	Предположим, что имеются алгоритмы для
SQUAREFREENESS(n) = (р2 | п или нет)
и нахождения ф(п). Можно ли свести один из них к другому?
6.49.	В функциональной криптосистеме 3 есть начальное зна-
чение, а функции /о(ж) — Зя и fi(x) = Зх + 1. Так, 011 зашифру-
ется как
З/оА/1 = 85.
Какой имеется простой способ расшифровать криптотекст, за-
писанный как десятичное число? Какие числа могут появляться
в качестве криптотекстов?
6.50.	Покажите, что рюкзачный вектор
(2106,880,1320,974,2388,1617,1568,2523,48,897)
будет супердостижимым.
6.51.	Приведите пример задачи о рюкзаке (А(г),а(г)), имею-
щей ровно i решений, i = 1,2,...
6.52.	Пусть секретная матрица имеет вид
/	1	0	1	0	0	1	\
Н=	0	1	1	1	0	1
\	1	0	1	1	1	о	/
Как расшифровывать открытый текст слишком большой дли-
ны?
6.53.	Ясно, что может быть построена двойственная теория
для убывающих и сверху бывающих векторов, которые определя-
ются аналогично возрастающим и сверхвозрастающим векторам.
109
В частности, понятие супер d-достижимости относится к сверх-
убывающим векторам. Приведите примеры инъективных векто-
ров, которые не будут ни супердостижимыми, ни супер d-дости-
жимыми.
6.54.	Постройте протокол для бросания кубика по телефо-
ну. Не стоит удовлетворяться следующим очевидным решением.
Подбрасываем монету три раза. В случае ”орел-орел-орел” или
’’решка-решка-решка” перебрасываем до получения любого дру-
гого результата.
6.55.	Предположим, что простые числа р и q в RSA имеют по
100 цифр, причем первая цифра у них не равна нулю. Оцените
число возможных значений для п.
6.56.	Раскрыть следующую криптограмму:
YJCVKUVJGJGCTVQHUCWPC? UVQXG
6.57.	Докажите, что остатки в алгоритме Евклида удовлетво-
ряют неравенствам rj+2 < rj/% для всех Постройте вариант это-
го алгоритма, в котором допускались бы отрицательные остатки
и сходимость была бы немного лучше:
rj+2 < rj+i/2.
110
6.58.	Расшифруйте
KOKOOKOKOONKOKOKOKKOKOKOKOKKOKOKOKOKOKKO
и
XACHINTAKARTURXACHINTAKSASHAXACHINTAKVALERYX.
Оба выражения на самом деле являются предложениями в из-
вестных естественных языках. Несомненно, что язык исходных
текстов играет какую-то роль!
6.59.	Рассмотрите исходный текст шифра, приведенный в при-
мере 6.56. Если добавить к концу исходного текста YES, то как
будет продолжен криптотекст?
6.60.	Пусть (a, m) = 1. Покажите, что = l(mod т) при
условии, что т отлично от чисел 1, 2, 4, рк и 2рк, где р — простое
число и k > 1.
6.61.	Докажите, что (ат — 1,ап — 1) =	— 1. Предполага-
ется, что а > 1.
6.62.	В системе RSA всегда найдутся такие экспоненты зашиф-
рования, что любой текст не меняется при зашифровании. Более
точно докажите следующее утверждение. Для любых р и q экспо-
нента е может быть выбрана так, что we = w(mod п) для всех w.
(Тривиальные случаи е = 1 и е = ф(п) + 1 исключаются.)
6.63.	Следующий алгоритм зашифровывания является клас-
сическим. Большое простое число р известно всем пользовате-
лям. Каждый пользователь выбирает и держит в секрете экс-
поненты зашифровывания и расшифровывания — е и d, причем
ed = l(mod р — 1). Таким образом, А шифрует исходный текст w
как
Ea^W) — w^(mod р).
Ill
Сначала А посылает В криптотекст JE?a(w) = с. В отвечает А
сообщением Ев (с) = щ. Наконец, А посылает РДщ) к В. Пока-
жите, что В в состоянии осуществить расшифрование, и рассмот-
рите возникающие здесь вопросы безопасности.
6.64.	Найдите необходимые и достаточные условия на р и t,
чтобы любой элемент 0,1 поля GF^p1) был бы (а) порождаю-
щим элементом, (6) квадратом некоторого порождающего элемен-
та.
6.65.	Предположим, что экспонента зашифрования е в системе
RSA является небольшой. Предположим, что некий оракул всегда
сообщает Е(х + г) для заданных Е(х) и г. (Понятно, что никакой
оракул не нужен, чтобы сообщить Е(х*г) по заданным Е(х) и г.)
Как в таком случае можно осуществить расшифрование?
6.66.	Разложите п = 4386607, зная ф(п) = 4382136.
6.67.	Рассмотрим следующую модификацию RSA, когда мо-
дуль п есть произведение трех больших чисел р, q и г. В этом слу-
чае по-прежнему выполняется ed = l(mod ф(п)). Отметьте пре-
имущества и недостатки этой модификации в сравнении с обыч-
ной системой RSA.
6.68.	Пусть f(x) и д(х) есть односторонние функции. При-
ведите эвристические аргументы в пользу того, что ни одна из
функций f(x) + д(х), f(x) * д(х) не обязательно должна быть од-
носторонней.
6.69.	Покажите, что следующая проблема лежит в пересече-
нии классов NP и Со — NP для любой криптосистемы. По за-
данному криптотексту требуется выяснить, будет или нет SUVI
подсловом в соответствующем исходном тексте.
6.70.	Рассмотрите случай п = 8137. Вычислите таблицу для
г(г), ANS(i) и t(i) при х = 20.
112
6.71.	В системе DES каждая S'-матрица переводит 6-битовый
вход в 4-битовый выход. Покажите, что изменение одного вход-
ного бита всегда приводит к изменению по крайней мере двух
выходных битов.
6.72.	Если зафиксировать два входных бита, то каждая S-
матрица определяет отображение 4-битовых наборов в 4-битовые
наборы. Какой бит можно зафиксировать, чтобы получить вза-
имнооднозначное отображение во всех восьми случаях? Приведи-
те пример отображения такого типа, не являющегося взаимно-
однозначным.
6.73.	Докажите, что имеется бесконечно много пар простых
чисел (р, д), таких, что р = q = 3(mod 4), но р ф q (mod 8). Исполь-
зуйте теорему Дирихле, утверждающую, что в последовательно-
сти ia + 6, i — 1,2,..., найдется бесконечно много простых чисел,
при условии, что а и Ь — натуральные числа и (а, Ь) = 1.
6.74.	Рассмотрим вектор рюкзака А = (ai,... ,ап), где щ —
= Р/рг^ i = 1.. .п, и pi — различные простые числа, произведение
которых равно Р. Укажите простой алгоритм для решения задачи
о рюкзаке (А,и).
6.75.	Постройте криптосистему Уильямса для р = 47, q = 59 и
зашифруйте текст РАБОТАТЬ С ЧИСЛАМИ ВИДА А + В^С В
RSA СЛОЖНЕЕ.
6.76.	Предположим, что в RSA р = 127 и q = 131. Сколько
сообщений шифруются в себя для обеих экспонент 29 и 31?
6.77.	Рассмотрите систему обмена ключей Диффи—Хеллмана
eq — 4079, q = 1709 и секретными числами A?i — 2344 и = 3420.
Какие числа раскрываются и каким будет общий ключ между
пользователями А1 и А2?
6.78.	Найдите все квадратные корни из 64 по модулю 105.
113
6.79.	В схеме Эль-Гамаля открываются простое число q и по-
рождающий элемент д поля GF(q). Что произойдет при зашифро-
вывании и расшифровывании, если в действительности д не будет
порождающим элементом?
6.80.	В шестнадцатиричном представлении 4-битовых набо-
ров 0000, 0001, ... , 1111 используются цифры 0, 1, 2, ... , 9, А,
В, С, D, Е, F в указанном порядке. Предположим, что ключом в
системе DES будет 0123456789ABCDEF. Зашифруйте тексты 516
И 616-
6.81.	Изучите криптографическое значение начальной пере-
становки в DES.
6.82.	Укажите все квадратичные вычеты по модулю 29, а так-
же по модулю 31. Докажите, что для всех простых р число 3 будет
квадратичным вычетом по модулю р тогда и только тогда, когда
р = l(mod 3).
6.83.	Пусть п будет таким, как в RSA. Покажите, что проблема
перечисления всех квадратичных вычетов по модулю п даже не
из NP.
6.84.	Рассмотрим схему идентификации при п — 2491. Сек-
ретный идентификатор Р состоит из тройки С1 = 143, С2 = 32,
СЗ = 2261. Опишите один этап протокола для выбранных значе-
ний г — 61 и S = {1,3}.
6.85.	При каких р сравнение
X2 — с * У2 = (mod р)
имеет решение, и найти их число.
114
6.86.	Рассмотрим основанную на итерации морфизмов систему
с начальными морфизмами
ho: а —> ас b —> Ьа с —> са,
hi: а —> аа b be с —> cb
и с начальным словом с. Покажите, что легальный получатель мо-
жет расшифровать следующим образом. Вначале к криптотексту
применяется интерпретирующий морфизм и получается слово w
над алфавитом {а, 6, с}. Строится слово iz, z-я буква которого есть
(2г~1 + 1)-я буква w. Слово и читается справа налево с заменой а
и b на 0 и 1 соответственно. (Слово и не содержит с.)
6.87.	Покажите, что нахождение секретной лазейки для крип-
тосистем, основанных на итерации морфизмов, есть NP-полная
проблема.
6.88.	Приведите причины, по которым декодирование для ко-
дов Гоппы существенно проще, чем для линейных кодов.
6.89.	Рассмотрите протокол для игры в покер по телефону.
Какие имеются возможности схитрить, если некоторые из выби-
раемых чисел pi и qi на самом деле не будут простыми?
6.90.	Придумайте метод разделения секретов, основанный на
некоторых других идеях, а не на китайской теореме об остатках.
6.91.	Придумайте протокол голосования для случая двух сверх-
держав и пяти обычных стран.
6.92.	А располагает 8 секретами и желает раскрыть В в точ-
ности один из них таким образом, чтобы только В знал, какой из
секретов был ему передан. Однако В не может решить, какой сек-
рет он хочет получить. Придумайте протокол для этой ситуации.
6.93.	Приведите конкретный числовой пример для 7-шагового
протокола. Рассмотрите возможности активного мошенничества
в этом протоколе.
115
6.94.	Опишите подробно протокол для тринадцати избирате-
лей и двух стратегий голосования: (а) с двумя агентствами С и
L, (Ь) только с одним агентством С.
6.95.	Придумайте протокол для доказательства с нулевым зна-
нием, что вам известно решение в данной задаче о рюкзаке. Же-
лательно использовать идею запирающихся ящиков.
6.96.	Рассмотрите задачу коммивояжера в виде, когда для дан-
ной карты с указанием всех расстояний и данного к требуется
найти маршрут через все города на карте длиной < к. Предло-
жите протокол с нулевым знанием для убеждения проверяющей,
что вам известно решение.
6.97.	Рассмотрите некоторую аксиоматическую систему для
пропозиционального исчисления и некоторую простую теорему,
доказательство которой состоит, скажем, из пяти шагов. Предло-
жите доказательство с нулевым знанием этой теоремы. Рассмот-
рите, будут или нет эти идеи распространяться на любые доказа-
тельства в произвольных формальных системах.
6.98.	Используя RSA, получите метод построения запираю-
щихся ящиков.
6.99.	Рассмотрите РФПИ (XxV X2V X^{X2V Х^(ххVx^
&Т3. Объясните, почему вы потерпите неудачу, если попытаетесь
доказать с нулевым знанием, что вы знаете выполняющее припи-
сывание переменных.
6.100.	Приведите численный пример для подписи на основе
методов, описанных в 4.6.
6.101.	Доказать, что для любого натурального числа h > 3
и h < п существует вложение множества всех двоичных наборов
длины [log2 С^] во множество всех таких двоичных наборов длины
п, у которых число единиц равно h.
116
6.102.	Ключом шифра, называемого "поворотная решетка",
является трафарет, изготовленный из квадратного листа клет-
чатой бумаги размера п х п (п — четно). Некоторые из клеток
вырезаются. Одна из сторон трафарета помечена. При наложе-
нии этого трафарета на чистый лист бумаги четырьмя возмож-
ными способами (помеченной стороной вверх, вправо, вниз, влево)
его вырезы полностью покрывают всю площадь квадрата, причем
каждая клетка оказывается под вырезом ровно один раз.
Буквы сообщения, имеющего длину п2, последовательно впи-
сываются в вырезы трафарета, сначала наложенного на чистый
лист бумаги помеченной стороной вверх. После заполнения всех
вырезов трафарета буквами сообщения трафарет располагается в
следующем положении и т. д. После снятия трафарета на листе
бумаги оказывается зашифрованное сообщение.
Найдите число различных ключей для произвольного четного
числа п.
6.103.	В адрес олимпиады пришло зашифрованное сообщение:
ФВМЕЖТИВФЮ.
Найдите исходное сообщение, если известно, что шифрпреобразо-
вание заключалось в следующем. Пусть яд, я?2 ~ корни трехчлена
х2 + Зх + 1. К порядковому номеру каждой буквы в стандартном
русском алфавите (33 буквы) прибавлялось значение многочлена
/(я:) = х6 + Зя:5 + я:4 + я:3 + 4я:2 + 4я: + 3, вычисленное либо при
х = яд, либо при х = х^ (в неизвестном нам порядке), а затем
полученное число заменялось соответствующей ему буквой.
6.104.	Для передачи информации от резидента Гарриваса в
Нагонии только что внедренному разведчику был установлен сле-
дующий порядок. Все сообщения резидента определены заранее и
пронумерованы числами 1, 2, 3, ... Разведчик, обладающий фе-
номенальной памятью, полностью запомнил соответствие между
сообщениями и их номерами. Теперь для того чтобы передать ин-
формацию разведчику, достаточно было сообщить ему лишь со-
117
ответствующее число. Для передачи числа в условленном месте
оставлялась равная этому числу денежная сумма.
На момент разработки операции в Нагонии имели хождение
денежные купюры достоинством 1, 3, 7 и 10 бут (бут — денеж-
ная единица Нагонии). Однако в результате денежной реформы
купюры достоинством 1 и 3 бут были изъяты из обращения.
Выясните, начиная с какого номера, можно передать разведчи-
ку любое сообщение, пользуясь только оставшимися в обращении
купюрами.
6.105.	Сколько существует упорядоченных пар натуральных
чисел а и Ь, для которых известны их наибольший общий делитель
d = 6 и их наименьшее общее кратное т = 6930. Сформулируйте
ответ и в общем случае, используя канонические разложения d и
т на простые множители.
6.106.	Дана криптограмма:
ФН х Ы = ФАФ
+ х —
ЕЕ + Е = НЗ
ИША + МР = ИМИ
Восстановите цифровые значения букв, при которых справед-
ливы все указанные равенства, если разным буквам соответству-
ют различные цифры. Расставьте буквы в порядке возрастания
их цифровых значений и получите искомый текст.
6.107.	Одна фирма предложила устройство для автоматиче-
ской проверки пароля. Паролем может быть любой непустой упо-
рядоченный набор букв в алфавите {а, Ь, с}. Будем обозначать та-
кие наборы большими латинскими буквами. Устройство перера-
батывает введенный в него набор Р в набор Q = ф(Р)- Отобра-
жение ф держится в секрете, однако про него известно, что оно
118
определено не для каждого набора букв и обладает следующими
свойствами. Для любого набора букв Р:
1)	ф(аР) = Р;
2)	ф(ЪР) = ф(Р)аф(Ру
3)	набор ф{сР) получается из набора ф(Р) выписыванием букв
в обратном порядке.
Устройство признает предъявленный пароль верным, если
ф(Р) — Р. Например, трехбуквенный набор bab является верным
паролем, так как
<p(bab) — (р{аЪ)а(р{аЬ} — bab.
Подберите верный пароль, состоящий более чем из трех букв.
6.108.	В древнем шифре, известном под названием "Сцита-
ла", использовалась полоска папируса, которая наматывалась на
круглый стержень, виток к витку без просветов и нахлестов. Да-
лее, при горизонтальном положении стержня, на папирус построч-
но записывался текст сообщения. После этого полоска папируса с
записанным на ней текстом посылалась адресату, имеющему точ-
но такой же стержень, что позволяло ему прочитать сообщение.
В наш адрес поступило сообщение, зашифрованное с помощью
шифра ’’Сцитала”. Однако его автор, заботясь о том, чтобы строч-
ки были ровные, во время письма проводил горизонтальные ли-
нии, которые остались на полоске в виде черточек между буквами.
Угол наклона этих черточек к краю ленты равен а, ширина по-
лоски равна d, а ширина каждой строки равна h. Укажите, как,
пользуясь имеющимися данными, прочитать текст.
6.109.	Исходное цифровое сообщение коммерсант шифрует и
передает. Для этого он делит последовательность цифр исходно-
го сообщения на группы по пять цифр в каждой и после двух
последовательных групп приписывает еще две последние циф-
ры суммы чисел, изображенных этими двумя группами. Затем
к каждой цифре полученной последовательности он прибавляет
соответствующий по номеру член некоторой целочисленной ариф-
119
метической прогрессии, заменяя результат сложения остатком от
деления его на 10.
Найдите исходное цифровое сообщение по шифрованному со-
общению
423461405313
6.110.	Рассмотрим преобразование цифрового текста, в кото-
ром каждая цифра заменяется остатком от деления значения мно-
гочлена F(x) = Ь(х$ + 7х2 + Зх + а) на число 10, где а, b — фик-
сированные натуральные числа.
Выясните, при каких значениях а, b указанное преобразование
может быть шифрпреобразованием (т. е. допускает однозначное
расшифрование).
6.111.	При установке кодового замка каждой из 26 латинских
букв, расположенных на его клавиатуре, сопоставляется произ-
вольное натуральное число, известное лишь обладателю замка.
Разным буквам сопоставляются не обязательно разные числа. По-
сле набора произвольной комбинации попарно различных букв
происходит суммирование числовых значений, соответствующих
набранным буквам. Замок открывается, если сумма делится на
26.
Докажите, что для любых числовых значений букв существует
комбинация, открывающая замок.
6.112.	Сообщение, записанное в алфавите
АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯ
зашифровывается при помощи последовательности букв этого же
алфавита. Длина последовательности равна длине сообщения.
Шифрование каждой буквы исходного сообщения состоит в сло-
жении ее порядкового номера в алфавите с порядковым номе-
ром соответствующей буквы шифрующей последовательности и
замене такой суммы на букву алфавита, порядковый номер кото-
рой имеет тот же остаток от деления на 30, что и эта сумма.
120
Восстановите два исходных сообщения, каждое из которых со-
держит слово КОРАБЛИ, если результат их зашифрования при
помощи одной и той же шифрующей последовательности изве-
стен:
ЮПТЦАРГШАЛЖЖЕВЦЩЫРВУУ
и
ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ
6.113.	Буквы русского алфавита занумерованы в соответствии
с табли-цей:
А	Б	В	Г	д			3	И		л	м	Н	О	
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Р	С	Т	"У	Ф		ц		Ю	
16	17	18	19	20	21	22	23	24	25
Для зашифровывания сообщения, состоящего из п букв, выбира-
ется ключ К — некоторая последовательность из п букв приведен-
ного выше алфавита. Зашифровывание каждой буквы сообщения
состоит в сложении ее номера в таблице с номером соответству-
ющей буквы ключевой последовательности и замене полученной
суммы на букву алфавита, номер которой имеет тот же остаток
от деления на 30, что и эта сумма.
Прочтите шифрованное сообщение: РБЬНТСИТСРРЕЗОХ, ес-
ли известно, что шифрующая последовательность не содержала
никаких букв, кроме А, Б и В.
6.114.	Установите, можно ли создать проводную телефонную
сеть связи, состоящую из 993 абонентов, каждый из которых был
бы связан ровно с 99 другими.
6.115.	Шифрпреобразование простой замены в алфавите А =
— {«1,^2? • • •, состоящем из различных букв, заключается в
121
замене каждой буквы шифруемого текста буквой того же алфа-
вита, причем разные буквы заменяются разными. Ключом шиф-
ра простой замены называется таблица, в которой указано, ка-
кой буквой надо заменить каждую букву алфавита А. Если слово
СРОЧНО зашифровать простой заменой с помощью ключа:
Н
М
У
р	с	т	У	ф		ц	ч	щ	щ	ь	ы
3	в	р		м	л		А	и	О		Е)
то получится слово ВЗДАБД. Зашифровав полученное слово с
помощью того же ключа еще раз, получим слово ЮШЫЧЯЫ.
Сколько всего различных слов можно получить, если указанный
процесс шифрования продолжать неограниченно?
6.116.	Сообщение, зашифрованное в пункте А шифром про-
стой замены в алфавите из букв русского языка и знака пробе-
ла (—) между словами, передается в пункт Б отрезками по 12
символов. При передаче очередного отрезка сначала передают-
ся символы, стоящие на четных местах в порядке возрастания
их номеров, начиная со второго, а затем — символы, стоящие на
нечетных местах (также в порядке возрастания их номеров), на-
чиная с первого. В пункте В полученное шифрованное сообщение
дополнительно шифруется с помощью некоторого другого шифра
простой заменой в том же алфавите, а затем таким же образом,
как и из пункта А, передается в пункт В. По перехваченным в
пункте В отрезкам:
СО-ГЖТПНБЛЖО
РСТКДКСПХЕУБ
- Е-ПФПУБ - ЮОБ
СП-ЕОКЖУУЛЖЛ
СМЦХБЭКГОЩПЫ
УЛКЛ-ИКНТЛЖГ
122
восстановите исходное сообщение, зная, что в одном из передан-
ных отрезков зашифровано слово КРИПТОГРАФИЯ.
6.117.	Дана последовательность чисел Ci, С2,...,	..., в ко-
торой Сп есть последняя цифра числа пп. Докажите, что эта по-
следовательность периодическая и ее наименьший период равен
20.
6.118.	Исходное сообщение, состоящее из букв русского алфа-
вита и знака пробела (—) между словами, преобразуется в цифро-
вое сообщение заменой каждого его символа парой цифр согласно
следующей таблице:
А	Б	В	г	д			3	И		л	м	н	О
01	02	03	04	05	06	07	08	09	10	и	12	13	14
	Р	С	Т	У	Ф		• • •	я	—
15	16	17	18	19	20	21	• • •	30	31
Для зашифровывания полученного цифрового сообщения исполь-
зуется отрезок последовательности из задачи 6.117, начинающий-
ся с некоторого члена С^. При зашифровывании каждая цифра
сообщения складывается с соответствующей цифрой отрезка и за-
меняется последней цифрой полученной суммы. Восстановите со-
общение:
2339867216458160670617315588
6.119.	Ключом шифра, называемого ’’решетка”, является пря-
моугольный трафарет размером 6 х 10 клеток. В трафарете вы-
резаны 15 клеток так, что при наложении его на прямоугольный
лист бумаги размером 6 х 10 клеток четырьмя возможными спо-
собами его вырезы полностью покрывают всю площадь листа.
Буквы сообщения (без пропусков) последовательно вписыва-
ются в вырезы трафарета (по строкам, в каждой строке слева на-
123
право) при каждом из четырех его возможных положений. Прочи-
тайте исходный текст, если после зашифрования на листе бумаги
оказался следующий текст (на русском языке):
р		т	Ej	ш	А	в	Е	с	«л
О		т	А	л	—-	ь	3	т	—.—
—	У		Т	—		А	ь	—	с
н	п	—	ь		"У	—	ш	л	с
т	и	ь	3	ы	я	Е	м	—	О
—	Е	ф	—-	—	р	О	—	с	м
6.120.	Криптограмма
12 2 24 5 3 21 6 29 28 2 20 18 20 21 5 10 27 17 2 11 2 16 —
19 2 27 5 8 29 12 31 22 2 16, 19 2 19 5 17 29 8 29 6 29 16 :
8 2 19 19 29 10 19 29 14 19 29 29 19 10 2 24 2 И 2 16
10 14 18 21 17 2 20 2 28 29 16 21 29 28 6 29 16.
получена заменой букв на числа (от 1 до 32) так, что разным
буквам соответствуют разные числа. Отдельные слова разделены
несколькими пробелами, буквы — одним пробелом, знаки препи-
нания сохранены. Буквы "е" и "ё” не различаются. Прочитайте
четверостишие В. Высоцкого.
6.121.	"Шифровальный диск" используется для зашифровы-
вания числовых сообщений. Он состоит из неподвижного диска
и вращающегося на нем диска меньшего диаметра, имеющих об-
щую ось. На обоих дисках нанесены цифры от 0 до 9, которые
расположены в вершинах правильных 10-угольников, вписанных
в диски.
Цифра X на неподвижном диске зашифровывается в цифру Y
подвижного диска, лежащую на том же радиусе, что и X.
Для построения вписанного 10-угольника без транспортира на-
до уметь строить угол в 36°. Попытайтесь вычислить с точностью
до 0,1 значение какой-либо тригонометрической функции такого
угла без таблиц и калькулятора.
124
6.122.	Зашифровывание фразы на латинском языке осуществ-
лено в два этапа. На первом этапе каждая буква текста заменяет-
ся на следующую в алфавитном порядке (последняя Z заменяется
на первую Л). На втором этапе применяется шифр простой заме-
ны с неизвестным ключом. Его применение заключается в замене
каждой буквы шифруемого текста буквой того же алфавита, при
этом разные буквы заменяются разными буквами. Ключом такого
шифра является таблица, в которой указано, какой буквой надо
заменить каждую букву алфавита.
По данному шифртексту
OSZJX FXRE YOQJSZ RAYFJ
восстановите открытое сообщение, если известно, что для исполь-
зованного (неизвестного) ключа результат шифрования не зави-
сит от порядка выполнения указанных этапов для любого откры-
того сообщения. Пробелы в тексте разделяют слова.
Латинский алфавит состоит из следующих 24 букв:
ABCDEFGHIJLMNOPQRSTUVXYZ
6.123.	Для проверки телетайпа, печатающего буквами русско-
го алфавита
АБВГДЕ ЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
передан набор из 9 слов, содержащий все 33 буквы алфавита. В
результате неисправности телетайпа на приемном конце получены
слова
ГЪЙ АЭЕ БПРК ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ
Восстановите исходный текст, если известно, что характер неис-
правности таков, что каждая буква заменяется буквой, отстоящей
от нее в указанном алфавите не дальше, чем на две буквы. На-
пример буква Б может перейти в одну из букв {А, Б, В, Г}.
125
6.124.	Исходное сообщение из букв русского алфавита преоб-
разуется в числовое сообщение заменой каждой его буквы числом
по следующей таблице:
А	Б	В	Г	д	Е		3	И	IC	Л	м	н	О
00	01	02	03	04	05	06	07	08	09	10	11	12	13
	Р	С	Т	У	(J)		• • •	
14	15	16	17	18	19	20	• • •	29
Для зашифровывания полученного числового сообщения исполь-
зуется шифрующий отрезок последовательности Ai, Л2,... подхо-
дящей длины, начинающийся с Ащо-
При зашифровывании каждое число числового сообщения скла-
дывается с соответствующим числом шифрующего отрезка. Затем
вычисляется остаток от деления полученной суммы на 30, кото-
рый по данной таблице заменяется буквой. Восстановите сообще-
ние КЕНЗЭРЕ, если шифрующий отрезок взят из последователь-
ности, у которой Ai = 3 и Ak+i = Ak + 3(fc2 + к + 1) для любого
натурального к.
6.125.	Чтобы запомнить периодически меняющийся пароль в
ЭВМ, математики придумали следующий способ. При известном
числе (например номере месяца в году) пароль представляет собой
первые шесть цифр наименьшего решения уравнения
(Число меньшей значности дополняется справа необходимым чис-
лом нулей.) Решите такое уравнение при произвольном а > 0.
6.126.	Комбинация (j?,y, z) трех натуральных чисел, лежащих
в диапазоне от 10 до 20 включительно, является отпирающей
для кодового замка, если выполнено соотношение F(x, у, z) = 99.
Найдите все отпирающие комбинации для замка с F(x,y, z) =
= Зх2 — у2 — 7z.
126
6.127.	Сообщение было построчно записано в таблицу, имею-
щую 20 столбцов. При этом в каждую клетку таблицы записы-
валось по одной букве сообщения, пробелы между словами были
опущены, а знаки препинания заменены на условные комбина-
ции: точка — ТЧК, запятая — ЗПТ Затем столбцы таблицы были
некоторым образом переставлены, в результате чего был получен
текст:
ЯНЛВКРАДОЕТЕРГОМИЗЯЕ
ЙЛТАЛФЫИПЕУИООГЕДБОР
ЧРДЧИЕСМОНДКХИНТИКЕО
НУЛАЕРЕБЫЫЕЕЗИОННЫЧД
ЫТДОЕМППТЩВАНИПТЯЗСЛ
ИКСИ_ТЧНО_ _Е_ЛУЛ_Т_Ж
Прочтите исходное сообщение.
6.128.	Зашифрование сообщения состоит в замене букв исход-
ного текста на пары цифр в соответствии с некоторой (известной
только отправителю и получателю) таблицей, в которой разным
буквам алфавита соответствуют разные пары цифр. Криптогра-
фу дали задание восстановить зашифрованный текст.
В каком случае ему будет легче выполнить задание: если из-
вестно, что первое слово второй строки — "термометр" или что
первое слово третьей строки — "ремонт"? Обоснуйте свой ответ.
(Предполагается, что таблица зашифрования криптографу неиз-
вестна.)
6.129.	При передаче сообщений используется некоторый шифр.
Пусть известно, что каждому из трех шифрованных текстов
ЙМЫВОТСЬЛКЪГВЦАЯЯ
УКМАПОЧСРКЩВЗАХ
ШМФЭОГЧСЙЪКФЬВЫЕАКК
127
соответствовало исходное сообщение МОСКВА. Попробуйте рас-
шифровать три текста
ТПЕОИРВНТМОЛАРГЕИАНВИЛЕДНМТААГТДЬТКУБЧ
КГЕИШНЕИАЯРЯ
ЛСИЕМГОРТКРОМИТВАВКНОПКРАСЕОГНАЬЕП
РТПАИОМВСВТИЕОБПРОЕННИГЬКЕЕАМТАЛВТДЬСО
УМЧШСЕОНШЬИАЯК
при условии, что двум из них соответствует одно и то же сообще-
ние. Сообщениями являются известные крылатые фразы.
6.130.	В системе связи, состоящей из 2003 абонентов, каждый
абонент связан ровно с другими. Определите все возможные зна-
чения N.
6.131.	Квадратная таблица размером 2003 х 2003 заполнена
натуральными числами от 1 до 2003 так, что в каждой строке
присутствуют все числа от 1 до 2003. Найдите сумму чисел, сто-
ящих на диагонали, которая соединяет левый верхний и правый
нижний углы таблицы, если заполнение таблицы симметрично от-
носительно этой диагонали.
6.132.	Текст
МИМОПРАСТЕТИРАСИСПД
ИСАФЕИИБОЕТКЖРГЛЕОЛО
ИШИСАННСЙСАООЛТЛЕЯТУ
ИЦВЫИПИЯДПИЩПЬПСЕЮЯЯ
получен из исходного сообщения перестановкой его букв. Текст
УЩФМШПДРЕЦЧЕШЮШЧДАКЕ
ЧМДВКШБЕЕЧДФЭПЙЩГШФЩ
ЦЕЮЩФПМЕЧПМЕРЩМЕОФЧЩ
ХЕШРТГДИФРСЯЫЛКДФФЕЕ
128
получен из того же исходного сообщения заменой каждой бук-
вы на другую букву так, что разные буквы заменены разными, а
одинаковые — одинаковыми. Восстановите исходное сообщение.
6.133.	На каждой из трех осей установлено по одной вращаю-
щейся шестеренке и неподвижной стрелке. Шестеренки соедине-
ны последовательно. На первой шестеренке 33 зубца, на второй
— 10, на третьей — 7. На каждом зубце первой шестеренки по
часовой стрелке написано по одной букве русского языка в алфа-
витном порядке:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
На зубцах второй и третьей шестеренки в порядке возрастания по
часовой стрелке написаны цифры от 0 до 9 и от 0 до 6 соответ-
ственно. Когда стрелка первой оси указывает на букву, стрелки
двух других осей указывают на цифры.
Буквы сообщения шифруются последовательно. Зашифрова-
ние производится вращением первой шестеренки против часовой
стрелки до первого попадания шифруемой буквы под стрелку. В
этот момент последовательно выписываются цифры, на которые
указывают вторая и третья стрелки. В начале шифрования стрел-
ка 1-го колеса указывала на букву А, а стрелки 2-го и 3-го колес
— на цифру 0.
1.	Зашифруйте слово ОЛИМПИАДА.
2.	Расшифруйте сообщение 24809283911211.
6.134.	Цифры от 1 до 9 расположены на окружности в неко-
тором неизвестном порядке. При зашифровании цифрового сооб-
щения каждая, отличная от 0, цифра заменяется на соседнюю с
ней цифру на окружности по часовой стрелке, а при расшифро-
вании — на соседнюю с ней цифру на окружности против часовой
стрелки. Цифра 0 остается без изменения в обоих случаях.
Укажите условия, при которых порядок цифр на данной окруж-
ности можно однозначно восстановить по двум цифровым текстам
— результатам расшифрования и зашифрования одного и того же
цифрового текста с помощью данной окружности.
129
6.135.	Докажите, что для каждого простого числа р после-
довательность ai, «2,	• • • является периодической с периодом 2,
если ап равно остатку от деления числа рп+2 на 24 при всех п > 1.
6.136.	Какое наименьшее число соединений требуется для ор-
ганизации проводной сети связи из 10 узлов, чтобы при выходе из
строя любых двух узлов связи сохранялась возможность переда-
чи информации между любыми двумя оставшимися (хотя бы по
цепочке через другие узлы)?
6.137.	В компьютерной сети используются пароли, состоящие
из цифр. Чтобы избежать хищения паролей, их хранят на диске
в зашифрованном виде. При необходимости использования про-
исходит однозначное расшифрование соответствующего пароля.
Зашифрование пароля происходит посимвольно одним и тем же
преобразованием. Первая цифра остается без изменения, а резуль-
тат зашифрования каждой следующей цифры зависит только от
нее и от предыдущей цифры.
Известен список зашифрованных паролей: 428540012393,
5393511, 4249188780319, 4245133784397, 4262271910365, 425237003
1465, 4245133784735 и два пароля 4208212275831, 4242592823026,
имеющиеся в зашифрованном виде в этом списке. Можно ли опре-
делить какие-либо другие пароли? Если да, то восстановите их.
6.138.	В результате перестановки букв сообщения получена
криптограмма:
БТИПЧЬЛОЯЧЫЬТОТПУНТНОНЗЛЖАЧОЬОТУНИУХНИ
ППОЛОЬЧОЕЛОЛС
Прочтите исходное сообщение, если известно, что оно было раз-
бито на отрезки одинаковой длины г, в каждом из которых буквы
переставлены одинаково по следующему правилу. Буква отрезка,
имеющая порядковый номер (ж = 1,2,..., г), в соответствующем
отрезке криптограммы имеет порядковый номер f(x) = ах ф 5,
130
где а и b — некоторые натуральные числа в системе счисления с
основанием г + 1.
6.139.	Знаменитый математик Леонард Эйлер в 1759 г. нашел
замкнутый маршрут обхода всех клеток шахматной доски ходом
коня ровно по одному разу. Прочтите текст, вписанный в клетки
шахматной доски по такому маршруту. Начало текста в а4 (см.
рис. 4).
6.140.	Для рисования на большой прямоугольной доске ис-
пользуется мел с квадратным сечением со стороной 1 см. При
движении мела стороны сечения всегда параллельны краям дос-
ки. Как начертить выпуклый многоугольник площадью 1 м2 с
наименьшей площадью границы (площадь границы не входит в
площадь многоугольника)?
Рис. 4
6.141	Цифры 0,1,..., 9 разбиты на несколько непересекаю-
щихся групп. Из цифр каждой группы составляются всевозмож-
ные числа, для записи каждого из которых все цифры группы
используются ровно один раз (учитываются и записи, начина-
ющиеся с нуля). Все полученные числа расположили в порядке
131
возрастания и /с-му числу поставили в соответствие к-ю букву ал-
фавита
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
Оказалось, что каждой букве соответствует число и каждому чис-
лу соответствует некоторая буква. Шифрование сообщения осу-
ществляется заменой каждой буквы соответствующим ей числом.
Если ненулевое число начинается с нуля, то при шифровании этот
нуль не выписывается. Восстановите сообщение 873146507381 и
укажите таблицу замены букв числами.
6.142.	Сообщение, составленное из нулей и единиц, шифруется
двумя способами. При первом способе каждый нуль заменяется на
последовательность из нулей и следующих за ними к% единиц,
а каждая единица заменяется на последовательность из к% нулей.
При втором способе шифрования каждая единица заменяется на
последовательность из к^ единиц и следующих за ними к$ нулей, а
каждый нуль заменяется на последовательность из к$ нулей. При
каких натуральных значениях ki, i = 1,2,...,6 найдется хотя бы
одно сообщение, которое будет одинаково зашифровано обоими
способами? Укажите общий вид таких сообщений.
6.143.	Сообщение, подлежащее зашифрованию, представляет
собой цифровую последовательность, составленную из дат рож-
дения 6 членов оргкомитета олимпиады. Каждая дата представ-
лена в виде последовательности из 8 цифр, первые две из которых
обозначают день, следующие две — месяц, а остальные — год. На-
пример, дата рождения великого математика Л. Эйлера — 4 апре-
ля 1707 г. — представляется в виде последовательности 04041707.
Для зашифрования сообщения строится ключевая последователь-
ность длины 48. Для ее построения все нечетные простые числа,
меньшие 100, выписываются через запятую в таком порядке, что
модуль разности любых двух соседних чисел есть та или иная
степень числа 2. При этом каждое простое число выписано ровно
один раз, а числа 3, 5 и 7 записаны в виде 03, 05 и 07 соответствен-
132
но. Удалив запятые из записи этой последовательности, получим
искомую ключевую последовательность.
При зашифровании цифровой последовательности, представ-
ляющей сообщение, ее цифры почленно складываются с соответ-
ствующими цифрами ключевой последовательности, при этом
каждая полученная сумма заменяется ее остатком от деления на
10. В результате зашифрования сообщения получена последова-
тельность:
150220454213266744305682533362327363924975709849
Определите даты рождения членов оргкомитета олимпиады.
6.144.	Квадрат размером 13 х 13 разбит на клетки размером
1 х 1. В начальный момент некоторые клетки окрашены в чер-
ный цвет, а остальные — в белый. По клеткам квадрата прыгает
Криптоша. В момент попадания Криптоши в очередную клет-
ку происходит изменение цвета на противоположный у всех тех
клеток, расстояния от центров которых до центра клетки с Крип-
тошей — натуральные числа. После того как Криптоша побывал
в каждой клетке квадрата ровно 1999 раз, квадрат оказался рас-
крашенным так, как показано на рисунке. Восстановите цвет всех
клеток квадрата в начальный момент (см. рис. 5).
6.145.	Разложите число 230 + 1 на простые множители.
6.146.	Суммой двух букв назовем букву, порядковый номер ко-
торой в алфавите имеет тот же остаток от деления на число букв в
алфавите, что и сумма порядковых номеров исходных двух букв.
Суммой двух буквенных последовательностей одинаковой длины
назовем буквенную последовательность той же длины, получен-
ную сложением букв исходных последовательностей, стоящих на
одинаковых местах:
133
а)	докажите, что существует последовательность из 33 различ-
ных букв русского алфавита, сумма которой с последовательно-
стью букв, представляющей собой сам этот алфавит, не содержит
одинаковых букв;
б)	докажите, что сумма любой последовательности из 26 раз-
личных букв английского алфавита с последовательностью букв,
представляющей собой сам этот алфавит, содержит не менее двух
одинаковых букв.
6.147.	Некоторую последовательность из букв русского алфа-
вита
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШ
щ ъ ы ь э ю Я
194919" раз прибавили по правилу задачи 6.144 к слову КРИПТО-
ША. Получили слово АНАЛИТИК. Найдите эту последователь-
134
ность. Какое наименьшее число раз надо прибавить ее к слову
АНАЛИТИК, чтобы получить слово КРИПТОША?
6.148.	Каждую букву исходного сообщения заменили двузнач-
ным порядковым номером в русском алфавите согласно таблице
А	Б	В	г			ж	3	И		л	м	Н	О
01	02	03	04	05	Об	07	08	09	10	11	12	13	14
п	Р	С	т	Р	С			(J)		Ц
15	16	17	17	18	19	20	21	22	23	24
	Ш	Т Т Т	Ъ	Ы	Ь	э	ю	Я
25	26	27	28	29	30	31	32	33
Полученную цифровую последовательность разбили (справа
налево) на трехзначные цифровые группы без пересечений и про-
пусков. Затем каждое из полученных трехзначных чисел умножи-
ли на 77 и оставили только три последние цифры произведения.
В результате получилась следующая последовательность цифр:
317564404970017677550547850356
Восстановите исходное сообщение.
6.149.	Клетки квадрата 4x4 пронумеровали так, что клетка
в правом нижнем углу получила номер 1, а все остальные полу-
чили разные номера — от 2 до 16. Оказалось, что суммы номеров
клеток каждой строки, каждого столбца, а также каждой из двух
диагоналей квадрата одинаковы {"магический" квадрат). Клетки
"магического" квадрата заполнили буквами некоторого сообще-
ния так, что его первая буква попала в клетку с номером 1, вторая
— в клетку с номером 2 и т. д. В результате построчного выписы-
вания букв заполненного квадрата (слева направо и сверху вниз)
получилась последовательность букв
ЫРЕУСТЕВЬТАБЕВКП
135
Восстановите "магический" квадрат и исходное сообщение.
6.150.	Построить систему защиты информации с открытым
ключом на основе решений диофантового уравнения хп + уп = zn
над полями Галуа.
136
Приложение
Таблица Виженера
А	Б	в	Г	Д	Е	Ё	Ж	3	И	Й	К	Л	М	н	О	П	Р	с	т	У	ф	X	ц	ч	ш	щъ		ы	ь	э	юя		
Б	в	г	Д	Е	Ё	Ж	3	И	Й	К	Л	м	Н	о	П	Р	С	т	У	ф	X	Ц	ч	ш	ш	ъ	ы	ь	э	ГС	я		Д
В	г	д	Е	Ё	Ж	3	И	Й	К	Л	м	н	О	п	Р	С	т	У	ф	X	ц	ч	ш	ш	Ъ	ы	ь	э	ю	я			Б
Г	д	Е	Ё	Ж	3	И	Й	К	Л	м	н	о	П	р		т*	У	ф	X	ц	ч	ш	ш	ъ	ы	ь	э	ю	я			Б	В
д.	Е	Ё	Ж	3	И	Й	К	Л	М	н	о	п	Р	с	т	У	ф	X	ц	ч	ш	щ	Ъ	ы	ь	э	ю	я		А	Б	В	р
Е	Ё	Ж	3	И	й	К	Л	М	Н	о	п	р	£	т	У	ф	X	ц	ч		ш		ы	ь	э	ю	я		А	Б	В	Г	Д
Ё	Ж	3	И	Й	к	Л	м	Н	О	п	р	с	гр	у	ф	X	ц	ч	ш	щъ		ы	ь	э	ю	я		А	Б	В	Г	Д	Е
Ж	3	И	Й	К	л	м	н	О	П	р	с	Т*	У	ф	X	и	ч	ш	щ	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Ё
3	И	Й	К	Л	м	н	о	П	Р	с	т	У	ф	X	ц	ч	ш	ш	Ь	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Ё	Ж
И	Й	К	л	м	н	о	п	Р	£	гр	У	ф	X	ц	ч	ш	Щ	ъ	ы	ь	э		я		А	Б	В	Г	Д	Е	Ё	Ж	3
Й	К	Л	м	н	о	п	р		т	У	ф	X	ц	ч	ш	щ	ъ	ы	ь	э	ю	я		А	Б	в	Г	Д	Е	Ё	Ж	3	И
К	Л	м	н	о	п	р	с	т	У	ф	X	ц	ч	ш	ш	ъ	ы	ь	э	ю	я		А	Б	В	|£_	Д	Е	Ё	Ж	3	И	Й
Л,	м	н	О	п	р	с	т	У	ф	X	ц	ч	ш	щ	ъ	ы	ь	э	*9	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К
м	н	о	п	р	с	т	У	ф	X	ц	ч	ш	Ш	ъ	ы	ь	э	ю	Я		А	Б	В	г	Д	Е	Ё	Ж	3	И	Й	К	Л
н	о	п	р	с	т	У	ф	X	ц	ч	ш	Щ	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	Л	М
0	п	р		т	У	ф	X	и	ч	ш	ш	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	й	К	Л	М	Н
П|	р		т	У	ф	X	ц	ч	ш	ш	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	к	Л	М	Н	О
р	с	т	У	ф	X	Ц	ч	ш	ш	ъ	ы	ь	э	ГС	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	л	м	Н	О	П
	у.	У	ф	X	ц	ч	ш	Щ	ъ	ы	ь	э	ГС	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	Л	м	н	О	П	Р
т	У	ф	X	ц	ч	ш	ш	ъ	ы	ь	э	1€	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	л	м	н	о	П	Р	С
У	ф	X	ц	ч	ш	III	ъ	ы	ь	э	ю	я!		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	Л	м	н	о	п	Р	£	т
ф	X	ц	ч	ш	ш	ъ	ы	ь	э	ГС	я		А	Б	В	Г	Д	Е	Ё	Ж	3	И	Й	К	Л	М	н	о	п	р	£	т	У
X	ц	ч	ш	ш	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Ё	Ё	Ж	3	И	Й	К	л	м	Н	о	п	р	с	т	У	ф
ц	ч	ш	ш	ъ	ы	ь	э	ю	я		А	Б	В	Г	д	Е	Е	Ж	3	И	Й	К	Л	м	н	О	п	р	£	т	У	ф	X
ч		ш	ъ	ы	ь	э	ю	я			Б	В	Г	д	Е	Ё	Ж	3	И	й	К	Л	М	н	о	П	р	с	т	У	ф	X	ц
ш	щъ		ы	ь	э	к:	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	й	К	Л	м	Н	о	п	Р	£	т	У	ф	X	ц	ч
ш	ъ	ы	ь	э	ГС	я		А	Б	В	Г	Д	Е	Ё	Ж	3	и	й"	к	Л	М	н	О	п	р	CJ	гр	У	ф	X	ц	ч	ш
ъ	ы	ь		ю	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	й	к	л	М	Н	О	П	р	с	т	У	ф	X	ц	ч	ш	щ
ы	ь		гс	я		А	Б	В	Г	Д	Е	Ё	Ж	3	И	Й	к	л	м	Н	О	п	Р	с	т	У	ф	X	ц	ч	ш	Щ	к
ь	э	ю	я		А	Б	В	Г	Д	Е	Ё	Ж	3	И	Й	К	л	м	н	О	П	р	С	т	У	ф	X	ц	ч	ш	щ	ъ	ы
э	ю	я		А	Б	В	Г	д	Е	Ё	Ж	3	И	Й	К	Л	м	н	о	П	Р	с	т	У	ф		ц	ч	ш	ш	ъ	ы	ь
ю	я		А	Б	В	Г	Д	Е	Ё	Ж	3	И	й	К	Л	М	н	О	п	Р		г	У	ф		ц	ч	III	III	ъ	ыь		э
я		А	Б	В	Г	Д	Е	Ё	Ж	3	И	Й	к	Л	М	Н	о	п	р	С	т	У	ф		ц	ч	ш	ш	ъ	ы	ь	)	К)
	А	Б	В	Г	Д	Е	Ё	Ж	3	И	Й	К	л	М	Н	О	п	р	с	т	У	ф		ц	ч	ш	щ	ъ	ы	ь	э	ЦО	Я
137
Таблица относительных частот
встречаемости русских букв
а	0,062	И	0,062	Р	0,040	ш	0,006
б	0,014	о и	0,010	С	0,045	ттт	0,003
в	0,038	к	0,028	т	0,053	ы	0,016
г	0,013	л	0,035	У	0,021	ь, ъ	0,014
д	0,025	м	0,026	ф	0,002	э	0,003
е, ё	0,072	н	0,053	X	0,009	ю	0,006
ж	0,007	0	0,090	Ц	0,004	я	0,018
3	0,016	п	0,023	ч	0,012		
138
ЛИТЕРАТУРА
1.	Алферов А. П., Зубов А. Ю., Кузьмин А. С., ЧеремушкинА. В.
Основы криптографии. — М.: Гелиос АРВ, 2002.
2.	Введение в криптографию/Под ред. В. В. Ященко. — М.,
1998.
3.	Защита информации в персональных ЭВМ/A. В. Спесивцев,
В. А. Вегнер, А. Ю. Крутиков, В. В. Серегин, В. А. Сидоров. —
М., 1993.
4.	Коблиц Н. Курс теории чисел и криптографии. — М., 2001.
5.	Нечаев В. И. Элементы криптографии. Основы теории за-
щиты информации. — М., 1999.
6.	Саломаа А. Криптография с открытым ключом. — М., 1995.
7.	Хоффман Л. Дж. Современные методы защиты информа-
ции. — М., 1980.
8.	Чмора А. Л. Современная прикладная криптография. — М.:
Гёлиос АРВ, 2001.
9.	Шеннон К. Теория связи в секретных системах. — М., 1949.
ОГЛАВЛЕНИЕ
Глава 1. Основные обозначения и понятия.................3
1.1. Основные обозначения...............................3
Задачи и упражнения.....................................4
1.2. Основные понятия...................................5
Задачи и упражнения.....................................6
Глава 2. Общие принципы безопасной передачи информации...8
2.1.	Общие подходы засекречивания информации............8
Задачи и упражнения.....................................8
2.2.	Общая схема системы защиты информации..............9
Задачи и упражнения....................................10
2.3.	Построение функций шифрования. Односторонние функции.12
Задач и и упражнения...................................14
2.4.	Защита информации от помех в каналах связи........16
Задачи и упражнения....................................18
2.5.	Различные способы сокрытия информации.............18
Задачи и упражнения....................................19
2.6.	Защита данных с элементом маскировки..............20
Задачи и упражнения....................................21
Глава 3. Элементарные методы цифрового шифрования.
Симметричные системы защиты информации.................22
3.1.	Криптографические методы защиты информации........22
Задачи и упражнения....................................23
3.2.	Метод простой подстановки (замены)................25
140
Задачи и упражнения.....................................26
3.3.	Метод перестановки.................................30
Задачи и упражнения.....................................32
3.4.	Метод блочных шифров...............................34
Задачи и упражнения.....................................35
3.5.	Метод гаммирования.................................37
Задачи и упражнения.....................................38
3.6.	Метод шифрования на основе теоремы Эйлера—Ферма....40
Задачи и упражнения.....................................41
3.7.	Композиция шифров................................. 42
Задачи и упражнения.....................................43
3.8.	Симметричные системы защиты информации.............45
Задачи и упражнения.....................................45
3.9.	Стандарт криптозащиты США — DES....................49
Задачи и упражнения.....................................51
3.10.	Стандарт криптосистемы России — ГОСТ 28147-89.....52
Задачи и упражнения.....................................55
Глава 4. Системы защиты информации с открытым ключом.
Асимметричные системы...........................56
4.1.	Асимметричные системы защиты информации............56
Задачи и упражнения.....................................56
4.2.	Примеры асимметричных систем защиты информации.....57
4.2.1.	Числовой вариант системы защиты RSA..............58
4.2.2.	Многопользовательский вариант системы защиты RSA.59
4.2.3.	Полиноминальный вариант системы защиты RSA.......60
141
Задачи и упражнения.....................................61
4.3.	Система защиты информации Диффи—Хеллмана...........63
Задачи и упражнения.....................................64
4.4.	Система защиты информации на основе заданного рюкзака.65
Задачи и упражнения.....................................67
4.5.	Система защиты информации на основе кода Варшамова.70
Задачи и упражнения.....................................12
4.6.	Обобщенная рюкзачная криптосистема с открытым ключом..74
Задачи и упражнения.....................................77
4.7.	Системы защиты информации на основе решений
многостепенных систем диофантовых уравнений............80
4.7.1.	Система защиты информации на основе специального
рюкзака.................................................80
4.7.2.	Система защиты информации на основе секретного
рюкзака................................................82
4.7.3.	Система защиты информации на основе
многопараметрических решений...........................83
Задачи и упражнения.....................................84
4.8.	Временные оценки относительно трудоемкости
арифметических операций................................87
Задачи и упражнения.....................................88
4.9.	Относительная криптостойкость систем защиты информации....90
Задачи и упражнения.....................................91
Глава 5. Вопросы установления подлинности и целостности
данных. Системы электронной подписи............93
5.1.	Аутентификация данных.............................93
142
Задачи и упражнения...................................94
5.2.	Электронная цифровая подпись.....................95
Задачи и упражнения...................................96
5.3.	Реализация цифровой подписи на основе криптосистемы
Эль-Гамаля...........................................97
Задачи и упражнения...................................99
5.4.	Математика разделения секрета....................99
Задачи и упражнения..................................101
Глава 6. Дополнительные задачи и упражнения
по криптографии......................................102
Приложение...........................................137
Литература...........................................139
143
Учебное издание
Издание печатается в авторской редакции.
Криптография в упражнениях и задачах
Заведующая редакцией Т. А Денисова
Корректор Е. Н. Клитина
Компьютерная верстка О. Ю. Самариной
Издательство «Гелиос АРВ».
Издательская лицензия ЛР № 066255 от 29.12.1998 г.
107140, г. Москва, Верхняя Красносельская ул., 16.
Тел./факс: (095) 264-44-39, e-mail: info@gelios-arv.ru
Адрес в Internet: http://www.gelios-arv.ru
Формат 60x84/16. Печать офсетная. 9 печ. л. Тираж 2000 экз. Бумага газетная.
Заказ № 1625.
Отпечатано с готовых диапозитивов в
ОАО «Чебоксарская типография № 1».
428019, г. Чебоксары, пр. И. Яковлева, 15.
Криптография в упражнениях и задачах
Приведено более 400 различных задач и
упражнений, сгруппированных в соответствии
с основными направлениями развития крипто-
графических методов повышения
информационной безопасности
автоматизированных систем обработки
данных. Каждому разделу предшествует
краткое введение, состоящее из определений
и основных понятий соответствующей
области науки. Представленные задачи и
упражнения охватывают как классические
методы криптографической защиты
информации, так и современные методы
обеспечения конфиденциальности
и целостности данных, ориентированные на
применение вычислительной техники.
©