Компрометация протокола
Рассмотрим простой пример.
Используется поточный шифр. Известно, что передаваемые в протоколе сообщения имеют специальную форму: первые 20 бит несут в зашифрованном виде информа-цию, которая представляет сумму денег, переводимых со счета на счет. Активный противник может просто сделать побитовое сложе-ние первых 20 бит с какой-либо произвольной величиной и изме-нить количество денег, так и не узнав его. Другие примеры атак на протоколы и их подверженности компрометациям мы будем приво-дить при рассмотрении конкретных классов протоколов.При первоначальном знакомстве с финансовой и коммерческой криптографией вряд ли возможно ставить перед собой задачу научиться конструировать новые стойкие протоколы - достаточно ознакомиться с обширным арсеналом существующих протоколов, научиться грамотно их использовать. Современная криптография имеет вполне достаточно средств для решения подавляющего боль-шинства практических задач. Тем не менее полезным будет получить общее представление о тех научных и методических принци-пах, на которых строится такого рода конструкторская работа.
Завершая изложение основных понятий, связанных с криптогра-фическими протоколами, отметим основные подходы к конструированию безопасных протоколов в рамках концепции доказа-тельной безопасности.
1. Принцип редукции к вычислительно-сложным задачам. Безо-пасность протоколов основана на сводимости их вскрытия к реше-нию вычислительно-сложных задач. Решить задачу «вскрытия» (на-рушения безопасности) криптографических алгоритмов (примитивов), используемых в протоколе, по меньшей мере так же трудно, как «вскрыть» протокол.
В то же время решить одну из вычисли- тельно-сложных задач по меньшей мере так же сложно, как «вскрыть» этот криптографический алгоритм (примитив). Наиболее известные и часто используемые вычислительно-сложные задачи теории чисел приведены в табл. 1.1. В последнее время криптографами рассматривается ряд других вычислительно-сложных задач и алгебраических структур, не приведенных в таблице. С этими задачами и основанными на них криптосистемами можно ознакомиться в научной литературе.Таблица 1.1. Часто используемые в криптографии вычислительно-сложные задачи теории чисел Условное обозначение Наименова-ние задачи Дано Найти FACTORING Задача фак-торизации целых чисел п где pj - попарно простые числа, е,>1 RSA Задача RSA п = pq,
е:НОД(е,(р-1)(<7-1)) = = 1, с є Z т : /if = с (mod п) SRA Усиленная задача RS А n=pq, г є z; r = r(z)> 1, QRP Задача о квадратичных вычетах п - нечетное составное целое число,
ае Z: — =1
l»J SQROOT Задача из-влечения квадратного корня по модулю п п - составное число, ае QRn х:х2 =a(modn) DLP Задача дис-кретного логарифмир ования Р - простое число, А- образующий элемент Z*,$EZ*P х:0< л:< р-2, A* =P(mod Р)
Условное обозначение Наименова-ние задачи Дано Найти GDLP Обобщенная задача дискретного логарифмир ования G - конечная цикли-ческая группа, |G| = п, а- обр. элемент в G, |3є G х: 0 < х < п-1, aJ=(3 DHP Задача Диф- фи-
Хеллмана р - простое число, а- обр. элемент Z;,
а" mod р, аь mod р a"h mod р GDHP Обобщенная задача Диффи- Хеллмана G - конечная цикли-ческая группа, а- обр.
элемент в О, а", аь а"ь DDHP Задача распо-знавания (decision) Диффи - Хеллмана р - простое число, а- обр. элемент Z*,
а" mod р, аь mod р, ас mod р a"b =ас mod р SUBSET «Задача о рюкзаке» {а,,аJ,...,а,,} - множество положительных целых чисел, s - положительное целое число X aj=s
Ml /і}
Таким образом, чтобы доказать стойкость того или иного прото-кола, нужно задачу нарушения его безопасности «вложить» слева в одну из известных цепочек, связывающих относительную сложность решения вычислительно-сложных задач, например: ... < DDHP < DHP < DLOG; ... < GDDHP < GDHP < GDLOG; ...< SUBSET;
< FACTORING.
... < SRA < RSA ...