Защищенные вычисления

К защищенным вычислениям относятся различные протоколы, целью которых является совместное вычисление некоторого значения таким образом, чтобы скрыть это значение от всех или некоторых участников. Рассмотрим два протокола защищенных вычислений.

Сокрытие информации от оракула

Пусть укастник В – оракул, который умеет вычислять значение некоторой трудновычислимой функции f. А хочет обратиться к В за вычислением f(x), но не хочет раскрывать значение х.

Параметры протокола: конструкция (K,E,D), отвечающая требова­ниям к криптосистеме с секретным ключом и с функцией дешифрования, удовлетворяющей условию

D_k(f (E_k(x)))= f (x).             (*)

Алгоритм протокола:

1. А выбирает случайным образом ключ k, шифрует х на этом ключе: E _k (x), и посылает его В.

2. В вычисляет значение f (E _k (x)) функции от зашифрованного значения и отсылает его А.

3. А дешифрует полученное значение и получает по условию (*) значение функции.

Криптосистема с открытым ключом здесь не нужна, так как не нужно пересылать оракулу ни значение ключа, ни алгоритм дешифрования. Основное условие – наличие функций шифрования и дешифрования, удовлетворяющих условию (*).

Примером такого протокола может быть протокол вычисления трудновычислимой функции f(x) - дискретного логарифма x в Z^* _p по основанию g, (g – образующий элемент Z^* _p). В этом случае функции шифрования и дешифрования можно выбрать:

E _k (x) = x g^k mod p и D _k (y) = (y-k) mod (p-1), k Î Z^* _p-1.

Задача о двух миллионерах.

Два миллионера хотят выяснить у кого больше миллионов, но так, чтобы никто не узнал, сколько их у другого.

Параметры протокола:

Пусть a,b – секретные значения участников А и В.

В протоколе нужна криптосистема (K,E,D) с открытым ключом и число m, такое, что a£m и b£m. Пусть k - ключ участника В.

Алгоритм протокола:

1. А выбирает большое простое число х, вычисляет t =E _k (x)- a и посылает его В.

2. В выбирает простое число р, удовлетворяющее указанному ниже условию и вычисляет последовательность чисел S =(u₁, …,u_m, p) следующим образом:
, где z_i= D _k (t+i)mod p,
а р выбирается так, чтобы для " i¹j выполнялось ½ z_i - z_j ½>1.
Заметим, что при этом y_a=x.

3. А посылает В сообщение «а £ b», если u_a=x mod p и «а > b» в противном случае.

Этот протокол имеет очевидные недостатки:

· Чем больше m, тем сложнее подобрать р, удовлетворяющее условиям.

· Участник А узнает результат раньше, чем В и может отказаться от выполнения 3-го шага.

Специальные виды электронной подписи.

Для решения задач аутентификации и обеспечения целостности информации используется цифровая подпись. Обычные протоколы электронной подписи, разрабатываемые для практического примене­ния, являются неинтерактивными (т. е. весь обмен сообщениями сос­тоит в передаче отправителем получателю подписанного сообщения). Это вызвано прежде всего требованиями к эффективности.

Однако возникают ситуации в которых к электронной подписи предъявляются дополнительные требования. Рассмотрим специальные виды электронной подписи, в которых используются многораундовые протоколы.

Слепая подпись

Смысл протокола слепой подписи состоит в том, чтобы участник В подписал предложенное участником А сообщение, не получив информа­ции об этом сообщении. В «бумажном» документо­обороте такая схема может быть реализована с помощью запечатанно­го конверта, в котором находится документ, а поверх него лист копир­ки. Такая подпись используется, например, в финансовой криптогра­фии для обеспечения свойства неотслеживаемости электронных денег.

В цифровом варианте слепая подпись представляет собой частный случай сокрытия информации от оракула. Сообщение m путем шифро­вания упаковываетя в цифровой конверт P (m), который подписывается S (P (m)). При вскрытии конверта получается подпись для m: P ^-1(S (P (m))).

