ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2019
Просмотров: 12421
Скачиваний: 24
91
осуществления случайного выбора на каком-либо шаге алгоритма, либо как
результат выполнения (вычислителем) измерений параметров окружения
(внешних
объектов).
Алгоритм
выполняется
неким
субъектом
(вычислителем).
Под
протоколом
понимается совокупность действий (инструкций,
команд,
вычислений,
алгоритмов),
выполняемых
в
заданной
последовательности двумя или более субъектами с целью достижения
определенного результата. Корректность выполнения протокола зависит от
действий каждого субъекта (пользователя, абонента) криптосистемы. В
качестве субъектов могут выступать рабочая станция, программа для ЭВМ,
радиопередатчик, космический спутник, оператор, сервер, орган власти и т.п.
Обычно субъекты, участвующие в протоколах, действуют по определенному
предписанному алгоритму, т.е. алгоритм выступает как внутренний элемент
протокола.
Криптографические протоколы
– это такие протоколы в которых
используется криптографические преобразования исходных данных. Хотя
криптографические протоколы часто используют те или иные алгоритмы
шифрования данных, их целью не обязательно является секретность.
Например
стороны
криптографического
протокола
могут
желать
одновременно подписать какой либо контракт, провести электронную
жеребъевку, идентифицировать участников телеконференции и т.п.
Итак, криптографические протоколы дают возможность преобразовать
информацию таким образом, что ее прочтение (восстановление) возможно
только при знании ключа.
В качестве информации, подлежащей шифрованию и дешифрованию,
будут рассматриваться
тексты
, построенные на некотором
алфавите
. Под
этими терминами понимается следующее.
Алфавит
- конечное множество используемых для кодирования
информации знаков.
Текст
- упорядоченный набор из элементов алфавита.
В качестве примеров алфавитов, используемых в современных ИС
можно привести следующие:
*
алфавит Z
33
- 32 буквы русского алфавита и пробел;
*
алфавит Z
256
- символы, входящие в стандартные коды ASCII и КОИ-8;
*
бинарный алфавит - Z
2
= {0,1};
*
восьмеричный алфавит или шестнадцатеричный алфавит;
Шифрование
- преобразовательный процесс:
исходный текст
, который
носит также название
открытого текста
, заменяется
шифрованным тек-
стом
.
92
Дешифрование
- обратный шифрованию процесс. На основе ключа
шифрованный текст преобразуется в исходный.
Ключ -
информация, необходимая для беспрепятственного шифрования
и дешифрования текстов.
Криптографическая система
представляет собой семейство
T
преоб-
разований открытого текста. Члены этого семейства индексируются, или обо-
значаются символом
k
; параметр
k
является
ключом
. Пространство ключей
K
- это набор возможных значений ключа. Обычно ключ представляет собой
последовательный ряд букв алфавита.
Криптосистемы разделяются на
симметричные
и
с открытым ключом
.
В
симметричных криптосистемах
и для шифрования, и для
дешифрования используется
один и тот же ключ
.
В
системах с открытым ключом
используются два ключа -
открытый
и
закрытый
, которые математически связаны друг с другом. Информация
шифруется с помощью открытого ключа, который доступен всем
желающим, а расшифровывается с помощью закрытого ключа, известного
только получателю сообщения.
Термины
распределение ключей
и
управление ключами
относятся к про-
цессам системы обработки информации, содержанием которых является со-
ставление и распределение ключей между пользователями.
Электронной (цифровой) подписью
называется присоединяемое к
тексту его криптографическое преобразование, которое позволяет при
получении текста другим пользователем проверить авторство и подлинность
сообщения.
исходный
текст
шифрованный
текст
Криптографическая
система
КЛЮЧ
шифрованный
текст
исходный
текст
Криптографическая
система
КЛЮЧ
93
Криптостойкостью
называется характеристика шифра, определяющая
его стойкость к дешифрованию без знания ключа (т.е. криптоанализу).
Имеется несколько показателей криптостойкости, среди которых:
количество всех возможных ключей;
среднее время, необходимое для криптоанализа.
Преобразование T
k
определяется соответствующим алгоритмом и зна-
чением параметра
k
. Эффективность шифрования с целью защиты информа-
ции зависит от сохранения тайны ключа и криптостойкости шифра.
Требования к криптосистемам
Процесс криптографического закрытия данных может осуществляться
как программно, так и аппаратно. Аппаратная реализация отличается сущест-
венно большей стоимостью, однако ей присущи и преимущества: высокая
производительность, простота, защищенность и т.д. Программная реализация
более практична, допускает известную гибкость в использовании.
Для современных криптографических систем защиты информации сфор-
мулированы следующие общепринятые требования:
зашифрованное сообщение должно поддаваться чтению только при
наличии ключа;
число операций, необходимых для определения использованного клю-
ча шифрования по фрагменту шифрованного сообщения и соответст-
вующего ему открытого текста, должно быть не меньше общего числа
возможных ключей;
число операций, необходимых для расшифровывания информации пу-
тем перебора всевозможных ключей должно иметь строгую нижнюю
оценку и выходить за пределы возможностей современных компьютеров
(с учетом возможности использования сетевых вычислений);
знание алгоритма шифрования не должно влиять на надежность защи-
ты;
незначительное изменение ключа должно приводить к существенному
изменению вида зашифрованного сообщения даже при использовании
одного и того же ключа;
структурные элементы алгоритма шифрования должны быть неизмен-
ными;
дополнительные биты, вводимые в сообщение в процессе шифрова-
ния, должен быть полностью и надежно скрыты в шифрованном тексте;
длина шифрованного текста должна быть равной длине исходного
текста;
не должно быть простых и легко устанавливаемых зависимостью ме-
жду ключами, последовательно используемыми в процессе шифрования;
любой ключ из множества возможных должен обеспечивать надеж-
ную защиту информации;
алгоритм должен допускать как программную, так и аппаратную реа-
94
лизацию, при этом изменение длины ключа не должно вести к качест-
венному ухудшению алгоритма шифрования.
4. Математические основы криптографии.
Высшая арифметика, или теория чисел, изучает свойства натуральных
чисел 1, 2, 3, ... Эти числа интересуют человека с давних времен. Античные
летописи говорят о том, что уже тогда арифметику знали глубже и шире, чем
это было необходимо для нужд повседневной жизни. Но систематической,
самостоятельной наукой высшая арифметика становится лишь в новое время,
начиная с открытий Ферма (Fermat, 1601–1665).
Многие простые и общие теоремы высшей арифметики естественно
возникают из вычислений, однако при доказательстве этих теорем часто
встречаются очень большие трудности. «Эта особенность, — по словам
Гаусса, — вместе с неистощимым богатством высшей арифметики, которым
она столь сильно превосходит другие области математики, придает высшей
арифметике неотразимое очарование, сделавшее ее любимой наукой
величайших математиков».
4.1. Арифметика целых чисел.
В арифметике целых чисел
мы используем множество целых чисел и
несколько операций. Вы знакомы с этим множеством и соответствующими
операциями, но они рассмотрены здесь, чтобы объяснить потом основы
действий со сравнениями по модулю
m
.
Множество целых чисел
Множество целых чисел, обозначенных
Z
, содержит все числа (без
дробей) от минус бесконечности до плюс бесконечности (
Рис. 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.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
—
остаток
. Обратите внимание, что это — не операция,