Теория процессов
 Скачать 1.62 Mb.
|
A и K − A обозначают сопоставленные ему ключи шифрования и дешифрования в этой СШ, причём – ключ шифрования K + A (называемый открытым клю- чом (ОК) агента A) известен всем агентам – ключ дешифрования K − A (называемый закрытым клю- чом (ЗК) агента A) известен только агенту A (т.е. если какой-либо агент докажет, что он умеет де- шифровать сообщения вида K + A (m), то он совпадает с A) Главные различия между СШ с открытым ключом и симмет- ричными СШ заключаются в следующем: 293 • по сравнению с симметричными СШ, СШ с открытым клю- чом являются существенно более стойкими к атакам, свя- занным с нарушением конфиденциальности зашифрован- ных сообщений путём криптоанализа, • однако сложность выполнения операций шифрования и де- шифрования в СШ с открытым ключом примерно на три порядка выше сложности этих операций в симметричных СШ. Поэтому во многих КП использование этих СШ носит комбини- рованный характер: • Симметричные СШ используются для основной связи, но ключи, используемые в этих СШ, регулярно обновляются. Это делается для того, чтобы у противника, перехватываю- щего сообщения, не было большого количества перехвачен- ных сообщений, зашифрованных на одном и том же ключе, по которым он мог бы – вычислить используемый ключ, – или иным образом нарушить конфиденциальность путём криптоанализа перехваченных сообщений. • Новые ключи для симметричных СШ пересылаются ис- пользующим их агентам в зашифрованном виде, причём шифрование этих ключей происходит с использованием СШ с открытым ключом. 8.5.3 Формальное описание КП Одним из простейших видов формального описания КП являет- ся задание списка Σ действий, каждое из которых имеет вид A → B : m (8.36) где A и B – имена агентов, и m – выражение, значением которо- го является сообщение или неопределённый объект. Выполнение действия (8.36) происходит следующим образом. Если значение выражения m определено, то 294 • A посылает B сообщение, равное значению выражения m, и • B принимает это сообщение. Если значение выражения m не определено, то это действие про- пускается. Действия, входящие в список Σ, выполняются в соответствии с тем порядком, в котором они входят в этот список. Если теку- щее действие не относится к какому-либо из агентов, то этот агент не функционирует в момент исполнения этого действия. В описание КП могут также входить условия, выражающие, например, меру доверия одних агентов другим агентам. 8.5.4 Примеры КП КП продажи компьютера У A есть компьютер, а у B есть деньги. B хочет купить у A компьютер, для чего B должен передать A деньги, а A должен передать B компьютер. A и B не верят друг другу, поэтому • A хочет сначала получить деньги, и после этого передать B компьютер • B хочет сначала получить компьютер, и после этого отдать A деньги. Таким образом, решить проблему продажи компьютера сила- ми лишь A и B невозможно. Данная проблема может быть решена при помощи КП, в ко- тором кроме A и B принимает участие доверенный посредник T , относительно которого у A и B имеется уверенность в том, что T будет точно выполнять все действия, предписанные ему этим КП. Искомый КП может иметь следующий вид: • A → T : компьютер • B → A: деньги 295 • A → T : подтверждение или опровержение того, что полу- ченная от B сумма соответствует стоимости компьютера (A посылает опровержение вместе с деньгами B) • T → B : (от A поступило подтверждение) ? компьютер • T → A : (от A поступило опровержение) ? компьютер В этом КП значение выражения вида b?m, где b – условие, и m – сообщение • равно m, если b истинно, и • не определено, если b ложно. Читателю предлагается самостоятельно • разработать язык спецификаций, в терминах которого мож- но было бы – выразить условие того, что A и B доверяют посредни- ку T , и – сформулировать спецификацию Spec, выражающую свой- ство корректности этого КП • проанализировать соответствие этого КП спецификации Spec – с учётом условия, что A и B доверяют T , и – без учёта этого условия. Обедающие криптографы За круглым столом сидят три криптографа и обедают. После того, как они пообедали, официант сообщает им, что их обед полностью оплачен, но не уточняет, кто именно платил. Возможен один из двух вариантов: • обед оплатил один из криптографов, • за обед заплатила ФСБ. 296 Криптографы хотят выяснить, какой именно из вариантов име- ет место, причём, если имеет место первый вариант, то те из них, которые не платили, не должны узнать, кто же конкретно заплатил. Для решения этой задачи предлагается следующий КП. Поскольку криптографы сидят за круглым столом, то каж- дая пара соседей может подбрасывать монету между собой, так, чтобы результат был известен только им двоим. После того, как все три пары подбросили монету, каждый из них знает результаты двух подбрасываний (решка или орёл), которые могут быть • либо одинаковыми (оба раза была решка, или оба раза был орёл), • либо разными (один раз была решка, а другой - орёл). Каждый криптограф говорит другим “одинаково” или “по раз- ному”, причём тот, кто заплатил, говорит противоположное (т.е. если надо сказать “одинаково” то он говорит “по-разному”, и на- оборот). Если число ответов “по разному” чётно, то это значит, что обед оплатила ФСБ, иначе - один из них. Подтверждение приёма Имеется группа агентов, которые используют одну и ту же СШ с открытым ключом, обладающую следующим свойством: алго- ритм дешифрования этой СШ может использоваться также и для шифрования, причём имеет место условие: для каждого агента A и каждого сообщения m K + A (K − A (m)) = m (8.37) (большинство СШ с открытым ключом обладает этим свойством). Члены этой группы хотят обмениваться друг с другом за- шифрованными сообщениями. Если, например, агент A хочет послать агенту B сообщение m, то для этого A и B предполагают использовать следующий 297 КП из двух действий: ( A → B : (A, K + B (K − A (m))) B → A : (B, K + A (K − B (m))) т.е. A посылает B пару, состоящую из • своего имени (A), чтобы B знал, от кого ему пришло сооб- щение, и • шифрованного сообщения K + B (K − A (m)). Получив сообщение K + B (K − A (m)), агент B при помощи своего ЗК K − B извлекает из него сообщение K − A (m), из которого он, ис- пользуя ОК K + A , может извлечь m (это возможно на основании (8.37)). Второе действие в этом КП представляет собой подтвержде- ние агентом B получения сообщения от A: оно посылается от- правителю для того, чтобы он был уверен, что его сообщение m дошло до B в неискажённом виде. К сожалению, данный КП не содержит механизма противо- действия угрозам, связанным с мошенничеством. Если некото- рый агент M из этой группы перехватил сообщение (A, K + B (K − A (m))) то он может извлечь из него сообщение m, например, следующим способом. • M посылает B сообщение (M, K + B (K − A (m))) • B обрабатывает его в соответствии с КП, т.е. извлекает из него вторую компоненту и вычисляет сообщение K + M (K − B (K + B (K − A (m)))) = K + M (K − A (m)) • Получившийся результат не содержит никакого смысла, но, согласно используемому КП, B обязан послать M подтвер- ждение (B, K + M (K − B (K + M (K − A (m))))) • Из полученного сообщения агент M , используя свой ЗК K − M и известные ему ОК K + B и K + A , извлекает m. 298 КП двусторонней аутентификации Имеется группа агентов, которые используют • одну и ту же СШ с открытым ключом, и • одну и ту же симметричную СШ. Члены этой группы хотят обмениваться друг с другом за- шифрованными сообщениями. Каждая пара агентов A, B из этой группы использует для основной связи симметричную СШ, и в процессе своего взаимо- действия A и B предполагают регулярно обновлять ключи шиф- рования для этой СШ, т.е. • некоторый промежуток времени (который называется се- ансом взаимодействия) агенты A и B используют для шифрования своих сообщений один ключ (называемый се- ансовым ключом), • затем при помощи СШ с открытым ключом этот ключ об- новляется, и для шифрования сообщений в следующем се- ансе взаимодействия A и B используется новый сеансовый ключ • и т.д. В целях противодействия возможному мошенничеству, члены группы хотят производить обновление сеансовых ключей при по- мощи КП, который должен решать следующие задачи: • агенты A и B, желающие создать новый сеансовый ключ, должны принимать равноправное участие в создании этого ключа • перед тем, как начать очередной сеанс взаимодействия, они хотят удостовериться в подлинности друг друга, т.е. – агент A намерен удостовериться, что тот агент, сов- местно с которым он генерирует новый сеансовый ключ, это действительно B, а не мошенник, выступающий от имени B, и 299 – агент B имеет аналогичное намерение. Процедура взаимодействия агентов, целью которой является проверка подлинности кого-либо из них, называется аутенти- фикацией этого агента. Если в результате взаимодействия A и B они доказывают свою подлинность друг другу, то такая аутен- тификация называется двусторонней. Агенты A и B собираются решить задачи • двусторонней аутентификации, и • генерации нового сеансового ключа K AB при помощи следующего КП из трёх действий (данный КП назы- вается КП Нидхема - Шредера (Needham - Schroeder, 1979), мы будем сокращённо обозначать его знакосочетанием NS): A → B : K + B (A, N A ) B → A : K + A (N A , N B ) A → B : K + B (N B ) где • символ A в первом сообщении обозначает имя агента A, • символы N A и N B обозначают битовые строки, длина ко- торых равна длине создаваемого сеансового ключа K AB Данные строки называются нонсами. Как правило, нонс представляет собой псевдослучайную последовательность битов. Нонсы предназначены для решения следующих двух задач. 1. Каждый из нонсов является вкладом сгенерировавшего его агента в формирование ключа K AB : данный ключ по опре- делению полагается равным побитовой сумме по модулю 2 битовых строк h(N A ) и h(N B ), где h – некоторая хэш- функция. Нетрудно видеть, что условие равноправного участия аген- тов A и B в формировании ключа K AB выполнено. 300 2. Нонсы решают задачу аутентификации следующим обра- зом. • Когда B посылает A сообщение K + A (N A , N B ), он тем самым демонстрирует свою способность извлечь из по- лученного им зашифрованного сообщения K + B (A, N A ) нонс N A (т.к., по предположению, B не мог получить нонс N A никаким другим способом). Это убеждает A в том, что тот агент, с которым он вза- имодействует, знает ЗК K − B (т.к., по предположению, не зная K − B , извлечь сообщение m из сообщения ви- да K + B (m) невозможно), т.е. этот агент действительно есть B. • Когда A посылает B сообщение K + B (N B ), он тем самым демонстрирует свою способность извлечь из получен- ного им зашифрованного сообщения K + A (N A , N B ) нонс N B (т.к., по предположению, A не мог получить нонс N B никаким другим способом). Это убеждает B в том, что тот агент, с которым он вза- имодействует, знает ЗК K − A (т.к., по предположению, не зная K − A , извлечь сообщение m из шифртекста ви- да K + A (m) невозможно), т.е. этот агент действительно есть A. Одна из уязвимостей данного КП связана с тем, что один из агентов (например, B) может мошенничать, выдавая себя за другого агента. Работа КП NS в этом случае может иметь сле- дующий вид. 1. После того, как агент A выразит желание взаимодейство- вать с B по КП NS, и пришлёт ему первое сообщение (т.е. K + B (A, N A )), агент B может использовать это сообщение для того, чтобы • взаимодействовать по КП NS с ещё одним агентом C, • и в этом взаимодействии B будет выдавать себя за агента A. Для этого B 301 • договаривается с C о взаимодействии с ним по КП NS, • и посылает ему сообщение K + C (A, N A ). Получив это сообщение и расшифровав его, C делает вы- вод, что это сообщение было послано агентом A (о чём гово- рит ему первая компонента расшифрованного сообщения). На основании этого, C • генерирует нонс N C , и • посылает агенту B сообщение K + A (N A , N C ) (8.38) (думая, что он посылает его агенту A) 2. B пересылает полученное от C сообщение (8.38) агенту A, эта пересылка представляет собой второе действие в КП NS взаимодействия A и B. 3. A рассматривает извлечённую из полученного сообщения (8.38) компоненту N C как нонс, сгенерированный агентом B. В соответствии с третьим действием КП NS взаимодей- ствия A и B, агент A посылает агенту B сообщение K + B (N C ) B извлекает N C , и посылает агенту C сообщение K + C (N C ). C рассматривает эту пересылку как третье действие в КП NS взаимодействия A и C. После этого B знает нонсы N A и N C , которые позволит ему вычислить сеансовый ключ для шифрованного взаимодействия с C, в котором он будет выступать от имени A. Читателю предлагается самостоятельно • разработать язык спецификаций, в терминах которого мож- но было бы выразить свойство КП противодействовать мо- шенничеству описанного выше вида, и • разработать алгоритм проверки соответствия КП специфи- кациям, выраженным на этом языке. 302 Глава 9 Представление структур данных в виде процессов 9.1 Понятие структуры данных Структура данных (СД) – это дискретная динамическая си- стема, каждое состояние которой можно интерпретировать как совокупность данных (т.е. некоторых значений), хранящихся в текущий момент в этой системе. Как правило, каждое состояние СД представляет собой сово- купность из нескольких компонентов, каждая из которых явля- ется содержимым некоторого ресурса (например, содержимым ячейки памяти). Одним из способов формального описания СД является пред- ставление их в виде процессов. Если процесс P является представлением некоторой СД, то имена в P можно интерпретировать как точки доступа к данным, содержащимся в этой СД. Объекты, соответствующие этим име- нам, могут иметь виртуальный характер. Например, в качестве таких объектов могут выступать криптографические ключи. Представление СД в виде процессов позволяет формализо- вать понятие активных данных (= знаний), которые развивают- ся в результате наличия у них неполноты или противоречивости. Активность структур данных заключается в том, что они могут сами инициировать запросы к окружающей среде с целью полу- 303 чения дополнительной информации для достижения согласован- ности в знаниях, которые содержатся в этих СД. В этой главе мы приводим несколько примеров описания СД в виде процессов. Каждый из этих процессов задаётся в виде рекурсивного определения. Ниже мы будем отождествлять процесс, представляющий неко- торую СД, с самой этой СД. 9.2 СД “память с 2 k ячейками” СД “память с 2 k ячейками” (где k ≥ 0) – это процесс [[M EM k ( x)]] (9.1) где M EM k – процессное имя, и x – список из 2 k переменных вида x = {x m | m ∈ {0, 1} k } каждая из которых соответствует некоторой ячейке памяти: для каждого m ∈ {0, 1} k значение переменной x m представляет собой содержимое ячейки памяти с адресом m. Мы будем предполагать, что процесс [[M EM k ( x)]] работает следующим образом: 1. сначала, если k > 0, то через точку доступа α в процесс [[M EM k ( x)]] поступает адрес m, 2. затем через точку доступа β в процесс [[M EM k ( x)]] посту- пает значение v, которое надо записать в ячейке по адресу m 3. после чего через точку доступа γ процесс [[M EM k ( x)]] вы- даёт значение, которое содержалось в ячейке по адресу m до выполнения предыдущего шага. Процессы, соответствующие процессным выражениям вида M EM k ( x), определяются следующим РО: • M EM 0 (x) = β?y . γ!x . M EM 0 (y) (процесс [[M EM 0 (x)]] – это - ячейка памяти, хранящая зна- чение x) 304 • для каждого k ≥ 0 M EM k+1 ( x · y) = = SW IT CH | M EM k ( x) [ α 0 /α, β 0 /β, γ 0 /γ ] | M EM k ( y) [ α 1 /α, β 1 /β, γ 1 /γ ] \ ( α 0 , β 0 , γ 0 , α 1 , β 1 , γ 1 ) где – x · y – список из 2 k+1 различных переменных, пред- ставленный в виде конкатенации двух списков из 2 k переменных – SW IT CH - это процесс, называемый переключате- лем, и представляемый следующей блок-схемой: START α?m ˆ m = 0 α 0 !m 0 β?u β 0 !u γ 0 ?y γ!y α 1 !m 0 β?u β 1 !u γ 1 ?y γ!y ? s ? + ? ? ? ? ? - − ? ? ? ? ? где 305 – ˆ m = первый бит в битовой строке m, и – m 0 = строка из k−1 битов, получаемая из m удалением первого бита. Процесс [[M EM k+1 ( x · y)]] изображается следующим потоко- вым графом: ' & $ % ' & $ % ' & $ % M EM k ( x) M EM k ( y) SW IT CH d d t d d t d d t @ @ @ R @ @ @ R @ @ @ @ I t t d t t d α β γ α 0 β 0 γ 0 α 1 β 1 γ 1 Читателю предлагается самостоятельно доказать, что про- цесс [[M EM |