Краткие теоретические и учебно-методические материалы по теме практической работы.
Генерация большого простого числа.
Любая криптосистема основана на использовании ключей. Если для обеспечения конфиденциального обмена информацией между двумя пользователями процесс обмена ключами тривиален, то в системе, в которой количество пользователей составляет десятки и сотни, управление ключами – серьёзная проблема. Если не обеспечено достаточно надёжное управление ключевой информацией, то, завладев ею, злоумышленник получает неограниченный доступ ко всей информации. В этом случае необходимо введение какой-либо случайной величины в процесс шифрования.
В частности, для реализации алгоритма RSA требуются большие простые числа.
Считается, что вероятность выбора двумя людьми одного и того же большого простого .числа пренебрежимо мала.
Существуют различные вероятностные проверки чисел на простоту, определяющие с заданной степенью достоверности, является ли число простым. При условии, что эта степень достоверности велика, такие способы достаточно хороши. Такие простые числа часто называют «промышленными простыми», т.е. они просты с контролируемой возможностью ошибки.
В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (Diffi W., Hellman M.) предложили новый принцип построения криптосистем [2]. По их задумке, передачу от Алисы к Бобу сообщения можно было осуществить без передачи ключей, более того, не было необходимости скрывать метод шифрования. Предложенный принцип, в итоге, преобразовался в отдельную классификацию алгоритмов шифрования - шифрование с открытым ключом.
В поисках способов реализовать свою идею, Диффи и Хеллман пришли к использованию односторонних функций, т.е. функций, в которых получить исходное значение практически невозможно. Одна из таких функций в математике – вычисление по модулю . Перейдем к рассмотрению самого алгоритма.
Принцип простой. Сначала Алиса и Боб вместе выбирают большие простые числа n и g так, чтобы работало следующее соотношение: gxmod n. Эти два числа не нужно хранить в секрете, поэтому об использовании этих чисел Алиса и Боб могут договориться как им удобно (даже прийти в гости к Еве и выбрать эти числа при ней). Потом выполняются следующие действия:
1) Алиса выбирает случайное целое большое число x и присылает Бобу число X, полученное по формуле X = gxmod n.
2) Боб выбирает случайно целое большое число y и присылает Алисе число Y, которое считается как Y = gymod n.
3) Алиса вычисляет число k1 = Yxmod n.
4) Боб вычисляет число k2 = Xymod n.
Нетрудно заметить, что и k1, и k2 равны gxymod n. Но ни Ева, ни кто-нибудь еще, кто прослушивал канал, не знают этого значения. Им известны только n, g, X и Y. Теоретически, Ева знает функцию и может вычислить k1 или k2, но, к сожалению для нее, эта функция является односторонней, и если Алиса и Боб могут выполнить обратное преобразование, поскольку обладают всеми необходимыми числами, то Еве будет очень сложно сделать тоже самое, а учитывая, что работа ведется с большими числами, - почти невозможно.
Есть, конечно, одно «но». Выбор n и g довольно сильно влияет на безопасность системы. Следует выбирать n такое, чтобы (n-1)/2 было также простым, и, самое главное, чтобы n было большим: безопасность заключается в сложности разложения на множители чисел того же размера, что и n. Требования к выбору g не такие строгие, главное требование – оно должно быть примитивом mod n. В остальном же, оно может быть хоть одноразрядным простым числом.
Следует добавить, что алгоритм Диффи-Хеллмана успешно работает с тремя и более участниками, секретный ключ, после всех вычислений будет иметь вид k = gn1*n2*…*nNmod n, где n1..nN – переменные, закрепленные за каждым участником (x,y, z и т.д.) [1]. Алгоритм, как видно из заголовка, является алгоритмом обмена ключами, а не шифрования.
Задание.
Произвести расчет ключа.(Взять p больше 20)
1.Совместно с удалённой стороной устанавливить открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где
p является случайным простым числом
(p-1)/2 также должно быть случайным простым числом (для повышения безопасности)
g является первообразным корнем по модулю p
2.Вычислить открытый ключ A, используя преобразование над закрытым ключом
A(B) = ga(b) mod p для каждой стороны (A, a) для одной; (B, b) для другой.
3.Обменяться открытыми ключами с удалённой стороной
4.Вычислить общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a
K = Ba mod p
К получается равным с обеих сторон, потому что:
Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p
5. Сравнить общие ключи.
Контрольные вопросы:
1.Для чего применяется алгоритм Диффи-Хеллмана?
2.Что такое модулярная математика?
3.Чем обеспечивается секретность получаемого ключа?