Некоммерческое акционерное  общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра Телекоммуникационных Систем

  

 

 

ЗАЩИТА ИНФОРМАЦИИ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ

 Сборник задач для бакалавров специальностей

5В071900 – Радиотехника, электроника и телекоммуникации,

5В074600 – Космическая техника и технологии

  

 

 

 

Алматы 2011

    СОСТАВИТЕЛИ: Е.А. Шкрыгунова, О.А. Абрамкина. Защита информации в телекоммуникационных системах. Сборник задач для бакалавров специальностей 5В071900 – Радиотехника, электроника и телекоммуникации, 5В074600 – Космическая техника и технологии – Алматы: АУЭС, 2011. – 28 с.

 

Приведены задачи и упражнения, необходимые при освоении дисциплины «Защита информации в ТКС». Изложены основные подходы и методы современной криптографии для решения задач, возникающих при обработке, хранении и передаче информации. Рассмотрены симметричные и несимметричные шифры, методы цифровой подписи, хеш-функция.

Табл. - 4, библиогр. – 10 назв.

 

Рецензент: доц. каф. ТКС Федулина И.Н.

 

Печатается по плану издания НАО «Алматинского университета энергетики и связи» на 2011 г.

 

                              Ó «НАО» Алматинский университет энергетики и связи, 2011 г.

 

Введение 

«Защита информации в ТКС» - базовый теоретический курс для студентов ВУЗов связи.

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

 Цель курса – формирование у студентов знаний теоретических основ и практического использования систем защиты информации в телекоммуникационных системах. Дисциплина направлена на формирование у студентов систематизированного представления о принципах, методах и средствах реализации защиты данных.

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

 

Глава 1. криптографическая защита информации и этапы ее развития

 

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

История применения криптографических методов насчитывает десятки веков. Упоминания о криптографии (от греч. kryptos - скрытый, тайный) встречаются еще у Геродота и Плутарха, а также в русских рукописях XII—XIII веков. Но криптография появилась гораздо раньше — она ровесница истории человеческого языка.

Одной из важнейших способностей человека является умение общаться с себе подобными. Изначально для передачи сведений о том, что происходит в окружающем мире, о фактах своей субъективной реальности, человек использовал жесты и мимику. Язык тайной передачи сообщений жестами активно используется и в наши дни представителями некоторых криминальных «специальностей», например, шулеров. Во время «работы» пара шулеров ведет весьма оживленную беседу, незаметную для непосвященных и понятную только наметанному глазу профессионала.

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

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

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

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

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

С широким распространением письменности криптография стала формироваться как самостоятельная наука. Предполагается, что она была известна в Древнем Египте и Вавилоне. До нашего времени дошли сведения о том, что искусство секретного письма использовалось в Древней Греции. Первые действительно достоверные данные с описанием метода шифрования относятся к периоду смены старой и новой эры и описывают шифр Цезаря — способ, которым Юлий Цезарь прятал свои записи от излишне любопытных глаз. Уже тогда использование шифра решало проблему секретности передаваемого сообщения, а проблема его подлинности решалась практически сама собой: человек, не знавший шифр, не мог внести осмысленные изменения в зашифрованные текстовые сообщения, а изменения, внесенные наобум, приводили к тому, что после расшифровки получался бессмысленный набор букв; поскольку отправляемые сообщения записывали от руки, то запомнить почерк каждого из нескольких десятков наиболее важных своих корреспондентов не составляло особого труда.

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

Для этого этапа развития криптографии характерно следующее:

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

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

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

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

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

С появлением компьютеров и использованием для связи компьютерных сетей шифрование данных стало более изощренным и актуальным. Благодаря созданию новых мощных компьютеров, технологий сетевых и нейронных вычислений стало возможно «взломать» криптографические системы, до недавнего времени считавшиеся практически нераскрываемыми. Вместе с тем расширилось использование компьютерных сетей, в частности, глобальной сети Internet, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, доступ к которой для посторонних лиц недопустим. Все это привело к тому, что очень быстро практическая криптография в деловой сфере сделала огромный скачок в развитии, причем сразу по нескольким направлениям:

-     разработаны стойкие блочные шифры с секретным ключом, предназначенные для решения классической задачи — обеспечения секретности и целостности передаваемых или хранимых данных;

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

 

