все лекции

личество вариантов декодирования равно количеству всевозможных клю-

чей, – то есть шифр будет нераскрываем.

Но в практике идеальное сжатие не выполняется, так как конечен

кодирующий алфавит и дополнительно накладываются ограничения,

вызываемые вычислительной сложностью алгоритмов кодирования и

декодирования.

Поэтому говорят не о нулевой избыточности, а о заданной низкой из-

быточности.

И такая ненулевая избыточность приводит к «старению ключа»:

по мере кодирования символов открытого текста всё больше информации о ключе открывается в шифротексте.

То есть, количество вариантов расшифровки снижается и ключ необходи-

мо обновлять.

Типовые архиваторы не используют в криптографических целях, так

как они являются адаптивными кодерами и начинают сжатие после

нескольких сотен символов входного сообщения.

А при современных вычислительных средствах и достижениях криптоло-

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

Поэтому универсальные кодирующие устройства интегрируются с шифратором в одной системе для того, чтобы интенсивность исполь-

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

СПОСОБ РЭНДОМИЗАЦИИ.

В этом способе к кодовой последовательности добавляется шум от

дополнительного источника (генератора случайных чисел).

9

Даже при высокой избыточности кода, кодовую последователь-

ность удаётся сделать случайной, неотличимой от последовательности

равновероятных и независимых кодовых символов.

Количество вариантов расшифровки может быть меньше мощности множе-

ства ключей, но информация о самом ключе остаётся полностью закрытой, – она просто отсутствует в шифротексте (независимо от длины

сообщения). То есть ключ не устаревает по мере кодирования.

СМЕШАННЫЙ СПОСОБ.

Здесь объединяют сжатие и рэндомизацию, что даёт заданную криптостойкость шифра при коротком неустаревающем секретном

ключе.

По своей вычислительной эффективности этот способ превосходит

другие способы, но требуя при этом линейного или логарифмического ро-

ста объёма памяти кодера и декодера,

а также полиноминально-логарифмического роста времени кодиро-

вания и декодирования при снижении избыточности.

В той или иной мере ТРЕБОВАНИЯМ, предъявляемым К ШИФРАМ, ис-

пользуемым для криптографической защиты, отвечают следующие.

А) ШИФРЫ ПЕРЕСТАНОВОК: символы шифруемого текста

переставляются по определённому правилу в пределах некоторого

блока этого текста.

При достаточной длине блока и сложном неповторяющемся порядке перестановки можно достигнуть приемлемой для простых практических приложений

стойкости шифра.

10

Б) ШИФРЫ ПОДСТАНОВКИ (простой замены): символы шифруе-

мого текста заменяются символами того же алфавита или другого алфавита (или нескольких алфавитов) в соответствии с заранее обусловленной схемой замены.

В) ШИФРЫ ГАММИРОВАНИЯ: символы шифруемого текста

складываются с символами некоторой случайной последовательно-

сти, именуемой гаммой шифра.

Стойкость шифрования определяется длиной (периодом) неповто-

ряющейся гаммы шифра. Так как ЭВМ может генерировать практически беско-

нечную гамму шифра, то этот способ является одним из основных для шифрова-

ния информации в АС.

Д) ШИФРЫ С АНАЛИТИЧЕСКИМ ПРЕОБРАЗОВАНИЕМ шифруемых данных: шифруемый текст преобразуется по некоторому аналитическому правилу (формуле).

Классически, В ШИФРАХ НЕОБХОДИМО РЕАЛИЗОВАТЬ ДВА ОБЩИХ ПРИНЦИПА:

а) РАССЕИВАНИЕ – распространение влияния одного знака открытого текста на много знаков шифротекста, что позволяет скрыть статистические свойства открытого текста;

б) ПЕРЕМЕШИВАНИЕ – использование таких шифрующих пре-

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

только затруднять раскрытие, но и обеспечивать лёгкость шифрования и де-

