Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Получатель подписанного текста (/-й абонент) при необходимости, т.е. когда имеет место случай (а), расшифровывает текст с помощью формулы
X = (y(X))d(i,mod(N(i)), (4.16)
вычисляет хеш-функцию Іі*(Х) от аргумента X и сверяет ее значение с результатом расшифрования криптограммы S(h(X)). Иными словами, проверяется условие
h*(X) = (S(h(X)Y^mod(N(j)), (4.17)
соблюдение которого и есть доказательство того, что сообщение X с его хеш-функцией Ii(X) в адрес 1-го абонента было послано именно j-м абонентом. Ведь никто другой, кроме абонента, владеющего секретным ключом d(j), не может вычислить число S(h(X)) такое, чтобы оно удовлетворило равенству (4.17). Заметим, что в результате "перехвата" числа S(h(X)) злоумышленник сможет восстановить хеш-функцию Il(X), поскольку ЧИСЛО e(j), Т.е. открытый КЛЮЧ шифрования J-TO абонента, общеизвестно. Но это не поможет ему в деле подделки подписи. Для этого ему необходимо владеть закрытым ключом шифрования, т.е. числом d(j). Только тогда он сможет имитировать посылку в адрес любого абонента произвольного текста от имени (за подписью)
84 j-го абонента. Исходя из этого, можно заключить, что предъявление арбитру со стороны /-го абонента текста X, его хеш-функции Zi(Ar) и числа S(h(X)) является достаточно убедительным доказательством того, что текст X он получил именно от j-го абонента.
ВОЗМОЖНЫЕ АТАКИ НА СИСТЕМУ RSA И НЕКОТОРЫЕ ВОПРОСЫ ЕЕ КРИПТОСТОЙКОСТИ
Как при передаче конфиденциальных сообщений, так и при организации электронной подписи в системе RSA объектами атаки со стороны злоумышленников в одинаковой степени могут быть числа q, р, F(N) и d (ниже индексы, указывающие на абонентов, при этих числах будем ставить лишь при необходимости), поскольку знание любого из этих чисел при известных е и N вполне достаточно для рассекречивания системы RSA.
В ряде случаев, особенно тогда, когда программное обеспечение системы RSA приобретено на стороне, имеется определенная вероятность того, что противнику будет известен интервал значений, откуда могут быть выбраны числа q up. Покажем, что при определенных условиях это может представлять серьезную угрозу с точки зрения разложения противником числа N на множители q и р.
Пусть известно (в том числе и противнику), что простые числа q и р выбираются из интервала [а, Ь], причем q < р. Естественно полагать, что противнику известно также число N = q ¦ р, которое может оказаться меньшим, равным или большим произведения а ¦ Ь.
Если N = а ¦ Ь, то значения q и р удовлетворяют неравенствам
a^q<Ja~h, (4.18)
-U~b<pskb, (4.18а)
т.е. диапазоны изменения чисел q и р равны соответственно
Aq = ^a h - а, Ар = b - ^Ja ¦ Ь.
Отсюда следует, что
Ap-Aq = Cib- V^)2 > 0. (4.20)
Если N < а ¦ Ь, то значения q тлр удовлетворяют неравенствам
a =S q< V/V, (4.21)
V/V <р ^Nla, (4.21а)
(4.19) (4.19а)
85
ГЛАВА 5 т.е. диапазоны изменения чисел q и р равны соответственно
Aq = ^N ~ a, (4.22)
Ap = NZa -л[ы. (4.22а)
Отсюд следует, что
Ap - Aq = (V N - а)2/а) > 0. (4.23)
Если же N > а ¦ Ь, то значения q и р удовлетворяют неравенствам
Nlh q < V/V, (4.24)
V/V < /; s= b, (4.24а) т.е. диапазоны изменения чисел q и р равны соответственно
Aq = V/V - Nib, A p = b~^N.
Отсюда следует, что
Ap - Aq = (b- -(N)2Ib > 0. (4.26)
Таким образом, как это следует из (4.20), (4.23) и (4.26), во всех трех случаях имеет место Aq < Ар, т.е. диапазоны возможных значений q оказываются меньше диапазонов возможных значений р.
В случаях, когда N s? а ¦ Ь, область возможных значений q определяется формулой (4.21), а в случае, когда N > а ¦ Ь, эта область определяется формулой (4.24). Если у противника не имеется иных, более эффективных методов разложения числа N на множители q и р, чем метод прямого перебора, то при N^ab ему предстоит осуществить Aq = V/V - а (см. формулу (4.22)) проверок, а при N > а ¦ b необходимое число проверок определяется по формуле (4.25). Если рассматривать зависимость Aq от аргумента V/v, то в области
a SS V/V s? Va~/> (4.27)
эта зависимость линейная, а в области
Va • b s? V/V < h (4.28)
имеет место параболическая зависимость. На рис. 4.1 приведен примерный характер зависимости необходимого числа проверок от числа л/'V при известных значениях а и Ь. Здесь случаи (а), (б) и (в) характеризуют эту зависимость в случаях, когда соответственно а < b/4, а = Ь/4 и а > h/4.
Из рис. 4. J легко заметить, что с приближением числа Vzv к значе-
(4.25) (4.25а)
86 Рис. 4.1. Характер зависимости необходимого числа проверок (Aq) от числа V^
а) при а<Ь/4
б) при а=Ь/4
в) при а>Ь/4 ниям а или b необходимое число проверок, т.е. величина Aq уменьшается. А это таит в себе большую опасность, поскольку пользователи, придерживаясь принципа "выбрать числа q и /; как можно большими", могут значительно облегчить задачу злоумышленника. Если к примеру, в качестве чисел q и р пользователь возьмет числа, существенно близкие к верхней границе, т.е. к числу Ь, то тем самым значительно уменьшит необходимое число проверок для злоумышленника.
