Информационная безопасность / Общий_лекция

91

осуществления случайного выбора на каком-либо шаге алгоритма, либо как результат выполнения (вычислителем) измерений параметров окружения (внешних объектов). Алгоритм выполняется неким субъектом (вычислителем).

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

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

Итак, криптографические протоколы дают возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

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

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

Текст - упорядоченный набор из элементов алфавита.

Вкачестве примеров алфавитов, используемых в современных ИС можно привести следующие:

*алфавит Z33 - 32 буквы русского алфавита и пробел;

*алфавит Z256 - символы, входящие в стандартные коды ASCII и КОИ-8;

*бинарный алфавит - Z2 = {0,1};

*восьмеричный алфавит или шестнадцатеричный алфавит; Шифрование - преобразовательный процесс: исходный текст, который

носит также название открытого текста, заменяется шифрованным текстом.

92

исходный	Криптографическая	шифрованный
	система

КЛЮЧ

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

шифрованный	Криптографическая	исходный
	система

КЛЮЧ

Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы разделяются на симметричные и с открытым ключом.

Всимметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ.

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

изакрытый, которые математически связаны друг с другом. Информация

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

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

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

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

93

Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых:

количество всех возможных ключей;

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

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

Требования к криптосистемам

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

Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:

зашифрованное сообщение должно поддаваться чтению только при наличии ключа;

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

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

знание алгоритма шифрования не должно влиять на надежность защиты;

незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа;

структурные элементы алгоритма шифрования должны быть неизменными;

дополнительные биты, вводимые в сообщение в процессе шифрования, должен быть полностью и надежно скрыты в шифрованном тексте;

длина шифрованного текста должна быть равной длине исходного текста;

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

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

алгоритм должен допускать как программную, так и аппаратную реа-

94

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

4. Математические основы криптографии.

Высшая арифметика, или теория чисел, изучает свойства натуральных чисел 1, 2, 3, ... Эти числа интересуют человека с давних времен. Античные летописи говорят о том, что уже тогда арифметику знали глубже и шире, чем это было необходимо для нужд повседневной жизни. Но систематической, самостоятельной наукой высшая арифметика становится лишь в новое время, начиная с открытий Ферма (Fermat, 1601–1665).

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

4.1.Арифметика целых чисел.

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

Множество целых чисел

Множество целых чисел, обозначенных Z, содержит все числа (без дробей) от минус бесконечности до плюс бесконечности (рис. 2.1).

Рис. 2.1. Множество целых чисел.

То есть к целым числам относятся: натуральные (1,2,3,4,…), 0, и отрицательные натуральные числа.

К рациональным относятся все целые и дробные.

Простыми называются числа, которые не имеют собственных множителей – 2,3,5,7,11,13,17,19,23,29,31,37….

Собственным множителем числа А называется множитель отличный от 1 и числа А.

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

95

Бинарные операции

Вкриптографии нас интересует три бинарных операции в приложении

кмножеству целых чисел.

Бинарные операции имеют два входа и один выход. Для целых чисел определены три общих бинарных операции — сложение, вычитание и умножение. Каждая из этих операций имеет два входа ( a и b ) и выход ( c ), как это показано на рис. 2.2. Два входа принимают числа из множества целых чисел; выход выводит результат операции — число из множества целых чисел.

Обращаем внимание, что деление не относится к этой категории операций, потому что мы скоро убедимся, что этой операции нужны два выхода вместо одного.

Рис. 2.2. Три бинарных операции для множества целых чисел

Пример 2.1

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

операции.
Сложение	5+9=14	(-5)+9=4	5+(-9)=-4	(-5)+(-9)=-14
Вычитание	5-9=-4	(-5)-9=-14	5 - (-9)=14	(-5)- (-9)=+4
Умножение	5 x 9=45	(-5) x 9=-45	5 x (-9)=-45	(-5) x (-9)=45

Деление целых чисел

В арифметике целых чисел, если мы a делим на n, мы можем получить q и r. Отношения между этими четырьмя целыми числами можно показать как

В этом равенстве a называется делимое ; q — частное ; n — делитель и r — остаток. Обратите внимание, что это — не операция,

96

поскольку результат деления a на n — это два целых числа, q и r. Мы будем называть это уравнением деления.

Пример 2.2

Предположим, что a = 255, а n = 23. Мы можем найти q = 11 и r = 2, используя алгоритм деления, мы знаем из элементарной арифметики — оно определяется, как показано на рис. 2.3.

Рис. 2.3. Пример 2.2, нахождение частного и остатка

Большинство компьютерных языков может найти частное и остаток, используя заданные языком операторы. Например, на языке C оператор "/" может найти частное, а оператор "%" — остаток.

Два ограничения

Когда мы используем вышеупомянутое уравнение деления в криптографии, мы налагаем два ограничения. Первое требование: чтобы делитель был положительным целым числом ( n > 0 ). Второе требование: чтобы остаток был неотрицательным целым числом ( r > 0 ). Рисунок 2.4 показывает эти требования с двумя указанными ограничениями.

Рис. 2.4. Алгоритм деления целых чисел

Пример 2.3

Предположим, мы используем компьютер или калькулятор, а r и q отрицательны, при отрицательном a. Как можно сделать, чтобы выполнялось ограничение, что число r должно быть положительным? Решение простое: мы уменьшаем значение q на 1 и добавляем значение n к r, чтобы r стало положительным.

Мы уменьшили ( –23 ), получили ( –24 ) и добавили 11 к ( –2 ), чтобы получить + 9. Полученное равенство эквивалентно исходному.

Граф уравнения деления

97

Мы можем изобразить рассмотренные выше уравнения с двумя ограничениями на n и r на рис. 2.5 с помощью двух графов. Первый показывает случай, когда число a положительно; второй — когда отрицательно.

Рис. 2.5. Граф алгоритма деления

Граф начинается с нуля и показывает, как мы можем достигнуть точки, представляющей целое число a на линии. В случае положительного a мы должны перемещаться на величину направо и затем добавить дополнительную величину r в том же самом направлении. В случае отрицательного a мы должны двигаться на величину налево (число q в этом случае отрицательно) и затем дополнять число r в противоположном для указанного выше движения направлении. В обоих случаях значение r положительно.

Теория делимости

Теперь кратко обсудим теорию делимости — тема, с которой мы часто сталкиваемся в криптографии. Если a не равно нулю, а r = 0, в равенстве деления мы имеем

a = q x n

Мы тогда говорим, что a делится на n (или n — делитель a ). Мы можем также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как n|a. Если остаток не является нулевым, то n не делится, и мы можем записать отношения как n†a.

Пример 2.4
a.	Целое число 4 делит		целое число 32,	потому что		. Это
можно	отобразить	как 4|32. Число 8 не		делит	число 42,	потому
что	. В	этом	уравнении число 2 —		остаток. Это	можно

отобразить как8†42.

Пример 2.5

98

а. Отображение делимости 13|78, 7|98, –6|24, 4|44, и 11 | (–33).

б. Отображение неделимости 13†27, 7†50, – 6†23, 4†41, и 11†(–32).

Свойства

Следующие несколько свойств теории делимости. Доказательства заинтересованный читатель может проверить в приложении Q.

Свойство 1: если a|1, то a=±1. Свойство 2: если a|b и b|a, то a=±b

Свойство 3: если a|b и b|c, то a|c

Свойство 4: если a|b и a|c, то a|(m x b + n x c), где m и n —

произвольные целые числа.

Пример 2.6

а. Если 3|15 и 15|45 то, согласно третьему свойству, 3|45.

б. Если 3|15 и 3|9, то, согласно четвертому свойству, , что означает 3|66.

Все делители

Положительное целое число может иметь больше чем один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Мы можем упомянуть два интересных свойства делителей положительных целых чисел.

Свойство 1: целое число 1 имеет только один делитель — само себя. Свойство 2: любое положительное целое число имеет по крайней мере

два делителя — 1 и само себя (но может иметь больше).

Наибольший общий делитель

Одно целое число, часто необходимое в криптографии, — наибольший общий делитель (НОД) двух положительных целых чисел. Два положительных целых числа могут иметь много общих делителей, но только один наибольший общий делитель. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель —

4 (см. рис. 2.6).

Рис. 2.6. Общие делители двух целых чисел

99

Наибольший общий делитель (НОД) двух положительных целых чисел

— наибольшее целое число, которое делит оба целых числа.

Алгоритм Евклида

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

К счастью, больше чем 2000 лет назад математик по имени Эвклид разработал алгоритм, который может найти наибольший общий делитель двух положительных целых чисел. Алгоритм Евклида основан на следующих двух фактах (доказательство см. в приложении Q):

Факт 1: НОД (a, 0) = a

Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b Первый факт говорит, что если второе целое число — 0, наибольший

общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже.

НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)

Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0).Рисунок 2.7 показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).

Рис. 2.7. Алгоритм Евклида.

100

Для определения НОД мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1 на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.

Пример 2.7

Нужно найти наибольший общий делитель 2740 и 1760.

Решение

Применим вышеупомянутую процедуру, используя таблицу. Мы присваиваем начальное значение r1 2740 и r2 значение 1760. В таблице также показаны значения q на каждом шаге. Мы имеем НОД (2740, 1760) = 20.

q	r
1	2
	980
740 760
1	780
760 80
1	200
80	80
3	180
80	00
1	20
00	80
9	0
80	0
0

Расширенный алгоритм Евклида

Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и t, такие, которые

s x a + t x b = НОД (a,b)

Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рис. 2.8.