Криптография с открытым ключом. 2

Национальный  исследовательский  университет

МОСКОВСКИЙ  ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ) 
 
 
 
 
 
 
 
 
 
 
 

КУРСОВАЯ  РАБОТА

ПО  КУРСУ

«Криптография с открытым ключом» 
 
 
 
 
 
 
 
 
 
 
 
 

Студент:	Калмыков  А.В.
Группа:	А-4-10
Преподаватель:	Набебин А.А.

Москва 2012

Оглавление

ВВЕДЕНИЕ 3

1. КРИПТОГРАИЧЕСКАЯ СИСТЕМА RSA 5

1.1. Криптосистема RSA 5

1.2. Электронная цифровая подпись RSA с возвратом сообщения 6

1.3. Электронная цифровая подпись RSA с hash-функцией 8

2. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА ЭЛЬ-ГАМАЛЯ С ПРОСТЫМ ПОЛЕМ ГАЛУА 9

2.1. Шифросистема Эль-Гамаля с простым полем Галуа 9

2.2. Электронная цифровая подпись Эль-Гамаля с простым полем Галуа 11

3. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА ЭЛЬ ГАМАЛЯ С ОБЩИМ ПОЛЕМ ГАЛУА 12

3.1. Шифросистема Эль-Гамаля с общим полем полем Галуа 12

3.2. Электронная цифровая подпись Эль-Гамаля с общим полем Галуа 15

4. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА DSA 17

4.1. Электронная цифровая подпись DSA 17

5. MATHCAD ПРОГРАММНЫЙ ПРОЦЕССОР 20

6. ПРИМЕРЫ ИСПОЛЬЗУЕМЫХ MATHCAD-ПРОГРАММ 24

6.1. Криптосистема RSA 24

6.2. Электронная цифровая подпись RSA с возвратом сообщения 25

6.3. Электронная цифровая подпись RSA с hash-функцией 26

6.4. Шифросистема Эль-Гамаля с простым полем Галуа 27

6.5. Электронная цифровая подпись Эль-Гамаля с простым полем Галуа 28

6.6. Шифросистема Эль-Гамаля с общим полем полем Галуа 29

6.7. Электронная цифровая подпись Эль-Гамаля с общим полем Галуа 30

6.8. Электронная цифровая подпись DSA 32

ЛИТЕРАТУРА 32 
 
 
 
 
 
 
 
 
 
 
 

     ВВЕДЕНИЕ

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

Впервые, публично, Диффи и Хеллман в 1976 году изложили идею

разработанного  метода на национальной компьютерной конференции и

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

независимо от Диффи и Хеллмана пришел к тем же конструкциям, однако

опубликовал свои результаты только в 1978 году. Криптография с открытм ключем. Текущее состояние Однако, истинную точку отсчета криптографии с открытым ключом, следует отнести к более раннему времени. Известно несколько независимых источников, которые отдают пальму первенства, в разработке криптографии с открытым ключем, Агентству национальной безопасности США (National Security Agency - NSA).

По словам адмирала Бобби Инман (Bobby Inmann), занимал пост главы Агентства, метод криптографических преобразований с открытым ключом разработан NSA еще в середине 60-х годов. Первое документальное подтверждение этому,  появилось в 1970 году в закрытом отчете Джеймса Эллиса (James Ellis) из Группы

защиты электронных  коммуникаций Службы безопасности Великобритании.

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

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

исследований  состоит в поиске наиболее слабых достаточных условий для

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

предположения двух типов – общие (или теоретико-сложностные) и теоретико-числовые, т.е. предположения о сложности конкретных теоретико-числовых задач.

На основе указанных  принципов была предложена трудноразрешимая задача

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

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

Применение криптосистем с открытым ключом.

Двигателем данного  направления криптографии является, в первую очередь,

практика. Стремительное  развитие информационных систем ставит все новые и новые задачи перед разработчиками криптографических алгоритмов (протоколов).

Классифицируем  наиболее существенные побудительные  мотивы развития

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

     • Развитие телекоммуникационных систем и сетей различного назначения.

     • Развитие глобальной сети Интернет.

     • Развитие банковских систем, в том  числе и пластиковых карт.

     • Потребность мыслящего человека к познанию.

Выделяют следующие основные (глобальные, в самом широком смысле)

направления применения криптографических преобразований с открытым

ключом:

     • зашифровывание и расшифровывание;

     • выработка общего секрета или  обмен ключами;

     • наложение и проверка электронной  цифровой подписи;

     • аутентификация;

     • «электронные деньги».

Каждому, из перечисленных  направлений, присуща собственная  процедура

применения открытого  или личного кличей.

В современных  условиях, для решения задач защиты информации могут

применяться криптографические  алгоритмы, которые могут решать как одну, так и

несколько задач (из выше перечисленных). Алгоритм RSA [2], например, с

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

