Защита информации - курс лекций

53

Введение

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

Вводная лекция.

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

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

Криптосистема - это система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации.

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

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

В развитии криптологии принято выделять три этапа.

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

Второй этап. (1949-1976гг.) Этот этап принято отсчитывать с момента публикации американского математика-прикладника К. Шеннона «Теория связи в секретных системах». В этот период принято активно проводились систематические исследования по криптологии с использованием компьютера. Криптология становится математической наукой.

Третий этап. (1976г. - настоящее время). Этот этап можно назвать и «эрой открытой криптологии». Этот этап принято отсчитывать с момента публикации работы американских математиков У.Дифори, М.Хеллмана «Новые направления в криптографии».В этой работе было показано, что «секретная» передача информации возможна (вотличие от результатов Шеннона) без предварительной передачи «секретного ключа».

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

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

Некоторые определения и формулы.

В криптологии общеприняты следующие понятия:

· Пространство сообщений - множество всевозможных сообщений . Для сообщений используется также обозначение .

· Пространство ключей . Каждый ключ к определяет некоторую подстановку на пространство и обратное преобразование .

· Пространство зашифрованных сообщений , состоящее из зашифрованных . Используется также обозначение

Остается уточнить понятие текста. При этом обычно фиксируют некоторую сумму символов, называемую алфавита. Это может быть английский, русский или какой-нибудь другой алфавит. Часто в качестве алфавита используются натуральные числа или символы 0 и 1. Словом называется упорядоченный набор букв данного алфавита. Множество слов обозначают через . Текст набор слов.

1. Арифметические основы

Основные обозначения.

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

- множество натуральных чисел.

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

- множество комплексных чисел. Комплексное число - число вида , где и - действительные числа, а - т.н. мнимая единица, т.е. число, квадрат которого равен -1.

- множество рациональных чисел. Рациональное число - число, которое может быть представлено в виде дроби , где и - целые числа ().

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

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

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

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

(2.1)

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

(2.2)

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

/Пример/

Найдем НОД (175,77).

175=77*2+21;

77=21*3+14;

21=14*1+7;

14-7*2.

Последний положительный остаток равен 7. Следовательно (175,77)=7.

Наименьшее общее кратное. Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным (НОК) и обозначается .

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

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

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

(2.3)

это читается следующим образом: сравнимо с по модулю .

*Доказательство*

Из следует, что

( - остаток от деления на , - неполное частное)

откуда

Обратно, из представляя в виде

выводим

т.е.

. ?

Сравнимость чисел и по модулю равносильна: возможности представить в виде , где - целое.

Свойства сравнений.

1. Два числа, сравнимые с третьим, сравнимы между собой.

2. Сравнения можно почленно складывать.

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

4. Сравнения можно почленно перемножать.

5. Обе части сравнения можно возвести в одну и ту же степень.

6. Обе части сравнения можно умножить на одно и то же целое число.

7. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.

8. Обе части сравнения и модуль можно умножить на одно и то же целое.

9. Обе части сравнения и модуль можно разделить любой их общий делитель.

10. Если сравнение имеет место по нескольким модулям, то оно имеет место и по модулю, равному общему наименьшему кратному этих модулей.

11. Если сравнение имеет место по модулю , то оно имеет место и по модулю , равному любому делителю числа .

12. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

Первообразные корни. При существуют положительные с условием , например (теорема Эйлера) .Наименьшее из них называется: показатель, которому принадлежит по модулю .

Если по модулю принадлежит показателю , то числа по модулю несравнимы.

Если по модулю принадлежит показателю , то тогда и только тогда, когда в частности (при ), , тогда и только тогда, когда делится на .

Пусть по модулю принадлежит показателю . Тогда делится на . Таким образом, показатели, которым числа принадлежат по модулю , есть делители . Числа, принадлежащие показателю (если такие существуют), называются первообразными корнями по модулю .

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

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

Символ Якоби. Символ Якоби является обобщением символа Лежандра и служит для упрощения вычисления последнего. Пусть - нечетное натуральное число, - его разложение на простые множители. Для всякого целого , , символ Якоби определяется по формуле:

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

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

2. Алгебраические основы

Понятие группы.

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

1). Операция * ассоциативна, т.е. для любых .

2). В G имеется единичный элемент (или единица) e такой, что для любого

3). Для каждого a G существует обратный элемент такой, что

4). Для любых

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

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

Через будет отличать аддитивную группу классов вычетов по модулю m.

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

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

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

Циклическая группа всегда коммутативна.

Подгруппы групп.

Подмножество группы называется подгруппой этой группы, если H образует группу относительно операции группы .

Подгруппы группы , отличные от тривиальных групп , называется собственными подгруппами.

Гамоморфизмы групп.

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

Кольца и поля.

Кольцом называется множество с двумя бинарными операциями, обозначаемыми символами “+” и “*”, такими что:

1). - абелева группа;

2). Операция умножения ассоциативна, т.е. для всех ;

3). Выполняются законы дистрибутивности, т.е. для всех

и ;

Подкольца.

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

Гомоморфизмы колец.

Пусть и - кольца. Гомоморфизмом называется отображение, для которого , , при всех

3. Генераторы случайных последовательностей

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

Случайные числа и их генераторы являются неотъемлемыми современных криптосистем. Приведём конкретные примеры использования случайных чисел в криптологии:

1). Сеансовые и другие ключи для симметрических криптосистем, таких как DES, ГОСТ 28 147-89, Blowfish;

2). Стартовые значения для программ генерации ряда математических величин в асимметрических криптосистемах, например, “больших простых чисел” в криптосистемах RSA, ElGamal;

3). Случайные слова, комбинируемые с парольными для нарушения “атаки угадывания” пароля криптоаналитика;

4). Вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;

5). Случайные значения параметров для многих систем электронной цифровой, например DSA;

6). Случайные выборы в протоколах аутенфинации, например в протоколе Цербер (Kerberos);

7). Случайные параметры протоколов для обеспечения уникальности различных реализаций одного и того же протокола, например в протоколах SET и SSL.

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

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

РРСП - случайная последовательность со значениями в дискретном множестве, определённая на вероятностном пространстве и удовлетворяющая двум свойствам - и .

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

Свойство . Для любого номера случайная величина имеет дискретное равномерное на распределении вероятностей:

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

Свойство . Если - РРСП, то для любого и любой фиксированной последовательности индексов -мерное дискретное распределение вероятностей вектора (слова) является равномерным:

Свойство . Если - элемент РРСП, то справедливы следующие выражения его начального и центрального моментов - го порядка:

Где - числа Бернулли.

Свойство . Для новариационной функции и спектральной плотности РРСП справедливы следующие выражения:

Свойство . (воспроизводимость при прореживании). Для любой фиксированной последовательности моментов времени при “прореживании” РРСП возникает последовательность

,

которая тоже является РРСП.

Свойство . (воспроизводимость при суммировании). Если - РРСП, а - произвольная неслучайная либо случайная последовательность, не зависящая от , то случайная последовательность также является РРСП.

Свойство . Если - РРСП, то количество информации по Шеннону, содержащейся в отрезке последовательности , о будущем элементе равно нулю:

,

поэтому для любого алгоритма прогнозирования вероятность ошибки не может быть меньше, чем для “угадывания по жребию”:

.

Свойство . Если - РРСП, то для любого и произвольной борелевской функции переменных , при имеет место сходимость “почти наверное”:

Свойство . Если - равномерно распределенная последовательность порядка , то - РРСП.

С учетом свойств определим понятия генератора случайной последовательности и его типов.

Генератор РРСП - устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности длиной ; элементы этой реализации принято называть случайными числами. Существует три типа генераторов РРСП:

1. Табличный.

2. Физический.

3. Программный.