Глава 2. Симметричные методы криптографического преобразования данных

 

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

 

2.1      Шифрование заменой

 

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

 

Таблица 2.1 – Таблица простой замены

 

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

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

 

2.2       Метод Цезаря

 

Метод Цезаря является самым простым вариантом шифрования. Он назван по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита, сдвигая его на 3 символа вперед.

Подстановка определяется по таблице замещения (см. таблицу 2.2), содержащей алфавит из 32 букв (исключая букву «Ё»), «исходный текст – шифрованный текст». Сейчас используют смещение в алфавите на четыре, пять и более букв.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки  преобразуется в «еюыолхиврсеюивцнгкгрлб».

 

Таблица 2.2 – Таблица замещения с ключом 3

 

2.3       Системы шифрования Вижинера

 

Метод Вижинера является следствием подстановки Цезаря. В системе Вижинера задается некая конечная последовательность ключа  k = (k0 ,k1 ,...,kn), которая называется ключом пользователя, она продолжается до бесконечной последовательности, повторяя цепочку. Таким образом, получается  рабочий ключ.

Например, при ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...

Таким образом, при длине пользовательского ключа R:

1) исходный текст x делится на R фрагментов: xi = (xi , xi+r , ..., xi+r(n-1)), 0 £ i < r;

2) i-й фрагмент исходного текста xi шифруется при помощи подстановки Цезаря в зависимости от пользовательского ключа:

               (xi , xi+r , ..., xi+r(n-1)) ∙ (yi , yi+r , ..., yi+r(n-1)),

Пример: преобразование текста с помощью подстановки Вижинера (r=4)

Исходный текст (ИТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ: КЛЮЧ

Разобьем исходный текст на блоки по 4 символа:

НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ

и наложим на них ключ (используя таблицу Вижинера):

H+К=Ч, Е+Л=Р и т.д.

Получаем зашифрованный (ЗТ1) текст:

ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН

Криптостойкость метода резко убывает с уменьшением длины ключа.

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

 

2.4       Шифрование перестановкой

 

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

Выбирается размер блока шифрования в n столбцов и m строк и ключевая последовательность, которая формируется из натурального ряда чисел 1,2,...,n случайной перестановкой.

Шифрование проводится в следующем порядке:

1)       шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m;

2)       зашифрованный текст выписывается колонками в порядке возрастания номеров колонок, задаваемых ключевой последовательностью;

3)       заполняется новый блок и т.д.

 

Например, зашифруем текст: ГРУЗИТЕ_АПЕЛЬСИНЫ_БОЧКАХ блоком размером 8*3 и ключом 5-8-1-3-7-4-6-2. Таблица простой перестановки будет иметь вид:

 

Таблица 2.3 – Простая перестановка

Ключ
5	8	1	3	7	4	6	2
Г	Р	У	З	И	Т	Е	_
А	П	Е	Л	Ь	С	И	Н
Ы	_	Б	О	Ч	К	А	Х

 

Зашифрованное сообщение: УЕБ_НХЗЛОЕСЛГАЫЕИАИЬЧРП_.

Расшифровывание выполняется в следующем порядке:

1)       из зашифрованного текста выделяется блок символов размером n*m;

2)       этот блок разбивается на n групп по m символов;

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

4)       выделяется новый блок символов и т.д.

 

2.5       Шифрование с помощью аналитического метода

 

Наибольшее распространение получили методы шифрования, основанные на использовании матричной алгебры. Шифрование k-го блока исходной информации, представленного в виде вектора B_k = ||b_j||, осуществляется путем перемножения матрицы-ключа А = ||a_ij|| и вектора B_k. В результате перемножения получается блок шифртекста в виде вектора C_k = ||c_i|| , где элементы вектора C_k определяются по формуле (2.1):

 

          .                                         (2.1)

 

Расшифровывание информации осуществляется путем последовательного

перемножения векторов C_k и матрицы A^-1, обратной матрице A.

Пример: произведем шифрование информации с использованием алгебры матриц. Пусть необходимо зашифровать и расшифровать слово
Т₀ = «ЗАБАВА» с помощью матрицы – ключа А:

.

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

Шаг 1. Определяется числовой эквивалент исходного слова как последовательность соответствующих порядковых номеров букв слов Т_э: 

T_э = «8, 1, 2, 1, 3, 1»

Шаг 2. Получение матриц С₁ и С₂ путем умножения матрицы А на векторы: В₁ = {8, 1, 2} и В₂ = {1, 3, 1}.

 

      ,         .

 

Шаг 3. Зашифрованное слово записывается в виде последовательности чисел Т₁ = «28, 35, 67, 21, 26, 38».

 

Расшифровывание слова осуществляется следующим образом:

Шаг 1. Вычисляется определитель |А| = -115.

Шаг 2. Определяется присоединенная матрица А*, каждый элемент которой является алгебраическим дополнением элемента матрицы А:

.

           Шаг 3. Получается транспонированная матрица А^T:

.

 

Шаг 4. Вычисляется обратная матрица А^-1 по формуле (2.2):

 
А^-1 = А^Т/|А| .                                              (2.2)

 

В результате вычислений обратная матрица имеет вид:

.

          Шаг 5. Определяются векторы B₁ и B₂:  B₁ = A^-1*C₁; B₂ = A^-1*C₂:

 ,

 

.

 

Шаг 6. Числовой эквивалент расшифрованного слова  Т_э = «8, 1, 2, 1, 3, 1» заменяется символами, в результате чего получается исходное слово                        Т₀ = «ЗАБАВА».

 

Задачи и упражнения

 

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

2        Зашифровать слово «информация» используя таблицу 2.1.

3        Зашифровать слово «защита» используя полиалфавитную перестановку.

4        Составить таблицу полиалфавитной замены (русский и английский алфавит) и зашифровать слово «телекоммуникация».

5        Составить таблицу полиалфавитной замены (русский и английский алфавит) и зашифровать слово «стандартизация».

6        Определить ключи шифра Цезаря, если известны следующие пары «открытый текст-шифротекст»:

а)     АПЕЛЬСИН – САЦЬНВЩЮ

б)    АБРИКОС – ВГТКМРУ

в)     ИНФОРМАЦИЯ – НТЩУХСЕЫНД

г)     ЗАЩИТА - ПИБРЪИ

7        Зашифровать с использованием шифра Цезаря:

а)     k=10, слово «информация»;

б)    k=8, слово «защита»;

в)     k=15, слово «телекоммуникация»;

г)     k=23, слово «телефон».

8        Используя системы Вижинера зашифровать:

а)     слово «информация» ключом «мозг»;

б)    слово «сертификация» ключом «ключ»;

в)     слово «параметризация» ключом «защита»;

г)     слово «сертификация» ключом «информация».

9        Зашифровать текст «СИСТЕМА_БЛОЧНОГО_ШИФРОВАНИЯ» блоком размером 7*3 и ключом 5-7-3-1-6-4-2.

10   Зашифровать текст «ИСТОЧНИК_СООБЩЕНИЯ» блоком размером 9*2 и ключом 9-3-1-4-6-8-2-5-7.

11   Зашифровать текст:

«КОЛИЧЕСТВЕННАЯ_ВЕРОЯТНОСТЬ_ИСПОЛЬЗОВАНИЯ_ВСЕХ_КЛЮЧЕЙ» блоком размером 13*4 и ключом 8-3-6-11-5-2-9-13-1-4-7-10-12, проверить правильность шифрования путем дешифрования.

12   Зашифровать слово «информация», используя аналитический способ шифрования и матрицу-ключ А.                              .

13   Зашифровать и расшифровать слово «телефон», используя аналитический способ шифрования и матрицу-ключ А.         .

14   С помощью аналитического метода шифрования зашифровать и расшифровать слово «защита». Матрица-ключ А.     .

15   Используя аналитический метод, расшифровать слово «25,6,3,1,8,5», используя матрицу-ключ А. .

Глава 3. Системы шифрования с открытым ключом

 

3.1      Система с открытым ключом Диффи-Хелмана

 

Первая система с открытым ключом — система Диффи-Хеллмана. Это система, которая позволяла защи­щать информацию без использования секретных ключей, передавае­мых по защищенным каналам. Для того чтобы продемонстрировать одну из схем применения таких систем, рассмотрим сеть связи с N пользователями, где N – большое число.