подписи. Однако все универсальное не лишено недостатков. Для успешного

противостояния  криптоаналитикам и повышения эффективности алгоритма, были

предложены различные  модификации RSA [ ], решающие указанные задачи по

отдельности

1. КРИПТОГРАИЧЕСКАЯ СИСТЕМА RSA
1. Криптосистема RSA

Зашифровать и  расшифровать сообщение с помощью  криптосистемы RSA     (R. Rivest, A. Shamir, L. Adleman). Простые числа p и q определяются вариантом задания. В качестве исходного текста взять три первых латинских буквы своей фамилии.

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

1. Выбрать два больших различных простых числа p и q примерно одного размера.
2. Найти n = pq и функцию Эйлера φ = φ(n) = (p - 1)(q - 1).
3. Взять случайное число e, 1<e< φ такое, что нод(e, φ) = 1.
4. Найти такое целое a (1, φ), что ea ≡ 1 (mod φ). Для этого с помощью расширенного алгоритма Евклида найти такие целые a, x, что ea + φx = 1. Тогда    ea ≡ 1 (mod φ). Пусть произвольное k Z. Сложив ea ≡ 1 (mod φ) и ekφ ≡ 0 (mod φ), получим e(a + kφ) ≡ 1 (mod φ). Если a (1, φ), то найти такое целое k, что                  a + kφ (1, φ), и в качестве a взять a + kφ.
5. Открытый ключ адресата есть пара чисел (n,e). Секретный ключ адресата есть число a.

Шифрование. Адресат A шифрует свой текст t и отправляет его адресату B. B дешифрует сообщение от A и получает исходный текст t. Адресат A должен выполнить следующее:

1. Получить открытый ключ (n,e) адресата B.
2. С помощью какого-либо метода M, который публикуется, представить своё письмо t как сообщение в виде натурального числа m из сегмента [0, n-1].
3. Вычислить шифротекст c = m^e (mod n).
4. Отправить свой шифротекст c адресату B.

Дешифрование. Чтобы извлечь текст t из шифротекста c, адресат B должен выполнить следующее:

1. Взять свой секретный ключ a и вычислить сообщение m = c^a (mod n).
2. Вычислить текст t адресата A с помощью метода M.

Пример.

Адресат A пишет письмо t = KAL адресату B.

Вычисление  ключей. Адресат B выполняет следующее:

1. Выбирает два разных простых числа p = 5783, q = 5647.
2. Вычисляет n = pq =32656601 и функцию Эйлера φ = (p - 1)(q - 1) = 32645172.
3. Выбирает случайное число e = 3051835 (1, φ) с нод(e, φ) = 1.
4. С помощью расширенного алгоритма Евклида находит такое a = 13331995 (1, φ), что ea ≡ 1 (mod φ).
5. Открытый ключ адресата B есть пара чисел (n = 32656601, e = 3051835). Секретный ключ адресата B есть число a =13331995  .

Шифрование. Адресат А выполняет следующее:

1. Получает открытый ключ (n = 32656601, e = 3051835) адресата B.
2. Представляет свой текст t = KAL в виде натурального числа m из [0, n-1] с помощью 27-ричной системы счисления следующим образом. Нумеруются буквы алфавита:

   Текст KAL представляется в виде числа m = 12 * 27² + 1 * 27 +12 = 8059

3. Шифрует своё сообщение m = 8059 числом c = m^e (mod n) = 8059^3051835 (mod 32656601) = 726893.
4. Посылает свой шифротекст c адресату B.

Дешифрование. Чтобы дешифровать шифротекст c от A, адресат B выполняет следующее:

1. Находит (с помощью своего секретного ключа a) число m = c^a (mod n) = 726893^13331995 (mod 32656601) = 8059.
2. Представляет число m в 27-ричной системе счисления: m = (11 1 12)₂₇ и получает исходный текст KAL.

Замечание. Криптографическая стойкость криптосистемы RSA основана на трудной практической осуществимости проблемы факторизации больших чисел. На практике для криптографической стойкости модуль n задаётся двоичным числом с 1024 и более двоичными разрядами.

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

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

2. Электронная цифровая подпись RSA с возвратом сообщения

Зашифровать и расшифровать сообщение с помощью  криптосистемы RSA (R. Rivest, A. Shamir, L. Adleman) с электронной подписью. Простые числа p и q взять из задачи 29. В качестве исходного текста взять три первых латинских буквы своей фамилии.

     p = 324733,   q = 27061,   t = KAL.

Алгоритм:

Вычисление  ключей. Каждый адресат создает открытый ключ и ему соответствующий секретный ключ. Адресат должен выполнить следующее.

     1. Выбрать два больших различных  случайных простых числа p и q примерно одного размера.

     2.  Найти n = p ∙ q и функцию Эйлера φ = φ(n) = (p − 1)(q − 1).

     3.  Взять случайное число  e, 1 < e < φ, такое, что нод(e, φ) = 1.

     4.  Найти такое целое a (1, φ), что ea ≡ 1 (mod φ). С помощью расширенного алгоритма Евклида найти то единственное целое a, 1 < d < φ, для которого ea ≡ 1 (mod φ).

     5. Открытый ключ адресата есть  пара чисел (n, e). Секретный ключ адресата есть число a. 

     Вычисление подписи. Адресат А подписывает свой текст t. Любой адресат B может проверить подпись A и извлечь из нее текст t. Адресат A должен выполнить следующее.

1. Каким – либо методом M (который публикуется) представить свой текст t в виде целого числа m, 1 < m < n – 1.
2. Найти число w = R(m) с помощью открытой функции

R : [0, n – 1] → M_R , где M_R есть некоторое числовое множество, например,

R(m) = m*m, где a*b есть результат приписывания слова b к слову a. Тогда M_R = {w = m*m: m [0, n – 1]}.

     3.  Найти число s = w ^a(mod n).

     4.  Отправить подписанный шифротекст s адресату В. 

     Проверка подписи и вычисление сообщения. Чтобы проверить подпись s адресата A и извлечь из нее сообщение m, адресат B должен выполнить следующее.

1. Получить открытый ключ (n, e) адресата A.
2. Найти число w = s ^e(mod n).
3. Проверить, что w M_R . Если нет, отвергнуть подпись s.
4. Найти число m = R^–1(w).
5. С помощью метода M найти отправленный текст t.

Решение:

   Адресат A подписывает свой текст t. Любой адресат B может проверить подпись A.

     Вычисление ключей. Адресат А выполняет следующее.

     1.  Выбирает разные простые  числа p = 324733,   q = 27061.

     2.  Находим n = p ∙ q = 324733 * 27061 = 8787599713 и функцию Эйлера

φ = φ(n) = (p − 1)(q − 1) = 324732 * 27060 = 8787247920.

     3.  Выбирает случайное число  e = 23, 1 < e < φ, с нод(e, φ) = 1.

     4. С помощью расширенного алгоритма  Евклида находит то единственное  целое a = 1910271287 (1, φ), которое удовлетворяет сравнению ea ≡ 1 (mod φ).

     5. Открытый ключ для А есть пара (n = 8787599713, e = 23). Секретный ключ для А есть число a = 1910271287.

     Вычисление подписи.  Адресат А подписывает свой текст t = KAL и выполняет следующее.

1. Представим свой текст t = KAL числом каким – либо методом M, например, в 27 – ричной системе счисления числом 

m = 11 * 27² +1 * 27 + 12 = 8058.

Нумеруются  буквы алфавита: 

2. Вычисляет w = R(m) = R(8058) = 8058*8058 =80588058.

     3.  Вычисляет подпись

  s = w ^a(mod n) = 80588058^1910271287 (mod 8787599713) = 4604486656.

     4.  Отправляет подписанный шифротекст s адресату В. 

     Проверка подписи  и вычисление сообщения.  Адресат B получает от A подписанный шифротекст s и делает следующее.

1. Получить открытый ключ (n = 8787599713, e = 23) адресата A.
2. С помощью открытого ключа (n, e) адресата А вычисляет:

  w = s ^e(mod n) = 4604486656²³ (mod 13374982717) = 80588058.

3. Так как w =80588058=8058*8058 и M_R  , то B принимает

подпись А.

4. Вычисляет  m = R^–1(w) = 8058.
5. Представляет число  m = (8058)₁₀   в 27 – ричной системе счисления

m = (11 1 13)₂₇ и получает исходный текст t = KAL.

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

3. Электронная цифровая подпись RSA с hash-функцией

Теоретическое введение:

Криптографическая хэш-функция h — это функция, определенная на битовых строках произвольной длины со значениями в строках  битов фиксированной длины. Ее значение часто называют хэш-кодом или  хэш-значением. В информатике тоже используются своего рода хэш-функции, но важное отличие криптографических хэш-функций от стандартных состоит в том, что первые должны быть односторонними. Другими словами, должно быть невозможно в вычислительном отношении по элементу Y из множества значений хэш-функции подобрать такой х из области определения, при котором h(x) = Y. Другая характеризация односторонних хэш-функций — сказать о них, что они защищены от восстановления прообразов. Применение криптографических хэш-функций позволяет создать схему подписи RSA без восстановления сообщения, что намного эффективней для длинных сообщений.

Задача  №24.6

       Зашифровать и расшифровать сообщение с помощью криптосистемы RSA (R. Rivest, A. Shamir, L. Adleman) хэш-функцией. Простые числа p и q взять из задачи 29. В качестве исходного текста взять три первых латинских буквы своей фамилии.