Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- АЛГОРИТМ B.13
| АЛГОРИТМ B.12
Примитивный алгоритм для модульного возведения в степень Модуль N ; основание a ∈ ZN ; Выход: [ab mod N ] x := 1 for i = 1 to b: x := [x • a mod N лучше, опираясь на следующее рекуррентное соотношение: Это приводит к алгоритму, который по очевидным причинам называют «квадрат и умножение» (или «повторяющееся возведение в квадрат»), который требует только O(log b) = O(«b») модульных возведений в квадрат/умножений; см. алгоритм B.13. В этом алгоритме длина b уменьшается на 1 в каждой итерации; отсюда следует, что число итераций равно «b», и поэтому общий алгоритм действует в течение поли- номиального времени «a», «b», и «N «. Точнее, количество модульных возведений в квадрат равно точно»b», а количество дополнительных модульных умножений точно равно весу Хэмминга b (т.е., количеству единиц в двоичном представлении b). Это объясняет предпочтение, обсуждаемое в разделе 8.2.4, по выбору сте- пени e открытого RSA малых длины/веса Хэмминга. АЛГОРИТМ B.13 Алгоритм ModExp для эффективного модульного возведения в степень Мо- дуль N ; основание a ∈ ZN ; Выход: [ab mod N ] x := a t :=1 // поддерживает инвариант, поэтому ответ равен [ t • xb mod N ] while b > 0 do: if b является четным t :=[ t • x mod N ], b := b − 1 x:=[x2 mod N ], b := b/2 retun t Зафиксируем a и N и рассмотрим функцию модульного возведения в степень с учетом fa,N (b) = [ab mod N ]. Мы только что видели, что вычислить fa,N про- сто. Напротив, вычисление инверсии этой функции, то есть, вычисление b с учетом a, N и [ab mod N ], считается трудным для соответствующего выбора a и N . Инвертирование этой функции требует решения задачи дискретного лога- 327 рифмирования, кое-что мы обсуждаем подробно в разделе 8.3.2. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|