В. Р. Гинзбург Перевод с английского

13.4. Определение RSA
251
Обсуждая, каким должно быть значение
t
, мы пропустили один неболь-
шой момент:
x
t
mod
p
не может быть равно единице, если
x
mod
p
= 0
. По-
этому равенство
x
t
mod
n
= 1
не может выполняться для
всех
значений
x
.
К счастью, исключений из этого правила немного:
q
чисел, для которых
x
mod
p
= 0
, и
p
чисел, для которых
x
mod
q
= 0
. Всего таких чисел
p
+
q
,
точнее,
p
+
q
−
1
, поскольку 0 мы посчитали дважды. Это лишь небольшая
доля всех значений, общее количество которых равно
n
=
pq
. Следует отме-
тить, что на самом деле алгоритм RSA использует свойство несколько иного
вида:
x
t
+1
=
x
(mod
n
)
. Последнее выполняется даже для упомянутых выше
исключений. Это также легко показать с помощью CRT-представлений. Если
x
= 0(mod
p
)
, тогда
x
t
+1
= 0 =
x
(mod
p
)
. Аналогичное справедливо и для
q
.
Таким образом, фундаментальное свойство
x
t
+1
=
x
(mod
n
)
сохранено и вы-
полняется для всех элементов
Z
n
.
13.4
Определение RSA
Теперь можно определить систему RSA. Вначале случайным образом вы-
берем два разных простых числа
p
и
q
и вычислим
n
=
pq
. Простые числа
p
и
q
должны быть примерно одного размера, в результате чего число
n
будет
в два раза длиннее.
Мы также используем два разных показателя степени, которые принято
обозначать как
e
и
d
. Они должны удовлетворять требованию
ed
= 1(mod
t
)
,
где, как и раньше,
t
=
НОК
(
p
−
1
, q
−
1)
. В качестве открытого показателя
e
мы выбираем малое нечетное значение, после чего используем функцию
ExtendedGCD
(см. раздел 11.3.5), чтобы вычислить
d
как обратное
e
по
модулю
t
. Это гарантирует, что
ed
= 1(mod
t
)
.
Чтобы зашифровать сообщение
m
, отправитель генерирует шифрован-
ный текст
c
:=
m
e
(mod
n
)
. Чтобы расшифровать шифрованный текст
c
, по-
лучатель вычисляет
c
d
(mod
n
)
. Это эквивалентно значению
(
m
e
)
d
=
m
ed
=
m
kt
+1
= (
m
t
)
k
·
m
= (1)
k
·
m
=
m
(mod
n
)
, где
k
— некое целое число, ко-
торое всегда существует. Таким образом, получатель может расшифровать
шифрованный текст
m
e
, чтобы получить открытый текст
m
.
Пара
(
n, e
)
образует открытый ключ. Последний обычно распространяет-
ся среди многих участников общения. Значения
(
p, q, t, d
)
образуют
закрытый
ключ (private key)
и сохраняются в секрете человеком, который сгенерировал
ключ RSA.
Для удобства вместо
c
d
mod
n
часто пишут
c
1
/e
mod
n
. Следует помнить,
что все показатели вычислений по модулю
n
взяты по модулю
t
, так как
x
t
= 1(mod
n
)
, а значит, кратные
t
в показателе на результат не влияют. По-
скольку мы определили
d
как обратное
e
по модулю
t
, запись
d
как
1
/e
вполне

