WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Федеральное агентство по образованию

Уральский государственный технический университет – УПИ

А.В. Кибардин

МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ

Учебное текстовое электронное издание

Подготовлено кафедрой вычислительной техники

Научный редактор: проф., д-р т. наук С.Л. Гольдштейн

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

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

© УГТУ-УПИ,

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

СРАВНЕНИЯ И КЛАССЫ ВЫЧЕТОВ

ГРУППЫ

КОЛЬЦА И ПОЛЯ

МУЛЬТИПЛИКАТИВНЫЕ ФУНКЦИИ

Функция Мебиуса

Функция Эйлера

ПРИВЕДЕННАЯ СИСТЕМА ВЫЧЕТОВ

ТЕОРЕМЫ ЭЙЛЕРА И ФЕРМА

СРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ

ПРИМЕРЫ КРИПТОГРАФИЧЕСКИХ АЛГОРИТМОВ

Симметричные криптоалгоритмы

Подстановки

Перестановки

Ассиметричные криптоалгоритмы

Критпоалгоритм без передачи ключа

Криптоалгоритм с открытым ключом

Электронная подпись

Генерация ключей

Конгруэнтные датчики

Датчики М-последовательностей

Генерация простых чисел

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

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




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

Священные книги древнего Египта, древней Индии тому примеры.

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

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

СРАВНЕНИЯ И КЛАССЫ ВЫЧЕТОВ

Два числа a и b сравнимы по модулю n (n – натуральное), если их разность a – b делится на n без остатка.

a b (mod n), (1) где n – модуль сравнения.

Пример 35 2(mod 11) 25 -11(mod 9) Если зафиксировать модуль сравнения n, то всякое натуральное число можно единственным образом представить как c = k ·n + r, (2) где k – частное от деления c на n, r – остаток (вычет), совпадающий с одним из чисел 0, 1, 2, …n – Отметим, что запись (2), где 0 r n – 1 допускает любые целые числа, а не только натуральные.

Очевидно, что из равенства (2) следует, что с r ( mod n), т.е. всякое число сравнимо со своим остатком (вычетом) по модулю n.

Два числа a = k1· n + r1 и b = k2· n + r2 сравнимы по модулю n a b (mod n) (3) если имеют одинаковые остатки при делении на n (r1 = r2).

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

Если a1 b1 и a2 b2, то a1+a2 b1 + b a1· a2 b1· b Тогда 17·7 5 ·3 (mod 4) или 119 15(mod 4) Значения этих свойств заключается в том, что при рассмотрении вопросов делимости чисел и арифметических выражений можно входящие в эти выражения числа заменять на сравнимые с ними по модулю n.

Доказать, что 1981k + 1982k при любом нечетном натуральном k делится на 3.

Заметим, что 1981 1(mod 3), 1982 2(mod 3).

Тогда 1981k + 1982k 1+2k (mod 3).

Используя метод индукции легко показать, что 2k 1 при k четном и 2k при нечетном k. Отсюда Все числа, имеющие один и тот же вычет по модулю n и, следовательно, сравнимые между собой по модулю n, оказываются взаимозаменяемыми. Объединим их в один класс, обозначаемый r Иными словами класс r состоит из целых чисел 0, 1, 2, …n – 1. Каждому вычету 0, 1, 2, …n – 1 отвечает свой класс вычетов, так что имеется ровно n различных классов Операции сложения и умножения можно выполнять и над классами вычетов. Пусть r 1 и r 2 - два класса вычетов. Выберем любые два числа из этих классов: a1 r 1 и a2 r 2. Пусть сумма a1+a2 имеет вычет r, а произведение a1 a – вычет s:





Тогда будем считать, что сумма классов r 1 и r 2 равна r, а их произведение равно s.

Пример Пусть n = 2. Имеется два класса вычетов 0 и 1. Операции над ними выглядят так:

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

Таблицы сложения и умножения классов вычетов по модулю 4.

+ Эти таблицы можно понимать буквально, считая, что они определяют две операции на множестве {0, 1, 2, 3} – сложение и умножение по модулю 4.

ГРУППЫ

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

Пусть множество М состоит из чисел 1, 2, 3: M = {1, 2, 3}. Чтобы задать какую-либо подстановку множества М, достаточно указать для каждого из чисел 1, 2, 3 то число, в которое оно отображается этой подстановкой. Удобнее это сделать, используя таблицу из двух строк:

Данные две таблицы задают одну и ту же подстановку.

Нетрудно указать все различные подстановки множества М.

