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

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

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

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

 

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

 

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

 

Выполнил: студент Физико-математического  факультета, 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;

f ´X1 + d ´X2 = 1769 ´ (-23) + 550 ´ 74 = -40687 + 40700 = 13 = X3;

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

8. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë13/3û = 4.

T1 = X1 – Q ´ Y1 = (-23) – 4 ´ 37 = -171;

T2 = X2 – Q ´Y2 = 74 – 4 ´ (-119) = 550;

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

X1 = Y1 = 37;

X2 = Y2 = -119;

X3 = Y3 = 3.

Y1 = T1 = -171;

Y2 = T2 = 550;

Y3 = T3 = 1.

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

f ´T1 + d ´T2 = 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500= 1 = T3;

f ´X1 + d ´X2 = 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450 = 3 = X3;

f ´ Y1+ d ´ Y2= 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500 = 1 = Y3.

9. Y3 = 1.

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

T1 = X1 – Q ´Y1 = -171 – 1 ´ (-171) = 0;

T2 = X2 – Q ´Y2 = 550 – 1 ´ 550 = 0;

T3 = X3 – Q ´ Y3 = 1 – 1 ´ 1 = 0.

X1 = Y1 = -171;

X2 = Y2 = 550;

X3 = Y3 = 1.

Y1 = T1 = 0;

Y2 = T2 = 0;

Y3 = T3 = 0.

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

f ´T1 + d ´ T2 = 1769 ´ 0 + 550 ´ 0 = 0 = T3;

f ´X1 + d ´ X2 = 1769 ´ (-171) + 550 ´ 550 = - 302499 + 302500= 1 = X3;

f´Y1+d´Y2= 1769 ´ 0 + 550 ´ 0 = 0 = Y3.

Так как  на предыдущем (на восьмом) этапе 

f ´Y1+ d ´ Y2= 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500 = 1 = Y3,

и d ´Y2 = 1 + f ´ (-Y1),то d ´ Y2 º 1 mod 1769.

Основные  параметры вычислений занесены в  таблицу (табл.1.1).

Таблица 2.1 Параметры вычислений gcd(550, 1769) = 1

Этапы	Q	X1	X2	X3	Y1	Y2	Y3
0	-	1	0	1769	0	1	550
1	3	0	1	550	1	-3	119
2	4	1	-3	119	-4	13	74
3	1	-4	13	74	5	-16	45
4	1	5	-16	45	-9	29	29
5	1	-9	29	29	14	-45	16
6	1	14	-45	16	-23	74	13
7	1	-23	74	13	37	1119	3
8	4	37	-119	3	-171	550	1
9	1	-117	550	1	0	0	0

 

Ответ:gcd (550, 1769) = 1 и 550 ´ 550 º 1 mod 1769.

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

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

Известно, что:

[(a₁ mod n) ´ (a₂ mod n)] mod n = (a₁´ a₂) mod n.

Тогда, мы можем рассматривать промежуточные результаты по модулю n. Это намного облегчает вычисления. Будем вычислять a^bmod n.

Будем пользоваться следующим алгоритмом.

Степень b представляется в двоичной системе счисления. Через k будем обозначать номера разрядов полученного двоичного числа, начиная с нуля справа налево. Через b_i будем обозначать значение i-го разряда двоичного числа. Значение c в конце выполнения алгоритма будет соответствовать значению вычисленной степени.

На рис. 1.4 приводится блок-схема алгоритма быстрого возведения в степень для a^bmod n при больших значениях b.

Далее приводятся два примера, поясняющие работу данного  алгоритма.

Рис. 2.2. Блок-схема алгоритма быстрого вычисления a^bmod n

 

Пример 1: Вычислить a^bmodn, где a= 19, b = 5 и n= 119. Иначе, 19⁵ mod 119 =?

b = 5₁₀ = 101, k = 2, c = 0, d = 1, a = 19, n = 119.

1.k> 0, k = 2;

c = 2 ´ c = 2 ´ 0 = 0;