Приведем реализацию слепой подписи R S A.

Протокол создания слепой подписи RSA под сообщением m ÎZ_m

  Ключи участника В: (n,e) – открытый и (n,d) – секретный.

1. А ® В P (m)=mr^e mod n, r ÎZ^* _n

2. В ® А S (P (m))= P (m) ^d mod n

А вычисляет P ^-1 (S (P (m)))= r^-1 S (P (m))= m^d mod n

Как правило, необходимо, чтобы В подписывал только сообщения из некоторого множества «приемлемых» сообщений М, но не знал, какое именно сообщение он подписал.

Протокол создания слепой подписи RSA под приемлемым сообщением m ÎМ.

Ключи участника В: (n,e) – открытый и (n,d) – секретный.

Пусть m₁,..., m_k ÎМ – сообщения, для одного из которых будет получена цифровая подпись.

1. А ® В (P ₁(m₁),..., P _k(m_k)), где P_i (m_i)= m_i^e mod n, r_i ÎZ^* _n " i =1,..., k

2. В ® А выбирает номер конверта j Î{1, …, k }, который подпишет.

3. А ® В " (r_i) i¹j, А открывает все конверты, кроме j -го, В проверяет, что " i¹j сообщения приемлимые m_i ÎМ.

4. В ® А S (P_j (m_j))= P (m_j) ^d mod n.

А вскрывает подписанный конверт, то есть вычисляет подпись для т:

P ^-1 (S (P (m_j))) = r^-1 S (P (m_j))= m_j^d mod n.

Вероятность того, что А удастся получить подпись под неприемлемым сообщением, не превосходит k ^-1.

Невидимая подпись.

Можно сделать так, чтобы подпись доказывающего участника Р (prover) не могла быть проверена проверяющим V (verifier) без участия Р. При этом получится так называемая невидимая подпись или неоспоримая подпись (undeniable signature, термин ввел David Chaum, впервые предло­живший такую схему).

Применение невидимой подписи:

Ø предоставление фирмой возможности проверить подлинность распространяемого программного продукта только зарегистрированным пользователям;

Ø осуществление безбумажного документооборота внутри организации так, чтобы в случае утечки документа за пределы организации нельзя было доказать его подлинность.

Параметры системы:

Группа Z_р, где р — простое число.

Пусть g Î Z_р - образующий элемент (делит р-1).

Ключи участника Р:

x ÎZ_р — закрытый ключ,

y=g^x — открытый ключ.

Создание подписи:

z = S (h)= h^x mod p, где h Î Z_р —хэш-функция сообще­ния.

1. P ® V    число w=h^ag^b mod p, где a,b Î Z_р. - выбранные Р числа.

2. V ® P    пару чисел (r,s), где r= wg^t = h^ag^b+t mod p.

где t ÎZ_р - выбранное V число и s=r^x mod p.

3. P ® V    пару чисел (a,b)

и Р проверяет, что w=h^ag^b mod p.

4. V ® P    число t

и V проверяет, что r= h^ag^b+t и s=z^a y^b+t mod p.

Утверждение (надежность протокола). Даже обладая неограничен­ной вычислительной мощностью, Р не может с вероятностью, большей р, дать верные ответы при неверной подписи.

Утверждение (безопасность протокола). В ходе протокола не происходит раскрытия информации о закрытом ключе Р, поскольку V может самостоятельно построить все сообщения протокола с тем же распределением, но без участия Р.

1.32. Разделение секрета

Криптографические схемы разделения секрета были независимо откры­ты Шамиром (A. S hamir) и Блэкли (G. R. Blakley). Основное назначение протоколов или схем разделения секрета - управление ключами. Во многих прак­ти­ческих приложениях доступность информации зависит от одного-единственного секретного ключа. Если ключ каким-либо образом утерян (потерян но­ситель с записанным ключом, разрушена память, в которой хранится ключ, и т.д.), доступ к информации блокируется. Схемы разделе­ния секрета позволя­ют решить сформулирован­ную проблему. Идея заклю­чается в разделении секретно­го ключа на ком­поненты с последу­ющим их распределением среди легального сооб­щества участников. Восстановление ключа возможно только в том случае, если некоторая легальная коалиция участников объединит свои ключевые компоненты.

