Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм RSA


Протокол генерации ключей алгоритма Диффи-Хеллмана

Абоненты А и В:

 

1. знают числа A и P, которые являются открытыми константами протокола и известны всем участникам Р– простое число и А является примитивным корнем Р;

 

2. генерируют независимо друг от друга случайные числа – закрытые ключи: Ka, Kb,удовлетворяющих условию: 1 < K < P ;

3. вычисляют значения YA = A Ka mоd(P) и YB = A Kb mоd(P)и обмениваются ими по открытому каналу связи;

4. вычисляют общий секретный ключ K ,которым шифруют сообщения по симметричному алгоритму.

абонент А:

K = (YB)Ка mod (Р) = (AКb mod (Р))Ка mod (Р) = (AКb )Ка mod (Р)

абонент В:

K = (YА)Кb mod (Р) = (AКа mod (Р))Кb mod (Р) = (AКа )Кb mod (Р)

Таким образом, две стороны обменялись секретным ключом. Так как значения КаиКb являются секретными, противник может получить только следующие значения: Р, A, YАиYВ. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить КаиКb , что является вычислительно трудной задачей.

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

Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Yj , создать свою пару открытого и закрытого ключа н, Yн) и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.

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



Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом. Криптостойкость алгоритма основана на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа. Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых числа p и q

2. Вычисляется их произведение n=(p*q)

3. Выбирается произвольное число e (e < n), такое, что

НОД(e,(p-1)(q-1))=1,

то есть eдолжно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах уравнение

e*d+(p-1)(q-1)*y=1.

Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа {e,n} – являются открытым ключом KU.

6. Число dхранится в секрете – это и есть закрытый ключ – KR = {d,n}, который позволит расшифровать сообщения, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел :

1. Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок может быть интерпретирован как число из диапазона (0; 2k-1). Для каждого такого числа mi вычисляется выражение ci=(mi)e mod n. Блоки ci и есть зашифрованное сообщение.

На приемной стороне процесс расшифрования производится с помощью числа d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел pи q, то для любого x имеет место равенство

(x(p-1)(q-1))mod n = 1.

 

Для дешифрования RSA-сообщений используется эта формула. Возведем обе ее части в степень (-y):

(x(-y) (p-1) (q-1)) mod n = 1(-y) = 1.

Теперь умножим обе ее части на x :

(x(-y) (p-1) (q-1) +1)mod n = 1*x = x (1)

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в выражении (1) мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=(mi)emod n достаточно возвести его в степень dпо модулю m:

(ci)dmod n = (mi)e*dmod n = mi.

Алгоритм RSA основан на использовании односторонней функции с лазейкой. Зная публично известные n и e, мы можем найти С = Me (mod n) по заданному M, но не наоборот (если злоумышленник перехватит C, то восстановить Mвычислительно трудная задача). При этом, если мы знаем как nраскладывается на множители, то выполнить обратную операцию легко, вычислив d. Разложение числа n на множители и есть та самая лазейка. Наличие лазейки позволяет применять RSA как для шифрования, так и в схеме цифровой подписи.

<== предыдущая лекция | следующая лекция ==>
Алгоритм обмена ключами Диффи-Хеллмана | Алгоритм ЭльГамаля

Дата добавления: 2014-01-07; Просмотров: 813; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.006 сек.