ANDOS (криптография)

Шаблон:Другие значения Шаблон:Underlinked ANDOS (Шаблон:Lang-en) — криптографический протокол «секретной продажи секретов». Пусть продавец S секретов имеет некий список вопросов и выставляет на продажу ответы к любому из них. Предположим, покупатель B хочет купить секрет, но не хочет раскрывать какой именно. Протокол гарантирует, что B получит нужный ему секрет и ничего более, в то время как S не будет знать какой именно секрет получил B.

Алгоритм

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

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

Шаг 2. B сообщает C (соответственно C — B) $k$ случайных $n$-битных чисел $x_1,...,x_k$ (соответственно $x_{1^{\prime }},...,x_{k^{\prime }}$).

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

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

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

Шаг 5. S сообщает B (соответственно C) числа

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

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

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

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

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

Примеры

• За основу односторонних функций $f$ и $g$ возьмём RSA.

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

$s_1=1990,$ $s_2=471,$ $s_3=3860,$ $s_4=1487,$ $s_5=2235,$ $s_6=3751,$ $s_7=2546,$ $s_8=4043.$

Шаг 1.

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

Шаг 2.

B сообщает C восемь 12-битных чисел $x_i,1⩽i⩽8$: $x_1=743,$ $x_2=1988,$ $x_3=4001,$ $x_4=2942,$ $x_5=3421,$ $x_6=2210,$ $x_7=2306,$ $x_8=912.$

C сообщает B восемь 12-битных чисел $x{\text{'}}_i,1⩽i⩽8$: $x{\text{'}}_1=1708,$ $x{\text{'}}_2=711,$ $x{\text{'}}_3=1969,$ $x{\text{'}}_4=3112,$ $x{\text{'}}_5=4014,$ $x{\text{'}}_6=2308,$ $x{\text{'}}_7=2212,$ $x{\text{'}}_8=222.$

Шаг 3.

Пусть B хочет купить секрет $s_7$. Он вычисляет

$f(x{\text{'}}_7)=(x{\text{'}}_7{)}^{e_1}(\mathrm{mod}{n}_1)=2212^{5145}(\mathrm{mod}7387)=5928.$

Сравнивая бинарное представление $x{\text{'}}_7$ и $f(x{\text{'}}_7),$

$2212=0100010100100$ $5928=1011100101000$

B сообщает C набор ИФБ${}_B=\{0,1,4,5,6\}$ соответствующих $(x{\text{'}}_7,f).$

Пусть C хочет купить секрет $s_2$. После вычислений, C сообщает B набор ИФБ${}_C=\{0,1,2,6,9,10\}$ соответствующих $(x_2,g).$

Шаг 4.

B сообщает S числа $y_i,1⩽i⩽8$, где $y_i$ — результат, полученный заменой каждого бита в $x_i$, чей индекс не принадлежит $\{0,1,2,6,9,10\}$, на противоположный, например:

$y_2=0110011111100=1660.$

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

$y{\text{'}}_7=1011100101000=5928.$

Шаг 5.

S сообщает B числа $s_i\oplus f^{-1}(y{\text{'}}_i),1⩽i⩽8($обратная функция $f^{-1}(y^{\prime })=y{\text{'}}^{d_1}(\mathrm{mod}{n}_1)=y{\text{'}}^{777}(\mathrm{mod}7387))$, например:

$s_7=2546=0100111110010$ $f^{-1}(y{\text{'}}_7)=2212=0100010100100$ $s_7\oplus f^{-1}(y{\text{'}}_7)=0000101010110=342$

S сообщает C числа $s_i\oplus g^{-1}(y_i),1⩽i⩽8($обратная функция $g^{-1}(y)=y^{d_2}(\mathrm{mod}{n}_2)=y^{2261}(\mathrm{mod}2747))$, например.

$s_2=471=000111010111$ $g^{-1}(y_2)=1988=011111000100$ $s_2\oplus g^{-1}(y_2)=011000010011=1555$

Шаг 6.

B узнаёт секрет $s_7$, побитовым сложение $x{\text{'}}_7$ и 7-го числа, полученного от S, а именно:

$x{\text{'}}_7=2212=100010100100$ $342=000101010110$ $x{\text{'}}_7\oplus 342)=100111110010=2546$

.

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

$x_2=1988=11111000100$ $1555=11000010011$ $x_2\oplus 1555)=00111010111=471$

.

Литература

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