WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» ...»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ»

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

И КРИПТОЗАЩИТА

Учебное пособие

Составители:

Б. Н. Воронков, А. С. Щеголеватых Издательско-полиграфический центр Воронежского государственного университета Утверждено научно-методическим советом факультета прикладной математики, информатики и механики 27 февраля 2008 г., протокол № 6 Рецензент канд. физ.-мат. наук, доц. К. П. Лазарев Учебное пособие подготовлено на кафедре технической кибернетики и автоматического регулирования факультета прикладной математики, информатики и механики Воронежского государственного университета.

Рекомендуется для студентов 4-го курса дневного отделения и 4-го курса вечернего отделения.

Для специальности 010501 — Прикладная математика и информатика СОДЕРЖАНИЕ Предисловие…………………………………………....……….. 5

1. Основные понятия и определения………………………………..

2. Элементы теории чисел и модулярная арифметика…………….. 10

2.1. Малая теорема Ферма. Теорема Эйлера …………………... 15

2.2. Квадратичные вычеты и закон взаимности.……………….. 21



2.3. Вычисление обратных по модулю величин………………... 24

2.4. Сравнение арифметических операций по их трудоемкости...... 26

2.5. Нахождение простых чисел…………………………………. 32

3. Формальное определение криптосистемы……………………..... 35

4. Криптосистема Эль Гамаля……………………………………..... 36

5. Криптосистема RSA (R. Rivest, A. Shamir, L. Adleman)……...… 37

6. Методы распределения криптографических ключей…….……... 43

6.1. Распределение секретных ключей с обеспечением конфиденциальности и аутентификации…………………...….... 48

7. Криптография с использованием эллиптических кривых…….... 52

7.1. Аналог обмена ключами по схеме Диффи-Хеллмана ……... 59

7.2. Протокол обмена ключами по схеме Месси-Омуры…..…..

7.3. Протокол распределения ключей Менезеса-Кью-Ванстона (MQV-протокол)…………………… 61

7.4. Протокол Эль Гамаля для криптосистемы с использованием эллиптических кривых…

7.5. Обоснование протоколов с использованием модулярной арифметики……………………………………......... 63

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

8.1. Стандарт DSS, алгоритм DSA………………………………. 65

8.2. Обобщенная схема цифровой подписи Эль Гамаля……….. 67

8.3. Схема цифровой подписи Эль Гамаля с возвратом сообщения……………………………………………………...………. 68

8.4. Цифровая подпись с использованием точек эллиптической кривой………………….……………………...... 69

9. Модели атаки нарушителя………………………………………... 70

10. Модель несанкционированной подмены передаваемой информации…………………...……………………………………… 71 Библиография…………………………………………………… 87

–  –  –

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

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

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

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

1. Основные понятия и определения

Источники основных понятий и определений :

ГОСТ Р 50922-96 Защита информации: термины и определения. Госстандарт России.

ГОСТ Р 51583-00 Защита информации. Порядок создания автоматизированных систем в защищенном исполнении. Общие положения. Госстандарт России.

ГОСТ Р 51624-00 Защита информации. Автоматизированные системы в защищенном исполнении. Общие требования. Госстандарт России.

ОСТ 45.127-99. Система обеспечения информационной безопасности Взаимоувязанной сети связи Российской Федерации. Термины и определения.

Информация — сведения о лицах, предметах, фактах, событиях, явлениях и процессах независимо от формы их представления.

Сообщение — информация, представленная в определенной форме.

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

Дискретные сообщения — сообщения, вырабатываемые дискретными источниками, среди которых выделяются источники цифровой информации.

Дискретная информация — информация, зафиксированная в дискретном сообщении.

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

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

Канал связи — физическая среда между источником и получателем информации совместно с совокупностью технических устройств и субъектов, обеспечивающих передачу сообщений от источника информации к получателю.

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

Информационные ресурсы — документы, массивы документов (архивы, фонды), программы для ЭВМ, базы данных, существующие отдельно или в составе информационных систем.

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

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

Закрытая информация содержит государственную, коммерческую или иную тайну.

Секретная информация содержит государственную тайну.

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

Защищаемая информация — информация, являющаяся предметом собственности и подлежащая защите в соответствии с требованиями правовых документов или требованиями, устанавливаемыми собственниками информации.

Утечка информации — неконтролируемое распространение защищаемой информации.

Утечки трех видов:

а) разглашение,

б) несанкционированный доступ к информации,

в) разведка.

Уничтожение информации — утрата информации при невозможности ее восстановления.

Блокировка информации — невозможность ее использования при сохранности.

Модификация информации — изменение ее содержания по сравнению с первоначальной.

Цена информации — полезность информации для участников информационного рынка.

Ценность информации — полезность информации для ее владельца (пользователя).

Угрозы информации:

а) нарушение конфиденциальности — потеря ценности информации при ее раскрытии;





б) нарушение целостности — потеря ценности информации при ее модификации или уничтожении;

в) нарушение доступности — потеря ценности информации при невозможности ее оперативного использования;

г) нарушение устойчивости к ошибкам — потеря ценности информации при сбоях в информационных системах.

Эффективность защиты информации — мера соответствия уровня информационной безопасности требованиям при заданном ресурсе на ее защиту.

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

Структурная схема системы связи представлена на рис. 1.

Канал (среда) Рис. 1. Общая структурная схема системы связи: 1 — источник информации;

2 — передатчик; 3 — приемник; 4 — адресат (получатель); 5 — источник шума и помех.

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

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

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

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

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

Ключ — информация, необходимая для беспрепятственного шифрования или расшифрования текстов.

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

Дешифрование — нахождение ключа или открытого текста на основе шифрованного текста.

Расшифрование — нахождение открытого текста на основе известного ключа и шифра.

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

MIPS (Million Instructions Per Second) — миллион инструкций в секунду.

Криптограмма — шифрованный текст (ШТ).

Основная идея шифрования — скрытие смысла передаваемого сообщения.

Выделяют два класса криптосистем:

симметричные (одноключевые) криптосистемы;

асимметричные (двухключевые) криптосистемы.

Методы симметричного шифрования: 1. Перестановки. 2. Подстановки.

3. Гаммирование. 4. Аналитическое преобразование шифруемых данных.

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

Рис. 2. Структурная схема передачи шифрованных сообщений: 1 — отправитель; 2 — устройство шифрования; 3 — устройство расшифрования; 4 — получатель;

5 — перехватчик (злоумышленник); 6 –– канал связи; 7 –– генератор ключей.

Алфавит — конечное множество используемых для шифрования знаков.

Z33 — 32-буквенный русский алфавит и пробел.

Z256 — расширенный ASCII (American Standard Code for Information Interchange – Американский стандарт кодирования для обмена информацией (KOИ8)).

Z2 — {0;1}.

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

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

2. Элементы теории чисел и модулярная арифметика [1; 7; 10]

–  –  –

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

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

11) к каждой части сравнения можно прибавить любое число, кратное модулю;

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

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

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

Ненулевые элементы кольца вычетов Zm тогда и только тогда образуют группу относительно операции умножения по модулю m, когда m — простое число. Следовательно, для простого числа р кольцо Zp является полем. Это конечное поле принято обозначать GF ( p ). Его элементы {0, 1,…, (p – 1)} — это всевозможные остатки от деления целых чисел на р, а алгебраические действия с ними — сложение и умножение по модулю р.

Характеристикой поля называется такое наименьшее положительное число k, для которого k a 0(mod p ), а GP ( p ). Если такого элемента не существует, то считается, что характеристика поля равна нулю.

Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом.

Для конечного поля справедлива малая теорема П. Ферма.

2.1. Малая теорема Ферма. Теорема Эйлера

Малая теорема Ферма. Пусть р — простое число, а — некоторое цеp p-1 лое число. Тогда a a (mod p). Если p не делит a, тогда a 1 (mod p).

Доказательство. Предположим сначала, что p не делит a, так что (а, р) = 1, и рассмотрим р – 1 чисел а, 2а, 3а,..., (р – 1)а. Ни одно из них не кратно p ( p | ja означает, что p | j, так как р — простое число и p не делит a). Также не найдётся двух чисел, которые конгруэнтны (сравнимы) по модулю р, так как ja ka (mod p) означает j k (mod p). Следовательно, по модулю р эти р – 1 чисел различны и не равны нулю. Итак, числа 1, 2, 3,..., р – 1 должны располагаться в соответствующем порядке. Перемножая их, мы получим a p 1 1 2 3...( p 1) = a 2a 3a...( p 1)a (1 2 3...( p 1))(mod p).

Числа 2, 3,..., р – 1 все являются взаимно простыми с р и могут быть последовательно сокращены один за другим из этого сравнения. Отp–1 p сюда следует, что a 1 (mod p). Умножение на а даёт a a (mod p).

Если, с другой стороны, р | a, тогда р и а оба 0 (mod p), а из этоp го следует, что a a (mod p).

Обобщением малой теоремы Ферма является теорема Эйлера для составного модуля.

Теорема Эйлера. Пусть n 0 и предположим, что (a, n) = 1. Тогда (n) a 1 (mod n), где (n) — фи-функция Эйлера.

Доказательство. Пусть r1, r2,..., rk (k = (n) ) будут целыми числами Z 1, n и взаимно простыми с n. Рассмотрим a r1, a r2,..., a rk.

Из представленных членов не найдётся двух, которые сравнимы по mod n (a ri a rj, что означает ri rj (mod n), так как (a, n) = 1) и все они взаимно простые ((a, n) = ( ri, n) = 1, что означает (a ri, n) = 1). Следовательно, среди них существуют (n) таких, что их наименьшие положительные вычеты по модулю n должны быть точно числами r1, r2,..., rk в соответствующем порядке. Отсюда r1 r2... rk ( ar1 a r2... a rk )(mod n), так что, сокращая ri, так как они взаимно простые с n, мы получим искоk мое сравнение 1 a (mod n).

Функция (n) является мультипликативной, т.е. если (m, n) = 1, тогда (mn) = ( m) ( n). Принято, что (1) = 1 и ( 2) = 1.

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

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

-метод факторизации Полларда. Пусть f(x) = x + 1 и запишем f2(x) = f(f(x)), f3(x) = f(f2(x)) и т. д. Пусть ak =f k(1). (Следовательно, а1 = 2, а2 = 5, аk+1 = ak 2 + 1). Конечно, вместо этого f можно использовать другие полиномы. Предположим, что мы хотим представить N в виде сомножителей, т.е. найти простое число р (возможно наименьшее простое число), для которого p | N. Конечно, последовательность {ak}, взятая по модулю р или по модулю N в конце концов будет повторяться, и ожидается, что это повторение будет происходить быстрее по модулю p, чем по модулю N. (Действительно, повторение будет реальной возможностью, если количество членов превзойдёт p ). Следовательно, мы надеемся, что ai aj (mod p) для j i и j не достаточно большое. Заметим, что тогда at aj-i+t (mod p) для всех t i. Конечно, мы не можем решить задачу нахождения ai mod p, пока мы не знаем, что собой представляет р, но мы можем решить задачу нахождения ai по модулю N, мы просто запишем p | ((aj – ai) mod N, N).

(Чтобы не связываться с aj – ai, требуется, чтобы эта разность быстро становилась очень большой).

Проделаем простое усовершенствование: так как i j, то существует целое число t, для которого i t j и (j - i) | t. (Это становится понятным, если задать вопрос, почему должно существовать целое число k, для которого i /(j – i) k j /(j – i), и тогда используйте t = k(j – i)). Более того, at = ak(i-i ) a(k+1)(j-1) a(k+2)(j-1)... a2k(j-1) a2t (mod p), т.е. вместо контроля i и j мы должны рассмотреть at и a2t для t = 1, 2, 3,...

Таким образом, метод заключается в следующем:

Зададим x = a1 = 2, y = a2 = 5.

Заменим х на f (x), y на f (f (y)); таким образом, теперь x = a2, y = a4. Найдём (x – y, N).

Повторим: теперь х = a3, у = a6. Найдём (x – y, N).

Продолжаем до тех пор, пока (x – y, N) не станет равным 1 или N.

Конечно, х и у сокращаются по модулю N на каждой стадии, используя x:= (x – N) · INT(x / N), и т. д. Заметим, что вышеприведённый метод значительно лучше, чем сохранение ai в массиве, даже учитывая, что ai вычисляется дважды. При этом удаётся избежать проблемы, связанной с большими массивами чисел повышенной точности.

(р – 1) метод факторизации Полларда. Одной из версий этого метода будет следующая. Предположим, что р — простое число, а k такое, что (р – 1) | k! Это означает, что все простые сомножители числа (р – 1) будут меньше k. Теорема Ферма утверждает, что 2k! 1 (mod p).

Предположим, что мы хотим разложить на множители данное целое число N. Возьмём малое целое число, скажем, 2 и вычислим последовательно 21, 22, 26, 224,..., 2k! (все по модулю N), где k является разумно большим (но не слишком большим!). Если р — простой множитель N, тогда, естественно, р является множителем числа (2 k! – 1N, N) и НОД будет скорее р, чем N. (Обозначение хN принято для наименьшего положительного вычета x по модулю N). Этот метод можно проверить на числах, которые являются произведением двух простых чисел. Заметим, что для успеха вычислений мы должны потребовать, чтобы все простые множители искомого фактора р были бы k.

Китайская теорема об остатках. Пусть m1, m2,..., mr — положительные числа, причем, каждая пара взаимно простая: (mi, mj) = 1 для i j. Тогда система сравнений x a1 (mod m1), x a2 (mod m2),..., x aк (mod mк) имеет единственное решение — сравнение по модулю произведения m1 m2... mr.

Доказательство. Существование решения может быть доказано индукцией или следующим образом. Пусть ki для i = 1,..., r будет произведением всех положительных чисел m за исключением mi. Конечно, (ki, mi) = 1, так что ki имеет обратное число ni по модулю mi. Тогда x = a1 k1 n1 + a2 k2 n2 +... + ar kr nr есть искомое решение. Например, m1 является сомножителем n2,..., nr и k1 n1 1 (mod m1), Отсюда x a1 (mod m1). Таким же образом доказываются другие сравнения.

Порядком числа а по модулю n, если (a, n) = 1, называется наиk меньшее целое k 0 такое, что a 1 (mod n). Это записывается как k = ordn a и произносится, что а имеет порядок k по модулю n. Естественно, что ordn a (n). Заметим, что если (a, n) 1 и k 0, то невозможно k для a быть сравнимым с 1 (mod n). Если а имеет порядок k mod n, тогда в некоторых книгах используют выражение “а является показателем k по модулю n”.

k Предположим (a, n) = 1. Тогда a 1 (mod n), если ordn a | k. Отсюда получим, что степень а, которая сравнима с 1, не только ordn a, но

–  –  –

2.3. Вычисление обратных по модулю величин [2; 4; 10] Определение. Целое число а является обратным числу b по модулю n, если выполняется сравнение: ab 1 (mod n).

Теорема. Для целых а и n существует b такое, что ab 1 (mod n), если и только если (a, n) = 1. Когда b существует, оно также будет взаимно простым с b и единственным по модулю n. Последнее утверждение означает: если ab 1 (mod n), тогда b b (mod n).

Доказательство. Если ab 1(mod n), тогда ab = 1 + k n, так что некоторый общий множитель а и n должен делить 1, что даёт (a, n) = 1 (аналогично (b, m) = 1). Обратно, если (а, n) = 1, тогда, используя алгоритм Евклида, найдём такие целые числа b и k, что ab + n k = 1. Для этого b ab 1 (mod n).

Для нахождения числа а необходимо решить сравнение a х 1 (mod n).

Это эквивалентно нахождению таких значений целых чисел х и k, что а х = n k + 1.

Существует три основных способа нахождения числа а, обратного числу b по модулю n:

–  –  –

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

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

Широко применяемые для выполнения арифметических операций способы на основе позиционной системы счисления (ПСС) изучены достаточно полно.

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

Информация в виде позиционного двоичного кода представляет собой набор из k разрядов для представления любого целого числа х между 0 k и 2 1, а именно, k d j 2 j 1, x= (2.1) j =1 dj где двоичные коэффициенты являются разрядами числа j 1 x = (d k d k 1...d 2 d1 ) по основанию 2. Веса 2 в этом представлении являются целыми степенями по этому числовому основанию (j = 1, 2, …, k).

Рассмотрим теперь использование ряда весов w1, w2,..., wn для представления n—разрядного числа x = (ck ck 1...c2 c1 ) в том же виде, а именно:

–  –  –

j показывая, что количество 2w, добавленное от переполнения в цифровой позиции j, должно теперь перемещено не только слева от позиции (j + 1), но также справа (если эта позиция снимается при представлении) от позиции цифры (j – s).

Двойной перенос серьезно усложняет схему параллельного сумматора, а двойное направление при преобразовании из параллельной записи в простую последовательную форму делает сумматор практически неосуществимым. Более того, результат такого суммирования по Фибоначчи необходимо скорректировать для очистки слева всех единичных строк длиннее, чем s – 1. Следовательно, двоичная арифметика, как следует из описания, обладает предпочтением.

Существует ли процедура преобразования кодирования или декодирования, где кодированные разряды могут генерироваться синхронно по времени с приемом цифр от источника последовательного кода? Исследования двоичных весов, эквивалентных весам Фибоначчи и весовым эквивалентам Фибоначчи по степеням 2, показывают, что ни наиболее важные, ни наименее важные разряды результирующего слова не могут быть известны до получения закодированного слова и соответствующим образом преобразованного. Таким образом, схема, которая выполняет преобразование, должна иметь возможность осуществлять сдвиг влево и вправо внутри длины полученного слова. Упрощение кодера к чисто последовательной и непрерывной форме операций (как в обычном двоичном сумматоре) является, следовательно, в своей основе неосуществимым. Обе процедуры преобразования кодов, описанные ранее, требуют, чтобы двоичное весовое представление n весов Фибоначчи было бы доступно в течение общепринятого процесса. Таким образом, эти веса должны быть или сохранены в памяти с произвольной выборкой, или сгенерированы с помощью локальных схем. Рекуррентные соотношения (2.3) и (2.5) показывают, что каждый из этих весов может быть просто сгенерирован из предыдущих значений, требующих хранения только s последовательных весов, не зависимо от того, насколько большим может быть n.

Считаем соотношение между параметрами k и n, достаточными для ( m +1) k выполнения условия 2 N 3 ( m, n) = wn +1 ; т.е. следует выбрать n таким, что wn 2k wn +1.

За исключением достаточно малых значений m = s – 1, даже очень длинные коды требуют не более n – k избыточных разрядов.

В криптологии часто приходится выполнять операции с многозначными числами. Обычный прием умножения двух 2n-значных чисел легко сводится к четырем умножениям n-значных чисел. Метод А.А. Карацубы позволяет обойтись тремя умножениями n-значных чисел. Если записать 2n-значное число в виде Аn + 10n Bn, n n то легко установить тождество (Аn + 10 Bn )(Cn + 10 Dn) = =А n Cn (10n + 1) + (Dn – Cn)( Аn – Bn)10n + Bn Dn(102n +10n ), которое доказывает утверждение.

