Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
| f (x) = x
e mod m, () где x — шифруемый исходный текст, e, m — заданные натуральные числа. (Здесь и далее выражение a mod m означает остаток от деле- ния числа a на число m. Другими словами, для вычисления значения f (x) по формуле () нужно x возвести в степень e и результат по- делить на m. Остаток от деления и даст искомое значение функции). Пара чисел e и m считается известной, она составляет открытый ключ схемы шифрования. Для расшифрования сообщения y = f (x) необходимо, зная y, най- ти x из уравнения x e = y mod m. Авторы схемы RSA показали, что для вычисления обратной функ- ции достаточно вычислить x = y d mod m, где d — некоторое число, удовлетворяющее соотношению de mod ϕ(m) = 1. () Число d является секретным ключом схемы, необходимым для рас- шифрования. В уравнении () функция ϕ(m) — так называемая функция Эйле- ра — хорошо изученная в теории чисел. Для любого целого m она рав- на числу целых чисел из интервала 1, 2, …, m − 1, взаимно простых с m. Достаточно легко проверить следующие свойства функции Эйлера: 0) ϕ(1) = 1; 1) ϕ(p) = p − 1 для любого простого p; 2) ϕ(p r ) = p r−1 ( p − 1) для любого простого p и целого r; 3) ϕ(pq) = ϕ(p)ϕ(q) для любых взаимно простых p и q. Свойства , , позволяют легко вычислять ϕ(m), если известно разложение числа m на простые множители. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если произвольное число x взаимно просто с m, то x ϕ(m) mod m = 1. Теперь готов весь алгоритм для организации схемы шифрования RSA. • Организатор схемы — выбирает два достаточно больших простых числа p, q; 1.3. Математическая формализация 19 — вычисляет m = pq; — выбирает e < m, которое должно быть взаимно простым с чис- лом (p − 1) · (q − 1); — с помощью алгоритма Евклида вычисляет число d из усло- вия (); — числа m и e публикуются, числа d, p, q остаются секретными. • Любой участник схемы, желающий зашифровать исходный текст x, вычисляет (зная e и m) y = x e mod m и результат y отправляет организатору схемы в качестве зашифрован- ного текста. • Организатор схемы, получив шифрованное сообщение y и зная секретное число d, вычисляет исходное сообщение x = y d mod m. Проверим это равенство: y d mod m = x de mod m = по условию () = = x ϕ(m) x mod m = по теореме Эйлера = x mod m. • Участник схемы, знающий всю организацию схемы RSA, но не знающий секретного числа d, должен, чтобы расшифровать сообще- ние y, вычислить d по формуле (). В эту формулу входит величина ϕ(m), которую можно легко вычислить, зная разложение m на про- стые множители. Заметим, что организатор схемы, знающий разло- жение числа m на простые множители, легко вычислял ϕ(m) по фор- муле ϕ(m) = (p − 1)(q − 1). Для пользователя, не знающего секретно- го числа d, единственная возможность вычислить ϕ(m) — разложить m на простые множители, а эта задача, как уже указывалось, не имеет эффективного алгоритма. жүктеу/скачать 460.25 Kb. Достарыңызбен бөлісу:
|