Компрометация протокола

Рассмотрим простой пример.

При первоначальном знакомстве с финансовой и коммерческой криптографией вряд ли возможно ставить перед собой задачу научиться конструировать новые стойкие протоколы - достаточно ознакомиться с обширным арсеналом существующих протоколов, научиться грамотно их использовать. Современная криптография имеет вполне достаточно средств для решения подавляющего боль-шинства практических задач. Тем не менее полезным будет получить общее представление о тех научных и методических принци-пах, на которых строится такого рода конструкторская работа.

Завершая изложение основных понятий, связанных с криптогра-фическими протоколами, отметим основные подходы к конструированию безопасных протоколов в рамках концепции доказа-тельной безопасности.

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 ...2. Принцип моделирования действий противника. При конструировании протокола отмечается вся наблюдаемая противником ин-формация и (если противник активный) его действия как участника протокола. Далее строится формальное доказательство того, что противник сможет самостоятельно путем моделирования сгенерировать всю информацию, наблюдаемую в протоколе. Иными словами, из выполнения протокола реальными участниками противник полу-чает информации не больше, чем он мог бы получить самостоятельно, моделируя этот протокол. Пример, иллюстрирующий этот принцип, будет рассмотрен в следующем разделе.