d = (d ´ d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;

b_k= b₂= 1;

c = c + 1 = 0 + 1 = 1;

d = (d ´ a) mod n = (1 ´ 19) mod 119 = 19 mod 119 = 19 - ë19 / 119û´ 119 = 19 – 0 ´119 = 19.

k = k – 1 = 2 – 1 = 1.

2.k> 0, k = 1;

c = 2 ´ c = 2 ´ 1 = 2;

d = (d ´ d) mod n = (19 ´ 19) mod 119 = 361 mod 119 = 361 - ë361 / 119û´ 119 = 361 – 3 ´ 119 = 361 – 357 = 4;

b_k= b₁= 0;

k = k – 1 = 1 – 1 = 0.

3. k> 0, k = 0;

c = 2 ´c = 2 ´ 2 = 4;

d = (d ´d) mod n = (4 ´ 4) mod 119 = 16 mod 119 = 16 - ë16 / 119û´ 119 = 16 – 0 ´ 119 = 16;

b_k= b₀= 1;

c = c + 1 = 4 + 1 = 5;

d = (d ´ a) mod n = (16 ´ 19) mod 119 = 304 mod 119 = 304 - ë304 / 119û´ 119 = 304 – 2 ´119 = =66.

k = k – 1 = 0 – 1 = -1.

Ответ: 19⁵ mod 119 = 66.

Пример 2: Вычислитьa^bmodn, гдеa= 66,b= 77иn= 119.Иначе, 66⁷⁷ mod 119=?

b = 77₁₀ = 1001101₂, k = 6, c = 0, d = 1, a = 66, n = 119.

1.k> 0, k = 6;

c = 2 ´c = 2 ´ 0 = 0;

d = (d ´d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;

b_k= b₆= 1;

c = c + 1 = 0 + 1 = 1;

d = (d ´ a) mod n = (1 ´ 66) mod 119 = 66 mod 119 = 66 - ë66 / 119û´ 119 = 66 – 0 ´119 = 66.

k = k – 1 = 6 – 1 = 5.

2.k> 0, k = 5; b₅= 0;

c = 2 ´c = 2 ´ 1 = 2;

d = (d ´ d) mod n = (66 ´ 66) mod 119 = 4356 mod 119 = 4356 - ë4356 /119û´ 119 = 4356 – (36´´ 119) = 4356 – 4284 = 72;

k = k – 1 = 4;

b_k= b₄= 0;

c = c ´ 1 = 2 ´ 2 = 4;

d = (d ´d) mod n = (72 ´ 72) mod 119 = 5184 mod 119 = 5184 - ë5184 / 119û´ 119 = 5184 – (43´119) = 5184 – 5117 = 67.

k = k – 1 = 4 – 1 = 3.

3.k> 0, k = 3; b₃= 1;

c = 2 ´ c = 2 ´ 4 = 8;

d = (d ´ d) mod n = (67 ´ 67) mod 119 = 4489 mod 119 = 4489 - ë4489 /119û´ 119 = 4489 – (37 ´´119) = 4489 – 4403 = 86;

c = c + 1 = 8 + 1 = 9;

d = (d ´ a) mod n = (86 ´ 66) mod 119 = 5676 mod 119 = 5676 - ë5676 / 119û´ 119 = 5676 – (47´´119) = 5676 – 5593 = 83.

k = k – 1 = 3 – 1 = 2; b₂= 1.

4.k> 0, k = 2; b₂= 1;

c = 2 ´ c = 2 ´ 9 = 18;

d = (d ´ d) mod n = (83 ´ 83) mod 119 = 6889 mod 119 = 6889 - ë6889 /119û´ 119 = 6889 – (57 ´´ 119) = 6889 – 6783 = 106;

c = c + 1 = 18 + 1 = 19;

d = (d ´ a)mod n = (106 ´ 66) mod 119 = 6996 mod 119 = 6996 - ë6996 / 119û´ 119 = 6996 – (58 ´119)= 6996 – 6902 = 94.

k = k – 1 = 2 – 1 = 1; b₁= 0.

5.k> 0, k = 1; b₁= 0;

c = 2 ´ c = 2 ´ 19 = 38;

d = (d ´d) mod n = (94 ´ 94) mod 119 = 8836 mod 119 = 8836 - ë8836 /119û´ 119 = 8836 – (74 ´´119) = 8836 – 8806 = 30;

b₁= 0;

6.k> 0, k = 0; b₀= 1;

c = 2 ´c = 2 ´ 38 = 76;

d = (d ´ d) mod n = (30 ´ 30) mod 119 = 900 mod 119 = 900 - ë900 /119û´ 119 = 900 – (7 ´ 119 == 900 – 833 = 67;

c = c + 1 = 76 + 1 = 77;

d = (d ´a)mod n = (67 ´ 66) mod 119 = 4422 mod 119 = 4422 - ë4422 / 119û´ 119 = 4422 – (37´´119) = 4422 – 4403 = 19.

k=k– 1 = 0 – 1 = -1.

Так как k< 0, то получен следующий ответ.

Ответ: 66⁷⁷mod119 = 19.

 

 

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

 

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

Этот  процесс состоит из двух частей:

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

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

 

В дальнейшем нам понадобятся некоторые важные понятия из теории чисел.

Число положительных  целых значений, которые меньше n и являются взаимно простыми с n, обозначается через f(n) и называется функцией Эйлера. Для простого числа p

f(p) =p– 1.

Если  имеется два простых числа p и q, тогда для n=pq получим f(n) =f(pq) =f(p) ´f(q) = (p-1) ´(q-1).

Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n a^f(n)º 1 mod n. Пример: a= 3, n = 10, f(n) =f(pq) =f(p) ´f(q) = (p-1) ´ (q-1) = (5-1) ´ (2-1) = 4.Следовательно,3⁴ = 81 º 1mod10.

Важным является следующее.

Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению a^mº 1 mod n, где m=f(n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются следующие названия:

• порядок числа a по модулю n;
• показатель, которому принадлежит a по модулю n;
• длина периода последовательности, генерируемой степенями a.

Пример 1. Рассмотрим степени числа 5 по модулю 19:

 

Поэтому в нашем примере, любые две  степени числа 5, показатели которых  отличаются на 9 (или на число, кратное 9), сравнимы по модулю 19. Иначе, последовательность является периодической с периодом, равным наименьшему положительному показателю m, при котором 5^m= 1 mod 19.

В общем случае можно сказать, что  наивысшим из показателей, которому может принадлежать число a по модулю n, является f(n). Числа, принадлежащие показателю f(n), называются первообразными корнями по модулю n.

В таблице (табл.2.1), в продолжение примера, приводятся степени целых чисел  по модулю 19 (первая выделенная строка соответствует степеням; затемненные  части строк соответствуют конкретным периодам).

Как видно, все последовательности заканчиваются числом 1.

 В нашем примере длина  последовательности является делителем f(19) = 18. Некоторые последовательности для a< 19 будут иметь длину 18. В таком случае говорят, что целое число a генерирует (своими степенями) множество всех ненулевых вычетов по модулю 19.

 Любое из этих  чисел называют первообразным  корнем по модулю 19.

Важность  этого понятия подтверждается тем, что если a является первообразным корнем n, его степени a¹, a²,…,a^f(n) оказываются различными по модулю n и взаимно простыми с n.

В частности, для простого числа p, если a является первообразным корнем p, то a¹, a²,…,a^p-1 оказываются различными по модулю n и взаимно простыми с n.

Как видно  из таблицы, для простого числа 19 его  первообразными корнями являются числа 2, 3, 10, 13, 14 и 15.

Не все целые числа  имеют первообразные корни. Этими  числами могут быть числа 2, 4, p^a и 2p^a, где p- любое нечетное простое число.

  Таблица 3.1 Степени целых чисел по модулю 19

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

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

 

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

 

Эффективность алгоритма Диффи-Хеллмана опирается  на трудностях вычисления дискрет-ных  логарифмов. В общем виде

yºg^x modp,

вычисление y при заданных g, x и p является относительно простой задачей даже при очень больших значениях x (имеются соответствующие эффективные алгоритмы). Однако если заданыy, g и p, то вычисление x (дискретное логорифмирование) является, вообще говоря, очень непростой задачей. Согласно [1], до недавного времени сложность асимптотически наиболее быстрого из известных алгоритмов вычисления дискретных логарифмов по модулю простого числа оценивалась величиной порядка

e^z, где z = ((lnp)^1/3ln (lnp))^2/3.

Теперь  рассмотрим алгоритм открытого распределения ключей Диффи-Хеллмана [1, 2]

Алгоритм  Диффи-Хелмана основывается на трудностях вычисления дискретных логарифмов.

Глобальные открытые элементы:

простое число p;

первообразный корень простого числа pÞa, где a<p.

Вычисление ключа пользователем  А:

Пользователь А выбирает случайное целое число X_A<p и вычисляет      Y_A = a^X_A modp.

X_A<p- секретная величина (закрытый ключ пользователя А);

Y_A - открытая величина (открытый ключ пользователя А).

Вычисление ключа пользователем  В:

Пользователь В выбирает случайное целое число X_В<p и вычисляет      Y_В = a^X_Вmodp.

X_В<p- секретная величина (закрытый ключ пользователя В);

Y_В - открытая величина (открытый ключ пользователя B).