В следующем разделе мы рассмотрим программный генератор.

Программный генератор РРСП - программа имитации на компьютере реализации РРСП. Имитируемая последовательность называется псевдослучайной, так как она вычисляется на компьютере по известному детерминированному (обычно рекуррентному) соотношению, и в то же время её статические свойства “близкие” к свойствам РРСП.

В разделе “Алгоритмы генерации псевдослучайных последовательностей” мы познакомимся с основными методами генерации псевдослучайных последовательностей, а в разделе “Методы генерации истинно случайных последовательностей” мы рассмотрим различные методы повышения “случайности” генераторов РРСП.

3.2 Алгоритмы генерации псевдослучайных последовательностей.

Классификация существующих алгоритмов генерации псевдослучайных последовательностей представлена на рис. Выделяются три основных подхода к построению алгоритмов генерации:

1). Прямые методы построения элементарных рекуррентных последовательностей:

.

2). Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.

3). Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.

Линейные и мультипликативные конгруэнтные генераторы. Линейным конгруэнтным генератором (ЛКГ) с параметрами () называется программный генератор РРСП, порождающий псевдослучайную последовательность ,, с помощью рекуррентного соотношения

(3.2.1)

Параметры этого генератора (3.2.1) имеют следующий смысл:

- начальное или стартовое значение;

- не нулевой множитель;

- приращение;

- модуль, равный мощности алфавита .

Если приращение , то генератор () называется мультипликативным конгруэнтным генератором (МКГ), а если , то смешанным конгруэнтным генератором (СКГ).

«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы , то точки , на плоскости будут лежать на прямых из семейства . Для устранения этого недостатка нелинейные конгруэнтные генераторы, среди которых известны: квадратичный конгруэнтный генератор; Генератор Эйхенауэра-Лена с обращением; конгруэнтный генератор, использующий умножение с переносом.

Квадратичный конгруэнтный генератор. Этот алгоритм генерации псевдослучайной последовательности определяется квадратичным рекуррентным соотношением

, ()

где - параметры генератора. Выбор этих параметров осуществляется на основе следующих двух свойств последовательности ().

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

1). - взаимно простые числа;

2). - кратны , где - любой нечётный простой делитель ;

3). - чётное число, причем

4). Если кратно 9, то либо , либо и .

Свойство . Если , то наибольший период тогда и только тогда, когда - нечётно, - чётно, - нечётное число, удовлетворяющее соотношению

.

Генератор Эйхенауэра-Лена с обращением. Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра-Лена с обращением определяется следующим нелинейным рекуррентным соотношением :

(

где - обратный к элемент по модулю , т.е. - параметры генератора.

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

(

Где в отличие от (), «приращение» изменяется во времени и зависит от указанных аргументов нелинейно:

()

Параметрами нелинейного конгруэнтного генератора (), () является .

Рекуррентны в конечном поле. Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка над конечным полем ( - простое число):

()

где - коэффициенты рекуррентны, а - начальные значения рекуррентны.

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

()

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

Генераторы Фибоначчи. Общий вид рекуррентного соотношения, определяющего генератор Фибоначчи задаётся уравнением

, ()

где - параметры генератора, . В случае или - целые числа .

4. Первый этап развития криптографии

Защита информации может быть двух видов: шифрование и передача по закрытому каналу.

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

Будем считать, что A (Алиса) - отправитель сообщения, а В (Боб) - корреспондент (получатель) сообщения, Е (Елена) - некий враг.

Классическая система секретной связи показана на рис. 1.

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

Шифрование осуществляется в соответствии с этой подстановкой. Величина не является единственно возможной.

Криптоанализ этого шифра очень прост. Для любого современно языка вычислены частотные характеристики букв, т.е. относительные частоты их появления в “нормальных” текстах.

Модулярный шифр.

Выберем число , взаимно просто с модулем. Пусть р - буква английского алфавита, отождествлённая со своим порядковым номером (0,1,…,25). Тогда ,, где - фиксировано. В этом случае ключом является пара чисел . Условие взаимной простоты необходимо для обратимости шифра.

Гомофоническое шифрование.

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

Полиграммное шифрование.

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

Замена биграмм производится по правилам:

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

2) если и находятся на одном столбце, то берутся нижние соседи с аналогичной оговоркой.

3) если , то в незашифрованном тексте между ними вставляется незначащая буква (например, ).

