Шифрование по алгоритму RSA

ОСНОВЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

 

Задания на курсовую работу с методическими указаниями для студентов V курса

 

Специальностей

 

….

 

 

Москва – 2015

 

 

Составитель: к.ф.-м.н., доцент И.М. Губенко

 

___________________

(подпись)

 

© Российская Открытая Академия Транспорта

Московского Государственного Университета Путей Сообщения, 2015

1. СОДЕРЖАНИЕ РАБОТЫ

 

Курсовая работа по дисциплине ”Основы информационной безопасности” выполняется студентами V курса. Работа заключается в шифровании информации различными криптоалгоритмами.

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

 

2. ИСХОДНЫЕ ДАННЫЕ

 

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

Таблица 1

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

 

 

Ключи шифрования:

K1=Фамилия

K2=ddmm (день и месяц рождения, 4 цифры, цифру 0, если она есть в дате, заменить на 9)

Число М:

Если последняя цифра учебного шифра – простое число, то M=№ последней цифры учебного шифра{mod 11} (если M=0, то M=9, если M=1, то M=8), иначе M=№ последней цифры учебного шифра.

Выбор р и q (по последней цифре учебного шифра):

1. p=11 и g=3

2. p=13 и g=3

3. p=19 и g=7

4. p=9 и g=5

5. p=7 и g=3

6. p=4 и g=7

7. p=7 и g=11

8. p=8 и g=13

9. p=17 и g=4

10. p=13 и g=6.

 

ЗАДАНИЯ

 

1. Зашифровать перестановкой P (между словами пробел) на ключе K1.

2. Зашифровать P (между словами пробел) многоалфавитной подстановкой на ключе K2.

3. Зашифровать и расшифровать M по алгоритму RSA (выбор ключей начать с p=3, q=11 для четных значений вариантов и с p=5, q=7 для нечетных значений вариантов).

4. Зашифровать и расшифровать M по алгоритму Эль-Гамаля. Выбор ключей:

 

4. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

Операция mod

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

Таким образом, по определению:

Разделить целое число а на натуральное число b > 0 с остатком, значит представить его в виде:

где q – неполное частное , а r - остаток от деления а на b. При этом и .

Шифры перестановки.

Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки (ШП).

Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью матрицы:

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

Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка:

и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА.

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

n
n!

При больших для приближенного вычисления можно пользоваться известной формулой Стирлинга:

где e= 2,718281828.

4.3. Шифры замены

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

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

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

Таблица 2

Ключ шифра замены

А	B	C	….	Z
МА	МB	МC	….	МZ

 

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

Система RSA

В 1978 году Риверст, Шамир и Адлеман (США) предложили пример функции f(x) для шифрования, обладающей рядом достоинств. На ее основе была построена одноименная система шифрования (по первым буквам фамилий).

Достоинства этой функции:

· Существует достаточно быстрый алгоритм вычисления значения функции f(x)

· Существует достаточно быстрый алгоритм вычисления обратной функции f^-1(x)

· Функция f(x) обладает секретом, знание которого позволяет быстро вычислить

f ^-1(x); в противном случае вычисление становится невозможным.

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

Рассмотрим алгоритмы шифрования и дешифрования.

1. Выбираются простые числа Р и Q

2. Генерируется сообщение М = 8

3. Вычисляется значение N = Р·Q

4. Вычисляется значение φ = (Р-1) ·(Q-1)

5. Выбирается число D, взаимно простое с φ, то есть НОД (D, φ) = 1:

6. Выбирается число Е, такое что (Е, φ) = 1(Mod φ).

7. Проверяется условие: D · Е = 1 Mod (φ).

Таким образом, получаем пару (Е, N), то есть открытый ключ и пару закрытых ключей (D, N).

Тогда шифрование и дешифрование сообщения М соответственно:

С = (M^Е) Mod N.

M = (C^D) Mod N.

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

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

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

Схема Эль - Гамаля

