Инф. безопасность

	Арифметический сдвиг вправо	X'=X SHR V
	Циклический сдвиг влево	X'=X ROL V
	Циклический сдвиг вправо	X'=X ROR V
	Табличные подстановки
	S-box (англ. Substitute)	X'=Table[X,V]

В качестве параметра V для любого из этих преобразований может использоваться:

9фиксированное число (например, X'=X+125)

9число, получаемое из ключа (например, X'=X+F(Key))

9число, получаемое из независимой части блока (например, X2'=X2+F(X1))

9Последний вариант используется в схеме, названной по имени ее создателя сетью Фейстеля (нем. Feistel).

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

Поскольку операция зашифровки или расшифровки отдельного блока в процессе кодирования пакета информации выполняется многократно (иногда до сотен тысяч раз), а значение ключа и, следовательно, функций Vi(Key) остается неизменным, то иногда становится целесообразно заранее однократно вычислить данные значения и хранить их в оперативной памяти совместно с ключом. Поскольку эти значения зависят только от ключа, то они в криптографии называются материалом ключа. Необходимо отметить, что данная операция никоим образом не

41

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

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

Классическая сеть Фейстеля имеет следующую структуру (рисунок 8):

Рисунок 8 — Структура сети Фейстеля

Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической

42

схеме их две. Величины Vi именуются параметрами сети, обычно это функции от материала ключа. Функция F называется образующей. Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом сети Фейcтеля. Оптимальное число раундов K – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптоскойстость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла на столь активное распространение сети Фейcтеля – ведь при обнаружении, скажем, какого-либо слабого места в алгоритме, почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, а лишь указываются разумные пределы (обязательно нижний, и не всегда – верхний) этого параметра.

Сразу же возникает вопрос, – является ли данная схема обратимой? Очевидно, да. Сеть Фейcтеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Фейcтеля не нужно вычислять функцию F-1.

Более того, как нетрудно заметить, сеть Фейcтеля симметрична. Использование операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Фейcтеля, но с инверсным порядком параметров Vi. Заметим, что для обратимости сети Фейcтеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой, которой в качестве параметра передается вектор величин Vi либо в исходном, либо в инверсном порядке.

С незначительными доработками сеть Фейcтеля можно сделать и абсолютно симметричной, то есть выполняющей функции шифрования и дешифрования одним и тем же набором

43

операций. Математическим языком это записывается как «Функция EnCrypt тождественно равна функции DeCrypt».

Рисунок 9 — Модификация сети Фейстеля для двух ветвей

Модификацию сети Фейcтеля для большего числа ветвей применяют очень часто. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по

44

модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейcтеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рисунке 10а Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейcтеля с большим количеством ветвей) применяются две модифицированные схемы, называемые «type- 2» и «type-3». Они изображены на рисунках 7б и 7в.

Рисунок 10 — Модификации сети Фейстеля для четырех ветвей

Сеть Фейcтеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и оконечных преобразований над шифруемым блоком. Подобные преобразования, выполняемые обычно также либо «исключающим ИЛИ» или сложением имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейcтеля, определяется на 95% функцией F и правилом вычисления Vi из ключа. Эти функции и являются объектом все новых и новых исследований специалистов в области криптографии.

45

5 Идея открытых ключей

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

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

Конечно, алгоритм зашифрования открывает в математическом смысле и алгоритм расшифрования, потому что они «обратны» друг другу. Предположим тем не менее, что потребуются сотни лет работы криптоаналитика для раскрытия алгоритма расшифрования из алгоритма зашифрования. Тогда раскрытиеалгоритмазашифрованияничемунеугрожает.

В математике, так же как и в реальной жизни, существуют одно сторонние улицы.[9] Легко добраться по такой улице из А в В, тогда как практически невозможно добраться из В в А. Шифрование рассматривается как направление от А к В. Хотя мы можем двигаться в этом направлении, мы не в состоянии двигаться в обратном направлении— расшифрования.

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

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

46

очень малой вероятностью шифруются одинаково. Шифрование сообщенияSAUNA можетбытьтаким:

Сообщение	Выбранное имя	Криптотекст
S	Scott	3541920
A	Adleman	4002132
U	Ullman	7384502
N	Nivat	5768115
A	Aho	7721443

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

Заметим, что алгоритм зашифрования не является детерминированным. Бесконечно много криптотекстов можно получить из одного и того же исходного сообщения. C другой стороны, каждый криптотекст порождает только один исходный текст.

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

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

легковычислимо

X

f(x)

трудновычислимо

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

47

очень многих случаях не получить ответа совсем. Метод становится заведомо непригодным при использовании старого справочника.

Система, основанная на телефонном справочнике, годится только в качестве начальной иллюстрации, а не для серьезного применения. Действительно, не так трудно составить «обратные» справочники.

Идея криптографии с открытым ключом тесно связана с идеей односторонних функций. По заданному аргументу x легко вычислить значение функции f(x), тогда как определение x из f(x) трудновычислимо. Здесь «трудновычислимость» понимается в смысле теории сложности.

Определение x из f(x) трудновычислимо только для криптоаналитика. Легальный получатель имеет подходящую лазейку. Далее такие односторонние функции будем называть

криптографическими.

Упомянем по этому поводу, что ни одного примера криптографической односторонней функции неизвестно. Зато существуетмногокриптографическихфункцийf(x), таких, что:

9Легковычислитьf(x)из x.

9Определение x из f(x), вероятно, будет трудновычислимым.

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

Пример 16 . Наш пример основан на задаче о рюкзаке. Задан набор

(a1, a2,..., an) = A

п различных положительных целых чисел и еще одно положительное целое число k. Задачей является нахождение таких ai, если этовозможно, суммакоторыхравнаk.

Впростейшем случае k указывает размер рюкзака, а каждое из чисел ai указывает размер предмета, который может быть упакован

врюкзак. Задачей является нахождение такого набора предметов, чтобы рюкзакбылполностьюзаполнен.

Вкачестве иллюстрации рассмотрим число 3231 и набор из 10

чисел

48

(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523). Заметим, что 3231 = 129 + 473 + 903 + 561+1165 .

Такимобразом, мынашлирешение.

В принципе решение всегда может быть найдено полным перебором подмножеств А и проверкой, какая из их сумм равна k. В нашем случае это означает перебор 210 = 1024 подмножеств (включая при этом и пустоемножество). Этовполнеосуществимо.

Но что будет, если существует несколько сотен чисел ai? В нашем примере n=10, чтобы не усложнять изложение. В реальных условиях примербудетиметь, скажем, 300 ai-х. Сутьздесьвтом, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сравнению с полным перебором. Поиск среди 2300 подмножеств не поддаетсяобработке.

Наш n-набор А определяет функцию f(x) следующим образом. Любое число х в интервале 0 < х < 2n — 1 может быть задано двоичным представлением из n разрядов, где при необходимости добавляются начальные нули. Теперь определим f(x) как число, получаемое из А суммированием всех таких ai, что соответствующий разряд в двоичном представлении х равен 1. Так,

f(1) = f(0…001)= an f(2) = f(0…010) = an-1

f(3) = f(0…011) = an-1+ an

и т. д. Используявекторное умножение, мыможем записать f(x) = ABx

где Вх — вектор-столбецдвоичногопредставления х. Нашепредыдущее равенствоможетбытьзаписановвиде

f(364) = f(0101101100) = 129 + 473 + 903 + 561 + 1165 = 3231 .

Функция f(x) определялась n-набором А. Очевидно, что если мы в состоянии вычислить х из f(x), то практически за то же время будет решена задача о рюкзаке: по х немедленно вычисляется его двоичное представление, которое в свою очередь дает компоненты набора А, входящие в сумму для f(x).

Сначала рассмотрим, как «рюкзачные векторы» А могут быть использованы в качестве основы криптосистемы. Исходное сообщение вначале кодируется и разбивается на n- разрядные блоки. Если это не обходимо, последний блок дополняется в конце нулями. Каждый из n- разрядных блоков теперь шифруется с помощью вычисления значения функции f

49

для этого блока.

Если исходное сообщение написано по-английски, естественным способом кодирования является замена каждой буквы двоичным представлением ее порядкового номера в алфавите. Для этих целей потребуется пять битов. В следующей таблице нумерация букв начинается с 1, тогда как пробел между двумясловамизадаетсячислом0.

Буква	Число	Двоичное
		представление
Пробел	0	00000
A	1	00001
B	2	00010
C	3	00011
D	4	00100
E	5	00101
F	6	00110
G	7	00111
H	8	01000
I	9	01001
J	10	01010
K	11	01011
L	12	01100
M	13	01101
N	14	01110
O	15	01111
P	16	10000
Q	17	10001
R	18	10010
S	19	10011
T	20	10100
U	21	10101
V	22	10110
W	23	10111
X	24	11000
Y	25	11001
Z	26	11010

Рассмотрим предыдущий набор и исходное сообщение

50