Русская Википедия:ANDOS (криптография)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Другие значения Шаблон:Underlinked ANDOS (Шаблон:Lang-en) — криптографический протокол «секретной продажи секретов». Пусть продавец 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) числа

<math>s_i \oplus f^{-1}(y'_i)(</math> соответственно <math>s_i \oplus g^{-1}(y_i))</math> , <math>i=1,...,k</math>.

Шаг 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>. Он вычисляет

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

Сравнивая бинарное представление <math>x'_7</math> и <math>f(x'_7),</math>

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

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>, на противоположный, например:

<math>y_2=0110011111100=1660.</math>

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>, на противоположный, например:

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

Шаг 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>, например:

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

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>, например.

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

Шаг 6.

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

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

.

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

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

.

Литература

• Шаблон:Статья
• Шаблон:Статья