252
Глава 13. Алгоритм RSA
естественна. Запись
c
1
/e
зачастую оказывается легче для восприятия, особен-
но при использовании сразу большого количества ключей RSA. Вот почему
мы также говорим о взятии корня степени
e
из числа
c
. Просто запомни-
те, что вычисления любых корней по модулю
n
требуют знания закрытого
ключа.
13.4.1
Создание цифровой подписи с помощью RSA
До сих пор речь шла только о шифровании сообщений с помощью RSA.
Между тем одним из больших преимуществ данного алгоритма является воз-
можность его применения как для шифрования, так и для создания цифро-
вых подписей. Эти операции используют одни и те же вычисления. Чтобы
подписать сообщение
m
, владелец закрытого ключа вычисляет
s
:=
m
1
/e
mod
n
. Пара
(
m, s
)
образует подписанное сообщение. Чтобы удостовериться в под-
линности подписи, каждый, кто знает открытый ключ, может проверить,
действительно ли
s
e
=
m
(mod
n
)
.
Как и для шифрования, безопасность цифровой подписи основывается
на том, что корень степени
e
из числа
m
может быть вычислен только тем
человеком, который знает закрытый ключ.
13.4.2
Открытые показатели степеней
Описанная выше процедура имеет один недостаток. Если
e
имеет общий
делитель с числом
t
=
НОК
(
p
−
1
, q
−
1)
, тогда нужного
d
не существует. Поэто-
му параметры
p
,
q
и
e
следует выбирать таким образом, чтобы не допустить
подобной ситуации. Это скорее нюанс, нежели проблема, однако упускать его
из виду тоже нельзя.
Использование открытого показателя малой длины значительно повыша-
ет эффективность RSA, поскольку для возведения числа в степень
e
потребу-
ется меньше вычислений. Вот почему мы будем стараться выбрать в качестве
e
малое значение. Здесь мы устанавливаем фиксированное значение
e
, а затем
подбираем
p
и
q
, чтобы они удовлетворяли упомянутым условиям.
Необходимо тщательно следить за тем, чтобы функции шифрования и
цифровой подписи не взаимодействовали между собой каким-либо нежела-
тельным образом. Нельзя допустить, чтобы злоумышленник мог расшифро-
вать сообщение
c
, убедив владельца частного ключа подписать это сообще-
ние. В конце концов, подписывание “сообщения”
c
— это то же самое, что
и расшифровка шифрованного текста
c
. Функции шифрования, которые рас-
сматриваются немного позднее, помогают не допустить подобной ситуации,
однако использовать одну и ту же операцию RSA в качестве обеих функций
все же не стоит. Мы могли бы применять для аутентификации и шифрова-

13.4. Определение RSA
253
ния разные ключи RSA, однако это бы повысило сложность и удвоило объем
данных ключа.
В качестве возможного решения можно порекомендовать использование
одного и того же
n
с двумя разными показателями степеней. Мы будем ис-
пользовать
e
= 3
для цифровых подписей и
e
= 5
для шифрования. Это
разъединит системы, потому что кубические корни и корни пятой степени по
модулю
n
не зависят друг от друга. Знание одного из этих корней не поможет
злоумышленнику вычислить другой [28].
Выбор фиксированных значений для
e
упрощает систему и позволяет оце-
нить ее производительность. С другой стороны, он накладывает ограничения
на используемые простые числа, поскольку
p
−
1
и
q
−
1
не могут быть крат-
ными 3 или 5. Впрочем, наличие этого свойства легко проверить еще при
генерации
p
и
q
.
Аргументы в пользу значений 3 и 5 очень просты. Они являются наимень-
шими подходящими значениями
2
. Меньший показатель степени будет приме-
няться для подписывания, потому что цифровые подписи зачастую проверя-
ются по многу раз, в то время как любой фрагмент данных шифруется только
единожды. Поэтому имеет смысл сделать процедуру верификации цифровых
подписей более эффективной.
Другими распространенными значениями, которые принято использовать
в качестве
e
, являются 17 и
65 537
. Мы предпочитаем меньшие значения,
поскольку они повышают эффективность системы. Разумеется, применение
малых открытых показателей может быть связано с некоторыми второсте-
пенными проблемами, однако функции кодирования, которые обсуждаются
немного позднее, позволяют этого избежать.
Было бы неплохо использовать малое значение и в качестве
d
, но здесь
мы вынуждены вас разочаровать. Хотя найти пару
(
e, d
)
с малым значением
d
в принципе возможно, использование малого
d
небезопасно [94]. Поэтому
не стоит поддаваться соблазну, пытаясь найти удобное значение
d
.
13.4.3
Закрытый ключ
Злоумышленнику крайне сложно найти параметр закрытого ключа
p
,
q
,
t
или
d
, если он знает только открытый ключ
(
n, e
)
. При достаточно большом
значении
n
не существует известного алгоритма, который мог бы определить
закрытый ключ за приемлемое время. Наилучшее решение, которое нам из-
вестно, — это разложить
n
на множители
p
и
q
и затем попытаться на их
основе вычислить
d
. Вот почему разложение на множители играет такую
важную роль в криптографии.
2
Теоретически мы могли бы использовать
e
= 2
, однако это привнесло бы в систему
целый ряд дополнительных сложностей.

254

жүктеу/скачать 2,74 Mb.

Достарыңызбен бөлісу: