Файл: прикладная теория информации.pdf

113 фигурацию после аварии. Необходима защита от случайных, непродуманных мо- дификаций. Предусмотреть возможность возврата к прошлой программной ра- ботающей версии.
Резервное копирование необходимо для восстановления программ и дан- ных после аварии. Должны быть созданы полные эталонные копии программ си- стемы. Копии размещаются в месте, защищенном от несанкционированного до- ступа.
Управление носителями посредством физической защиты, обеспечивает целостность информации, хранящейся вне компьютерных систем. Под физиче- ской защитой здесь понимается не только отражение попыток несанкциониро- ванного доступа, но и предохранения от вредных влияний окружающей среды
(влага, жара, холод, магнетизм).
4. Документирование. В виде документов оформляется журнал учета носи- телей информации, план восстановления данных после аварии.
Для построения надежной защиты информации современная информаци- онная система должна включать в себя и такие сервисы безопасности как:
‒ помехоустойчивое кодирование;
‒ криптографическое кодирование (шифрование).
6.5. Общие сведения по классической криптографии
6.5.1. Криптографическое кодирование
Определение 6.9. Криптография ‒ это раздел прикладной математики, изу- чающий модели, методы, алгоритмы, программные и аппаратные средства пре- образования информации.
Криптографическое кодирование (шифрование) относится к традицион- ным сервисам безопасности. Это наиболее мощное средство обеспечения инфор- мационной безопасности. Криптографическое кодирование необходимо для реа- лизации трех сервисов безопасности:
‒ шифрования;
‒ контроля целостности;
‒ аутентификации.
Определение 6.10. Шифрование ‒ это кодирование (преобразование) ис- ходного текста, который носит название открытого текста, в шифрованный текст
(криптограмму) с помощью секретного ключа.
Процесс создания криптограммы записывается как
???? = ????
????
(????),
где ???? ‒ шифротекст;
???? (encryption) ‒ шифрующая функция (кодирование, преобразование);
???? ‒ секретный ключ;

114
???? (message) ‒ открытый текст.
Ключ ???? определяет также процесс, обратный шифрованию, который назы- вают расшифрованием (дешифрованием):
???? = ????
????
(????), где ???? (decryption) – дешифрирующая функция (декодирование, обратное преоб- разование).
При этом должно выполняться тождество
???? = ????
????
(????) = ????
????
(????
????
(????)).
Замечание. Алгоритмы шифрования ???? и дешифрования ???? открыты, и сек- ретность исходного текста ???? в шифротексте ???? зависит от ключа ????.
Существуют два основных алгоритма шифрования.
В первом, процессы шифрования/дешифрования используют один и тот же секретный ключ отправителя и получателя информации. Этот метод использу- ется в так называемых симметричных криптосистемах. В них ключ поставляется абонентам специальным конфиденциальным способом.
Второй метод шифрования основан на двух ключах. Первый, ‒ открытый ключ, доступный всем пользователям информационной системы, применяется при шифровании. Второй ключ, математически связанный с первым, ‒ секрет- ный. Он нужен при расшифровывании текста. Такие криптосистемы называются ассиметричными или криптосистемами с открытым ключом.
Определение 6.11. Криптосистема ‒ это система, реализованная програм- мно, аппаратно или программно-аппаратно и осуществляющая криптографиче- ское преобразование информации.
Аппаратная реализация имеет существенную стоимость, однако ей при- сущи и преимущества:
‒ высокая производительность;
‒ сравнительная простота;
‒ защищенность.
Программная реализация криптосистемы более практична, допускает гиб- кость в использовании.
6.5.2. Требования к криптосистемам защиты информации
Основными требованиями являются:
‒ функциональное преобразование сообщения
????
????
(????) и обратное преобра- зование зашифрованного сообщения ????
????
(????) должны быть сравнительно легко вы- числимы;