Пусть строится система связи для абонентов А,В,С,... .У каж­дого абонента есть своя секретная и открытая информация. Для  организации этой системы выбирается большое простое число р и некоторое число g, 1 < g < р-1, такое, что все числа из множе­ства {1, 2, … ,р-1} могут быть представлены как различные сте­пени g mod p (известны различные подходы для нахождения таких чисел g, один из них будет представлен ниже). Числа р и g известны всем абонентам.

Абоненты выбирают большие числа X_a,X_b,X_c, которые хра­нят в секрете (обычно такой выбор рекомендуется проводить случай­но, используя датчики случайных чисел). Каждый абонент вычис­ляет соответствующее число Y, которое открыто передается другим абонентам, по формуле (3.1):

 

Y_i = g^X_i mod р.                                                    (3.1)

 

В результате получаем таблицу 3.1.

 

Таблица 3.1 – Ключи  пользователей в системе Диффи-Хеллмана

 

Допустим, абонент А решил организовать сеанс связи с В, при этом обоим абонентам доступна открытая информация из таблицы 3.1. Абонент А сообщает В по открытому каналу, что он хочет передать ему сообщение. Затем абонент А вычисляет величину Z_AB по формуле (3.2):

 

Z_AB=(Y_B)^XAmodp.                                         (3.2)

 

В свою очередь, абонент В вычисляет число Z_BA по формуле (3.3):

 

Z_BA=(Y_A)^XBmodp.                                                 (3.3)

 

Утверждение   Zab = Zba   действительно,

Zab = (Yb)^Xa modp = (g^Xb)^Хa modp=g^ХaХbmodp=(Ya)^Xb mod p = Z_ba.

 

Пример: пусть р = 23 = 2∙11 + 1 (q = 11). Выберем пара­метр g. Попробуем взять g=3. Проверим: 311 mod 23 = 1, и значит, такое g не подходит. Возьмем g = 5. Проверим: 511 mod 23 = 22. Итак, мы выбрали параметры р = 23, g = 5. Теперь каждый або­нент выбирает секретное число и вычисляет соответствующее ему открытое число. Пусть выбраны Хa = 7, Хb = 13. Вычисляем Ya = 57 mod 23 = 17, Yb = 513 mod 23 = 21. Пусть А и В реши­ли сформировать общий секретный ключ. Для этого А вычисляет Zab = 217 mod 23 = 10, а В вычисляет Zba = 1713 mod 23 = 10. Теперь они имеют общий ключ 10, который не передавался по кана­лу связи.

 

3.2      Шифрование по алгоритму Шамира

 

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

Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту Б так, чтобы никто не узнал его содержание. А выбирает случай­ное большое простое число р и открыто передает его В. Затем А выбирает два числа  с_А и d_A такие, что:

 

                                                с_Аd_A mod (р - 1) = 1.                                               (3.4)

 

Эти числа А держит в секрете и передавать не будет. В тоже вы­бирает два числа св  и  dв такие, что:

                                                св<dв mod (p - 1) = 1,                                                  (3.5)

 

и держит их в секрете.

После этого А передает свое сообщение m, используя трехсту­пенчатый протокол.

Шаг 1.  А вычисляет число Х₁ по формуле (3.6):

 

Х₁ =m^СА modp,                                                                                                (3.6)

 

где m — исходное сообщение, и пересылает Х₁ к В.

Шаг 2.   В, получив Х₁, вычисляет число Х₂ по формуле (3.7):

 

X₂ = Х₂^CB mod p                                                                                               (3.7)               

и передает Х₂ к А.

Шаг 3.  А вычисляет число Х₃ по формуле (3.8):

 

X₃=Х₂^dAmodp                                                                                                   (3.8)

 

и передает его В.

Шаг 4. В, получив Х₃, вычисляет число Х₄ по формуле (3.9):

 

X₄=X₃^dBmodp.                                                                                                  (3.9)

 

Пример: пусть А хочет передать В сообщение m = 10. А выбирает р = 23, с_А = 7 (gcd(7,22) = 1) и вычисляет d_A = 19. Аналогично. В выбирает параметры c_B = 5 (взаимно простое с 22) и d_B = 9. Переходим к протоколу Шамира.

Шаг 1. X₁ = 107 mod 23 = 14.