шифрования при известном пользователю секретном ключе.

Распространённый способ использования этих принципов – примене-

11

ние СОСТАВНОГО шифра: реализуется в виде некоторой последова-

тельности простых шифров, каждый из которых вносит свой вклад в

значительное суммарное рассеивание и перемешивание.

В составных шифрах чаще всего используют простые перестановки и под-

становки. Так в современном блочном шифре с блоками текста и шифротекста в виде двоичных последовательностей длиной 64 бита, каждый блок может принимать 264 значений. Поэтому подстановки выполняются в очень большом алфавите, содержащем до 264 ≈ 1019 «символов».

При многократном чередовании простых перестановок и подстановок, управляемых достаточно длинным секретным ключом, можно полу-

чить очень стойкий шифр с хорошим рассеиванием и перемешиванием.

5.3.2 Шифрование в асимметричных криптосистемах и однонаправленные функции

Концепция асимметричных криптосистем с открытым ключом ос-

нована на применении однонаправленных функций.

Пусть X и Y некоторые множества. Функция f: X→Y является однонаправ-

ленной, если для всех x X можно легко вычислить функцию у = f(x), где у

Y.

И в то же время для большинства у Y достаточно сложно получить значе-

ния x X, такое, что f(x) = y. То есть, для однонаправленных функций

нет эффективных алгоритмов обратного преобразования Y → X.

Например, ЦЕЛОЧИСЛЕННОЕ УМНОЖЕНИЕ: прямая задача – вычисление произведения двух очень больших простых чисел P и Q –

несложная задача для ЭВМ:
N = PQ.	()

Обратная задача – разложение на множители большого целого

12

числа N = PQ является практически неразрешимой задачей при доста-

точно больших значениях N.

При целом N 2664 и P Q для разложения числа N потребуется около 1023 операций (практически неразрешимая задача).

Следующая однонаправленная функция – МОДУЛЬНАЯ

ЭКСПОНЕНТА с фиксированным основанием и модулем.

Это криптосистема, предложенная ЭльГамалем в 1985 г. Используется как для цифровых подписей, так и для шифрования. Криптостойкость определяется трудоёмкость вычисления дискретного алгоритма в конечном поле.

Для ГЕНЕРАЦИИ ПАРЫ КЛЮЧЕЙ выбираются простое число Р и

два случайных числа G и X (оба этих числа должны быть меньше P). Затем

вычисляется:

Y = GX [mod P].

Открытым ключом являются Y, G и P. Ключи G и P можно сделать

общими для группы пользователей. Секретным является X.

Чтобы ПОДПИСАТЬ сообщение M, сначала выбирается случайное число К, взаимно простое с (Р – 1). Затем вычисляется А = GK [mod P],

и с помощью расширенного алгоритма Евклида из уравнения

M = (X A + K B) [mod (P – 1)],

находится B.

Цифровой подписью является пара чисел А и В. Случайное значение К должно храниться в секрете.

лгоритм вклида – алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин. Древнегреческие математики называли этот алгоритм «взаимное вычитание». лгоритм вклида – процедуры последовательного вза-

13

имного вычитания.

Для иллюстрации, алгоритм вклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим знаменатель меньше чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147: 1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка: 147 = 7 × 21 + 0.

Так как последний остаток равен нулю, алгоритм заканчивается и НОД (1071, 462)=21. В табличной форме, шаги были следующие:

Шаг k	Равенство		Частное и остаток
0	1071	= q0 462 + r0	q0 = 2 и r0 = 147
1	462 = q1 147 + r1		q1 = 3 и r1 = 21
2	147	= q2 21 + r2	q2 = 7 и r2 = 0; алгоритм заканчивается

}

Для проверки подписи необходимо убедиться, что:

YAAB [mod P] = GM [mod P].

Каждая новая подпись требует нового значения K, и это значение

должно выбираться случайным образом. Если злоумышленник раскроет K,

