Схема Асмута — Блума

Поделись знанием:
Перейти к: навигация, поиск

Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между <math>n</math> сторонами таким образом, что его смогут восстановить любые <math>m</math> участников.





Описание

Пусть <math>M</math> — некоторый секрет, который требуется разделить. Выбирается простое число <math>p</math>, большее <math>M</math>. Выбирается <math>n</math> взаимно простых друг с другом чисел <math>d_1, d_2, \dots, d_n</math>, таких что:

  • <math>\forall i:d_i > p</math>
  • <math>\forall i:d_i < d_{i+1}</math>
  • <math>d_1 * d_2 * \dots d_m > p * d_{n-m+2} * d_{n-m+3} * \dots * d_n</math>

Выбирается случайное число <math>r</math> и вычисляется

<math>M' = M + r p </math>

Вычисляются доли:

<math>k_i = M' \mod d_i</math>

Участникам раздаются <math>\left\{p, d_i, k_i\right\}</math>

Теперь, используя китайскую теорему об остатках, можно восстановить секрет <math>M</math>, имея <math>m</math> и более долей.

Пример

Предположим, что нам нужно разделить секрет <math>M=2</math> между четырьмя участниками таким образом, чтобы любые три из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему.

В качестве простого числа выберем <math>p=3</math>, в качестве взаимно простых — <math>11, 13, 17, 19</math>. Проверяем, что:

  • <math>\forall i:d_i > p</math>
    <math>\forall i: i \in \{11, 13, 17, 19\}, i > p = 3</math>
  • <math>d_1 < d_2 < d_3 < d_4</math>
    <math>11 < 13 < 17 < 19</math>
  • <math>d_1 * d_2 * \dots d_m > p * d_{n-m+2} * d_{n-m+3} * \dots * d_n</math>
    <math>d_1 * d_2 * d_3 > p * d_3 * d_4</math>
    <math>11 * 13 * 17 > 3 * 17 * 19</math>

Выбираем случайное число <math>r = 51</math> и вычисляем:

<math>M' = M + r p = 2 + 51 * 3 = 155</math>

Вычисляем доли:

<math>k_i = M' \mod d_i</math>
<math>k_1 = 155 \mod 11 = 1</math>
<math>k_2 = 155 \mod 13 = 12</math>
<math>k_3 = 155 \mod 17 = 2</math>
<math>k_4 = 155 \mod 19 = 3</math>

Теперь попробуем восстановить исходный секрет, имея на руках доли <math>\left\{3, 11, 1\right\}</math>, <math>\left\{3, 13, 12\right\}</math>, <math>\left\{3, 17, 2\right\}</math>. Составим систему уравнений:

<math>1 = M' \mod 11</math>
<math>12 = M' \mod 13</math>
<math> 2 = M' \mod 17</math>

Мы можем восстановить <math>M'</math>, используя китайскую теорему об остатках.

Зная <math>M'</math>, мы восстанавливаем секрет.

<math>M \equiv M' \mod p</math>
<math>M \equiv 155 \mod 3 \equiv 2 </math>

В данном примере (так как 155<17*19) два участника спокойно восстановят секрет. M' должно быть больше произведения долей неавторизованных участников.

Обобщенная схема Асмута – Блума в кольце многочленов от нескольких переменных

Рассмотрим кольцо многочленов от нескольких переменных <math>\mathbb{F}_q[X]</math>, <math>X=(x_1,\cdots,x_n)</math> над полем Галуа <math>\mathbb{F}_q</math>. Пусть зафиксирован некоторый мономиальный порядок. Тогда приведение многочлена по модулю идеала определено однозначно. Пусть <math>I_1,I_2,\cdots,I_t</math> – нульмерные идеалы, а <math>s_1(X),s_2(X),\cdots,s_t(X)\in\mathbb{F}_q[X]</math> — некоторые многочлены. Тогда справедливо утверждение: система сравнений

<math>\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}</math>

либо несовместна, либо имеет единственное решение по модулю наименьшего общего кратного(НОК) идеалов <math>I_1,I_2,\cdots,I_t</math> . В случае, если идеалы попарно взаимно простые, т. е. <math>I_i + I_j =1, \forall i \ne j</math>, имеем обобщенную китайскую теорему об остатках, причем решение системы всегда существует.

Рассмотрим сначала обобщение схемы Миньотта. Секретом будет некоторый многочлен <math>C(X)</math> , участнику <math>i</math> выдается модуль <math>I_i</math> и частичный секрет <math>s_i (X) = C (X)\ \bmod \ I_i</math> . Для реализации структуры доступа необходимо и достаточно, чтобы секрет <math>C(X)</math> был приведенным по модулю НОК идеалов из любого разрешенного подмножества участников и не являлся таковым для запрещенных подмножеств.

В обобщенной схеме Асмута – Блума присутствует дополнительный модуль <math>I_0</math> , а секретом является <math>s_i (X) = C (X)\ \bmod \ I_i</math> . В этой схеме <math>C(X)</math> называется промежуточным секретом.

Совершенность схемы

Схема разделения секрета называется совершенной, если запрещенное подмножество участников не получает никакой дополнительной информации о секрете, кроме априорной. Другими словами, распределение секрета остается равномерным и при наличии частичных секретов участников из запрещенного подмножества. Схема Асмута – Блума в отличие от схемы Миньотта может быть совершенной.

Для выработки критерия совершенности, исследуем схему Асмута – Блума в кольце <math>\mathbb{F}_q[X]</math>. Обозначим через <math>RT(I)</math> множество мономов, приведенных по модулю <math>I</math>, а через <math>RP(I)</math> – линейную оболочку <math>RT(I)</math>. Пусть также

<math>I^B=\mbox{HOK}[I_i,i\in B], \ M_2=\bigcap_{B\in \Gamma}RT(I^B)</math>

– множество мономов, лежащих в пересечении <math>RT</math> идеалов всех разрешенных подмножеств. Отметим, что промежуточный секрет <math>C(X) \in RP(M_2)</math>.

Теорема. Схема Асмута – Блума в кольце <math>\mathbb{F}_q[X]</math> совершенна тогда и только тогда, когда выполнены следующие условия:

1) <math>I_0 + I_i =1, \forall i \in J</math>.
2) <math>\forall A \notin \Gamma :RT(I^A I_0) \subseteq M_2</math>.

Доказательство.

Необходимость. Пусть есть совершенная схема Асмута – Блума, но первое условие теоремы не выполнено, т. е. <math>\exists I_i:I_i + I_0 =D \ne 0</math>. Тогда множество возможных значений секрета для такого участника можно сузить: <math>c(X) \equiv s_i (X) \ \bmod \ D</math>. Следовательно, схема несовершенна – получили противоречие.

Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество <math>A</math> такое, что <math>RT(I^A I_0) \not\subset M_2</math>. Иными словами, существует моном <math>m\in RT(I^A I_0)\backslash M_2</math>. Рассмотрим многочлен

<math>g(X)=s^A(X)+(m-m(\bmod I^A))=s^A(X)+f_m(X),</math>

где <math>s^A(X)</math> – общий частичный секрет, восстановленный участниками из подмножества <math>A</math>.

Заметим, что многочлен <math>f_m(X)</math> тогда удовлетворяет следующим условиям:

1) <math>f_m(X) \in I^A</math>
2) <math>f_m(X) \in RP(I^A I_0)</math>
3) Содержит моном <math>m</math>.

Следовательно, <math>g(X) \in RP(I^A I_0)</math>. Положим <math>c'=g(X) \ \bmod \ I_0</math>. Согласно китайской теореме об остатках, для системы

<math>\begin{cases}

C (X) \equiv s^A (X) \ \bmod \ I^A \\ C (X) \equiv c' (X) \ \bmod \ I_0 \\ \end{cases}</math>