В дальнейшем этот метод был усовершенствован.

Алгоритм Хэда (опубликованный в 1980 г.) представляет собой более тонкий путь выполнения умножения без представления чисел, больших, чем 2m. Для повышенной точности это даёт возможность уверенно оперировать с числами, такими как 10. Алгоритм Хэда может быть включён в виде подпрограммы в степенной алгоритм.

Пусть нужно умножить х и у по модулю m, где 0 х m, 0 y m.

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

Пусть m 2, T = m +, t = T – m. Тогда –T t T и T 2m.

Доказательство. Из определения T мы имеем m T m+ (2.6) и, возводя эти неравенства в квадрат, получим T2 m + m+ m+.

m– (2.7) T2 + T, Сложение левых частей неравенств (2.6) и (2.7) даёт m – а так как правая часть представляет собой целое число, мы получим Т2 + Т m, что является долей искомого результата.

Вторая часть получается, если сложить правую часть неравенства (2.7) с левой частью неравенства (2.6), умножив на (–1), мы получим T2 – T m + T2 – T m. Наконец, T2 2 m просто следует, что даёт из правой части выражения (2.7).

Пусть x = aT + b, где 0 b T. Тогда 0 а Т. Пусть y = c T + d, где 0 d T. Тогда 0 с Т.

Доказательство. Очевидно, что а 0. Если а T, тогда x = aT + +b aT (T + 1) T m. Это является противоречием. Другая половина доказывается аналогично.

1. Определим z (ad + bc) (mod m), где 0 z m. Тогда ad m, bc m и ху (act + zT + bd) (mod m).

2. Пусть ac = eT + f, где 0 f T. Тогда 0 е Т и xy ((et + +z)T + ft + bd) (mod m).

3. Пусть v (z + et) (mod m), 0 v m.

4. Пусть v = gT + h, где 0 h T. Тогда 0 g T и xy (hT + (f + + g)t + bd) (mod m).

Представленные результаты просто проверить в такой последовательности ( все сравнения по модулю m):

a, b, c, d, z, e, f; v; g; h; j (f + g) t, k j + bd; xy hT + k, включая числа размером не более 4m.

Для нахождения целых чисел в классах вычетов можно воспользоваться китайской теоремой об остатках В кольце вычетов по модулю определены такие операции как сложение, вычитание, умножение, поэтому их выполнение осуществляется в соответствии с законами модулярной арифметики. Например, операцию модулярного вычитания чисел и можно осуществить в соответствии с выражением ( – ) mod m = [ + (m – )]mod m, т.е. сводится к операции модулярного сложения.

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

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

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

–  –  –

Теорема Вильсона. Целое число р 1 является простым, если и только если (р –1)! – 1 (mod p).

Доказательство. Предположим, что р — простое число большее 2.

Мы должны умножить между собой все числа 1, 2,..., р – 1 и найти вычет по модулю р. Каждое из этих чисел х имеет обратное y по mod p, т.е., xy 1 (mod p). Далее мы должны все время сокращать y mod p, так что у станет одним из чисел 1, 2,..., р – 1. В этом случае имеем x = y x 1 (mod p) x ±1 (mod p), так как р – простое число. Другие числа разделены на пары, причем произведение каждой пары равно 1 mod p, ·· так что 1 2 3... (р – 1) –1 (mod p). Результат также верен и для р = 2!

С другой стороны, предположим,, что n — составное число, например, n = ab, где a 1 и b 1, а (n – 1)! –1 (mod n). Тогда получаем противоречие. Очевидно, что a | (n – 1)! для всех 1 a n. Но мы знаем, что a | n, так что их совпадение означает, что выражение a | (–1) является ложным.

Хотя теорема Вильсона в принципе даёт возможность тестировать на простоту, но для использования она достаточно малоэффективна, так как для этого требуется умножение на все числа 2, 3,.... р – 1 по модулю p.

Это получается медленнее, чем проверка р на принадлежность к простым числам путём пробного деления на простые числа p.

m Числа Мерсенна имеют вид M(m) = 2 – 1, где m — натуральное число, большее единицы.

Совершенным числом считается такое целое n 1, что сумма его делителей, включая 1, но исключая само число n, равно самому n.

Существует связь между совершенными числами и простыми числами Мерсенна.

Если известно разложение числа на простые множители, то можно указать все делители этого числа, а также найти их сумму, которую обозначим через (n), где n — само число. При этом для совершенных чисел справедлива формула (n) = 2n.

Прежде чем выявить связь между совершенными числами и простыми числами Мерсенна, полезно описать метод, позволяющий определить, m является ли число вида M(m) = 2 – 1 действительно простым.

Теорема. Пусть р будет нечётным простым числом, а q будет проq стым числом. Предположим, что q | (2 – 1). Тогда q имеет вид 1 + 2kp для целого числа k. Все делители 2р – 1, простые или составные, будут иметь такой же вид.

–  –  –

показать, что q = 1.

s+1 Предположим, что q 1, так что t = (2 – 1)q, Тогда q является собственным множителем t, a t имеет различные множители 1, q, t (и, возможно, другие), обеспечивая (t) 1 + q + t, С другой стороны, (t) = 2s+1q = (2s+1 – 1)q + q = t + q.

s+1 Это противоречие доказывает, что q = 1, обеспечивая t = 2 – 1, и (t) = 1 + t. Последнее уравнение показывает, что t — простое число, так s s+1 что n = 2 (2 – 1), где второй сомножитель является простым.

Таким образом, существует тесная связь между чётными совершенными числами и простыми числами Мерсенна. Значения m, при которых число становится простым, сами все являются простыми. Приведем несколько первых простых чисел Мерсенна при m = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127,521, 607, 1279, 2203, 2281, 3217, 4253,...

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

Числом Кармайкла называется составное число n, которое удовлеn-1 творяет сравнению b 1 (mod n) для всех b, являющихся взаимно простыми с n (в честь Р. Д. Кармайкла, который предложил их в 1912 г.).

Конечно, давая определение, мы не доказали, что такие числа существуют, но приведём пример. Пусть n = 561 = 3 · 11 · 17. Таким образом, (b, 561) = 1 означает, что (b, 3) = (b, 11) = (b, 17) = 1. Используя малую теорему Ферма, b2 1 (mod 3) предполагает, что b 560 = (b2)280 1 (mod 3);

b10 1 (mod 11) означает, что b560 = (b10)56 1 (mod 11);

b16 1 (mod 17) означает, что b560 = (b16)35 1 (mod 17).

Так как 3, 11 и 17 являются тремя различными простыми числами, то это означает, что b 1 (mod 561).

Теорема. Пусть n = q1 q2... qk, где qi — различные простые числа и k 2. Предположим, что для каждого i, (qi – 1) | (n – 1). Тогда n будет числом Кармайкла.

Заметим, что простые числа должны быть нечётными, так как, если q1 = 2, тогда n — чётное, а q2, будучи нечётным, не удовлетворяет условию (q2 – 1) | (n – 1).

<

–  –  –

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

–  –  –

по известному M.

Так как криптостойкость системы Эль Гамаля определяется сложностью решения задачи дискретного логарифмирования в совокупности Z p, то следует учесть, что в настоящее время эта задача неразрешима при p, содержащем примерно 300 десятичных цифр. Рекомендуется также, чтобы число ( p 1) содержало большой простой делитель.

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

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

5. Криптосистема RSA (R. Rivest, A. Shamir, L. Adleman)

Наиболее широкое признание и применение в современном мире получила схема шифрования с открытым ключом RSA, аббревиатура которого исходит от фамилий авторов Р. Л. Ривеста, А. Шамира и Л. М. Адлемана. Основой надёжности этого метода является огромная трудность факторизации очень больших целых чисел. Метод также требует использования очень больших простых чисел (150-значных и более), которые практически находятся вероятностными методами, подобными изложенным ранее.

Основы создания криптосистемы RSA, рассматриваемой далее, берут своё начало из экспоненциального шифрования [10]. Они были открыты С.

Полигом и М. Хэллманом [9;10]. Идея довольно проста. Выбирается простое число р и ключ кодирования е, который является взаимно простым с ( p ) = p 1. Блок открытого текста, который предполагается зашифровать, сначала преобразуется в числовую форму (один из методов осуществления этого приведён ниже), а потом разбивается на подблоки цифр, которые, если рассматривать их как обычные числа, будут р.

Предположим, например, что р = 37 781, а подблоки цифр сообщения в числовом виде выглядят как 8069 6578 8584 8332.

Чтобы зашифровать это послание, заменим каждое четырёхзначное число Mi (существующее «открытым текстом» в виде четырёхзначных чиe сел) на Ci Mi (mod p), 0 Ci p. Таким образом, выбирая е = 367 (которое является взаимно простым числом с р – 1 = 37 780 = 22 · 5 ·1889), зашифрованной формой будет (т. е. 8069 37 059 (mod p)).

Как может быть это послание расшифровано, т.е. возвращено к первоначальной цифровой форме и, далее, к обычному языку? Пусть d (ключ расшифрования) будет таким, что de 1 (mod( p – 1)). То есть d просто представляет собой инверсию е по модулю (p – 1), так как (е, р – 1) = 1, и которая может быть вычислена методами определения обратных по модулю величин. В представленном случае d = 3603. Теперь Cid = (Mie) d = Mied = (Mied-1)·Mi = Mi mod p согласно малой теореме Ферма, так как (p – 1) | (ed – 1). Таким образом, возводя каждое (пятизначное) зашифрованное число в степень d и приводя по mod p, мы раскроем первоначальное (четырёхзначное) число. То есть (37 0593603) mod p = 8069 и т. д.

Чтобы использовать этот метод для отправки секретных посланий между двумя людьми А и В, которые оба желают знать р (вся шифрация производится по модулю p), А необходимо выбрать шифровальный ключ е, в то время как В должен произвести соответствующую расшифровку ключом d. Конечно, В может выбрать другой шифровальный ключ е для отправки посланий А, так как А знает соответствующий ключ расшифровки d, для которого d e 1 (mod (p – 1)).

Раскрытие этого шифра достаточно сложно, даже если р известно и если соответствующие открытый текст M и зашифрованный текст С изe вестны, так что C M (mod p ). Проблема заключается в том, что не существует простого способа определения е из такого сравнения, когда р представляет большое простое число.

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

Сама идея достаточно проста. Если два абонента сети, которых обозначим А и В, соответственно, хотят установить скрытую связь, каждый выбирает два больших простых числа: pR, qR и pG, qG. Пусть nR = pR qR, nG = pG qG. Числа nR и nG могут быть известны окружающим, так как используемые простые числа достаточно большие. Каждый выбирает ключ шифрования: еR и еG, каждый из которых будет взаимно простым с ( nR ), (nG ), соответственно. (Заметим, что ( pq ) = ( p 1)(q 1), когда p и q являются простыми). Эти шифровальные ключи могут также быть известны окружающим. Каждый человек, знающий свои р, q и е, может просто рассчитать инверсию d для е по модулю (n). Но посторонний человек, знающий только n и е, имеет незначительный шанс вычислить d без действительного разложения на простые сомножители n, а А реально не в состоянии вычислить dG, а В не сможет определить dR.

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

Он также использует шифровальный ключ В еG (который, как все шифровальные ключи, общеизвестен), чтобы зашифровать каждый блок Р в соответствии с правилом шифрования EG:

ЕG ( Р) Р еG (mod nG ).

Заметим, что, выполнив это шифрование, А будет не в состоянии расшифровать его снова, так как он не знает dG.

Однако В будет находиться не в таком безнадёжном положении: зная оба dG и nG, он сможет расшифровать с помощью правила расшифрования:

DG (С ) С d G (mod nG ).

Таким образом, DG (ЕG(Р)) Р (mod nG) на основе тех же самых аргументов, какие были использованы в случае экспоненциального шифрования.

Конечно, когда В пожелает отправить послание R, он использует правило шифрования Е R ( Р) Р е R (mod nR ), dR а А расшифрует согласно правилу расшифровки DR (С ) С (mod nR ).

Снова DR (ЕR(Р)) Р (mod nR). Вспомните, что А знает ER, EG и DR, в то время, как В знает ER, EG и DG.

Важной частью написанного послания является подпись, чью индивидуальность подтверждает получатель тем, что сообщение действительно получено от персоны, которую затребовал отправитель. Удивительно, что возможно послать подпись, используя также открытый метод RSA шифрования. Предположим, что nR nG (конечно, оба А и В знают об этом) и то, что А желает послать подпись В, т. е. последовательность символов в конце послания, которую В должен сделать, чтобы раскрыть смысл послания, которое могло бы прийти только от А. Предположим, что в действительности подпись представляет собой один блок открытого текста Р. Тогда А зашифровывает его с помощью представления DR(P) в меньших блоках перед дальнейшим шифрованием его как S. В конце этого сообщения А тогда посылает подпись S.

Когда получатель В расшифрует конец послания, используя ключ расшифрования d G, получается настоящая тарабарщина, а именно:

DG (S) = DG (EG(DR(P))) = DR (P) (конечно, DR(P) является числом). Бессмыслица получится, когда В будет стремиться превратить эти числа в слова. Предполагая, что это является подписью, он для этого использует Е R, которое раскрывает В; когда оно переводится в слова, то приобретает смысл. Заметим, что только отправитель А знает DR, так что только он может послать специфическую тарабарщину DR в конце послания.

Доказательство корректности алгоритма RSA [5]

Определение. Пусть n = p q, где p и q — простые числа. Пусть X = Y = Z n –– множество открытых текстов, которое по объему совпадает с множеством шифрованных текстов и равняется полной системе вычетов по модулю n.

Предположим, что ключевое пространство имеет вид K = {(n, p, q, e, d ) : e, d Z n, n = p q, e d 1(mod (n))}, где () — функция Эйлера, (e, (n)) = 1. Представим ключ k K в виде k = (ko ; k s ), где ko = (n, e) — открытый ключ; k s = (d ) — секретный ключ.

–  –  –

6. Методы распределения криптографических ключей Для распределения ключей используют несколько методов, которые можно сгруппировать в следующие классы [8; 11; 12] :

1) публичное объявление;

2) публично доступный каталог;

3) авторитетный источник открытых ключей;

4) сертификаты открытых ключей.

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

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

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

Такая схема включает следующие элементы:

1) уполномоченный объект поддерживает каталог с записями, включающими имя и открытый ключ для каждого участника;

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

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

4) периодически объект, уполномоченный вести каталог, публикует весь каталог или дополнения к нему;

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

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

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

При этом выполняются следующие действия:

1) инициатор А посылает сообщение с меткой даты/времени авторитетному источнику открытых ключей с запросом о текущем открытом ключе участника В;

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

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

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

— оригинальную метку даты/времени, чтобы отправитель А мог удостовериться, что это сообщение не является одним из старых сообщений от авторитетного источника, содержащим ключ, отличный от текущего открытого ключа адресата В;

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

4) респондент В получает открытый ключ участника А от авторитетного источника точно таким же способом, каким отправитель А получил открытый ключ получателя В;

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

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

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

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

К описанной схеме выдвигаются следующие требования:

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

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

3) только авторитетный источник сертификатов должен иметь возможность создавать и изменять сертификаты.

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

Для участника А авторитетный источник обеспечивает сертификат вида С А = ЕKRавт [T, IDА, KU В ], где KRавт — личный ключ, используемый авторитетным источником;

KU В — открытый ключ участника В; IDА — идентификатор участника А;

Т — дата/время отправления. Участник А может переслать этот сертификат любому другому участнику, который прочтет и примет сертификат:

DKU авт [ С А ] = DKU авт [ ЕKRавт [Т, IDА, KU А ]] = (Т, IDА, KU А ), где KU авт — открытый ключ авторитетного источника; KU А — открытый ключ участника А.

Так как сертификат можно прочитать только с помощью открытого ключа авторитетного источника сертификатов, это дает гарантию того, что сертификат пришел именно от авторитетного источника. Элементы IDА и KU А сообщают получателю имя и открытый ключ владельца сертификата. Метка даты/времени Т определяет срок действия сертификата. Метка даты/времени должна быть защищена от следующей последовательности действий. Нарушитель узнает личный ключ А. По этой причине А генерирует новую пару ключей (личный и открытый) и обращается к авторитетному источнику сертификатов за новым сертификатом. Тем временем нарушитель воспроизводит сообщение со старым сертификатом и отсылает его В. Если В будет шифровать сообщения, используя старый скомпрометированный ключ, нарушитель сможет прочитать это сообщение.

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

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

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

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

1) сторона А генерирует пару (открытый/личный) ключей ( KU А, KRА ) и передает сообщение стороне В, содержащее KU А и идентификатор отправителя А IDА ;

2) получатель В генерирует секретный ключ К и передает этот ключ инициатору сообщения А зашифрованным с помощью открытого ключа инициатора А;

3) пользователь А вычисляет DKRА [ EKU А [ К S ]], чтобы восстановить секретный ключ. Поскольку только пользователь А может расшифровать это сообщение, только два участника обмена А и В будут знать значение К А ;

4) участник А уничтожает ключ KRА, а участник В — ключ KU А.

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

Этот протокол уязвим в отношении активных атак. Если нарушитель

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

1) участник А генерирует пару открытый/личный ключи ( KU А, KRА ) и передает сообщение адресату В, содержащее KU А и идентификатор участника А IDА ;

2) нарушитель Е перехватывает сообщение, создает собственную пару открытый/личный ключи ( KU Е, KRЕ ) и передает сообщение адресату В, содержащее KU Е, IDА ;

3) В генерирует секретный ключ К S и передает ЕKU Е [К S ];

4) нарушитель Е перехватывает это сообщение и узнает К S, вычисляя DKR Е [ E KU Е [ К S ]] ;

5) нарушитель передает участнику А сообщение Е KU А [К S ].

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

–  –  –

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

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

1) сторона А использует открытый ключ В для пересылки стороне В шифрованного сообщения, содержащего идентификатор участника А ( IDА ) и оказию ( N1 ), используемую для идентификации данной транзакции;

2) пользователь В посылает сообщение пользователю А, зашифрованное с помощью KU А, содержащее полученную от него оказию ( N1 ) и новую оказию ( N 2 ), сгенерированную пользователем В.

Присутствие N1 в сообщении убеждает участника А в том, что респондентом является сторона В;

3) сторона А возвращает N 2, шифруя сообщение открытым ключом стороны В, гарантируя В, что респондентом является сторона А;

4) участник А выбирает секретный ключ К S и посылает участнику В [ ] сообщение М = Е KU В Е KRА [К S ]. Шифрование этого сообщения открытым ключом стороны В гарантирует, что только участник В сможет прочитать его, а шифрование личным ключом участника А, — что только участник А мог послать его;

[ ]

