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

Министерство образования Республики Беларусь

Учреждение образования

Могилевский Государственный Университет  им. А.А. Кулешова

 

Физико-математический факультет

 

Кафедра информатики

 

Выполнил: студент Физико-математического  факультета, 3 курс, группа «ВГ».  Климов Н.С.   Научный руководитель: доцент кафедры информатики, кандидат физ.-мат. наук, доцент Тимощенко Е.В.

Курсовой проект

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Могилев, 2012 

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ..............................................................................................................................3

 

1. Теоретические сведения.....................................................................................................5

 

2. Вспомогательные алгоритмы для  реализации шифрования...........................................8

 

2.1 Алгоритм Евклида - нахождения  наибольшего общего делителя................................8

 

2.2 Расширенный алгоритм Евклида  для вычисления мультипликативного  обратного.8

 

2.3 Алгоритм быстрого возведения  в степень для a^b mod n при больших значениях b.13

 

3. Алгоритм вычисления степеней  целого числа a^m по модулю p 
и целых чисел, принадлежащих показателю f(p),- первообразных корней по модулю p. Обмен ключами по схеме Диффи-Хеллмана..................................................................17

 

3.1 Алгоритм вычисления степеней  целого числа a^m по модулю p и целых чисел, принадлежащих показателю f(p), первообразных корней по модулю p. .......................17

 

3.2 Генерация и обмен секретными  ключами по схеме Диффи-Хеллмана  между пользователями сети.............................................................................................................20

 

4. Метод зашифровывания с открытым ключом RSA.......................................................24

5. Решение поставленной задачи методом RSA на языке С.............................................30

ЗАКЛЮЧЕНИЕ.....................................................................................................................31

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ.................................................................32

ПРИЛОЖЕНИЯ.....................................................................................................................33

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

Целью работы является освоение основных методов и алгоритмов криптографии с открытым ключом и тем самым закрепить знания практическими навыками использования криптографических методов с открытым ключом.

К основным задачам данной работы относятся:

−   изучение криптографических алгоритмов с открытым ключом;

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

 

1. Теоретические сведения

 

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

 

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

1. Безопасная система. Система считается безопасной, если она, используя соответствующие аппаратные и программные средства, управляет доступом к информации так, что только должным образом авторизованные лица или же действующие от их имени процессы получают право читать, писать, создавать и удалять информацию.
2. Дискретный логарифм. Для любого целого числа b и любого первообразного корня a простого числа p однозначно определяется показатель степени i, при котором b = aⁱmod p, где  
   0 £i£(p-1). Этот показатель степени и есть дискретный логарифм.
3. Зашифровывание данных. Процесс преобразования открытых данных в зашифрованные при помощи шифра.
4. Криптоанализ. Анализ криптографической системы и/или чувствительности данных, включая открытый текст.
5. Криптографическая защита. Это защита данных при помощи криптографического преобразования данных.
6. Криптографический алгоритм. Это алгоритм, который трансформирует данные с целью закрыть (скрыть) содержащуюся в них информацию и который при этом использует, по крайней мере, один секретный параметр.
7. Криптографический протокол. Установленный порядок действий абонентов при решении некоторой криптографической задачи (передача секретного сообщения, обмен ключами и др.).
8. Криптографическое контрольное значение. Это информация, получаемая в результате выполнения криптографического преобразования блока данных. Примечание. Контрольное значение может быть получено путем выполнения одного или нескольких шагов и является результатом математической функции ключа и блока данных. Оно обычно используется для проверки целостности блока данных.
9. Криптографическое преобразование. Это преобразование данных при помощи шифровывания и (или) выработки имитосвязи.
10. Криптография. Дисциплина, охватывающая принципы, средства и методы преобра-зования данных для сокрытия их информационного содержимого, предотвращения их от необнаруживаемой модификации и/или их несанкционированного использования.
11. Криптология. В общем виде криптологию называют наукой о шифрах. Криптология (образовано из греческих слов: «cryptos» — тайный и «logos» — слово) — это наука о создании и анализе систем безопасной связи, хотя тут скорее всего имеется в виду не безопасная, а секретная связь (секретность, как известно, является только одним из элементов безопасности или целостности информации).
12. Открытый ключ. Это открытая (несекретная) половина криптографической пары, используемая при шифровании с применением открытых ключей. Открытые ключи обычно используются при шифровании ключей сеансов, проверке цифровых подписей и шифровании данных, предназначенных для расшифровки соответствующим закрытым ключом.
13. Открытый текст. Это смысловые данные, семантическое содержание которых доступно, или это исходное сообщение (или исходная информация), которое должно быть преобразовано с целью защиты.
14. Пароль. 1) Это конфиденциальная информация аутентификации, обычно состоящая из строки знаков; 2) идентификатор субъекта доступа, который является его (субъекта) секретом.
15. Первообразный корень простого числа p. Это такое число a, что все числа amodp, a²modp, …,a^p-1modp являются разными и представляют все целые числа от 1 до (p-1) в некоторой перестановке.
16. Преобразование перестановки. Изменение порядка следования элементов открытого текста (при этом главным требованием является отсутствие потерь информации, то есть обратимость всех операций).
17. Продукционные шифры. Шифры, в которых применяются комбинации нескольких операций замены и перестановки.
18. Расшифровывание данных. Это процесс преобразования зашифрованных данных в открытые данные при помощи шифра.
19. Симметричная криптографическая система (криптосистема с секретным ключом). Отправитель и получатель используют один и тот же ключ для зашифровывания и для расшифровывания. Эти ключи либо совпадают, либо обладают некоторой симметрией.
20. Стойкость криптосистемы. Это способность противостоять попыткам криптоаналитика дешифровать зашифрованное сообщение (при этом предполагается, что криптоаналитик хорошо вооружен современными знаниями и различными средствами, а целью попытки является раскрыть ключи или нарушить целостность и (или) подлинность сообщения).
21. Цифровая подпись. Это шифрованная электронная подпись, формируемая с использованием цифрового сертификата, которая подтверждает подлинность макроса или документа, то есть наличие подписи говорит о том, что макрос или документ получен от владельца подписи, и он не был изменен.
22. Шифр. Это совокупность обратимых преобразований множества возможных открытых данных на множество возможных зашифрованных данных, осуществляемых по определенным правилам с применением ключей.
23. Шифрование. Процесс зашифровывания или расшифровывания;- криптографическое преобразование данных для получения шифротекста. Примечание. Шифрование может быть необратимым процессом, в связи с чем соответствующий процесс дешифрования невозможно реализовать.
24. Электронная цифрованная подпись. Это последовательность символов, полученная в результате криптографического преобразования исходной информации с использованием закрытого ключа электронной цифровой подписи, которая позволяет лицу, владеющему открытым ключом электронной цифровой подписи, установить целостность и неизменность этой информации, а также владельца закрытого ключа электронной цифровой подписи.

 

 

 

 