Определим теперь на множестве S ={1, 2, 3, 4, 5, 6} всех подстановок операцию умножения ( или композицию) подстановок: произведением подстановок i и j будем называть подстановку k, получающуюся в результате последовательного выполнения сначала подстановки i, а затем подстановки j:

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

Множество S с определенной выше операцией умножения называют группой подстановок множества М. Операция умножения на S обладает следующими свойствами.

1. Операция ассоциативна: для любых i, j, k 2. Существует единичный элемент 1, такой, что 3. Вместе с каждой подстановкой i множество S содержит обратную ей подстановку j, которая переводит число a в b тогда и только тогда, когда i переводит число b в число a. При этом понятно, что каждое из произведений i · j и j · i будет тождественной подстановкой:

Существуют самые разнообразные системы объектов с операцией, обладающей указанными свойствами.

Дадим общее определение группы.

Множество G, на котором определено умножение элементов, называется группой, если выполняются три следующие аксиомы.

1. Умножение ассоциативно: для любых элементов a, b, c из G a(bc) =(ab)c.

2. В множестве G существует единичный элемент e, такой, что ea = ae = e.

3. Для каждого элемента a множества G существует обратный элемент a-1, В приведенном выше определении говорится об умножении элементов.

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

1. Сложение ассоциативно: для любых элементов a, b, c из G 2. В множестве G существует нулевой элемент 0, такой, что 0+a = a+0 = a.

3. Для каждого элемента a множества G существует противоположный элемент -a, такой, что a =(-a) = (-a)+a = 0.

Примеры групп 1. Множество всех действительных чисел относительно операции умножения – мультипликативная группа действительных чисел R*.

2. Множество всех целых чисел относительно операции сложения – аддитивная группа целых чисел Z.

3. Множество всех векторов пространстве относительно операции сложения векторов.

4. Множество всех многочленов с действительными коэффициентами относительно операции сложения многочленов.

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

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

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

Если некоторое подмножество H группы G само образует группу относительно операции, определенной в G, то подмножество H называют подгруппой группы G. Например, подмножества H1={ 1, 2} и H2={ 1, 4, 5,} группы S являются подгруппами этой группы. Подмножество четных целых чисел есть подгруппа аддитивной группы целых чисел, а подмножество нечетных чисел не будет подгруппой этой группы.

Для того, чтобы подмножество H являлось группой G, необходимо и достаточно, чтобы выполнялись два условия:

1) произведение любых элементов h1 и h2 из подмножества H также 2) если h H, то и обратный к нему элемент принадлежит H.

Наиболее простые так называемые циклические подгруппы, которыми обладает любая группа G. Со всяким элементом g G можно связать порожденную им циклическую подгруппу, которая по существу, представляет собой наименьшую из подгрупп, содержащую данный элемент. Чтобы определить ее, введем понятие степени элемента g, полагая, что g0 = e и для любого натурального k Ясно, что всякая подгруппа, содержащая элемент g, должна содержать все его степени. С другой стороны, уже само множество степеней образует группу.

Указанную группу называют циклической подгруппой, порожденной элементом g; ее обозначают (g), а сам элемент g называют образующим элементом этой группы.

Может случиться, что для некоторого элемента g циклическая подгруппа (g) совпадает со всей группой G, тогда группа G также называется циклической.

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

КОЛЬЦА И ПОЛЯ

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

Кольцом называется непустое множество K, на котором определены две операции (сложение и умножение), обладающие следующими свойствами:

1) множество К относительно умножения образует коммутативную группу;

2) умножение ассоциативно: для любых a, b, c из K 3) сложение и умножение подчиняются дистрибутивному закону: для любых a, b, c из K При этом множество K, рассматриваемое лишь относительно операции сложения, называется аддитивной группой кольца.

Примеры 1. Множество целых чисел с операциями сложения и умножения – кольцо целых чисел Z.

2. Множество многочленов от одного неизвестного с действительными коэффициентами с операциями сложения и умножения многочленов.

3. Множество классов вычетов по модулю n с операциями сложения и умножения классов вычетов – кольцо классов вычетов Zn.

В общем определении кольца не содержится требования коммутативности умножения. В том случае, если умножение в кольце обладает этим дополнительным свойством, кольцо называется коммутативным. Примеры колец 1…3 – это коммутативные кольца.

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

Рассмотрим таблицы умножения ненулевых элементов в кольцах классов вычетов Z4 и Z5.

* Первая таблица показывает, что в кольце могут существовать ненулевые элементы, произведение которых равно нулю: в Z4 это 2 · 2 = 0. Из этой же таблицы видно, что класс вычетов 2 необратим. С другой стороны, вторая таблица показывает, что в кольце Z5 всякий ненулевой элемент обратим. Кольца с этим свойством имеют особое значение. Примем следующее определение.

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

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