5) сторона В вычисляет DKU А Е KR В [М ], чтобы восстановить секретный ключ.

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

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

В основе такого трехуровнего подхода лежит следующая логика:

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

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

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

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

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

Эффективность алгоритма Диффи — Хеллмана опирается на трудность вычисления дискретных логарифмов.

Обмен ключами по схеме Диффи — Хеллмана происходит следующим образом. В этой схеме имеются два открытых числа : простое число q и целое, являющееся первообразным корнем q. Предположим, что пользователи А и В намерены обменяться ключами. Пользователь А выбирает Х случайное целое число Х А q и вычисляет YА А (mod q ). Точно также пользователь В независимо выбирает случайное целое число Х В q и вычисляет YВ Х В (mod q ). Каждая сторона сохраняет значение Х в тайне и делает значение Y свободно доступным другой стороне.

Х Пользователь А вычисляет ключ по формуле К (YВ ) А (mod q ), а польХ зователь В — по формуле К (YА ) В (mod q ). По этим двум формулам вычисления дают одинаковые результаты, как следует из вычислений.

К (YВ ) Х А (mod q ) ( Х В mod q ) Х А (mod q) ( Х В ) Х А (mod q ) Х В Х А (mod q ) ( Х А ) Х В (mod q) ( Х А mod q) Х В (mod q ) (YА ) Х В (mod q).

Обе стороны обменялись секретными ключами. Поскольку при этом ХА и Х В были только в личном пользовании и поэтому сохранялись в тайне, нарушителю придется работать только с q,, А и В. Таким образом, нарушителю придется вычислять дискретный логарифм, чтобы определить ключ Х В = ind, q (YВ ).

После этого он сможет вычислить ключ К точно так же, как это делает пользователь В.

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

Для примера выберем простое число q = 97 с первообразным корнем = 5. Пользователи А и В выбирают секретные ключи Х А = 36 и Х В = 58, соответственно.

Каждый вычисляет открытый ключ:

А = 53650 (mod 97), B = 55844 (mod 97).

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

К (YВ ) Х А (mod 97) 4436 75(mod 97), К (YА ) Х В (mod 97) 5058 75(mod 97).

Имея 44 и 50, нарушителю не удастся с легкостью вычислить 75.

На рисунке 4 представлен простой протокол, в котором применяются вычисления в соответствии со схемой Диффи — Хеллмана [9]. Предположим, что пользователь А собирается установить связь с пользователем В и использовать секретный ключ, чтобы зашифровать сообщения, передаваемые с помощью такой связи. Пользователь А может сгенерировать одноразовое секретное значение Х А, вычислить значение А и отослать последнее пользователю В. В ответ пользователь В генерирует секретное значение Х В, вычисляет B и посылает B пользователю А. Оба пользователя теперь могут вычислить их общий ключ. Необходимые открытые значения q и должны быть известны заранее. Пользователь А может также выбрать эти значения на свое усмотрение и включить их в первое сообщение.

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

–  –  –

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

7. Криптография с использованием эллиптических кривых

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

Это породило множество проблем, особенно для узлов связи, специализирующихся на электронной коммерции, где требуется защита больших транзакций. В связи с этим появился конкурент RSA — это криптография на основе эллиптических кривых (ЕСС — Elliptic curve cryptography). Появились стандарты по криптографии с открытым ключом ЕСС, например, IEEE P1363.

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

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

у 2 + аху + by = x 3 + сх 2 + dx + g, (7.1) где a, b, c, d, g являются целыми числами.

Определение эллиптической кривой включает некоторый элемент, обозначаемый О и называемый несобственным элементом (точкой бесконечности, нулевым элементом).

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

Из этого определения вытекают следующие правила сложения над точками эллиптической кривой:

1) объект О выступает в роли нулевого элемента при сложении, т.е.

О = – О и для любой точки на эллиптической кривой Р + О = Р;

2) вертикальная линия пересекает эллиптическую кривую в двух точках с одной и той же абсциссой х. Эта линия пересекает кривую и в бесконечной точке. Поэтому Р1 + Р2 + О = О и Р1 = Р2, где Р1 = ( х, у ), Р2 = ( х, у ). Точкой со знаком «минус» является точка с той же координатой х, но с противоположным по знаку координатой у;

3) чтобы сложить две точки Q и R с разными координатами х, необходимо провести через эти точки прямую и найти третью точку пересечения Р1 этой прямой с эллиптической кривой. Существует только одна точка, если прямая не является касательной к эллиптической кривой в какой-либо из точек. В таком случае нужно положить Р1 = Q или Р1 = R, соответственно. Затем нужно воспользоваться выражением Q + R= – Р1 ;

4) чтобы удвоить точку Q, необходимо провести касательную в точке Q и найти другую точку пересечения S. Тогда Q + Q = 2Q = – S.

Вышеприведенные свойства сложения подчиняются всем обычным свойствам сложения, например, коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k также определено: это сумма k копий точки Р. Так, 2Р = Р + Р, 3Р = Р + +Р + Р и т. д. Следовательно, в случае криптографии с использованием эллиптических кривых приходится иметь дело с редуцированной формой эллиптической кривой, которая определяется над конечным полем.

Особый интерес для криптографии представляет объект, называемый эллиптической группой по модулю р, где р является простым числом. Такая группа определяется следующим образом. Выберем два неотрицательных целых числа а и b, которые меньше р и удовлетворяют условию (детерминанту) 4а 3 + 27b 2 mod p 0, тогда Е р ( а, b) обозначает эллиптическую группу по модулю р, элементами которой являются пары неотрицательных целых чисел (х, у), которые меньше р и вместе с точкой в бесконечности О удовлетворяют условию у 2 ( х 3 + ах + b)(mod p).

Эллиптическая кривая над полем действительных чисел с ненулевым дискриминантом представляет собой гладкую кривую, в каждой точке которой можно провести касательную. В случае характеристики 2 существуют две разновидности эллиптических кривых: суперсингулярные и несуперсингулярные. Суперсингулярные — это эллиптические кривые, для которых левая часть уравнения (7.1) имеет вид у + by. Несуперсингулярные — это эллиптические кривые, для которых левая часть уравнения (7.1) имеет вид у + аху. Эллиптической кривой соответствует эллиптический интеграл, не берущийся в элементарных функциях.

р = 23 рассмотрим эллиптическую кривую Для модуля у 2 х3 + х + 1. Детерминант (4 13 + 27 12 ) mod 23 = 8 0, что удовлетворяет условиям эллиптической группой по модулю 23.

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

Нахождение точек на эллиптической кривой производится по следующему алгоритму:

1) для каждого значения х, удовлетворяющего 0 x p, вычисляется ( х 3 + ах + b) mod p ;

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

Если нет, то во множестве Е р ( а, b) нет точек с этим значением х.

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

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

1) Р + О = Р ;

2) если Р = ( х, у ), то Р + ( х, у ) = О. Точка ( х, у ) является отрицательным значением точки Р и обозначается (–Р). Точка ( х, у ) лежит на эллиптической кривой и принадлежит Е р ( а, b) ;

3) если Р = ( х1, у1 ) и Q = ( х2, у2 ), где Р Q, то Р + Q = ( х3, у3 ) определяется в соответствии с правилами х3 (2 х1 х2 )(mod p), у3 ( ( х1 х2 ) у1 )(mod p), где у2 у1 х х Р Q, = 22 1 3 х1 + а Р = Q.

2 у1 Для примера рассмотрим следующий случай. Пусть Р = (0,0) на эллиптической кривой у 2 + у = х3 х 2.

Требуется найти 2Р = Р + Р, 3Р= Р + Р + Р.

–  –  –

эффициент t = q + m + 1.

По теореме Хассе [10] выполняется неравенство t 4q и в случае строгого неравенства корни квадратного уравнения и будут комплексными.

В качестве примера найдем порядок группы эллиптической кривой в случае 2.

Рассматривая 2 над полем GF ( 2), получим на ней точки:

(0,0), (0,1), (1,0), (1,1) и нулевой элемент О — всего пять элементов циклической группы. Таким образом, q = 2, m = 5, t = – 2, откуда находим корни квадратного уравнения х + 2 х + 2 = 0 : = 1 + i и = 1 i

–  –  –

7.1. Аналог обмена ключами по схеме Диффи-Хеллмана Обмен ключами с использованием эллиптических кривых может быть выполнен следующим образом. Сначала выбирается большое простое число p и параметры а и b для эллиптической кривой в уравнении (7.1).

Это задает эллиптическую группу точек Е р ( a, b). Затем в Е р ( a, b) выбирается генерирующая точка G = ( х, у ). При выборе G важно, чтобы наименьшее значение n, при котором nG = O оказалось очень большим простым числом. Параметры Е р ( a, b) и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями А и В можно провести по следующей схеме:

1) сторона А выбирает целое число n А n. Это число будет личным ключом участника А. Затем участник А генерирует открытый ключ РА = n А G. Открытый ключ представляет собой некоторую точку из Е р ( a, b) ;

2) сторона В выбирает аналогично личный ключ nВ и вычисляет открытый ключ РВ = nВ G ;

3) участник А генерирует секретный ключ К = n А РВ, а участник В генерирует секретный ключ К = nВ РА.

Две формулы, полученные в п. 3) дают один и тот же результат, поскольку n А РВ = n А (nВ G ) = n В (n А G ) = nВ РА.

Чтобы взломать эту схему, нарушитель должен будет вычислить k по данным G и kG, что представляется трудным делом.