2. Вспомогательные алгоритмы для  реализации шифрования

2.1 Алгоритм Евклида - нахождения наибольшего общего делителя

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

Для любого неотрицательного числа X и любого положительного числа Y справедливо следующее:

gcd (X, Y) = gcd (Y, X mod Y),

где X>Y>0.

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

gcd (X, Y) = gcd (Y, XmodY) =gcd (Y, X– (ëX/Yû-целое частное) ´Y)).

Пример:gcd(18, 12)=gcd(12, 18mod12)=gcd(12, 18–1´ 12)=gcd(12, 6).gcd(12, 6) =gcd(6, 12mod6)=gcd(6, 12–2´6)=gcd(6, 0).

Ответ:gcd(18, 12) = 6.

2.2  Расширенный алгоритм Евклида для вычисления  
мультипликативного обратного

 

Если  gcd (d, f) = 1, то d имеет мультипликативное обратное по модулю f [1]. То есть, для положительного целого числа d<f существует такое d^-1<f, что dd^-1 = 1 mod f.По алгоритму Евклида нахождения наибольшего общего делителя чисел d и f, для случаев, когда делитель оказывается равным 1, естественно, можно получить и мультипликативное обратное d.

На рис.2.1 приводится общая блок-схема расширенного алгоритма Евклида.

Рис. 2.1. Расширенный алгоритм Евклида для вычисления мультипликативного обратного

 

Пример: gcd (d, f) =gcd(550, 1769). Вычислить мультипликативное обратное числа 550 по модулю 1769.

1.X1 = 1, X2 = 0, X3 =f= 1769;

Y1 = 0, Y2 = 1, Y3 =d= 550.

Q = ëX3/Y3û= ë1769/550û= 3.

T1 = X1 – Q ´ Y1 = 1 – 3´0 = 1;

T2 = X2 – Q ´Y2 = 0 – 3 ´ 1 = - 3;

T3 = X3 – Q ´ Y3 = 1769 – 3 ´ 550 = 119.

X1 = Y1 = 0;

X2 = Y2 = 1;

X3 = Y3 = 550.

Y1 = T1 = 1;

Y2 = T2 = -3;

Y3 = T3 = 119.

Соотношения:

f ´ T1 + d ´ T2 = 1769 ´ 1+ 550 ´ (-3) = 119 = T3;

f ´ X1 + d ´ X2 = 1769 ´ 0 + 550 ´ 1 =550 = X3;

f ´ Y1+ d ´ Y2= 1769 ´ 1+ 550 ´ (-3) = 119 = Y3.

2. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë550/119û = 4.

T1 = X1 – Q ´Y1 = 0 – 4 ´ 1 = -4;

T2 = X2 – Q ´ Y2 = 1 – 4 ´ (-3) = 13;

T3 = X3 – Q ´Y3 = 550 – 4 ´ 119 = 74.

