Меню Главная Случайная статья Настройки Схема Асмута — Блума Материал из https://ru.wikipedia.org Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между ${\displaystyle n}$ сторонами таким образом, что его смогут восстановить любые ${\displaystyle m}$ участников. Содержание 1 Описание 1.1 Пример 2 Обобщенная схема Асмута – Блума в кольце многочленов от нескольких переменных 3 Совершенность схемы 4 Литература Описание Пусть ${\displaystyle M}$ — некоторый секрет, который требуется разделить. Выбирается простое число ${\displaystyle p}$, большее ${\displaystyle M}$. Выбирается ${\displaystyle n}$ взаимно простых друг с другом чисел ${\displaystyle d_{1},d_{2},\dots ,d_{n}}$, таких что: ${\displaystyle \forall i:d_{i}>p}$ ${\displaystyle \forall i:d_{i}<d_{i+1}}$ ${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n}}$ Выбирается случайное число ${\displaystyle r}$ и вычисляется ${\displaystyle M'=M+rp}$ Вычисляются доли: ${\displaystyle k_{i}=M'\mod d_{i}}$ Участникам раздаются ${\displaystyle \left\{p,d_{i},k_{i}\right\}}$ Теперь, используя китайскую теорему об остатках, можно восстановить секрет ${\displaystyle M}$, имея ${\displaystyle m}$ и более долей. Пример Предположим, что нам нужно разделить секрет ${\displaystyle M=2}$ между четырьмя участниками таким образом, чтобы любые три из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему. В качестве простого числа выберем ${\displaystyle p=3}$, в качестве взаимно простых — ${\displaystyle 11,13,17,19}$. Проверяем, что: ${\displaystyle \forall i:d_{i}>p}$ ${\displaystyle \forall i:i\in \{11,13,17,19\},i>p=3}$ ${\displaystyle d_{1}<d_{2}<d_{3}<d_{4}}$ ${\displaystyle 11<13<17<19}$ ${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n}}$ ${\displaystyle d_{1}*d_{2}*d_{3}>p*d_{3}*d_{4}}$ ${\displaystyle 11*13*17>3*17*19}$ Выбираем случайное число ${\displaystyle r=51}$ и вычисляем: ${\displaystyle M'=M+rp=2+51*3=155}$ Вычисляем доли: ${\displaystyle k_{i}=M'\mod d_{i}}$ ${\displaystyle k_{1}=155\mod 11=1}$ ${\displaystyle k_{2}=155\mod 13=12}$ ${\displaystyle k_{3}=155\mod 17=2}$ ${\displaystyle k_{4}=155\mod 19=3}$ Теперь попробуем восстановить исходный секрет, имея на руках доли ${\displaystyle \left\{3,11,1\right\}}$, ${\displaystyle \left\{3,13,12\right\}}$, ${\displaystyle \left\{3,17,2\right\}}$. Составим систему уравнений: ${\displaystyle 1=M'\mod 11}$ ${\displaystyle 12=M'\mod 13}$ ${\displaystyle 2=M'\mod 17}$ Мы можем восстановить ${\displaystyle M'}$, используя китайскую теорему об остатках. Зная ${\displaystyle M'}$, мы восстанавливаем секрет. ${\displaystyle M\equiv M'\mod p}$ ${\displaystyle M\equiv 155\mod 3\equiv 2}$ В данном примере (так как 155<17*19) два участника спокойно восстановят секрет. M' должно быть больше произведения долей неавторизованных участников. Обобщенная схема Асмута – Блума в кольце многочленов от нескольких переменных Рассмотрим кольцо многочленов от нескольких переменных ${\displaystyle \mathbb {F} _{q}[X]}$, ${\displaystyle X=(x_{1},\cdots ,x_{n})}$ над полем Галуа ${\displaystyle \mathbb {F} _{q}}$. Пусть зафиксирован некоторый мономиальный порядок. Тогда приведение многочлена по модулю идеала определено однозначно. Пусть ${\displaystyle I_{1},I_{2},\cdots ,I_{t}}$ – нульмерные идеалы, а ${\displaystyle s_{1}(X),s_{2}(X),\cdots ,s_{t}(X)\in \mathbb {F} _{q}[X]}$ — некоторые многочлены. Тогда справедливо утверждение: система сравнений ${\displaystyle {\begin{cases}c(X)&\equiv s_{1}(X)\ {\bmod {\ }}I_{1}\\c(X)&\equiv s_{2}(X)\ {\bmod {\ }}I_{2}\\&\vdots \\c(X)&\equiv s_{t}(X)\ {\bmod {\ }}I_{t}\\\end{cases}}}$ либо несовместна, либо имеет единственное решение по модулю наименьшего общего кратного(НОК) идеалов ${\displaystyle I_{1},I_{2},\cdots ,I_{t}}$ . В случае, если идеалы попарно взаимно простые, т. е. ${\displaystyle I_{i}+I_{j}=1,\forall i\neq j}$, имеем обобщенную китайскую теорему об остатках, причем решение системы всегда существует. Рассмотрим сначала обобщение схемы Миньотта. Секретом будет некоторый многочлен ${\displaystyle C(X)}$ , участнику ${\displaystyle i}$ выдается модуль ${\displaystyle I_{i}}$ и частичный секрет ${\displaystyle s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}}$ . Для реализации структуры доступа необходимо и достаточно, чтобы секрет ${\displaystyle C(X)}$ был приведенным по модулю НОК идеалов из любого разрешенного подмножества участников и не являлся таковым для запрещенных подмножеств. В обобщенной схеме Асмута – Блума присутствует дополнительный модуль ${\displaystyle I_{0}}$ , а секретом является ${\displaystyle s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}}$ . В этой схеме ${\displaystyle C(X)}$ называется промежуточным секретом. Совершенность схемы Схема разделения секрета называется совершенной, если запрещенное подмножество участников не получает никакой дополнительной информации о секрете, кроме априорной. Другими словами, распределение секрета остается равномерным и при наличии частичных секретов участников из запрещенного подмножества. Схема Асмута – Блума в отличие от схемы Миньотта может быть совершенной. Для выработки критерия совершенности, исследуем схему Асмута – Блума в кольце ${\displaystyle \mathbb {F} _{q}[X]}$. Обозначим через ${\displaystyle RT(I)}$ множество мономов, приведенных по модулю ${\displaystyle I}$, а через ${\displaystyle RP(I)}$ – линейную оболочку ${\displaystyle RT(I)}$. Пусть также ${\displaystyle I^{B}={\mbox{HOK}}[I_{i},i\in B],\ M_{2}=\bigcap _{B\in \Gamma }RT(I^{B})}$ – множество мономов, лежащих в пересечении ${\displaystyle RT}$ идеалов всех разрешенных подмножеств. Отметим, что промежуточный секрет ${\displaystyle C(X)\in RP(M_{2})}$. Теорема. Схема Асмута – Блума в кольце ${\displaystyle \mathbb {F} _{q}[X]}$ совершенна тогда и только тогда, когда выполнены следующие условия: 1) ${\displaystyle I_{0}+I_{i}=1,\forall i\in J}$. 2) ${\displaystyle \forall A\notin \Gamma :RT(I^{A}I_{0})\subseteq M_{2}}$. Доказательство. Необходимость. Пусть есть совершенная схема Асмута – Блума, но первое условие теоремы не выполнено, т. е. ${\displaystyle \exists I_{i}:I_{i}+I_{0}=D\neq 0}$. Тогда множество возможных значений секрета для такого участника можно сузить: ${\displaystyle c(X)\equiv s_{i}(X)\ {\bmod {\ }}D}$. Следовательно, схема несовершенна – получили противоречие. Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество ${\displaystyle A}$ такое, что ${\displaystyle RT(I^{A}I_{0})\not \subset M_{2}}$. Иными словами, существует моном ${\displaystyle m\in RT(I^{A}I_{0})\backslash M_{2}}$. Рассмотрим многочлен ${\displaystyle g(X)=s^{A}(X)+(m-m({\bmod {I}}^{A}))=s^{A}(X)+f_{m}(X),}$ где ${\displaystyle s^{A}(X)}$ – общий частичный секрет, восстановленный участниками из подмножества ${\displaystyle A}$. Заметим, что многочлен ${\displaystyle f_{m}(X)}$ тогда удовлетворяет следующим условиям: 1) ${\displaystyle f_{m}(X)\in I^{A}}$ 2) ${\displaystyle f_{m}(X)\in RP(I^{A}I_{0})}$ 3) Содержит моном ${\displaystyle m}$. Следовательно, ${\displaystyle g(X)\in RP(I^{A}I_{0})}$. Положим ${\displaystyle c'=g(X)\ {\bmod {\ }}I_{0}}$. Согласно китайской теореме об остатках, для системы ${\displaystyle {\begin{cases}C(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}\\C(X)\equiv c'(X)\ {\bmod {\ }}I_{0}\\\end{cases}}}$ существует единственное решение в ${\displaystyle RP(I^{A}I_{0})}$, но по построению этим решением является многочлен ${\displaystyle g(X)}$. С другой стороны, ${\displaystyle m\in g(X)\notin RP(M_{2})}$, а значит, значение ${\displaystyle c'(X)}$ для секрета невозможно – опять получили противоречие. Достаточность. Пусть условия теоремы выполнены. Покажем, что секрет остается равномерно распределенным и при наличии частичных секретов из запрещенного подмножества. Рассмотрим произвольное запрещенное подмножество ${\displaystyle A\notin \Gamma }$ и множество многочленов ${\displaystyle V=\{s^{A}(X)+f(X)|f(X)\in I^{A},f(X)\in LP(M_{2})\}}$ — множество возможных значений промежуточного секрета. Зафиксируем некоторое значение секрета ${\displaystyle c^{j}(X)\in RP(I_{0})}$.Тогда существует единственный многочлен ${\displaystyle g^{j}(X)\in LP(I^{A}I_{0})}$, такой, что согласно китайской теореме об остатках ${\displaystyle g^{j}(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}}$ ${\displaystyle g^{j}(X)\equiv c^{j}(X)\ {\bmod {\ }}I_{0}}$ Рассмотрим теперь 2 случая: 1) Если ${\displaystyle RT(I^{A}I_{0})=M_{2}}$, то каждому значения секрета соответствует единственный промежуточный секрет из множества ${\displaystyle V}$, т.е. секрет остается равномерно распределенным при наличии частичных секретов из подмножества ${\displaystyle A}$. 2) Пусть тогда ${\displaystyle RT(I^{A}I_{0})\subset M_{2}}$. Каждому многочлену ${\displaystyle f(X)\in RP(M_{2})}$, содержащему хотя бы один моном из ${\displaystyle M_{2}\setminus RT(I^{A}I_{0})}$, поставим в соответствие многочлен ${\displaystyle {\overline {f}}(X)=f(X)-f(X)\ {\bmod {\ }}RT(I^{A}I_{0})\neq 0}$ Очевидно, что ${\displaystyle {\overline {f}}(X)\in I^{A}I_{0}}$. Тогда каждому значению секрета ${\displaystyle c^{j}(X)\in RP(I_{0})}$ соответствует множество промежуточных секретов ${\displaystyle C^{j}=\{g^{j}(X),g^{j}(X)+{\overline {f}}(X)|{\overline {f}}(X)\in I^{A}I_{0},{\overline {f}}(X)\in RP(M_{2})\}\subset V}$ Очевидно, что множества ${\displaystyle C^{j}}$ равномощные. Следовательно, в множестве ${\displaystyle V}$ для каждого значения секрета существует одинаковое число возможных значений промежуточного секрета, что влечет равномерное распределение секрета и при наличии частичных секретов из запрещенного подмножества. Теорема доказана. Литература Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4. Asmuth C., Bloom J. A modular approach to key safeguarding (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1983.1056651 Шенец Н. Н. Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных // Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. — Минск: БГУ, 2011. — Т. 1. Статьи факультета прикладной математики и информатики. — С. 169—173. — ISBN 978-985-518-563-6