В качестве примера выберем р = 211, Е211 (0, – 4), что соответствует эллиптической кривой у = х 4 и G = ( 2,2). Нетрудно сосчитать, что 241G = О. Личным ключом участника А является n А = 121, поэтому открытым ключом участника А будет РА = 121( 2,2) = (115,48). Личным ключом участника В будет nВ = 203, поэтому открытым ключом участника В будет РВ = 203(2,2) = (130,203). Общим секретным ключом является 121(130, 203) = 203 (115, 48) = (161, 169).

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

7.2. Протокол обмена ключами по схеме Месси-Омуры

–  –  –

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

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

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

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

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

В обоих случаях используется двоякая трактовка координат точек эллиптической кривой: а) как элементов расширения поля, над которым строится кривая; б) как кодов целых чисел.

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

Участники А и В располагают точкой Р эллиптической кривой порядка n, над которой осуществляются все вычисления.

Кроме того, они знают долговременные и кратковременные ключи друг друга:

1) ключи участника В известны участнику А QВ = d В Р = (аВ, bВ ), RВ = k В Р = ( хВ, уВ ) ;

2) ключи участника А известны участнику В QА = d А Р = (а А, bА ), RА = k А Р = ( х А, у А ).

7.4. Протокол Эль Гамаля для криптосистемы с использованием эллиптических кривых В случае криптосистемы RSA использование протокола Эль Гамаля выглядит следующим образом. Выбирается простое число n и случайные р n и q n. Открытым ключом является тройка числа (n, p, p q mod n = у ), а q используется в качестве секретного ключа.

Для шифрования открытого текста m необходимо вычислить а p k (mod n), b(m) ( у k m)(mod n), где k — случайное взаимно простое с n число. Шифртекстом является пара а, b(m). Очевидно, что для q расшифровки требуется вычислить m = (b( m) / a ) mod n.

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

Пусть открытый текст М является точкой эллиптической кривой Е. В случае если открытый текст представлен в виде набора точек, описанные ниже преобразования производятся для каждой точки отдельно.

Абоненты криптосистемы А и В уже совершили обмен частями ключа k АQ и k ВQ по протоколу Диффи-Хеллмана. Теперь абонент А, желающий переслать В сообщение М, должен выбрать секретное число l и отправить другому абоненту пару точек эллиптической кривой Е = (lQ, M + l (k ВQ)). Для расшифровки полученного сообщения абонент В вычисляет Т = k В (lQ )(l ( k В Q )). Очевидно, что М = М + l (k ВQ ) T.

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

–  –  –

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

8.1 Стандарт DSS, алгоритм DSA В 1991 г. Правительственный национальный институт стандартов и технологий США утвердил стандарт цифровой подписи DSS (Digital Signature Standard), основанный на специальном алгоритме цифровой подписи DSА (Digital Signature Algorithm) для использования в правительственных и коммерческих организациях. Алгоритм основан на трудности проблемы дискретного логарифмирования мультипликативной группы конечного поля.

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

1) выбрать простое число q, не менее 150 бит, используя для этого генератор случайных чисел и тесты на простоту;

2) аналогичным образом выбрать второе простое число р, не менее 500 бит, причем делителем р – 1 является q;

3) выбрать образующий элемент единственной циклической подгруппы группы F р порядка q, которое находится вычислением g ( р1) q (mod p ) для случайно выбранного целого числа g (если в результате вычислений получается целое, отличное от единицы, то будет образующим элементом);

4) определить случайное число а 0, q в качестве секретного ключа а и образовать открытый ключ у (mod p ).

Теперь пользователь может подписывать сообщения. Сначала он применяет к открытому тексту m хэш-функцию, получая целое h(m) 0, q. Затем он выбирает случайное целое k 0, q и вычисляет r ( k mod p)(mod q). В заключение пользователь находит целое s такое, что s (k –1 [ h(m) + ar ])(mod q ). Подпись этого пользователя m образуется парой чисел ( r, s ) по модулю q.

Чтобы проверить подпись, противоположная сторона, получив аутентифицированный открытый ключ от первого пользователя ( р, q,, у ), должна выполнить следующие действия :

1) проверить, выполняются ли условия (0 r q ) и (0 s q ), а если нет, то отклонить подпись;

2) вычислить w s –1 (mod q ) и h(m) ;

3) найти u1 ( s h)(mod q ) и u 2 ( rw)(mod q ) ;

u u

4) вычислить v (( 1 у 2 ) mod p )(mod q ) ;

5) принять подпись, если v = r, и отклонить в противоположном случае.

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

Алгоритм ESDSA — аналог DSA для эллиптических кривых. Для простоты будем рассматривать эллиптические кривые над полем Fр.

Пусть Е — эллиптическая кривая, определенная над полем Fр, и пусть Р — точка простого порядка q кривой Е ( Fр ). Эта кривая и точка на ней являются системными параметрами. Используемые простые числа р и q примерно одного порядка. Каждый пользователь выбирает случайное число а в интервале 1 a q 1 и вычисляет свой открытый ключ по формуле Q = aP. Он публикуется при сохранении числа а в качестве секретного ключа пользователя.

Протокол ESDSA для вычисления цифровой подписи. Чтобы подписать свое сообщение, пользователь проделывает следующее:

1) выбирает случайное целое число k 1, q 1;

2) вычисляет kP = ( x1, y1 ) и r x1 (mod q ) ( х1 0, p 1 с дальнейшим приведением по модулю q). Если r 0(mod q ), то выбирают новое случайное число k 1, q 1;

3) определяет k mod q ;

-1

4) вычисляет s (k [h(m) + xr])(modq), где h(m) — хэшированное посылаемое сообщение m. Если s = 0, то значения s 1 mod q, требуемого по п. 3) для верификации подписи не существует, откуда необходимо возвращение к п. 1);

5) подписью для сообщения m является пара чисел ( r, s ).

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

1) получает авторизированную копию открытого ключа Q источника сообщения;

2) проверяет принадлежность чисел ( r, s ) интервалу (1, q 1) ;

3) вычисляет w s –1 (mod q ) и h(m) ;

4) находит u1 ( s h)(mod q ) и u 2 (rw)(mod q ) ;

5) вычисляет ( х0, у0 ) = u1P + u2Q, v х0 (mod q ) ;

6) принимает подпись, если v = r, и отклонить в противоположном случае.

Основное различие между ECDSA и DSA состоит в способе образоk вания r. DSA вычисляет r как случайную степень mod p, приведенную по модулю q, которое должно принадлежать интервалу (1, q 1).

ECDSA формирует целое r взятием абсциссы точки kP и приведением ее по модулю q.

Для получения того же уровня секретности, что и в случае применения DSA, параметр q должен быть 160-битовым.

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

8.2. Обобщенная схема цифровой подписи Эль Гамаля

Обобщенная схема электронной подписи Эль Гамаля работает в любой абелевой группе.

Для работы по данной схеме каждому участнику необходимо:

1) выбрать подходящую циклическую группу G порядка n и её образующий элемент ;

2) выбрать случайное целое число а 1, n 1 и вычислить элемент у = а mod n ;

3) сформировать открытый ключ (, у ) на основе секретного ключа а.

Для формирования подписи, сопровождающей документ m, участник А должен выполнить следующие действия:

1) выбрать случайное секретное число k 1, n 1, взаимно простое с n, ( k, n) = 1 ;

k

2) вычислить элемент r = mod n ;

3) найти k mod n ;

4) вычислить хэш-функции h(m) и h(r ) ;

5) найти s = k [ h( m) ah(r )] mod n ;

6) цифровой подписью является пара ( r, s ).

Для проверки цифровой подписи участника А на документе m участник В должен проделать следующие действия:

1) получить авторизированную версию открытого ключа участника А (, у ) ;

2) вычислить хэш-функции h(m) и h(r ) ;

h(r ) r s ) mod n ;

3) найти v1 = ( у h(m)

4) вычислить v2 = mod n ;

5) принять подпись, если v1 = v 2 и отклонить ее в противоположном случае.

Генерация подписи требует вычислений, как в группе G, так и в группе Z n, в то же время проверка подписи связана с вычислениями только в группе G.

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

8.3. Схема цифровой подписи Эль Гамаля с возвратом сообщения

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

Пространством сообщений здесь является М = Z р, где р — простое число. В качестве пространства подготовленных к подписанию сообщений М S используется декартово произведение М S = Z р Z q, где q — простое число, которое является делителем ( р 1). Пусть R — инъекция из пространства сообщений М в пространство подписанных сообщений М S. Например, значение R(m) может быть представлено как (m, m mod q ). Через R 1 обозначается отображение из образа функции R

–  –  –

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

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

При анализе надежности систем безопасности возникают две задачи:

1. Проверить безопасность данной системы относительно некоторой модели нарушителя.

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

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

1. Вычислительные (тип вычислительной модели, ее производительность, объем памяти и др.).

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

3. Технические (инструмент, реализующий атаку).

4. Организационные (дополнительные способы получения информации, такие как доступ к открытым текстам, доступ к ключам, выведенным из употребления и т. п.).

В случае криптосистем на эллиптических кривых специфическими являются математические возможности нарушителя.

Модель возможностей нарушителя называется вырожденной, если единственный способ чтения информации нарушителем — чтение установленным в протоколе порядком, а единственный способ изменения информации — запись установленным порядком.

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

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

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

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

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

10. Модель несанкционированной подмены передаваемой информации

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

Пользователь А передает файл у пользователю В, который получается из открытого текста х путем шифрования его по правилу у = (х(m)), (10.1) где m — ключ шифрования.

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

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

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

Рассмотрим двух главных участников рассматриваемого процесса:

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

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