Схема Эль - Гамаля (Elgamal) – ассиметричная криптосистема, использующая одностороннюю функцию возведения в степень. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Данная схема лежит в основе стандартов электронной подписи в США (DSA) и России (ГОСТ Р 34.10 - 94).

Односторонней называется функция вида Р: Х →Y, обладающая двумя свойствами:

1. Существует полиномиальный алгоритм вычисления значения функции Y по известному значению Х;

2. Не существует полиномиальный алгоритм вычисления значения функции X по известному значению Y.

Рассмотрим в рамках данного методического пособия работу алгоритма в режиме шифрования.

Алгоритм генерации ключей

1. Получатель сообщения выбирает два случайных числа Р и G, таких что ;

2. Получатель сообщения выбирает случайное целое число Х, такое что ;

3. Вычисляется

4. Открытым ключом (OK) является тройка , секретным (SK) – .

Алгоритм шифрования

Сообщение шифруется следующим образом:

1. Выбирается сессионный ключ – случайное целое число , такое что ;

2. Вычисляются числа

3. Пара чисел и является шифротекстом.

Алгоритм дешифрования

M = b/(a^x)^-1= M · (Y^К) Mod P / [(G^К) Mod P]

 

5. ПРИМЕРЫ

Шифр перестановки

Пусть необходимо зашифровать сообщение

Р = ”информационная_безопасность” (N=27). Тогда c учетом пробела: Р* = ”информационная_безопасность_” (N=28).

K1=ГУБЕНКО (m=7)

Разобьем Р* на блоки длиной m (в данном примере на 7):

 

Р1*	и	н	ф	о	р	м	а
Р2*	ц	и	о	н	н	а	я
Р3*	_	б	е	з	о	п	а
Р4*	с	н	о	с	т	ь	_

 

Условие m < P* выполняется.

Тогда:

 

К1*
Б	Г	Е	К	Н	О	У
К1

 

Составим криптограмму согласно С_i = P* _K1[i]

 

C1*	н	а	и	ф	р	о	м
C2*	и	я	ц	о	н	н	а
C3*	б	а	_	е	о	з	п
C4*	н	_	с	о	т	с	ь

Запишем полученную криптограмму в строку:

С= “наифромияцоннаба_еозпн_стось”

 

Шифр замены

Пусть необходимо зашифровать сообщение

Р = ”информационная_безопасность” (равно 27).

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

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

ю

я

_

 

К2= 9594 (N=4).

Разобьем исходный текст Р на блоки длиной N:

и

н

ф

о

р

м

а

ц

и

о

н

н

а

я

_

б

е

з

о

п

а

с

н

о

с

т

ь

 

Составим криптограмму, сдвигая каждый символ фразы на i число шагов в алфавите. Получим :

с

т

э

т

щ

с

и

ь

с

у

ц

с

и

г

з

ч

е

н

м

ч

у

и

ц

т

ь

ч

в

 

Таким образом, зашифрованный текст С = ”стэтщсиьсуцсигзченмчуцтьчв”.

Шифрование по алгоритму RSA

 

6. Пусть Р=3, Q=11 (простые числа)

7. Пусть сообщение М = 8

8. Вычисляем значение N = Р·Q=33

9. Вычисляем значение φ = (Р-1) ·(Q-1)=20

10. Выбираем число D, взаимно простое с φ, то есть НОД (D, φ) = 1:

Пусть D = 3 (условие НОД (D, φ) = 1 выполняется ).

6. Выбираем число Е, такое что (Е, φ) = 1(Mod φ). Тогда пусть Е = 7. Проверяем условие: D · Е = 1 Mod (φ).

Таким образом, получаем пару (Е, N), то есть открытый ключ, - (7,33) и пару закрытых ключей (D, N) – (3,33).

Тогда шифрование и дешифрование сообщения М соответственно:

С = (M^Е) Mod N = 8⁷ Mod 33 = 2.

M = (C^D) Mod N = 2³ Mod 33 = 8.