Просмотр кода страницы ANDOS (криптография)

{{другие значения|2=ANDOS}}
{{Underlinked|date=март 2016}}
'''ANDOS''' ({{lang-en|All or Nothing Disclosure Of Secrets}}) — [[Криптография|криптографический]] протокол «секретной продажи секретов». Пусть продавец '''S''' секретов имеет некий список вопросов и выставляет на продажу ответы к любому из них. Предположим, покупатель '''B''' хочет купить секрет, но не хочет раскрывать какой именно. Протокол гарантирует, что '''B''' получит нужный ему секрет и ничего более, в то время как '''S''' не будет знать какой именно секрет получил '''B'''.

== Алгоритм ==
Пусть <math>s_1,...,s_k</math> секреты, которым обладает '''S''', каждый из них содержит <math>n</math> бит. Для каждого <math>s_j</math> '''S''' публикует описание секрета. Предположим, что покупатели '''B''' и '''C''' хотят купить секреты <math>s_j</math> и <math>s_{j'}</math>, соответственно. Идея в том, что покупатели имеют индивидуальные односторонние функции и каждый из них оперирует над числами, полученными другим.

: '''Шаг 1.''' '''S''' даёт '''B''' и '''C''' индивидуальные односторонние функции ''f'' и ''g'', но сохраняет обратные к ним для себя.

: '''Шаг 2.''' '''B''' сообщает '''C''' (соответственно '''C''' — '''B''') <math>k</math> случайных <math>n</math>-битных чисел <math>x_1,...,x_k</math> (соответственно <math>x_{1'},...,x_{k'}</math>).

Для <math>f</math>, отображающего <math>n</math>-разрядные числа в <math>n</math>-разрядные числа, и <math>n</math>-разрядного числа <math>x</math>, скажем, что индекс <math>i, 1 \leqslant i \leqslant n</math> — это ''Индекс Фиксированного Бита (ИФБ)'' соответствующего паре <math>(x,f)</math>, если <math>i</math>-й бит в <math>x</math> равен <math>i</math>-му биту в <math>f(x)</math>.
Ясно, что <math>i</math> есть ИФБ соответствующий паре <math>(x,f)</math>, если он является ИФБ, соответствующим паре <math>(f(x),f^{-1})</math>. Если <math>f</math> ведёт себя достаточно произвольно при изменении битов в <math>x</math> (как хорошие криптографические функции), то, для случайного <math>x</math>, можно грубо оценить, что примерно <math>\frac{n}{2}</math> индексов являются ИФБ, соответствующими <math>(x,f).</math>

: '''Шаг 3.''' '''B''' сообщает '''C''' (соответственно '''C''' — '''B''') набор ИФБ<math>_B</math> индексов, соответствующих <math>(x'_j,f)(</math> соответственно набор ИФБ<math>_C</math> индексов, соответствующих <math>(x_{j'},g)).</math>