Простейшие примеры числовых полей – поле рациональных чисел Q и поле действительных чисел R (относительно операций сложения и умножения).

Полем является кольцо классов вычетов Z5. Вообще, можно доказать, что при любом простом p (и только в этом случае) кольцо вычетов Zp является полем.

Оно называется полем вычетов по модулю p.

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

Важное их свойство, используемое в теории кодирования состоит в следующем: мультипликативная группа поля Галуа является циклической группой порядка q-1. Образующий элемент мультипликативной группы поля Галуа называют примитивным элементом. Так в поле Z7 примитивным элементом является класс вычетов 3. Действительно, его степени исчерпывают все ненулевые элементы.

МУЛЬТИПЛИКАТИВНЫЕ ФУНКЦИИ

Функция (a) называется мультипликативной, если она удовлетворяет двум следующим условиям:

1) эта функция определена для всех целых положительных а и не равна нулю по меньшей мере при одном таком а;

2) для любых взаимно простых а1 и а2 имеем Функция as, где s – вещественное или комплексное число, является мультипликативной.

Отметим следующее свойство любой мультипликативной функции: (1)=1.

Рассмотрим мультипликативные функции, использующиеся в криптографии.

Функция Мебиуса Функция Мебиуса определяется следующими равенствами: для любого простого p (p)=-1, (p)=0, если 1.

Из этого определения следует, в частности, что 1) если в каноническом разложении числа a = p11· p22 · …· pkk (pi – простые сомножители числа, а i – кратности их вхождения) по меньшей мере один из показателей i превосходит 1, то имеем (а)=0;

2) в противном случае, т.е. в случае, если каноническое разложение числа а имеет вид a = p1· p2· …· pk, имеем (а)=(-1)k.

Примеры Функция Эйлера Функция Эйлера (а) определяется для всех целых положительных а и представляет собой количество чисел в ряду 0, 1, 2, …а-1, взаимно простых с а.

Отметим, что если p – простое число, то (p) = p -

ПРИВЕДЕННАЯ СИСТЕМА ВЫЧЕТОВ

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

Взяв от каждого такого класса по одному числу, получим приведенную систему вычетов (полную систему вычетов образуют числа 0, 1, 2, …m-1). Количество чисел из ряда 0, 1, 2, …m-1, взаимно простых с m есть (m).

Приведенная система вычетов по модулю 42:

ТЕОРЕМЫ ЭЙЛЕРА И ФЕРМА

1. При m1 и a и m взаимно простых (этот факт будем обозначать (a, m)=1) имеет место теорема Эйлера:

2. При p – простом и а, не делящимся на p, имеет место теорема Ферма:

Эта теорема – следствие теоремы Эйлера при m=p.

Другая формулировка теоремы Ферма:

СРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ

Рассмотрим сравнение вида Если a не делится на m, то n называется степенью сравнения.

Решить сравнение – значит найти все значения x, ему удовлетворяющие.

Два сравнения, которым удовлетворяют одни и те же значения x, называются равносильными.

Если сравнению удовлетворяет какое-либо x=x1, то тому же сравнению будут удовлетворять и все числа, сравнимые с x1 по модулю m:

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

Имеется сравнение x5 + x + 10 (mod 7).

Среди чисел 0, 1, 2, 3, 4, 5, 6 полной системы вычетов по модулю 7 ему удовлетворяют два числа х=2 и х=4.

Сравнение 1-й степени перенесением свободного члена в правую часть можно привести к виду 1. При условии (a, m) =1 сравнение (7) имеет одно решение.

2. Пусть (a, m) =d. Сравнение (7) невозможно, если b не делится на d.

При b, кратном d сравнение имеет d решений:

где m1=m/d.

Рассмотрим сравнение вида ax(mod m), где (a, m)=1. Обычно для решения сравнения пользуются алгоритмом Евклида или теоремой Ферма-Эйлера. Согласно этой теореме (см. выше) если (a, m)=1, то Поэтому x a(m)-1(mod m).

ПРИМЕРЫ КРИПТОГРАФИЧЕСКИХ АЛГОРИТМОВ

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

где a – десятичный коэффициент; s – коэффициент сдвига; e – код буквы исходного текста; c – код зашифрованной буквы; K – длина алфавита; mod – операция вычисления остатка от деления выражения в скобках на модуль К.

Пример. Шифр Цезаря Рассмотрим шифрование на алфавите, состоящим и 26 латинских букв и знака пробела (пробел будем изображать знаком #). Знаку # присвоим код 0, букве A – код 1, B – код 2,… букве Z – код 26.

Исходное сообщение: WE#NEED#SNOW Формула для шифрования примет вид Входной алфавит:

#ABCDE FGHI J K LMNOPQRSTUVWXYZ

Выходной алфавит

BCDEFGHIJKLMNOPQRSTUVWXYZ#A

(Буквы сдвигаются на две позиции: A-C B-D и т.д.) Тогда исходное сообщение в зашифрованном виде будет выглядеть так:

YGBPGGFBUPQY

Для расшифровки (для случая, когда a=1) используется следующая формула Простая многоалфавитная подстановка последовательно и циклически меняет используемые алфавиты (в предыдущем случае для шифрования использовался один алфавит). При m-алфавитной подстановке знак a1 из исходного сообщения заменяется знаком из алфавита B1, знак a2 – знаком из алфавита B2, … знак am – знаком из алфавита Bm, знак am+1 – знаком из алфавита B1 и т.д.

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

Исходное сообщение: WE#NEED#SNOW Ключ: SECURITY В качестве ключа выбрано слово SECURITY. Слово записывается под исходным сообщением, когда буквы ключа исчерпываются, начинаем повторять слово, пока не закончатся буквы исходного сообщения.

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

Задание Предлагаем в качестве упражнения составить шифровку до конца.

Перестановки Знаки исходного текста можно переставлять в соответствии с определенным правилом.

Пример 1. Линейная перестановка Пусть необходимо зашифровать следующий текст:

ГРУЗИТЕ#АПЕЛЬСИНЫ#БОЧКАХ

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

ГРУЗ ИТЕ# АПЕЛ ЬСИН Ы#БО ЧКАХ

Зададим следующее правило перестановки: «переставить группировки из четырех букв, находящихся в порядке 1-2-3-4 в порядок 3-1-4-2».

Получим следующий зашифрованный текст:

УГЗР ЕИ#Т ЕАЛП ИЬНС БЫО# АЧХК

!!!Если длина сообщения не кратна длине группы, то последнюю группу дополняем символами (например, пробелами) до нужной длины.

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

Пример 2. Решетка Кардано Решетка Кардано – это прямоугольная карточка с отверстиями, чаще квадратная, которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. Число строк и столбцов четно. Карточка сделана так, что при ее последовательном повороте каждая клетка лежащего под ним листа будет занятой. Если решетка квадратная, то можно последовательно поворачивать ее вокруг центра квадрата на 90°. На рис. 2 приведен пример решетки: 1 – исходное состояние; 2…4 – результаты ее поворотов по часовой стрелке на 90°.

Задание Пусть имеется следующая решетка размером 6 х 6.

Шифровка:

ВАВОЧСМУНОТИМЫЖРОЕЬУХСОЙМДОСТОЯАСНТВ

Расшифровать сообщение, вращая решетку по часовой стрелке на 90°. Сообщение впишите в квадрат по строкам.

Ассиметричные криптоалгоритмы Критпоалгоритм без передачи ключа Пусть абоненты А и В условились организовать секретную переписку между собой. Для этой цели они выбирают достаточно большое простое число р, такое, что р-1 разлагается на не очень большие простые сомножители. Каждый из абонентов независимо от другого выбирает случайное, натуральное и взаимно простое с числом р-1: а и b числа выбранные абонентами А и В соответственно.

Далее абоненты находят свои вторые ключи. Абонент А находит число из условия Абонент В находит число из условия:

Пусть абонент А решает послать сообщение m абоненту B. Будем считать, что 0mp-1. Если это не так, то m можно разделить на части и переслать по частям. Тогда абонент А сначала зашифровывает это сообщение своим первым секретным ключом а и находит Зашифрованное сообщение m1 он отправляет своему абоненту.

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

и получает исходное сообщение m (m4=m).

Пусть абоненты А и В выбрали простое число р=23 и каждый их них независимо от другого выбрал числа a=5 и b=7 соответственно.

Далее они находят свои вторые ключи, решая следующие сравнения.

Пусть абонент А отправляет сообщение m=17 абоненту В.

Тогда он сначала шифрует сообщение своим первым ключом a= Второй абонент, получив сообщение m1, также шифрует его своим первым ключом b=7 и отравляет его абоненту А:

Абонент А, вновь шифрует полученное сообщение своим вторым ключом = 9 и отправляет его абоненту В:

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

A: p1, p2, rA = p1· p2, (rA), (a, (rA)) = 1, 0 a (rA) B: q1, q2, rB = q1· q2, (rB), (b, (rB)) = 1, 0 b (rB) Затем печатается телефонная книга, доступная всем желающим, которая имеет вид:

Здесь rA – произведение двух простых чисел p1, p2, известных только абоненту А; а – открытый ключ, доступный каждому, кто хочет передать сообщение А;

rB – произведение двух простых чисел q1, q2, известных только абоненту B;

b – открытый ключ, доступный каждому, кто хочет передать сообщение B.

Каждый из абонентов находит свой секретный ключ из сравнений:

Получаем следующую таблицу ключей:

Таблица Ключи абонентов Пусть абонент А решает послать сообщение m абоненту В:

иначе текст делят на куски длиной rB.

Далее абонент А шифрует свое сообщение m открытым ключом абонента В и находит Абонент В расшифровывает это сообщение своим секретным ключом:

и получает m2 = m.

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

p1 = 7 p2 = 23 - простые числа А rB = q1· pq2 = 187 (rB) = a = 7 b = 9 – случайные числа, выбранные А и В соответственно.

Телефонная книга:

Каждый из абонентов находит свой секретный ключ:

Пусть абонент А решает послать абоненту В сообщение m =3.

Тогда он шифрует свое сообщение открытым ключом абонента В:

Абонент расшифровывает это сообщение своим секретным ключом:

Следовательно m2 = m =3.

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

- если известно разложение rB (rA) на простые сомножители;

- если известен модуль сравнения (rA) ((rB)).

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

Предположим, что у нас имеется банкир B и несколько вкладчиков W1, W2, W3, … Банкир и каждый из вкладчиков независимо друг от друга выбирают по два больших простых числа и держат их в секрете. Пусть числа P и Q – числа, выбранные банкиром, а pn и qn – числа, выбранные вкладчиком Wn. Далее каждый из них вычисляет произведение этих чисел: R=PQ, rn=pnqn, (n=1,2,3,...), а также функцию Эйлера от этого произведения (R), (rn).

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

Вкладчик Wn: sn, 0 sn (rn), (sn, (rn)) = После этого публикуется всем доступная телефонная книга:

Далее каждый находит свои секретные ключи из условий (T – секретный ключ банкира, tn, n=1,2,3,.. – секретные ключи вкладчиков):

B: ST1(mod (R)), 0T (R) Wn: sntn1((mod (rn)), 0tn (rn) n=1,2,3,… Предположим, что вкладчик W1 собирается дать распоряжение m своему банкиру, и пусть выполняется условие 0r1R. Данное неравенство определяет дальнейшую схему вычислений.

Будем считать, что mr1 и (m, r1)=1.

Вкладчик W1 шифрует распоряжение m сначала своим секретным ключом m1mt1 (mod r1), 0m1r1, а затем открытым ключом банкира m2m1S (mod R), 0m2R и отсылает зашифрованное сообщение банкиру.

Банкир, получив секретное сообщение m2, расшифровывает его, пользуясь сначала своим секретным ключом T m3m2T (mod R), 0m3R, а затем открытым ключом вкладчика m4m3s1 (mod r1), 0m4r1· и получает m4=m.

В том случае, если неравенство 0r1R не выполняется, а выполняется неравенство r1R, последовательность процедур меняется.

1. Вкладчик сначала шифрует сообщение открытым ключом банкира, затем своим секретным ключом.

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

Пусть банкир выбрал числа 7 и 13, а вкладчик – 11 и 23.

R=7·13=91, (R)= r1=11·23=253, (r1)= Пусть банкир выбрал случайное число S=5, а вкладчик – число s1=31.

Далее каждый вычисляет свой секретный ключ.

Банкир B: T·51 (mod 72), отсюда T=29.

Вкладчик W1: t1·31 1(mod 220), отсюда t1=71.

Телефонная книга имеет вид:

Пусть вкладчик дает поручение m=41 своему банкиру и замечая, что Rr1, шифрует его сначала открытым ключом банкира, а затем своим секретным ключом:

m1415 (mod 91), отсюда m1=6, m2671 (mod 253), отсюда m2=94.

Банкир, получив сообщение m2, расшифровывает его сначала открытым ключом вкладчика, а затем своим секретным ключом:

m39431(mod 253), отсюда m3=6, m4629(mod 91), отсюда m4=41=m.

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

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

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

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

Такой датчик генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений a и c. Значение m обычно устанавливают равным 2n или 2n-1, где n – длина машинного слова в битах. Датчик имеет максимальный период M до того, как генерируемая последовательность начнет повторяться при определенных значениях констант a и c. Показано, что линейный конгруэнтный датчик имеет максимальный период М, если с – нечетное и a 1(mod 4).

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

r0:=a0r1 a1r2 … ak-2rk- Гi:=rk- Здесь r0, r1...rk-1 – k однобитовых регистров, a0, a1,…ak-1 – коэффициенты неприводимого двоичного полинома степени k-1, Гi – i-ое значение выходной гаммы.

Период М-последовательности равен 2k –1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k (табл. 2).

Объемы ансамблей М-последовательностей Очевидно, что такие объемы неприемлемы. Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М-последовательностей. Объем ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих последовательностей. Так, при k=10 объем составляет 388000.

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

1) сгенерировать случайное число и проверить, является ли оно простым или нет;

2) с помощью специальных алгоритмов сразу построить случайное простое число.