С точки зрения математики задача разделения секрета является преж­де всего комбинаторной задачей. Отметим, что первая постановка задачи была сформулиро­вана в виде следующей комбинаторной проблемы. Рассмотрим ситуацию, в которой одиннадцать ученых работают над секрет­ным проектом. Рабочие документы проекта заперты в сейфе. Условие задачи — только шесть и более ученых, объединившись и предъ­явив ключи, могут отпереть сейф и получить доступ к докумен­там.

Постановка задачи сводится к оценке наименьшего числа замков сейфа и наименьшего числа ключей у каждого из ученых. В качестве реше­ния предлагается следующее рассуждение. По условию сущест­вует как минимум один замок, который не может быть открыт ни одним ученым из произвольной пятерки. Таким образом, каждый из шести остав­шихся ученых имеет ключ от этого замка. Причем нет необ­хо­димос­ти в более чем одном подобном замке для коалиции из пяти ученых. Таким образом, минимальное число замков и клю­чей оценивается как число сочетаний =462 и и =252 соот­вет­ствен­но. Очевидно, что предлагаемое комби­наторное решение неприемлемо с практической точки зрения.

Криптографические схемы разделения секрета предлагают иное решение проблемы. Рассмотрим ее как группо­вой криптогра­фический протокол с некоторым множеством участников.

Обычно в протоколах мы рассматри­вали пару взаимодействующих участников (А, В). В групповых протоколах вместо А будем рассмат­ривать группы участни­ков (А _{i 1},...,А _ik,С), где участники выбираются из множества возможных уча­стников U={А₁,...,А_l} (их иногда называют процессорами). При этом все А _i и В взаимодействуют только с выде­ленным участ­ником С. Участник С называется комбинатором (combi­ner)или дилером (иногда, лидером) и добавлен для достиже­ния анонимности, чтобы В не мог узнать о составе группы А _i.

На множестве U выделяется структура доступа Г — множество под­множеств U, называемых разрешенными коалициями. Множество Г обычно монотонно по включению: если V Ì V ` и V `ÎГ, то V ÎГ. Протокол должен быть работоспособен, если {А _{i 1},...,А _{i k} }Î Г.

Как и в других типах криптографических протоколов, в протоко­ле разделе­ния секрета участники, вообще говоря, не доверяют друг другу, и каждый из них может оказаться противником, в том числе и дилер. Групповой криптографический протокол должен отвечать следующим свойствам.

· Надежность. Для любой разрешенной коалиции {А _{i 1},..., А _{i k} }Î Г прото­кол ((А _{i 1},...,А _{i k}, С), В) удовлетворяет требованиям надежности и безо­пасности.

· Групповая безопасность. Для любой неразрешенной коалиции
{А _{i 1},...,А _{i k} }Ï Г никакие заговорщики А _i1 ^*,..., А _ik ^*,С^* такие, что любой А _i ^* и С^* имеет доступ к секретам всех А _i и С, не могут нарушить надежность системы.

В дальнейшем будем рассматривать коалиции участников как подмноже­ства множества номеров участников IÎГÍ{1, ...,l }=L.

Помимо схем разделения секретов групповые протоколы чаще всего используются для решения следующих задач:

Ø групповое вычисление значения некоторой функции — может применяться для построения групповых криптосистем, групповой подписи, групповой идентификации /протоколы конфиденциаль­­­ных вычислений/;

Ø групповая генерация псевдослучайных чисел;

Ø анонимная почта и удаленное тайное голосование.

Но круг приложений схем проверяемого разделения секрета существенно шире.