Математичні основи RSA

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 7. Криптографічна система RSA

1.... Математичні основи RSA.. 1

2.... Шифрування та підпис за схемою RSA.. 3

3.... Безпека RSA: деякі алгоритми факторизації 6

1. Тилборг ван Х.К. Основы криптологии. Профессиональное руководство и интерактивный учебник. — М.: Мир, 2006, с. 148 – 160.

2. Henk C.A. van Tilborg, FUNDAMENTALS OF CRYPTOLOGY. A Professional Reference and Interactive Tutorial. Eindhoven University of Technology. The Netherlands. KLUWER ACADEMIC PUBLISHERS, Boston/Dordrecht/London.

3. Rivest R.L., A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key crypto systems, Comm. ACM, Vol 21, pp. 120-126, 1978.

4. Lenstra H.W. Jr. Factoring integers with elliptic curves, Report 86-16, Dept. of Mathematics, University of Amsterdam, Amsterdam, the Netherlands.

5. Morrison M.A., J. Brillhart, A method of factoring and the factorization of F7, Math. Сотр. 29, pp. 183-205, 1975.

В 1978 г. Райвест, Шамир и Адлеман [3] предложили криптосистему с публичными ключами, которая стала известна, как система RSA. Она использует следующие три утверждения:

1) возведение в степень по модулю составного числа, т.е. вычисление из сравнения для заданных и — относительно простая операция;

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

3) если разложение на простые сомножители известно, то задача извлечения корней по модулю выполнима.

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

Приведенной системой вычетов по модулю называют подмножество полной системы вычетов, члены которой взаимно просты с.

Например, полную систему вычетов по модулю составляют числа, приведенную систему вычетов по модулю составляют числа. Если – простое число, в приведенную систему вычетов входит всё множество чисел от до. Для любого, не равного 1, число 0 никогда не входит в приведенную систему вычетов.

Число элементов в приведенной системе вычетов определяется функциейЭйлера.

Дата добавления: 2013-12-12