115
‒ не зная ключ ????, невозможно за заданное (реальное) время вычислить со- общение ???? по шифротексту ???? = ????
????
(????). Не должно быть простых зависимостей между используемыми ключами;
‒ изменение длины ключа не должно вести к качественному ухудшению алгоритма шифрования;
‒ число операций, необходимых для определения ключа по фрагменту шифрованного текста должно быть не меньше общего числа ключей;
‒ число операций, необходимых для дешифрования информации путем пе- ребора всевозможных ключей должно иметь строгую нижнюю оценку. При этом следует учитывать вычислительные возможности по числу операций в единицу времени современных суперкомпьютеров, возможности использования сетевых вычислений;
‒ знание алгоритма шифрования не должно влиять на надежность защиты.
6.5.3. Криптоанализ
Криптоанализ занимается задачами, обратными задачам криптографии.
Основной задачей специалиста криптоаналитика является поиск ключа. Ему мо- гут представиться следующие возможности для атаки:
‒ получен лишь зашифрованный текст ???? = ????
????
(????);
‒ известны незашифрованный и зашифрованный тексты;
‒ имеется возможность выбрать пространство сообщений {????} и простран- ство шифротекстов {????}, т. е. иметь пару {????, ????}.
Криптоанализ и криптография развиваются параллельно. Криптографы пытаются создать такую криптосистему, которая была бы стойкой ко всем из- вестным в данный момент методам криптоанализа.
Эффективность шифрования зависит от сохранения тайны ключа и крип- тостойкости шифра.
Определение 6.12. Криптостойкостью называется характеристика шифра, определяющая его стойкость крипоанализу (к дешифрованию) без знания ключа.
Имеется несколько основных показателей криптостойкости, среди кото- рых:
‒ количество всех возможных ключей;
‒ среднее время, необходимое для криптоанализа.
В практических применениях показателями стойкости могут служить ал- горитмы обеспечивающие вычислительную стойкость, т. е. такие алгоритмы, ко- торые теоретически раскрываемы, но требуют для осуществления криптоанализа значительных вычислительных затрат, например, работы 10 млн компьютеров в течение 10 000 лет.
История развития криптологии имеет большую продолжительность. При археологических раскопках в Месопотамии был найден, относящийся к XX веку до н. э. один из самых древних шифротекстов. Он был написан клинописью на

116 глиняной дощечке и содержал коммерческую тайну: рецепт глазури для покры- тия гончарных изделий. В XVII веке кардинал Ришилье создал первую в мире шифрослужбу. Задачами криптологии занимались такие известные ученые как
Ньютон, Лейбниц, Эйлер, Гаусс и др. В развитии криптологии принято выделять три этапа.
Первый этап ‒ с древних времен до 1949 г., характеризовался частными, узкоспециальными и вычислительно простыми алгоритмами криптографии и криптоанализа. Этот этап называют этапом докомпьютерной криптологии.
Второй этап ‒ с 1949 г., когда К. Шеннон опубликовал работу «Теория связи в секретных системах», до 1976 г. В этот период проводились большие ис- следования с использованием компьютеров. Основными потребителями резуль- татов криптологии являлись военные и дипломатические организации, поэтому криптология была закрытой наукой.
Третий этап ‒ с 1976 г., когда была опубликована работа «Новые направ- ления в криптографии» американских математиков У. Диффи (W. Diffie) и М.
Хеллмена (М. Hellman). В этой работе показано, что секретная передача инфор- мации возможна без предварительной передачи ключа. Особенностью этого этапа стало применение криптографии в банковском деле, компьютерных сетях и др. приложениях. В развитие криптологии вкладываются значительные госу- дарственные средства. Например, в США ежегодные расходы на криптологию составляют порядка 18–20 млр дол. США.
Криптология строится на базе таких дисциплин как теория вероятностей, математическая статистика, алгебра, теория чисел, теория алгоритмов и слож- ность вычислений. Процесс шифрования осуществляется на специализирован- ных компьютерах.
6.6. Алгоритмы блочного шифрования
Блочное шифрование используется в симметричных криптосистемах.
Блочный шифр обрабатывает блок открытого текста фиксированной длины.
Процесс шифрования текста ???? записывается как
???? = ????
????
(????), где ???? ‒ это блок шифротекста,
???? – секретный ключ, шифрующая функция.
В этом алгоритме зашифрованный первый блок сообщения далее исполь- зуется для шифрования следующего. Шифрующие процедуры одного типа чере- дуются с процедурами другого типа. В качестве простых шифров могут быть ис- пользованы подстановки ????, перестановки ???? и линейные преобразования ????. Сек- ретный ключ может использоваться при осуществлении всех процедур. Блочные шифры используют многократное повторение операций преобразования, назы- ваемое раундом шифрования.

