Лаб Раб ЗИ_6-Шифрование с открытым или асимметричным ключом. Лабораторная работа 6 Основы криптографической защиты информации Шифрование с открытым или асимметричным ключом Введение

• Название: Лабораторная работа 6 Основы криптографической защиты информации Шифрование с открытым или асимметричным ключом Введение
• Анкор: LAB_1
• Дата: 30.10.2019
• Размер: 55 Kb.
• Имя файла: Лаб Раб ЗИ_6-Шифрование с открытым или асимметричным ключом.doc
• Тип: Лабораторная работа; #92569

Лабораторная работа №6

Основы криптографической защиты информации

Шифрование с открытым или асимметричным ключом

Введение

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

1. Цель работы

Изучение методов криптографической зашиты информации. Шифрование с открытым или асимметричным ключом
2. Краткие сведения из теории

Методы криптографии. Реализация алгоритма RSA.

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

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

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

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

Существуют два класса криптосистем:

• 
  симметричные (классическая криптография);
  
• 
  ассиметричные (криптография с открытым ключом).
  

В системах шифрования с открытым или асимметричным ключом (public/assymmetric key) используется два ключа. Один из ключей, называемый открытым, несекретным используется для шифрования сообщений, которые могут быть расшифрованы только с помощью секретного ключа, имеющегося у получателя, для которого предназначено сообщение. Либо для шифрования сообщения может использоваться секретный ключ и если сообщение можно расшифровать с помощью открытого ключа, то подлинность отправителя будет гарантирована (система электронной подписи). Открытый ключ зашифровки не совпадает с секретным ключом расшифровки. Этот принцип изобретен Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г.

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

Среди несимметричных алгоритмов наиболее известен алгоритм RSA, разработанный учеными Роном Ривестом (Ron Rivest), Ади Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman) в 1978 г.

Шифрование с использованием алгоритма RSA

Задача, положенная в основу метода состоит в том, чтобы найти такую функцию y=f(x), чтобы получение обратной функции x=f^-1(y), было бы в общем случае очень сложной задачей (NP-полной задачей), однако, если знать некую секретную информацию, то сделать это существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом. Например, получить произведение двух чисел n=p*q просто, а разложить n на множители, если p и q достаточно большие простые числа, сложно.

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

1. 
   Случайно выбрать два очень больших простых целых числа p и q (длина десятичной записи каждого из чисел p и q не меньше 100, в реальных приложениях используют числа порядка 200-400 десятичных цифр).
   
2. 
   Вычислить произведение n= p*q. Число n открытое, однако разложение n на множители - секретное
   
3. 
   Выбрать большое случайное целое число d, не имеющее общих сомножителей с числом m=(p-1)*(q-1).
   
4. 
   Определить число e, чтобы выполнялось (e*d) mod ((p-1)*(q-1))=1.
   

Тогда открытым ключом (public key) будут числа {e, n}, а секретным ключом (private key) - числа {d, n}.

Теперь, чтобы зашифровать данные по известному ключу {e, n}, необходимо сделать следующее:

• 
  Разбить шифруемый текст на блоки, где i-й блок может быть представлен в виде числа m(i)=0,1,2..., n-1. Их должно быть не более n-1.
  
• 
  Зашифровать текст, рассматриваемый как последовательность чисел m(i) по формуле c(i)=(m(i)^e)mod n.
  

Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необходимо вычислить: m(i) = (c(i)^d) mod n. В результате будет получено множество чисел m(i), которые представляют собой исходный текста.

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

Зная открытый ключ {e, n}, можно вычислить значение закрытого ключа d. Необходимым промежуточным действием в этом преобразовании является нахождение чисел p и q, для чего нужно разложить на простые множители очень большое число n, а на это требуется очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множители связана высокая криптостойкость алгоритма RSA, основанная на предположении, что исключительно трудно определить секретный ключ по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Если использовать числа, состоящие из 200 цифр, для несанкционированной расшифровки придется генерировать огромное число операций (около 10^23).

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

В связи со схемой RSA возникает ряд алгоритмических задач.

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

Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна
Пример 1. Зашифруем и расшифруем сообщение "САД".

1. 
   Выбираем p=3 и q=11 (числа на самом деле должны быть большими).
   
2. 
   Находим n=3*11=33.
   
3. 
   Определяем (p-1)*(q-1) = 20. Следовательно, d будет равно, например d=3.
   
4. 
   Выберем e по следующей формуле (e*3) mod 20=1. Например, e=7.
   
5. 
   Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 32 (кончается на n-1). Буква А =1, В=2, Д=3.
   

Теперь зашифруем сообщение, используя открытый ключ {7,33}

• 
  C1 = (3^7) mod 33 = 2187 mod 33 = 9;
  
• 
  C2 = (1^7) mod 33 = 1 mod 33 = 1;
  
• 
  C3 = (2^7) mod 33 = 128 mod 33 = 29.
  

Криптотекст - 9 1 29.

Теперь расшифруем эти данные, используя закрытый ключ {3,33}.

• 
  M1=(9^3) mod 33 =729 mod 33 = 3(С);
  
• 
  M2=(1^3) mod 33 =1 mod 33 = 1(А);
  
• 
  M3=(29^3) mod 33 = 24389 mod 33 = 2(Д).
  

Таким образом, все данные расшифрованы.
Пример 2. Зашифруем и расшифруем сообщение "12345".

1. 
   p=3, q=7.
   
2. 
   n=p*q=21.
   
3. 
   (p-1)*(q-1)=12, откуда d=5.
   
4. 
   (e*5) mod 12=1, откуда e=17.
   

Открытый ключ {17, 21}, секретный – {5, 21}.

• 
  C(1)= 1¹⁷ mod 21= 1
  
• 
  C(2)= 2¹⁷ mod 21 =11
  
• 
  C(3)= 3¹⁷ mod 21= 12
  
• 
  C(4)= 4¹⁷ mod 21= 16
  
• 
  C(5)= 5¹⁷ mod 21= 17
  

Криптотекст — 1 11 12 16 17.

Расшифруем:

• 
  M(1)= 1⁵ mod 21= 1
  
• 
  M(2)= 11⁵ mod 21= 2
  
• 
  M(3)= 12⁵ mod 21= 3
  
• 
  M(4)= 16⁵ mod 21= 4
  
• 
  M(5)= 17⁵ mod 21= 5
  

Очевидно, результат совпал.
Зная открытый ключ {e, n}, можно вычислить значение закрытого ключа d. Необходимым промежуточным действием в этом преобразовании является нахождение чисел p и q, для чего нужно разложить на простые множители очень большое число n, а на это требуется очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множители связана высокая криптостойкость алгоритма RSA, основанная на предположении, что исключительно трудно определить секретный ключ по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Если использовать числа, состоящие из 200 цифр, для несанкционированной расшифровки придется генерировать огромное число операций (около 10^23).

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

В связи со схемой RSA возникает ряд алгоритмических задач.

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

Задание:

Написать программу, кодирующую и декодирующую произвольное пятибуквенное сообщение, записанное в текстовом файле, с помощью алгоритма RSA.