используемое Алисой, он сможет раскрыть секретный ключ Алисы X. Если злоумышленник сможет получить два сообщения, подписанные при помощи одного и того же K, он сможет раскрыть X, даже не зная K.

В целом, модульная экспонента с основанием А по модулю N пред-

ставляет собой функцию (A и N – целые числа, такие, что 1 A < N):

f		( x) A	X		,	()
	A,N		mod N

где х – целое число, 1 х (N–1).

Термин "по модулю N" и символ modN отражают так называемую "арифметику часов",

например: 3 ч дня + 14 ч 5 ч утра (mod12). Это вычисление записывается, как 17 5(mod12), и

читается: "17 сравнимо с 5 по модулю 12". Запись в общем виде выглядит следующим образом: a b(mod N) , и читается как "а" сравнимо с "b" по модулю N. То есть a = b + kN для неко-

торых k.

Из математики, если у = AX, то х = loqАy. Поэтому задачу обраще-

ния функции fA,N(x) называют задачей нахождения дискретного лога-

рифма.

14

Задача дискретного логарифмирования формулируется следующим

образом: для известных A, N и y найти целое число х, такое, что

AX(mod N) = у.

()

Алгоритм этого вычисления за приемлемое время пока не найден и

модульная экспонента считается условно однонаправленной функцией.

Теория целых чисел даёт оценку: при А 2664 и N 2664 потребуется около

1026 операций.

Также существует класс однонаправленных функций с

«ПОТАЙНЫМ ХОДОМ».

Функция f: X→Y относится к этому классу в том случае, если она

является однонаправленной и возможно эффективное вычисление обратной функции, если известен «потайной ход» (секретное число,

строка или другая информация, ассоциирующаяся с данной функцией).

ПРИМЕЧАНИЕ:

Современная ТЕХНОЛОГИЯ ШИФРОВАНИЯ часто основана на

применении двух различных ключей.

Одноразовый псевдослучайный сеансовый ключ используется для

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

А долговременный ключ используется для шифрования (дешифрования)

сеансовых ключей [5]. Долговременный ключ – это элемент ключа шифра,

действующий в неизменном виде длительное время, определяемое правилами

пользования шифром.

15

Для обеспечения возможности последующего расшифрования, сеансовый

ключ должен быть сохранен вместе с зашифрованной информацией.

Для этого используется долговременный ключ шифрования, который хра-

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

Применение асимметричных (двухключевых) криптосистем ведёт к большим задержкам при шифровании (дешифровании) по сравнению с сим-

метричными криптосистемами.

Для минимизации задержки применяют гибридную схему, где асим-

метричная криптосистема применяется ДЛЯ ШИФРОВАНИЯ КОРОТКОГО СЕАНСОВОГО КЛЮЧА: отправитель выполняет

шифрование на открытом ключе получателя, а получатель дешифру-

ет на своём секретном ключе.

А ИНФОРМАЦИОННЫЕ ПОТОКИ в течение сеанса ШИФРУЮТСЯ с использованием ключей СИММЕТРИЧНОЙ

КРИПТОСИСТЕМЫ.

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

системе когда шифруется короткий сеансовый ключ, а сеансовый ключ принад-

лежит симметричной криптосистеме – с его помощью шифруются соб-

ственно сообщения. Данный метод называется методом «цифрового

конверта» (digital envelope).

То есть, «цифровой конверт» – это протокол асимметричного шифрования ключа, который используется затем для симметричного шифрования информа-

ции.

5.4 Понятие квантовой криптографии Задача безопасной пересылки ключей может быть решена с помощью квантовой рассылки

16

ключей QKD (Quantum Key Distribution).

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

Степень надёжности в данной методике выше, чем в случае применения алгоритмов с парными ключами, например, RSA. Здесь ключ может генерироваться во время передачи по совершенно открытому оптическому каналу.

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

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

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

Так поляризация фотонов может быть ортогональной диагональной или циркулярной. Измерение одного вида поляризации рэндомизует другую составляющую.

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