117
На этом принципе работает известный стандарт шифрования данных DES и его модификация AES. DES использует ключи размером 64 бит с эффективной длиной 56 бит. Всего создается ????
????????????
= 2 56
≈ 7,2 ∙ 10 16
ключей. Система AES имеет три варианта размеров ключей 128, 192 и 256 битов. Длина ключа 128 бита позволяет формировать ????
????????????
= 2 128
= 3,4 ∙ 10 38
ключей. Система AES имеет в
(
????
????????????
????
????????????
) ≈ 10 21
раз больше ключей, чем DES. Если предположить, что можно про- верить все ключи DES за 1 с, то при скорости ???? = 2 56
бит/c для тестирования всех ключей блочного шифрования AES потребовалось бы 149 трлн лет (возраст вселенной 13,7 млрд лет).
Недостатком блочного шифрования является обмен ключами между от- правителем и получателем. Передача ключей в практическом аспекте уязвима для перехвата.
6.7. Ассиметричные алгоритмы шифрования
Теоретико-числовые алгоритмы являются основой современной крипто- графии и криптографических систем с открытым ключом. В этом случае про- граммное обеспечение, программный интерфейс криптографических систем с шифрующими алгоритмами строится на базе конечных алгебраических струк- тур: групп, колец, полей.
Первой известной криптографической системой с открытым ключом явля- ется система, созданная в Массачусетском технологическом институте в 1978 году. Система названа по фамилиям авторов (R. L. Rivest, A. Shamir,
L. Alldeman) как RSA-криптосистема. Особенностью математического алго- ритма системы является то, что криптосистему создает не отправитель сообще- ния, а получатель. Алгоритм шифрования основывается на задаче RSA.
6.7.1. Задача RSA
Предположим, что произвольный получатель А информации разрешает всем желающим передавать ему секретные сообщения. т е. он выступает в каче- стве получателя сообщения. Получатель А случайным образом выбирает два больших простых числа ???? и ????, причем ???? ≠ ????. Числа ???? и ???? выбираются порядка не менее чем 2 256
. Эти числа являются секретными.
Получатель А вычисляет число ???? = ???? ∙ ????. Число ???? называется модулем ал- горитма и является несекретным. Получатель А открыто публикует число ????. Та- ким образом, всем пользователем системы известно число ????, но не известны сомножители ‒ ???? и ????.
Решение задачи RSA (дешифрации) сведется к поиску простых делителей
???? и ???? числа ????. Криптостойкость системы обосновывается сложностью решения задачи факторизации очень больших чисел в произведение простых чисел.
Алгоритм RSA использует понятие функции Эйлера числа ???? и теорему Эй- лера.