X1 = Y1 = 1;

X2 = Y2 = -3;

X3 = Y3 = 119.

Y1 = T1 = -4;

Y2 = T2 = 13;

Y3 = T3 = 74.

Соотношения:

f ´T1 + d ´T2 = 1769 ´ (-4) + 550 ´ 13 = 7070 + 7150 = 74 = T3;

f ´X1 + d ´X2 = 1769 ´ 1 + 550 ´ (-3) = 1769 - 1650 = 119 = X3;

f ´ Y1+ d ´Y2= 1769 ´ 1+ 550 ´ (-3) = 1769 – 1650 = 119 = Y3.

3. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë119/74û = 1.

T1 = X1 – Q ´Y1 = 1 – 1 ´ (-4) = 5;

T2 = X2 – Q ´ Y2 = -3 – 1 ´ (13) = -16;

T3 = X3 – Q ´ Y3 = 119 – 1 ´ 74 = 45.

X1 = Y1 = -4;

X2 = Y2 = 13;

X3 = Y3 = 74.

Y1 = T1 = 5;

Y2 = T2 = -16;

Y3 = T3 = 45.

Соотношения:

f ´ T1 + d ´ T2 = 1769 ´ 5 + 550 ´ (-16) = 8845 + 8800 = 45 = T3;

f ´ X1 + d ´ X2 = 1769 ´ (-4) + 550 ´ (13) = -7076 + 7150 = 74 = X3;

f ´ Y1+ d ´ Y2= 1769 ´ 5+ 550 ´ (-16) = 8845 – 8800 = 45 = Y3.

4. Y3 ¹ 0; Y3 ¹ 1.

Q = ëX3/Y3û= ë74/45û = 1.

T1 = X1 – Q ´ Y1 = (-4) – 1 ´ 5 = -9;

T2 = X2 – Q ´Y2 = 13 – 1 ´ (-16) = 29;

T3 = X3 – Q ´ Y3 = 74 – 1 ´ 45 = 29.

X1 = Y1 = 5;

X2 = Y2 = -16;

X3 = Y3 = 45.

Y1 = T1 = -9;

Y2 = T2 = 29;

Y3 = T3 = 29.

Соотношения:

f ´ T1 + d ´ T2 = 1769 ´ (-9) + 550 ´ 29 = -15927 + 15950 = 29 = T3;

f ´ X1 + d ´ X2 = 1769 ´ 5 + 550 ´ (-16) = 8845 - 8800 = 45 = X3;

f ´ Y1+ d ´ Y2= 1769 ´ (-9)+ 550 ´ 29 = -15921 + 15950 = 29 = Y3.

5. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë45/29û = 1.

T1 = X1 – Q ´ Y1 = 5 – 1 ´ (-9) = 14;

T2 = X2 – Q ´Y2 = (-16) – 1 ´ 29 = -45;

T3 = X3 – Q ´Y3 = 45 – 1 ´ 29 = 16.

X1 = Y1 = -9;

X2 = Y2 = 29;

X3 = Y3 = 29.

Y1 = T1 = 14;

Y2 = T2 = -45;

Y3 = T3 = 16.

Соотношения:

f ´T1 + d ´T2 = 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = T3;

f ´X1 + d ´ X2 = 1769 ´ (-9) + 550 ´ 29 = -15921 + 15950 = 29 = X3;

f ´Y1+ d ´ Y2= 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = Y3.

6. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë29/16û = 1.

T1 = X1 – Q ´Y1 = (-9) – 1 ´ 14 = -23;

T2 = X2 – Q ´ Y2 = 29 – 1 ´ (-45) = 74;

T3 = X3 – Q ´ Y3 = 29 – 1 ´ 16 = 13.

X1 = Y1 = 14;

X2 = Y2 = -45;

X3 = Y3 = 16.

Y1 = T1 = -23;

Y2 = T2 = 74;

Y3 = T3 = 13.

Соотношения:

f ´ T1 + d ´ T2 = 1769 ´ (-23) + 550 ´ 74 = -40687 + 40700= 13 = T3;

f ´X1 + d ´X2 = 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = X3;

f ´Y1+ d ´Y2= 1769 ´ (-29) + 550 ´ 74 = -40687 + 40700 = 13 = Y3.

7. Y3 ¹ 0; Y3 ¹ 1.

Q = ëX3/Y3û= ë16/13û = 1.

T1 = X1 – Q ´Y1 = 14 – 1 ´ (-23) = 37;

T2 = X2 – Q ´Y2 = (-45) – 1 ´ 74 = -119;

T3 = X3 – Q ´Y3 = 16 – 1 ´ 13 = 3.

X1 = Y1 = -23;

X2 = Y2 = 74;

X3 = Y3 = 13.

Y1 = T1 = 37;

Y2 = T2 = -119;

Y3 = T3 = 3.

Соотношения:

f ´ T1 + d´T2 = 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450= 3 = T3;