Отправитель кодирует отправляемые данные, задавая определённые квантовые состояния, получатель регистрирует эти состояния. Затем получатель и отправитель совместно обсуждают результаты наблюдений. В конечном итоге со сколь угодно высокой достоверностью можно быть уверенным, что переданная и принятая кодовые последовательности тождественны. Обсуждение результатов касается ошибок, внесённых шумами или злоумышленником, и ни в малейшей мере не раскрывает содержимого переданного сообщения. Может обсуждаться чётность сообщения, но не отдельные биты. При передаче данных контролируется поляризация фотонов. Поляризация может быть ортогональной (горизонтальной или вертикальной), циркулярной (левой или правой) и диагональной (450 или 1350).

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

Получатель измеряет поляризацию фотонов, используя произвольную последовательность базовых состояний (ортогональная или циркулярная). Получатель открыто сообщает отправителю, какую последовательность базовых состояний он применил. Отправитель открыто уведомляет получателя о том, какие базовые состояния использованы корректно. Все измерения, выполненные при неверных базовых состояниях, отбрасываются. Измерения интерпретируются согласно двоичной схеме: лево-циркулярная поляризация или горизонтальная – 0, правоциркулярная или вертикальная – 1. Реализация протокола осложняется присутствием шума, который может вызвать ошибки. Вносимые ошибки могут быть обнаружены и устранены с помощью подсчёта чётности, при этом один бит из каждого блока отбрасывается. Беннет в 1991 году предложил следующий протокол.

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

2 Строки делятся на блоки размера k (k выбирается так, чтобы вероятность ошибки в блоке была мала).

3 Для каждого блока отправитель и получатель вычисляют и открыто оповещают друг друга о полученных результатах. Последний бит каждого блока удаляется.

4 Для каждого блока, где чётность оказалась разной, получатель и отправитель производят итерационный поиск и исправление неверных битов.

5 Чтобы исключить кратные ошибки, которые могут быть не замечены, операции пунктов 1–4 повторяются для большего значения k.

6 Для того, чтобы определить, остались или нет необнаруженные ошибки, получатель и отправитель повторяют псевдослучайные проверки:

–получатель и отправитель открыто объявляют о случайном перемешивании позиций половины бит в их строках;

–получатель и отправитель открыто сравнивают чётности. сли строки отличаются, чётности должны не совпадать с вероятностью 0,5;

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

17

сли отличий нет, после m итераций получатель и отправитель получают идентичные строки с вероятностью ошибки 2–m.

5.5 Блочные шифры

Как отмечалось в предыдущем подразделе, в различной мере требованиям, предъявляемым к шифрам, используемым для криптографической защиты,

отвечают:

–шифры перестановок;

–шифры замены (подстановки);

–шифры гаммирования;

–шифры с аналитическим преобразованием шифруемых данных.

Все современные шифры используют принцип Керкхгоффса:

секретность шифра обеспечивается секретностью ключа, а не сек-

ретностью алгоритма шифрования.

(Правило Керкгоффса – общепринятое в криптографии предположение проведения криптоанализа, впервые сформулированное голландским криптографом Н. Керкгоффсом («компрометация системы не должна причинять неудобств корреспондентам»). В современном понимании это правило означает, что описание криптосистемы (криптопротокола) может быть полностью известно противнику и/или нарушителю, а стойкость криптографическая основана только на том, что не известен ключ (секретный).

Не делая общедоступным описание сути криптосистемы, можно дополнительно

повысить надёжность шифра [17]. Но анализ надёжности таких систем всегда

должен производиться исходя из того, что противник имеет всю информацию о применяемом криптоалгоритме, – неизвестен только ре-

ально использованный ключ.

Стойкость криптосистемы зависит:

–от сложности алгоритмов преобразования;

–длины ключа (объёма ключевого пространства);

–метода реализации (программной или аппаратной).

18