118
Определение 6.13. Количество положительных целых чисел меньших ???? и взаимно простых с ???? называется функцией Эйлера φ(????), или тотиент-функцией
Эйлера. Функция Эйлера φ(????) – это количество вычетов по модулю ????.
Теорема 6.1. Если ???? – простое число, то φ(????) = ???? − 1.
Так как пара простых чисел ???? и ???? известна получателю А, используя свой- ство мультипликативности функции Эйлера, получатель А секретной информа- ции легко может вычислить значение функции φ(????):
φ(????) = φ(???? ∙ ????) = φ(????)φ(????) = (???? − 1)(???? − 1).
Получатель А публикует также число ????, т. е. ???? является несекретным.
Число ???? выступает в качестве открытого ключа криптосистемы RSA и исполь- зуется для шифрования данных. Число ???? называется шифрующей экспонентой.
Выбор получателем A числа ???? должен удовлетворять двум условиям:
1 < ???? ≤ φ(????) = (???? − 1)(???? − 1); (6.1)
НОД (
????, φ(????)) = НОД (Е, (???? − 1), (???? − 1)) = 1. (6.2)
Следовательно, число ???? и число φ(????) должны быть взаимно простыми.
Число ???? выбирается случайным образом, но часто ???? равно числу Ферма:
???? = 2 2
????
+ 1, ???? ∈ ????
????
Например, открытый ключ ???? может быть равен таким числам Ферма:
5, 17, 257, 65537,…
Определение 6.14. Пара (????, ????) называется открытым ключом RSA (RSA public key).
Теорема 6.2 (Теорема Эйлера). Если α и ???? ‒ взаимно простые числа, т. е.
НОД (α, ????) = 1, то
α
φ(????)
≡ 1mod ????. (6.3)
Получатель А пересылает отправителю В пару чисел (????, ????) по открытому
(незащищенному) каналу. Таким образом, всем желающим передавать получа- телю А секретную информацию доступна пара (????, ????).
Исходный текст ???? переводится в числовую форму (шифруется) по фор- муле
????
????
≡ ????mod ????. (6.4)

119
Шифруемый текст представляется криптограммой ???? = ????
????
∈ {1, 2, … , ???? −
−1} в виде одного большого числа. Затем это число разбивается на блоки так, что каждый из них представляется в виде числа ????
????
∈ {0, 1, 2, … , ???? − 1}. Формула
(6.4) шифрования (кодирования) текста в числовую форму является несекретной.
Так как по задаче RSA число ???? и число φ(????) должны быть взаимно про- стыми, по теореме Эйлера справедливо выражение
????
φ(φ(????))
≡ 1mod φ(????) = ????
φ((????−1)(????−1))
≡ 1mod (???? − 1)(???? − 1). (6.5)
Обозначим функцию Эйлера φ(φ(????)) = φ((???? − 1)(???? − 1)) через ????, тогда выражение (6.5) запишем в виде
????
????
≡ 1mod (???? − 1)(???? − 1). (6.6)
Выражение (6.6) можно записать в виде
???? ∙ ????
????−1
≡ 1mod (???? − 1)(???? − 1). (6.7)
Обозначим ????
????−1
= ????. C учетом этого получаем
???? ∙ ???? ≡ 1mod (???? − 1)(???? − 1), (6.8) где ???? – это секретный ключ.
Секретный ключ ????, применяется для дешифрования криптограммы по фор- муле
???? ≡ ????
????
mod ????. (6.9)
Таким образом, секретными данными RSA-системы является тройка чисел
(????, ????, ????).
Нахождение ???? получателем А для дешифрации криптограммы сводится к вычислению числа обратному числу ???? по mod (???? − 1)(???? − 1). Необходимо найти такое число ???? ∈ { 1, 2, … , ???? − 1}, для которого выполняется сравнение
(6.8). Так как получателю А известны числа
????, ????, ????, сравнение разрешимо един- ственным образом, поскольку НОД (Е, (???? − 1)(???? − 1)) = 1.
Замечание. Число ???? можно легко вычислить, используя алгоритм Евклида или другие быстрые алгоритмы нахождения обратных чисел.
6.7.2. Алгоритм вычисления обратных чисел по теореме Эйлера
Используя формулу (6.3), можно записать
α
−1
∙ α
φ(????)
≡ α
−1
∙ 1mod ????.