Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
ГЛАВА 6. КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ Успешное решение задачи открытого распределения ключей, создание практических схем цифровой подписи способствовали возникновению нового направления криптографии – теории криптографических протоколов. Для современных информаци- онных систем характерен перевод всего документооборота в электронную форму. Возникающие при этом проблемы чаще всего могут быть решены только с использованием возможно- стей криптографии. Типичный пример: взаимодействуют два удаленных абонента А (клиент банка) и В (банк). Абонент А хо- чет доказать абоненту В, что он тот, за кого себя выдает, а не злоумышленник. Для решения этой задачи требуется протокол аутентификации абонента. В каждом конкретном случае для решения некой задачи, связанной с обеспечением безопасности пересылаемых электронных документов, требуется использова- ние соответствующих криптографических протоколов, которые за последние годы превратились в основной объект исследова- ний криптографии. Материал данной главы в значительной сте- пени основывается на работе [4]. 6.1. Основные понятия Объект изучения теории криптографических протоколов – удаленные абоненты, взаимодействующие по открытым каналам связи. Цель взаимодействия – решение какой-либо практической задачи. Модель предусматривает наличие противника, пресле- дующего собственные цели. Противник может выдавать себя за законного субъекта взаимодействия, вмешиваться в информаци- онный обмен между абонентами и т.п. Участники протокола в общем случае не доверяют друг другу, иначе говоря, некоторые протоколы должны быть рассчитаны на ситуацию, когда про- тивником может оказаться даже один из абонентов или несколь- ко абонентов, вступивших в сговор. В настоящее время известно несколько десятков различных типов протоколов. Все эти типы можно разделить на две группы: 181 1) прикладные протоколы, решающие конкретную задачу, которая может возникнуть на практике; 2) примитивные протоколы, используемые в качестве свое- образных строительных блоков при создании приклад- ных протоколов. Протокол чаще всего интерактивен, т.е. предусматривает многораундовый обмен сообщениями между участниками, и включает в себя: распределенный алгоритм, т.е. описание характера и после- довательности действий каждого из участников; спецификацию форматов пересылаемых сообщений; спецификацию синхронизации действий участников; описание действий при возникновении сбоев [4]. 6.2. Доказательства с нулевым разглашением Существенное влияние на разработку многих криптографи- ческих протоколов оказали исследования двух математических моделей – интерактивной системы доказательств (Interactive Proof System) и доказательств с нулевым разглашением знаний (Zero-Knowledge Proofs). Интерактивная система доказательств суть протокол (P, V, S) взаимодействия двух субъектов: доказывающего (претендента) P и проверяющего (верификатора) V. Абонент P хочет доказать V, что утверждение S истинно. При этом считается, что абонент V самостоятельно проверить утверждение S не в состоянии, что абонент V не может быть противником, а абонент P может быть противником, пытающимся доказать истинность ложного утвер- ждения S. Протокол, состоящий из некоторого числа раундов обмена сообщениями между P и V, должен удовлетворять двум условиям: 1) полнота – если S действительно истинно, то доказываю- щий убедит проверяющего признать это; 2) корректность – если S ложно, то доказывающий не смо- жет убедить проверяющего в обратном. 182 Если предположить, что V может быть противником, который хочет получить информацию об утверждении S, необходим про- токол (P, V, S), называемый доказательством с нулевым разгла- шением, удовлетворяющий, помимо перечисленных, еще и сле- дующему условию: 3) нулевое разглашение – в результате работы протокола абонент V не увеличит своих знаний об утверждении S. Иными словами, в результате реализации протокола абонент P сможет доказать абоненту V, что он владеет некоторой секрет- ной информацией, не разглашая ее сути. Упрощенно процедуру доказательства с нулевым разглаше- нием можно представить следующим образом. Проверяющий задает серию случайных вопросов, каждый из которых допуска- ет ответ «да» или «нет». После первого вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятно- стью 1/2. После второго вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятностью 1/4 и т.д. (после каждого вопроса знаменатель удваивается). После 100 вопросов вероятность того, что доказывающий заблуждается или не располагает доказательством (не владеет секретной информа- цией), становится настолько близкой к нулю, что даже у самого «недоверчивого» проверяющего не должно остаться сомнений в справедливости доказываемого утверждения. После 300 вопро- сов знаменатель достигает величины, которая превосходит число атомов во Вселенной. Роль доказательств с нулевым разглашением особенно велика при реализации протоколов аутентификации. Пусть, например, Р – алгоритм, реализованный в интеллектуальной карточке кли- ента (абонент А)банка; V – программа, выполняемая компьюте- ром банка (абонент В). Перед выполнением любой операции банк должен убедиться в подлинности карточки и идентифици- ровать ее владельца. Если для этой цели использовать протокол (P, V, S), свойство полноты позволит карточке доказать свою аутентичность; свойство корректности защитит интересы банка от злоумышленника, который попытается воспользоваться 183 фальшивой карточкой; свойство нулевого разглашения защитит клиента от злоумышленника, который попытается пройти аутен- тификацию под именем абонента А, воспользовавшись инфор- мацией, перехваченной во время предыдущих раундов аутенти- фикационного обмена. Аналогичных результатов можно добить- ся, используя протоколы доказательств с нулевым разглашением для создания не поддающихся подделке удостоверений лично- сти, как для военных так и гражданских целей [4]. 6.2.1. Пещера нулевого знания На рис. 6.1 показана физическая реализация протокола дока- зательства с нулевым разглашением с помощью так называемой «пещеры нулевого знания» [32]. В пещере имеется дверь Д, от которой у участника протокола P (доказывающего) есть секрет- ный ключ. P хочет доказать другому участнику протокола V (проверяющему) свою способность проходить через дверь (на- личие секретного ключа), не демонстрируя сам факт прохожде- ния через дверь. Показаны две итерации протокола. Работу генератора ПСЧ в этой реализации имитирует проце- дура подбрасывания монеты, которую на определенных шагах протокола выполняют обе стороны. 6.2.2. Протокол Фиата–Шамира Примером протокола доказательства с нулевым разглашением может являться схема Фиата–Шамира, показанная на рис. 6.2. Доверенный третий участник протокола выбирает два больших простых числа p и q, затем вычисляет n = pq. Величина n откры- то публикуется. Абонент A выбирает случайное число n Z s , вычисляет n s mod 2 . А хранит s в качестве своего секретного ключа и объявляет ν своим открытым ключом. 184 P V А Д В С D' D'' V Д P Д V Д P V P R A = 0 R B = 0 Исходная ситуация: доказывающий P и проверяющий V находятся в точке А Итерация 1, шаг 1: доказывающий P спускается в пещеру; дойдя до точки С, подбрасывает монету; исход R A = 0, поэтому Р поворачивает налево и спускается в точку D'; V не видит, куда повернул Р Итерация 1, шаг 2: V спускается в точку В; V не видит, где находится Р Итерация 1, шаг 3: V подбрасывает монету; исход R B = 0, поэтому V просит Р выйти из пещеры слева, Р из точки D' возвращается в точку В, не пройдя через дверь Д Рис. 6.1. Пещера нулевого знания (начало) 185 P V Д V Д P Д V Д P V P R A = 1 R B = 1 Итерация 2, шаг 4: P и V возвращаются в исходную ситуацию – в точку А Итерация 3, шаг 1: доказывающий P спускается в пещеру; дойдя до точки С, подбрасывает монету; исход R A = 1, поэтому Р поворачивает направо и спускается в точку D''; V не видит, куда повернул Р Итерация 3, шаг 2: V спускается в точку В; V не видит, где находится Р Итерация 3, шаг 3: V подбрасывает монету; исход R B = 1, поэтому V просит Р выйти из пещеры справа, Р из точки D’’ возвращается в точку В, не пройдя через дверь Д Итерация 3, шаг 4: P и V возвращаются в исходную ситуацию - в точку А Результат: С вероятностью 7/8 можно утверждать, что P владеет секретом прохождения через дверь Д Рис. 6.1. Пещера нулевого знания (окончание) 186 A B y A = (x A ) 2 mod n y A 6 2 1 b 3 y A ' = x A s b mod n 4 y A ' 5 Сравнение (y A ') 2 mod n и y A ν 2 mod n Доказательство принимается или отвергается s – закрытый ключ А x A – случайное число ν, n – открытый ключ А, b – случайный бит Рис. 6.2. Протокол Фиата–Шамира Протокол включает шесть шагов: 1) абонент A выбирает случайное число x A ; А вычисляет n x y A A mod 2 ; 2) А посылает y A абоненту В; 3) абонент В, проверяющий, посылает А в качестве запроса случайный бит 1 , 0 b ; 4) абонент А вычисляет ответ b A A s x ' y ; 5) А посылает ответ В, чтобы доказать, что он знает свой секретный ключ s; 6) абонент В вычисляет 2 ' y A и b A y . Если эти два числа сравнимы по модулю n, то либо абонент А знает число s, либо вычислил значение y каким-либо другим способом. Доказательство этого факта элементарно: b A b A b A A y s x s x ' y 2 2 2 2 Эти шесть шагов образуют один раунд. Проверка осуществ- ляется несколько раз с выбираемыми случайно значениями b. 187 Доказывающая сторона должна успешно пройти проверку в ка- ждом раунде, чтобы быть аутентифицированной. Если в каком- то раунде проверка завершилась отрицательным результатом, процесс аутентификации прерывается. Если А знает s, он пройдет проверку во всех раундах. Если А не является тем, за кого он себя выдает, т.е. не знает s, он может попытаться пройти раундовую проверку, правильно предсказав величину b. При этом возможны две ситуации: 1) А предполагает, что b будет равно 1. А вычисляет / 2 A A x y и посылает y A абоненту В. Если предположение А оказывается правильным, он посыла- ет на шаге 3 A A x ' y в качестве ответа. Видно, что А пройдет проверку, так как b A A y ' y 2 Если А ошибся, значение ' y A не пройдет проверку и В пре- рвет процесс аутентификации. 2) А предполагает, что b будет равно 0. А вычисляет 2 A A x y и посылает y A абоненту В. Если предположение А оказывается правильным, он посыла- ет на шаге 3 A A x ' y в качестве ответа. Видно, что А пройдет проверку, так как b A A y ' y 2 Если А ошибся, значение ' y A не пройдет проверку и В пре- рвет процесс аутентификации. Таким образом, абонент, не знающий числа s, успешно прой- дет раундовую проверку с вероятностью 1/2. Если процесс по- вторяется 20 раз, вероятность успеха снижается до 10 5 , 9 2 / 1 7 - 20 6.2.3. Протокол Фейга–Фиата–Шамира Особенностью данного протокола (рис. 6.3) является исполь- зование вектора секретных ключей, вектора открытых ключей и вектора запросов. Секретные ключи выбираются случайно, но при этом они должны быть взаимно простые с n. Открытые клю- 188 чи выбираются таким образом, чтобы n s i i mod 1 - 2 i b на ша- ге 3 также выбираются случайно. Протокол основывается на справедливости равенства 1 1 1 ' 2 1 2 1 2 2 1 1 2 1 2 1 2 1 2 2 2 2 1 2 1 2 2 2 2 1 2 1 2 1 2 2 2 2 1 2 2 1 2 A b b b A b m m b b A b m b m b b b b A b m b b b m b b A b m b b A y y s s s y s s s y s s s x v y m m m m m m m A B y A = x A 2 mod n y A 6 2 1 [b 1 , b 2 , …, b m ] 3 y A ′ = (x A ×s 1 b1 ×s 2 b2 ×...×s m bm ) mod n 4 y A ′ 5 Сравнение ((y A ′) 2 ×ν 1 b1 ×ν 2 b2 ×...×ν m bm ) mod n и y A Доказательство принимается или отвергается [s 1 , s 2 , …, s m ] – закрытые ключи А x A – случайное число [ν 1 , ν 2 , …, ν m ], n – открытые ключи А, [b 1 , b 2 , …, b m ] – случайные биты Рис. 6.3. Протокол Фейга–Фиата–Шамира 6.3. Протоколы подбрасывания монеты Классическим примером задачи, решаемой двумя удаленными абонентами, является бросание жребия с помощью подбрасыва- ния монеты. Это необходимо сделать так, чтобы абонент А, подбрасывающий монету, не мог изменить результат после по- лучения догадки от абонента В, угадывающего этот результат. Протокол решения данной задачи называют протоколом под- брасывания монеты. Этот примитив (по сути, протокол генера- 189 ции случайного бита) используют в своем составе многие при- кладные протоколы. Примером такого протокола является схема Блюма–Микали, предполагающая наличие у двух его участников односторонней функции , : Y X F удовлетворяющая следующим требованиям: X – конечное множество целых чисел, содержащее одинако- вое количество четных и нечетных чисел; любые числа , , 2 1 X x x такие, что , 2 1 x F x F имеют одинаковую четность; по заданному значению F(x) невозможно определить чет- ность аргумента x. Протокол подбрасывания монеты (схема Блюма–Микали) 1. Абонент А выбирает случайное число X x A (подбрасы- вает монету), вычисляет A A x F y и посылает A y або- ненту В. 2. Абонент В, получив , A y пытается угадать четность A x и посылает свою догадку А. 3. Абонент А, получив догадку от В, сообщает последнему, угадал ли он, посылая ему выбранное число A x . 4. Абонент В, получив , A x проверяет, не обманывает ли А, вычисляя значение A x F и сравнивая его с полученным на втором шаге значением A y . Суть протокола состоит в том, что абонент А связывает себя с числом , A x так как он сообщает абоненту В значение , A A x F y однако абонент В не может самостоятельно вычис- лить , A x так как x F является односторонней функцией. Следующий протокол подбрасывания монеты (рис. 6.4) осно- ван на предположении о вычислительной неразрешимости зада- чи дискретного логарифмирования. Пусть p и q – простые числа, причем q делит p – 1. Найдем такое p Z g , что 1 , mod 1 g p g q |