4) при нечетном количестве букв в незашифрованном тексте к нему дописывается незначащая буква.

5) в наиболее вероятном количестве, когда и расположены в разных столбцах и строках, и выбираются, как показано на схеме:

Код Энигма.

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

Код Энигма в своем первоначальном виде потерял свою привлекательность при появлении ЭВМ, т.к. пять барабанов могли обеспечить лишь около ста миллионов ключей, что возможно перебрать за один день.

5. Второй этап развития криптографии

5.1 Шенноновское понятие секретных систем

По Шеннону существует три общих типа секретных систем:

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

2. Тайные системы (например, инвертирование речи), в которых для раскрытия сообщения требуется специальное оборудование;

3. «Собственно» секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., но само существование сообщения не скрывается и предполагается. Что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов.

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

Оценка секретных систем.

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

1) Количество секретности.

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

2) Объем ключа.

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

3) Сложность операции шифрования и дешифрования.

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

4) Разрастание числа ошибок.

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

5) Увеличение объема сообщения.

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

Совершенная секретность.

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

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

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

где - априорная вероятность сообщения ;

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

- вероятность получения криптограммы ;

- апостериорная вероятность сообщения при условии, что перехвачена криптограмма .

Для совершенной секретности системы величины и должны быть равны для всех и . Следовательно, должно быть выполнено одно из равенств:

или же , для любых и .

Если , то , и система совершенно секретна.

Теорема.

Необходимое и достаточное условие для совершенной секретности состоит в том, что

для всех и , т.е. не должно зависеть от .

Ненадежность.

Имеется два основных типа ненадежности: ненадежность ключа и ненадежность сообщения.

- ненадежность ключа;

- ненадежность сообщения.

,

,

где , , - криптограмма, сообщение, ключ.

- вероятность ключа и криптограммы .

- апостериорная вероятность ключа , если перехвачена криптограмма .

- вероятность сообщения и криптограммы .

- апостериорная вероятность сообщения , если перехвачена криптограмма .

Для кода подстановки.

6. Третий этап развития криптографии

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

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

6.1 Шифр Ривеста - Шамира - Алдемана

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

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

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

Чтобы восстановить исходный текст, поступает следующим образом:

1. Находит число , такое, что и .Это сравнение разрешимо единственным образом, поскольку .

Для решения сравнения пользователь должен вычислить .

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

Алгоритм применения RSA.

1. Отправитель выбирает два больших простых числа и . Вычисляет два произведения и

2. Затем он выбирает случайное число (целое), взаимно простое с , и вычисляет , удовлетворяющее условию .

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

4. Если - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале , то она превратится в криптограмму возведением в степень по модулю и отправляется получателю в следующем виде .

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

Пояснение.

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

Электронная подпись (цифровая подпись).

Если планирует подписывать документ Ц.П., то он должен выбрать параметры RSA. выбирает два простых числа и , вычисляет затем выбирает число ,взаимно простое с , и вычисляет , далее публикует числа и и хранит в секрете . Числа - более не понадобятся.

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

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

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

- вид сообщения с подписью.

Теперь каждый, кто знает открытые параметры , т.е. и , может проверить подлинность его подписи.

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

/*Пример*/ Электронная подпись RSA.

Пусть

(алгоритм Евклида).

(допущение)

вычисляет

- сообщение с подписью

Вычисляем значение хеш-функции, получим

Подпись верна.

Определение Хеш-функции.

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

9. Криптографические алгоритмы

