Протоколы разделения секрета реферат
Обновлено: 04.07.2024
Успешное решение задачи открытого распределения ключей, создание практических схем электронной подписи способствовало возникновению нового направления криптографии - теории криптографических протоколов. Для современных информационных систем характерен перевод всего документооборота в электронную форму. Возникающие при этом проблемы чаще всего могут быть решены только с использованием возможностей криптографии.
Типичный пример: взаимодействуют два удаленных абонента А (клиент банка) и В (банк). Абонент А хочет доказать абоненту В, что он тот, за кого себя выдает, а не злоумышленник . Для решения этой задачи требуется протокол аутентификации абонента. В каждом конкретном случае для обеспечения юридической значимости пересылаемых электронных документов требуется использование соответствующих криптографических протоколов, которые за последние годы превратились в основной объект исследований криптографии.
3.7.1. Основные понятия
Объектом изучения теории криптографических протоколов являются удаленные абоненты, взаимодействующие по открытым каналам связи. Целью взаимодействия является решение какой-либо практической задачи. Модель предусматривает наличие противника, преследующего собственные цели. Противник может выдавать себя за законного субъекта взаимодействия, вмешиваться в информационный обмен между абонентами и т.п. Участники протокола в общем случае не доверяют друг другу, другими словами, некоторые протоколы должны быть рассчитаны на ситуацию, когда противником может оказаться даже один из абонентов или несколько абонентов, вступивших в сговор. В настоящее время известно около трех десятков различных типов протоколов. Все эти типы можно разделить на две группы:
- прикладные протоколы, решающие конкретную задачу, которая может возникнуть на практике;
- примитивные протоколы, которые используются в качестве своеобразных строительных блоков при создании прикладных протоколов.
Типы протоколов приведены на рис. 3.25.
3.7.2. Доказательства с нулевым разглашением
Существенное влияние на разработку многих криптографических протоколов оказали исследования двух математических моделей - интерактивной системы доказательств (Interactive Proof System) и доказательств с нулевым разглашением знаний (Zero-Knowledge Proofs).
-
полнота - если S действительно истинно, то доказывающий убедит проверяющего признать это;
корректность - если S ложно, то доказывающий не сможет убедить проверяющего в обратном.
Если предположить, что V может быть противником, который хочет получить информацию об утверждении S, необходим протокол (P, V, S), называемый доказательством с нулевым разглашением, удовлетворяющий помимо перечисленных еще и следующему условию:
Иными словами, в результате реализации протокола абонент P сможет доказать абоненту V, что он владеет некоторой секретной информацией, не разглашая ее сути.
Упрощенно процедуру доказательства с нулевым разглашением можно представить следующим образом. Проверяющий задает серию случайных вопросов, каждый из которых допускает ответ "да" или "нет". После первого вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятностью 1/2. После второго вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятностью 1/4, и т.д. (после каждого вопроса знаменатель удваивается). После 100 вопросов вероятность того, что доказывающий заблуждается или не располагает доказательством (не владеет секретной информацией), становится настолько близкой к нулю, что даже у самого "недоверчивого" проверяющего не должно остаться сомнений в справедливости доказываемого утверждения. После 300 вопросов знаменатель достигает величины, которая превосходит число атомов во Вселенной.
Роль доказательств с нулевым разглашением особенно велика при реализации протоколов аутентификации. Допустим, например, Р - алгоритм, реализованный в интеллектуальной карточке клиента (абонент А) банка, V - программа, выполняемая компьютером банка (абонент В). Перед выполнением любой операции банк должен убедиться в подлинности карточки и идентифицировать ее владельца. Если для этой цели использовать протокол (P, V, S), свойство полноты позволит карточке доказать свою аутентичность; свойство корректности защитит интересы банка от злоумышленника, который попытается воспользоваться фальшивой карточкой; свойство нулевого разглашения защитит клиента от злоумышленника, который попытается пройти аутентификацию под именем абонента А, воспользовавшись информацией, перехваченной во время предыдущих раундов аутентификационного обмена. Аналогичных результатов можно добиться, используя методы доказательств с нулевым разглашением для создания не поддающихся подделке удостоверений личности.
3.7.3. Протоколы разделения секрета
Эффективным методом защиты является разделение доступа (не путать с разграничением доступа), разрешающее доступ к секретной информации только при одновременном предъявлении своих полномочий участниками информационного взаимодействия, не доверяющих друг другу. Протоколы или схемы разделения секрета (СРС) (Secret Sharing Scheme) позволяют распределить секрет между n участниками протокола таким образом, чтобы заранее заданные разрешенные множества участников могли однозначно восстановить секрет, а неразрешенные - не получали бы никакой информации о возможном значении секрета. Выделенный участник протокола, распределяющий доли (share) секрета, обычно называется дилером (D).
Пусть M - защищаемая информационная последовательность (битовая строка) длиной m. Простейшая схема разделения секрета между тремя абонентами A, B и C имеет следующий вид.
Шаги 1 и 2 - это стадия распределения долей секрета. Шаг 3 - стадия восстановления секрета. Каждая доля секрета сама по себе не имеет никакого смысла, но если их сложить, смысл исходной информационной последовательности полностью восстанавливается. При правильной реализации приведенный протокол полностью безопасен, так как для закрытия информации применяется абсолютно стойкий шифр, описанный ранее, и поэтому никакие вычисления не смогут помочь при попытке определить секрет по одной или двум его частям. Аналогичную схему можно легко реализовать для любого числа участников.
Рассмотрим схему разделения доступа Шамира. Пусть n - число участников протокола, GF (p) - конечное поле из p элементов, p - простое, p > n. Поставим в соответствие каждому i-му участнику ненулевой элемент поля и, положим, .
Схема разделения доступа Шамира.
- Стадия распределения долей секрета. Дилер СРС вырабатывает t – 1 независимых равномерно распределенных на GF (p) случайных чисел
X^ + R_ X^ + \ldots + R_1 X + R_0" />
, где .
.
Схемы подобного типа находят применение при построении пороговых структур доступа и носят название (n, t)-пороговых СРС. Такие схемы, например, позволяют владельцу некоей секретной информации распределить эту информацию при хранении на n своеобразных ее дубликатов таким образом, что ему для восстановления секрета достаточно получить доступ к любым t из них. При этом никакие t – 1 дубликатов не предоставляют никакой информации об этом секрете.
3.8. Контроль целостности информации
3.8.1. Аутентичность. Задача аутентификации информации
В информационных системах помимо обеспечения секретности информации необходимо также решать не менее важную задачу аутентификации обрабатываемых массивов данных. Информация может считаться аутентичной, когда потребитель имеет гарантии, во-первых, целостности информации, а во-вторых, ее авторства, иначе говоря, подлинности.
На самом деле приведенные рассуждения ошибочны. Искажения, внесенные в зашифрованные данные, становятся очевидны после расшифрования только в случае большой избыточности исходных данных. Эта избыточность имеет место лишь в некоторых частных случаях, например когда исходная информация является текстом на естественном или искусственном языке. В общем случае требование избыточности данных может не выполняться, а это означает, что после расшифрования модифицированных данных они по-прежнему могут поддаваться интерпретации.
При использовании симметричной криптосистемы факт успешного расшифрования данных, зашифрованных на секретном ключе, может подтвердить их авторство лишь для самого получателя. Третий участник информационного обмена, арбитр, при возникновении споров не сможет сделать однозначного вывода об авторстве информационного массива, так как его автором может быть каждый из обладателей секретного ключа, а их, как минимум, двое.
Таким образом, секретность и аутентичность суть различные свойства информационных систем, поэтому традиционно задачи обеспечения секретности и аутентичности решаются различными средствами.
Для обнаружения искажений в распоряжении законного пользователя (например, получателя информации при ее передаче) должна быть некая процедура проверки Т (М), дающая на выходе 1 (если в массиве данных М отсутствуют искажения) или 0, если такие искажения имеют место. С целью ограничения возможностей противника по подбору информационной последовательности М` (M`M), где М - правильная последовательность (без искажений), для которой Т (М`) = 1, идеальная процедура такой проверки должна обладать следующими свойствами:
.
увеличить изображение
Рис. 3.26. Схемы контроля целостности: а - с использованием зашифрования; б - с формированием контрольного кода; в - с формированием контрольного кода и зашифрованием
Самый естественный способ преобразования информации с внесением избыточности - это добавление к исходным данным контрольного кода S фиксированной разрядности N, вычисляемого как некоторая функция от этих данных:
T (M`) = 1, если S = F (M`), и T (M`) = 1, если S F (M`).
Функция F формирования контрольного кода должна удовлетворять следующим требованиям:
Второе свойство можно обеспечить двумя способами: либо сделать функцию F зависимой от некоторого секретного параметра (ключа), либо пересылать контрольный код отдельно от защищаемых данных.
Простейшим примером кода S является контрольная сумма блоков массива данных. Например, если
,
Что такое схемы разделения секрета и зачем они нужны?
Начну свое повествование с примера, описанного в книге неизвестного бельгийского автора "Gent und seine Schönheiten". В городе Генте была построена ратушная башня, в одной из комнат которой хранились очень важные документы. Эти документы лежали в шкафу, закрывавшемся на три замка, шкаф - в яйце, яйцо - в утке, утка - в зайце. Один ключ от шкафа хранился у фогта, а два других – у главного шеффена. В секретной комнате было две двери, каждая с тремя замками. Ключи от этих замков находились во владении различных цехов. Таким образом, получить доступ к документам могли только совместно собравшиеся представители трех цехов, фогт и шеффен.
На этом ярком примере можно понять основной смысл схем разделения секрета. Чтобы получить доступ к зашифрованным данным, необходимо присутствие нескольких доверенных лиц, у каждого из которых будет часть секрета. Собрав все части вместе, пользователи могут довольствоваться расшифрованной информацией.
Такие протоколы используются в случае возможности компрометации одного или нескольких участников схемы разделения секрета. Чем больше хранителей различных "ключей от шкафов и дверей", тем больше вероятность того, что секрет восстановится честным способом и информация не окажется в руках злоумышленников.
Основные понятия
В своей статье я буду использовать следующие установившиеся термины:
Доля секрета - некоторая уникальная для каждого участника процесса информация, помогающая восстановить секрет
Дилер - доверенное лицо, которое производит распределение долей секрета между участниками
Разделение секрета - фаза подсчета и раздачи долей секрета
Восстановление секрета - фаза сбора долей секрета и подсчета самого́ секрета
Пороговые схемы разделения секрета
В городе Генте для получения доступа к документам обязательным условием было присутствие всех хранителей ключа. Но что если фогт заболеет, а представитель одного из цехов потеряет ключ? Неужели тайны города Генте будут навсегда утеряны?
Что было с городскими документами история умалчивает, но понимая последствия подобных протоколов разделения секрета, люди придумали пороговые (t, n) схемы. Имея n частей секрета, можно восстановить его, используя только t из них. Если любая группа из t-1 или меньше сторон не могут восстановить секрет, то такая схема называется совершенной. В случае, когда размер долей секрета такой же, как и у самого секрета, то схема называется идеальной.
Если бы работники администрации города Генте знали о таком методе, они бы выбрали n хранителей ключей, но построили бы систему безопасности таким образом, что нужно было бы не менее t из n участников процесса чтобы получить доступ к секрету. Однако, в случае заговора, несколько хранителей ключа, количество которых было бы меньше t, не смогли бы открыть двери и украсть документы.
Рассмотрим далее несколько пороговых схем, которые не так популярны, как, например, схема Блэкли и схема Шамира.
Схема Миньотта
Данный метод основан на китайской теореме об остатках. Звучит она следующим образом:
Если натуральные числа взаимно просты, то для любых чисел таких, что при всех найдется число которое при делении на дает остаток для всех . Более того, если найдутся два таких числа и , то .
Иными словами, теорема позволяет утверждать о единственности решения системы:
В схеме Миньотта используются так называемые последовательности Миньотта – последовательности взаимно простых положительных чисел
такие, что при том, что n – целое, и .
Наконец, опишем алгоритм схемы разделения секрета. Имеется открытая последовательность Миньотта, из которой выбирается случайным образом секрет S. Обозначим
и потребуем чтобы .
Задача дилера в этом случае заключается в вычислении долей секрета по формуле и распределении их между участниками.
Восстанавливается секрет с помощью t значений . Составляется система:
По китайской теореме об остатках она имеет единственное решение, лежащее в пределах так как . В случае попытки решить систему имея t-1 долей секрета, можно считать, что где – единственное решение системы с t-1 уравнениями. Отсюда следует, что подобрать секрет будет тем сложнее, чем больше будет последовательность Миньотта, то есть чем выше значение .
Очевидно, что схема разделения секрета Миньотта не обладает высокой криптографической стойкостью, так как в худшем случае может быть взломана перебором, то есть не является совершенной. Более того, во многих случаях данный метод может быть неудобен требованиями ограничения секрета и генерации больших последовательностей Миньотта, что является довольно ресурсоемкой задачей. Так как размер секрета совпадает с его долей, то схема – идеальная.
Схема Карнина-Грина-Хеллмана
Следующая схема основана на том, что невозможно однозначно решить систему c t неизвестными, имея меньше, чем t уравнений. Все действия происходят в конечном поле. На этапе разделения секрета случайным образом выбирается n+2 различных векторов размерности t так, чтобы ранг любой матрицы размером t x t, составленной из этих векторов, был равен t (то есть все вектора выбираем попарно линейно независимыми). При этом значения являются открытыми. Секретом S будет служить скалярное произведение а долями секрета – скалярные произведения .
Восстановление секрета происходит с помощью решения системы линейных алгебраических уравнений из t уравнений и t неизвестных относительно компонент вектора U:
Система имеет единственное решение, так как на этапе распределения секрета выбирались линейно независимые векторы, значит определитель матрицы не равен нулю. Найдя вектор U, легко восстановить секрет путем вычисления скалярного произведения .
Если злоумышленник получит меньше, чем t значений, система будет иметь бесконечное количество решений и любое из них равновероятно может быть искомым секретом. Это означает, что схема Карнина-Грина-Хеллмана является совершенной. Однако, размер каждой доли секрета в t раз больше самого секрета, что делает схему не идеальной.
Применение схем разделения секрета
Для создания пороговых криптосистем могут использоваться такие системы открытого шифрования, как:
Пороговые криптосистемы используются во многих областях, например, для хранения секретного ключа центра сертификации, в государственной и военной сферах, облачных средах и схемах электронного голосования.
Источники
Karnin E. D., Greene J. W., Hellman M. E. “On Secret Sharing Systems” // IEEE, 1983.
Шнайер Б. “Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си” – Триумф, 2002
Рисунок 1. Шифрование
Дешифрование — обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный (рисунок 2).
Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов. Обычно ключ представляет собой последовательный ряд букв алфавита. [2, с. 97]
Криптосистемы разделяются на симметричные и ассиметричные (с открытым ключом).
Рисунок 2. Дешифрование
В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ: источник зашифровывает открытый текст на секретном ключе К, а приемник расшифровывает шифртекст на секретном ключе К*. Обычно К = К*.
Таким образом, в настоящее время шифрование является единственным надежным средством защиты при передаче информации.
2. Протокол разделения секретных данных
Протокол разделения секрета — протокол криптографический, реализующий схему разделения секрета в модели, где участники являются абонентами сети связи. В этой модели имеется дополнительный участник (дилер), которому известно значение секрета. Дилер генерирует доли секрета и рассылает их остальным участникам. Всякая правомочная коалиция участников может восстановить секрет, выполнив протокол восстановления секрета. Протокол разделения секрета могут найти применение в организации хранения конфиденциальной информации, например, ключей криптосистемы, а также как протоколы криптографические примитивные. [6, с. 60]
Протоколы разделения секрета призваны решить проблему хранения информации так, чтобы те группы людей, которым позволено знать секрет, могли бы его восстановить, а те группы, которым секрет знать не позволено, восстановить его не смогли даже путем перебора.
В протоколе разделения секрета имеются n участников (абонентов) Р1 , Р2 , …, Pn и один выделенный участник D, называемый дилером (раздающим). Пусть через Р= обозначено множество всех абонентов. Введем следующую терминологию:
•группа доступа (разрешенная группа) – непустое подмножество A участников множества P, которые, собравшись вместе, имеют право восстановить секрет;
•структура доступа Г будем называть непустое множество всех групп доступа.
Далее будем полагать, что любой участник Р1 , Р2 , …, Pn входит хотя бы в одну группу доступа, иначе присутствие его присутствие бессмысленно. Также считаем, что Г замкнуто, то есть если A ⊂ B ⊂ P и A⊂ Г, то B ⊂ Г. Действительно, если абоненты Р1 , Р2 , …, Pk могут совместно восстановить секрет, то, если к ним присоединятся дополнительные участники P k+2 , Р k+2 . , то получившаяся группа тем более сможет восстановить секрет.
Протокол разделения секрета состоит из двух основных фаз. [3,с. 46]
1. Разделение секрета – фаза раздачи, когда дилер, знающий секрет M , генерирует n долей m1, m 2 , . mn секрета и выдает каждому участнику его долю по защищенному каналу связи. Раздачу нужно организовать так, чтобы разрешенные группы участников, собравшись вместе, могли однозначно восстановить секрет, а неразрешенные – не могли.
2. Фаза восстановления секрета, когда какая–либо группа из структуры доступа Г объединяет свои доли секретов и получает секрет.
Таким образом, протоколы разделения секрета призваны решить проблему хранения информации так, чтобы те группы людей, которым позволено знать секрет, могли бы его восстановить, а те группы, которым секрет знать не позволено, восстановить его не смогли даже путем перебора.
3. Протокол секретного вычисления с участием многих пользователей
В криптографии протокол секретного вычисления - криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Впервые задача конфиденциального вычисления была поднята Эндрю Яо (англ. Andrew Yao) в 1982 году в статье. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения этой задачи, получившей впоследствии название проблема миллионеров. Гораздо позже, в 2004 году Йехуда Линделл (Yehuda Lindell) и Бенни Пинкас (Benny Pinkas) предоставили математически строгое доказательство корректности протокола Яо в статье. Задача конфиденциального вычисления тесно связана с задачей разделения секрета.
В конфиденциальном вычислении участвуют N участников p1, p2, …, pN. У каждого участника есть тайные входные данные d1, d2, …, dN соответственно. Участники хотят найти значение F(d1, d2, …, dN), где F — известная всем участникам вычислимая функция от N аргументов. Допускается, что среди участников будут получестные нарушители, то есть те, которые верно следуют протоколу, но пытаются получить дополнительную информацию из любых промежуточных данных. [2, с. 100]
К безопасности протоколов конфиденциального вычисления обычно предъявляются различные требования в зависимости от ситуации. Приведём основные требования.
Конфиденциальность. Никто из участников не должен иметь возможности получить больше информации, чем им предписано.
Корректность. Каждый участник должен гарантировано получить верные данные.
Гарантия получения информации. У участников не должно быть возможности помешать другим участников получить выходные данные. [4, с. 65]
Пусть миллионеры Алиса и Боб хотят выяснить, чьё состояние больше, не разглашая точную сумму своих состояний. Для определённости предположим, что у Алисы имеется i миллионов, а у Боба — j, где 1 2255
− m – порядок группы точек эллиптической кривой
− q – простое число, порядок циклической подгруппы группы точек эллиптической кривой
(m = nq, 2254
Читайте также: