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

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование

чом.

К основным задачам, стоящим перед написанием работы Криптография с открытым ключом относятся:

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

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

В результате выполнения данного выпускной квалификационной работы:

Освоил математические основы и наиболее распространенные алгоритмы криптографии с открытым ключом;

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

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

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

 

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

 

1.1 Проблемы традиционных методов шифрования

 

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

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

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

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

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

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

 

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

 

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

 

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

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

 

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

где X>Y>0.

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

gcd (X, Y) = gcd (Y, X mod Y) = gcd (Y, X - (X/Y - целое частное) Y)).

Пример: gcd (18, 12) = gcd (12, 18 mod 12) = gcd (12, 18 - 1 12) = gcd (12, 6). gcd (12, 6) = gcd (6, 12 mod 6) = gcd (6, 12 - 2 6) = gcd (6, 0).

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

Блок-схема алгоритма Евклида приводится на рис.1.2. (слайд 1.3.).

 

Рис. 1.2. Блок-схема алгоритма нахождения наибольшего общего делителя

Рассмотрим конкретный пример и решим поставленную задачу согласно приведенному алгоритму вычисления EUCLID (d, f) [1]. В алгоритме d> f> 0 и достаточно рассмотреть только положительные целые числа, так как gcd (a, b) = gcd (a, b).

Пример Е: Найти EUCLID (d, f) для d = 1970, f = 1066.

EUCLID (1970, 1066) = ?

Ответ: gcd (1970, 1066) = 2.

dc

 

1.1.3 Инструкция по выполнению задания 1

Проанализировать приведенный пример Е. Выбрать два числа d и f, таких, что d> f и d>200, а f>100. Определить по заданному алгоритму Евклида вручную, с использованием калькулятора (или составив программу на любом языке программирования), наибольший общий делитель чисел d и f ? EUCLID (d, f).

Полученный ответ и исходные данные d и f ввести в компьютер (ПРОГРАММА 1 - алгоритм Евклида для нахождения наибольшего общего делителя).

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