существует единственное решение в <math>RP(I^A I_0)</math>, но по построению этим решением является многочлен <math>g(X)</math>. С другой стороны, <math>m \in g(X) \notin RP(M_2)</math>, а значит, значение <math>c'(X)</math> для секрета невозможно – опять получили противоречие.

Достаточность. Пусть условия теоремы выполнены. Покажем, что секрет остается равномерно распределенным и при наличии частичных секретов из запрещенного подмножества. Рассмотрим произвольное запрещенное подмножество <math>A \notin \Gamma</math> и множество многочленов

<math>V= \{ s^A(X)+f(X)|f(X) \in I^A, f(X) \in LP(M_2) \} </math>

— множество возможных значений промежуточного секрета.

Зафиксируем некоторое значение секрета <math>c^j(X) \in RP(I_0)</math>.Тогда существует единственный многочлен <math>g^j(X) \in LP(I^A I_0)</math>, такой, что согласно китайской теореме об остатках

<math>g^j(X) \equiv s^A(X) \ \bmod \ I^A</math>
<math>g^j(X) \equiv c^j(X) \ \bmod \ I_0</math>

Рассмотрим теперь 2 случая:

1) Если <math>RT(I^A I_0)=M_2</math>, то каждому значения секрета соответствует единственный промежуточный секрет из множества <math>V</math>, т.е. секрет остается равномерно распределенным при наличии частичных секретов из подмножества <math>A</math>.

2) Пусть тогда <math>RT(I^A I_0) \subset M_2</math>. Каждому многочлену <math>f(X) \in RP(M_2)</math>, содержащему хотя бы один моном из <math>M_2 \setminus RT(I^A I_0)</math>, поставим в соответствие многочлен

<math>\overline{f}(X) = f(X) - f(X)\ \bmod \ RT(I^A I_0) \ne 0</math>

Очевидно, что <math>\overline{f}(X) \in I^A I_0</math>. Тогда каждому значению секрета <math>c^j(X) \in RP(I_0)</math> соответствует множество промежуточных секретов

<math>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</math>

Очевидно, что множества <math>C^j</math> равномощные. Следовательно, в множестве <math>V</math> для каждого значения секрета существует одинаковое число возможных значений промежуточного секрета, что влечет равномерное распределение секрета и при наличии частичных секретов из запрещенного подмножества.

Теорема доказана.

Напишите отзыв о статье "Схема Асмута — Блума"

Литература

  • Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • C. Asmuth, J. Bloom A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — Т. 29, вып. 2. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0018-9448&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0018-9448].
  • Шенец, Н. Н. [elib.bsu.by/handle/123456789/9565 Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных] // БГУ. — 2011. — ISBN 978-985-518-563-6.
  • Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — P. 512. — ISBN 978-1584885085.

Отрывок, характеризующий Схема Асмута — Блума