Если нарушитель попытается послать стороне А ложное сообщение уo, для которого может не быть исходного сообщения х', удовлетворяющего уо = (х, m), и тогда сторона А обнаружит обман нарушителя. Но если нарушитель сможет решить уравнение (10.1), то тогда он может успешно заменить истинное сообщение ложным, но правильно зашифрованным уо = (х, m). Возникает задача получения (, ) такого, чтобы было невозможным для нарушителя обмануть сторону А, не будучи обнаруженным.

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

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

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

Чтобы затруднить возможность нарушителю раскрыть ключ, используя уравнение (10.1), сторона А должна сконструировать такую функцию (, ), чтобы (10.1) имело бы несколько решений для m. Тогда нарушитель вероятнее всего, выберет неправильный ключ mо и сторона А обнаружит, что зашифрованное нарушителем послание уo не соответствует правильному ключу. Как можно ожидать, для обеспечения нескольких решений уравнения (10.1) сторона А должна использовать большое число К возможных ключей.

Вероятность быть необнаруженным для нарушителя, пытающегося заменить истинное послание на ложное, обозначим через ро. Вероятность ' ро для оптимальной стратегии нарушителя обозначим ро. Покажем, что ро К 0,5. Равенство в этом случае достигается только жестким ограничением числа N возможных посланий х. Более полезные коды должны выбираться, исходя из компромисса между тремя конфликтующими параметрами: малое ро, малый К и большое N. Рассмотрим два таких случая: случайный код и систематический.

Для анализа указанных случаев мы полагаем, что нарушитель имеет ' особое, но неизвестное ложное послание х для замены истинного х. Примем, что х равновероятно одному какому-либо значению из N возможных ' значений и что нарушитель выбирает ложное послание х случайно из остальных N – 1 возможностей. Тогда ро является средней из вероятностей ' ' успеха ро (х, у, х ), когда нарушитель замещает х на х, зная у.

Для подтверждения подлинности (аутентификации) сообщения принята специальная форма построения файла, записываемая как у = (х; z), (10.2) т.е. у является соединением незашифрованного текста х и некоторого количества дополнительных цифр или букв z. Здесь z — некоторая функция от х и m, которую будем называть аутентификатором.

Хотя уравнение (10.2) является особым случаем (10.1), без существенной потери общности можно распространить шифрование и на эту особую форму. Действительно, если некоторые другие о (х, m) в уравнении (10.1) дают хороший код, можно всегда создать код вида (10.2), выбирая z = о (х, у), т.е.

y = (x, m) = [x;o (x, m)].

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

Использовать или не использовать код в форме (10.2) — это предмет договора. Однако уравнение (10.2) имеет специальное свойство, которое характерно для всех кодов. Оно заключается в том, что различные открытые послания х1, х2 не могут быть закодированы в одно и то же у, т.е.

(m1, х1 ) (m2, x2 ) (10.3) выполняется для всех m1, m2, если х1 х2. Тогда типовой код можно представить диаграммой, изображающей открытые послания х как точки в левом столбце, а зашифрованные послания у — как точки в правом столбце. Стрелки, направленные слева направо, будут отображать наименование ключей 1,..., К, используемых для отображения процесса кодирования каждого х в у. Согласно выражению (10.3), закодированные послания у делятся на несвязные кластеры, причем каждый кластер содержит все возможные представления каждого х.

Оценим вероятность обмана. Пусть нарушитель успешно обманывает сторону А с вероятностью ро К для наугад выбранного ключа mo при условии, что все ключи К равновероятны. Лучшей стратегией для нарушителя будет использование знаний об х и у для ограничения выбора ключей, которые удовлетворяют уравнению (10.1). Обычно нарушитель не нуждается в выборе при mo = m правильного ключа, так как он получает удовлетворение, если (х',то ) = (х', m). (10.4) Нарушитель выбирает для mo одно из значений 2, 3, 4, 5 или 6. Если m = 2, тогда подходят выбранные mo = 2, 4 или 6.

Важной качественной особенностью кода является размерность пучка линий, переводящих послание х в закодированную форму у на кодовой диаграмме. А должен стремиться делать эти послания достаточно большими, чтобы предотвратить угадывание нарушителя с достаточно большой вероятностью. Однако, если пучки достаточно большие, нарушитель будет чаще угадывать, так как большинство ключей mo будут удовлетворять выражению (10.4). Компромисс между двумя крайними размерностями пучков не позволяет стороне А ограничить нарушителя вероятностью ро = К 1. Действительно, теперь покажем, что нарушитель всегда может использовать стратегию с вероятностью ро К 0,5. (10.5)

Для доказательства формулы (10.5) установим несколько естественных ограничений на поведение стороны А и нарушителя:

'

а) нарушитель не пытается обмануть сторону А заменой х на х = х.

Если допустить, что нарушитель «обманывает» в каком-либо виде с вероятностью ро = 1, то, исходя из выражения (10.5), это дает слабый результат;

б) все N посланий х равновероятны. Хотя это требование может быть ослаблено, некоторые условия, подобные этому, должны быть поставлены.

Для страховки сторона А может использовать одно специальное послание х1 только в исключительных случаях. В этом случае сторона А может присвоить всем ключам, имеющим код х1, одинаковое значение у1, а ' всем другим посланиям — код х. К различных ключей для шифрования 0,5 тогда должны давать вероятность ро К, но сторона А при этом получит минимум информации от каждого послания;

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

–  –  –

тот, что для p не требуется значительно превышать K 2.

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

В этом случае код обеспечивает вероятность po, зависящую от случайного выбора. Определим ожидаемое значение Е(ро ). Особые коды с заданными N и К и имеющие po менее, чем эти прогнозы, действительно существуют.

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

–  –  –

Е(ро ) теперь может считаться решением задачи распределения ключей. Представим, что правильным ключом будет ключ 1, и он занимает ячейку в столбце 1 и строке 1. Распределим оставшиеся К - 1 ключей случайным образом по А ячейкам. Пусть рn,k будут вероятности того, что ячейка (1, 1) содержит v(1,1 ) = n ключей таких, что k 1 других ячеек в столбце 1 содержат n ключей. Более того, все А - k остальных ячеек в столбце 1 содержат менее, чем n ключей. Тогда Е(ро ) = k 1 рn,k (10.16) n,k является вероятностью того, что нарушитель выбирает первую строку по уо.

Точная формула для рn,k весьма громоздка. Не составляет труда смоделировать экспериментальное распределение на компьютере, чтобы оценить Е(ро ), когда К меньше нескольких сотен. Это было проделано [11], но только для проверки на возможность более простой аппроксимации.

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

–  –  –

256 2 0 16 1 8,01 0,0039 0,0039 41 3 1 16,08 41 10,7 0,0244 0,0250 16 4 1 16 1 16,1 0,0625 0,0078 9 5 2 15,9 9 19,2 0,1111 0,0137 7 6 2 16,86 1 25,5 0,1429 0,0058 5 7 3 16,24 5 28,3 0,2000 0,0096 4 8 3 16 1 32,5 0,2500 0,0078 3 10 4 15,9 1 40,5 0,3333 0,0082 2 16 7 16 1 65,9 0,5000 0,0078 Библиография

1. Айерлэнд К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен. — М. : Мир, 1987. — 416 с.

2. Воронков Б. Н. Методическое пособие по разработке средств защиты информации в вычислительных сетях / Б. Н. Воронков, В. И. Тупота. — Воронеж : ЛОП ВГУ, 2000. — 112 с.

3. Иванов В. А. Криптографические методы защиты информации в компьютерных системах и сетях / В. А. Иванов. — М. : КУДИЦ — ОБРАЗ, 2001. — 368 с.

4. Математические и компьютерные основы криптологии : учеб. пособие / Ю. С. Харин [и др.]. — Минск : Новое знание, 2003. — 382 с.

5. Основы криптографии : учеб. пособие / А. П. Алферов [и др.]. — М. :

Гелиос АРВ, 2001. — 480 с.

6. Питерсон У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. — М. : Мир, 1976. — 594 c.

7. Холл М. Комбинаторика / М. Холл. — М. : Мир, 1970. — 424 c.

8. Bauer R. C. A key distribution protocol using event markers / R. C. Bauer, T. A. Berson, R. J. Feiertag // ACM Trans. Comput. Syst. — 1983. — Vol. 1, № 5. — P. 249 — 255.

9. Diffie W. New directions in cryptography / W. Diffie, M. Hellman // IEEE Trans. Inf. Theory, 1976. — Vol. 22, № 11. — P. 644 — 654.

10. Giblin P. J. Primes and Programming : An Introduction to Number Theory with Computing / P. J. Giblin. – Cambridge : Cambridge University Press, 1993. — 237 c.

11. Matyas S. M. Generation, distribution and instalation of criptografic keys / S. M. Matyas, C. H. Meyer // IBM Syst. J. — 1978. — Vol.17, № 2. — P. 125 —137.

12. Needham R. M. Using encription for autentification in large networks for computers / R. M. Needham, M. D. Schroeder // Commun. ACM. — 1978. — Vol. 21. — P. 993 — 999.

–  –  –

Издательско-полиграфический центр Воронежского государственного университета.

394000, г. Воронеж, пл. им. Ленина, 10. Тел. 208-298, 598-026 (факс) http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru Отпечатано в типографии Издательско-полиграфического центра Воронежского государственного университета.

394000, г. Воронеж, ул. Пушкинская, 3. Тел. 204-133.

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

«6304 3056 – 12/2005 RU Сервисный уровень Инструкция по пуску в эксплуатацию и техническому обслуживанию Дизельная горелка Logatop SE Внимательно прочитайте перед пуском в эксплуатацию и техническим обслуживанием Содержание 1 Указания по безопасной эксплуатации 1.1 Об этой...»

«Объемы реализованной продукции ОАО KazTransCom за 2003 год. тыс.тенге С начала Обьем реализованной продукции (оказанных года, всего услуг) 2003г. Реализовано всего в том числе по основной деятельности: 2 399 989 Услуги местной телефонной связи 47 516 Услуги транкинговой связи 34 233 Ус...»

«УДК 621.34 В. Б. КЛЕПИКОВ, д-р техн. наук, проф., зав. каф. АЭМС НТУ "ХПИ" К 85-ЛЕТИЮ КАФЕДРЫ "АВТОМАТИЗИРОВАННЫЕ ЭЛЕКТРОМЕХАНИЧЕСКИЕ СИСТЕМЫ" 85-летие кафедры совпало с 130-летием нашего университета. Открытый в 1885 г. Харьковский технол...»

«НОВА ФІЛОЛОГІЯ № 58 2013 УДК 811.111:8137 ЗАЦНИЙ Ю. А. (Запорізький національний університет) О НЕКОТОРЫХ ИННОВАЦИОННЫХ ПРОЦЕССАХ И МЕХАНИЗМАХ В ЛЕКСИКО-СЕМАНТИЧЕСКОЙ СИСТЕМЕ АНГЛИЙСКОГО ЯЗЫКА В статье анализируются тенденции и механизмы словообразования, аналогии, процессов внутренних межвариантных заимствований как...»

«УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОГО УНИВЕРСИТЕТА Том 154, кн. 5 Гуманитарные науки 2012 УДК 811.161 СЕМАНТИЧЕСКАЯ ДЕРИВАЦИЯ И СИНКРЕТИЗМ М.Вас. Пименова Аннотация Статья посвящена основным механизмам семантической деривации, осуще...»

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

«Безопасность труда при дорожных работах Авторы: Март Йоосеп, Рейн Рейсберг Литературное редактирование: Agentuur La Ecwador O Оформление: Agentuur La Ecwador O Фотографии: частные коллекции, stock.adobe.com Типография: Agentuur La Ecwador O © Инспекция труда, 2016 I...»

«Об обеспеченности нормативными документами в области проектирования, строительства и эксплуатации объектов ТЭК на многолетнемезлых грунтах и на Арктических территориях Авторы: Н. В. Варламов Управляющий директор ОАО "Гипротюменнефтегаз" С. Н. Стрижков Зам. управляющего директора по науке ОАО "Гипротюменнефтегаз"...»

«УДК 800.7 О некоторых трудностях перевода научно-технической литературы. И. М. Галецкая Для каждого творчески работающего специалиста необходимо получение профессиональной информации на иностранно...»

«685 УДК 539.543.544 Исследование термодинамики сорбции производных адамантана на полимерных неподвижных фазах различной полярности в условиях газожидкостной хроматографии Кудашева Н.В., Яшкин С.Н., Светлов А.А. ГОУ ВПО Самарский государственный технический университет, Самара Поступи...»

«УДК 678.61.742.3.046.52 И. Н. Мусин, И. З. Файзуллин, С. И. Вольфсон МОДИФИКАЦИЯ ДРЕВЕСНОПОЛИМЕРНЫХ КОМПОЗИТОВ НА ОСНОВЕ ПОЛИОЛЕФИНОВ МОНТМОРИЛЛОНИТОМ Ключевые слова: древеснополимерный комп...»

«Подписной индекс в каталоге "Пресса России" 39898 ISSN 1680-1709 ББК 95.4 Ч-823 ВЕСТНИК ЧУВАШСКОГО ГОСУДАРСТВЕННОГО ПЕДАГОГИЧЕСКОГО УНИВЕРСИТЕТА ИМЕНИ И. Я. ЯКОВЛЕВА 2011. № 2 (70). Ч. 1 Серия "Естественные и технич...»

«TS-EML300 ЗАЩЁЛКА ЭЛЕКТРОМЕХАНИЧЕСКАЯ РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ 1. НАЗНАЧЕНИЕ Защёлка электромеханическая TS-EML300 предназначена для запирания распашных дверей, ворот и калиток, с возможностью их дистанционного открывания с помощью контроллеров систем конт...»

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

«Возможности ОАО "Пневмостроймашина" по термообработке металла в печах "IVA" Корпус термического цеха. Выполнена реконструкция в соответствии с современными требованиями Комплекс оборудования включает в себя: • 4 печи RH1299RV/e • моечную машину • электропогрузчик • аммиачную станцию •...»

«О.А. Кузяева УДК 624.15.001 Кузяева О. А. студ. гр. ГРб-11-1 Государственный ВУЗ "Национальный горный университет", г. Днепропетровск, Украина ГЕОМЕХАНИЧЕСКАЯ ОЦЕНКА УСТОЙЧИВОСТИ УЧАСТКОВЫХ ВЫРАБОТОК В УСЛОВИЯХ ШАХТЫ "КОМСОМОЛЬСКАЯ" На сегодняшний день в угледобывающей отрасли немалов...»

«ГЛОБАЛЬНАЯ ЯДЕРНАЯ БЕЗОПАСНОСТЬ, 2013 №2(7), С. 40–44 ИЗЫСКАНИЕ, ПРОЕКТИРОВАНИЕ, СТРОИТЕЛЬСТВО И МОНТАЖ ТЕХНОЛОГИЧЕСКОГО ОБОРУДОВАНИЯ АЭС УДК 004.942 МОДЕЛЬ АНАЛИЗАТОРА ТРАЕКТОРИИ ТОРЦА ЭЛЕКТРОДА В МУЛЬТИМЕДИЙНОМ ТРЕНАЖ...»

«1 ПРОГРАММА II ФОРУМА НАУКОГРАДОВ Регистрация участников. 9.00 -10.00 Пленарная сессия: ИНВЕСТИЦИИ В НАУКУ: КОГДА, КУДА И С КЕМ? Приветственное слово участникам "II Форума Наукоградов" 10.00 – 10.10 от Правительства Московской Об...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ СОВРЕМЕННЫЕ ПРОБЛЕМЫ МАТЕМАТИКИ Тезисы Международной (43-й Всероссийской) молодежной школы-конференции, 29 января 5 февраля 2012 г. ЕКАТЕРИНБУРГ ...»

«DOI: 10.22455/ 2500-4247-2016-1-1-2-73-90 УДК 82-0 ББК 83 ПРОБЛЕМА ПАМЯТИ И ЗАБВЕНИЯ: М. М. БАХТИН О МЕХАНИЗМАХ СОХРАНЕНИЯ / СТИРАНИЯ СЛЕДОВ ТРАДИЦИИ В ИСТОРИИ КУЛЬТУРЫ1 © 2016 г. И. Л. Попова Институт мировой литературы им. А. М. Горького Российской академии наук, Москва, Россия Дата поступления с...»

«SCHNEIDER-KESSEL BERLIN ® Паровые и водогрейные котлы Водотрубные котлы серии ERK (ЕРК) Конструкция и описание процесса работы котла SCHNEIDER Eckrohrkessel® из серии ERK(ЕРК) – это водотрубный котёл с естественной циркуляцией. Он отличается от котлов своей наглядной и прочной...»

«Министерство образования и науки Украины Донецкий национальный технический университет Кафедра Основы проектирования машин Структурный анализ механизмов с группами Ассура разных модификаций Методические указания к выполнению лабораторной работы №1 по курсу Теория механизмов и машин Донецк, ДонНТУ 2006 ...»

«226 Д. В. Дежинов, А. Н. Ларионов МЕТОДИКА ОЦЕНКИ ИНВЕСТИЦИОННОЙ ПРИВЛЕКАТЕЛЬНОСТИ ПРОЕКТОВ Волгоградский государственный технический университет Необходимость оценки инвестиционной привлекательности проектов обусловлена еще и тем, что инвестиционный проект является самостоятельн...»

«Адрес этой статьи в интернете: www.biophys.ru/archive/congress2012/proc-p206-d.pdf СИСТЕМА БЕСКОНТАКТНОЙ РЕГИСТРАЦИИ РЕАКЦИИ ЧЕЛОВЕКА-ОПЕРАТОРА И ГРУППЫ ЛЮДЕЙ НА ИНФОРМАЦИОННО-ПСИХОЛОГИЧЕСКИЕ ВОЗДЕЙСТВИЯ Орлов Д.В.1,2, Коротков К.Г. 1,2, Гатчин...»

«Министерство образования Российской Федерации Алтайский государственный технический университет им.И.И.Ползунова НАУЧНОЕ ТВОРЧЕСТВО СТУДЕНТОВ И СОТРУДНИКОВ 61-я научно-техническая конференция студентов, аспирантов и профессорско-преподавательского состава Ча...»

«12. Королев В. И. Тенденции в развитии систем безопасности на плавучих объектах с ЯЭУ / В. И. Королев, А. Ю. Ластовцев, Д. А. Барышников // Науч.-техн. конф. проф.-преп. сост., науч. сотр. и курсантов: тез. докл. — Ч. 2. — СПб.: Изд-во ГМА им. адм. С. О. Макарова, 2012. — С. 65–67.13. Королев В. И. Технические решения по нед...»

«Протокол взаимодействия между внешней платежной системой и Процессинговым Центром Pay-logic Руководство разработчика АННОТАЦИЯ Данный документ содержит описание и техническую спецификацию протокола взаимодействия с внешними платежными системами. Актуален для ПО "Процессинговый центр" 4.3.хх Версия 4.0 "Процес...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

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