Наиболее простым в реализации является первый подход. Здесь самым очевидным способом проверки простоты числа N является перебор всех простых чисел в интервале 1k N с проверкой на делимость. Однако если требуется очень большое число для обеспечения высокой криптостойкости системы, данный алгоритм бесполезен из-за высокой вычислительной сложности.

В настоящее время известно большое число более эффективных способов проверки больших чисел на простоту. Одним из таких способов является тест Рабина. Он основан на малой теореме Ферма: aN-1 1(mod N) для любого простого N и целого aN.

Пусть требуется найти вычет ad(mod N). Представим d в виде двоичного числа d=d0d1…dr (d0 – старший двоичный разряд). Положим a0=a и по реккурентной формуле найдем ar, которое и будет ничем иным, как искомым вычетом.

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

Пусть имеется число N=2S·t + 1, где t – нечетно. Требуется установить, простое оно или составное. Тест Рабина заключается в следующем.

Выбирается случайное число из интервала 1aN и проверяются два условия:

1) N не делится на a;

2) at 1(mod N).

Если оба условия выполняются, то вероятность того, что число N окажется составным, равна 1/4. Если провести не один, а m аналогичных тестов, то можно установить простоту числа N c вероятностью 1- 4-m.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Л.Дж. Хоффман. Современные методы защиты информации / Л.Дж.