Ритор прокашлялся, сложил на груди руки в перчатках и начал говорить:
– Теперь я должен открыть вам главную цель нашего ордена, – сказал он, – и ежели цель эта совпадает с вашею, то вы с пользою вступите в наше братство. Первая главнейшая цель и купно основание нашего ордена, на котором он утвержден, и которого никакая сила человеческая не может низвергнуть, есть сохранение и предание потомству некоего важного таинства… от самых древнейших веков и даже от первого человека до нас дошедшего, от которого таинства, может быть, зависит судьба рода человеческого. Но так как сие таинство такого свойства, что никто не может его знать и им пользоваться, если долговременным и прилежным очищением самого себя не приуготовлен, то не всяк может надеяться скоро обрести его. Поэтому мы имеем вторую цель, которая состоит в том, чтобы приуготовлять наших членов, сколько возможно, исправлять их сердце, очищать и просвещать их разум теми средствами, которые нам преданием открыты от мужей, потрудившихся в искании сего таинства, и тем учинять их способными к восприятию оного. Очищая и исправляя наших членов, мы стараемся в третьих исправлять и весь человеческий род, предлагая ему в членах наших пример благочестия и добродетели, и тем стараемся всеми силами противоборствовать злу, царствующему в мире. Подумайте об этом, и я опять приду к вам, – сказал он и вышел из комнаты.
– Противоборствовать злу, царствующему в мире… – повторил Пьер, и ему представилась его будущая деятельность на этом поприще. Ему представлялись такие же люди, каким он был сам две недели тому назад, и он мысленно обращал к ним поучительно наставническую речь. Он представлял себе порочных и несчастных людей, которым он помогал словом и делом; представлял себе угнетателей, от которых он спасал их жертвы. Из трех поименованных ритором целей, эта последняя – исправление рода человеческого, особенно близка была Пьеру. Некое важное таинство, о котором упомянул ритор, хотя и подстрекало его любопытство, не представлялось ему существенным; а вторая цель, очищение и исправление себя, мало занимала его, потому что он в эту минуту с наслаждением чувствовал себя уже вполне исправленным от прежних пороков и готовым только на одно доброе.
Через полчаса вернулся ритор передать ищущему те семь добродетелей, соответствующие семи ступеням храма Соломона, которые должен был воспитывать в себе каждый масон. Добродетели эти были: 1) скромность , соблюдение тайны ордена, 2) повиновение высшим чинам ордена, 3) добронравие, 4) любовь к человечеству, 5) мужество, 6) щедрость и 7) любовь к смерти.
– В седьмых старайтесь, – сказал ритор, – частым помышлением о смерти довести себя до того, чтобы она не казалась вам более страшным врагом, но другом… который освобождает от бедственной сей жизни в трудах добродетели томившуюся душу, для введения ее в место награды и успокоения.
«Да, это должно быть так», – думал Пьер, когда после этих слов ритор снова ушел от него, оставляя его уединенному размышлению. «Это должно быть так, но я еще так слаб, что люблю свою жизнь, которой смысл только теперь по немногу открывается мне». Но остальные пять добродетелей, которые перебирая по пальцам вспомнил Пьер, он чувствовал в душе своей: и мужество , и щедрость , и добронравие , и любовь к человечеству , и в особенности повиновение , которое даже не представлялось ему добродетелью, а счастьем. (Ему так радостно было теперь избавиться от своего произвола и подчинить свою волю тому и тем, которые знали несомненную истину.) Седьмую добродетель Пьер забыл и никак не мог вспомнить ее.
В третий раз ритор вернулся скорее и спросил Пьера, всё ли он тверд в своем намерении, и решается ли подвергнуть себя всему, что от него потребуется.
– Я готов на всё, – сказал Пьер.
– Еще должен вам сообщить, – сказал ритор, – что орден наш учение свое преподает не словами токмо, но иными средствами, которые на истинного искателя мудрости и добродетели действуют, может быть, сильнее, нежели словесные токмо объяснения. Сия храмина убранством своим, которое вы видите, уже должна была изъяснить вашему сердцу, ежели оно искренно, более нежели слова; вы увидите, может быть, и при дальнейшем вашем принятии подобный образ изъяснения. Орден наш подражает древним обществам, которые открывали свое учение иероглифами. Иероглиф, – сказал ритор, – есть наименование какой нибудь неподверженной чувствам вещи, которая содержит в себе качества, подобные изобразуемой.
Пьер знал очень хорошо, что такое иероглиф, но не смел говорить. Он молча слушал ритора, по всему чувствуя, что тотчас начнутся испытанья.
– Ежели вы тверды, то я должен приступить к введению вас, – говорил ритор, ближе подходя к Пьеру. – В знак щедрости прошу вас отдать мне все драгоценные вещи.
– Но я с собою ничего не имею, – сказал Пьер, полагавший, что от него требуют выдачи всего, что он имеет.
– То, что на вас есть: часы, деньги, кольца…
Пьер поспешно достал кошелек, часы, и долго не мог снять с жирного пальца обручальное кольцо. Когда это было сделано, масон сказал:
– В знак повиновенья прошу вас раздеться. – Пьер снял фрак, жилет и левый сапог по указанию ритора. Масон открыл рубашку на его левой груди, и, нагнувшись, поднял его штанину на левой ноге выше колена. Пьер поспешно хотел снять и правый сапог и засучить панталоны, чтобы избавить от этого труда незнакомого ему человека, но масон сказал ему, что этого не нужно – и подал ему туфлю на левую ногу. С детской улыбкой стыдливости, сомнения и насмешки над самим собою, которая против его воли выступала на лицо, Пьер стоял, опустив руки и расставив ноги, перед братом ритором, ожидая его новых приказаний.
– И наконец, в знак чистосердечия, я прошу вас открыть мне главное ваше пристрастие, – сказал он.
– Мое пристрастие! У меня их было так много, – сказал Пьер.
– То пристрастие, которое более всех других заставляло вас колебаться на пути добродетели, – сказал масон.
Пьер помолчал, отыскивая.
«Вино? Объедение? Праздность? Леность? Горячность? Злоба? Женщины?» Перебирал он свои пороки, мысленно взвешивая их и не зная которому отдать преимущество.
– Женщины, – сказал тихим, чуть слышным голосом Пьер. Масон не шевелился и не говорил долго после этого ответа. Наконец он подвинулся к Пьеру, взял лежавший на столе платок и опять завязал ему глаза.
– Последний раз говорю вам: обратите всё ваше внимание на самого себя, наложите цепи на свои чувства и ищите блаженства не в страстях, а в своем сердце. Источник блаженства не вне, а внутри нас…
Пьер уже чувствовал в себе этот освежающий источник блаженства, теперь радостью и умилением переполнявший его душу.


