Студопедия

КАТЕГОРИИ:


Архитектура-(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




Система RSA, название которой происходит от первых букв фамилий авторов, Р. Риверса, А. Шамира и Л. Адлемана, является наиболее распространенной и изученной криптосистемой с открытым ключом. Она основана на использовании того факта, что легко перемножить два больших простых числа, в то же время крайне трудно разложить на множители их произведение. В результате произведение может быть использовано в качестве элемента открытого ключа зашифрования. Исходные простые числа необходимы для расшифрования, при этом задача их восстановления до сих пор сопротивляется всем атакам криптоаналитиков. Таким образом, имеются хорошие предпосылки для построения од­носторонней функции с секретом.

Рассмотрим некоторые матем-е факты, на которых основан алгоритм. Согласно малой теореме Ферма, если р - простое число, то для любого х, взаимно простого с р, справедливо хp-1 = (mod р);

для любого х справедливо Xр= x(modp).

Функция ф(n) натурального аргумента n, равная количеству положительных целых чисел, меньших п и взаимно простых с r, называется функцией Эйлера. Для нее справедливы следующие соотношения:

φ(1)=1; φ(pr) = pr-1(p-1);

φ(ab) - φ(а)φ(b), где р - простое, r, а и b - натуральные, (а, b) = 1.

Эти свойства позволяют легко вычислять ф(n), когда известно разложение n на простые множители. Если натуральное число е удовлетворяет условию (е, φ(n)) = 1, то существует единственное натуральное число d < φ(n), для которого справедливо de ≡ 1 (mod φ(n)).

Пусть n = pq, где р и q - два больших различных простых числа, и (х, φ(n)) = 1. Тогда согласно теореме Эйлера для любого натурального х выполняется сравнение хed= x(mod n) и, следовательно, хed(mod n) = х при условии x < n.

Итак, выберем два больших различных простых числа р и q и число е, взаимно простое с числом (р - 1)(q -1). Вычислим n = pq и найдем d, такое, что de≡ 1 (mod (р-1)(q-1)).

Тогда рассматриваемая криптосистема выглядит следующим образом.

Криптосистема RSA:

Открытый ключ зашифрования: числа n и е.

Закрытый ключ расшифрования: числа р, q и d.

Алгоритм зашифрования сообщения р~:

Ek(р~) = р~e(mod n) = с.

Алгоритм расшифрования закрытого сообщения с:

Dk(c) = cd(mod n) =р~.

Единственный способ найти алгоритм расшифрования Dkпри известных е и n состоит в том, чтобы разложить на простые множители число n, найти р и q, а следовательно, и d. Правильный выбор разрядности чисел р и q (первоначально авторы RSA предлагали в качестве р и q использовать не менее чем 40-разрядные десятичные числа) делает задачу факторизации n практически неосуществимой.

Криптосистема с открытым ключом RSA часто используется не только для шифрования, но и для построения схемы электронной подписи. Пусть EA (x) = xC mod n - открытая функция зашифрования, а DA (x) = xD mod n - секретная функция расшифрования.


 




Поделиться с друзьями:


Дата добавления: 2015-03-29; Просмотров: 574; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



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




Генерация страницы за: 0.013 сек.