Хоффман. М.., 2. Б.Анин. Защита компьютерной информации / Б.Анин. С-Пб.., 3. М.Левин. Криптография / М.Левин. М.., 4. С.Л. Баричев. Основы современной криптографии / С.Л. Баричев, В.В.

Гончаров, Р.Е. Серов. М.., 5. В.И. Нечаев. Элементы криптографии / В.И. Нечаев.Основы теории защиты информации. М.., 6. А.В. Домашев. Программирование алгоритмов защиты информации / А.В. Домашев, В.О. Попов, Д.И. Правиков, И.В. Прокофьев, А.Ю. Щербаков. М.., 7. Д.Кук. Компьютерная математика / Д.Кук, Г.Бейз.М.., 8. В.Н. Сачков. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.., 9. И.М. Виноградов. Основы теории чисел / И.М. Виноградов. М.., Учебное текстовое электронное издание Кибардин Алексей Владимирович

МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ

Компьютерная верстка А. В. Кибардина Рекомендовано РИС ГОУ ВПО УГТУ-УПИ Разрешен к публикации 03.06. Формат 60х90 1/8 Объем 2 уч.изд.л.

620002, Екатеринбург, ул.Мира,

 
Похожие работы:

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ СФУ УТВЕРЖДАЮ Заведующий кафедрой Н. В. Соснин _2007 г. Кафедра Инженерная и компьютерная графика ДИПЛОМНАЯ РАБОТА СОЗДАНИЕ ЭЛЕКТРОННОГО УЧЕБНО-МЕТОДИЧЕСКОГО ПОСОБИЯ ПО ДИСЦИПЛИНЕ WEB - ДИЗАЙН В РАМКАХ НАПРАВЛЕНИЯ ЭЛЕКТРОННОЙ ПЕДАГОГИКИ Пояснительная записка Руководитель проекта / А. А. Воронин / Разработал...»

«РУКОВОДЯЩИЙ ДОКУМЕНТ ОТРАСЛИ СРЕДСТВА ИЗМЕРЕНИЙ ЭЛЕКТРОСВЯЗИ Методические указания по поверке сетевых анализаторов типа ANT-20 РД 45.1 01-99. 1 Область применения Настоящий руководящий документ отрасли устанавливает порядок поверки сетевых анализаторов типа ANT-20 Требования руководящего документа обязательны для выполнения специалистами метрологической службы отрасли, занимающимися поверкой данного типа средств измерений Руководящий документ отрасли разработан с учетом положений РД 50-660, ОСТ...»