Скоро после этого в темную храмину пришел за Пьером уже не прежний ритор, а поручитель Вилларский, которого он узнал по голосу. На новые вопросы о твердости его намерения, Пьер отвечал: «Да, да, согласен», – и с сияющею детскою улыбкой, с открытой, жирной грудью, неровно и робко шагая одной разутой и одной обутой ногой, пошел вперед с приставленной Вилларским к его обнаженной груди шпагой. Из комнаты его повели по коридорам, поворачивая взад и вперед, и наконец привели к дверям ложи. Вилларский кашлянул, ему ответили масонскими стуками молотков, дверь отворилась перед ними. Чей то басистый голос (глаза Пьера всё были завязаны) сделал ему вопросы о том, кто он, где, когда родился? и т. п. Потом его опять повели куда то, не развязывая ему глаз, и во время ходьбы его говорили ему аллегории о трудах его путешествия, о священной дружбе, о предвечном Строителе мира, о мужестве, с которым он должен переносить труды и опасности. Во время этого путешествия Пьер заметил, что его называли то ищущим, то страждущим, то требующим, и различно стучали при этом молотками и шпагами. В то время как его подводили к какому то предмету, он заметил, что произошло замешательство и смятение между его руководителями. Он слышал, как шопотом заспорили между собой окружающие люди и как один настаивал на том, чтобы он был проведен по какому то ковру. После этого взяли его правую руку, положили на что то, а левою велели ему приставить циркуль к левой груди, и заставили его, повторяя слова, которые читал другой, прочесть клятву верности законам ордена. Потом потушили свечи, зажгли спирт, как это слышал по запаху Пьер, и сказали, что он увидит малый свет. С него сняли повязку, и Пьер как во сне увидал, в слабом свете спиртового огня, несколько людей, которые в таких же фартуках, как и ритор, стояли против него и держали шпаги, направленные в его грудь. Между ними стоял человек в белой окровавленной рубашке. Увидав это, Пьер грудью надвинулся вперед на шпаги, желая, чтобы они вонзились в него. Но шпаги отстранились от него и ему тотчас же опять надели повязку. – Теперь ты видел малый свет, – сказал ему чей то голос. Потом опять зажгли свечи, сказали, что ему надо видеть полный свет, и опять сняли повязку и более десяти голосов вдруг сказали: sic transit gloria mundi. [так проходит мирская слава.]