Научная литература
booksshare.net -> Добавить материал -> Физика -> Аветисян Р.Д. -> "Теоретические основы информатики" -> 33

Теоретические основы информатики - Аветисян Р.Д.

Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики — Телеком , 2003. — 170 c.
Скачать (прямая ссылка): teoriticheskieosnoviinformatiki2003.pdf
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 64 >> Следующая


Получатель подписанного текста (/-й абонент) при необходимости, т.е. когда имеет место случай (а), расшифровывает текст с помощью формулы

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 и р пользователь возьмет числа, существенно близкие к верхней границе, т.е. к числу Ь, то тем самым значительно уменьшит необходимое число проверок для злоумышленника.
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 64 >> Следующая
Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed