Шифрование и расшифровывание

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Черниговский государственный технологический университет

 

 

 

ИСПОЛЬЗОВАНИЕ

АЛГОРИТМОВ

КРИПТОСИСТЕМ

С ОТКРЫТЫМ КЛЮЧОМ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к расчетно-графической работе по дисциплине

“ЗАЩИТА ИНФОРМАЦИИ

В КОМПЬЮТЕРНЫХ СИСТЕМАХ И СЕТЯХ”

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

0915 - “Компьютерная инженерия”

 

           УТВЕРЖДЕНО

      на заседании кафедры

          информационных

     и компьютерных систем

                                                          Протокол № 8 от 14 апреля 2010 г.

 

 

Чернигов ЧГТУ 2010

Використання алгоритмів криптосистем з відкритим ключем. Методичні вказівки до розрахунково-графічної роботи з дисципліни “Захист інформації в комп”ютерних системах та мережах” для студентів напряму підготовки 0915 - “Комп’ютерна інженерія” / Укладачі Соломаха В.В., Павловський В.І., Верьовко О.В. – Чернігів: ЧДТУ, 2010. - 41 с. Рос. мовою.

 

 

Составители: Соломаха Валерий Владимирович, старший преподаватель

                   Павловский Владимир Ильич, канд. техн. наук, доцент

                   Верёвко Александр Валериевич, студент

 

 

Ответственный за выпуск:	Павловский В.И., зав. кафедрой информационных и компьютерных систем, канд. техн. наук, доцент
Рецензент:	Нестеренко С.О., канд. техн. наук, доцент

 

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ............................................................................................... 4

1 АЛГОРИТМ RSA................................................................................ 5

1.1 История........................................................................................... 5

1.2 Описание алгоритма................................................................ 5

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

1.2.2 Шифрование и расшифровывание........................................ 6

1.2.3 Пример.................................................................................... 7

2 СХЕМА ИДЕНТИФИКАЦИИ ГИЛЛОУ - КУИСКУОТЕРА........... 8

3 РАЗДЕЛЕНИЕ СЕКРЕТА................................................................ 10

3.1 Мотивация.................................................................................... 10

3.2 Тривиальная схема.................................................................. 10

3.3 Пример t ≠ n.................................................................................. 11

3.4 Схема Блэкли.............................................................................. 11

3.5 Схема Шамира............................................................................ 12

4 АЛГОРИТМ ЦИФРОВОЙ ПОДПИСИ ЭЛЬ ГАМАЛЯ (EGSA).... 13

5 ПРИМЕЧАНИЯ................................................................................. 16

5.1 Расширенный алгоритм Евклида..................................... 16

5.1.1 Пример.................................................................................. 16

5.2 Алгоритм быстрого возведения в степень.................. 17

5.2.1 Теоретические основы алгоритма....................................... 17

5.2.2 Оценка сложности................................................................ 18

5.2.3 Пример.................................................................................. 18

6 ВАРИАНТЫ ЗАДАНИЙ НА РГР.................................................... 20

6.1 Задание №1.................................................................................... 20

6.2 Задание №2.................................................................................... 24

6.3 Задание №3.................................................................................... 28

6.4 Задание №4.................................................................................... 31

7 ПРИМЕРЫ РЕШЕНИЯ ЗАДАНИЙ................................................. 35

7.1 Задание №1.................................................................................... 35

7.1.1 Решение................................................................................. 35

7.2 Задание №2.................................................................................... 37

7.2.1 Решение................................................................................. 37

7.3 Задание №3.................................................................................... 38

7.3.1 Решение................................................................................. 38

7.4 Задание №4.................................................................................... 39

7.4.1 Решение................................................................................. 39

ЛИТЕРАТУРА......................................................................................... 41

 

ВВЕДЕНИЕ

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

 

Расчетно-графическая работа состоит из 4 заданий:

 

1. Дешифрование сообщения, зашифрованного по криптосистеме RSA.

2. Идентификация пользователей по системе Гиллоу-Куинскуотера.

3. Разделение и восстановление секрета для сети из n абонентов по схеме разделения секрета Шамира.

4. Подпись и верификация сообщения по схеме электронной цифровой подписи Эль-Гамаля.

 

1 АЛГОРИТМ RSA

RSA — криптографический алгоритм с открытым ключом.

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

История

Описание RSA было опубликовано в 1977 году Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT). Система была названа по первым буквам их фамилий.

Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.

В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.

В 1977 году создателями RSA была зашифрована фраза «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку была обещана награда в 100 долларов США. Фраза была расшифрована в 1993—1994 годах. Более 600 добровольцев жертвовали процессорное время с около 1600 машин (две из которых были факс-машинами) больше шести месяцев. Координирование проходило через Интернет, и это был один из первых подобных проектов распределённых вычислений. Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

Описание алгоритма

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

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

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

1. Выбираются два больших случайных простых числа и

2. Вычисляется их произведение

3. Вычисляется Функция Эйлера

4. Выбирается целое  такое, что  и  взаимно простое с

5. С помощью расширенного алгоритма Евклида находится число  такое, что  это значит, что при некотором целом .

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

Шифрование и расшифровывание

Для того, чтобы зашифровать сообщение вычисляется

.

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

.

Нетрудно убедиться, что при расшифровывании мы восстановим исходное сообщение:

Из условия

следует, что

для некоторого целого , следовательно

Согласно теореме Эйлера:

,

поэтому

Пример

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

Вычислим модуль

Вычислим функцию Эйлера

Положим открытый показатель равным 3

С помощью расширенного алгоритма Евклида вычислим секретный показатель

Заметьте, что

Пара чисел (3, 9173503) образует открытую часть ключа, а число 6111579 является секретным ключом.

Зашифруем с помощью открытого ключа число :

Шифртекстом является число 4051753.

Для расшифрования вычисляем

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

 

2 СХЕМА ИДЕНТИФИКАЦИИ ГИЛЛОУ - КУИСКУОТЕРА

Алгоритм идентификации с нулевой передачей знания, разработанный Л.Гиллоу и Ж.Куискуотером (Луи Гиллу (Louis Guillou) и Жан-Жак Кискатр (Jean-Jacques Quisquater)), имеет несколько лучшие характеристики, чем другие схемы идентификации. В этом алгоритме обмены между сторонами А и В и аккредитации в каждом обмене доведены до абсолютного минимума - для каждого доказательства требуется только один обмен с одной аккредитацией. Однако обьем требуемых вычислении для этого алгоритма больше, чем для схемы Фейге-Фиата-Шамира.

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

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

Секретным ключом стороны А является величина G, выбираемая таким образом, чтобы выполнялось соотношение

I * GV ≡ 1 (mod n).

Сторона А отправляет стороне В свои идентификационные данные I. Далее ей нужно доказать стороне В, что эти идентификационные данные принадлежат имеиио ей. Чтобы добиться этого, сторона  А должна убедить сторону В, что ей известно значение G.

Протокол доказательства подлинности А без передачи стороне В значения G:

1.Сторона А выбирает случайное целое r, такое, что 1 < r ≤ n - 1. Она вычисляет

Т = r^V mod n

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

2.Сторона  В выбирает случайное целое d, такое, что 1 < d ≤ n - 1, и отправляет это значение d стороне А.

3. Сторона  А вычисляет

D = r * G^d mod n

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

4. Сторона В вычисляет значение

T' = D^V I^d mod n.

Если Т ≡ Т' (mod n), то проверка подлинности успешно завершена. Математические выкладки. использованные в этом протоколе не очень сложны:

T' = D^V I^d = (r G^d)^V I^d = r^V G^dV I^d = r^V (IG^V)^d = r^V ≡ T(mod n).

поскольку G вычислялось таким образом, чтобы выполнялось соотношение IG^V ≡ 1 (mod n).

 

3 РАЗДЕЛЕНИЕ СЕКРЕТА

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

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

В схеме разделения секрета участвуют один дилер и n игроков. Изначально секрет находится у дилера, затем дилер вычисляет доли секрета и раздает их участникам, каждому участнику по одной доле. Обычно для схемы разделения секрета определен порог t: любая группа из t или более игроков, собравшись вместе, может восстановить секрет, но никакая группа из менее чем t игроков не сможет. Такую схему разделения секрета называют (t, n)-пороговая схема (англ. (t, n)-threshold scheme).

 

Мотивация

Надежная схема разделения секрета позволяет распределить доли секрета так, что любая коалиция из менее чем t игроков не сможет получить абсолютно никакой информации о секрете. Рассмотрим наивную схему разделения секрета, в которой секретное слово «пароль» делится на доли «па----», «--ро--» и «----ль». Допустим у хакера нету ни одной доли секрета, тогда ему придется пробовать все возможные шестибуквенные пароли, а это 336=1,2 млрд комбинаций. Если хакер сморг заполучить одну долю, то ему теперь придется угадать только четыре буквы, а это 334=1,2 млн комбинаций, что существенно меньше. Такая система ненадежна, так как коалиция из меньше чем t игроков может получить значительную информацию о секрете.

 

Тривиальная схема

Существует множество (t, n) - схем для которых t = n, то есть для восстановления секрета нужны все доли, например:

• Закодируем секрет как целое число s. Дадим всем игрокам кроме одного по случайному числу r_i, а последнему игроку дадим число r_n=s-r₁-r₂-…-r_n-1. Для восстановления секрета нужно сложить все числа r_i.
• Закодируем секрет как байт s. Дадим всем игрокам кроме одного по случайному байту r_i, а последнему игроку дадим байт r_n=s XOR r₁ XOR r₂ XOR … XOR r_n-1. Для восстановления секрета нужно применить ко всем числам r_i операцию XOR.

Когда объем используемой памяти некритичен, то можно использовать схемы такого рода для любого подмножества игроков применяя такую схему для каждой возможной коалиции игроков. Например, есть три игрока: Алиса, Боб и Кэрол. Чтобы создать схему в которой любые два игрока смогут восстановить секрет, мы можем создать три разных (2,2) схемы. Каждая схема даст нам две доли секрета. Две доли первой схемы дадим Алисе и Бобу, две доли второй схемы — Бобу и Кэрол, а две доли третьей схемы — Алисе и Кэрол. Однако такой подход очень быстро становится неэффективным вместе с ростом n u t.

 

3.3 Пример t ≠ n

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

 

Схема Блэкли

Две непараллельные прямые на плоскости пересекаются в одной точке. Три "непараллельные" плоскости в пространстве пересекаются тоже в одной точке. Вообще n n-мерных гиперплоскостей всегда пересекаются в одной точке. Одна из координат этой точки будет секретом. Если закодировать секрет как несколько координат точки, то уже по одной доле секрета (одной гиперплоскости) можно будет получить какую-то информацию о секрете, то есть о взаимозависимости координат точки пересечения. С помощью схемы Блэкли можно создать (t, n)-схему разделения секрета для любых t u n: для этого надо положить размерность пространства равную t, и каждому из n игроков дать одну гиперплоскость, проходящую через секретную точку. Тогда любые t из n гиперплоскостей будут однозначно пересекаться в секретной точке. Схема Блэкли менее эффективна чем схема Шамира: в схеме Шамира каждая доля такого же размера как и секрет, а в схеме Блэкли каждая доля в t раз больше. Существуют улучшения схемы Блэкли, позволяющие повысить ее эффективность.

 

Схема Шамира

Основная идея схемы Шамира заключается в том, что двух точек достаточно для задания прямой, трех точек — для задания параболы, четырех точек — для кубической параболы, и так далее. Чтобы задать многочлен степени n требуется n+1 точек. Допустим, мы хотим создать (k, n)-пороговую схему Шамира (k<n) для разделения секретного числа S. Выберем k - 1 случайных коэффициентов a₁, …, a_k-1, а также пусть a₀=S. Возьмем многочлен f(x) = a₀ + a₁x₁+ a₂x₂ + … + a_k-1x_k-1. Долями секрета будут являться n пар: (i, f(i)), где i=1…n. Имея k долей секрета можно вычислить все коэффициента многочлена, например с помощью интерполяционного многочлена Лагранжа, а значит и секрет S=a₀.

 

4 АЛГОРИТМ ЦИФРОВОЙ ПОДПИСИ ЭЛЬ ГАМАЛЯ (EGSA)

Название EGSA происходит от слов El Gamai Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSA, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Для того чтобы генерировать пару ключей (открытый ключ секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G<P. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.

Отправитель выбирает случайное целое число Х, 1<Х (Р-1), и вычисляет

Y = G^X mod P.

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

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

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

m = h(M), 1 < m < (P-1)

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

a = G^K mod P

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

m = X* a + K * b (mod (P-1))

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

S = (a, b)

проставляемую под документом М.

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

После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись S = (a, b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число

m = h(M),

т.е. хэширует принятое сообщение М.

Затем получатель вычисляет значение

A = Y * a^b (mod P)

и признает сообщение М подлинным, если, и только если

A = G^m (mod P).

Иначе говоря, получатель проверяет справедливость соотношения

Y^aa^b (mod P) = G^m (mod P).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S = (a, b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.

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

 

Пример

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

Y= G^X mod Р =Y= 2⁸ mod 11 = 3.

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

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

Действительно, НОД(9, 10)= 1.

Далее вычисляем элементы а и b подписи: a = G^K mod P* 2⁹ mod 11 = 6,

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

m = X * a + K * b (mod(P-1)).

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

5 = (6 * 8 + 9 * b) (mod 10) или 9 * b ≡ - 43 (mod10).

Решение: b = 3. Цифровая подпись представляет собой пару: а=6, b=3.

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

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

2) G^m (mod P) = 2⁵ (mod 11) =10 (mod 11).

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

 

5 ПРИМЕЧАНИЯ