: '''Шаг 4.''' '''B''' (соответственно '''C''') сообщает '''S''' числа <math>y_1,...,y_k</math> (соответственно <math>y_{k'},...,y_{k'}</math>, где <math>y_i</math> — результат, полученный заменой каждого бита в <math>x_i</math>, чей индекс не является ИФБ<math>_C</math>, ему противоположным (соответственно <math>y'_i</math> получаются из <math>x'_i</math> аналогичным образом).

: '''Шаг 5.''' '''S''' сообщает '''B''' (соответственно '''C''') числа
<center><math>s_i \oplus f^{-1}(y'_i)(</math> соответственно <math>s_i \oplus g^{-1}(y_i))</math> , <math>i=1,...,k</math>.</center>

: '''Шаг 6.''' '''B''' (соответственно '''C''') может вычислить <math>s_j</math> (соответственно <math>s'_j</math>), поскольку известны <math>x'_j=f^{-1}(y'_j)(</math> соответственно <math>x_{j'}=g^{-1}(y_{j'})).</math>

'''B''' и '''C''' узнали нужные им секреты. '''S''' не узнал ничего об их выборе. Кроме того, ни '''B''', ни '''C''' не узнали более одного секрета или выбора друг друга. Сговор между '''B''' и '''C''' приводит к тому, что они могут узнать все секреты. Сговор между '''S''' и кем-либо из покупателей может вскрыть какой секрет хочет другой покупатель.

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

В случае, ели число покупателей <math>t \geqslant 3</math> протокол действует абсолютно так же, но каждый покупатель получает <math>t-1</math> функцию от продавца наравне с наборами чисел от других покупателей.

== Примеры ==
* За основу односторонних функций <math>f</math> и <math>g</math> возьмём [[RSA]].

: Выберем <math>k=8,n=12</math>. Считаем, что '''S''' имеет 8 следующих 12-битных секретов на продажу:

: <math>s_1=1990,</math> <math>s_2=471,</math> <math>s_3=3860,</math> <math>s_4=1487,</math> <math>s_5=2235,</math> <math>s_6=3751,</math> <math>s_7=2546,</math> <math>s_8=4043.</math>

: '''Шаг 1.'''
:: '''S''' даёт '''B''' и '''C''' индивидуальные односторонние функции ''f'' и ''g'', основанные на простых числах <math>p_1=83, q_1=89</math> (соответственно <math>p_2=67, q_2=41</math>), модуль <math>n_1=7387</math> (соответственно <math>n_2=2747</math>). Открытая и закрытая экспоненты равны <math>e_1=5145, d_1=777</math> (соответственно <math>e_2=1421, d_2=2261</math>).

: '''Шаг 2.'''
:: '''B''' сообщает '''C''' восемь 12-битных чисел <math>x_i, 1 \leqslant i \leqslant 8 </math>: <math>x_1=743,</math> <math>x_2=1988,</math> <math>x_3=4001,</math> <math>x_4=2942,</math> <math>x_5=3421,</math> <math>x_6=2210,</math> <math>x_7=2306,</math> <math>x_8=912.</math>
:: '''C''' сообщает '''B''' восемь 12-битных чисел <math>x'_i, 1 \leqslant i \leqslant 8 </math>: <math>x'_1=1708,</math> <math>x'_2=711,</math> <math>x'_3=1969,</math> <math>x'_4=3112,</math> <math>x'_5=4014,</math> <math>x'_6=2308,</math> <math>x'_7=2212,</math> <math>x'_8=222.</math>

: '''Шаг 3.'''
:: Пусть '''B''' хочет купить секрет <math>s_7</math>. Он вычисляет

<center><math>f(x'_7)=(x'_7)^{e_1}\pmod {n_1}=2212^{5145}\pmod {7387}=5928.</math></center>

:: Сравнивая [[Двоичная система счисления|бинарное представление]] <math>x'_7</math> и <math>f(x'_7),</math>

<center><math>2212 = 0100010100100</math></center>
<center><math>5928 = 1011100101000</math></center>

:: '''B''' сообщает '''C''' набор ИФБ<math>_B=\{0,1,4,5,6\}</math> соответствующих <math>(x'_7,f).</math>
:: Пусть '''C''' хочет купить секрет <math>s_2</math>. После вычислений, '''C''' сообщает '''B''' набор ИФБ<math>_C=\{0,1,2,6,9,10\}</math> соответствующих <math>(x_2,g).</math>

: '''Шаг 4.'''
:: '''B''' сообщает '''S''' числа <math>y_i, 1 \leqslant i \leqslant 8</math>, где <math>y_i</math> — результат, полученный заменой каждого бита в <math>x_i</math>, чей индекс не принадлежит <math>\{0,1,2,6,9,10\}</math>, на противоположный, например:
<center><math>y_2=0110011111100=1660.</math></center>

:: '''C''' сообщает '''S''' числа <math>y'_i, 1 \leqslant i \leqslant 8</math>, где <math>y'_i</math> — результат, полученный заменой каждого бита в <math>x'_i</math>, чей индекс не принадлежит <math>\{0,1,4,5,6\}</math>, на противоположный, например:

<center><math>y'_7=1011100101000=5928.</math></center>

: '''Шаг 5.'''
:: '''S''' сообщает '''B''' числа <math>s_i \oplus f^{-1}(y'_i), 1 \leqslant i \leqslant 8 (</math>обратная функция <math>f^{-1}(y')=y'^{d_1}\pmod {n_1}=y'^{777}\pmod {7387})</math>, например:

<center><math>s_7=2546=0100111110010</math></center>
<center><math>f^{-1}(y'_7)=2212=0100010100100</math></center>
<center><math>s_7 \oplus f^{-1}(y'_7)=0000101010110=\boldsymbol{342}</math></center>

:: '''S''' сообщает '''C''' числа <math>s_i \oplus g^{-1}(y_i), 1 \leqslant i \leqslant 8 (</math>обратная функция <math>g^{-1}(y)=y^{d_2}\pmod {n_2}=y^{2261}\pmod {2747})</math>, например.

<center><math>s_2=471=000111010111</math></center>
<center><math>g^{-1}(y_2)=1988=011111000100</math></center>
<center><math>s_2 \oplus g^{-1}(y_2)=011000010011=\boldsymbol{1555}</math></center>

: '''Шаг 6.'''
:: '''B''' узнаёт секрет <math>s_7</math>, побитовым сложение <math>x'_7</math> и 7-го числа, полученного от '''S''', а именно:

<center><math>x'_7=2212=100010100100</math></center>
<center><math>342=000101010110</math></center>
<center><math>x'_7 \oplus 342)=100111110010=\boldsymbol{2546}</math></center>.

:: Если '''C''' хочет купить секрет <math>s_2</math>, то он вычисляет побитовое сложение <math>x_2</math> и 2-го числа, полученного от '''S''', а именно:

<center><math>x_2=1988=11111000100</math></center>
<center><math>1555=11000010011</math></center>
<center><math>x_2 \oplus 1555)=00111010111=\boldsymbol{471}</math></center>.

== Литература ==
* {{статья|автор=G.Brassard, C.Crepeau and J.-M. Robert|заглавие=All-or-nothing disclosure of secrets|ссылка=http://cactus.eas.asu.edu/partha/Teaching/539-CommonFiles/ANDOS.PDF|язык=en|издание=Springer Lecture Notes in Computer Science 263(1987)|archiveurl=https://web.archive.org/web/20160304195606/http://cactus.eas.asu.edu/partha/Teaching/539-CommonFiles/ANDOS.PDF|archivedate=2016-03-04}}
* {{статья|автор=A.Salomaa and L.Santean|заглавие=Secret selling of secrets with many buyers|ссылка=http://cactus.eas.asu.edu/partha/Teaching/539-CommonFiles/ANDOS.PDF|язык=en|издание=EATCS Bulletin 42(1990))|archiveurl=https://web.archive.org/web/20160304195606/http://cactus.eas.asu.edu/partha/Teaching/539-CommonFiles/ANDOS.PDF|archivedate=2016-03-04}}

{{нет сносок|дата=2014-10-30}}
{{rq|wikify}}

[[Категория:Криптографические протоколы]]