9.1 Шифр Эль-Гамаля

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

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

Затем каждый абонент выбирает своё секретное число , , и вычисляет соответствующе ему открытое число ,

()

В результате получаем следующую таблицу ().

Табл(). Ключи пользователей в системе Эль=Гамаля.

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

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

(9.1.2)

(9.1.3)

и передаёт пару чисел абоненту Бобу.

Шаг 2. Боб, получив , вычисляет

(9.1.4)

/*Пример*/

Алиса хочет передать Бобу сообщение . Допустим Пусть Боб выбрал для себя секретное число и вычислил по формуле (9.1.1)

Алиса выбирает случайное число , например , и вычисляет по (9.1.2) и (9.1.3):

.

Теперь Алиса посылает Бобу шифрограмму (17,12). Боб вычисляет по формуле (9.1.4):

Боб расшифровал сообщение

Электронная подпись на базе Эль-Гамаля.

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

Затем она вычисляет число

(9.1.5)

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

Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение . Опишем последовательность действий для построения подписи.

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

(9.1.6)

Далее Алиса вычисляет числа:

(9.1.7)

(9.1.8).

Под в (9.1.8) подразумевается число, удовлетворяющее уравнению

(9.1.9)

Такое существует, так как и взаимно просты, и может быть найдено по алгоритму Евклида. Наконец Алиса формирует подписанное сообщение

(9.1.10).

Получив сообщение Боб заново вычисляет значение хеш-функции и проверяет подпись, используя равенство

(9.1.11)

/*Пример*/

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

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

9.2 Криптосистемы на эллиптических кривых

Использование эллиптических кривых в криптографических целях было Нило Коблицом и Виктором Миллером в 1985 году. С 1998 года использование эллиптических кривых для решения криптографических задач, таких, как цифровая подпись, было закреплено в стандартах США ANSI X9.62 и FIPS 186-2, а в 2001 году аналогичный стандарт, ГОСТ Р34.10-2001, был принят и в России.

Особое достоинство криптосистем на эллиптических кривых состоит в том, что по сравнению с “обычными” RSA системами, они обеспечивают существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стойкости.

В результате тот уровень стойкости, который достигается в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.

Эллиптические кривые.

Кривая третьего порядка , задаваемая уравнением вида:

(1)

называется эллиптической кривой.

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

(2)

Дискриминант этого уравнения равен

(3)

Если уравнение (2) имеет три различных корня если то (2) имеет три действительных корня (два из которых равны); если уравнение имеет один действительный корень и два комплексно сопряженных.

Графический вид шифрования.

- изменение знака

Алгоритм шифрования.

Для пользователей некоторой сети выбираются общая эллиптическая кривая и некоторая точка , такая, что … - это различные точки, а (точка в бесконечности) для некоторого простого числа .

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

Допустим, пользователь хочет передать сообщение пользователю .

делает следующее:

1. Выбирает случайное число

2. Вычисляет ;

3. Шифрует

4. Посылает криптограмму

Пользователь после получения

1. Вычисляет

2. Дешифрует

{ - угловой коэффициент }

Цифровая подпись.

Для сообщества пользователей выбирается общая эллиптическая кривая и точка на ней, такая, что … суть различные точки, и для некоторого простого числа (длина числа равна 256 бит).

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

Чтобы подписать сообщение, Алиса делает следующее:

1. Вычисляет значение хеш-функции сообщения ;

2. Выбирает случайно число , ;

3. Вычисляет ;

4. Вычисляет (при возвращается к шагу 2);

5. Вычисляет (при возвращается к шагу 2);

6. Подписывает сообщение парой чисел .

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

1. Вычисляет ;

2. Убеждается, что ;

3. Вычисляет и ;

4. Вычисляет композицию точек на кривой и если , отвергает подпись;

5. Если , принимает подпись, в противном случае отвергает ее.

9.5 Общие принципы стохастической защиты информации

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

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

1) Примен ...........