Шаг 2. Х₂ = 145 mod 23 = 15.

Шаг З. X₃= 1519 mod 23 = 19.

Шаг 4. Х₄ = 199 mod 23 = 10.

Таким образом, В получил передаваемое сообщение m = 10.      

 

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

 

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

 

          Теорема. Пусть a и b – два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что:

 

                                                 ax + by = gcd(a, b)         .                                             (3.10)

 

Обобщенный алгоритм Евклида служит для отыскания gcd(a,b) и x,y, удовлетворяющих (2.10). Введем три строки U=(u1, u2, u3), V=(v1, v2, v3) и Т=(t1, t2, t3). Тогда алгоритм записывается следующим образом.

 

Вход: положительные целые числа a, b, .

Выход: gcd(a,b), x, y, удовлетворяющие (1).

1. .

2.WHILE u₁0 DO

3. u₁ div v₁;

4. T( u₁ mod v₂, u₂-qu₂, u₃-qv₃);

5. UV, VT.

6. RETURN U= (gcd(a,b), x, y).

 

Результат содержится в строке U.

 

          Операция div в алгоритме – это целочисленное деление:

 

     a div b=[a/b].                                                 (3.11)

 

          Пример: пусть a=28, b=19. Найдем числа x и y, удовлетворяющие (3.10).

 

                   1  U                    28     1         0

                   2  V   U              19     0         1

                   3  T   V   U          9      1       -1  q=1

                   4        T   V   U    1     -2        3  q=2

                   5              T    V    0    19     -28  q=9.

 

Поясним представленную схему. Вначале в строку U записываются числа (28, 1, 0), а в строку V – числа (19, 0, 1) (это первые строки на схеме). Вычисляется строка Т (третья строка в схеме). После этого в качестве строки U берется вторая строка в схеме, а в качестве V – третья, и опять вычисляется строка Т (четвертая строка в схеме). Этот процесс продолжается до тех пор, пока первый элемент строки V не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ. В нашем случае gcd(28,19) = 1, x= -2, y=3. Выполним проверку: .

 

          Рассмотрим  одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел с, m требуется находить такое число d<m, что:

                                                          cd mod m = 1.                                           (3.12)  

Отметим, что такое d существует тогда и только тогда, когда числа c и m взаимно простые.

 

          Определение. Число d, удовлетворяющие (3.12), называется инверсией  c по модулю m и часто обозначается c^-1 mod m = 1.

                    Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (3.12) в виде (3.13):

 

                                                          cc^-1 mod m = 1.                                         (3.13)

 

Умножение на c^-1 соответствует делению на с при вычислениях по модулю m. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю m:

 

( mod m)          .                                   (3.14)

 

          Пример: 3∙4mod 11 = 1, поэтому число 4 – это инверсия числа 3 по модулю 11. Можно записать 3^-1 mod 11 = 4. Число 5^-2  mod  11 может быть найдено двумя способами:

          5^-2 mod 11 = (5² mod 11)^-1 mod 11 = 3^-1 mod 11 = 4,

         

          5^-2 mod 11= (5^-1 mod 11)²  mod 11 = 9² mod 11 = 4.

 

При вычислениях по второму способу мы использовали равенство                   5^-1 mod 11 = 9. Действительно, 5∙9 mod 11 = 45 mod 11 = 4.

          Покажем, как можно вычислить инверсию с помощью обобщенного алгоритма Евклида. Равенство (2.12) означает, что для некоторого целого k:

 

                                                   cd – km = 1.                                                    (3.15)

 

Учитывая, что c и m взаимны просты, перепишем (3.15) в виде (3.16):

 

   m(-k)+cd=gcd(m,c),                                         (3.16)

 

что полностью соответствует (3.12), здесь только по-другому обозначены переменные.

 

          Пример: вычислим 7^-1 mod 11:

 

                             11      0

                               7      1

                               4     -1    q=1      

                               3      2    q=1

                               1     -3    q=1

                               0     11    q=3.

 

Получаем d= -3 и d mod 11 = 11-3 = 8, т.е. 7^-1 mod 11 = 8.

Проверим результат:mod 11 = 56 mod 11 = 1.       

 

 

3.4       Шифрование по алгоритму Эль-Гамаля

 

Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищен­ных каналов связи. Шифр, предло­женный Эль-Гамалем (Tahcr ElGamal), решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку со­общения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего со­общения секретный ключ вычисляется заново.

Для всей группы абонентов выбираются некоторое большое про­стое число р и число g.Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми або­нентами сети).

Затем каждый абонент группы выбирает свое секретное число ci, 1 < Ci < р - 1 и вычисляет соответствующее ему открытое число di по формуле (3.17):

 

       di=g^cimodp.                                                    (3.17)

 

Покажем теперь, как А передает сообщение т абоненту В. Бу­дем предполагать, как и при описании шифра Шамира, что сообще­ние представлено в виде числа m < р.

 

Шаг 1. А формирует случайное число к, 1  к  р-2, вычисляет числа:

 

r = g^k mod p;                                                                                                  (3.18)

e = m d^Bk mod p.                                                                                           (3.19)

 

и передает пару чисел (r, е) абоненту В.

Шаг 2.  В, получив (r,е), вычисляет число по формуле (3.20):

 

m'= е r^p-1-cBmod р.                                                                                         (3.20)

 

Абонент В получил сообщение, т.е. m'=m.

 

Пример: передадим сообщение m - 15 от А к В. Возьмем р = 23, g = 5. Пусть абонент В выбрал для себя секретное число св = 13 и вычислил по (3.1):

 

dB = 513 mod 23 = 21.

 

Абонент А выбирает случайно число k, например, k = 7, b вы­числяет по (3.18), (3.19):

r = 57 mod 23 =17, е = 15217 mod 23 = 1510 mod 23 = 12.

 

Теперь A посылает к В зашифрованное сообщение в виде пары чи­сел (17,12). B вычисляет по формуле (3.20):

 

m' = 12  17^23-1-13 mod 23 = 12  17⁹ mod 23 = 15.

 

Мы видим, что В смог расшифровать переданное сообщение.        

 

3.5      Электронно-цифровая подпись и ее реализация на основе криптосистемы Эль-Гамаля

 

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

Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, как и в асимметричных системах шифрования, используются разные математические схемы, основанные на применении однонаправленных функции. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:

-       задача факторизации (разложения на множители) больших целых чисел;

-       задача дискретного логарифмирования.

Идея алгоритма цифровой подписи Эль-Гамаля основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,- задача дискретного логарифмирования. Кроме того, Эль-Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число р и большое целое число g, причем g < р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа р и g, которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 < Х £ (р-1), и вычисляет по формуле (3.21):

 

   Y =g^X mod р.                                                 (3.21)

 

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h(М) в целое число m по формуле (3.22):

 

m = h(М), 1<m<(Р-1),                                       (3.22)

 

 

и генерирует случайное целое число К, 1 < К < (р-1), такое, что К и (р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а по (3.23):

а = g^K mod Р.                                                    (3.23)

 

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения (3.24):

 

m = Х·а + К·b (mod (р-1)).                                (3.24)

 

Пара чисел (а,b) образует цифровую подпись S, проставляемую под документом М (3.25):

 

S = (а, b).                                                          (3.25)

 

Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К).держится в секрете.

После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись S = (а, b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число m = h(М), т.е. хэширует принятое сообщение М. Затем получатель вычисляет значение (3.26):

 

А = Y^a a^b (mod р).                                             (3.26)

 

и признает сообщение М подлинным, если выполняется равенство (3.27):

А = G^m (mod р).                                                (3.27)

 

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.

 

Пример: выберем числа р=11, g=2 и секретный ключ Х = 8. Вычисляем значение открытого ключа:

Y = g^X mod р = Y = 2⁸ mod 11=3.

Предположим, что исходное сообщение М характеризуется хэш-значением m = 5.

Для того, чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m = 5, сначала выберем случайное целое число К = 9. Убедимся, что числа К и (р-1) являются взаимно простыми. Действительно, НОД (9,10)=1. Далее вычисляем элементы а и b подписи:

а = g^K mod р = 2⁹ mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = Х * а + К * b (mod(р-1)).

При m = 5, а = 6, Х = 8, К = 9, р = 11 получаем

5 = (6* 8+9* b)(mod 10)

или

9* b=-43(mod 10).

 

Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения М :

m = 5, а затем вычисляет два числа:

1 Y^aa^b (mod р) = 3⁶ * 6³ (mod 11) =10 (mod 11);

2 g^m (mod р) = 2⁵ (mod 11) =10 (mod 11).

 

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

Следует отметить, что схема Эль-Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а, b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

 

3.6      Шифрование по алгоритму RSA

 

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

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

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

Шаг 2. Вычисляется открытая компонента ключа n по формуле (3.28):

 

n = р∙q.                                                     (3.28)

 

Шаг 3. Находится функция Эйлера по формуле  (3.29):

 

        f(р, q)=(р-1)(q-1).                                      (3.29)

 

Функцией Эйлера f(n) называется число положительных целых, меньших n и простых относительно n.

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

 Шаг 4. Выбирается число е, которое должно взаимно простым со значением функции Эйлера и меньшим, чем f(р q.)

Шаг 5. Определяется число d, удовлетворяющее соотношению (3.30):

 

        е ∙ d(mod f(р, q.))=1.                                            (3.30)

 

Числа е и n принимаются в качестве открытого ключа. В качестве секретного ключа используются числа d и n.

Шаг 6. Зашифрованная информация получается в виде последовательности чисел Y(i) и вычисляется по формуле (3.31):

 

Y(i) = (Y(i)) ^e  (mod n).                             (3.31)

 

Шаг 7. Для расшифрования информации используется зависимость (3.32):

 

Х(i)= (Y(i)) ^d (mod n).                               (3.32)

 

Пример: зашифруем и расшифруем сообщение {16, 17, 6, 5, 6, 12} по алгоритму RSA.

1) Выберем p=3 and q=11.

2) Вычислим открытую компоненту ключа:  n= 3∙11=33.

3) Определим функцию Эйлера:  (p-1)∙(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).

4) Выберем число е по следующей формуле: (e∙3) mod 20=1. е будет равно 7: (e=7).

Числа е и n принимаются в качестве открытого ключа, d и n используются в качестве секретного ключа.

5)     Зашифруем сообщение, используя открытый ключ {7,33}:

Y1 = 16⁷ mod 33 =25;

Y2 = 17⁷ mod 33 =8;

Y3 = 6⁷ mod 33 =30;

Y4 = 5⁷ mod 33 =14;

Y5 = 6⁷ mod 33 =30;

Y6 = 12⁷ mod 33 =12.

6)     Расшифруем полученные данные, используя закрытый ключ {3,33}:

Y1 = 25³ mod 33 =16;

Y2 = 8³ mod 33 =17;

Y3 = 30³ mod 33 =6;

Y4 = 14³ mod 33 =5;

Y5 = 30⁷ mod 33 =6;

Y6 = 12³ mod 33 =12.

 

Задачи и упражнения

 

2        Вычислить секретные ключи Ya, Yb и общий ключ Zab для системы Диффи Хеллмана с параметрами:

а)     р=23, g=5, Хa=5, Хb=7;

б)    р=19, g=2, Хa=5, Хb=7;

в)     р=23, g=7, Хa=3, Хb=4;

г)     р=17, g=3, Хa=10, Хb=5;

д)    р=19, g=10, Хa=4, Хb=8.

3        Для шифра Шамира с заданными параметрами найти недостающие параметры и описать процесс передачи сообщения m от А к В:

а)     р=19, Сa=5, Сb=7, m=4;

б)    р=23, Сa=15, Сb=7, m=6;

в)     р=19, Сa=11, Сb=5, m=10;

г)     р=23, Сa=9, Сb=3, m=17;

д)    р=17, Сa=3, Сb=13, m=9.

4        Вычислить с помощью обобщенного алгоритма Евклида значения x и y в уравнениях:

а)     21х+12у=gcd(21,12);

б)    30х+12у=gcd(30,12);

в)     24х+40у=gcd(24,40);

г)     33х+16у=gcd(33,16);

д)    20х+14у=gcd(20,14).

5        С помощью обобщенного алгоритма Евклида найти:

а)     gcd(21,12);

б)    gcd(30,12);

в)     gcd(24,40);

г)     gcd(33,16);

д)    gcd(20,14).

6        Для шифра Эль-Гамаля с заданными параметрами найти недостающие параметры  и описать процесс передачи сообщения m от А к В:

а)     р=19, g=2, Сb=5, k=7, m=5;

б)    р=23, g=5, Сb=8, k=10, m=10;

в)     р=19, g=2, Сb=11, k=4, m=10;

г)     р=23, g=7, Сb=3, k=15, m=5;

д)    р=17, g=3, Сb=10, k=5, m=10.

7        Найти пару ключей, используя алгоритм RSA с параметрами:

а)     р=7, q=11;

б)    р=19, q=11;

в)     р=23, q=7;

г)     р=13, q=7.

8        Зашифровать сообщение по алгоритму RSA с параметрами р=7, q=11:

а)     {8,10,5,1};

б)    {18,7,3,9,11};

в)     {ПРИМЕР};

г)     {ЗАЩИТА};

д)    {23,15,7,3}.

9        Абоненты некоторой сети применяют подпись Эль-Гамаля с общими параметрами р=23, g=5. Для указанных секретных параметров найти открытый ключ Y и построить подпись для сообщения m:

а)     Х=11, k=3, m=h=15;

б)    Х=10, k=15, m=h=5;

в)     Х=3, k=13, m=h=8;

г)     Х=18, k=7, m=h=5;

д)    Х=9, k=19, m=h=15.

10   Для указанных открытых ключей Y пользователей системы Эль-Гамаля с общими параметрами р=23, g=5 проверить подлинность подписанных сообщений:

а)     Y=22: (15;20;3), (15;10;5), (15;19;3);

б)    Y=9: (5;19;17), (7;17;8), (6;17;8);

в)     Y=10: (3;17;12), (2;17;12), (8;21;11);

г)     Y=6: (5;17;1), (5;11;3), (5;17;10);

д)    Y=11: (15;7;1), (10;15;3), (15;7;16).

 

Список литературы

Основная  

1.     Основы практической защиты информации: Учебное пособие. А.В.Петраков – М.: Радио и связь, 2001. – 360 с.

2.     Защита от утечки информации по техническим каналам. Г.А.Бузов – М., 2005.

3.     Криптографические методы защиты информации. Учебное пособие. Б.Я.Рябко, А.Н Фионов – М.: Горячая линия - Телеком, 2005. – 225 с.

4.     Физические основы технических средств обеспечения информационной безопасности. А.Н.Соболев – М., 2004.

 

Дополнительная

 

5.     Информационная безопасность: Концептуальные и методологические основы защиты информации. А.А.Малюк – М., 2004.

6.     Основы построения виртуальных частных сетей. Учебное пособие. С.В.Запечников – М.: Горячая линия. – Телеком, 2005. – 245 с.

7.     защита информации в системах мобильной связи. Учебное пособие. А.А.Чекалин – М.: Горячая линия. – Телеком, 2005. – 170 с.

 

Методические материалы, конспекты лекций и учебные пособия

 

8.     Защита информации в телекоммуникационных системах. Конспект лекций. А.С.Байкенов, Е.А.Шкрыгунова – АИЭС, Алматы, 2008 г.

9.     Защита информации в телекоммуникационных системах. Методические указания к выполнению расчетно-графических работ. А.С.Байкенов, Е.А.Шкрыгунова – АИЭС, Алматы, 2009 г.

10. Защита информации. Учебное пособие. И.В.Васильев – АИЭС, Алматы, 2010 г.

 

Содержание

Введение	3
Глава 1. Криптографическая защита информации и этапы ее развития	4
Глава 2 Симметричные методы криптографического преобразования данных	7
2.1      Шифрование заменой	7
2.2      Метод Цезаря	8
2.3      Системы шифрования Вижинера	9
2.4      Шифрование перестановкой	9
2.5      Шифрование с помощью аналитического метода	10
Задачи и упражнения	12
Глава 3 Системы шифрования с открытым ключом	14
3.1      Система с открытым ключом Диффи-Хелмана	14
3.2      Шифрование по алгоритму Шамира	15
3.3      Алгоритм Евклида	16
3.4      Шифрование по алгоритму Эль-Гамаля	19
3.5      Электронно-цифровая подпись и ее реализация на основе криптосистемы Эль-Гамаля	20
3.6      Шифрование по алгоритму RSA	22
Задачи и упражнения	24
Список литературы	27