«Министерство образования и науки Российской Федерации ФГАОУ ВПО УрФУ имени первого Президента России Б.Н.Ельцина В.И. Лихтенштейн, В.В. Конашков ОПРЕДЕЛЕНИЕ СВОЙСТВ НЕРВНОЙ СИСТЕМЫ ПО ПСИХОМОТОРНЫМ ПОКАЗАТЕЛЯМ Учебное электронное текстовое издание Издание второе, стереотипное Подготовлено кафедрой Безопасность жизнедеятельности Научный редактор: доц., канд. техн. наук А.А. Волкова Методические указания к деловой игре № П-8 по курсу Безопасность жизнедеятельности, Психология безопасности труда...»

«8 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Новокузнецкий институт (филиал) Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Кемеровский государственный университет юридический факультет Учебно-методический комплекс дисциплины (модуля) Правоведение_ (Наименование дисциплины (модуля) Направление подготовки _280700.62 Техносферная безопасность Профили подготовки Безопасность технологических процессов и производств Квалификация...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра охраны труда М.Н. Гамрекели МЕТОДЫ ОЧИСТКИ ВОДЫ Методические указания по выполнению лабораторной работы по курсу Безопасность жизнедеятельности для всех специальностей и направлений Екатеринбург 2008 Печатается по рекомендации методической комиссии МТД. Протокол № 3 от 5 декабря 2008 г. Рецензент ст. преп. И.Э. Ольховка. Редактор Е.Л. Михайлова Оператор А.А. Сидорова Подписано в печать 29.12.08...»

«База нормативной документации: www.complexdoc.ru ГОСГОРТЕХНАДЗОР РОССИИ НТЦ ПРОМЫШЛЕННАЯ БЕЗОПАСНОСТЬ СЕРИЯ 08 НОРМАТИВНЫЕ ДОКУМЕНТЫ ПО БЕЗОПАСНОСТИ, НАДЗОРНОЙ И РАЗРЕШИТЕЛЬНОЙ ДЕЯТЕЛЬНОСТИ В НЕФТЯНОЙ И ГАЗОВОЙ ПРОМЫШЛЕННОСТИ ВЫПУСК 1 ПРОМЫШЛЕННАЯ БЕЗОПАСНОСТЬ НА ГАЗОПЕРЕРАБАТЫВАЮЩИХ ПРОИЗВОДСТВАХ СБОРНИК ДОКУМЕНТОВ ИНСТРУКЦИЯ ПО ТЕХНИЧЕСКОМУ ДИАГНОСТИРОВАНИЮ СОСТОЯНИЯ ПЕРЕДВИЖНЫХ УСТАНОВОК ДЛЯ РЕМОНТА СКВАЖИН РД...»

«Министерство образования и науки РФ Федеральное агентство по образованию ГОУ ВПО Алтайский государственный университет Факультет психологии и философии Кафедра общей и прикладной психологии АКТУАЛЬНЫЕ ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ПСИХОЛОГИИ Программа и методические рекомендации Направление подготовки: 030300.68 Психология Магистерская программа Психология личности Барнаул - 2010 Учебный курс Актуальные проблемы теоретической и прикладной психологии предназначен для магистрантов 1 года...»

«ПРИОРИТЕТНЫЙ НАЦИОНАЛЬНЫЙ ПРОЕКТ ОБРАЗОВАНИЕ РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ А.А. ВАРФОЛОМЕЕВ ОСНОВЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ Учебное пособие Москва 2008 Инновационная образовательная программа Российского университета дружбы народов Создание комплекса инновационных образовательных программ и формирование инновационной образовательной среды, позволяющих эффективно реализовывать государственные интересы РФ через систему экспорта образовательных услуг Экспертное заключение – кандидат...»

«Министерство образования и наук Красноярского края краевое государственное бюджетное образовательное учреждение среднего профессионального образования (среднее специальное учебное заведение) Красноярский аграрный техникум Методические указания и контрольные вопросы по дисциплине История для студентов I курса заочного отделения Разработал преподаватель: А. А. Тонких Красноярск 2011 г. Содержание дисциплины. Раздел 1. Послевоенное мирное урегулирование. Начало холодной войны. Тема.1.1....»

«Министерство образования и науки Российской Федерации Владивостокский государственный университет экономики и сервиса _ МАТЕРИАЛОВЕДЕНИЕ Учебная программа курса по специальности 19070265 Организация и безопасность движения Владивосток Издательство ВГУЭС 2007 1 ББК 34 Учебная программа по дисциплине Материаловедение разработана в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования Российской Федерации. Рекомендуется для студентов...»

«Кафедра европейского права Московского государственного института международных отношений (Университета) МИД России М.М. Бирюков ЕВРОПЕЙСКОЕ ПРАВО: ДО И ПОСЛЕ ЛИССАБОНСКОГО ДОГОВОРА Учебное пособие 2013 УДК 341 ББК 67.412.1 Б 64 Рецензенты: доктор юридических наук, профессор, заслуженный деятель науки РФ С.В. Черниченко; доктор юридических наук, профессор В.М. Шумилов Бирюков М.М. Б 64 Европейское право: до и после Лиссабонского договора: Учебное пособие. – М.: Статут, 2013. – 240 с. ISBN...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА И ПРОДОВОЛЬСТВИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Кубанский государственный аграрный университет Г.А. Кравченко ЦИТОЛОГИЯ, ГИСТОЛОГИЯ, ЭМБРИОЛОГИЯ (часть 1) Методические указания для аудиторной и внеаудиторной самостоятельной работы студентов Краснодар 2010 Г.А.Кравченко Цитология и Общая гистология. Методические указания. Краснодар, КГАУ, 2010 г Печатается по решению методической комиссии факультета ветеринарной медицины. Протокол № Предназначено методическое указание для...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра Безопасность жизнедеятельности УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Безопасность в чрезвычайных ситуациях Основной образовательной программы по направлению подготовки 280700.62 Техносферная безопасность (для набора 2013 – 2017 г.) Благовещенск 2013 УМКД разработан кандидатом...»

«1 ГКУ Курганская областная юношеская библиотека Методические рекомендации Безопасный интернет Курган, 2013 2 Проблема обеспечения информационной безопасности молодого поколения в информационных сетях становится все более актуальной в связи с существенным возрастанием численности молодых пользователей. В современных условиях развития общества компьютер стал для юных граждан другом, помощником, воспитателем и даже учителем. Между тем существует ряд аспектов при работе с компьютером, в частности,...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра безопасности жизнедеятельности УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ ПРОМЫШЛЕННАЯ БЕЗОПАСНОСТЬ Основной образовательной программы по специальности: 280101.65 Безопасность жизнедеятельности в техносфере Благовещенск 2012 Печатается по решению редакционно-издательского совета...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Региональный учебно-научный центр по проблемам информационной безопасности Восточной Сибири и Дальнего Востока в системе высшей школы Кафедра радиоэлектроники и защиты информации ОБНАРУЖЕНИЕ ПОЛУПРОВОДНИКОВЫХ ЭЛЕМЕНТОВ С ПОМОЩЬЮ НЕЛИНЕЙНОГО ЛОКАТОРА Руководство к лабораторной работе по курсу Инженерно-технические средства защиты информации для студентов специальностей 075300,...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра охраны труда Г.В. Чумарный МЕТОДИЧЕСКИЕ УКАЗАНИЯ к сбору материалов и составлению раздела Безопасность проекта в дипломных проектах (работах) для студентов ИЭФ специальностей 240502, 240406, 280202, 280201 направления 280200 Защита окружающей среды Екатеринбург 2008 Печатается по рекомендации методической комиссии инженерноэкологического факультета. Протокол № 2 от 23.10.07. Рецензент В.Е....»

«БИБЛИОГРАФИЧЕСКИЙ УКАЗАТЕЛЬ КНИГ, ПОСТУПИВШИХ В БИБЛИОТЕКУ Апрель 2010 МЕТОДИКИ ФГУ ВНИИЗЖ 1. 72-09 Методика выявления антител к вирусу инфекционного ринотрахеита крупного рогатого скота в реакции нейтрализации микрометодом / А.А. Нестеров, В.А. Мищенко, Д.К. Павлов, Т.И. Корпусова; ФГУ ВНИИЗЖ. - Владимир, 2010. - 22 с. 2. 93-09 Методические рекомендации по оценке безопасности на свиноводческих предприятиях в Российской Федерации / М.А. Титов, А.К. Караулов, А.А. Шевцов [и др.]; ФГУ ВНИИЗЖ. -...»

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

«КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙУНИВЕРСИТЕТ ИНСТИТУТ ФИЗИЧЕСКОЙ КУЛЬТУРЫ, СПОРТА И ВОССТАНОВИТЕЛЬНОЙ МЕДИЦИНЫ ЛАБОРАТОРНЫЕ И ПРАКТИЧЕСКИЕ ЗАНЯТИЯ ПО КУРСУ БЕЗОПАСНОСТЬ ЖИЗНЕДЕЯТЕЛЬНОСТИ Учебно-методическое пособие Казань 2012 Печатается по решению кафедры безопасности жизнедеятельности Института физической культуры, спорта и восстановительной медицины Казанского (Приволжского) федерального университета Авторы-составители: Ситдикова А.А. – кандидат биологических наук, старший преподаватель Святова Н.В. –...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.